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

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