数据结构—线性结构复习.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,线性结构复习,线性表复习重点,顺序表与链表的存储结构特点,顺序表插入和删除结点的过程、算法,链表插入和删除结点的指针变化、算法,循环链表的特点（判断为空）,双向链表的插入和删除过程中指针的变化,掌握表的合并过程（应用）,对于一个具有,n,个结点的单链表，在已知,p,所指结点后插入一个新的结点的时间复杂度为_，在给定值为,x,的结点后插入一个新结点的时间复杂度为_。,在一个长度为,n,的线性表中，删除值为,x,的元素时需要比较元素和移动元素的总次数为()次.,判断下列算法的功能,LinkList,Demo(,LinkList,L)/L,是无头结点单链表,ListNode,*Q,*P;if(Lreturn L,；,/Demo,单链表表逆置的算法,LinkListReverseList,(,LinkList,head),ListNode,*p,*q;,/,设置两个临时指针变量,if(head-next,while(q),p=q;q=q-next;p-next=head-next;head-next=p;returnhead;returnhead;,完成单循环表逆置的算法,Void,contray,_,cirl,(,linklist,&L),lnode,*p,*t,*q;,t=L;,p=t-next;,q=p-next;,while(p!=L),p-next=t;,_,_,_,L-next=t;,假设某个单向循环链表的长度大于,1,，且表中既无头结点也无头指针。已知,s,为指向链表中某个结点指针，试编写算法在链表中删除指针,s,所指结点的前驱结点。,status,deletecirlelist,(,linklist,ET*s),lnode,*s,*q;,q=s;,While(s-next!=q),s=s-next;,r=s;,While(s-next!=r),s=s-next;,s-next=q;,Free(r);,Return ok;,栈和,队列,栈与,队列,栈的形式,顺序栈（固定分配，动态分配）,链栈,各种形式判空、判满的条件,栈的应用（表达式求值、递归）,队列的形式,链队列,顺序队列,循环队列,各种队列判空、判满的表示,由两个栈共享同一个向量空间的好处是（,）。,A.,减少存取时间，降低下溢发生的机率,B.,节省存储空间，降低上溢发生的机率,C.,减少存取时间，降低上溢发生的机率,D.,节省存储空间，降低下溢发生的机率,了解上溢、下溢和假溢出产生的原因,SeqStack,S1,S2,tmp,;,DataType,x;/,假设栈,tmp,和,S2,已做过初始化,while(!,StackEmpty,(Push(&,tmp,x);while(!,StackEmpty,(&,tmp,)x=Pop(&,tmp,);Push(,说明下列算法的功能,void Demo3(,CirQueue,*Q)/,设,DataType,为,int,型,int,x;,SeqStack,S;,InitStack,(while(!,QueueEmpty,(Q)x=,DeQueue,(Q);Push(while(!,StackEmpty,(,EnQueue,(Q,x);/Demo3,说明下列算法的功能,串,掌握要点,串的,相关定义,串的基本操作,函数,Sub(s,I,j),的功能是返回串,s,中从第,I,个字符起长度为,j,的子串，函数,Scopy,(s,t),的功能为复制串,t,到,s。,若字符串,S=SCIENCESTUDY，,则调用函数,Scopy,(P,Sub(S,1,7),后得到()。,A.P=SCIENCEB.P=STUDYC.S=SCIENCED.S=STUDY,若,str,是采用单链表存储的串，编写一个函数将其中的所有为,c,的字符替换为,s,字符,Lstring,*trans(,Lstring,*,str,char c,char s),Lstring,*p;,p=,str,;,/,指向开头,While(p!=null),if(p-data)=c;,pdata=s;,p=p-next;,Return,str,;,数组与广义表,掌握要点,二维数组存储地址的公式求法,特殊矩阵（对称矩阵）压缩存储的方法、计算公式,稀疏矩阵的三元组表示和十字链表的表示，矩阵转置的算法,广义表的定义，表长和表深度的求法,广义表的存储结构,二维,数组,A68，,每个元素占6个字节存储,，且,A00,的存储地址是1000,若按行先存放，元素,A14,的起始地址是_,若按列先存放，元素,A47,的起始地址是_,已知广义表,GL=(a,(b,c,d),e),运用,head,和,tail,函数取出,GL,中的原子,b,的运算是_,将,下列稀疏矩阵分别用三元组和十字链表的形式表示,设有广义表：,E=(b,g),D=(c,d,e),C=(a,D),F(D,f),A=(C,E,F),求,A,的长度和深度，并以链式结构表示,A,