數(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)系是由指針域來(lái)確定的。鏈?zhǔn)酱鎯?chǔ)方式即可以用于表示線性結(jié)構(gòu)，也可用于表示非線性結(jié)構(gòu)。一般來(lái)說(shuō)，在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)符號(hào)是不連續(xù)的，并且各結(jié)點(diǎn)在存儲(chǔ)空間中的位置關(guān)系與邏輯關(guān)系也不一致。對(duì)于線性鏈表，可以從頭指針開(kāi)始，沿各結(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)。這樣原來(lái)的表頭指針由指向第一個(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)通過(guò)定義單向鏈表的數(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語(yǔ)言集成開(kāi)發(fā)環(huán)境。八、數(shù)據(jù)結(jié)構(gòu)與程序：#include "stdafx.h"#include <stdio.h>#in

4、clude <stdlib.h>#include <string.h>#definemaxcnt 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)建失敗

5、int list_create(listptr l, elemtype elem, int n)int result = 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.stunam

6、e, elemi.stuname);p->next = q->next;q->next = p;i = i - 1;(*l) = q;return result;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é)

7、點(diǎn)指針域?yàn)榭誰(shuí)ist_destroy(&p); / 銷毀p所指的單鏈表/ 單鏈表中結(jié)點(diǎn)插入算法: 在單鏈表l中的第pos個(gè)結(jié)點(diǎn)前插入值為elem的數(shù)據(jù)元素/ 插入結(jié)果是新結(jié)點(diǎn)占據(jù)第pos個(gè)位置，原pos位置結(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 && i<pos-1) i+;p = p->ne

8、xt;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;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)in

9、t result = 1;listnodeptr p = (*l)->next, q;int i = 1;while(p && i<pos-1) i+;p = p->next;if(p && i = pos-1)q = p->next;p->next = q->next;free(q);result = 0;return result;/ 合并單鏈表操作,合并后的鏈表儲(chǔ)存在鏈表la中；/ 合并之后按年齡遞減也就是年月日遞增的順序，排列學(xué)生信息；void list_merge(listptr la, listptr lb)lis

10、tnodeptr 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)-&g

11、t;next->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;

12、(*la)->next = pb;pb = p;while(pa) / a表中還有元素p = pa->next;pa->next = (*la)->next;(*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"

13、;, p->data.age, p->data.stuname);p = p->next;int read_file(char * fname, char namemaxcnt11, _int64* age)int scount = 0;char charage13 + 1;file * pfile = null;pfile = fopen(fname, "r");if(!pfile)printf("read_file(): file open failed!n");exit(0);elseprintf("read_file(

14、): 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 = _atoi64(charage);scount+;fclose(pfile);return scount;void bubble_sort(elemtype elem, int n)/ 冒泡排序 將

15、學(xué)生信息以年齡遞增的順序 也就是按出生年月降序排列int i, j, swap;for(i=1; i<n; i+)swap = 0; for(j=1; j<=n-1; j+)if(elemj.age<elemj+1.age)elem0.age = elemj+1.age; elemj+1.age = elemj.age; elemj.age = elem0.age;strcpy(elem0.stuname, elemj+1.stuname); strcpy(elemj+1.stuname, elemj.stuname);strcpy(elemj.stuname, elem0.

16、stuname);swap = 1; if(swap = 0) break; int main()charnamemaxcnt10+1; /存放姓名，名字最長(zhǎng)為10個(gè)字符； _int64agemaxcnt; /采用64位整型；char * fnamea = "d:filestuinfoa.txt", * fnameb = "d:filestuinfob.txt"/ 定義文本信息存儲(chǔ)路徑char main_command, case_command;int i, num, pos, temp;listnodeptr la=null ,lb=null;ele

17、mtype 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; i<=num; +i)elemi.age = agei-1;strcpy(elemi.stun

18、ame, 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"

19、;);fflush(stdin);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.打印線

20、性表a中的信息*n");printf("* c.銷毀線性表a *nn");fflush(stdin);printf("請(qǐng)輸入您要進(jìn)行的操作（a，b或c）：");scanf("%c", &case_command);switch(case_command)case 'a': case 'a':printf("請(qǐng)輸入要?jiǎng)h學(xué)生信息的序號(hào)：");scanf("%d", &pos);temp = list_remove(&la, pos);

21、if(temp=1) printf("對(duì)不起，學(xué)生信息刪除失??！n");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;defaul

22、t: printf("對(duì)不起，您的輸入有誤！n"); break;break;case 'b': case'b' :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);p

23、rintf("請(qǐng)輸入您要進(jìn)行的操作（a，b或c）：");scanf("%c", &case_command);switch(case_command)case 'a': case 'a':printf("請(qǐng)輸入待刪學(xué)生信息的序號(hào)：");scanf("%d", &pos);temp = list_remove(&lb, pos);if(temp=1) printf("對(duì)不起，學(xué)生信息刪除失??！n");else printf("您好，

24、學(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(&qu