数据结构代码汇总(13页).doc

《数据结构代码汇总(13页).doc》由会员分享，可在线阅读，更多相关《数据结构代码汇总(13页).doc（13页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、-数据结构代码汇总-第 13 页实验一 /*线性表的应用*/#includeint n,j,k; /声明结构体类型，并确定其成员变量typedef struct student char name20;char sex5;int age;long long tel;long qq;char email50;person;person a100;/输入链表的个人信息void creat(int n)if(n100) printf(超出划定内存); /判断所存个人信息是否超出内存else int i=0;for(int i=0;in;i+)printf(依次输入 姓名 性别 年龄 电话号码 QQ号

2、 Email地址(回车键隔开);inputname(); /输入姓名inputtel(); /输入电话scanf(%d,ai.age); scanf(%d,ai.tel);scanf(%d,ai.qq);inputemail(); /输入email地址/输入第i个成员数据void shuru(int i)printf(依次输入 姓名 性别 年龄 电话号码 QQ号 Email地址(回车键隔开);inputname(); /输入姓名inputtel(); /输入电话scanf(%d,ai.age); scanf(%d,ai.tel);scanf(%d,ai.qq);inputemail(); /输

3、入email地址/创建一个姓名输入方法void inputname()char name20;for(int i=0;i20;i+)scanf(%c,&namei);/创建电话输入方法void inputtel()char tel15;for(int i=0;i15;i+)scanf(%c,&teli);/创建email输入方法void inputemail()char email50;for(int i=0;i50;i+)scanf(%c,&emaili);/插入方法 插入第i个成员void insert(int k)if(k100) printf(插入位置错);else int i;for

4、(i=n;ik;i-)ai+1=ai;shuru(k);/删除第k个元素void dele(int k)if(kn) printf(删除位置不存在);elsefor(int k; kn;k+)ak=ak+1;void main()printf(输入您将输入的通讯录人数);scanf(%d,&n);creat(n);printf(输入插入的位置);scanf(%d,&k);insert(k);printf(输入删除的位置);scanf(%d,&j);creat(j);实验二/*求哈夫曼编码*/#include#include#includeusing namespace std;#define

5、n 5#define m 2*n-1#define infinity 32727struct HTNodeunsigned int weight;unsigned int plink,rlink,llink;*HuffmanTree;struct codetype int start; char bitsn+1;struct element char symbol; codetype code;struct element tablen+1;inline void select(struct HTNode ht2*n,int s,int &x1,int &x2)int i; float v1,

6、v2; v1=v2=infinity; x1=x2=0; for(i=1;i=s;i+)if(hti.plink=0)if(hti.weightv1)v2=v1;x2=x1;v1=hti.weight;x1=i;else if(hti.weightv2)v2=hti.weight;x2=i;void set_huffmantree(struct HTNode ht2*n)inline void select(struct HTNode ht2*n,int s,int &x1,int &x2);int i;int s1,s2; for (i=1;i=m;+i)hti.plink= hti.lli

7、nk= hti.rlink=0; for (i=n+1;i=m;+i)/建哈夫曼树select(ht,i-1,s1,s2);/在htk(1=k=i-1)中选择两个双亲域为零的最小的/ 结点 :s1和s2 (s1和s2为最小值所在的下标) hts1.plink= hts2.plink=i;hti.llink=s1; hti.rlink=s2; hti.weight=hts1.weight + hts2.weight;void sethufcode(struct HTNode ht2*n)struct HTNode *p=ht;void set_huffmantree(struct HTNode

8、ht2*n);int i,s,f; codetype c; for(i=1;i=n;i+)printf(请输入字符：); scanf(%s,&tablei.symbol);printf(请输入相应的权值：);scanf(%d,&hti.weight); set_huffmantree(p); for(i=1;i=n;i+) c.start=n+1; s=i; f=hts.plink; do c.start-; if(s=htf.llink) c.bitsc.start=0; else c. bitsc.start=1; s=f; f=hts.plink; while(f);tablei.cod

9、e=c;void OutHuffmanTree(struct HTNode ht2*n)int i,j;codetype c;for(i=1;i=n;i+) printf(n%c,tablei.symbol); c=tablei. code;for(j=c.start;jnumEdges=8;G-numVertexes=5;for (i = 0; i numVertexes; i+)/* 初始化图 */G-vexsi=i;for (i = 0; i numVertexes; i+)/* 初始化图 */for ( j = 0; j numVertexes; j+)if (i=j)G-arcij=

10、0;elseG-arcij = G-arcji = INFINITY;G-arc01=3;G-arc04=30; G-arc12=25; G-arc13=8; G-arc24=10; G-arc34=12; G-arc30=20; G-arc32=4;G-arc40=15;for(i = 0; i numVertexes; i+)for(j = i; j numVertexes; j+)G-arcji =G-arcij;/ Floyd算法，求网图G中各顶点v到其余顶点w的最短路径Pvw及带权长度Dvw。 void ShortestPath_Floyd(MGraph G, Patharc *P,

11、 ShortPathTable *D)int v,w,k; for(v=0; vG.numVertexes; +v) /* 初始化D与P */ for(w=0; wG.numVertexes; +w) (*D)vw=G.arcvw;/* Dvw值即为对应点间的权值 */(*P)vw=w;/* 初始化P */for(k=0; kG.numVertexes; +k) for(v=0; vG.numVertexes; +v) for(w=0; w(*D)vk+(*D)kw)/* 如果经过下标为k顶点路径比原两点间路径更短 */(*D)vw=(*D)vk+(*D)kw;/* 将当前两点间权值设为更小的

12、一个 */(*P)vw=(*P)vk;/* 路径设置为经过下标为k的顶点 */int main(void)int v,w,k; MGraph G; Patharc P; ShortPathTable D; /* 求某点到其余各点的最短路径 */ CreateMGraph(&G);ShortestPath_Floyd(G,&P,&D); printf(各顶点间最短路径如下:n); for(v=0; vG.numVertexes; +v) for(w=v+1; w %d,k);/* 打印路径顶点 */k=Pkw;/* 获得下一个路径顶点下标 */printf( - %dn,w);/* 打印终点 *

13、/printf(n);printf(最短路径Dn);for(v=0; vG.numVertexes; +v) for(w=0; wG.numVertexes; +w) printf(%dt,Dvw);printf(n);printf(最短路径Pn);for(v=0; vG.numVertexes; +v) for(w=0; wnumEdges=11;G-numVertexes=8;for (i = 0; i numVertexes; i+)/* 初始化图 */G-vexsi=i;for (i = 0; i numVertexes; i+)/* 初始化图 */for ( j = 0; j num

14、Vertexes; j+)if (i=j)G-arcij=0;elseG-arcij=INFINITY;G-arc01=6;G-arc02=4;G-arc03=5;G-arc14=1;G-arc24=1;G-arc35=2;G-arc46=9;G-arc47=7;G-arc57=4;G-arc68=2;G-arc78=4;/* 利用邻接矩阵构建邻接表 */void CreateALGraph(MGraph G,GraphAdjList *GL)int i,j;EdgeNode *e;*GL = (GraphAdjList)malloc(sizeof(graphAdjList);(*GL)-nu

15、mVertexes=G.numVertexes;(*GL)-numEdges=G.numEdges;for(i= 0;i adjListi.in=0;(*GL)-adjListi.data=G.vexsi;(*GL)-adjListi.firstedge=NULL; /* 将边表置为空表 */for(i=0;iG.numVertexes;i+) /* 建立边表 */for(j=0;jG.numVertexes;j+)if (G.arcij!=0 & G.arcijadjvex=j;/* 邻接序号为j */ e-weight=G.arcij;e-next=(*GL)-adjListi.first

16、edge;/* 将当前顶点上的指向的结点指针赋值给e */(*GL)-adjListi.firstedge=e;/* 将当前顶点的指针指向e */ (*GL)-adjListj.in+;/* 拓扑排序 */Status TopologicalSort(GraphAdjList GL) /* 若GL无回路，则输出拓扑排序序列并返回1，若有回路返回0。 */ EdgeNode *e; int i,k,gettop; int top=0; /* 用于栈指针下标 */int count=0;/* 用于统计输出顶点的个数 */ int *stack;/* 建栈将入度为0的顶点入栈 */ stack=(i

17、nt *)malloc(GL-numVertexes * sizeof(int) ); for(i = 0; inumVertexes; i+) if(0 = GL-adjListi.in) /* 将入度为0的顶点入栈 */ stack+top=i; top2=0; etv=(int *)malloc(GL-numVertexes * sizeof(int) ); /* 事件最早发生时间数组 */ for(i=0; inumVertexes; i+) etvi=0; /* 初始化 */stack2=(int *)malloc(GL-numVertexes * sizeof(int) );/*

18、初始化拓扑序列栈 */printf(TopologicalSort:t);while(top!=0) gettop=stacktop-; printf(%d - ,GL-adjListgettop.data); count+; /* 输出i号顶点，并计数 */ stack2+top2=gettop; /* 将弹出的顶点序号压入拓扑序列的栈 */for(e = GL-adjListgettop.firstedge; e; e = e-next) k=e-adjvex; if( !(-GL-adjListk.in) ) /* 将i号顶点的邻接点的入度减1，如果减1后为0，则入栈 */ stack+

19、top=k; if(etvgettop + e-weight)etvk) /* 求各顶点事件的最早发生时间etv值 */ etvk = etvgettop + e-weight;printf(n); if(count numVertexes) return ERROR; else return OK;/* 求关键路径,GL为有向网，输出G的各项关键活动 */void CriticalPath(GraphAdjList GL) EdgeNode *e; int i,gettop,k,j; int ete,lte; /* 声明活动最早发生时间和最迟发生时间变量 */ TopologicalSort

20、(GL); /* 求拓扑序列，计算数组etv和stack2的值 */ ltv=(int *)malloc(GL-numVertexes*sizeof(int);/* 事件最早发生时间数组 */ for(i=0; inumVertexes; i+) ltvi=etvGL-numVertexes-1; /* 初始化 */ printf(etv:t); for(i=0; inumVertexes; i+) printf(%d - ,etvi); printf(n); while(top2!=0) /* 出栈是求ltv */ gettop=stack2top2-; for(e = GL-adjList

21、gettop.firstedge; e; e = e-next) /* 求各顶点事件的最迟发生时间ltv值 */ k=e-adjvex; if(ltvk - e-weight weight; printf(ltv:t); for(i=0; inumVertexes; i+) printf(%d - ,ltvi); printf(n); for(j=0; jnumVertexes; j+) /* 求ete,lte和关键活动 */ for(e = GL-adjListj.firstedge; e; e = e-next) k=e-adjvex; ete = etvj; /* 活动最早发生时间 */

22、 lte = ltvk - e-weight; /* 活动最迟发生时间 */ if(ete = lte) /* 两者相等即在关键路径上 */ printf(length:%dn,GL-adjListj.data,GL-adjListk.data,e-weight);int main(void)MGraph G; GraphAdjList GL; CreateMGraph(&G);CreateALGraph(G,&GL);CriticalPath(GL);system(pause);return 0;实验四/*Hash存储*/#include#include#define MAX 30typed

23、ef struct nodeint key;int flag;int l;node *next;HashtableMAX;Hashtable table;void Init_table(Hashtable&list)/初始化HASH表for (int i=0;iMAX;i+)listi.flag=0;listi.l=0;listi.next=NULL;void creat_table(Hashtable&list)/创建Hash表int length=12;int mod=13;int account=12;int date;for(int i=0;iaccount;i+)/输入数据print

24、f(请输入第&i个数据的值,i);/cout输入第i+1个数据key=date; p-next=listn.next;listn.next=p;/前插/else /for /*堆排序*/#include#include/*假设节点i的左右子树都是最大堆，操作使节点i的子树变成最大堆*/void maxHeap(int A,int len,int i) int l,r,large,temp; l=2*i; r=2*i+1; large=i; if(lAi) large=l; if(rAlarge) large=r; if(large!=i) temp=Alarge; Alarge=Ai; Ai=

25、temp; maxHeap(A,len,large);/*建立大顶堆*/void buildMaxHeap(int A,int len) int i; for(i=len/2-1;i=0;i-) maxHeap(A,len,i);/*堆排序*/void maxHeapSort(int A,int len) int i,temp; buildMaxHeap(A,len); printf(建立大顶堆n); for(i=0;i1;i-) temp=A0; A0=Ai-1; Ai-1=temp; printf(%d ,Ai-1); buildMaxHeap(A,i-1); printf(n);/*测试堆排序*/int main() int i; int A12=14,1,68,27,55,23,11,10,19,20,79,84; maxHeapSort(A,11); for(i=0;i11;i+) printf(%d ,Ai); printf(n);