數(shù)據(jù)結(jié)構(gòu)上機(jī)報(bào)告

1、* *數(shù)據(jù)結(jié)構(gòu)上機(jī)報(bào)告_2011_ 年_ 3 _月_ 9 _日姓名 _學(xué)號(hào)_同組成員_ _無(wú)_ _1. 實(shí)驗(yàn)題目及要求編寫(xiě)一個(gè)程序，實(shí)現(xiàn)單鏈表 的各種基本運(yùn)算2. 需求分析建立一個(gè)單鏈表，實(shí)現(xiàn)單鏈表的初始化，插入、刪除節(jié)點(diǎn)等功能，以及確定某一元素在單鏈表中的位置。（ 1 ） 初始化單鏈表；（ 2 ） 依次采用尾插入法插入 a,b,c,d,e 元素；（ 3 ） 輸出單鏈表 L；（ 4 ） 輸出單鏈表 L 的長(zhǎng)度；（ 5 ） 判斷單鏈表 L 是否為空；（ 6 ） 輸出單鏈表 L 的第三個(gè)元素；（ 7 ） 輸出元素 a 的位置；（ 8 ） 在第 4 個(gè)元素位置上插入 f 元素；（ 9 ） 輸出單鏈表

2、 L；* *（ 10）刪除 L的第 3 個(gè)元素；（ 11 ） 輸出單鏈表 L；（ 12 ） 釋放單鏈表。3. 概要設(shè)計(jì)（ 1 ） 為了實(shí)現(xiàn)上述程序功能，需要定義一個(gè)簡(jiǎn)化的線性表抽象數(shù)據(jù)類(lèi)型：ADT LinearList 數(shù)據(jù)對(duì)象： D= a i|a iIntegerSet,i=0,1,2,n,n 0結(jié)構(gòu)關(guān)系： R=|a i,ai+1 D基本操作：InitList_L(L)操作前提： L 是一個(gè)未初始化的線性表操作結(jié)果：將L 初始化為一個(gè)空的線性表CreateList_L(L)操作前提： L 是一個(gè)已初始化的空表操作結(jié)果：建立一個(gè)非空的線性表LListInsert_L(L,pos,e)操作前提：

3、線性表L 已存在操作結(jié)果：將元素e 插入到線性表L 的 pos 位置* *ListDelete_L(L,pos,e)操作前提：線性表L 已存在操作結(jié)果：將線性表L 中 pos 位置的元素刪除，刪除的元素值通過(guò)e 返回LocateList_L(L,e)操作前提：線性表L 已存在操作結(jié)果：在線性表L 中查找元素e，若存在，返回元素在表中的序號(hào)位置；若不存在，返回-1DestroyList_L(&L)初始條件：線性表L 已存在操作結(jié)果：銷(xiāo)毀線性表ListEmpty_L(L)初始條件：線性表已存在操作結(jié)果：若L 為空表，則返回ERROR ，否則返回FALSEListLength_L(L)初始條件：線性

4、表L 已存在* *操作結(jié)果：返回L 中數(shù)據(jù)元素個(gè)數(shù)GetElem_L(L,I,&e)初始條件：線性表L 已存在操作結(jié)果：用e 返回 L 中第 i 個(gè)數(shù)據(jù)元素值（ 2 ） 本程序包含 10 個(gè)函數(shù)：主函數(shù) main()初始化單鏈表函數(shù) InitList_L()顯示單鏈表內(nèi)容函數(shù) DispList_L()插入元素函數(shù) ListInsert_L()刪除元素函數(shù) ListDelete_L()查找元素函數(shù) LocateList_L()創(chuàng)建鏈表函數(shù) CreateList_L()鏈表元素長(zhǎng)度函數(shù) ListLength_L()判斷鏈表是否為空函數(shù) ListEmpty_L()取值函數(shù) GetElem_L()各函

