線性表的實(shí)現(xiàn)及操作(二).doc

實(shí)驗(yàn)一、線性表的實(shí)現(xiàn)及操作（一）一、實(shí)驗(yàn)?zāi)康牧私夂驼莆站€性表的順序存儲(chǔ)結(jié)構(gòu)；掌握用C語(yǔ)言上機(jī)調(diào)試線性表的基本方法；掌握線性表的基本操作：插入、刪除、查找以及線性表合并等運(yùn)算在順序存儲(chǔ)結(jié)構(gòu)和鏈接存儲(chǔ)結(jié)構(gòu)上的運(yùn)算，以及對(duì)相應(yīng)算法的性能分析。二、實(shí)驗(yàn)要求給定一段程序代碼，程序代碼所完成的功能為：（1）建立一個(gè)線性表；（2）依次輸入數(shù)據(jù)元素1,2,3,4,5,6,7,8,9,10；（3）刪除數(shù)據(jù)元素5；（4）依次顯示當(dāng)前線性表中的數(shù)據(jù)元素。假設(shè)該線性表的數(shù)據(jù)元素個(gè)數(shù)在最壞情況下不會(huì)超過100個(gè)，要求使用順序表。程序中有3處錯(cuò)誤的地方，有標(biāo)識(shí)，屬于邏輯錯(cuò)誤，對(duì)照書中的代碼仔細(xì)分析后，要求同學(xué)們修改錯(cuò)誤的代碼，修改后上機(jī)調(diào)試得到正確的運(yùn)行結(jié)果。(1)需求分析： 這份實(shí)驗(yàn)報(bào)告為所有必做題的實(shí)驗(yàn)報(bào)告。包括實(shí)驗(yàn)一順序表建立、插入、刪除等基本操作，實(shí)驗(yàn)二單鏈表的建立、插入、刪除等基本操作，實(shí)驗(yàn)四二叉樹的基本操作：樹的建立、前序、中序、后序遍歷及實(shí)驗(yàn)六圖的遍歷：深度優(yōu)先和廣度優(yōu)先。這四份基礎(chǔ)性的實(shí)驗(yàn)為改錯(cuò)性質(zhì)，將每個(gè)實(shí)驗(yàn)題目中的錯(cuò)誤改正過來(lái)并通過調(diào)試，有助于對(duì)基礎(chǔ)知識(shí)的理解與強(qiáng)化記憶。(2)概要設(shè)計(jì)： 實(shí)驗(yàn)一為對(duì)順序線性表實(shí)現(xiàn)插入，刪除，查找等基本操作。 需要用到的語(yǔ)句包括void ListInitiate(SeqList *L) int ListInsert(SeqList *L, int i, DataType x) int ListDelete(SeqList *L, int i, DataType *x) int ListGet(SeqList L, int i, DataType *x)等。 實(shí)驗(yàn)二是對(duì)單鏈表進(jìn)行建立，插入，刪除等基本操作。 需要的語(yǔ)句為void ListInitiate(SeqList *L) int ListInsert(SeqList *L, int i, DataType x) int ListDelete(SeqList *L, int i, DataType *x) int ListGet(SeqList L, int i, DataType *x)等。 實(shí)驗(yàn)四為二叉樹，要求建立一個(gè)二叉樹，并實(shí)現(xiàn)前序，中序及后序的遍歷。 所需語(yǔ)句包括void ListInitiate(SeqList *L) int ListInsert(SeqList *L, int i, DataType x) int ListDelete(SeqList *L, int i, DataType *x) int ListGet(SeqList L, int i, DataType *x)等。 實(shí)驗(yàn)六的內(nèi)容是圖的遍歷包括鄰接矩陣和鄰接鏈表兩種方法。三、程序代碼（更正后的代碼）#include #define MaxSize 100typedef int DataType;typedef structDataType listMaxSize;int size; SeqList;void ListInitiate(SeqList *L)/*初始化順序表L*/L-size = 0;/*定義初始數(shù)據(jù)元素個(gè)數(shù)*/ int ListLength(SeqList L)/*返回順序表L的當(dāng)前數(shù)據(jù)元素個(gè)數(shù)*/return L.size;int ListInsert(SeqList *L, int i, DataType x) /*在順序表L的位置i（0 i size）前插入數(shù)據(jù)元素值x*/ /*插入成功返回1，插入失敗返回0*/int j;if(L-size = MaxSize)printf(順序表已滿無(wú)法插入! n);return 0;else if(i L-size )printf(參數(shù)i不合法! n);return 0;else for(j = L-size; j i; j-) L-listj = L-listj;/*為插入做準(zhǔn)備*/L-listi = x;/*插入*/L-size +;/*元素個(gè)數(shù)加1*/return 1;int ListDelete(SeqList *L, int i, DataType *x)/*刪除順序表L中位置i（0 i size - 1）的數(shù)據(jù)元素值并存放到參數(shù)x中*/*刪除成功返回1，刪除失敗返回0*/int j;if(L-size = 0)printf(順序表已空無(wú)數(shù)據(jù)元素可刪! n);return 0;else if(i L-size-1)printf(參數(shù)i不合法);return 0;else/此段程序有一處錯(cuò)誤*x = L-listi;/*保存刪除的元素到參數(shù)x中*/for(j = i +1; j size-1; j+) L-listj = L-listj-1;/*依次前移*/L-size-;/*數(shù)據(jù)元素個(gè)數(shù)減1*/return 1;int ListGet(SeqList L, int i, DataType *x)/*取順序表L中第i個(gè)數(shù)據(jù)元素的值存于x中，成功則返回1，失敗返回0*/if(i L.size-1)printf(參數(shù)i不合法! n);return 0;else*x = L.listi;return 1;void main(void) SeqList myList; int i , x; ListInitiate(&myList); for(i = 0; i 10; i+) ListInsert(&myList, i, i+1); ListDelete(&myList, 4, &x); for(i = 0; i ListLength(myList); i+) ListGet( myList, i, &x); /此段程序有一處錯(cuò)誤printf(%d , x); 測(cè)試結(jié)果：線性表的實(shí)現(xiàn)及操作（二）一、實(shí)驗(yàn)?zāi)康牧私夂驼莆站€性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)；掌握用C語(yǔ)言上機(jī)調(diào)試線性表的基本方法；掌握線性表的基本操作：插入、刪除、查找以及線性表合并等運(yùn)算在順序存儲(chǔ)結(jié)構(gòu)和鏈接存儲(chǔ)結(jié)構(gòu)上的運(yùn)算，以及對(duì)相應(yīng)算法的性能分析。二、實(shí)驗(yàn)要求給定一段程序代碼，程序代碼所完成的功能為：（1）建立一個(gè)線性表；（2）依次輸入數(shù)據(jù)元素1,2,3,4,5,6,7,8,9,10；（3）刪除數(shù)據(jù)元素5；（4）依次顯示當(dāng)前線性表中的數(shù)據(jù)元素。假設(shè)該線性表的數(shù)據(jù)元素個(gè)數(shù)在最壞情況下不會(huì)超過100個(gè)，要求使用單鏈表。程序中有3處錯(cuò)誤的地方，有標(biāo)識(shí)，屬于邏輯錯(cuò)誤，對(duì)照書中的代碼仔細(xì)分析后，要求同學(xué)們修改錯(cuò)誤的代碼，上機(jī)調(diào)試并得到正確的運(yùn)行結(jié)果。三、程序代碼：（更正后的結(jié)果）#include /*該文件包含pringtf()等函數(shù)*/#include /*該文件包含exit()等函數(shù)*/#include /*該文件包含malloc()等函數(shù)*/typedef int DataType;/*定義DataType為int*/typedef struct NodeDataType data;struct Node *next; SLNode;void ListInitiate(SLNode *head)/*初始化*/*如果有內(nèi)存空間，申請(qǐng)頭結(jié)點(diǎn)空間并使頭指針head指向頭結(jié)點(diǎn)*/if(*head = (SLNode *)malloc(sizeof(SLNode) = NULL) exit(1);(*head)-next = NULL;/*置鏈尾標(biāo)記NULL */int ListLength(SLNode *head)SLNode *p = head;/*p指向首元結(jié)點(diǎn)*/int size = 0;/*size初始為0*/while(p-next != NULL)/*循環(huán)計(jì)數(shù)*/p = p-next;size +;return size;int ListInsert(SLNode *head, int i, DataType x)/*在帶頭結(jié)點(diǎn)的單鏈表head的數(shù)據(jù)元素ai（0 i size）結(jié)點(diǎn)前*/*插入一個(gè)存放數(shù)據(jù)元素x的結(jié)點(diǎn)*/SLNode *p, *q;int j;p = head; /*p指向首元結(jié)點(diǎn)*/j = -1;/*j初始為-1*/while(p-next != NULL & j next;j+;if(j != i - 1)printf(插入位置參數(shù)錯(cuò)！);return 0;/*生成新結(jié)點(diǎn)由指針q指示*/if(q = (SLNode *)malloc(sizeof(SLNode) = NULL) exit(1);q-data = x;/此段程序有一處錯(cuò)誤p-next = q-next;/*給指針q-next賦值*/p-next = q;/*給指針p-next重新賦值*/return 1;int ListDelete(SLNode *head, int i, DataType *x)/*刪除帶頭結(jié)點(diǎn)的單鏈表head的數(shù)據(jù)元素ai（0 i size - 1）結(jié)點(diǎn)*/*刪除結(jié)點(diǎn)的數(shù)據(jù)元素域值由x帶回。刪除成功時(shí)返回1；失敗返回0*/SLNode *p, *s;int j;p = head; /*p指向首元結(jié)點(diǎn)*/j = -1;/*j初始為-1*/while(p-next != NULL & p-next-next!= NULL & j next;j+;if(j != i - 1)printf(插入位置參數(shù)錯(cuò)！);return 0;/此段程序有一處錯(cuò)誤s = p-next; /*指針s指向數(shù)據(jù)元素ai結(jié)點(diǎn)*/*x = s-data;/*把指針s所指結(jié)點(diǎn)的數(shù)據(jù)元素域值賦予x*/p-next = s-next;/*把數(shù)據(jù)元素ai結(jié)點(diǎn)從單鏈表中刪除指*/free(s);/*釋放指針s所指結(jié)點(diǎn)的內(nèi)存空間*/return 1;int ListGet(SLNode *head, int i, DataType *x)/*取數(shù)據(jù)元素ai和刪除函數(shù)類同，只是不刪除數(shù)據(jù)元素ai結(jié)點(diǎn)*/SLNode *p;int j;p = head;j = -1;while(p-next != NULL & j next;j+;if(j != i)printf(取元素位置參數(shù)錯(cuò)！);return 0;/此段程序有一處錯(cuò)誤*x = p-data;return 1;void Destroy(SLNode *head)SLNode *p, *p1;p = *head;while(p != NULL)p1 = p;p = p-next;free(p1);*head = NULL;void main(void)SLNode *head;int i , x;ListInitiate(&head);/*初始化*/for(i = 0; i 10; i+)if(ListInsert(head, i, i+1) = 0) /*插入10