《數(shù)據(jù)結(jié)構(gòu)》實訓(xùn)報告

1、實驗一 線性表1. 實驗要求1.1 掌握數(shù)據(jù)結(jié)構(gòu)中線性表的基本概念。1.2 熟練掌握線性表的基本操作：創(chuàng)建、插入、刪除、查找、輸出、求長度及合并并運算在順序存儲結(jié)構(gòu)上的實驗。1.3 熟練掌握鏈表的各種操作和應(yīng)用。2. 實驗內(nèi)容2.1 編寫一個函數(shù)，從一個給定的順序表A中刪除元素值在x到y(tǒng)之間的所有元素，要求以較高效率來實現(xiàn)。2.2 試寫一個算法，在無頭結(jié)點的動態(tài)單鏈表上實現(xiàn)線性表插入操作2.3 設(shè)計一個統(tǒng)計選票的算法，輸出每個候選人的得票結(jié)果。3. 實驗代碼2.1代碼：#includetypedef int elemtype;#define maxsize 10int del(int A,in

2、t n,elemtype x,elemtype y)int i=0,k=0;while(i=x&Ai=y)k+;elseAi-k=Ai;i+;return(n-k);void main()int i,j;int amaxsize;printf(輸入%d個數(shù):n,maxsize);for(i=0;imaxsize;i+)scanf(%d,&ai); j=del(a,maxsize,1,3); printf(輸出刪除后剩下的數(shù):n); for(i=0;idata=x;s-next=L;L=s;elsep=L;j=1;while(p&jnext;if(p|ji-1)return error;s=(L

3、inklist)malloc(sizeof(Lnode);s-data=x;s-next=p-next;p-next=s;2.3代碼：typedef int elemtypetypedef struct linknodeelemtype data;struct linknode *next;nodetype;nodetype *create()elemtype d;nodetype h=NULL,*s,*t;int i=1;printf(建立單鏈表:n);while(1)printf(輸入第%d個結(jié)點數(shù)據(jù)域,i);scanf(%d,&d);if(d=0)break;if(i=1)h=(node

4、type *)malloc(sizeof(nodetype);h-data=d;h-next=NULL;t=h;elses=(nodetype *)malloc(sizeof(nodetype);s-data=d;s-next=NULL;t-next=s;t=s;i+;return h;void sat(nodetype *h,int a)nodetype *p=h;while(p!=NULL)ap-data+;p=p-next;void main()int aN+1,i;for(i=0;iN;i+)ai=0;nodetype *head;head=create();sat(head,a);p

5、rintf(候選人:);for(i=1;i=N;i+) printf(%3d,i);printf(n得票數(shù)n);for(i=1;i=N;i+)printf(%3d,ai);printf(n);4. 實驗小結(jié)線性表是最簡單的、最常用的一種數(shù)據(jù)結(jié)構(gòu)，是實現(xiàn)其他數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)。實驗二 棧與隊列1. 實驗要求1.1 了解棧和隊列的特性，以便靈活運用。1.2 熟練掌握棧和有關(guān)隊列的各種操作和應(yīng)用。2. 實驗內(nèi)容2.1 設(shè)一個算術(shù)表達(dá)式包括圓括號，方括號和花括號三種括號，編寫一個算法判斷其中的括號是否匹配。3. 實驗代碼2.1代碼：#include#include#include#define NULL

6、0typedef struct listchar str;struct list *next;list;void push(char,list *);int pop(char.list *);void deal(char *str);main(void)char str20;printf(n請輸入一個算式:n);gets(str);deal(str);printf(正確!);getchar();return 0;void deal(char *str)list *L;L=(list *)malloc(sizeof(list);if(!L)printf(錯誤!);exit(-2);L-next=

7、NULL;while(*str)if(*str=(|*str=|*str=)push(*str,L);elseif(*str=)|*str=|*str=)if(pop(*str,L)puts(錯誤,請檢查!);puts(按回車鍵退出);getchar();exit(-2);str+;if(L-next)puts(錯誤,請檢查!);puts(按任意鍵退出);getchar();exit(-2);void push(char c,list *L)list *p;p=(list *)malloc(sizeof(list);if(!p)printf(錯誤!);exit(-2);p-str=c;p-ne

8、xt=L-next;L-next=p;#define check(s) if(L-next-str=s)p=l-next;L-next=p-next;free(p);return(0);int pop(char c,list *L)list *p;if(L-next=NULL)return 1;switch(c)case):check() break;case:check() break;case:check() break;return 1;4. 實驗小結(jié)棧和隊列是最基礎(chǔ)的一種數(shù)據(jù)結(jié)構(gòu)之一，為實現(xiàn)其他數(shù)據(jù)結(jié)構(gòu)的奠定基石。實驗三 樹1. 實驗要求1.1 掌握二叉樹，二叉樹排序數(shù)的概念和存儲方法

9、。1.2 掌握二叉樹的遍歷算法。1.3 熟練掌握編寫實現(xiàn)樹的各種運算的算法。2. 實驗內(nèi)容2.1 編寫程序，求二叉樹的結(jié)點數(shù)和葉子數(shù)。2.2 編寫遞歸算法，求二叉樹中以元素值為X的結(jié)點為根的子數(shù)的深度。2.3 編寫程序，實現(xiàn)二叉樹的先序，中序，后序遍歷，并求其深度。3. 實驗代碼2.1代碼：#include#includestruct nodechar data;struct node *lchild,*rchild;bnode;typedef struct node *blink;blink creat()blink bt;char ch;ch=getchar();if(ch= ) retu

10、rn(NULL);elsebt=(struct node *)malloc(sizeof(bnode);bt-data=ch;bt-lchild=creat();bt-rchild=creat();return bt;int n=0,n1=0;void preorder(blink bt)if (bt)n+;if(bt-lchild=NULL&bt-rchild=NULL)n1+;preorder(bt-lchild);preorder(bt-rchild);void main()blink root;root=creat();preorder(root);printf(此二叉數(shù)的接點數(shù)有:%

11、dn,n);printf(此二叉數(shù)的葉子數(shù)有:%dn,n1);2.2代碼：int get_deep(bitree T,int x)if(T-data=x)printf(%dn,get_deep(T);exit 1;elseif(T-lchild)get_deep(T-lchild,x);if(T-rchild)get_deep(T-rchild,x);int get_depth(bitree T)if(!T)return 0;elsem=get_depth(T-lchild);n=get_depth(T-rchild);return(mn?m:n)+1;2.3代碼：#include#inclu

12、destruct nodechar data;struct node *lchild,*rchild;bnode;typedef struct node *blink;blink creat()blink bt;char ch;ch=getchar();if(ch= ) return(NULL);elsebt=(struct node *)malloc(sizeof(bnode);bt-data=ch;bt-lchild=creat();bt-rchild=creat();return bt;void preorder(blink bt)if (bt)printf(%c,bt-data);pr

13、eorder(bt-lchild);preorder(bt-rchild);void inorder(blink bt)if(bt) inorder(bt-lchild);printf(%c,bt-data);inorder(bt-rchild);void postorder(blink bt)if(bt)postorder(bt-lchild);postorder(bt-rchild);printf(%c,bt-data);int max(int x,int y)if(xy)return x;else return y;int depth(blink bt)if (bt)return 1+m

14、ax(depth(bt-lchild),depth(bt-rchild);elsereturn 0;void main()blink root;root=creat();printf(n);printf(按先序排列:); preorder(root);printf(n); printf(按中序排列:);inorder(root);printf(n);printf(按后序排列:); postorder(root);printf(n);printf(此二叉數(shù)的深度是:);printf(depth=%dn,depth(root);4. 實驗小結(jié)通過本章學(xué)習(xí)實驗，對樹有了初步的認(rèn)識。樹就是一種非線性的

15、數(shù)據(jù)結(jié)構(gòu)，描述了客觀世界中事物之間的層次關(guān)系。這種結(jié)構(gòu)有著廣泛的應(yīng)用，一切具有層次關(guān)系的問題都可以用樹來表示。 實驗四 圖1. 實驗要求1.1 熟悉圖的各種存儲方法。1.2 掌握遍歷圖的遞歸和非遞歸的算法。1.3 理解圖的有關(guān)算法。2. 實驗內(nèi)容2.1 寫出將一個無向圖的鄰接矩陣轉(zhuǎn)換成鄰接表的算法。2.2 以鄰接表作存儲結(jié)構(gòu)，給出拓?fù)渑判蛩惴ǖ膶崿F(xiàn)。3. 實驗代碼2.1代碼：void mattolist(int a,adjlist b,int n) /*n為圖的結(jié)點個數(shù)*/for(i=0;in;i+)bi.firstarc=NULL; /*鄰接表置空*/for(i=0;i=0;j-)if(ai

16、j!=0)p=(arcnodetp *)malloc(sizeof(arcnodetp);/*產(chǎn)生鄰接點*/p-adjvex=j; p-nextare=bi.firstare;bi.firstarc=p;2.2代碼：typedef struct vexnodeVertexType vertex;int in;/*增加一個入度域*/ArecNodeTp * fristarc;AdjListvnum;typedef struct graphAdjList adjlist;int vexnum,arcnum;GraphTp;Top_Sort(GraphTp g) LstackTp *p;/*建立入度

17、為0的頂點棧S*/int m,i,v; initStack(S);for(i=0;ivprintf(%d,v);/*輸出v*/m+;p=g.adjlisti.fristarc;/*p=圖g中頂點v的第一個鄰接點*/while(p!=NULL)/p存在(g.adjlistp-adjvex.in)-;/*p的入度-*/if(g.adjlistp-adjvex.in=0)/*if(p的入度=0)*/Push(S,p-adjvex);/*p入S棧*/p=p-nextarc;/*p=圖g中的頂點v的下一個鄰接點*/if(mg.vexnum) return 0;/*圖含有環(huán)*/else return 1;

18、4. 實驗小結(jié)通過本章學(xué)習(xí)實驗，對圖有了具體的認(rèn)識。圖也是一種非線性的數(shù)據(jù)結(jié)構(gòu)，這種結(jié)構(gòu)有著廣泛的應(yīng)用，一切具有關(guān)系的問題都可以用圖來表示。 實驗五 查找1. 實驗要求1.1 掌握順序查找、二分法查找、分塊查找和哈希表查找的算法。1.2 能運用線性表的查找方法解決實際問題。2. 實驗內(nèi)容2.1 編寫一個算法，利用二分查找算法在一個有序表中插入一個元素X，并保持表的有序性。2.2 根據(jù)給定的數(shù)據(jù)表，先建立索引表，然后進(jìn)行分塊查找。3. 實驗代碼2.1代碼：#include #include #define MAXNUM 20int input(int *);/*輸入數(shù)據(jù)*/int search(

19、int *,int,int);/*查找插入位置*/void plug(int *,int,int);/*插入數(shù)據(jù)*/void main(void)int dataMAXNUM,m;int insert=1;m=input(data);printf(Input the insert num:);scanf(%d,data);insert=search(data,1,m);/*返回插入位置*/ plug(data,insert,m);for(insert=1;insert=m+1;insert+)/*顯示數(shù)據(jù)*/printf(%3d,*(data+insert);getch();int input

20、(int *data)int i,m; printf(nInput the max num:);scanf(%d,&m);printf(input datan);for(i=1;ihigh) return low;/*沒有找到插入數(shù)據(jù)，返回low*/elsemid=(low+high)/2;if(*(data+mid)=*data) retun mid;/*找到插入數(shù)據(jù)，返回mid*/else if(*(data+mid)*data)search(data,low,high);void plug(int *data,int insert,int m) int i;for(i=m;iinsert

21、;i-)*(data+i+1)=*(data+i);*(data+insert)=*data2.2代碼：#include #include #include #definr N 18 /*元素個數(shù)*/#definr Blocknum 3 /*分塊數(shù)*/typedef struct indextermint key;/*最大關(guān)鍵字*/int addr;/*塊的起始地址*/index; /*索引表數(shù)據(jù)類型*/index * CreateList(int data,int n)/*建索引表*/index *p;int m,j,k;m=n/BlockNum;/*分為BlockNum塊，每塊有m個元素*/p=(index *)malloc(BlockNum *sizeof(index