《數(shù)據(jù)結構代碼匯總》由會員分享，可在線閱讀，更多相關《數(shù)據(jù)結構代碼匯總（16頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、實驗一/*線性表的應用 */#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(超出劃定內(nèi)存);/ 判斷所存?zhèn)€人信息是否超出內(nèi)存elseint i=0;for(int i=0;in;i+)printf( 依次輸入inputname();inputtel();姓名性別 年齡電話號碼
2、/ 輸入姓名/ 輸入電話QQ 號Email 地址 (回車鍵隔開);scanf(%d,ai.age);scanf(%d,ai.tel);scanf(%d,ai.qq);inputemail();/ 輸入email地址/ 輸入第 i 個成員數(shù)據(jù)void shuru(int i)printf( 依次輸入姓名性別 年齡電話號碼inputname();/ 輸入姓名inputtel();/ 輸入電話scanf(%d,ai.age);scanf(%d,ai.tel);scanf(%d,ai.qq);inputemail();/ 輸入 email 地址QQ 號Email 地址 (回車鍵隔開);/ 創(chuàng)建一個姓名
3、輸入方法void inputname()char name20;for(int i=0;i20;i+)scanf(%c,&namei);/ 創(chuàng)建電話輸入方法void inputtel()char tel15;for(int i=0;i15;i+)scanf(%c,&teli);/ 創(chuàng)建 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;
4、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( 輸入您將輸入的通訊錄人數(shù));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、 5#define m 2*n-1#define infinity 32727struct HTNodeunsigned int weight;unsigned int plink,rlink,llink;*HuffmanTree;struct codetypeint start;char bitsn+1;struct elementchar 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=
6、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.rl
7、ink=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);
8、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;doc.start-;if(s=htf.llink)c.bitsc.start=0;elsec. bitsc.start=1;s=f;f=hts.plink;while(f);tablei.code=c;void OutHuffmanTre
9、e(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 = IN
10、FINITY;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 算法，求網(wǎng)圖 G 中各頂點 v 到其余頂點 w 的最短路徑 Pvw 及帶權長度 Dvw 。void ShortestPath_Floyd(MGraph G, Patharc *P , ShortPathTable *D)int
11、v,w,k;for(v=0; vG.numVertexes; +v) /*初始化 D 與 P */for(w=0; wG.numVertexes; +w)(*D)vw=G.arcvw;(*P)vw=w;/* Dvw 值即為對應點間的權值/*初始化 P */*/for(k=0; kG.numVertexes; +k)for(v=0; vG.numVertexes; +v)for(w=0; w(*D)vk+(*D)kw)/*如果經(jīng)過下標為k 頂點路徑比原兩點間路徑更短*/(*D)vw=(*D)vk+(*D)kw;/*將當前兩點間權值設為更小的一個*/(*P)vw=(*P)vk;/*路徑設置為經(jīng)過下
12、標為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.numVer
13、texes; +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=INFINIT
14、Y;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;fo
15、r(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;/*將當
16、前頂點的指針指向e*/(*GL)-adjListj.in+;/*拓撲排序*/Status TopologicalSort(GraphAdjList GL)/*若 GL 無回路，則輸出拓撲排序序列并返回1，若有回路返回0。 */EdgeNode *e;int i,k,gettop;int top=0;/*用于棧指針下標*/int count=0;/*用于統(tǒng)計輸出頂點的個數(shù)*/int *stack;/*建棧將入度為0 的頂點入棧*/stack=(int *)malloc(GL-numVertexes * sizeof(int) );for(i = 0; inumVertexes; i+)if(0
17、= GL-adjListi.in) /*將入度為 0 的頂點入棧*/stack+top=i;top2=0;etv=(int *)malloc(GL-numVertexes * sizeof(int) ); /*事件最早發(fā)生時間數(shù)組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-adjList
18、gettop.data);count+;/*輸出stack2+top2=gettop;i 號頂點，并計數(shù)*/*將彈出的頂點序號壓入拓撲序列的棧*/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)/*求各頂點事件的最早發(fā)生時間etv 值*/etvk = etvgettop + e-weight;printf(n);if(count
19、numVertexes)return ERROR;elsereturn OK;/* 求關鍵路徑 ,GL 為有向網(wǎng)，輸出 G 的各項關鍵活動 */ void CriticalPath(GraphAdjList GL)EdgeNode *e;int i,gettop,k,j;int ete,lte;/*聲明活動最早發(fā)生時間和最遲發(fā)生時間變量*/TopologicalSort(GL);/*求拓撲序列，計算數(shù)組etv 和 stack2 的值*/ltv=(int *)malloc(GL-numVertexes*sizeof(int);/*事件最早發(fā)生時間數(shù)組for(i=0; inumVertexes;
20、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) /*求各頂點事件的最遲發(fā)生時間ltv 值 */k=e-adjvex;if(ltvk - e-weight weight;printf(ltv:t);for(i=0; inumVertexes; i
21、+)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;/*活動最早發(fā)生時間*/lte = ltvk - e-weight; /*活動最遲發(fā)生時間*/if(ete = lte)/*兩者相等即在關鍵路徑上*/printf(length:%dn,GL-adjListj.data,GL-adjListk.data,e-weight);int main(void)MGraph G
22、;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;lis
23、ti.l=0;listi.next=NULL;void creat_table(Hashtable&list)/ 創(chuàng)建 Hash表int length=12;int mod=13;int account=12;int date;for(int i=0;iaccount;i+)/ 輸入數(shù)據(jù)printf( 請輸 入第 &i 個數(shù) 據(jù)的值 ,i);/cout 輸 入第 i+1個數(shù) 據(jù)key=date;p-next=listn.next;listn.next=p;/ 前插/else/for/*堆排序 */#include#include/* 假設節(jié)點 i 的左右子樹都是最大堆，操作使節(jié)點i 的子樹變成
24、最大堆*/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=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);
數(shù)據(jù)結構代碼匯總
