太原理工大學(xué)數(shù)據(jù)結(jié)構(gòu)實驗報告2016

1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)據(jù)結(jié)構(gòu)實驗報告專業(yè)：軟件工程班級：軟件姓名： 2016年12月太原理工大學(xué)學(xué)生實驗報告學(xué)院名稱軟件學(xué)院專業(yè)班級軟件學(xué)號2實驗成績學(xué)生姓名實驗題目線性表實驗日期一目的與要求 本次實習(xí)的主要目的是為了使學(xué)生熟練掌握線性表的基本操作在順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)上的實現(xiàn)，提高分析和解決問題的能力。要求仔細(xì)閱讀并理解下列例題，上機(jī)通過，并觀察其結(jié)果，然后獨(dú)立完成后面的實習(xí)題。二例題 問題描述 用鏈表形式存儲一個字符串，插入、刪除某個字符，最后按正序、逆序兩種方式輸出字符串。輸入初始字符串，插入位置，插入字符，刪除字符。輸出已建立鏈表（字符串），插入字符后鏈表，刪除字符后鏈表，

2、逆轉(zhuǎn)后鏈表。存儲結(jié)構(gòu)采用鏈?zhǔn)酱鎯Y(jié)構(gòu)算法的基本思想建立鏈表：當(dāng)讀入字符不是結(jié)束符時，給結(jié)點(diǎn)分配存儲空間，寫數(shù)據(jù)域，將新結(jié)點(diǎn)插到表尾；插入字符：根據(jù)讀入的字符在鏈表中找插入位置，將新結(jié)點(diǎn)插入到該位置之前；刪除字符：根據(jù)讀入的刪除字符在鏈表中找到被刪結(jié)點(diǎn)后，將其從鏈表中刪除；鏈表逆轉(zhuǎn)：從鏈表的第一個結(jié)點(diǎn)開始對所有結(jié)點(diǎn)處理，將每個結(jié)點(diǎn)的前驅(qū)變?yōu)樗暮罄^；打印鏈表：從鏈表的第一個結(jié)點(diǎn)開始，依次打印各個結(jié)點(diǎn)的數(shù)據(jù)域。參考源程序#define NULL 0typedef struct node    char a;    struct node

3、*link;node,*nodelink;void readlink(nodelink head)    nodelink p,q;    char c;    p=head;    printf("Input a linktable(a string):");    scanf("%c",&c);    if (c='n') printf("

4、This string is empty。");    while(c!='n')       q=(nodelink)malloc(sizeof(node);       q->a=c;       p->link=q;       p=q;    

5、   scanf("%c",&c);          p->link=NULL;void writelink(nodelink head)    nodelink q;    if (head->link=NULL) printf(" This link is empty。n");    for(q=head->link;q;q=q->link

6、)       printf("%c",q->a);    printf("n");    int  insert(nodelink head,char k1,char k2)    nodelink p,q;    p=head->link;    while(p->a!=k1&&p) 

7、60;     p=p->link;    if(p)       q=(nodelink)malloc(sizeof(node);       q->a=k2;       q->link=p->link;       p->link=q; 

8、60;     return 1;          else         printf("There is no %cn",k1);       return 0;      int  delete(nodelink head,char k)  

9、0; nodelink p,q;    q=head;    p=head->link;    while(p->a)!=k)&&p)       q=q->link;       p=p->link;          if(p)    

10、   q->link=p->link;       return 1;           else       printf("There is no %cn",k);       return 0;      void opside(

11、nodelink head)    nodelink p,q;    p=head->link;    while(p->link)       q=p->link;       p->link=q->link;       q->link=head->link;  

