數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)實(shí)驗(yàn)一

1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)一學(xué)院：班級：學(xué)號：姓名：1、 實(shí)驗(yàn)?zāi)康牡谝活} 利用單向環(huán)表實(shí)現(xiàn)約瑟夫環(huán)。第二題 歸并順序表。二、實(shí)驗(yàn)內(nèi)容 第一題 采用單向環(huán)表實(shí)現(xiàn)約瑟夫環(huán)。 請按以下要求編程實(shí)現(xiàn)： 從鍵盤輸入整數(shù)m，通過create函數(shù)生成一個(gè)具有m個(gè)結(jié)點(diǎn)的單向環(huán)表。環(huán)表中的結(jié)點(diǎn)編號依次為1，2，m。 從鍵盤輸入整數(shù)s（1<=s<=m）和n，從環(huán)表的第s個(gè)結(jié)點(diǎn)開始計(jì)數(shù)為1，當(dāng)計(jì)數(shù)到第n個(gè)結(jié)點(diǎn)時(shí)，輸出該第n結(jié)點(diǎn)對應(yīng)的編號，將該結(jié)點(diǎn)從環(huán)表中消除，從輸出結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)開始重新計(jì)數(shù)到n，這樣，不斷進(jìn)行計(jì)數(shù)，不斷進(jìn)行輸出，直到輸出了這個(gè)環(huán)表的全部結(jié)點(diǎn)為止。 例如，

2、m=10，s=3，n=4。則輸出序列為：6，10，4，9，5，2，1，3，8，7。 第二題 選作：歸并順序表。 請按以下要求編程實(shí)現(xiàn)： 從鍵盤輸入兩個(gè)升序排列的整數(shù)序列l(wèi)inka和linkb，每個(gè)序列以輸入0為結(jié)束標(biāo)記。 將鏈表linka和linkb歸并為linkc，linkc仍然為升序排列。歸并完成后，linka和linkb為空表。輸出linkc。 對linkc進(jìn)行處理，保持升序不變，刪除其中重復(fù)的整數(shù)，對重復(fù)的整數(shù)只保留一個(gè)，輸出刪除重復(fù)整數(shù)后的鏈表。 例如：linka輸入為：10 20 30 40 50 0 linkb輸入為：15 20 25 30 35 40 45 50 0 歸并后的l

3、inkc為：10 15 20 20 25 30 30 35 40 40 45 50 50 刪除重復(fù)后的linkc為：10 15 20 25 30 35 40 45 50 3、 程序設(shè)計(jì)1、 概要設(shè)計(jì)第一題 為了實(shí)現(xiàn)程序功能，應(yīng)當(dāng)建立單向環(huán)表來寄存信息及結(jié)點(diǎn)，通過查找結(jié)點(diǎn)來完成相應(yīng)的操作。順序是：輸入數(shù)據(jù)-建立頭結(jié)點(diǎn)-建立環(huán)表-循環(huán)輸出和刪除結(jié)點(diǎn)。 程序流程開始輸入數(shù)據(jù)（m，s，n）創(chuàng)建環(huán)表計(jì)算處理 輸出環(huán)表結(jié)束 第二題 為了實(shí)現(xiàn)程序功能，應(yīng)當(dāng)建立單向鏈表來寄存信息及結(jié)點(diǎn)，順序是：輸入數(shù)據(jù)-建立頭結(jié)點(diǎn)-建立鏈表-合并鏈表-輸出鏈表-刪除重復(fù)數(shù)據(jù)-輸出鏈表。程序流程開始輸入鏈表a和鏈表b創(chuàng)建鏈表合

4、并鏈表 輸出鏈表c刪除重復(fù)數(shù)據(jù) 輸出鏈表c結(jié)束2、 詳細(xì)設(shè)計(jì)第一題#include <stdio.h>#include <stdlib.h>/定義結(jié)構(gòu)體typedef struct LNode int data;struct LNode *next;LNode,*LinkList;/創(chuàng)建具有m個(gè)結(jié)點(diǎn)的單向環(huán)表void Create(LinkList &l,int m)LinkList p;l=(LinkList)malloc(sizeof(LNode);l->next=NULL;l->data=1;for(int i=m;i>1;i-)p=(L

