數(shù)據結構代碼匯總

實驗一/*線性表的應用 */#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("超出劃定內存");/ 判斷所存?zhèn)€人信息是否超出內存elseint i=0;for(int i=0;i<n;i+)printf(" 依次輸入inputname();inputtel();姓名性別 年齡電話號碼/ 輸入姓名/ 輸入電話QQ 號Email 地址 (回車鍵隔開)");scanf("%d",ai.age);scanf("%d",ai.tel);scanf("%d",ai.qq);inputemail();/ 輸入email地址/ 輸入第 i 個成員數(shù)據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)建一個姓名輸入方法void inputname()char name20;for(int i=0;i<20;i+)scanf("%c",&namei);/ 創(chuàng)建電話輸入方法void inputtel()char tel15;for(int i=0;i<15;i+)scanf("%c",&teli);/ 創(chuàng)建 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(" 輸入您將輸入的通訊錄人數(shù)");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 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=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;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 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 是函數(shù)的類型,其值是函數(shù)結果狀態(tài)代碼，如OK 等 */typedef structint vexsMAXVEX;int arcMAXVEXMAXVEX;int numVertexes, numEdges;MGraph;typedef int PatharcMAXVEXMAXVEX;typedef int ShortPathTableMAXVEXMAXVEX;/*構件圖*/void CreateMGraph(MGraph *G)int i, j;/* printf(" 請輸入邊數(shù)和頂點數(shù):"); */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;(*P)vw=w;/* Dvw 值即為對應點間的權值/*初始化 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 是函數(shù)的類型,其值是函數(shù)結果狀態(tài)代碼，如OK 等 */int *etv,*ltv; /*事件最早發(fā)生時間和最遲發(fā)生時間數(shù)組，全局變量*/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; /*圖中當前頂點數(shù)和邊數(shù)*/graphAdjList,*GraphAdjList;/* * */void CreateMGraph(MGraph *G)/*構建圖*/int i, j;/* printf(" 請輸入邊數(shù)和頂點數(shù):"); */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;/*用于統(tǒng)計輸出頂點的個數(shù)*/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) ); /*事件最早發(fā)生時間數(shù)組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+;/*輸出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 < GL->numVertexes)return ERROR;elsereturn OK;/* 求關鍵路徑 ,GL 為有向網，輸出 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; 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) /*求各頂點事件的最遲發(fā)生時間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;/*活動最早發(fā)生時間*/lte = ltvk - e->weight; /*活動最遲發(fā)生時間*/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)/ 創(chuàng)建 Hash表int length=12;int mod=13;int account=12;int date;for(int i=0;i<account;i+)/ 輸入數(shù)據printf(" 請輸 入第 &i 個數(shù) 據的值 ",i);/cout<<" 輸 入第 "<<i+1<<"個數(shù) 據"<<endl;scanf("%d",&date);int n=date%mod;if(listn.flag=0)/ 該位置為空則插入到該地址， flag 變?yōu)?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>/* 假設節(jié)點 i 的左右子樹都是最大堆，操作使節(jié)點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");