5、數(shù)間調(diào)用關(guān)系如下：InitListDispListCreateListListLengthListEmptymain* *( 3 )主函數(shù)的偽碼main() 說(shuō)明一個(gè)單鏈表L ；* *初始化L；建立L；顯示L；4. 詳細(xì)設(shè)計(jì)采用單鏈表實(shí)現(xiàn)概要設(shè)計(jì)中定義的抽象數(shù)據(jù)類(lèi)型，有關(guān)的數(shù)據(jù)類(lèi)型和偽碼算法定義如下：（1 ）類(lèi)型定義typedef int ElemType;typedef struct LNodeElemType data;/ 數(shù)據(jù)域struct LNode *next; /指針域 LNode,* LinkList;（ 2 ） 基本操作的偽碼算法初始化Bool InitLinkList(Lin

6、kList *L) *L= 申請(qǐng)新結(jié)點(diǎn) ;如果申請(qǐng)失敗，返回失敗標(biāo)志；(*L)-next=NULL;返回成功標(biāo)志；* *建立單鏈表Bool CrtLinkList(LinkList L)/* L 是已經(jīng)初始化好的空鏈表的頭指針，通過(guò)鍵盤(pán)輸入元素值，利用尾插法建單鏈表L */ rear=L;打印輸入提示： “請(qǐng)輸入若干個(gè)正整數(shù)（用空格分隔），并用-1結(jié)束：”讀入一個(gè)數(shù)x;當(dāng) x 不是結(jié)束標(biāo)志時(shí)，循環(huán)做如下處理：申請(qǐng)一個(gè)新結(jié)點(diǎn)s；如果申請(qǐng)失敗，返回失敗標(biāo)志；將 x 送到 s 的 data 域 ; rear-next=s; rear=s;讀入下一個(gè)數(shù)x;rear-next=NULL;返回成功標(biāo)志；*

7、 *顯示單鏈表（輸出）void DispLinkList(LinkList L)p= 首元素結(jié)點(diǎn)地址;while ( p不空)打印結(jié)點(diǎn)p的元素值；p= 下一個(gè)結(jié)點(diǎn)地址;插入操作bool InsLinkList(LinkList L, int pos, ElemType e)/* 在帶頭結(jié)點(diǎn)的單鏈表L 中第 pos 個(gè)位置插入值為e 的新結(jié)點(diǎn)s*/從“頭”開(kāi)始，查找第i-1 個(gè)結(jié)點(diǎn)pre ;if ( 查找失敗 ) 顯示參數(shù)錯(cuò)誤信息 ; return ERROR;* *else申請(qǐng)一個(gè)新的結(jié)點(diǎn)s ;將 e 放入 s 的數(shù)據(jù)域 ;將 s 插到 pre 后面 ; return OK;刪除操作bool

8、DelLinkList(LinkList L, int pos, ElemType *e)/*在帶頭結(jié)點(diǎn)的單鏈表L 中刪除第pos 個(gè)元素，并將刪除的元素保存到變量*e 中 */查找待刪除結(jié)點(diǎn)i 的前驅(qū)結(jié)點(diǎn)，并用pre 指向它 ;if ( 查找失敗 ) 顯示參數(shù)錯(cuò)誤信息 ; return ERROR;elser=pre-next;修改指針，刪除結(jié)點(diǎn)r ;* *釋放被刪除的結(jié)點(diǎn)所占的內(nèi)存空間;return OK;查找操作intLocLinkList(LinkList L, ElemType e)/ *在帶頭結(jié)點(diǎn)的單鏈表L 中查找其結(jié)點(diǎn)值等于e 的結(jié)點(diǎn)，若找到則返回該結(jié)點(diǎn)的序號(hào)位置k，否則返回-1

