數(shù)據(jù)結(jié)構(gòu)與算法綜合設(shè)計(jì)實(shí)驗(yàn)1實(shí)驗(yàn)報(bào)告

1、電 子 科 技 大 學(xué)實(shí) 驗(yàn) 報(bào) 告學(xué)生姓名：蘇魏明 學(xué) 號(hào)：指導(dǎo)教師： 實(shí)驗(yàn)地點(diǎn)： 實(shí)驗(yàn)時(shí)間：一、實(shí)驗(yàn)室名稱：軟件實(shí)驗(yàn)室 二、實(shí)驗(yàn)項(xiàng)目名稱：數(shù)據(jù)結(jié)構(gòu)與算法線性表三、實(shí)驗(yàn)學(xué)時(shí)：4四、實(shí)驗(yàn)原理：在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)空間可以不連續(xù)，各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致，而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來確定的。鏈?zhǔn)酱鎯?chǔ)方式即可以用于表示線性結(jié)構(gòu)，也可用于表示非線性結(jié)構(gòu)。一般來說，在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)符號(hào)是不連續(xù)的，并且各結(jié)點(diǎn)在存儲(chǔ)空間中的位置關(guān)系與邏輯關(guān)系也不一致。對(duì)于線性鏈表，可以從頭指針開始，沿各結(jié)點(diǎn)的指針掃描到鏈表中的所有結(jié)點(diǎn)。線性表

2、的鏈接存儲(chǔ)中，為了方便在表頭插入和刪除結(jié)點(diǎn)的操作，經(jīng)常在表頭結(jié)點(diǎn)（存儲(chǔ)第一個(gè)元素的結(jié)點(diǎn)）的前面增加一個(gè)結(jié)點(diǎn)，稱之為頭結(jié)點(diǎn)或表頭附加結(jié)點(diǎn)。這樣原來的表頭指針由指向第一個(gè)元素的結(jié)點(diǎn)改為指向頭結(jié)點(diǎn)，頭結(jié)點(diǎn)的數(shù)據(jù)域?yàn)榭?，頭結(jié)點(diǎn)的指針域指向第一個(gè)元素的結(jié)點(diǎn)。五、實(shí)驗(yàn)?zāi)康模罕緦?shí)驗(yàn)通過定義單向鏈表的數(shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)創(chuàng)建鏈表、插入結(jié)點(diǎn)、遍歷結(jié)點(diǎn)等基本算法，使學(xué)生掌握線性鏈表的基本特征和算法，并能熟練編寫c程序，培養(yǎng)理論聯(lián)系實(shí)際和自主學(xué)習(xí)的能力，提高程序設(shè)計(jì)水平。六、實(shí)驗(yàn)內(nèi)容：使用數(shù)據(jù)結(jié)構(gòu)typedef struct node elemtype data； struct node *next； listnode,

3、 *listptr； typedef struct stuinfo char stuname10; /*學(xué)生姓名*/ int age /*年齡*/ elemtype實(shí)現(xiàn)帶頭結(jié)點(diǎn)的單向鏈表的創(chuàng)建、刪除鏈表、插入結(jié)點(diǎn)等操作，并能實(shí)現(xiàn)年齡遞增的兩個(gè)單向鏈表合并一個(gè)鏈表，合并后的鏈表按年齡遞減，可認(rèn)為同名同年齡是同一個(gè)學(xué)生，每個(gè)學(xué)生在合并后的鏈表中僅出現(xiàn)一次。最后打印輸出合并后的鏈表元素，驗(yàn)證結(jié)果的正確性。七、實(shí)驗(yàn)器材（設(shè)備、元器件）：pc機(jī)一臺(tái)，裝有c語言集成開發(fā)環(huán)境。八、數(shù)據(jù)結(jié)構(gòu)與程序：#include stdafx.h#include #include #include #definemaxcn

4、t 50typedef struct stuinfo char stuname10; _int64 age; elemtype;typedef struct node elemtype data; struct node *next; listnode, *listnodeptr;typedef listnodeptr list, *listptr;/ 創(chuàng)建單鏈表: 設(shè)線性表n個(gè)元素已存放在數(shù)組elem中，動(dòng)態(tài)創(chuàng)建一個(gè)單鏈表l/ 函數(shù)返回值為整型：0表示創(chuàng)建成功，1表示創(chuàng)建失敗int list_create(listptr l, elemtype elem, int n)int result

