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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上實(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ì)超過(guò)100個(gè)，要求使用順序表。程序中有3處錯(cuò)誤的地方，有標(biāo)識(shí)，屬于邏輯錯(cuò)誤，對(duì)照書(shū)中的代碼仔細(xì)分

2、析后，要求同學(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ù)的基本操作：樹(shù)的建立、前序、中序、后序遍歷及實(shí)驗(yàn)六圖的遍歷：深度優(yōu)先和廣度優(yōu)先。這四份基礎(chǔ)性的實(shí)驗(yàn)為改錯(cuò)性質(zhì)，將每個(gè)實(shí)驗(yàn)題目中的錯(cuò)誤改正過(guò)來(lái)并通過(guò)調(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

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

4、ataType *x)等。 實(shí)驗(yàn)四為二叉樹(shù)，要求建立一個(gè)二叉樹(shù)，并實(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 <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ù)元素個(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，插入失

6、敗返回0*/int j;if(L->size >= MaxSize)printf("順序表已滿無(wú)法插入! 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 +;/*元素個(gè)數(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("順序表已空無(wú)數(shù)據(jù)元素可刪! n");return 0;else if(i < 0 | i > L->size-1)printf("參數(shù)i不合法");return 0;else/此段程序有一處錯(cuò)誤*x = L->listi;/*保存刪除的元素到參數(shù)x中*/for(j = i +

8、1; j <= L->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 < 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); /此段程序有一處錯(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)試線性表的基本

10、方法；掌握線性表的基本操作：插入、刪除、查找以及線性表合并等運(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ì)超過(guò)100個(gè)，要求使用單鏈表。程序中有3處錯(cuò)誤的地方，有標(biāo)識(shí)，屬于邏輯錯(cuò)誤，對(duì)照書(shū)中的代碼仔細(xì)分析后，要求同學(xué)們修改錯(cuò)誤的代碼，上機(jī)調(diào)試并得到正確的運(yùn)行結(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)存空間，申請(qǐng)頭結(jié)點(diǎn)空間并使頭指針head指向頭結(jié)點(diǎn)*/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é)點(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 s

13、ize）結(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 < i - 1) /*最終讓指針p指向數(shù)據(jù)元素ai-1結(jié)點(diǎn)*/p = p->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-&g

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

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

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