数据结构习题集.ppt

数据结构-复习,1,数据结构题集-2,P14：2.6、2.7P15:2.9P17:2.11、2.19,数据结构-复习,2,s-next=p-next;p-next=s;p-next-prior=s;s-prior=p;,p,s,插入元素算法2.8(a),在 P 所指向的结点后插入新结点,数据结构-复习,3,在 P 所指向的结点前插入新结点,插入元素算法2.8(b),s-prior=p-prior;p-prior-next=s;s-next=p;p-prior=s;,p,s,数据结构-复习,4,p-next=p-next-next;p-next-prior=p;,p,删除元素算法2.8(c),删除结点P 的后继元素,数据结构-复习,5,p-prior-next=p-next;p-next-prior=p-prior;,p,删除元素算法2.8(e),删除结点P 指向的元素,数据结构-复习,6,2.11,Status Insert_SqList(SqList/Insert_SqList,数据结构-复习,7,2.19,Status Delete_Between(Linklist/Delete_Between,数据结构-复习,8,其它习题,P16:2.10 2.12P18:2.21 2.22 2.24 2.29 2.33,数据结构-复习,9,2.10,Status DeleteK(SqList/DeleteK,数据结构-复习,10,2.12,int ListComp(SqList A,SqList B)/比较字符表A和B,并用返回值表示结果,值为1,表示AB;值为-1,表示AB.elemi?1:-1;if(A.length=B.length)return 0;return A.lengthB.length?1:-1;/当两个字符表可以互相比较的部分完全相同时,哪个较长,哪个就较大/ListComp,数据结构-复习,11,2.21,void reverse(SqList/reverse,数据结构-复习,12,2.22,void LinkList_reverse(Linklist/LinkList_reverse,数据结构-复习,13,2.24,void reverse_merge(LinkList/构造新表头/reverse_merge,数据结构-复习,14,2.29,void SqList_Intersect_Delete(SqList/SqList_Intersect_Delete,数据结构-复习,15,2.30,void LinkList_Intersect_Delete(LinkList/else/while/LinkList_Intersect_Delete,数据结构-复习,16,2.33,Status LinkList_Divide(LinkList/完成循环链表/LinkList_Divide,数据结构-复习,17,数据结构题集-3,P22:3.3P23:3.9 3.12P24:3.16P25:3.28,数据结构-复习,18,3.16,void Train_arrange(char*train)/这里用字符串train表示火车,H表示硬席,S表示软席p=train;q=train;InitStack(s);while(*p)if(*p=H)push(s,*p);/把H存入栈中else*(q+)=*p;/把S调到前部p+;while(!StackEmpty(s)pop(s,c);*(q+)=c;/把H接在后部/Train_arrange,数据结构-复习,19,3.28,void InitCiQueue(CiQueue/InitCiQueue,数据结构-复习,20,void EnCiQueue(CiQueue/修改尾指针,3.28,数据结构-复习,21,Status DeCiQueue(CiQueue/DeCiQueue,3.28,数据结构-复习,22,P22:3.4P23:3.10 P24:3.13 3.15 3.17 3.19 3.21P26:3.30 3.31,其它习题,数据结构-复习,23,typedef struct Elemtype*base2;Elemtype*top2;BDStacktype;/双向栈类型 Status Init_Stack(BDStacktype/Init_Stack,3.15,数据结构-复习,24,typedef struct Elemtype*base2;Elemtype*top2;BDStacktype;/双向栈类型 Status push(BDStacktype/push,3.15,数据结构-复习,25,typedef struct Elemtype*base2;Elemtype*top2;BDStacktype;/双向栈类型 Status pop(BDStacktype/pop,3.15,数据结构-复习,26,int IsReverse()InitStack(s);while(e=getchar()!=/IsReverse,3.17,数据结构-复习,27,Status AllBrackets_Test(char*str)InitStack(s);for(p=str;*p;p+)if(*p=(|*p=|*p=)push(s,*p);else if(*p=)|*p=|*p=)if(StackEmpty(s)return ERROR;pop(s,c);if(*p=)/AllBrackets_Test,3.19,数据结构-复习,28,数据结构-复习,29,void NiBoLan(char*str,char*new)p=str;q=new;InitStack(s);/s为运算符栈while(*p)if(*p是字母)*q+=*p;/直接输出elsec=gettop(s);if(*p优先级比c高)push(s,*p);elsewhile(gettop(s)优先级不比*p低)pop(s,c);*(q+)=c;/whilepush(s,*p);/else/elsep+;/while/NiBoLan,3.21,数据结构-复习,30,Status EnCyQueue(CyQueue/EnCyQueue,3.30,Status DeCyQueue(CyQueue/DeCyQueue,数据结构-复习,31,int Palindrome_Test()InitStack(S);InitQueue(Q);while(c=getchar()!=)Push(S,c);EnQueue(Q,c);while(!StackEmpty(S)Pop(S,a);DeQueue(Q,b);if(a!=b)return ERROR;return OK;/Palindrome_Test,3.31,数据结构-复习,32,数据结构题集-5,P31:5.1P32:5.2P35:5.21 5.22,数据结构-复习,33,void TSMatrix_Add(TSMatrix A,TSMatrix B,TSMatrix/if,else if(A.datapa.jB.datapb.j)C.datapc.i=x;C.datapc.j=B.datapb.j;C.datapc.e=B.datapb.e;pb+;pc+;elseC.datapc.i=x;C.datapc.j=A.datapa.j;C.datapc.e=A.datapa.epa+;pc+;/while,5.21,数据结构-复习,34,while(A.datapa=x)/插入A中剩余的元素(第x行)C.datapc.i=x;C.datapc.j=A.datapa.j;C.datapc.e=A.datapa.epa+;pc+;while(B.datapb=x)/插入B中剩余的元素(第x行)C.datapc.i=x;C.datapc.j=B.datapb.j;C.datapc.e=B.datapb.e;pb+;pc+;/forC.tu=pc;/TSMatrix_Add,数据结构-复习,35,数据结构题集-6,P38:6.1P41:6.22 6.23 6.24 6.26 6.27 6.28P42:6.37 6.38 6.39,数据结构-复习,36,void PreOrder_Nonrecursive(Bitree T)InitStack(S);Push(S,T);/根指针进栈while(!StackEmpty(S)while(Gettop(S,p)/向右一步/while/PreOrder_Nonrecursive,6.37,数据结构-复习,37,void PostOrder_Stack(BiTree T)PMType a;InitStack(S);Push(S,T,0);/根结点入栈while(!StackEmpty(S)Pop(S,a);switch(a.mark)case 0:Push(S,a,1);if(a-lchild)Push(S,a-lchild,0);break;case 1:Push(S,a,2);if(a-rchild)Push(S,a-rchild,0);break;case 2:visit(a);/访问结点,返回/while/PostOrder_Stack,6.38,数据结构-复习,38,void PostOrder_Nonrecursive(EBitree T p=T;while(p)switch(p-mark)case 0:p-mark=1;if(p-lchild)p=p-lchild;/访问左子树break;case 1:p-mark=2;if(p-rchild)p=p-rchild;/访问右子树break;case 2:visit(p);p-mark=0;/恢复mark值p=p-parent;/返回双亲结点/PostOrder_Nonrecursive,6.39,数据结构-复习,39,数据结构题集-7,P47:7.8P48:7.15 7.16,数据结构-复习,40,最小生成树-普里姆算法,取图中任意一个顶点 v 作为生成树的根，之后往生成树上添加新的顶点 w。在添加的顶点 w 和已经在生成树上的顶点v 之间必定存在一条边，并且该边的权值在所有连通顶点 v 和 w 之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树上含有 n-1 个顶点为止。,数据结构-复习,41,最小生成树-克鲁斯卡尔算法,先构造一个只含 n 个顶点的子图 SG，然后从权值最小的边开始，若它的添加不使SG 中产生回路，则在 SG 上加上这条边，如此重复，直至加上 n-1 条边为止,数据结构-复习,42,const MAXNUM=20;typedef enum DG,UDG GraphKind;,typedef struct ArcCell VRType adj;AdjMatrix MAXNUM MAXNUM;,typedef struct VType vexsMAXNUM;AdjMatrix arcs;int vexnum,arcnum;GraphKind kind;MGraph;,图的数组表示法,数据结构-复习,43,无向图,数据结构-复习,44,有向图,数据结构-复习,45,Status Insert_Vex(MGraph/Insert_Vex,数据结构-复习,46,Status Insert_Arc(MGraph/Insert_Arc,数据结构-复习,47,Status Delete_Vex(MGraph/Delete_Vex,数据结构-复习,48,Status Delete_Arc(MGraph/Delete_Arc,数据结构-复习,49,1.无向图邻接表,对图中每个顶点Vi建立一个单链表,每个链表附设一个头结点,图的链式存储结构邻接表,数据结构-复习,50,无向图邻接表,数据结构-复习,51,有向图的邻接表,数据结构-复习,52,const MAX_VERTEX_NUM=20;typedef struct ArcNode int adjvex;struct ArcNode*nextarc;VRType weight;InfoType*info;,typedef struct VNode VertexType data;ArcNode*firstarc;AdjListMAX_VERTEX_NUM;,typedef struct AdjList vertices;int vexnum,arcnum;GraphKind kind;ALGraph;,数据结构-复习,53,Status Insert_Arc(ALGraph/Insert_Arc,数据结构-复习,54,有向图的邻接表,i=0,j=4,i=1,j=2,