数据结构随堂笔记

《数据结构随堂笔记》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

第一章概 论1.数据：信息的载体,能被计算机识别、存储和加工处理。2.数据元素：数据的基本单位，可由若干个数据项组成，数据项是具有独立含义的最小标识单位。3.数据结构：数据之间的相互关系，即数据的组织形式。它包括：1）数据的逻辑结构，从逻辑关系上描述数据，与数据存储无关，独立于计算机；2）数据的存储结构，是逻辑结构用计算机语言的实现，依赖于计算机语言。3）数据的运算，定义在逻辑结构上，每种逻辑结构都有一个运算集合。常用的运算：检索/插入/删除/更新/排序。4.数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。数据的存储结构是逻辑结构用计算机语言的实现。5.数据类型：一个值的集合及在值上定义的一组操作的总称。分为：原子类型和结构类型。6.抽象数据类型：抽象数据的组织和与之相关的操作。优点：将数据和操作封装在一起实现了信息隐藏。7.抽象数据类型ADT：是在概念层上描述问题；类：是在实现层上描述问题；在应用层上操作对象（类的实例）解决问题。8.数据的逻辑结构，简称为数据结构，有：（1）线性结构，若结构是非空集则仅有一个开始和终端结点，并且所有结点最多只有一个直接前趋和后继。（2）非线性结构，一个结点可能有多个直接前趋和后继。9.数据的存储结构有：1）顺序存储，把逻辑相邻的结点存储在物理上相邻的存储单元内。2）链接存储，结点间的逻辑关系由附加指针字段表示。3）索引存储，存储结点信息的同时，建立附加索引表，有稠密索引和稀疏索引。4）散列存储，按结点的关键字直接计算出存储地址。10.评价算法的好坏是：算法是正确的；执行算法所耗的时间；执行算法的存储空间（辅助存储空间）；易于理解、编码、调试。11.算法的时间复杂度T(n)：是该算法的时间耗费，是求解问题规模n的函数。记为O(n)。时间复杂度按数量级递增排列依次为：常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、……k次方阶O(n^k)、指数阶O(2^n)。13.算法的空间复杂度S(n)：是该算法的空间耗费，是求解问题规模n的函数。12.算法衡量：是用时间复杂度和空间复杂度来衡量的，它们合称算法的复杂度。13.算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。 第二章  线性表 1.线性表：是由n(n≥0)个数据元素组成的有限序列。2.线性表的基本运算有：1）InitList(L),构造空表，即表的初始化；2）ListLength(L),求表的结点个数，即表长；3）GetNode(L,i),取表中第i个结点，要求1≤i≤ListLength(L)；4）LocateNode(L,x)查找L中值为x的结点并返回结点在L中的位置，有多个x则返回首个，没有则返回特殊值表示查找失败。5）InsertList(L,x,i)在表的第i个位置插入值为x的新结点，要求1≤i≤ListLength(L)+1；6）DeleteList(L,i)删除表的第i个位置的结点，要求1≤i≤ListLength(L)；3.顺序表：把线性表的结点按逻辑次序存放在一组地址连续的存储单元里。4.顺序表结点的存储地址计算公式：Loc(ai)=Loc(a1)+(i-1)*C；1≤i≤n 5.顺序表上的基本运算 （1）插入voidinsertlist(seqlist*L,datatypex,inti){ intj; if(i<1||i>L->length+1) error(“positionerror”); if(L->length>=listsize) error(“overflow”); for(j=L->length-1;j>=i-1;j--) L->data[j+1]=L->data[j]; 结点后移 L->data[i-1]=x; L->length++;}在顺序表上插入要移动表的n/2结点，算法的平均时间复杂度为O(n)。（2）删除voiddelete(seqlist*L,inti){ intj; if(i<1||i>L->length) error(“positionerror”); for(j=i;j<=L->length-1;j++) L->data[j-1]=L->data[j]; 结点前移 L->length--;}在顺序表上删除要移动表的（n+1）/2结点，算法的平均时间复杂度为O(n)。6.单链表：只有一个链域的链表称单链表。在结点中存储结点值和结点的后继结点的地址，data next data是数据域，next是指针域。（1）建立单链表。时间复杂度为O(n)。加头结点的优点：1）链表第一个位置的操作无需特殊处理；2）将空表和非空表的处理统一。（2）查找运算。时间复杂度为O(n)。1）按序号查找。Listnode*getnode(linklisthead,inti){ intj; listnode*p; p=head;j=0; while(p->next&&jnext;指针下移 j++; } if(i==j) returnp; else return NULL;}2）按值查找。Listnode*locatenode(linklisthead,datatypekey){ listnode*p=head->next; while(p&&p->data!=key) p=p->next; returnp;}（3）插入运算。时间复杂度为O(n)。Voidinsertlist(linklisthead,datatypex,inti){ listnode*p; p=getnode(head,i-1); if(p==NULL); error(“positionerror”); s=(listnode*)malloc(sizeof(listnode)); s->data=x; s->next=p->next; p->next=s;}（4）删除运算。时间复杂度为O(n)。Voiddeletelist(linklisthead,inti){ listnode*p,*r; p=getnode(head,i-1); if(p==NULL||p->next==NULL) error(“positionerror”); r=p->next; p->next=r->next; free(r);}7.循环链表：是一种首尾相连的链表。特点是无需增加存储量，仅对表的链接方式修改使表的处理灵活方便。8.空循环链表仅由一个自成循环的头结点表示。9.很多时候表的操作是在表的首尾位置上进行，此时头指针表示的单循环链表就显的不够方便，改用尾指针rear来表示单循环链表。用头指针表示的单循环链表查找开始结点的时间是O(1),查找尾结点的时间是O(n)；用尾指针表示的单循环链表查找开始结点和尾结点的时间都是O(1)。10.在结点中增加一个指针域，prior|data|next。形成的链表中有两条不同方向的链称为双链表。1)双链表的前插操作。时间复杂度为O(1)。Voiddinsertbefore(dlistnode*p,datatypex){ 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)。Voidddeletenode(dlistnode*p){ p->prior->next=p->next; p->next->prior=p->prior; free(p);}11.顺序表和链表的比较1）基于空间的考虑：顺序表的存储空间是静态分配的，链表的存储空间是动态分配的。顺序表的存储密度比链表大。因此，在线性表长度变化不大，易于事先确定时，宜采用顺序表作为存储结构。2）基于时间的考虑：顺序表是随机存取结构，若线性表的操作主要是查找，很少有插入、删除操作时，宜用顺序表结构。对频繁进行插入、删除操作的线性表宜采用链表。若操作主要发生在表的首尾时采用尾指针表示的单循环链表。12.存储密度=（结点数据本身所占的存储量）/（整个结点结构所占的存储总量）存储密度：顺序表=1，链表<1。第三章  栈和队列 1.栈是限制仅在表的一端进行插入和删除运算的线性表又称为后进先出表（LIFO表）。插入、删除端称为栈顶，另一端称栈底。表中无元素称空栈。2.栈的基本运算有：1）initstack(s),构造一个空栈；2）stackempty(s),判栈空；3）stackfull(s),判栈满；4）push(s,x),进栈；5）pop(s),退栈；6）stacktop(s)，取栈顶元素。3.顺序栈：栈的顺序存储结构称顺序栈。4.当栈满时，做进栈运算必定产生空间溢出，称“上溢”。当栈空时，做退栈运算必定产生空间溢出，称“下溢”。上溢是一种错误应设法避免，下溢常用作程序控制转移的条件。6.链栈：栈的链式存储结构称链栈。栈顶指针是链表的头指针。 8.队列是一种运算受限的线性表，允许删除的一端称队首，允许插入的一端称队尾。队列又称为先进先出线性表，FIFO表。9.队列的基本运算：1）initqueue(q),置空队；2）queueempty(q),判队空；3）queuefull(q),判队满；4）enqueue(q,x),入队；5）dequeue(q),出队；6）queuefront(q),返回队头元素。10.顺序队列：队列的顺序存储结构称顺序队列。设置front和rear指针表示队头和队尾元素在向量空间的位置。 11.顺序队列中存在“假上溢”现象，由于入队和出队操作使头尾指针只增不减导致被删元素的空间无法利用，队尾指针超过向量空间的上界而不能入队。12.为克服“假上溢”现象，将向量空间想象为首尾相连的循环向量，存储在其中的队列称循环队列。i=(i+1)%queuesize13.循环队列的边界条件处理：由于无法用front==rear来判断队列的“空”和“满”。解决的方法有：1）另设一个布尔变量以区别队列的空和满；2）少用一个元素，在入队前测试rear在循环意义下加1是否等于front；3）使用一个记数器记录元素总数。15.链队列：队列的链式存储结构称链队列，链队列由一个头指针和一个尾指针唯一确定。第六章  树1.树：是n个结点的有限集T，T为空时称空树，否则满足：1）有且仅有一个特定的称为根的结点；2）其余结点可分为m个互不相交的子集，每个子集本身是一棵树，并称为根的子树。2.树的表示方法：1）树形表示法；2）嵌套集合表示法；3）凹入表表示法；4）广义表表示法；3.一个结点拥有的子树数称为该结点的度；一棵树的度是指树中结点最大的度数。4.度为零的结点称叶子或终端结点；度不为零的结点称分支结点或非终端结点5.根结点称开始结点，根结点外的分支结点称内部结点；6.树中某结点的子树根称该结点的孩子；该结点称为孩子的双亲；7.树中存在一个结点序列K1，K2，…Kn，使Ki为Ki+1的双亲，则称该结点序列为K1到Kn的路径或道路；8.树中结点K到Ks间存在一条路径，则称K是Ks的祖先，Ks是K的子孙；9.结点的层数从根算起，若根的层数为1，则其余结点层数是其双亲结点层数加1；双亲在同一层的结点互为堂兄弟；树中结点最大层数称为树的高度或深度；10.树中每个结点的各个子树从左到右有次序的称有序树，否则称无序树；11.森林是m棵互不相交的树的集合。 12.二叉树：是n个结点的有限集，它或为空集，或由一个根结点及两棵互不相交的、分别称为该根的左子树和右子树的二叉树组成。13.二叉树不是树的特殊情况，这是两种不同的数据结构；它与无序树和度为2的有序树不同。14.二叉树的性质：1）二叉树第i层上的结点数最多为2^(i-1)；2）深度为k的二叉树至多有2^k-1个结点；3）在任意二叉树中，叶子数为n0，度为2的结点数为n2，则n0=n2+1；15.满二叉树是一棵深度为k的且有2^k-1个结点的二叉树；16.完全二叉树是至多在最下两层上结点的度数可以小于2，并且最下层的结点集中在该层最左的位置的二叉树；17.具有N个结点的完全二叉树的深度为log2N取整加1；18.二叉树的存储结构（1）顺序存储结构：把一棵有n个结点的完全二叉树，从树根起自上而下、从左到右对所有结点编号，然后依次存储在一个向量b[0~n]中，b[1~n]存放结点，b[0]存放结点总数。各个结点编号间的关系：1）i=1是根结点；i>1则双亲结点是i/2取整；2）左孩子是2i,右孩子是2i+1；（要小于n）3）i>（n/2取整）的结点是叶子；4）奇数没有右兄弟，左兄弟是i-1；5） 偶数没有左兄弟，右兄弟是i+1；（2）链式存储结构结点的结构为：lchild|data|rchild；相应的类型说明：typedefchardata;typedefstructnode{ datatypedata; structnode*lchild,*rchild;}bintnode;typedefbintnode*bintree;19.在二叉树中所有类型为bintnode的结点和一个指向开始结点的bintree类型的头指针构成二叉树的链式存储结构称二叉链表。20.二叉链表由根指针唯一确定。在n个结点的二叉链表中有2n个指针域，其中n+1个为空。 21.二叉树的遍历方式有：前序遍历、中序遍历、后序遍历。时间复杂度为O(n)。22.线索二叉树：利用二叉链表中的n+1个空指针域存放指向某种遍历次序下的前趋和后继结点的指针，这种指针称线索。加线索的二叉链表称线索链表。相应二叉树称线索二叉树。23.线索链表结点结构：lchild|ltag|data|rtag|rchild；ltag=0,lchild是指向左孩子的指针；ltag=1,lchild是指向前趋的线索；rtag=0,rchild是指向右孩子的指针；rtag=1,rchild是指向后继的线索；24.查找*p在指定次序下的前趋和后继结点。算法的时间复杂度为O(h)。线索对查找前序前趋和后序后继帮助不大。25.遍历线索二叉树。时间复杂度为O(n)。 26.树、森林与二叉树的转换（1）树、森林与二叉树的转换1）树与二叉树的转换：1}所有兄弟间连线；2}保留与长子的连线，去除其它连线。该二叉树的根结点的右子树必为空。2）森林与二叉树的转换：1}将所有树转换成二叉树；2}将所有树根连线。（2）二叉树与树、森林的转换。是以上的逆过程。27.树的存储结构（1）双亲链表表示法：为每个结点设置一个parent指针，就可唯一表示任何一棵树。Data|parent（2）孩子链表表示法：为每个结点设置一个firstchild指针，指向孩子链表头指针，链表中存放孩子结点序号。Data|firstchild。（3双亲孩子链表表示法：将以上方法结合。Data|parent|firstchild（4）孩子兄弟链表表示法：附加两个指向左孩子和右兄弟的指针。Leftmostchild|data|rightsibling28.树和森林的遍历：前序遍历一棵树等价于前序遍历对应二叉树；后序遍历等价于中序遍历对应二叉树。 29.最优二叉树（哈夫曼树）：树的路径长度是从树根到每一结点的路径长度之和。将树中的结点赋予实数称为结点的权。30.结点的带权路径是该结点的路径长度与权的乘积。树的带权路径长度又称树的代价，是所有叶子的带权路径长度之和。31.带权路径长度最小的二叉树称最优二叉树（哈夫曼树）。32.具有2n-1个结点其中有n个叶子，并且没有度为1的分支结点的树称为严格二叉树。33.哈夫曼编码34.对字符集编码时，要求字符集中任一字符的编码都不是其它字符的编码前缀，这种编码称前缀码。35.字符出现频度与码长乘积之和称文件总长；字符出现概率与码长乘积之和称平均码长；36.使文件总长或平均码长最小的前缀码称最优前缀码37.利用哈夫曼树求最优前缀码，左为0，右为1。编码平均码长最小；没有叶子是其它叶子的祖先，不可能出现重复前缀。 第七章  图1.图：图G是由顶点集V和边集E组成，顶点集是有穷非空集，边集是有穷集；2.G中每条边都有方向称有向图；有向边称弧；边的始点称弧尾；边的终点称弧头；G中每条边都没有方向的称无向图。 3.顶点n与边数e的关系：无向图的边数e介于0~n(n-1)/2之间，有n(n-1)/2条边的称无向完全图；有向图的边数e介于0~n(n-1)之间，有n(n-1)条边的称有向完全图；4.无向图中顶点的度是关联与顶点的边数；有向图中顶点的度是入度与出度的和。所有图均满足：所有顶点的度数和的一半为边数。5.图G（V，E），如V’是V的子集，E’是E的子集，且E’中关联的顶点均在V’中，则G’(V’,E’)是G的子图。6.在有向图中，从顶点出发都有路径到达其它顶点的图称有根图；7.在无向图中，任意两个顶点都有路径连通称连通图；极大连通子图称连通分量；8.在有向图中，任意顺序两个顶点都有路径连通称强连通图；极大连通子图称强连通分量；9.将图中每条边赋上权，则称带权图为网络。10.图的存储结构：（1）邻接矩阵表示法：邻接矩阵是表示顶点间相邻关系的矩阵。n个顶点就是n阶方阵。无向图是对称矩阵；有向图行是出度，列是入度。（2）邻接表表示法：对图中所有顶点，把与该顶点相邻接的顶点组成一个单链表，称为邻接表，adjvex|next,如要保存顶点信息加入data；对所有顶点设立头结点，vertex|firstedge,并顺序存储在一个向量中；vertex保存顶点信息，firstedge保存邻接表头指针。11.邻接矩阵表示法与邻接表表示法的比较：1）邻接矩阵是唯一的，邻接表不唯一；2）存储稀疏图用邻接表，存储稠密图用邻接矩阵；3）求无向图顶点的度都容易，求有向图顶点的度邻接矩阵较方便；4）判断是否是图中的边，邻接矩阵容易，邻接表最坏时间为O(n)；5）求边数e，邻接矩阵耗时为O(n^2)，与e无关，邻接表的耗时为O(e+n)；12.图的遍历：（1）图的深度优先遍历：类似与树的前序遍历。按访问顶点次序得到的序列称DFS序列。对邻接表表示的图深度遍历称DFS，时间复杂度为O(n+e);对邻接矩阵表示的图深度遍历称DFSM，时间复杂度为O(n^2);（2）图的广度优先遍历：类似与树的层次遍历。按访问顶点次序得到的序列称BFS序列。对邻接表表示的图广度遍历称BFS，时间复杂度为O(n+e);对邻接矩阵表示的图广度遍历称BFSM，时间复杂度为O(n^2);13.将没有回路的连通图定义为树称自由树。14.生成树：连通图G的一个子图若是一棵包含G中所有顶点的树，该子图称生成树。有DFS生成树和BFS生成树，BFS生成树的高度最小。非连通图生成的是森林。15.最小生成树：将权最小的生成树称最小生成树。（是无向图的算法）（1）普里姆算法：1）确定顶点S、初始化候选边集T[0~n-2]；formvex|tovex|lenght2）选权值最小的T[i]与第1条记录交换；3）从T[1]中将tovex取出替换以下记录的fromvex计算权；若权小则替换，否则不变；4）选权值最小的T[i]与第2条记录交换；5）从T[2]中将tovex取出替换以下记录的fromvex计算权；若权小则替换，否则不变；6）重复n-1次。初始化时间是O(n),选轻边的循环执行n-1-k次，调整轻边的循环执行n-2-k；算法的时间复杂度为O(n^2)，适合于稠密图。（2）克鲁斯卡尔算法：1）初始化确定顶点集和空边集；对原边集按权值递增顺序排序；2） 取第1条边，判断边的2个顶点是不同的树，加入空边集，否则删除；3）重复e次。对边的排序时间是O(elog2e)；初始化时间为O(n)；执行时间是O(log2e)；算法的时间复杂度为O(elog2e)，适合于稀疏图。16.路径的开始顶点称源点，路径的最后一个顶点称终点；17.单源最短路径问题：已知有向带权图，求从某个源点出发到其余各个顶点的最短路径；18.单目标最短路径问题：将图中每条边反向，转换为单源最短路径问题；19.单顶点对间最短路径问题：以分别对不同顶点转换为单源最短路径问题；20.所有顶点对间最短路径问题：分别对图中不同顶点对转换为单源最短路径问题；21.迪杰斯特拉算法：1）初始化顶点集S[i],路径权集D[i],前趋集P[i]；2）设置S[s]为真，D[s]为0；3）选取D[i]最小的顶点加入顶点集；4）计算非顶点集中顶点的路径权集；5）重复3）n-1次。算法的时间复杂度为O(n^2)。22.拓扑排序：对一个有向无环图进行拓扑排序，是将图中所有顶点排成一个线性序列，满足弧尾在弧头之前。这样的线性序列称拓扑序列。（1）无前趋的顶点优先：总是选择入度为0的结点输出并删除该顶点的所有边。设置各个顶点入度时间是O(n+e)，设置栈或队列的时间是O(n)，算法时间复杂度为O(n+e)。（2）无后继的顶点优先：总是选择出度为0的结点输出并删除该顶点的所有边。设置各个顶点出度时间是O(n+e)，设置栈或队列的时间是O(n)，算法时间复杂度为O(n+e)。求得的是逆拓扑序列。