数据结构期末复习知识点(兼容版)

《数据结构》期末复习复习要点：第一章1.相关基本概念：数据、数据元素（基本单位）、数据项（最小单位）、算法及其特征等；◎数据：所有能输入到计算机中并被计算机程序处理的符号总称。◎数据元素：基本单位。◎数据项：最小单位。◎算法特征（5点）：有穷性；确定性；可行性；输入；输出。2.逻辑结构、存储结构（物理结构）及其类型；◎逻辑结构有四种基本类型：集合、线性结构、树形结构和网状结构。◎数据元素之间的关系有两种不同的表示方法：顺序映象和非顺序映象，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。◎注：期中考题目数据结构分为两大类，即为逻辑结构和存储结构。其中逻辑结果又分为线性结构和非线性结构，存储结构一共有四种（顺序、链接、索引、散列）。3.算法分析：语句频度（执行次数）计算、时间和空间复杂度分析。表示方法◎语句频度：直接写次数。◎时间复杂度：O(执行次数),如：O(n)。◎空间复杂度：O(所需空间)第二章1.顺序表（数组）插入、删除、有序表合并算法及其移动次数计算；数据元素序号12345678表示L.elem[0][1][2][3][4][5][6][7]◎顺序表插入算法思想：如果要在序号5前插入元素e，需要将序号5～8向后移动一个位置。▲移动次数为4次，公式n-i+11213212428304277◎顺序表删除算法思想：如果要删除序号5元素，需要将6～8依次向前移动一位▲移动次数为3次，公式n-i◎有序表合并LA=(3,5,8,11)LB=(2,6,8,9,11,15,20)则LC=(2,3,5,6,8,8,9,11,11,15,20)算法思想（以非递减为例）：La和Lb非递减排列，La与Lb中元素逐个比较，较小的先插入Lc中。▲注：非递减是指递增排序，但元素有可能相等，与之相对的有非递增排序。▲移动次数为（La.length+Lb.length）2.链表（有无头节点、单双、循环）插入(前、后)、删除（前、本身、后）的指针挂接、建立（不带头节点）算法。◎单链表▲每个节点有数据域和指针域datanext头a1a2a3a4a5a6带头节点L→→→→→→→P↑a1a2a3a4a5a6不带头节点L→→→→→→P↑单循环链表●在P（a3）节点前插入S节点(1)Q=P;//先让Q指向a3(2)P=L;//P指向第一个节点（带头结点指向头结点，不带头结点指向a1）(3)while(P-next!=Q)P=P-next;//找到a3的前驱a2，P指向a2(4)S-next=P-next;//P-next为a3，让S-next等于a3(5)P-next=S;//a2指针域指向节点S●在P（a3）节点后插入S节点(1)S-next=P-next;(2)P-next=S;●删除P（a3）前一个节点(1)Q=P;(2)P=L;(3)while(P-next-next!=Q)P=P-next;//找到a1(4)P-next=P-next-next;//让a1指针域指向a3，从而删除a2●删除P（a3）节点(1)Q=P;(2)P=L;(3)while(P-next!=Q)P=P-next;//找到a2(4)P-next=P-next-next;//让a2指针域指向a4，从而删除a3●删除P（a3）后一个节点(1)P-next=P-next-next;//让a3指针域指向a5，从而删除a4◎双链表▲每个节点有前驱指针、数据域、后继指针priordatanext双循环链表头a1a2a3a4●在P（a2）节点前插入S节点▲技巧：先让S-prior和S-next与链表建立关系注：步骤(4)必须在步骤(3)后面(1)S-next=P;//先让S-next指向a2(2)S-prior=P-prior;//S-prior指向a1(3)P-prior-next=S;//再把a1-next指向S(4)P-prior=S;//a2-prior指向S●在P（a2）节点后插入S节点注：步骤(4)必须在步骤(3)后面(1)S-prior=P;(2)S-next=P-next;(3)P-next-prior=S;//a3-prior指向S(4)P-next=S;●删除P（a2）前一个节点a1(1)Q=P-prior;//Q指向要被删除的a1;(2)P-prior=P-prior-prior;//P-priro指向头(3)P-prior-next=P;//头-next指向P(4)free(Q);//释放a1的存储空间●删除P（a2）节点(1)P-next-prior=p-prior;(2)P-prior-next=p-next;(3)free(P);●删除P（a2）后一个节点a3(1)Q=P-next;(2)P-next=P-next-next;//a2-next指向a4(3)P-next-prior=P;//a4-prior=P(4)free(Q);//释放a3存储空间◎建立（不带头节点）单链表读程序：设n为2（i取0，1）i=0时，p↑L↑q↑i=1时，→L↑q↑p↑L↑q↑p↑→L↑q↑p↑第三章1.栈的进出序列、栈、队列、循环队列的满/空条件;▲由于栈的插入、删除操作是限制在栈顶进行的，因而后进栈的元素必然是先出栈，0.所以栈是“后进先出”表。▲由于队列的输入、输出操作分别在队的两端进行，因此先入队的元素必然先输出，故队列又称为“先进先出”表◎栈的进出序列例题：进栈序列为123，可能得到的出栈序列是什么？答：共五种123/132/213/231/321进出栈情况（以132序列为例）：1进栈→1出栈，输出1→2进栈→3进栈→3出栈→2出栈输出32◎栈、队列、循环队列的满/空条件栈空条件：s.top=s.base;栈满条件：s.top-s.base=stacksize;队空条件：Q.front=Q.rear;队满条件：q-rear-q-front=MAXSIZE循环队列空条件：Q.front=Q.rear循环队列满条件：为避免在队满是队头指针和队尾指针也是重合的情况，规定队列中还有一个空的存储单元时为队满，即为Q.front=(Q.rear+1)MODmaxsize(MOD为取余运算符）。因而，这种循环队列不适合用动态数组作为存储结构。2.栈、队列的存储结构、基本操作算法（双向栈）;◎栈存储结构●顺序栈typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;●链式栈◎队列存储结构●顺序存储结构●链式存储结构◎双向栈存储结构：typedefstruct{Elemtype*base[2];Elemtype*top[2];}BDStacktype;//双向栈类型初始化：StatusInit_Stack(BDStacktype&tws,intm)//初始化一个大小为m的双向栈tws{tws.base[0]=(Elemtype*)malloc(sizeof(Elemtype)*m);tws.base[1]=tws.base[0]+m;tws.top[0]=tws.base[0];tws.top[1]=tws.base[1];returnOK;}//Init_Stack入栈：Statuspush(BDStacktype&tws,inti,Elemtypex)//x入栈,i=0表示低端栈,i=1表示高端栈{if(tws.top[0]tws.top[1])returnOVERFLOW;//注意此时的栈满条件if(i==0)*tws.top[0]++=x;elseif(i==1)*tws.top[1]--=x;elsereturnERROR;returnOK;}//push出栈：Statuspop(BDStacktype&tws,inti,Elemtype&x)//x出栈,i=0表示低端栈,i=1表示高端栈{if(i==0){if(tws.top[0]==tws.base[0])returnOVERFLOW;x=*--tws.top[0];}elseif(i==1){if(tws.top[1]==tws.base[1])returnOVERFLOW;x=*++tws.top[1];}elsereturnERROR;returnOK;}//pop第四章1.字符串模式匹配的简单算法；intIndex(SStringS,SStringT,intpos){//算法4.5//返回子串T在主串S中第pos个字符之后的位置。//若不存在，则函数值为0。//其中，T非空，1≤pos≤StrLength(S)。inti=pos;intj=1;while(i=S[0]&&j=T[0]){if(S[i]==T[j]){//继续比较后继字符++i;++j;}else{//指针后退重新开始匹配i=i-j+2;//此时i为上次开始比较位置的下一位j=1;}}if(jT[0])returni-T[0];elsereturn0;}//Index2.计算NEXT。j：1234567串：abcabaanext[j]：0111232▲技巧：第一二个肯定是0，1！如果要计算next[4]，找的字符串必须是以第3个字符c为结尾，第1个字符a为开头的。以第6个为例，a前一个字母是b，以第5个字符b为结尾的ab刚好和以第1个字符为开头的ab匹配，所以next[6]=2+1=3。第五章1.二维数组的地址（下标）换算；习题5.1假设有二维数组A6*8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，计算：（1）数组A的体积（即存储量）6*8*6=288字节（3）按行存储是，元素a14的第一个字节的地址1000+(8*1+4)*6=1072基址+(每行的元素个数*行数+当前列序)*每个元素所占存储单元（4）按列存储时，元素a47的第一个字节的地址1000+(6*7+4)*6=6276基址+(每列的元素个数*列数+当前行序)*每个元素所占存储单元习题5.2假设按低下标优先存储整数组A9*3*5*8时，第一个元素的字节地址是100，每个整数占四个字节。问下列元素的存储地址是什么？（2）a1111地址：100+(3*5*8*1+5*8*1+8*1+1)*4=776（3）a3125地址：100+(3*5*8*3+5*8*1+8*2+5)*4=1784（4）a8247地址：100+(3*5*8*8+5*8*2+8*4+7)*4=44162.特殊矩阵（三角、其他有规律）压缩为一维的下标计算；◎下三角矩阵压缩为一维数组（记忆公式）▲技巧：推荐把公式(2)背下来（i,j,R范围都是从0开始），其他根据范围变化公式(1)若1=j,j=n,0=R=n(n+1)/2-1当i=j时，k=i(i-1)/2+j-1;当ij时，k=j(j-1)/2+i-1.(2)若0=i,j=n-1,0=R=n(n+1)/2-1//注意i,j是0到n-1，下面的公式相当于把(1)中i变成i+1,j变成j+1当i=j时，k=(i+1)i/2+j;当jj时，k=(j+1)j/2+i.(3)若1=j,j=n,1=R=n(n+1)/2//注意R是1到n(n+1)/2，下面公式相当于把(1)中k变成k-1当i=j时，k=i(i-1)/2+j;当ij时，k=j(j-1)/2+i;(4)若0=j,j=n-1,1=R=n(n+1)/2当i=j时，k=(i+1)i/2+j+1;当ij时，k=(j+1)j/2+i+1;3.稀疏矩阵的三元组表示。4.稀疏矩阵应用的算法。（略）第六章1.二叉树的性质；性质1：)1(21iii个结点层上至多有在二叉树的第。性质2：深度为k的二叉树至多有12k个结点(k1)。性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n