数据结构代码汇总.docx

实验一 /*线性表的应用*/#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号 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(); /输入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(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 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,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.llink= 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 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.code=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=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, 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;/* 将当前两点间权值设为更小的一个 */(*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);/* 打印终点 */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 numVertexes; 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)-numVertexes=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.firstedge;/* 将当前顶点上的指向的结点指针赋值给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=(int *)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) );/* 初始化拓扑序列栈 */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+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(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-adjListgettop.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; /* 活动最早发生时间 */ 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 30typedef 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;f