數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告201最新整理

1、 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 實(shí)驗(yàn)報(bào)告課程名稱：數(shù)據(jù)結(jié)構(gòu) 專(zhuān) 業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)班 級(jí)：2011 級(jí) 1 班 學(xué) 號(hào)： 201113137024 姓 名： 鎮(zhèn)方權(quán) 指導(dǎo)老師： 邱奕敏 20 實(shí)驗(yàn)一1. 實(shí)驗(yàn)題目設(shè)有兩個(gè)無(wú)頭結(jié)點(diǎn)的單鏈表，頭指針?lè)謩e為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é)點(diǎn) */ 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("請(qǐng)輸入ha中數(shù)據(jù)的個(gè)數(shù)： ");scanf("%d",&n);printf("請(qǐng)依次輸入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("請(qǐng)輸入hb中數(shù)據(jù)的個(gè)數(shù)： ");scanf("%d",&n);printf("請(qǐng)依次輸入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.實(shí)驗(yàn)總結(jié) 要注意歸并時(shí)若ha表中已有的數(shù)據(jù)若hb中也有，則hb中的數(shù)據(jù)不歸并到ha中，hb的鏈表在算法中不允許破壞。 實(shí)驗(yàn)二1. 實(shí)驗(yàn)題目 結(jié)合書(shū)上第41頁(yè)的例子（一元多項(xiàng)式相加），采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，將兩個(gè)線性鏈表表示的一元多項(xiàng)式相加，并輸出。2. 程序核心代碼typedef struct lnodeint data; /存儲(chǔ)系數(shù)int flag; /存儲(chǔ)對(duì)應(yīng)冪數(shù)struct lnode *next;lnode;/建立帶頭結(jié)點(diǎn)的單鏈表，n項(xiàng)多項(xiàng)式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; /插入鏈表/多項(xiàng)式l1與l2對(duì)應(yīng)項(xià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) /同類(lèi)項(xiàng)合并p->data += q->data;q = q->next;else /否則，直接將非同類(lèi)項(xiàng)插到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è)定多項(xiàng)式a的項(xiàng)數(shù)：n");scanf("%d",&m);printf("請(qǐng)輸入多項(xiàng)式a的系數(shù)及對(duì)應(yīng)位冪次：n");createlist(&p1,m);printf("a");polyoprint(&p1);printf("設(shè)定多項(xiàng)式b的項(xiàng)數(shù)：n");sca

12、nf("%d",&m);printf("請(qǐng)輸入多項(xiàng)式b的系數(shù)及對(duì)應(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. 實(shí)驗(yàn)總結(jié)合并多項(xiàng)式是指相同指數(shù)的項(xiàng)的系數(shù)相加，比較兩個(gè)鏈表的節(jié)點(diǎn)的指數(shù)的大小，作為指針移動(dòng)的條件，同事合并的過(guò)

13、程中應(yīng)消除系數(shù)項(xiàng)為零的節(jié)點(diǎn)。 實(shí)驗(yàn)三1. 實(shí)驗(yàn)題目 二叉樹(shù)的動(dòng)態(tài)二叉鏈表結(jié)構(gòu)中的每個(gè)結(jié)點(diǎn)有三個(gè)字段：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的類(lèi)型為bitree。靜態(tài)二叉鏈表是用數(shù)組作為存儲(chǔ)空間，每個(gè)數(shù)組元素存儲(chǔ)二叉樹(shù)的一個(gè)結(jié)點(diǎn)，也有三個(gè)字段：data，lchild，rchild。所不同的是，lchild和rdhild 為integer型，分別用

15、于存儲(chǔ)左右孩子的下標(biāo)，如果沒(méi)有左右孩子，則相應(yīng)的值為0。例如，二叉樹(shù)的靜態(tài)二叉鏈表如上圖所示。編寫(xiě)算法由二叉樹(shù)的動(dòng)態(tài)二叉鏈表構(gòu)造出相應(yīng)的靜態(tài)二叉鏈表a1.n，并寫(xiě)出其調(diào)用形式和有關(guān)的類(lèi)型描述。其中n為一個(gè)確定的整數(shù)。2. 程序核心代碼 typedef struct bitnodechar data;struct bitnode *lchild,*rchild;bitnode, *bitree;typedef struct node /靜態(tài)鏈表結(jié)點(diǎn)結(jié)構(gòu) char data; /結(jié)點(diǎn)數(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é)點(diǎn) createbitree(t->lchild); / 構(gòu)造左子樹(shù) createbitree(t->rchi

17、ld); / 構(gòu)造右子樹(shù) void preorder(bitree bt)/ 先序遍歷二叉樹(shù)，填寫(xiě)靜態(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)鏈表中查二叉樹(shù)結(jié)點(diǎn)的下標(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;/無(wú)左孩子，其lchild域填0if(p->rchild)sti.rchild = locate(p->rchild->data);elsesti.rchild=0;/無(wú)右孩子，其rchild域填0int main()bitree t;printf("請(qǐng)輸入二叉樹(shù)各結(jié)點(diǎn)的值:n");createbitree(t);nodenum(t);

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

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

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

23、gt;j; cout<<endl;p1=new edgenode;p1->endver=j;p1->edgenext=g->adjlistsi.edgelink; /將結(jié)點(diǎn)始終插到表結(jié)點(diǎn)后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<<"請(qǐng)輸入開(kāi)

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

27、d,*rchild;bitnode,*bitree;static bitree head;/建二叉排序樹(shù)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); /刪除二叉排序樹(shù)中結(jié)點(diǎn)pbool delete(bitree p)bitree q,s;q=(bitree)malloc(sizeof(bitnode);s=(bitree)malloc(sizeof(bitnode);if(!p->rchild&&!p->lchild) /刪除的節(jié)點(diǎn)是葉子節(jié)點(diǎn)q=searchparent(head,p);if(q->lchild=p) q->lchild=null;else q->rchild=null;else if(!p->rchild) /左子樹(shù)不為空，右子樹(shù)為空searchparent(head,p)->lchild = p->lchild;free(p);else if(!p->lchild) /右子樹(shù)不為空，左子樹(shù)為空 searchparent(head,p)->rchild = p->rchild;free(p);else /左右子樹(shù)都不為空q=p;s=p->lchild;while(s-