數(shù)據(jù)結(jié)構(gòu)實驗報告201最新整理

1、 計算機(jī)科學(xué)與技術(shù)學(xué)院 實驗報告課程名稱：數(shù)據(jù)結(jié)構(gòu) 專 業(yè)：計算機(jī)科學(xué)與技術(shù)班 級：2011 級 1 班 學(xué) 號： 201113137024 姓 名： 鎮(zhèn)方權(quán) 指導(dǎo)老師： 邱奕敏 20 實驗一1. 實驗題目設(shè)有兩個無頭結(jié)點的單鏈表，頭指針分別為ha，hb，鏈中有數(shù)據(jù)域data，鏈域next，兩鏈表的數(shù)據(jù)都按遞增序存放，現(xiàn)要求將hb表歸到ha表中，且歸并后ha仍遞增序，歸并中ha表中已有的數(shù)據(jù)若hb中也有，則hb中的數(shù)據(jù)不歸并到ha中，hb的鏈表在算法中不允許破壞。2. 程序核心代碼struct lnode int data; struct lnode *next; ; typedef stru

2、ct lnode *linklist;linklist union( linklist ha, linklist hb ) linklist head = (lnode*)malloc(sizeof(lnode); head->next = ha; lnode* pa,*pb,*ptmp; pa = ha->next; pb = hb->next; ptmp = ha; while ( pa&&pb ) if ( pa->data < pb->data ) ptmp = pa; pa = pa->next; else if ( pa-&

3、gt;data > pb->data ) lnode* lr = (lnode*)malloc(sizeof(lnode); lr->data = pb->data; lr->next = pa; ptmp->next = lr; ptmp = lr; pb = pb->next; else ptmp = pa; pa = pa->next; pb = pb->next; if ( pa ) ptmp->next = pa; else while ( pb ) lnode* lr = (lnode*)malloc(sizeof(lno

4、de); lr->data = pb->data; ptmp->next = lr; ptmp = lr; pb = pb->next; ptmp->next = null; free(head); return ha;int listinsert(linklist l,int i,int e) int j=0; linklist p=l,s; while(p&&j<i-1) p=p->next; j+; if(!p|j>i-1) return 0; s=(linklist)malloc(sizeof(struct lnode);

5、 /* 生成新結(jié)點 */ s->data=e; /* 插入l中 */ s->next=p->next; p->next=s; return 1; int main()linklist ha,hb;int n,i;int data; initlist(&ha);printf("請輸入ha中數(shù)據(jù)的個數(shù)： ");scanf("%d",&n);printf("請依次輸入ha中的數(shù)據(jù)：n");for(int i = 1;i <= n;i+)scanf("%d",&data

6、);listinsert(ha,i,data);printf("ha= ");linklist p = ha->next;while(p)printf("%d ",p->data);p = p->next;printf("n"); initlist(&hb);printf("請輸入hb中數(shù)據(jù)的個數(shù)： ");scanf("%d",&n);printf("請依次輸入hb中的數(shù)據(jù)：n");for(i = 1;i <= n;i+)scanf(&

7、quot;%d",&data);listinsert(hb,i,data);printf("hb= ");p = hb->next;while(p)printf("%d ",p->data);p = p->next;printf("n");printf("hb歸并到ha后，新的ha=");p = union(ha,hb)->next;while(p)printf("%d ",p->data);p = p->next;printf("

8、n");system("pause");return 0;3. 運(yùn)行結(jié)果 4.實驗總結(jié) 要注意歸并時若ha表中已有的數(shù)據(jù)若hb中也有，則hb中的數(shù)據(jù)不歸并到ha中，hb的鏈表在算法中不允許破壞。 實驗二1. 實驗題目 結(jié)合書上第41頁的例子（一元多項式相加），采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，將兩個線性鏈表表示的一元多項式相加，并輸出。2. 程序核心代碼typedef struct lnodeint data; /存儲系數(shù)int flag; /存儲對應(yīng)冪數(shù)struct lnode *next;lnode;/建立帶頭結(jié)點的單鏈表，n項多項式void createlist(lnode

9、 *l, int n)lnode *p;int i = 0;*l = (lnode *) malloc (sizeof(lnode);(*l)->next = null; for (i = 0; i<n; +i)p = (lnode *) malloc (sizeof(lnode); scanf("%d%d",&(p->data),&(p->flag); p->next = (*l)->next;(*l)->next = p; /插入鏈表/多項式l1與l2對應(yīng)項相加得到新的l2void polyoadd(lnode

10、*l1, lnode *l2) int ck;lnode *p,*q;p = null;q = null;q = (*l1)->next;while(q)ck = 0;p = (*l2)->next;while(p) if (q->flag = p->flag) ck = 1; break; p = p->next;if (ck = 1) /同類項合并p->data += q->data;q = q->next;else /否則，直接將非同類項插到l2最前面(*l1)->next = q->next;q->next = (*l2

11、)->next;(*l2)->next = q;q = (*l1)->next;int main()int m=0;lnode *p1,*p2;p1 = null;p2 = null;printf("設(shè)定多項式a的項數(shù)：n");scanf("%d",&m);printf("請輸入多項式a的系數(shù)及對應(yīng)位冪次：n");createlist(&p1,m);printf("a");polyoprint(&p1);printf("設(shè)定多項式b的項數(shù)：n");sca

12、nf("%d",&m);printf("請輸入多項式b的系數(shù)及對應(yīng)位冪次：n");createlist(&p2,m);printf("b");polyoprint(&p2);polyoadd(&p1,&p2);printf("相加后的");polyoprint(&p2);system("pause");return 0;3. 運(yùn)行結(jié)果4. 實驗總結(jié)合并多項式是指相同指數(shù)的項的系數(shù)相加，比較兩個鏈表的節(jié)點的指數(shù)的大小，作為指針移動的條件，同事合并的過

13、程中應(yīng)消除系數(shù)項為零的節(jié)點。 實驗三1. 實驗題目 二叉樹的動態(tài)二叉鏈表結(jié)構(gòu)中的每個結(jié)點有三個字段：data，lchild，rchild。其中指針lchild下標(biāo)datalchildrchild   1   a   2   6   2   b   3   4   3   c   0   0   4   d &

14、#160; 5   0   5   e   0   0   6   f   0   7   7   g   0   0和rchild的類型為bitree。靜態(tài)二叉鏈表是用數(shù)組作為存儲空間，每個數(shù)組元素存儲二叉樹的一個結(jié)點，也有三個字段：data，lchild，rchild。所不同的是，lchild和rdhild 為integer型，分別用

15、于存儲左右孩子的下標(biāo)，如果沒有左右孩子，則相應(yīng)的值為0。例如，二叉樹的靜態(tài)二叉鏈表如上圖所示。編寫算法由二叉樹的動態(tài)二叉鏈表構(gòu)造出相應(yīng)的靜態(tài)二叉鏈表a1.n，并寫出其調(diào)用形式和有關(guān)的類型描述。其中n為一個確定的整數(shù)。2. 程序核心代碼 typedef struct bitnodechar data;struct bitnode *lchild,*rchild;bitnode, *bitree;typedef struct node /靜態(tài)鏈表結(jié)點結(jié)構(gòu) char data; /結(jié)點數(shù)據(jù) int row,lchild,rchild ; /下標(biāo)，左右孩子node;node *st; /st容量足夠大

16、static int length=0;static int num=0;void createbitree(bitree &t) char ch; scanf("%c",&ch); if (ch='#') t = null; else if (!(t = (bitnode *)malloc(sizeof(bitnode) printf("error"); t->data = ch; / 生成根結(jié)點 createbitree(t->lchild); / 構(gòu)造左子樹 createbitree(t->rchi

17、ld); / 構(gòu)造右子樹 void preorder(bitree bt)/ 先序遍歷二叉樹，填寫靜態(tài)鏈表的“下標(biāo)”和data域if (bt) st+num.data=bt->data;stnum.row=num;preorder(bt->lchild);preorder(bt->rchild);int locate(char x) /在靜態(tài)鏈表中查二叉樹結(jié)點的下標(biāo) int i; for (i=1;i<=num;i+)if (sti.data=x)return (i); bitree levelorderlocatep(bitree root,char x)int fr

18、ont,rear;bitree queuemaxsize,p;p = root;front = rear =0;if(p)queuerear+ = p;while(front < rear)p = queuefront+;if(p->data = x)return p;if(p->lchild)queuerear+ = p->lchild;if(p->rchild)queuerear+ = p->rchild;void dynatost (bitree t) int i;bitree p;preorder(t);for(i = 1;i <= num;i

19、+)p = levelorderlocatep(t,sti.data);if(p->lchild)sti.lchild = locate(p->lchild->data);elsesti.lchild=0;/無左孩子，其lchild域填0if(p->rchild)sti.rchild = locate(p->rchild->data);elsesti.rchild=0;/無右孩子，其rchild域填0int main()bitree t;printf("請輸入二叉樹各結(jié)點的值:n");createbitree(t);nodenum(t);

20、st = (node*)malloc(sizeof(struct node)*length);dynatost(t);show(st);return 0;3. 運(yùn)行結(jié)果4. 實驗體會 二叉樹的建立是按照先序遍歷的方式遞歸的建立的，因此在輸入二叉樹的節(jié)點中的值時，要注意#字符的個數(shù)。 實驗四1. 實驗題目 設(shè)無向圖g有n個點e條邊，編寫算法建立g的鄰接表，并按照深度優(yōu)先搜索輸出頂點，要求該算法時間復(fù)雜性為o（n+e），且除鄰接表本身所占空間之外只用o（1）輔助空間。2. 程序核心代碼struct edgenode/表結(jié)點int endver;edgenode* edgenext;struct v

21、exnode/頭結(jié)點char vertex;edgenode * edgelink;struct graph/無向圖vexnode adjlistsmax_ver_num;int vexnum, arcnum;void creatadjlist(graph* g)int i,j,k;edgenode * p1;edgenode * p2;cout<<"請輸入無向圖的頂點數(shù)和邊數(shù):"<<endl;cin>>g->vexnum>>g->arcnum;cout<<endl;cout<<"

22、開始輸入頂點表:"<<endl;for (i=1;i<=g->vexnum;i+)cin>>g->adjlistsi.vertex;g->adjlistsi.edgelink=null;cout<<endl;cout<<"開始輸入邊表信息:"<<endl; cout<<endl;for (k=1;k<=g->arcnum;k+)cout<<"請輸入邊<vi,vj>對應(yīng)的頂點序號:"cin>>i>&

23、gt;j; cout<<endl;p1=new edgenode;p1->endver=j;p1->edgenext=g->adjlistsi.edgelink; /將結(jié)點始終插到表結(jié)點后g->adjlistsi.edgelink=p1;p2=new edgenode;p2->endver=i;p2->edgenext=g->adjlistsj.edgelink;g->adjlistsj.edgelink=p2;void dfs(graph *g, int i, int visited)cout<<g->adjlis

24、tsi.vertex<<" "visitedi=1;edgenode *p=new edgenode;p=g->adjlistsi.edgelink;if(g->adjlistsi.edgelink && !visitedp->endver)dfs(g,p->endver,visited);void dfstraversal(graph *g, char c)cout<<"該圖的深度優(yōu)先遍歷結(jié)果為:"<<endl;int visitedmax_ver_num;for(int i=

25、1; i<=g->vexnum; i+)visitedi=0;for (int i=1;i<=g->vexnum;i+)if (g->adjlistsi.vertex=c) dfs(g,i,visited);break;for(int i=1;i<=g->vexnum;i+)if(visitedi=0)dfs(g,i,visited);cout<<endl;/主程序int main()graph * g=new graph;creatadjlist(g);printgaph(g);char vi;cout<<"請輸入開

26、始遍歷的頂點:"<<endl;cin>>vi;dfstraversal(g,vi); cout<<endl; return 0;3. 運(yùn)行結(jié)果4. 實驗體會在輸入邊表關(guān)系時，要注意因為是無向圖，所以有兩次建立邊表的過程，不需要重復(fù)輸入。 實驗五1. 實驗題目 二叉排序樹采用二叉鏈表存儲。寫一個算法，刪除結(jié)點值是x的結(jié)點。要求刪除該結(jié)點后,此樹仍然是一棵二叉排序樹，并且高度沒有增長（注：可不考慮被刪除的結(jié)點是根的情況）。2. 程序核心代碼typedef struct bitnodeelemtype data;struct bitnode *lchil

27、d,*rchild;bitnode,*bitree;static bitree head;/建二叉排序樹bitree createbst(bitree head,int number)bitree p;p=(bitree)malloc(sizeof(bitnode); p->data=number;p->lchild =p->rchild=null;if(head=null) return p;else if(p->data < head->data)head->lchild=createbst(head->lchild,number); els

28、ehead->rchild=createbst(head->rchild,number); return head;/求p的雙親bitree searchparent(bitree head,bitree p) if(head->lchild=p|head->rchild=p|head=p|head=null) return head; else if(p->data < head->data) return searchparent(head->lchild ,p); else return searchparent(head->rchi

29、ld ,p); /刪除二叉排序樹中結(jié)點pbool delete(bitree p)bitree q,s;q=(bitree)malloc(sizeof(bitnode);s=(bitree)malloc(sizeof(bitnode);if(!p->rchild&&!p->lchild) /刪除的節(jié)點是葉子節(jié)點q=searchparent(head,p);if(q->lchild=p) q->lchild=null;else q->rchild=null;else if(!p->rchild) /左子樹不為空，右子樹為空searchparent(head,p)->lchild = p->lchild;free(p);else if(!p->lchild) /右子樹不為空，左子樹為空 searchparent(head,p)->rchild = p->rchild;free(p);else /左右子樹都不為空q=p;s=p->lchild;while(s-