實(shí)驗(yàn)二：線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)

1、學(xué)校代碼： 10128學(xué) 號(hào)： 201220905048 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告（題 目：線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)學(xué)生姓名：孫躍學(xué) 院：理學(xué)院系 別：數(shù)學(xué)系專 業(yè)：信息與計(jì)算科學(xué)班 級(jí)：信計(jì)12-2任課教師：杜雅娟二一四年九月111、 實(shí)驗(yàn)?zāi)康?理解線性結(jié)構(gòu)的定義、組織形式、結(jié)構(gòu)特征和類型說(shuō)明以及在鏈?zhǔn)酱鎯?chǔ)方式下實(shí)現(xiàn)的插入、刪除和按值查找的算法。2、 實(shí)驗(yàn)內(nèi)容線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)3、 實(shí)驗(yàn)程序 根據(jù)給出的程序清單分別另建立4個(gè)文件：c1.h、c2-2.h、bo2-2.cpp和main2-2.cpp，并把它們保存在同一個(gè)文件夾中。 1.預(yù)定義常量和類型 教材定義OK、ERROR等為函數(shù)結(jié)果狀態(tài)代碼，文

2、件Status為其類型。我們把這些信息放到頭文件c1.h中。c1.h還包含一些常用的，如string.h、stdio.h等。為了操作的方便，幾乎每一個(gè)程序都把C1.h包含進(jìn)去，也就把這些結(jié)果狀態(tài)代碼和頭文件包含了進(jìn)去。頭文件的內(nèi)容如下： / c1.h (程序名) #include<string.h> #include<ctype.h> #include<malloc.h> / malloc()等 #include<limits.h> / INT_MAX等 #include<stdio.h> / EOF(=Z或F6),NULL #inc

3、lude<stdlib.h> / atoi() #include<io.h> / eof() #include<math.h> / floor(),ceil(),abs() #include<process.h> / exit() #include<iostream.h> / cout,cin / 函數(shù)結(jié)果狀態(tài)代碼 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 / #define OVERFLOW -2 因?yàn)樵趍ath

4、.h中已定義OVERFLOW的值為3,故去掉此行/ #define OVERFLOW -2 因?yàn)樵趍ath.h中已定義OVERFLOW的值為3,故去掉此行 typedef int Status; / Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等 typedef int Boolean; / Boolean是布爾類型,其值是TRUE或FALSE2、 線性鏈表的單鏈表存儲(chǔ)結(jié)構(gòu)/ c2-2.h 線性表的單鏈表存儲(chǔ)結(jié)構(gòu) struct LNode ElemType data; LNode *next; ; typedef LNode *LinkList; / 另一種定義LinkList的方

5、法3、 單鏈表線性表的基本操作/ bo2-2.cpp 單鏈表線性表(存儲(chǔ)結(jié)構(gòu)由c2-2.h定義)的基本操作(12個(gè)) Status InitList(LinkList &L) / 操作結(jié)果：構(gòu)造一個(gè)空的線性表L L=(LinkList)malloc(sizeof(LNode); / 產(chǎn)生頭結(jié)點(diǎn),并使L指向此頭結(jié)點(diǎn) if(!L) / 存儲(chǔ)分配失敗 exit(OVERFLOW); L->next=NULL; / 指針域?yàn)榭?return OK; Status DestroyList(LinkList &L) / 初始條件：線性表L已存在。操作結(jié)果：銷毀線性表L LinkLis

6、t q; while(L) q=L->next; free(L); L=q; return OK; Status ClearList(LinkList L) / 不改變L / 初始條件：線性表L已存在。操作結(jié)果：將L重置為空表 LinkList p,q; p=L->next; / p指向第一個(gè)結(jié)點(diǎn) while(p) / 沒(méi)到表尾 q=p->next; free(p); p=q; L->next=NULL; / 頭結(jié)點(diǎn)指針域?yàn)榭?return OK; Status ListEmpty(LinkList L) / 初始條件：線性表L已存在。操作結(jié)果：若L為空表，則返回TRU

7、E，否則返回FALSE if(L->next) / 非空 return FALSE; else return TRUE; int ListLength(LinkList L) / 初始條件：線性表L已存在。操作結(jié)果：返回L中數(shù)據(jù)元素個(gè)數(shù) int i=0; LinkList p=L->next; / p指向第一個(gè)結(jié)點(diǎn) while(p) / 沒(méi)到表尾 i+; p=p->next; return i; Status GetElem(LinkList L,int i,ElemType &e) / 算法2.8 / L為帶頭結(jié)點(diǎn)的單鏈表的頭指針。當(dāng)?shù)趇個(gè)元素存在時(shí),其值賦給e并返

8、回OK,否則返回ERROR int j=1; / j為計(jì)數(shù)器 LinkList p=L->next; / p指向第一個(gè)結(jié)點(diǎn) while(p&&j<i) / 順指針向后查找,直到p指向第i個(gè)元素或p為空 p=p->next; j+; if(!p|j>i) / 第i個(gè)元素不存在 return ERROR; e=p->data; / 取第i個(gè)元素 return OK; int LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType) / 初始條件: 線性表L已存在,compa

