自考02331数据结构重点总结(最终修订)
第一章 概论
1.瑞士计算机科学家沃思提出：算法+数据结构=程序。算法是对数据运算的描述，而数据结构包括逻辑结构和存储结构。由此可见，程序设计的实质是针对实际问题选择一种好的数据结构和设计一个好的算法，而好的算法在很大程度上取决于描述实际问题的数据结构。
2.数据是信息的载体。数据元素是数据的基本单位。一个数据元素可以由若干个数据项组成，数据项是具有独立含义的最小标识单位。数据对象是具有相同性质的数据元素的集合。 3.数据结构指的是数据元素之间的相互关系，即数据的组织形式。
数据结构一般包括以下三方面内容：数据的逻辑结构、数据的存储结构、数据的运算
①数据的逻辑结构是从逻辑关系上描述数据，与数据元素的存储结构无关，是独立于计算机的。 数据的逻辑结构分类: 线性结构和非线性结构。
线性表是一个典型的线性结构。栈、队列、串等都是线性结构。数组、广义表、树和图等数据结构都是非线性结构。 ②数据元素及其关系在计算机内的存储方式，称为数据的存储结构（物理结构）。 数据的存储结构是逻辑结构用计算机语言的实现，它依赖于计算机语言。 ③数据的运算。最常用的检索、插入、删除、更新、排序等。
4.数据的四种基本存储方法: 顺序存储、链接存储、索引存储、散列存储 （1）顺序存储：通常借助程序设计语言的数组描述。 （2）链接存储：通常借助于程序语言的指针来描述。
（3）索引存储：索引表由若干索引项组成。关键字是能唯一标识一个元素的一个或多个数据项的组合。 （4）散列存储：该方法的基本思想是：根据元素的关键字直接计算出该元素的存储地址。
5.算法必须满足5个准则：输入，0个或多个数据作为输入；输出，产生一个或多个输出；有穷性，算法执行有限步后结束；确定性，每一条指令的含义都明确；可行性，算法是可行的。
算法与程序的区别：程序必须依赖于计算机程序语言，而一个算法可用自然语言、计算机程序语言、数学语言或约定的符号语言来描述。目前常用的描述算法语言有两类：类Pascal和类C。 6.评价算法的优劣：算法的\正确性\是首先要考虑的。此外，主要考虑如下三点： ① 执行算法所耗费的时间，即时间复杂性；
② 执行算法所耗费的存储空间，主要是辅助空间，即空间复杂性； ③ 算法应易于理解、易于编程，易于调试等，即可读性和可操作性。 以上几点最主要的是时间复杂性，时间复杂度常用渐进时间复杂度表示。 7.算法求解问题的输入量称为问题的规模,用一个正整数n表示。 8.常见的时间复杂度按数量级递增排列依次为：常数阶0(1)、对数阶0(log2n)、线性阶0(n)、线性对数阶0(nlog2n)、
23kn
平方阶0(n)立方阶0(n)、…、k次方阶0(n)、指数阶0(2)和阶乘阶0(n!)。
9.一个算法的空间复杂度S(n)定义为该算法所耗费的存储空间，它是问题规模n的函数,它包括存储算法本身所占的存储空间、算法的输入输出数据所占的存储空间和算法在运行过程中临时占用的存储空间。
第二章 线性表
1.数据的运算是定义在逻辑结构上的，而运算的具体实现是在存储结构上进行的。
2.只要确定了线性表存储的起始位置，线性表中任意一个元素都可随机存取，所以顺序表是一种随机存取结构。 3.常见的线性表的基本运算:
(1)置空表InitList（L） 构造一个空的线性表L。
(2)求表长ListLength（L）求线性表L中的结点个数，即求表长。 (3)GetNode（L，i） 取线性表L中的第i个元素。
(4)LocateNode（L，x）在L中查找第一个值为x 的元素，并返回该元素在L中的位置。若L中没有元素的值为x ，则返回0值。
(5)InsertList（L，i，x）在线性表L的第i个元素之前插入一个值为x 的新元素，表L的长度加1。 (6)DeleteList（L，i）删除线性表L的第i个元素，删除后表L的长度减1。
4.顺序存储方法：把线性表的数据元素按逻辑次序依次存放在一组地址连续的存储单元里的方法。 顺序表（Sequential List）：用顺序存储方法存储的线性表称为顺序表。顺序表是一种随机存取结构,顺序表的特点是逻辑上相邻的结点其物理位置亦相邻。
顺序表中结点ai 的存储地址: LOC（ai）= LOC（a1）+（i-1）*c 1≤i≤n，
- 1 -
5.顺序表上实现的基本运算：
（1）插入：该算法的平均时间复杂度是O(n)，即在顺序表上进行插入运算，平均要移动一半结点（n/2）。 在第i个位置插入一个结点的移动次数为n-i+1
（2）删除：顺序表上做删除运算，平均要移动表中约一半的结点（n-1）/2，平均时间复杂度也是O(n)。 删除第i个结点移动次数为n-i
6.采用链式存储结构可以避免频繁移动大量元素。一个单链表可由头指针唯一确定，因此单链表可以用头指针的名字来命名。
①生成结点变量的标准函数 p=( ListNode *)malloc(sizeof(ListNode))； //函数malloc分配一个类型为ListNode的结点变量的空间,并将其首地址放入指针变量p中
②释放结点变量空间的标准函数 free(p)；//释放p所指的结点变量空间 ③结点分量的访问 方法二：p-﹥data和p-﹥next
④指针变量p和结点变量*p的关系: 指针变量p的值——结点地址, 结点变量*p的值——结点内容 7.建立单链表:
（1） 头插法建表：算法： p=(ListNode *)malloc(sizeof(ListNode));①//生成新结点 p->data=ch;② //将读入的数据放入新结点的数据域中 p->next=head;③ head=p;④
（2） 尾插法建表：算法： p=(ListNode *)malloc(sizeof(ListNode)); ①//生成新结点 p->data=ch; ② //将读入的数据放入新结点的数据域中 if (head==NULL) head=p;//新结点插入空表 else rear->next=p;③//将新结点插到*r之后 rear=p;④//尾指针指向新表尾
（3） 尾插法建带头结点的单链表：
头结点及作用：头结点是在链表的开始结点之前附加一个结点。它具有两个优点:
⒈由于开始结点的位置被存放在头结点的指针域中,所以在链表的第一个位置上的操作就和在表的其它位置上操作一致,无须进行特殊处理;
⒉无论链表是否为空，其头指针都是指向头结点的非空指针（空表中头结点的指针域空），因此空表和非空表的处理也就统一了。
头结点数据域的阴影表示该部分不存储信息。在有的应用中可用于存放表长等附加信息。
具体算法：r=head;// 尾指针初值也指向头结点 while((ch=getchar())!='\\n'){
s=(ListNode *)malloc(sizeof(ListNode));//生成新结点 s->data=ch; //将读入的数据放入新结点的数据域中 r->next=s; r=s;}
- 2 -
r->next=NULL;//终端结点的指针域置空，或空表的头结点指针域置空 以上三个算法的时间复杂度均为O(n)。 8.单链表上的查找：（带头结点）
（1）按结点序号查找：序号为0的是头结点。
算法：p=head;j=0;//从头结点开始扫描
while(p->next&&j
if(i==j) return p;//找到了第i个结点
else return NULL;//当i<0或i>0时，找不到第i个结点 时间复杂度：在等概率假设下，平均时间复杂度为：为n/2=O(n) （2）按结点值查找：
具体算法：ListNode *p=head->next;//从开始结点比较。表非空，p初始值指向开始结点 while(p&&p->data!=key)//直到p为NULL或p->data为key为止 p=p->next;//扫描下一结点
return p;//若p=NULL，则查找失败，否则p指向值为key的结点
时间复杂度为：O(n)
9.插入运算：插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。
s=(ListNode *)malloc(sizeof(ListNode)); ② s->data=x;③ s->next=p->next;④ p->next=s;⑤ 算法的时间主要耗费在查找结点上，故时间复杂度亦为O(n)。 10.删除运算
r=p->next;②//使r指向被删除的结点ai p->next=r->next③;//将ai从链上摘下free(r);④//释放结点ai的空间给存储池
算法的时间复杂度也是O（n）.p指向被删除的前一个结点。 链表上实现的插入和删除运算，无须移动结点，仅需修改指针。
11.单循环链表—在单链表中，将终端结点的指针域NULL改为指向表头结点或开始结点即可。判断空链表的条件是head==head->next;
12.仅设尾指针的单循环链表: 用尾指针rear表示的单循环链表对开始结点a1和终端结点an查找时间都是O(1)。而表的操作常常是在表的首尾位置上进行，因此，实用中多采用尾指针表示单循环链表。判断空链表的条件为rear==rear->next;
13.循环链表：循环链表的特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。若在尾指针表示的单循环链表上实现，则只需修改指针，无须遍历，其执行时间是O(1)。
- 3 -
具体算法：
LinkList Connect(LinkList A,LinkList B) {//假设A，B为非空循环链表的尾指针 LinkList p=A->next;//①保存A表的头结点位置
A->next=B->next->next;//②B表的开始结点链接到A表尾 free(B->next);//③释放B表的头结点 B->next=p;//④
return B;//返回新循环链表的尾指针
循环链表中没有NULL指针。涉及遍历操作时，其终止条件就不再是像非循环链表那样判别p或p-＞next是否为空，而是判别它们是否等于某一指定指针，如头指针或尾指针等。
在单链表中，从一已知结点出发，只能访问到该结点及其后续结点，无法找到该结点之前的其它结点。而在单循环链表中，从任一结点出发都可访问到表中所有结点，这一优点使某些运算在单循环链表上易于实现。
14.双向链表: 双（向）链表中有两条方向不同的链，即每个结点中除next域存放后继结点地址外，还增加一个指向其直接前趋的指针域prior。
①双链表由头指针head惟一确定的。
②带头结点的双链表的某些运算变得方便。
③将头结点和尾结点链接起来，为双（向）循环链表。
15.双向链表的前插和删除本结点操作 ①双链表的前插操作
void DInsertBefore(DListNode *p,DataType x){//在带头结点的双链表中，将值为x的新结点插入*p之前，设p≠NULL
DListNode *s=malloc(sizeof(DListNode));//① s->data=x;//②
s->prior=p->prior;//③ s->next=p;//④
p->prior->next=s;//⑤ p->prior=s;//⑥}
②双链表上删除结点*p自身的操作
- 4 -
void DDeleteNode(DListNode *p)
{//在带头结点的双链表中，删除结点*p，设*p为非终端结点 p->prior->next=p->next;//① p->next->prior=p->prior;//② free(p); }//③
与单链表上的插入和删除操作不同的是，在双链表中插入和删除必须同时修改两个方向上的指针。上述两个算法的时间复杂度均为O(1)。 16.顺序表和链表比较
时间性能：a、线性表：经常性的查找； b、链式存储结构：经常插入删除操作；
空间性能：a、对数据量大小事先能够知道的用线性表； b、数据量变化较大的用链式存储结构。 存储密度越大，存储空间的利用率越高。显然，顺序表的存储密度是1，链表的存储密度肯定小于1。
第三章 栈和队列
1.栈称为后进先出（Last In First Out）的线性表，简称为LIFO表。 栈是运算受限的线性表，顺序栈也是用数组表示的。
进栈操作：进栈时，需要将S-＞top加1， ①S-＞top==StackSize-1表示栈满 ②\上溢\现象--当栈满时，再做进栈运算产生空间溢出的现象。
退栈操作：退栈时，需将S-＞top减1， ①S-＞top<0表示空栈
②\下溢\现象--当栈空时，做退栈运算产生的溢出现象。
下溢是正常现象，常用作程序控制转移的条件。
空栈时栈顶指针不能是0，只能是-1。
两个栈共享同一存储空间: 当程序中同时使用两
个栈时，可以将两个栈的栈底分别设在顺序存储空间的两端，让两个栈顶各自向中间延伸。当一个栈中的元素较多而栈使用的空间超过共享空间的一半时，只要另一个栈的元素不多，那么前者就可以占用后者的部分存储空间。 当Top1=Top2-1时，栈满
2.为了克服顺序存储分配固定空间所产生的溢出和空间浪费问题。可采用链式存储结构来存储栈。链栈是没有附加头结点的运算受限的单链表。栈顶指针就是链表的头指针。
链栈中的结点是动态分配的，所以可以不考虑上溢，无须定义StackFull运算
栈的一个重要应用是实现递归，直接调用自己或间接调用自己的函数。
3. 队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。允许删除的一端称为队头（Front），允许插入的一端称为队尾（Rear），当队列中没有元素时称为空队列，队列亦称作先进先出（First In First Out）的线性表，简称为FIFO表。 队列的顺序存储结构称为顺序队列，顺序队列实际上是一个受限的线性表。
顺序队列的基本操作
①入队时：将新元素插入rear所指的位置，然后将rear加1。
②出队时：删去front所指的元素，然后将front加1并返回被删元素。
- 5 -
自考02331数据结构重点总结（最终修订） - 图文