5、= 0, / 記錄程序運(yùn)行結(jié)果 0表示成功 1表示失敗i = n;listnodeptr p,q;q = (listnodeptr)malloc(sizeof(listnode);q-next = null;while(i = 1)p = (listnodeptr)malloc(sizeof(listnode);if(!p) result = 1; break;p-data.age = elemi.age;strcpy(p-data.stuname, elemi.stuname);p-next = q-next;q-next = p;i = i - 1;(*l) = q;return resu

6、lt;void list_destroy(listptr l)/ 銷毀單鏈表：釋放單鏈表所占存儲(chǔ)單元listnodeptr p;while(*l)p = (*l)-next;free(*l);*l = p;void list_clear(listptr l) / 初始化：將單鏈表l重置為空表listnodeptr p=(*l)-next; / p指向第一個(gè)節(jié)點(diǎn)(*l)-next=null; / 頭結(jié)點(diǎn)指針域?yàn)榭誰ist_destroy(&p); / 銷毀p所指的單鏈表/ 單鏈表中結(jié)點(diǎn)插入算法: 在單鏈表l中的第pos個(gè)結(jié)點(diǎn)前插入值為elem的數(shù)據(jù)元素/ 插入結(jié)果是新結(jié)點(diǎn)占據(jù)第pos個(gè)位置，原p

7、os位置結(jié)點(diǎn)變?yōu)榈趐os+1個(gè)結(jié)點(diǎn)/ 函數(shù)返回值為整型：0表示插入成功，1表示插入失敗int list_insert(listptr l, int pos, elemtype elem)int result = 1;listnodeptr p = (*l)-next, s;int i = 1;while(p & inext;if(p & i = pos-1)s = (listnodeptr)malloc(sizeof(listnode);if(s)p-data.age = elem.age;strcpy(p-data.stuname, elem.stuname);s-next = p-next

8、;p-next = s;result = 0;return result;/ 刪除單鏈表中結(jié)點(diǎn): 刪除單鏈表l中的第pos個(gè)結(jié)點(diǎn)數(shù)據(jù)元素/ 函數(shù)返回值為整型：0表示刪除成功，1表示刪除失敗int list_remove(listptr l, int pos)int result = 1;listnodeptr p = (*l)-next, q;int i = 1;while(p & inext;if(p & i = pos-1)q = p-next;p-next = q-next;free(q);result = 0;return result;/ 合并單鏈表操作,合并后的鏈表儲(chǔ)存在鏈表la中

9、；/ 合并之后按年齡遞減也就是年月日遞增的順序，排列學(xué)生信息；void list_merge(listptr la, listptr lb)listnodeptr p, pa=(*la)-next, pb=(*lb)-next;if(!pa & !pb)printf(對(duì)不起，由于兩張線性表均為空,合并失敗。n);exit(0);if(pa & pb) if(pa-data.age = pb-data.age)(*la)-next = pa;pa = pa-next;(*la)-next-next = null;else(*la)-next = pb;pb = pb-next;(*la)-nex

10、t-next = null;while(pa & pb)if(pa-data.age = pb-data.age)p = pa-next;pa-next = (*la)-next;(*la)-next = pa;pa = p;else p = pb-next;pb-next = (*la)-next;(*la)-next = pb;pb = p;while(pb) / b表中還有元素p = pb-next;pb-next = (*la)-next;(*la)-next = pb;pb = p;while(pa) / a表中還有元素p = pa-next;pa-next = (*la)-next

11、;(*la)-next = pa;pa = p;printf(合并成功！n);void show_list(listnodeptr l)/ 輸出單鏈表中元素listnodeptr p = l-next;if(!p) printf(對(duì)不起，由于單鏈表為空，打印失敗！n); return;while(p)printf(%i64dt%sn, p-data.age, p-data.stuname);p = p-next;int read_file(char * fname, char namemaxcnt11, _int64* age)int scount = 0;char charage13 + 1

12、;file * pfile = null;pfile = fopen(fname, r);if(!pfile)printf(read_file(): file open failed!n);exit(0);elseprintf(read_file(): file open succeeded!n);memset(age, 0, maxcnt *8);memset(name, 0, maxcnt * (10 + 1);while(!feof(pfile)fscanf(pfile,%s,charage);fscanf(pfile,t%sn,namescount);agescount = _atoi

13、64(charage);scount+;fclose(pfile);return scount;void bubble_sort(elemtype elem, int n)/ 冒泡排序 將學(xué)生信息以年齡遞增的順序 也就是按出生年月降序排列int i, j, swap;for(i=1; in; i+)swap = 0; for(j=1; j=n-1; j+)if(elemj.ageelemj+1.age)elem0.age = elemj+1.age; elemj+1.age = elemj.age; elemj.age = elem0.age;strcpy(elem0.stuname, ele

14、mj+1.stuname); strcpy(elemj+1.stuname, elemj.stuname);strcpy(elemj.stuname, elem0.stuname);swap = 1; if(swap = 0) break; int main()charnamemaxcnt10+1; /存放姓名，名字最長為10個(gè)字符； _int64agemaxcnt; /采用64位整型；char * fnamea = d:filestuinfoa.txt, * fnameb = d:filestuinfob.txt;/ 定義文本信息存儲(chǔ)路徑char main_command, case_com

15、mand;int i, num, pos, temp;listnodeptr la=null ,lb=null;elemtype elemmaxcnt+1;/ 讀入學(xué)生信息，并分別存入單鏈表表la，lb中num = read_file(fnamea, name, age);for(i=1; i=num; +i)elemi.age = agei-1;strcpy(elemi.stuname, namei-1);bubble_sort(elem, num);list_create(&la, elem, num);num = read_file(fnameb, name, age);for(i=1;

16、 i=num; +i)elemi.age = agei-1;strcpy(elemi.stuname, namei-1);bubble_sort(elem, num);list_create(&lb, elem, num);for(;)printf(n*% 請(qǐng)選擇將要進(jìn)行的操作 ooooooo*nn);printf(*% a.對(duì)線性表a進(jìn)行操作 ooooooo*n);printf(*% b.對(duì)線性表b進(jìn)行操作 ooooooo*n);printf(*% c.對(duì)線性表a,b進(jìn)行合并 ooooooo*n);printf(*% 輸入其他字符退出程序 ooooooo*nn);fflush(stdin);

17、printf(請(qǐng)輸入您要進(jìn)行的操作（a，b或c）：);scanf(%c, &main_command);switch(main_command)case a: case a:if(la=null) printf(您好，線性表b已被刪除！n); break;printf(n* 請(qǐng)選擇將要進(jìn)行的操作 *nn);printf(* a.刪除線性表a中的信息*n);printf(* b.打印線性表a中的信息*n);printf(* c.銷毀線性表a *nn);fflush(stdin);printf(請(qǐng)輸入您要進(jìn)行的操作（a，b或c）：);scanf(%c, &case_command);switch(

18、case_command)case a: case a:printf(請(qǐng)輸入要?jiǎng)h學(xué)生信息的序號(hào)：);scanf(%d, &pos);temp = list_remove(&la, pos);if(temp=1) printf(對(duì)不起，學(xué)生信息刪除失?。);else printf(您好，學(xué)生信息刪除成功！n);printf(打印刪除學(xué)生信息后的線性表如下：n);show_list(la);break;case b:case b:show_list(la);break;case c:case c:list_destroy(&la);printf(您好，線性表a刪除成功！n); break;def

19、ault: printf(對(duì)不起，您的輸入有誤！n); break;break;case b: caseb :if(lb=null) printf(對(duì)不起，線性表b已被刪除！n); break;printf(n* 請(qǐng)選擇將要進(jìn)行的操作 *nn);printf(* a.刪除線性表b中的信息*n);printf(* b.打印線性表b中的信息*n);printf(* c.銷毀線性表b *nn);fflush(stdin);printf(請(qǐng)輸入您要進(jìn)行的操作（a，b或c）：);scanf(%c, &case_command);switch(case_command)case a: case a:pri

20、ntf(請(qǐng)輸入待刪學(xué)生信息的序號(hào)：);scanf(%d, &pos);temp = list_remove(&lb, pos);if(temp=1) printf(對(duì)不起，學(xué)生信息刪除失?。);else printf(您好，學(xué)生信息已成功刪除！n);break;case b:case b:show_list(lb);break;case c:case c:list_destroy(&lb);printf(您好，線性表b已成功刪除！n); break; default: printf(對(duì)不起，您的輸入有誤！n); break;break;case c: case c:list_merge(&la, &lb);printf(打印合并后的線性表如下：n);show_list(la);system(pause);return 0;break;default:pr