數(shù)據(jù)結(jié)構(gòu)與算法綜合設(shè)計實驗1實驗報告

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

2、的鏈接存儲中，為了方便在表頭插入和刪除結(jié)點的操作，經(jīng)常在表頭結(jié)點（存儲第一個元素的結(jié)點）的前面增加一個結(jié)點，稱之為頭結(jié)點或表頭附加結(jié)點。這樣原來的表頭指針由指向第一個元素的結(jié)點改為指向頭結(jié)點，頭結(jié)點的數(shù)據(jù)域為空，頭結(jié)點的指針域指向第一個元素的結(jié)點。五、實驗?zāi)康模罕緦嶒炌ㄟ^定義單向鏈表的數(shù)據(jù)結(jié)構(gòu)，設(shè)計創(chuàng)建鏈表、插入結(jié)點、遍歷結(jié)點等基本算法，使學(xué)生掌握線性鏈表的基本特征和算法，并能熟練編寫c程序，培養(yǎng)理論聯(lián)系實際和自主學(xué)習(xí)的能力，提高程序設(shè)計水平。六、實驗內(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實現(xiàn)帶頭結(jié)點的單向鏈表的創(chuàng)建、刪除鏈表、插入結(jié)點等操作，并能實現(xiàn)年齡遞增的兩個單向鏈表合并一個鏈表，合并后的鏈表按年齡遞減，可認(rèn)為同名同年齡是同一個學(xué)生，每個學(xué)生在合并后的鏈表中僅出現(xiàn)一次。最后打印輸出合并后的鏈表元素，驗證結(jié)果的正確性。七、實驗器材（設(shè)備、元器件）：pc機(jī)一臺，裝有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個元素已存放在數(shù)組elem中，動態(tài)創(chuàng)建一個單鏈表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)/ 銷毀單鏈表：釋放單鏈表所占存儲單元listnodeptr p;while(*l)p = (*l)-next;free(*l);*l = p;void list_clear(listptr l) / 初始化：將單鏈表l重置為空表listnodeptr p=(*l)-next; / p指向第一個節(jié)點(*l)-next=null; / 頭結(jié)點指針域為空list_destroy(&p); / 銷毀p所指的單鏈表/ 單鏈表中結(jié)點插入算法: 在單鏈表l中的第pos個結(jié)點前插入值為elem的數(shù)據(jù)元素/ 插入結(jié)果是新結(jié)點占據(jù)第pos個位置，原p

7、os位置結(jié)點變?yōu)榈趐os+1個結(jié)點/ 函數(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é)點: 刪除單鏈表l中的第pos個結(jié)點數(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;/ 合并單鏈表操作,合并后的鏈表儲存在鏈表la中

9、；/ 合并之后按年齡遞減也就是年月日遞增的順序，排列學(xué)生信息；void list_merge(listptr la, listptr lb)listnodeptr p, pa=(*la)-next, pb=(*lb)-next;if(!pa & !pb)printf(對不起，由于兩張線性表均為空,合并失敗。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(對不起，由于單鏈表為空，打印失??！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個字符； _int64agemaxcnt; /采用64位整型；char * fnamea = d:filestuinfoa.txt, * fnameb = d:filestuinfob.txt;/ 定義文本信息存儲路徑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*% 請選擇將要進(jìn)行的操作 ooooooo*nn);printf(*% a.對線性表a進(jìn)行操作 ooooooo*n);printf(*% b.對線性表b進(jìn)行操作 ooooooo*n);printf(*% c.對線性表a,b進(jìn)行合并 ooooooo*n);printf(*% 輸入其他字符退出程序 ooooooo*nn);fflush(stdin);

17、printf(請輸入您要進(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* 請選擇將要進(jìn)行的操作 *nn);printf(* a.刪除線性表a中的信息*n);printf(* b.打印線性表a中的信息*n);printf(* c.銷毀線性表a *nn);fflush(stdin);printf(請輸入您要進(jìn)行的操作（a，b或c）：);scanf(%c, &case_command);switch(

18、case_command)case a: case a:printf(請輸入要刪學(xué)生信息的序號：);scanf(%d, &pos);temp = list_remove(&la, pos);if(temp=1) printf(對不起，學(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(對不起，您的輸入有誤！n); break;break;case b: caseb :if(lb=null) printf(對不起，線性表b已被刪除！n); break;printf(n* 請選擇將要進(jìn)行的操作 *nn);printf(* a.刪除線性表b中的信息*n);printf(* b.打印線性表b中的信息*n);printf(* c.銷毀線性表b *nn);fflush(stdin);printf(請輸入您要進(jìn)行的操作（a，b或c）：);scanf(%c, &case_command);switch(case_command)case a: case a:pri

20、ntf(請輸入待刪學(xué)生信息的序號：);scanf(%d, &pos);temp = list_remove(&lb, pos);if(temp=1) printf(對不起，學(xué)生信息刪除失??！n);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(對不起，您的輸入有誤！n); break;break;case c: case c:list_merge(&la, &lb);printf(打印合并后的線性表如下：n);show_list(la);system(pause);return 0;break;default:pr