5、inkList)malloc(sizeof(LNode);p->data=i;if(i=m) p->next=l;else p->next=l->next;l->next=p;/主函數(shù)int main ()int m,s,n,i;LNode *l,*p,*q;printf("請輸入m s nn");scanf("%d %d %d",&m,&s,&n);Create(l,m);for(i=1,p=l;i<s;i+) /尋找起始結(jié)點(diǎn)s p=p->next;while (m-)for(i=1;i

6、<n-1;i+) /計(jì)數(shù)到第n個(gè)結(jié)點(diǎn)時(shí)，輸出該第n結(jié)點(diǎn)對應(yīng)的編號 p=p->next; q=p->next;printf("%d ",q->data);p->next=q->next; /將該結(jié)點(diǎn)從環(huán)表中消除p=p->next;free(q);return 0;第二題#include <stdio.h>#include <stdlib.h>typedef struct LNodeint data;struct LNode *next;LNode,*LinkList;/從鍵盤輸入升序排列的整數(shù)序列，序列以輸入0

7、為結(jié)束標(biāo)記。 void create(LinkList &head)LinkList p,q;int n;head=(LinkList)malloc(sizeof(LNode); head->next=NULL; scanf("%d",&n); p=(LinkList)malloc(sizeof(LNode); p=head; while(n!=0) q=(LinkList)malloc(sizeof(LNode); q->data=n; q->next=p->next; p->next=q; p=q; scanf("

8、%d",&n); /將鏈表La和Lb歸并為Lc，Lc仍然為升序排列 void paixu(LinkList &La,LinkList &Lb,LinkList &Lc) LinkList pa,pb,pc,p,q; pa=La->next; pb=Lb->next; Lc=(LinkList)malloc(sizeof(LNode); Lc->next=NULL; pc=Lc; while(pa&&pb) if(pa->data<=pb->data) pc->next=pa;pc=pa;pa=p

9、a->next; else pc->next=pb;pc=pb;pb=pb->next; pc->next=pa?pa:pb;/對c進(jìn)行處理，保持升序不變，刪除其中重復(fù)的整數(shù)，對重復(fù)的整數(shù)保留一個(gè)void shanchu(LinkList &c)LinkList p,q;p=(LinkList)malloc(sizeof(LNode);q=(LinkList)malloc(sizeof(LNode);p=c->next;while(p->next!=NULL)if(p->data=p->next->data)q=p->next

10、;p->next=q->next;else p=p->next;/輸出鏈表cvoid output(LinkList &c)LinkList p;p=(LinkList)malloc(sizeof(LNode);p=c->next;while(p->next!=NULL)printf("%d ",p->data);p=p->next;printf("%dn",p->data);/主函數(shù)int main() LNode *a,*b,*c;printf("請輸入整數(shù)序列l(wèi)inka：n"

11、;);create(a);printf("請輸入整數(shù)序列l(wèi)inkb：n");create(b);paixu(a,b,c);free(a); free(b); /歸并完成后，a和b為空表output(c);shanchu(c);output(c);return 0;4、 程序調(diào)試分析 第一題 計(jì)數(shù)到第n個(gè)結(jié)點(diǎn)時(shí)應(yīng)定位在n-1個(gè)節(jié)點(diǎn)，這樣才能刪除第n個(gè)節(jié)點(diǎn)。第二題 將鏈表a和鏈表b合并時(shí)易出錯(cuò)，需要理好關(guān)系，可以借助畫圖試思路更清晰。體會(huì) 當(dāng)程序運(yùn)行出現(xiàn)問題的時(shí)候，一定要仔細(xì)一步步去調(diào)試，很有可能一個(gè)很小的漏洞就導(dǎo)致整個(gè)程序的錯(cuò)誤。五、程序運(yùn)行結(jié)果與分析第一題 測試用例1 輸入

12、：10 5 4 輸出：8 2 6 1 7 4 3 5 10 9 測試用例2 輸入：15 3 4 輸出：6 10 14 3 8 13 4 11 2 12 7 5 9 1 15第二題 測試用例1 輸入：10 20 30 40 0 10 15 20 25 30 0 輸出：10 10 15 20 20 25 30 30 40 10 15 20 25 30 40測試用例2 輸入：100 200 300 400 0 150 200 300 350 400 0 輸出：100 150 200 200 300 300 350 400 400 100 150 200 300 350 400六、用戶使用說明書 第一題1、 本程序的運(yùn)行環(huán)境為Windows操作系統(tǒng)下的DEV c+。2