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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上實驗一、線性表的實現(xiàn)及操作（一）一、實驗?zāi)康牧私夂驼莆站€性表的順序存儲結(jié)構(gòu)；掌握用C語言上機(jī)調(diào)試線性表的基本方法；掌握線性表的基本操作：插入、刪除、查找以及線性表合并等運算在順序存儲結(jié)構(gòu)和鏈接存儲結(jié)構(gòu)上的運算，以及對相應(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ì)分

2、析后，要求同學(xué)們修改錯誤的代碼，修改后上機(jī)調(diào)試得到正確的運行結(jié)果。(1)需求分析： 這份實驗報告為所有必做題的實驗報告。包括實驗一順序表建立、插入、刪除等基本操作，實驗二單鏈表的建立、插入、刪除等基本操作，實驗四二叉樹的基本操作：樹的建立、前序、中序、后序遍歷及實驗六圖的遍歷：深度優(yōu)先和廣度優(yōu)先。這四份基礎(chǔ)性的實驗為改錯性質(zhì)，將每個實驗題目中的錯誤改正過來并通過調(diào)試，有助于對基礎(chǔ)知識的理解與強化記憶。(2)概要設(shè)計： 實驗一為對順序線性表實現(xiàn)插入，刪除，查找等基本操作。 需要用到的語句包括void ListInitiate(SeqList *L) int ListInsert(SeqList

3、*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, D

4、ataType *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 <stdio.h>#define MaxSi

5、ze 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，插入失

6、敗返回0*/int j;if(L->size >= MaxSize)printf("順序表已滿無法插入! n");return 0;else if(i < 0 | 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 ListDele

7、te(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 < 0 | i > L->size-1)printf("參數(shù)i不合法");return 0;else/此段程序有一處錯誤*x = L->listi;/*保存刪除的元素到參數(shù)x中*/for(j = i +

8、1; j <= L->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 < 0 | i > L.size-1)printf("參數(shù)i不合法! n");return 0;else*x = L.listi;return 1;void main(void) SeqList myLis

9、t; 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)試線性表的基本

10、方法；掌握線性表的基本操作：插入、刪除、查找以及線性表合并等運算在順序存儲結(jié)構(gòu)和鏈接存儲結(jié)構(gòu)上的運算，以及對相應(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)試并得到正確的運行結(jié)果。三、程序代碼：（更正后的結(jié)果）#include <stdio.h&

11、gt;/*該文件包含pringtf()等函數(shù)*/#include <stdlib.h>/*該文件包含exit()等函數(shù)*/#include <malloc.h>/*該文件包含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 *

12、)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 s

13、ize）結(jié)點前*/*插入一個存放數(shù)據(jù)元素x的結(jié)點*/SLNode *p, *q;int j;p = head; /*p指向首元結(jié)點*/j = -1;/*j初始為-1*/while(p->next != NULL && j < i - 1) /*最終讓指針p指向數(shù)據(jù)元素ai-1結(jié)點*/p = p->next;j+;if(j != i - 1)printf("插入位置參數(shù)錯！");return 0;/*生成新結(jié)點由指針q指示*/if(q = (SLNode *)malloc(sizeof(SLNode) = NULL) exit(1);q-&g

14、t;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->

15、;next != NULL && p->next->next!= NULL && j < i - 1) /*最終讓指針p指向數(shù)據(jù)元素ai-1結(jié)點*/p = p->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(

16、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 < i)p = p->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個數(shù)據(jù)元素*/printf("錯誤! n");return;i