数据结构代码汇总.docx

精选优质文档-倾情为你奉上实验一 /*线性表的应用*/#include<stdio.h>int 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(n>100) printf("超出划定内存"); /判断所存个人信息是否超出内存else int i=0;for(int i=0;i<n;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;i<20;i+)scanf("%c",&namei);/创建电话输入方法void inputtel()char tel15;for(int i=0;i<15;i+)scanf("%c",&teli);/创建email输入方法void inputemail()char email50;for(int i=0;i<50;i+)scanf("%c",&emaili);/插入方法 插入第i个成员void insert(int k)if(k<0 | k>100) printf("插入位置错");else int i;for(i=n;i<k;i-)ai+1=ai;shuru(k);/删除第k个元素void dele(int k)if(k<0 | k>n) printf("删除位置不存在");elsefor(int k; k<n;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<stdio.h>#include<malloc.h>#include<stdlib.h>using 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.weight<v1)v2=v1;x2=x1;v1=hti.weight;x1=i;else if(hti.weight<v2)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;j<=n;j+)printf("%c",c.bitsj);int main()struct HTNode HT2*n;void OutHuffmanTree(struct HTNode ht2*n);void sethufcode(struct HTNode ht2*n);sethufcode(HT);OutHuffmanTree(HT);printf("n");return 0;实验三 /*最短路径*/#include "stdio.h" #include "stdlib.h" #include "io.h" #include "math.h" #include "time.h"#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define MAXEDGE 20#define MAXVEX 20#define INFINITY 65535typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */typedef structint vexsMAXVEX;int arcMAXVEXMAXVEX;int numVertexes, numEdges;MGraph;typedef int PatharcMAXVEXMAXVEX;typedef int ShortPathTableMAXVEXMAXVEX;/* 构件图 */void CreateMGraph(MGraph *G)int i, j;/* printf("请输入边数和顶点数:"); */G->numEdges=8;G->numVertexes=5;for (i = 0; i < G->numVertexes; i+)/* 初始化图 */G->vexsi=i;for (i = 0; i < G->numVertexes; i+)/* 初始化图 */for ( j = 0; j < G->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 < G->numVertexes; i+)for(j = i; j < G->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; v<G.numVertexes; +v) /* 初始化D与P */ for(w=0; w<G.numVertexes; +w) (*D)vw=G.arcvw;/* Dvw值即为对应点间的权值 */(*P)vw=w;/* 初始化P */for(k=0; k<G.numVertexes; +k) for(v=0; v<G.numVertexes; +v) for(w=0; w<G.numVertexes; +w) if (*D)vw>(*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; v<G.numVertexes; +v) for(w=v+1; w<G.numVertexes; w+) printf("v%d-v%d weight: %d ",v,w,Dvw);k=Pvw;/* 获得第一个路径顶点下标 */printf(" path: %d",v);/* 打印源点 */while(k!=w)/* 如果路径顶点下标不是终点 */printf(" -> %d",k);/* 打印路径顶点 */k=Pkw;/* 获得下一个路径顶点下标 */printf(" -> %dn",w);/* 打印终点 */printf("n");printf("最短路径Dn");for(v=0; v<G.numVertexes; +v) for(w=0; w<G.numVertexes; +w) printf("%dt",Dvw);printf("n");printf("最短路径Pn");for(v=0; v<G.numVertexes; +v) for(w=0; w<G.numVertexes; +w) printf("%d ",Pvw);printf("n");return 0;/*关键路径*/#include "stdio.h" #include "stdlib.h" #include "io.h" #include "math.h" #include "time.h"#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define MAXEDGE 30#define MAXVEX 30#define INFINITY 65535typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */ int *etv,*ltv; /* 事件最早发生时间和最迟发生时间数组，全局变量 */int *stack2; /* 用于存储拓扑序列的栈 */int top2; /* 用于stack2的指针 */* 邻接矩阵结构 */typedef structint vexsMAXVEX;int arcMAXVEXMAXVEX;int numVertexes, numEdges;MGraph;/* 邻接表结构* */typedef struct EdgeNode /* 边表结点 */int adjvex; /* 邻接点域，存储该顶点对应的下标 */int weight;/* 用于存储权值，对于非网图可以不需要 */struct EdgeNode *next; /* 链域，指向下一个邻接点 */EdgeNode;typedef struct VertexNode /* 顶点表结点 */int in;/* 顶点入度 */int data; /* 顶点域，存储顶点信息 */EdgeNode *firstedge;/* 边表头指针 */VertexNode, AdjListMAXVEX;typedef structAdjList adjList; int numVertexes,numEdges; /* 图中当前顶点数和边数 */graphAdjList,*GraphAdjList;/* * */void CreateMGraph(MGraph *G)/* 构建图 */int i, j;/* printf("请输入边数和顶点数:"); */G->numEdges=11;G->numVertexes=8;for (i = 0; i < G->numVertexes; i+)/* 初始化图 */G->vexsi=i;for (i = 0; i < G->numVertexes; i+)/* 初始化图 */for ( j = 0; j < G->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 <G.numVertexes;i+) /* 读入顶点信息，建立顶点表 */(*GL)->adjListi.in=0;(*GL)->adjListi.data=G.vexsi;(*GL)->adjListi.firstedge=NULL; /* 将边表置为空表 */for(i=0;i<G.numVertexes;i+) /* 建立边表 */ for(j=0;j<G.numVertexes;j+)if (G.arcij!=0 && G.arcij<INFINITY)e=(EdgeNode *)malloc(sizeof(EdgeNode);e->adjvex=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; i<GL->numVertexes; i+) if(0 = GL->adjListi.in) /* 将入度为0的顶点入栈 */ stack+top=i; top2=0; etv=(int *)malloc(GL->numVertexes * sizeof(int) ); /* 事件最早发生时间数组 */ for(i=0; i<GL->numVertexes; 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 < GL->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; i<GL->numVertexes; i+) ltvi=etvGL->numVertexes-1; /* 初始化 */ printf("etv:t"); for(i=0; i<GL->numVertexes; 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 < ltvgettop) ltvgettop = ltvk - e->weight; printf("ltv:t"); for(i=0; i<GL->numVertexes; i+) printf("%d -> ",ltvi); printf("n"); for(j=0; j<GL->numVertexes; 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("<v%dv%d>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<stdio.h>#include<math.h>#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;i<MAX;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;i<account;i+)/输入数据printf("请输入第&i个数据的值",i);/cout<<"输入第"<<i+1<<"个数据"<<endl; scanf("%d",&date); int n=date%mod; if(listn.flag=0)/该位置为空则插入到该地址，flag变为1 listn.key=date; listn.flag=1; else/否则链地址解决冲突node *p;p=new node;/定义指针变量p并开辟地址p->key=date; p->next=listn.next;listn.next=p;/前插/else /for /*堆排序*/#include<stdio.h>#include<stdlib.h>/*假设节点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(l<len) if(Al>Ai) large=l; if(r<len) if(Ar>Alarge) large=r; if(large!=i) temp=Alarge; Alarge=Ai; Ai=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;i<len;i+) printf("%d ",Ai); printf("n"); for(i=len;i>1;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;i<11;i+) printf("%d ",Ai); printf("n");专心-专注-专业