9、 * /p= 首元素結(jié)點(diǎn)地址;while ( p不空)if (p-data!=e) p=p-next;k+; elsebreak;if ( p不空 )returnk;elsereturn-1;* *5.調(diào)試分析開(kāi)始運(yùn)行時(shí)會(huì)出現(xiàn)Debug Error， DAMAGE: After Normal block， 搜索后了解到是內(nèi)存越界操作，檢查后發(fā)現(xiàn)內(nèi)存分配L 和S=(LinkList)malloc(sizeof(LNode)寫(xiě)成了 =(LinkList)malloc(sizeof(LinkList)，修改后正常。6. 使用說(shuō)明程序執(zhí)行后，界面直接輸出要求的結(jié)果7. 測(cè)試結(jié)果* *8. 附件#inc

10、lude#include#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define NULL 0typedef int Status;typedef int ElemType;typedef struct LNode ElemType data;struct LNode *next;LNode,*LinkList;Status InitList_L(LinkList &L) / 初始化線性表L=(LinkList )malloc(sizeof(LNode);/L指向頭節(jié)點(diǎn)， 頭節(jié)點(diǎn)數(shù)據(jù)域?yàn)榭誏-next=NULL;return

11、 OK;* */ InitList_LStatus DispList_L(LinkList &L) / 輸出線性表LinkList p=L-next;while(p!=NULL)printf(%c,p-data);p=p-next;return OK; / DispList_LStatus CreateList_L(LinkList &L,ElemType a,int n) / 尾插法建表LinkList s,r;int i;L=(LinkList )malloc(sizeof(LNode);r=L;for(i=0;idata=ai;r-next=s;r=s;* *r-next=NULL;re

12、turn OK;/ CreateList_LStatus ListLength_L(LinkList L) LinkList p=L;int n=0; while(p-next!=NULL) / 求線性表的長(zhǎng)度n+;p=p-next;return(n);/ ListLength_LStatus ListEmpty_L(LinkList L) return(L-next=NULL);/ ListEmpty_L/ 判斷單鏈表是否為空Status DestroyList_L(LinkList &L) LinkList p=L,q=p-next;/ 銷(xiāo)毀線性表* *while(q!=NULL)free

13、(p);p=q;q=p-next;free(p);return OK;/ DestroyList_LStatus GetElem_L(LinkList L, int i, ElemType &e) / L 為帶頭節(jié)點(diǎn)的單鏈表的頭指針。/ 當(dāng)?shù)?i 個(gè)元素存在時(shí)，其值賦給 e 并返回 OK ，否則返回 ERROR int j=0;LinkList p=L; while(jnext;if(p=NULL)return ERROR;* *elsee=p-data;return OK;/ GetElem_LStatus ListInsert_L(LinkList &L, int i, ElemType

14、e) int j=0;LinkList p=L,s;/*/ 插入數(shù)據(jù)元素找到插入節(jié)點(diǎn)的上一個(gè)元素，如果是頭節(jié)點(diǎn)則退出，當(dāng)i=1時(shí)表示頭節(jié)點(diǎn)，i=2 時(shí)，表示第一個(gè)元素*/while(jnext;if(p=NULL)* *return ERROR;elses=(LinkList )malloc(sizeof(LNode);s-data=e;s-next=p-next;p-next=s;return OK;/ ListInsret_LStatus ListDelete_L(LinkList &L, int i, ElemType &e) int j=0;LinkList p=L,q;/ 刪除數(shù)據(jù)元

15、素while(jnext;if(p=NULL)* *return ERROR;elseq=p-next;/q 為要?jiǎng)h除的元素節(jié)點(diǎn)if(q=NULL)return ERROR;e=q-data;/e 為刪除節(jié)點(diǎn)的數(shù)據(jù)區(qū)域p-next=q-next;free(q);return OK;/ ListDelete_Lint LocateElem_L(LinkList L, ElemType e) / 按元素值查找元素LinkList p=L-next;int i=1;while(p!=NULL&p-data!=e)p=p-next;i+;* */ 如果要插入的節(jié)點(diǎn)為頭節(jié)點(diǎn)，則退出if(p=NULL)r

16、eturn ERROR;elsereturn(i);/ LocateElem_Lint main() ElemType e,a5=a,b,c,d,e;LinkList L;printf(1)初始化單鏈表 Ln);InitList_L(L);/ 初始化單鏈表 Lprintf(2)依次采用尾插法插入a,b,c,d,e 元素 n);CreateList_L(L,&a0,5);/ 依次采用尾插入法插入a， b ，c，d ，e 元素printf(3)輸出單鏈表 L： );DispList_L(L);/ 輸出單鏈表 L* *printf(n);printf(4)單鏈表 L 的長(zhǎng)度為： );printf(%

17、d,ListLength_L(L);/ 輸出單鏈表 L 的長(zhǎng)度printf(n);if(ListEmpty_L(L)printf(5)該單鏈表為空 n);elseprintf(5)該單鏈表不為空 n);/ 判斷單鏈表 L 是否為空GetElem_L(L,3,e);printf(6)單鏈表 L 的第三個(gè)元素為： );printf(%c,e);printf(n);/ 輸出單鏈表 L 的第 3 個(gè)元素printf(7)單鏈表 L 中 a 的位置為： );printf(%d,LocateElem_L(L,a);/ 輸出元素 a 的位置printf(n);ListInsert_L(L,4,f);/ 在第 4