《数据结构》知识点
- 格式：docx
- 大小：31.82 KB
- 文档页数：9
第1章 绪论
1.1 数据是表示客观事物的符号，是对客观事物的抽象，是信息的载体。对计算机科学而言，经抽象(数字化)后，能被计算机识别、存储和加工处理的客观事物均称作数据。
1.2 具有某种共同属性的数据集合称作数据对象。数据集中的元素称作数据元素，简称元素，又称结点、顶点、记录等。
数据对象={数据元素，数据元素，…，数据元素}
1.3 就数据的自身结构而言，分为原子型和结构型，前者是不可分解或无须分解的数据，后者可分解为若干个数据项。
1.4 通常，数据项是无须分解或不可分解的所谓最小数据单位，数据元素是作为整体对待的基本数据单位。
1.5 数据集和其上定义的一组操作合称数据类型，即，
数据类型=数据集+一组操作=(数据集，一组操作)
[了解]狭义地说，数据类型侧重于数据的值，不区分值相同的数据，忽略数据的自身结构。
例. 复数类=(复数集，运算集)，复数集以复数为基本元素，复数由两个数据项组成：实部和虚部或模和幅角。
1.6 数据集和其元素间的一组关系合称数据结构，即，
数据结构=数据对象+数据关系=(数据对象，数据关系)
1.7 数据结构的抽象描述称作逻辑结构。逻辑结构分为：①集合结构；②线性结构；③树形结构(简称树结构)；④图形结构(简称图结构)。
1.8
树结构和图结构统称非线性结构。
1.9 数据结构在计算机上的具体实现称作存储结构或物理结构。存储结构分为：①顺序存储；②链式存储；③索引存储；④散列存储。
1.10 数据结构和其上定义的一组操作的抽象描述合称抽象数据类型，即，
抽象数据类型=数据结构+基本操作=数据对象+数据关系+基本操作
1.11
求解问题的步骤称作算法，是合法指令的有限序列，具有以下主要特性：①有穷性；②确定性；③可行性。
1.12 算法所用的总时间称作时间复杂度，通常用算法中执行次数最多(频度最高)的操作的执行次数(频度)或数量级表示。
时间复杂度又称时间效率，但两者的高低是相反的。
1.13 算法所用最大存储量称作空间复杂度。
空间复杂度又称空间效率，但两者的高低是相反的。
1.14 从数量级上说，算法的时间复杂度和空间复杂度与规模n的某个函数同级。常见数量级由低到高排列如下：
1、logan、nk、an、n!、nn (k>0,a>1)
对同一个具体问题，数据本身所用存储量与算法无关，通常，空间复杂度只考虑附加存储空间复杂度。
1.15 算法的性能分析主要包括时间复杂度和空间复杂度。
1.16 数据元素间的关系分为有序关系和无序关系。有序关系简称弧(或有向弧、有向边)，无序关系简称边(或无向弧、无向边)，分别表为:
、(元素，元素) 或 前驱 → 后继 、 元素 — 元素
1.17 k阶斐波那契序列的定义及其化简式。
f0=f1=…=fk-2=0，fk-1=1，n≥k时，fn=fn-1+fn-2+…+fn-k
1.18 一元多项式的高效计算式。
Pn(x)=p0+p1x+p2x2+…+pnxn=p0+x(p1+x(…Pn-1+xpn…))
递推算法为：for(P=p[n],i=n-1;i>=0;i--)(P*=x)+=p[i];
第2章 线性表
2.1 同类型元素的有限序列称作线性表。简记为(a1,a2,…,an) 或 a1,a2,…,an 或
({ai|i=1,2,…,n},{|i=1,2,…,n-1})
2.2 线性表中元素的个数称作表长，表长为0的线性表称作空表。
2.3 在线性表中，第一个元素称作首元，它没有前驱，其它元素均有唯一前驱；最后一个元素称作尾元，它没有后继，其它元素均有唯一后继。线性表的这种关系称作一对一关系，记作1:1。
例. 既有首元又有尾元的线性表的表长≥1，某元素既有前驱又有后继的线性表的表长≥3。
2.5 用连续的一片存储空间依次顺序存放线性表的元素，称作线性表的顺序存储，简称顺序表。 顺序表中逻辑相邻者的存储位置也相邻。
顺序表有三个要素：①基址；②表长(或尾元下标)；③预留表长(或最大下标)。
如果顺序表的预留表长是常量，可用普通数组存储(称作静态顺序表，只有两个要素)，否则，用动态数组存储(称作动态顺序表)。
对于顺序表，附加存储空间复杂度为O(1)，插入、删除、查找操作的时间复杂度为O(n)，其它基本操作的时间复杂度均为O(1)。
2.6 附加“链”将逻辑相邻数据元素的存储位置链接起来的存储结构称作链式存储。
链式存储的线性表称作线性链表，简称链表。
附加一个链的线性链表称作单链表。习惯上，链域指向其后继。
单链表中第一个结点的地址称作头指针。
作为线性链表首元的形式前驱的附加结点称作头结点。
对于单链表，附加存储空间复杂度为O(n)，初始化操作的时间复杂度为O(1)，其它基本操作的时间复杂度均为O(n)。
2.7 静态顺序表的具体实现
⑴存储结构
typedef struct{//用静态数组存储的顺序表
int last;//尾元下标(表长-1)
DataType data[MAX];//MAX为最大表长(常量)
}SeqList;
⑵初始化操作的核心步骤
SeqList *p=new SeqList;
p->last=-1; ⑶插入操作的核心步骤
for(j=L->last++;j>=i-1;j--)//后移
L->data[j+1]=L->data[j];
L->data[i-1]=x;//插入x
注意后移次序：从后向前逐个后移。
⑷删除操作的核心步骤
for(j=i;j<=L->last;j++)//前移
L->data[j-1]=L->data[j];
L->last--;//修改表长
注意前移次序：从前向后逐个前移。
2.8 单链表的具体实现
⑴结点的存储结构
typedef struct node{//结点结构
DataType data;//数据域
struct node *next;//指针域
}Lnode,*LinkList;//结点及结点的地址
⑵附加头结点初始化操作的核心步骤
Lnode *L=new Lnode;
L->next=0;
⑶求表长操作的核心步骤
for(int j=0;L;L=L->next)j++;
return j;
附加头结点时，j的初值改为-1或返回值改为j-1或
int j=0; while(L=L->next)j++;
⑷在结点p之后插入元素x的核心步骤
s=new Lnode;
s->data=x;
s->next=p->next; p->next=s;
⑸删除结点p后继的核心步骤
s=p->next;
p->next=s->next; delete s;
⑹返回第i个元素地址的核心步骤
for(int j=1;jnext)j++;
return i<1||!L?0:L;
附加头结点时，j的初值改为0或
int j=1; while(jnext)j++; ⑺返回数据元素x地址的核心步骤
while(L&&L->data!=x)L=L->next;
return L;
附加头结点时，改为：
while(L=L->next&&L->data!=x);
⑻返回数据元素x序号的核心步骤
int j=1;
while(L&&L->data!=x)L=L->next,j++;
return L?j:0;
附加头结点时，改为：
while(L=L->next&&L->data!=x)j++;
⑼清空操作的核心步骤
Lnode *p;
while(p=L){L=L->next; delete p;}
另外，调用后需补上语句：
L=0;
附加头结点时，改为：
while(p=L->next){L=p->next; delete p;}
⑽某些操作的递归算法
①求表长
return L?1+Len(L->next):0;
②清空
if(L)Clear(L->next);
delete L;
第3章 栈和队列
3.1 只许一端插入和删除的线性表称作栈，此端称作栈顶，另一端称作栈底。
3.2 栈具有先进后出的特点(FILO)，即，后进先出的特点(LIFO)。
3.3 由入栈序列“…前…中…后…”不可能得到出栈序列“…后…前…中…”。
3.4 只许一端插入、另端删除的线性表称作队列，允许删除的一端称作队首，另端称作队尾。
3.5
队列具有先进先出的特点(FIFO)，即，后进后出的特点(LILO)。出队序列和入队序列相同。
3.6 顺序存储的栈简称顺序栈。通常，顺序栈以表尾作为栈顶。
⑴存储结构
typedef struct{//静态顺序栈
int top;//栈顶下标(或栈长)
DataType data[MAX];
}SeqStack;
⑵初始化的核心步骤
Stack *s=new SeqStack;
s->top=-1;
⑶栈空的条件：s->top==-1; ⑷栈满的条件：s->top+1==MAX
⑸入栈的核心步骤
s->data[++s->top]=x;
⑹出栈的核心步骤
return &s->data[s->top--];
或 return s->data[s->top--];
或 x=&s->data[s->top--];
或 x=s->data[s->top--];
3.7 链式存储的栈简称链栈。通常，链栈以表头作为栈顶。
⑴结点存储结构
typedef struct node{
DataType data;
struct node *next;
}StackNode,*LinkStack;
⑵栈空的条件：!L 或 L==0
⑶入栈的核心步骤
LinkStack p=new StackNode(x); p->next=s; s=p;
⑷出栈的核心步骤
Stack p=s; s=p->next;
*x=p->data; delete p;
⑸清空操作
Stack p;
while(s){p=s; s=s->next; delete p;}
3.8 由“入栈序列”、“出栈序列”、“栈操作序列”中的任意两项可确定另一项。
例. 习题3-2。
3.9 对于双目运算，运算符在两个操作数之前的表达式称作波兰式或前缀表达式。同理，可定义逆波兰式(或后缀表达式)。
