《数据结构习题集教案资料》由会员分享，可在线阅读，更多相关《数据结构习题集教案资料（54页珍藏版）》请在金锄头文库上搜索。
1、数据结构-复习,1,数据结构题集-2,P14：2.6 、2.7 P15: 2.9 P17: 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-
2、next-prior = p;,p,删除元素算法2.8(c),删除结点P 的后继元素,数据结构-复习,6,2.11,Status Insert_SqList(SqList /Insert_SqList,数据结构-复习,7,2.19,Status Delete_Between(Linklist /Delete_Between,数据结构-复习,8,其它习题,P16:2.10 2.12 P18:2.21 2.22 2.24 2.29 2.33,数据结构-复习,9,2.10,Status DeleteK(SqList /DeleteK,数据结构-复习,10,2.12,int ListComp(SqLi
3、st 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
4、,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,数据结构-复
5、习,17,数据结构题集-3,P22:3.3 P23:3.9 3.12 P24:3.16 P25: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
6、InitCiQueue(CiQueue /InitCiQueue,数据结构-复习,20,void EnCiQueue(CiQueue /修改尾指针,3.28,数据结构-复习,21,Status DeCiQueue(CiQueue /DeCiQueue,3.28,数据结构-复习,22,P22:3.4 P23:3.10 P24:3.13 3.15 3.17 3.19 3.21 P26:3.30 3.31,其它习题,数据结构-复习,23,typedef struct Elemtype *base2; Elemtype *top2;BDStacktype; /双向栈类型 Status Init_Sta
7、ck(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(
8、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
9、(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(
10、)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.1 P32:5.2 P35:5.21 5.22,数据结构-复习,33,void TSMatrix_Add(TSMatrix A,TSMatrix B,TSMatrix /if,else if(A.datapa.jB
11、.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.d
12、atapc.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.1 P41:6.22 6.23 6.24 6.26 6.27 6.28 P42: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/P
13、reOrder_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); /访问结
14、点,返回/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,数据结构-
15、复习,39,数据结构题集-7,P47:7.8 P48:7.15 7.16,数据结构-复习,40,最小生成树-普里姆算法,取图中任意一个顶点 v 作为生成树的根，之后往生成树上添加新的顶点 w。在添加的顶点 w 和已经在生成树上的顶点v 之间必定存在一条边，并且该边的权值在所有连通顶点 v 和 w 之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树上含有 n-1 个顶点为止。,数据结构-复习,41,最小生成树-克鲁斯卡尔算法,先构造一个只含 n 个顶点的子图 SG，然后从权值最小的边开始，若它的添加不使SG 中产生回路，则在 SG 上加上这条边，如此重复，直至加上 n-1 条边为止,数据
16、结构-复习,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
