數(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)年齡遞增的兩個單向鏈表合并一個鏈表，合并后的鏈表按年齡遞減，可認為同名同年齡是同一個學(xué)生，每個學(xué)生在合并后的鏈表中僅出現(xiàn)一次。最后打印輸出合并后的鏈表元素，驗證結(jié)果的正確性。七、實驗器材（設(shè)備、元器件）：pc機一臺，裝有c語言集成開發(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個元素已存放在數(shù)組elem中，動態(tài)創(chuàng)建一個單鏈表l/ 函數(shù)返回值為整型：0表示創(chuàng)建成功，1表示創(chuàng)建失敗

5、int list_create(listptr l, elemtype elem, int n)int result = 0, / 記錄程序運行結(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)/ 銷毀單鏈表：釋放單鏈表所占存儲單元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é)

7、點指針域為空list_destroy(&p); / 銷毀p所指的單鏈表/ 單鏈表中結(jié)點插入算法: 在單鏈表l中的第pos個結(jié)點前插入值為elem的數(shù)據(jù)元素/ 插入結(jié)果是新結(jié)點占據(jù)第pos個位置，原pos位置結(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 && 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é)點: 刪除單鏈表l中的第pos個結(jié)點數(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;/ 合并單鏈表操作,合并后的鏈表儲存在鏈表la中；/ 合并之后按年齡遞減也就是年月日遞增的順序，排列學(xué)生信息；void list_merge(listptr la, listptr lb)lis

10、tnodeptr 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)-&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("對不起，由于單鏈表為空，打印失?。"); 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; /存放姓名，名字最長為10個字符； _int64agemaxcnt; /采用64位整型；char * fnamea = "d:filestuinfoa.txt", * fnameb = "d:filestuinfob.txt"/ 定義文本信息存儲路徑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*% 請選擇將要進行的操作 ooooooo*nn");printf("*% a.對線性表a進行操作 ooooooo*n");printf("*% b.對線性表b進行操作 ooooooo*n");printf("*% c.對線性表a,b進行合并 ooooooo*n");printf("*% 輸入其他字符退出程序 ooooooo*nn"

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

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

21、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;defaul

22、t: printf("對不起，您的輸入有誤！n"); break;break;case 'b': case'b' :if(lb=null) printf("對不起，線性表b已被刪除！n"); break;printf("n* 請選擇將要進行的操作 *nn");printf("* a.刪除線性表b中的信息*n");printf("* b.打印線性表b中的信息*n");printf("* c.銷毀線性表b *nn");fflush(stdin);p

23、rintf("請輸入您要進行的操作（a，b或c）：");scanf("%c", &case_command);switch(case_command)case 'a': case 'a':printf("請輸入待刪學(xué)生信息的序號：");scanf("%d", &pos);temp = list_remove(&lb, pos);if(temp=1) printf("對不起，學(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("對不起，您的輸入有誤！n"); break;break;case 'c': case 'c':list_merge(&la, &lb);printf(&qu