《“数据结构”读书笔记(线性结构部分)》由会员分享，可在线阅读，更多相关《“数据结构”读书笔记(线性结构部分)（12页珍藏版）》请在金锄头文库上搜索。
1、1“数据结构”读书笔记（线性结构部分）第 1 章 绪 论1. 数据：信息的载体，能被计算机识别、存储和加工处理。2. 数据元素：数据的基本单位，可由若干个数据项组成，数据项是具有独立含义的最小标识单位。3. 数据结构：数据之间的相互关系，即数据的组织形式。它包括：（1）数据的逻辑结构，从逻辑关系上描述数据，与数据存储无关，独立于计算机；（2）数据的存储结构，是逻辑结构用计算机语言的实现，依赖于计算机语言。（3）数据的运算（基本操作），定义在逻辑结构上，每种逻辑结构都有一个运算集合。常用的运算：检索/插入/删除/更新 /排序。4. 数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。数据的存储
2、结构是逻辑结构用计算机语言的实现。5. 数据类型：一个值的集合及在值上定义的一组操作的总称。分为：原子类型和结构类型。6. 抽象数据类型：抽象数据的组织和与之相关的操作。优点：将数据和操作封装在一起实现了信息隐藏。7. 抽象数据类型 ADT：是在概念层上描述问题；类：是在实现层上描述问题；在应用层上操作对象（类的实例）解决问题。8. 数据的逻辑结构，简称为数据结构，有：（1）线性结构，若结构是非空集则仅有一个开始和终端结点，并且所有结点最多只有一个直接前趋和后继。（2）非线性结构，一个结点可能有多个直接前趋和后继。9. 数据的存储结构有：（1）顺序存储，把逻辑相邻的结点存储在物理上相邻的存储单
3、元内。（2）链接存储，结点间的逻辑关系由附加指针字段表示。（3）索引存储，存储结点信息的同时，建立附加索引表，有稠密索引和稀疏索引。（4）散列存储，按结点的关键字直接计算出存储地址。 10. 评价算法的好坏是：算法是正确的；执行算法所耗的时间；执行算法的存储空间（辅助存储空间）；易于理解、编码、调试。 11. 算法的时间复杂度 T(n)：是该算法的时间耗费，是求解问题规模 n 的函数。记为 O(n)。时间复杂度按数量级递增排列依次为：常数阶 O(1)、对数阶 O(log2n)、线性阶 O(n)、线性对数阶 O(nlog2n)、平方阶 O(n2)、立方阶 O(n3)、k 次方阶 O(nk)、指数
4、阶 O(2n)。12. 算法的空间复杂度 S(n)：是该算法的空间耗费，是求解问题规模 n 的函数。13. 算法衡量：是用时间复杂度和空间复杂度来衡量的，它们合称算法的复杂度。14. 算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。第 2 章 线性表1. 线性表：是由 n(n0)个数据元素组成的有限序列。2. 线性表的基本运算有：（1）InitList(L)，构造空表，即表的初始化；（2）ListLength(L)，求表的结点个数，即表长；（3）GetNode(L ，i) ，取表中第 i 个结点，要求 1iListLength(L)；（4）LocateNode(L，x) 查
5、找 L 中值为 x 的结点并返回结点在 L 中的位置，有多个 x 则返回首个，没有则返回特殊值表示查找失败。2（5）InsertList(L，x，i)在表的第 i 个位置插入值为 x 的新结点，要求 1iListLength(L)+1；（6）DeleteList(L ，i)删除表的第 i 个位置的结点，要求 1iListLength(L)；3. 顺序表：把线性表的结点按逻辑次序存放在一组地址连续的存储单元里。4. 顺序表结点的存储地址计算公式：Loc(ai)=Loc(a1)+(i-1)*C；1in 5. 顺序表上的基本运算（1）插入void insertlist(seqlist *L，data
6、type x，int i)int j；if(iL-length+1)error(“position error”)；if(L-length=listsize)error(“overflow”)；for(j=L-length-1；j=i-1 ；j-)L-dataj+1=L-dataj； 结点后移L-datai-1=x；L-length+；在顺序表上插入要移动表的 n/2 结点，算法的平均时间复杂度为 O(n)。（2）删除void delete (seqlist *L，int i)int j；if(iL-length)error(“position error”)；for(j=i； jlength
7、-1；j+)L-dataj-1=L-dataj； 结点前移L-length-；在顺序表上删除要移动表的（n+1）/2 结点，算法的平均时间复杂度为 O(n)。 6. 单链表：只有一个链域的链表称单链表。在结点中存储结点值和结点的后继结点的地址，结点结构如下：Data（节点值） Next（后继结点地址）其中 data 是数据域，next 是指针域（1）建立单链表。时间复杂度为 O(n)。加头结点的优点：1）链表第一个位置的操作无需特殊处理；2）将空表和非空表的处理统一。（2）查找运算。时间复杂度为 O(n)。1） 按序号查找。Listnode * getnode(linklist head，in
8、t i)int j；listnode *p；p=head； j=0；while(p-next&jnext； 指针下移j+；if(i=j)return p；elsereturn NULL；2） 按值查找。Listnode * locatenode(linklist head ，datatype key)listnode *p=head-next；while(p&p-data!=key)p=p-next；return p；（3）插入运算。时间复杂度为 O(n)。Void insertlist(linklist head ，datatype x， int i)listnode *p；p=getnod
9、e(head，i-1) ；if(p=NULL)；error(“position error”)；s=(listnode *)malloc(sizeof(listnode)；s-data=x；s-next=p-next；p-next=s； （4） 删除运算。时间复杂度为 O(n)。Void deletelist(linklist head ，int i)listnode *p ，*r；p=getnode(head ，i-1) ；if(p=NULL|p-next=NULL)error(“position error”)；r=p-next；p-next=r-next；free；7. 循环链表：是一种
10、首尾相连的链表。特点是无需增加存储量，仅对表的链接方式修改使表的处理灵活方便。8. 空循环链表仅由一个自成循环的头结点表示。9. 很多时候表的操作是在表的首尾位置上进行，此时头指针表示的单循环链表就显的不够方便，改用尾指针 rear 来表示单循环链表。用头指针表示的单循环链表查找开始结点的时间是 O(1)4，查找尾结点的时间是 O(n)；用尾指针表示的单循环链表查找开始结点和尾结点的时间都是 O(1)。10. 在结点中增加一个指针域，prior|data|next。形成的链表中有两条不同方向的链称为双链表。1) 双链表的前插操作。时间复杂度为 O(1)。Void dinsertbefore(d
11、listnode *p ，datatype x)dlistnode *s=malloc(sizeof(dlistnode)；s-data=x；s-prior=p-prior；s-next=p；p-prior-next=s；p-prior=s；2) 双链表的删除操作。时间复杂度为 O(1)。Void ddeletenode(dlistnode *p)p-prior-next=p-next；p-next-prior=p-prior；free(p)；11. 顺序表和链表的比较1）基于空间的考虑：顺序表的存储空间是静态分配的，链表的存储空间是动态分配的。顺序表的存储密度比链表大。因此，在线性表长度变化
12、不大，易于事先确定时，宜采用顺序表作为存储结构。2）基于时间的考虑：顺序表是随机存取结构，若线性表的操作主要是查找，很少有插入、删除操作时，宜用顺序表结构。对频繁进行插入、删除操作的线性表宜采用链表。若操作主要发生在表的首尾时采用尾指针表示的单循环链表。12.存储密度=（结点数据本身所占的存储量）/（整个结点结构所占的存储总量）存储密度：顺序表=1，链表top=-1；2）判栈空。int stackempty(seqstack *s)return s-top=-1；3）判栈满。int stackfull(seqstack *s)return s-top=stacksize-1；4）进栈。Void
13、 push(seqstack *s，datatype x)if(stackfull(s)error(“stack overflow”)；s-data+s-top=x；5）退栈。Datatype pop(seqstack *s)if(stackempty(s)error(“stack underflow”)；return S-datas-top-；6）取栈顶元素。Dtatatype stacktop(seqstack *s)if(stackempty(s)error(“stack underflow”)；return S-datas-top；6. 链栈：栈的链式存储结构称链栈。栈顶指针是链表的头
14、指针。7. 链栈上的基本运算：1）建栈。Void initstack(linkstack *s)s-top=NULL；2）判栈空。Int stackempty (linkstack *s)6return s-top=NULL；3）进栈。Void push(linkstack *s，datatype x)stacknode *p=(stacknode *)malloc(sizeof(stacknode)；p-data=x；p-next=s-top；s-top=p；4）退栈。Datatype pop(linksatck *s)datatype x；stacknode *p=s-top；if(sta
15、ckempty(s)error(“stack underflow”)；x=p-data；s-top=p-next；free(p)；return x；5）取栈顶元素。Datatype stacktop(linkstack *s)if(stackempty(s)error(“stack is empty”)；return s-top-data；8. 队列是一种运算受限的线性表，允许删除的一端称队首，允许插入的一端称队尾。队列又称为先进先出线性表，FIFO 表。9. 队列的基本运算：1） initqueue(q)，置空队；2） queueempty(q)，判队空；3） queuefull(q)，判队
16、满；4） enqueue(q，x)，入队；5） dequeue(q)，出队；6） queuefront(q)，返回队头元素。10. 顺序队列：队列的顺序存储结构称顺序队列。设置 front 和 rear 指针表示队头和队尾元素在向量空间的位置。11. 顺序队列中存在“假上溢”现象，由于入队和出队操作使头尾指针只增不减导致被删元素的空间无法利用，队尾指针超过向量空间的上界而不能入队。12. 为克服“假上溢”现象，将向量空间想象为首尾相连的循环向量，存储在其中的队列称循环队列。i=(i+1)%queuesize713. 循环队列的边界条件处理：由于无法用 front=rear 来判断队列的“空”和“满”。解决的方法有：1） 另设一个布尔变
