数据结构习题.doc

数据结构习题与实验目录习题一1习题二4习题三7一元多项式之和实验8哈夫曼树实验13求最小生成树算法实验17拓扑排序算法22求最短路径（迪接斯特算法）28关键路径35快速排序43习题一、请设计一算法：已知顺序表L，表中元素为整型且递增有序，现有一值为e的元素要插入L表，使插入后L表仍然有序。、已知L为非递减的顺序表，请设计算法删除L中重复的元素（即删除后使L表变为一递增表）。#include#include#include#define LIST_SIZE 100#define OK 1typedef structint *elem;int length;int listsize;SqList;int InitList_Sq(SqList &L) L.elem=(int*)malloc(LIST_SIZE*sizeof(int); if(!L.elem) exit(0); L.length=0; L.listsize=LIST_SIZE; return OK;void ListCreate(SqList &L,int i)if(iL.listsize)exit(0);for(int j=0;ji;j+)scanf(%d,&L.elemj);L.length+; int SortInsert(SqList &L,int e) int i,k=0; int *p,*q; p=L.elem; q=L.elem+L.length-1; for(i=1;i=L.length;i+) if(ep;q-) *q=*(q-1); *p=e; k=1; break; else p+; if(k=0) *(q+1)=e; L.length+; return OK;void main() void ListCreate(SqList &L,int i); int InitList_Sq(SqList &L); int SortInsert(SqList &L,int e); int i; SqList La; InitList_Sq(La); ListCreate(La,3); int a; printf(需要插入的数字： ); scanf(%d,&a); SortInsert(La,a); printf(插入后的元素列表变为：n); for(i=0;iLa.length;i+) printf(%d ,La.elemi); printf(n);/*void SortDeleSame(SqList &L) int *i; int *p; int *q; p=L.elem; q=L.elem+L.length-1; while(pq) if(*p=*(p+1) for(i=p;iq;i+) *i=*(i+1); L.length-; q-; else p+; void main() int InitList_Sq(SqList &L); void SortDeleSame(SqList &L); void ListCreate(SqList &L,int i); int i; SqList Lb; InitList_Sq(Lb); ListCreate(Lb,5); SortDeleSame(Lb); printf(n); for(i=0;iLb.length;i+) printf(%d ,Lb.elemi); */习题二、已知带头结点的动态单链表L中的结点是按整数值递增排列的，试写一算法将值x为的结点插入到表L中，使L仍然有序。#include#include#includetypedef struct LNodeint data;struct LNode *next;LNode,*LinkList;void main() void CreatList_LinkList(LinkList &L,int n); void ListInsert_LinkList(LinkList &L,int x); void Print_LinkList(LinkList &L,int n); LinkList La; int a,b; printf(请问要输入多少数：); scanf(%d,&a); printf(请输入这%d个数：n,a); CreatList_LinkList(La,a); printf(请问要插入的数是：); scanf(%d,&b); ListInsert_LinkList(La,b); printf(插入后结果为:n); Print_LinkList(La,a+1); printf(n);void CreatList_LinkList(LinkList &L,int n)int i,a;LNode *s,*tail;L=(LinkList)malloc(sizeof(LNode);L-next=NULL;tail=L;for(i=0;idata);tail-next=s;tail=tail-next;tail-next=NULL;void Print_LinkList(LinkList &L,int n) LNode* p; p=L-next; for(int i=0;idata); p=p-next; void ListInsert_LinkList(LinkList &L,int x) int k=0; LNode *pre,*p,*s; pre=L; p=L-next; while(pre&p) if(xdata) s=(LinkList)malloc(sizeof(LNode); s-next=pre-next; pre-next=s; s-data=x; k=1; break; pre=pre-next; p=p-next; if(k=0) s=(LinkList)malloc(sizeof(LNode); pre-next=s; s-data=x; s-next=NULL; 习题三、设计一算法，逆置带头结点的动态单链表L。/La为已知单链表，Lb为新建的一个单链表void Trunhead_LinkList(LinkList &La,LinkList &Lb,int n) LinkList p=La-next; LinkList s; Lb=(LinkList)malloc(sizeof(LNode); Lb-next=NULL; for(i=0;idata=p-data; s-next=Lb-next; Lb-next=s; p=p-next; 一元多项式之和实验#include #include #include typedef struct polynode float coef; /系数int expn; /指数struct polynode *next;polynode,*polylist;void create(polylist &L) /创建链表 int m; polylist p; printf(请输入一元多项式项数：); scanf(%d,&m); L=(polylist)malloc(sizeof(polynode); p=L; for(int i=1;inext=(polylist)malloc(sizeof(polynode); p=p-next; printf(请输入第%d项的系数和指数：,i); scanf(%f %d,&p-coef,&p-expn); p-next=NULL;void display(polylist L) /显示链表内容 polylist p; p=L-next; printf(%.0fx(%d),p-coef,p-expn); p=p-next; while(p) if(p-coefcoef,p-expn); else printf(+%.0fx(%d),p-coef,p-expn); p=p-next; printf(n);void add(polylist La, polylist Lb, polylist &Lc) /加法函数 polylist pa,pb,pc; float x; pa=La-next ; pb=Lb-next ; pc=(polylist)malloc(sizeof(polynode); Lc=pc; while (pa&pb) if(pa-expn=pb-expn) x=pa-coef+pb-coef; if(x!=0) pc-next=(polylist)malloc(sizeof(polynode); pc=pc-next; pc-coef=x; pc-expn=pa-expn; pa=pa-next; pb=pb-next; else / 无同类项可合并，指数小者复制到C表 pc-next=(polylist)malloc(sizeof(polynode); pc=pc-next; if(pa-expn expn) /a的指数小于b的指数 pc-coef=pa-coef; pc-expn=pa-expn; pa=pa-next; else pc-coef=pb-coef; pc-expn=pb-expn; pb=pb-next; while(pa) /还剩下a多项式 pc-next=(polylist)malloc(sizeof(polynode); pc=pc-next; pc-coef=pa-coef; pc-expn=pa-expn; pa=pa-next; while(pb) /还剩下b多项式 pc-next=(polylist)malloc(sizeof(polynode); pc=pc-next; pc-coef=pb-coef; pc-expn=pb-expn; pb=pb-next; pc-next=NULL;void subtract(polylist La,polylist Lb,polylist &Lc) /减法函数 polylist pa,pb,pc; float x; pa=La-next ; pb=Lb-next ; pc=(polylist)malloc(sizeof(polynode); Lc=pc; while(pa&pb) if(pa-expn=pb-expn) x=pa-coef-pb-coef; if(x!=0) pc-next=(polylist)malloc(sizeof(polynode); pc=pc-next; pc-coef=x; pc-expn=pa-expn; pa=pa-next; pb=pb-next; else /无同类项可合并，指数小者复制到C表 pc-next=(polylist)malloc(sizeof(polynode); pc=pc-next; if (pa-expnexpn) /a的指数小于b的指数 pc-coef=pa-coef; pc-expn=pa-expn; pa=pa-next; else pc-coef=-pb-coef; pc-expn=pb-expn; pb=pb-next; while(pa) /还剩下a多项式 pc-next=(polylist)malloc(sizeof(polynode); pc=pc-next; pc-coef=pa-coef; pc-expn=pa-expn; pa=pa-next; while (pb) /还剩下b多项式 pc-next=(polylist)malloc(sizeof(polynode); pc=pc-next; pc-coef=-pb-coef; pc-expn=pb-expn; pb=pb-next; pc-next=NULL;void main() /主函数polylist La,Lb,Lc,Ld;create(La); create(Lb);printf(一元多项式1：);display(La);printf(一元多项式2：);display(Lb);add(La,Lb,Lc);printf(加的结果：);display(Lc);subtract(La,Lb,Ld);printf(减的结果);display(Ld);哈夫曼树实验#include#include#include#includetypedef structchar ch;int weight;int parent,lchild,rchild;HTNode,*HuffmanTree;typedef char*HuffmanCode;void CreateHuffmanTree(HuffmanTree &HT,int w,char ch,int n);void Select(HuffmanTree HT,int n,int &s1,int &s2);void HTCoding(HuffmanTree HT,HuffmanCode &HC,int n);void PrintCode(HuffmanCode HC,int n,char ch);double AverageLength(HuffmanTree HT,HuffmanCode HC,int n);void DeCode(HuffmanTree HT,int n);void main() /主函数int n;int i;char arrch20;int arrweight20; double avlength;char ch;HuffmanTree HT;HuffmanCode HC;printf(请输入要输入字母的个数：);scanf(%d,&n);while(ch=getchar()!=n);if(n20|n2) exit(0);for(i=0;in;i+) printf(请输入第%d个字母：,i+1); scanf(%c,&arrchi); printf(请输入该字母权重：); scanf(%d,&arrweighti); while(ch=getchar()!=n);CreateHuffmanTree(HT,arrweight,arrch,n);HTCoding(HT,HC,n);PrintCode(HC,n,arrch); avlength=AverageLength(HT,HC,n); printf(平均编码长度为：%.2fn,avlength);printf(请输入要解码的数据：);DeCode(HT,n);for(i=0;in;i+) free(HCi);free(HC);free(HT);void CreateHuffmanTree(HuffmanTree &HT,int w,char ch,int n)int i,m,s1,s2;m=2*n-1;HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);for(i=1;i=n;i+)HTi.weight=wi-1;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;HTi.ch=chi-1;for(i=n+1;i=m;i+)HTi.weight=0;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;HTi.ch=0;for(i=n+1;i=m;i+)Select(HT,i-1,s1,s2);HTs1.parent=i; HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;void Select(HuffmanTree HT,int n,int &s1,int &s2)int i;int min;min=1000;for(i=1;i=n;i+) if(HTi.parent=0&HTi.weight=min) min=HTi.weight; s1=i; min=1000; for(i=1;i=n;i+) if(HTi.parent=0&HTi.weight=min&i!=s1) min=HTi.weight; s2=i; void HTCoding(HuffmanTree HT,HuffmanCode &HC,int n) int i,j,k,start;int f;int c;char* cd;HC=(HuffmanCode)malloc(n)*sizeof(char*);cd=(char*)malloc(n*sizeof(char);cdn-1=0;for(i=1;i=n;+i) start=n-1; for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)if(HTf.lchild=c)cd-start=0;elsecd-start=1;HCi-1=(char*)malloc(n-start)*sizeof(char);for(j=start,k=0;jn;j+,k+) HCi-1k=cdj;free(cd);void PrintCode(HuffmanCode HC,int n,char ch)for(int i=0;in;i+) printf(%c的编码是%sn,chi,HCi);double AverageLength(HuffmanTree HT,HuffmanCode HC,int n) int i,j;int s1=0,s2=0; for(i=1;i=n;i+)s1=s1+HTi.weight;for(i=0,j=1;in;i+,j+) s2=s2+HTj.weight*strlen(HCi);return s2*1.0/s1;void DeCode(HuffmanTree HT,int n)int i;char endflag=#;char ch;i=2*n-1; scanf(%c,&ch);while(ch!=endflag)if(ch=0)i=HTi.lchild;elsei=HTi.rchild;if(HTi.lchild=0)printf(%c,HTi.ch);i=2*n-1; scanf(%c,&ch);if(HTi.lchild!=0)&(i!=2*n-1)printf(n未能完全解码n);printf(n);求最小生成树算法实验#include#include#define INFINITY 10000 /最大值#define MAX_VERTEX_NUM 20 /最大顶点数typedef structchar vexsMAX_VERTEX_NUM;int arcsMAX_VERTEX_NUMMAX_VERTEX_NUM;int vexnum,arcnum;MGraph;typedef structint adjvex;int endvex;int lowcost;closedgeMAX_VERTEX_NUM;void main() void CreateUDN(MGraph &G);/创建无向网络 int LocateVex(MGraph G,char v);/结点在顶点向量中的下标 void PrintUDN(MGraph G);/输出存储结构示意图 void MiniSpanTree_PRIM(MGraph G,closedge &minedge);/求最小生成树的算法 void PrintMinEdge(MGraph G,closedge minedge);/输出最小生成树的边 MGraph G; closedge minedge; CreateUDN(G); printf(n该图的邻接矩阵存储示意图如下：n); PrintUDN(G); printf(n); MiniSpanTree_PRIM(G,minedge); printf(该图生成树的边如下：n); PrintMinEdge(G,minedge); printf(n);int LocateVex(MGraph G,char v) /结点在顶点向量中的下标 int i; for(i=0;iG.vexnum;i+) if(v=G.vexsi) return i; void CreateUDN(MGraph &G) /创建无向网络 int i,j,k,w; char v1,v2,ch; printf(请输入该网络的结点数：); scanf(%d,&G.vexnum); printf(请输入该网络的边数：); scanf(%d,&G.arcnum); printf(请输入这%d个结点：n,G.vexnum); while(ch=getchar()!=n); /这条很关键不可少！ for(i=0;iG.vexnum;i+) scanf(%c,&G.vexsi); for(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+) G.arcsij=INFINITY; for(k=0;kG.arcnum;k+) printf(请输入第%d条边及它的权重：,k+1); while(ch=getchar()!=n); /这条很关键不可少！ scanf(%c%c %d,&v1,&v2,&w); i=LocateVex(G,v1); j=LocateVex(G,v2); G.arcsij=w; G.arcsji=w; for(i=0;iG.vexnum;i+) G.arcsii=0; void PrintUDN(MGraph G) /输出存储结构示意图int i,j;printf( );for(i=0;iG.vexnum;i+) printf(%6c,G.vexsi);printf(n);for(i=0;iG.vexnum;i+)printf(%c,G.vexsi);for(j=0;jG.vexnum;j+)if(G.arcsij=10000)printf( );elseprintf(%6d,G.arcsij);printf(n);void MiniSpanTree_PRIM(MGraph G,closedge &minedge) /求最小生成树的算法 int i,j,k,z; int temp; int currentmin; k=0; for(j=1;jG.vexnum;j+) minedgej-1.adjvex=k; minedgej-1.endvex=j; minedgej-1.lowcost=G.arcskj; for(i=0;iG.vexnum-1;i+) currentmin=minedgei.lowcost; k=i; for(j=i+1;jG.vexnum-1;j+) if(minedgej.lowcostcurrentmin) currentmin=minedgej.lowcost; k=j; temp=minedgei.adjvex; minedgei.adjvex=minedgek.adjvex; minedgek.adjvex=temp; temp=minedgei.endvex; minedgei.endvex=minedgek.endvex; minedgek.endvex=temp; temp=minedgei.lowcost; minedgei.lowcost=minedgek.lowcost; minedgek.lowcost=temp; for(j=i+1;jG.vexnum-1;j+) z=minedgei.endvex; k=minedgej.endvex; if(k!=z) if(G.arcszkminedgej.lowcost) minedgej.adjvex=z; minedgej.lowcost=G.arcszk; void PrintMinEdge(MGraph G,closedge minedge) /输出最小生成树的边 int i; for(i=0;iG.vexnum-1;i+) printf(%c%c %dn,G.vexsminedgei.adjvex,G.vexsminedgei.endvex,minedgei.lowcost); 拓扑排序算法#include#include#define MAX_VERTEX_NUM 20typedef struct ArcNode/表结点 int adjvex;/该弧所指向的顶点位置 struct ArcNode *nextarc;/指向下一条弧的指针ArcNode;typedef struct VNode/头结点char data;/顶点信息ArcNode *firstarc;/指向第一条依附于该顶点的弧的指针VNode;typedef VNode AdjListMAX_VERTEX_NUM;/邻接表typedef struct /图 AdjList vertices;/邻接表verticesint vexnum,arcnum;/图当前的定点数和弧数ALGraph;typedef struct /栈的存储结构 int *base;/在栈构造之前和销毁之后，base的值为NULLint *top;/栈顶指针int stacksize;/当前已分配的存储空间SqStack;void InitStack(SqStack &S) /构造一个空栈 S.base=(int*)malloc(30*sizeof(int);if(!S.base)exit(0);S.top=S.base;S.stacksize=30;int StackEmpty(SqStack S) /判断是否为空栈，若栈为空返回TRUE，不为空返回FALSEif(S.base=S.top)return true;elsereturn false;void Push(SqStack &S,int e) /插入新的栈顶元素if(S.top-S.base=S.stacksize)S.base=(int*)realloc(S.base,(S.stacksize+100)*sizeof(int);/存储空间增加100if(!S.base)exit(0);S.top=S.base+S.stacksize;S.stacksize+=100;/栈的容量增加100*S.top=e;S.top+;void Pop(SqStack &S,int &e) /弹出栈顶元素，用e返回 if(S.top=S.base)exit(0);S.top-;e=*S.top;int LocateVex(ALGraph G,char v) /结点在顶点向量中的下标 int i; for(i=0;iadjvex+; p=p-nextarc; if(!p) /如果p为空，则从查找下一个顶点 k+; if(kG.vexnum) p=G.verticesk.firstarc; else break; void CreateALGraph(ALGraph &G) /创建一个邻接表int i,k,a,b;char ch,v0,v1; ArcNode *p;printf(请输入结点数：);scanf(%d,&G.vexnum);printf(请输入边数：);scanf(%d,&G.arcnum);printf(请输入顶点信息：n);while(ch=getchar()!=n);for(i=0;iv1)n);for(k=0;k%c,&v0,&v1); a=LocateVex(G,v0); b=LocateVex(G,v1); p=(ArcNode*)malloc(sizeof(ArcNode); p-adjvex=b; p-nextarc=G.verticesa.firstarc; G.verticesa.firstarc=p;void TopologicalSort(ALGraph G) /拓扑算法int i,count;SqStack S;ArcNode *p;int indegreeMAX_VERTEX_NUM=0; FindInDegree(G,indegree);InitStack(S);for(i=0;inextarc)indegreep-adjvex-;if(!indegreep-adjvex)Push(S,p-adjvex);while(!StackEmpty(S) /当栈为空时跳出循环Pop(S,i);printf(-%c,G.verticesi.data);count+;for(p=G.verticesi.firstarc;p;p=p-nextarc)indegreep-adjvex-;if(!indegreep-adjvex) /如果该结点入度为0，则压入栈Push(S,p-adjvex);if(countG.vexnum)printf(错误！);void main() /主函数ALGraph G