9、re()是數(shù)據(jù)元素判定函數(shù)(滿足為1,否則為0) / 操作結(jié)果: 返回L中第1個(gè)與e滿足關(guān)系compare()的數(shù)據(jù)元素的位序。 /若這樣的數(shù)據(jù)元素不存在,則返回值為0 int i=0; LinkList p=L->next; while(p) i+; if(compare(p->data,e) / 找到這樣的數(shù)據(jù)元素 return i; p=p->next; return 0; Status PriorElem(LinkList L,ElemType cur_e,ElemType &pre_e) / 初始條件: 線性表L已存在 / 操作結(jié)果: 若cur_e是L的數(shù)據(jù)

10、元素,且不是第一個(gè),則用pre_e返回它的前驅(qū), / 返回OK;否則操作失敗,pre_e無(wú)定義,返回INFEASIBLE LinkList q,p=L->next; / p指向第一個(gè)結(jié)點(diǎn) while(p->next) / p所指結(jié)點(diǎn)有后繼 q=p->next; / q為p的后繼 if(q->data=cur_e) pre_e=p->data; return OK; p=q; / p向后移 return INFEASIBLE; Status NextElem(LinkList L,ElemType cur_e,ElemType &next_e) / 初始條件

11、：線性表L已存在 / 操作結(jié)果：若cur_e是L的數(shù)據(jù)元素，且不是最后一個(gè)，則用next_e返回它的后繼， / 返回OK;否則操作失敗，next_e無(wú)定義，返回INFEASIBLE LinkList p=L->next; / p指向第一個(gè)結(jié)點(diǎn) while(p->next) / p所指結(jié)點(diǎn)有后繼 if(p->data=cur_e) next_e=p->next->data; return OK; p=p->next; return INFEASIBLE; Status ListInsert(LinkList L,int i,ElemType e) / 算法2.

12、9。不改變L / 在帶頭結(jié)點(diǎn)的單鏈線性表L中第i個(gè)位置之前插入元素e int j=0; LinkList p=L,s; while(p&&j<i-1) / 尋找第i-1個(gè)結(jié)點(diǎn) p=p->next; j+; if(!p|j>i-1) / i小于1或者大于表長(zhǎng) return ERROR; s=(LinkList)malloc(sizeof(LNode); / 生成新結(jié)點(diǎn) s->data=e; / 插入L中 s->next=p->next; p->next=s; return OK; Status ListDelete(LinkList L,

13、int i,ElemType &e) / 算法2.10。不改變L / 在帶頭結(jié)點(diǎn)的單鏈線性表L中，刪除第i個(gè)元素,并由e返回其值 int j=0; LinkList p=L,q; while(p->next&&j<i-1) / 尋找第i個(gè)結(jié)點(diǎn),并令p指向其前趨 p=p->next; j+; if(!p->next|j>i-1) / 刪除位置不合理 return ERROR; q=p->next; / 刪除并釋放結(jié)點(diǎn) p->next=q->next; e=q->data; free(q); return OK; Sta

14、tus ListTraverse(LinkList L,void(*vi)(ElemType) / vi的形參類型為ElemType，與bo2-1.cpp中相應(yīng)函數(shù)的形參類型ElemType&不同 / 初始條件：線性表L已存在 / 操作結(jié)果:依次對(duì)L的每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)vi()。一旦vi()失敗,則操作失敗 LinkList p=L->next; while(p) vi(p->data); p=p->next; printf("n"); return OK; 4、檢驗(yàn)b02-2.cpp的主程序/ main2-2.cpp 檢驗(yàn)bo2-2.cpp的主

15、程序(與main2-1.cpp很像) #include"c1.h" typedef int ElemType; #include"c2-2.h" / 與main2-1.cpp不同 #include"bo2-2.cpp" / 與main2-1.cpp不同 Status comp(ElemType c1,ElemType c2) / 數(shù)據(jù)元素判定函數(shù)(相等為TRUE,否則為FALSE) if(c1=c2) return TRUE; else return FALSE; void visit(ElemType c) / 與main2-1.c

16、pp不同 printf("%d ",c); void main() / 除了幾個(gè)輸出語(yǔ)句外，主程和main2-1.cpp很像 LinkList L; / 與main2-1.cpp不同 ElemType e,e0; Status i; int j,k; i=InitList(L); for(j=1;j<=5;j+) i=ListInsert(L,1,j); printf("在L的表頭依次插入15后：L="); ListTraverse(L,visit); / 依次對(duì)元素調(diào)用visit()，輸出元素的值 i=ListEmpty(L); printf(&

17、quot;L是否空：i=%d(1:是 0:否)n",i); i=ClearList(L); printf("清空L后：L="); ListTraverse(L,visit); i=ListEmpty(L); printf("L是否空：i=%d(1:是 0:否)n",i); for(j=1;j<=10;j+) ListInsert(L,j,j); printf("在L的表尾依次插入110后：L="); ListTraverse(L,visit); GetElem(L,5,e); printf("第5個(gè)元素的值為

18、：%dn",e); for(j=0;j<=1;j+) k=LocateElem(L,j,comp); if(k) printf("第%d個(gè)元素的值為%dn",k,j); else printf("沒(méi)有值為%d的元素n",j); for(j=1;j<=2;j+) / 測(cè)試頭兩個(gè)數(shù)據(jù) GetElem(L,j,e0); / 把第j個(gè)數(shù)據(jù)賦給e0 i=PriorElem(L,e0,e); / 求e0的前驅(qū) if(i=INFEASIBLE) printf("元素%d無(wú)前驅(qū)n",e0); else printf("元素%d的前驅(qū)為：%dn",e0,e); for(j=ListLength(L)-1;j<=ListLength(L);j+)/最后兩個(gè)數(shù)據(jù) GetElem(L,j,e0); / 把第j個(gè)數(shù)據(jù)賦給e0 i=NextElem(L,e0,e