《自考02331数据结构重点总结(最终修订)》由会员分享，可在线阅读，更多相关《自考02331数据结构重点总结(最终修订)（24页珍藏版）》请在金锄头文库上搜索。
1、WORD格式自考 02331 数据构造重点总结( 最终修订 )第一章概论1. 瑞士计算机科学家沃思提出：算法+数据构造 =程序。算法是对数据运算的描述，而数据构造包括逻辑构造和存储构造。由此可见，程序设计的实质是针对实际问题选择一种好的数据构造和设计一个好的算法，而好的算法在很大程度上取决于描述实际问题的数据构造。2. 数据 是信息的载体。 数据元素 是数据的根本单位。一个数据元素可以由假设干个 数据项 组成， 数据项 是具有独立含义的最小标识单位。 数据对象 是具有一样性质的数据元素的集合。3. 数据构造 指的是数据元素之间的相互关系，即数据的组织形式。数据构造一般包括以下三方面内容：数据的
2、逻辑构造、数据的存储构造、数据的运算数据的逻辑构造是从逻辑关系上描述数据，与数据元素的存储构造无关，是独立于计算机的。数据的逻辑构造分类 : 线性构造和非线性构造。线性表 是一个典型的线性构造。栈、队列、串等都是线性构造。数组、广义表、树和图等数据构造都是非线性构造。数据元素及其关系在计算机内的存储方式，称为数据的存储构造物理构造 。数据的存储构造是逻辑构造用计算机语言的实现，它依赖于计算机语言。 数据的运算 。最常用的检索、插入、删除、更新、排序等。4. 数据的四种根本存储方法 : 顺序存储、存储、索引存储、散列存储（ 1顺序存储： 通常借助程序设计语言的 数组 描述。（ 2存储： 通常借助
3、于程序语言的指针来描述。（ 3索引存储： 索引表由假设干索引项组成。关键字是能唯一标识一个元素的一个或多个数据项的组合。（ 4散列存储： 该方法的根本思想是：根据元素的关键字直接计算出该元素的存储地址。5. 算法必须满足5 个准那么： 输入 ， 0 个或多个数据作为输入；输出 ，产生一个或多个输出；有穷性 ，算法执行有限步后完毕； 确定性 ，每一条指令的含义都明确；可行性 ，算法是可行的。算法与程序的区别：程序必须依赖于计算机程序语言，而一个算法可用自然语言、计算机程序语言、数学语言或约定的符号语言来描述。目前常用的描述算法语言有两类：类Pascal 和类 C。6. 评价算法的优劣：算法的 正
4、确性 是首先要考虑的。此外，主要考虑如下三点： 执行算法所消耗的时间，即时间复杂性； 执行算法所消耗的存储空间，主要是辅助空间，即空间复杂性； 算法应易于理解、易于编程，易于调试等，即可读性和可操作性。以上几点最主要的是时间复杂性，时间复杂度常用渐进时间复杂度表示。7. 算法求解问题的 输入量 称为问题的规模 , 用一个正整数 n 表示。8.常见的时间复杂度按数量级递增排列依次为：常数阶 0(1) 、对数阶 0(log 2n) 、线性阶 0(n) 、线性对数阶 0(nlog2n)、平方阶 0(n 2) 立方阶 0(n 3) 、 k 次方阶 0(n k) 、指数阶 0(2 n) 和阶乘阶 0(n
5、!)。9.一个算法的空间复杂度S(n) 定义为该算法所消耗的存储空间，它是问题规模n 的函数 , 它包括存储算法本身所占的存储空间、算法的输入输出数据所占的存储空间和算法在运行过程中临时占用的存储空间。第二章线性表1. 数据的运算是定义在逻辑构造上的，而运算的具体实现是在存储构造上进展的。2. 只要确定了线性表存储的起始位置，线性表中任意一个元素都可随机存取，所以顺序表是一种随机存取构造。3. 常见的线性表的根本运算 :(1) 置空表 InitList L 构造一个空的线性表 L。(2) 求表长 ListLength L求线性表 L 中的结点个数，即求表长。(3)GetNode L， i 取线
6、性表L 中的第 i 个元素。(4)LocateNode L，x在 L 中查找第一个值为x 的元素，并返回该元素在L 中的位置。假设L 中没有元素的值为x ，那么返回 0 值。(5)InsertListL，i ， x在线性表L 的第 i 个元素之前插入一个值为x 的新元素，表L 的长度加1。(6)DeleteListL，i删除线性表L 的第 i 个元素，删除后表L 的长度减1。4. 顺序存储方法：把线性表的数据元素按逻辑次序依次存放在一组地址连续的存储单元里的方法。顺序表 SequentialList ：用顺序存储方法存储的线性表称为顺序表。顺序表 是一种 随机存取构造, 顺序表的特点是逻辑上相
7、邻的结点其物理位置亦相邻。顺序表中结点ai的存储地址 : LOC ai = LOCa1+ i-1 *c1i n，专业资料整理WORD格式- 1 -专业资料整理WORD格式5. 顺序表上实现的根本运算： 1插入： 该算法的平均时间复杂度是O(n) ，即在顺序表上进展插入运算，平均要移动一半结点n/2 。在第 i 个位置插入一个结点的移动次数为n-i+1 2删除 ：顺序表上做删除运算，平均要移动表中约一半的结点n-1 /2 ，平均时间复杂度也是O(n) 。删除第 i 个结点移动次数为n-i6. 采用链式存储构造可以防止频繁移动大量元素。一个单链表可由头指针唯一确定，因此单链表可以用头指针的名字来命
8、名。生成结点变量的标准函数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;
9、 /将读入的数据放入新结点的数据域中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 尾插法建带头结点的单链表：头结点及作用：头结点是在链表的开场结点之前附加一个结点。它具有两个优点:由于开场结点的位置被存放在头结点的指针域中, 所以在链表的第一个位置上的操作就和在表的其它位置
10、上操作一致 , 无须进展特殊处理;无论链表是否为空，其头指针都是指向头结点的非空指针空表中头结点的指针域空，因此空表和非空表的处理也就统一了。头结点数据域的阴影表示该局部不存储信息。 在有的应用中可用于存放表长等附加信息。具体算法： r=head;/尾指针初值也指向头结点while(ch=getchar()!=n)s=(ListNode *)malloc(sizeof(ListNode);/生成新结点s-data=ch;/将读入的数据放入新结点的数据域中r-next=s;r=s;专业资料整理WORD格式- 2 -专业资料整理WORD格式r-next=NULL;/终端结点的指针域置空，或空表的头
11、结点指针域置空以上三个算法的时间复杂度均为O(n) 。8. 单链表上的查找： 带头结点 1按结点序号查找：序号为0 的是头结点。算法： p=head;j=0;/从头结点开场扫描while(p-next&jnext为 NULL或 i=j为止p=p-next;j+;if(i=j) return p;/找到了第i 个结点else return NULL;/当 i0 时，找不到第i 个结点时间复杂度：在等概率假设下，平均时间复杂度为：为n/2=O(n) 2按结点值查找：具体算法： ListNode *p=head-next;/从开场结点比较。表非空，p 初始值指向开场结点while(p&p-data!
12、=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
13、=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) 。专业资料整理WORD格式- 3 -专业资料整理WORD格式具体算法：LinkList Conne