12、     head->link=q;      main()    char k1,k2,k3;    nodelink head;    head=(nodelink)malloc(sizeof(node);    head->link=NULL;    readlink(head);    if (head->lin

13、k!=NULL)    printf("Build link is :");    writelink(head);     if (head->link!=NULL)    printf("Please input a char you want to insert after:");    k1=getch();    printf("%cn",k

14、1);    printf("Please input a char you want to insert:");    k2=getch();    printf("%cn",k2);    if (insert(head,k1,k2)     printf("After %c insert %c,link is:",k1,k2);    writelin

15、k(head);        printf("Please input a char you want to delete:");    k3=getch();    printf("%cn",k3);    if (delete(head,k3)    printf("after delete %c,link is:",k3);  &

16、#160;  writelink(head);        if (head->link!=NULL)    printf("Opsite result is :");    opside(head);    writelink(head);    free(head);        運(yùn)行情況Input a linkt

17、able(a string):lopuiBuild link is :lopuiPlease input a char you want to insert after:pPlease input a char you want to insert:yAfter p insert y,link is:lopyuiPlease input a char you want to delete:pafter delete p,link is:loyuiOpsite result is :iuyol三實習(xí)題用單鏈表ha 存儲多項式A（x ）=a0+a1x1+a2x2+anxn(其中aI為非零系數(shù))，用

18、單鏈表hb 存儲多項式B（x ）=b0+b1x1+b2x2+bmxm(其中bj為非零系數(shù))，要求計算C（x ）= A（x ）+B（x ），結(jié)果存到單鏈表hc中。試寫出程序。 實驗程序：#include"stdio.h"#include <malloc.h>#include"stdafx.h"#include<malloc.h>static int n;static int m;static int max;struct Polynomialfloat data;struct Polynomial* next;struct Poly

19、nomial* Creat_H(int k)struct Polynomial* L;struct Polynomial* p;p = (struct Polynomial*)malloc(sizeof(struct Polynomial);L = p;float temp;int i;printf("請依次輸入系數(shù)(中間用空格隔開)：n");for (i = 0; i <= k; i+)scanf_s("%f", &temp);p->data = temp;if (i = k)p->next = NULL;break;p-&g

20、t;next = (struct Polynomial*)malloc(sizeof(struct Polynomial);p = p->next;return L;struct Polynomial* Calculate(struct Polynomial* Pa, struct Polynomial* Pb)struct Polynomial* Pc;struct Polynomial* L;int i;max = n >= m ? n : m;Pc = (struct Polynomial*)malloc(sizeof(struct Polynomial);L = Pc;fo

21、r (i = 0; i <= max; i+)if (i = max)Pc->next = NULL;break;Pc->next = (struct Polynomial*)malloc(sizeof(struct Polynomial);Pc = Pc->next;Pc = L;while (Pa != NULL&&Pb != NULL)Pc->data = Pa->data + Pb->data;Pc = Pc->next;Pa = Pa->next;Pb = Pb->next;if (Pa = NULL)whi

22、le (Pb != NULL)Pc->data = Pb->data;Pc = Pc->next;Pb = Pb->next;else if (Pb = NULL)while (Pa != NULL)Pc->data = Pa->data;Pc = Pc->next;Pa = Pa->next;return L;int main()int i;struct Polynomial *Ha, *Hb, *Hc;printf("請輸入多項式a的最高次系n:n");scanf_s("%d", &n);Ha

23、= Creat_H(n);printf("請輸入多項式b的最高次系m:n");scanf_s("%d", &m);Hb = Creat_H(m);Hc = Calculate(Ha, Hb);printf("系數(shù): 次數(shù):n");for (i = 0; i <= max; i+)printf("%f%-4dn", Hc->data, i);if (i = max)break;Hc = Hc->next;return 0;實驗室名稱致遠(yuǎn)樓指導(dǎo)教師姓名 張月琴太原理工大學(xué)學(xué)生實驗報告

24、學(xué)院名稱軟件學(xué)院專業(yè)班級軟件1學(xué)號實驗成績學(xué)生姓名實驗題目樹實驗日期. 一目的與要求熟悉樹的各種表示方法和各種遍歷方式，掌握有關(guān)算法的實現(xiàn)，了解樹在計算機(jī)科學(xué)及其它工程技術(shù)中的應(yīng)用。二例題問題描述任意給定一棵二叉樹。試設(shè)計一個程序，在計算機(jī)中構(gòu)造該二叉樹，并對它進(jìn)行遍歷。輸入一棵二叉樹的結(jié)點(diǎn)若無子樹，則可將其子樹看作“.”，輸入時，按照前序序列的順序輸入該結(jié)點(diǎn)的內(nèi)容。對下圖，其輸入序列為ABD.EH.CF.I.G.。 A B C D E F G H I 輸出若為空二叉樹，則輸出：THIS IS A EMPTY BINARY TREE。若二叉樹不空，按后序序列輸出，對上例，輸出結(jié)果為：DHEBI

25、FGCA。存儲結(jié)構(gòu)采用二叉鏈表存儲。算法的基本思想采用遞歸方法建立和遍歷二叉樹。首先建立二叉樹的根結(jié)點(diǎn)，然后建立其左右子樹，直到空子樹為止。后序遍歷二叉樹時，先遍歷左子樹，后遍歷右子樹，最后訪問根結(jié)點(diǎn)。參考源程序#include<stdio.h>#include<alloc.h> struct nodechar info;struct node *llink,*rlink;typedef struct node NODE;NODE *creat()char x;NODE *p; scanf("%c",&x);printf("%c&q

26、uot;,x);if(x!='.')p=(NODE *)malloc(sizeof(NODE);p->info=x;p->llink=creat();p->rlink=creat(); elsep=NULL;return p;void run(NODE *t)if(t)run(t->llink);run(t->rlink);printf("%c",t->info); main()NODE *T;printf("PLease input a tree:n");T=creat();printf("

27、n");if(!T)printf("This is a empty binary tree.");else printf("The result of post travese is:n ");run(T); printf("n");三實習(xí)題編寫遞歸算法，計算二叉樹中葉子結(jié)點(diǎn)的數(shù)目。#include<stdio.h>struct BiTree char data; struct BiTree *lchild; struct BiTree *rchild; struct BiTree* CreatBiTree()

28、char x; struct BiTree* p; scanf("%c",&x); if(x!='.') p=(struct BiTree*)malloc(sizeof(struct BiTree); p->data=x; p->lchild=CreatBiTree(); p->rchild=CreatBiTree(); else p=NULL; return p;int LeafNum(struct BiTree *T) if(!T) return 0; else if(!T->lchild&&!T->

29、rchild) return 1; else return LeafNum(T->lchild)+LeafNum(T->rchild); int main() int num; struct BiTree* T; printf("請按先序序列輸入二叉樹n"); T=CreatBiTree(); while(T=NULL) printf("empoty,again:n"); T=CreatBiTree(); num=LeafNum(T); printf("n二叉樹葉子結(jié)點(diǎn)為:%dn",num); system("p

30、ause"); return 0; 實驗室名稱指導(dǎo)教師姓名太原理工大學(xué)學(xué)生實驗報告學(xué)院名稱軟件學(xué)院專業(yè)班級軟件學(xué)號實驗成績學(xué)生姓名實驗題目圖實驗日期一目的與要求熟悉圖的存儲結(jié)構(gòu)，掌握有關(guān)算法的實現(xiàn)，了解圖在計算機(jī)科學(xué)及其他工程技術(shù)中的應(yīng)用。二例題問題描述給定一個圖，設(shè)計一個程序，找出一條從某一頂點(diǎn)A到另一頂點(diǎn)B邊數(shù)最少的一條路徑。輸入圖的頂點(diǎn)個數(shù)N，圖中頂點(diǎn)之間的關(guān)系及要找的路徑的起點(diǎn)A和終點(diǎn)B。輸出若A到B無路徑，則輸出“There is no path”，否則輸出A到B路徑上各頂點(diǎn)。存儲結(jié)構(gòu)圖采用鄰接矩陣的方式存儲。 算法的基本思想采用廣度優(yōu)先搜索的方法，從頂點(diǎn)A開始，依次訪問與

31、A鄰接的頂點(diǎn)VA1,VA2,.,VAK, 訪問遍之后,若沒有訪問B，則繼續(xù)訪問與VA1鄰接的頂點(diǎn)VA11,VA12,.,VA1M，再訪問與VA2鄰接頂點(diǎn).，如此下去，直至找到B，最先到達(dá)B點(diǎn)的路徑，一定是邊數(shù)最少的路徑。實現(xiàn)時采用隊列記錄被訪問過的頂點(diǎn)。每次訪問與隊頭頂點(diǎn)相鄰接的頂點(diǎn)，然后將隊頭頂點(diǎn)從隊列中刪去。若隊空，則說明到不存在通路。在訪問頂點(diǎn)過程中，每次把當(dāng)前頂點(diǎn)的序號作為與其鄰接的未訪問的頂點(diǎn)的前驅(qū)頂點(diǎn)記錄下來，以便輸出時回溯。參考源程序#include<stdio.h>int number;typedef structint q20;int f,r; queue;int

32、 nodelist2020;queue Q;int z20;int a,b,n,i,j,x,y;int finished;void enq(queue *Q,int x)Q->qQ->r=x;if(Q->r=19)Q->r=0;elseQ->r+;if(Q->r=Q->f)printf("Overflow!n");front(queue *Q)if(Q->r=Q->f)printf("Underflow!n");elsereturn(Q->qQ->f);void deq(queue *Q)

33、if(Q->r=Q->f)printf("Underflow!n");elseif(Q->f=19)Q->f=0;elseQ->f+; int qempty(queue Q)if(Q.f=Q.r)return 1;elsereturn 0;void readgraph()printf("nPlease input n:");scanf("%d",&n);printf("Please input nodelistij:n");for(i=1;i<=n;i+)for(j=1;

34、j<=n;j+)scanf("%d",&nodelistij);printf("n");printf("List-link is bulitn");for(i=1;i<=n;i+)for(j=1;j<=n;j+)printf("%3d",nodelistij);printf("n"); void shortest(int a,int b)if(a=b)nodelistaa=2;elseenq(&Q,a);nodelistaa=2;finished=0;while

35、(!qempty(Q)&&!finished)a=front(&Q);deq(&Q);j=1;while(j<=n)&&!finished)if(nodelistaj=1)&&(nodelistjj!=2)enq(&Q,j);nodelistjj=2;zj=a;if(j=b)/*&&(nodelistaj=1)*/finished=1;if(!finished)j+; if (!finished) printf("There is no path."); void writepat

36、h(int a,int b)i=b;while(i!=a)printf("%d <- ",i);i=zi; printf("%d",a);main()readgraph();printf("Please input a:");scanf("%d",&a);printf("Please input b:");scanf("%d",&b);Q.f=0; Q.r=0;shortest(a,b);if (finished)writepath(a,b);三實習(xí)題采

37、用鄰接表存儲結(jié)構(gòu)，編寫一個求無向圖的連通分量個數(shù)的算法。#include<stdio.h>#include<malloc.h>#include<stdlib.h>int n;struct VNode int position; struct VNode* next;struct ArcNode int mark; struct VNode* first;void DFS(struct ArcNode* v,struct ArcNode* w) struct VNode* L; w->mark=1; L=w->first; while(L!=NUL

38、L) if(v+(L->position)->mark=0) DFS(v,(v+L->position); L=L->next; int main() int i,j,k; int num=0; struct ArcNode* p; struct VNode* temp; struct VNode* flag; printf("該無向圖有多少個頂點(diǎn)：n"); scanf("%d",&n); while(n<1) printf("你輸入的值不合理，請重新輸入：n"); scanf("%d&

39、quot;,&n); p=(struct ArcNode*)malloc(n*sizeof(struct ArcNode); for(i=0;i<n;i+) printf("請輸入以V%d為弧尾的所有弧，并以-1結(jié)束輸入n",i+1); scanf("%d",&k); if(k=-1) pi.mark=0; pi.first=NULL; else temp=(struct VNode*)malloc(sizeof(struct VNode); temp->position=k; temp->next=NULL; pi.f

40、irst=temp; pi.mark=0; flag=temp; scanf("%d",&k); while(k!=-1) temp=(struct VNode*)malloc(sizeof(struct VNode); temp->position=k; temp->next=NULL; flag->next=temp; flag=temp; scanf("%d",&k); i=0; while(pi.mark=0) DFS(p,(p+i); num+; i=0; while(pi.mark!=0&&i

41、<n) i+; printf("此圖的連通分量個數(shù)為：%dn",num); return 0; 實驗室名稱指導(dǎo)教師姓名太原理工大學(xué)學(xué)生實驗報告學(xué)院名稱軟件學(xué)院專業(yè)班級軟學(xué)號20實驗成績學(xué)生姓名實驗題目查找實驗日期一目的與要求通過本次實驗，掌握查找表上的有關(guān)查找方法，并分析時間復(fù)雜度。二例題問題描述將折半查找算法寫成完整的程序，并上機(jī)通過。輸入有序表（12,23,28,35,37,39,50,60,78,90）及待查找記錄23,58。輸出輸入23，表中存在待查找記錄，則顯示該記錄在表中位置2，輸入58顯示該記錄不存在。存儲結(jié)構(gòu)有序表采用順序方式存儲。算法的基本思想首先用

42、待查找記錄與查找區(qū)間中間位置記錄比較，若相等則查找成功，返回該記錄在表中的位置數(shù)，若小于中間位置記錄，則修改區(qū)間上界為中間位置減 1，若大于中間位置記錄，則修改區(qū)間下界為中間位置加 1，在新的區(qū)間內(nèi)繼續(xù)查找。當(dāng)查找區(qū)間下界大于上界，則該記錄不存在。參考源程序#include"stdio.h"typedef structint a30;int length;sqtable;sqtable st;int b=0;void createst(int k)int i;printf("Please input data:"); st.a0=-100;for (i=

43、1;(!b&&(i<=k);i+)scanf("%d",&(st.ai);if (st.ai<st.ai-1) printf("Input data error.n"); b=1; if (!b) st.length=k; printf("The table is builted.n"); void stfind(sqtable st,int y) int f,l,h,m; l=1;h=st.length; f=1; while (l<=h)&&f) m=(l+h)/2; if

44、 (y=st.am) f=0; else if (y<st.am) h=m-1; else l=m+1; if (!f) printf("Find %d in position %d.n",y,m); else printf("Not find %d.n",y); main()int n,x;printf("nPlease input n:");scanf("%d",&n);createst(n);if (b=0) printf("Please input you want find val

45、ue:");scanf("%d",&x);stfind(st,x);三實習(xí)題試將折半查找的算法改寫成遞歸算法#include"stdafx.h"#include<stdio.h>#include<malloc.h>#include<stdlib.h>int Search(int* a, int k, int low, int hight)int mid;if (low>hight)return 0;mid = (low + hight) / 2;if (amid = k)return (mid

46、+ 1);else if (amid>k)return Search(a, k, low, mid - 1);elsereturn Search(a, k, mid + 1, hight);int main()int *p;int i, n, key, position;printf("輸入數(shù)據(jù)數(shù)量：n");scanf("%d", &n);p = (int*)malloc(n*sizeof(int);printf("請按非遞減序列輸入你的數(shù)據(jù)（整型），并用空格隔開：n");scanf("%d", &a

47、mp;p0);for (i = 1; i<n; i+)scanf("%d", &pi);while (pi<pi - 1)printf("你輸入的數(shù)據(jù)不合理，請重新輸入：n");scanf("%d", &pi);printf("請輸入你要查找的數(shù)據(jù)：n");scanf("%d", &key);position = Search(p, key, 0, n - 1);if (position = 0)printf("沒有找到你要查找的數(shù)據(jù)！n"

48、);elseprintf("你所查找的數(shù)據(jù)位于原有序表的第%d個位置！n", position);return 0;實驗室名稱指導(dǎo)教師姓名太原理工大學(xué)學(xué)生實驗報告學(xué)院名稱軟件學(xué)院專業(yè)班級軟件學(xué)號20實驗成績學(xué)生姓名實驗題目內(nèi)排序?qū)嶒炄掌谝荒康呐c要求通過本次實驗，掌握線性表的排序方法，并分析時間復(fù)雜度。二例題問題描述將快速排序算法寫成完整的程序上機(jī)通過，并統(tǒng)計遞歸深度。輸入待排序記錄個數(shù)n，各待排序記錄值。輸出n個記錄由小到大排列的結(jié)果。存儲結(jié)構(gòu)待排序記錄順序存儲。算法的基本思想快速排序算法每次任取一個記錄的關(guān)鍵字為標(biāo)準(zhǔn)，將其余記錄分為兩組，將所有關(guān)鍵字小于或等于標(biāo)準(zhǔn)的記錄都

49、放在它的位置之前，將所有關(guān)鍵字大于標(biāo)準(zhǔn)的記錄都放在它的位置之后。對這兩組再進(jìn)行快速排序，直到完全有序。每遞歸1次，遞歸深度加1。參考源程序#include<stdio.h>typedef int node;node afile20;node x;int d,dl,n;int l,r,i,j;void q(int l,int r)int p;d+;if(dl<d)dl=d;printf("dl=%d ",dl);printf("d=%dn",d);if(l<r)i=l; j=r;x=afilei;while(i!=j)while(afilej>x)&&(j>i)j-;if(i<j)afilei+=afilej;while(afilei<x)&&(j>i)i+;if(i<j)afilej-=afilei; afilei=x;for(p=1;p<=n;p+)printf("%