線性表的基本操作教案

1、實驗一 線性表的基本操作一、實驗?zāi)康膶W(xué)習(xí)掌握線性表的順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)。設(shè)計順序表的創(chuàng)建、插入、刪除等基本操作，設(shè)計單鏈表的建立、插入、刪除等基本操作。二、實驗內(nèi)容1.順序表的實踐（1）順序表的創(chuàng)建：基于順序表的動態(tài)分配存儲結(jié)構(gòu)，創(chuàng)建一個順序表S，初始狀態(tài)S=(1，2，3，4，5)。（2）順序表的遍歷：依次輸出順序表的每個數(shù)據(jù)元素。（3）順序表的插入：在順序表S=(1，2，3，4，5)的數(shù)據(jù)元素4和5之間插入一個值為9的數(shù)據(jù)元素。（4）順序表的刪除：順序表S=(1，2，3，4，9，5)中刪除指定位置（i=3）的數(shù)據(jù)元素3。（5）順序表的按值查找：查找順序表S中第1個值等于4的數(shù)據(jù)元素位

2、序。（6）順序表的清空：釋放順序表的存儲空間。2.單鏈表的實踐（1）單鏈表的創(chuàng)建：創(chuàng)建一個包括頭結(jié)點(diǎn)和4個元素結(jié)點(diǎn)的單鏈表L=（5，4，2，1）。（2）單鏈表的遍歷：依次輸出順序表的每個數(shù)據(jù)元素。（3）單鏈表的取值：輸出單鏈表中第i個（i=2）數(shù)據(jù)元素的值。（4）單鏈表的插入：在已建好的單鏈表的指定位置（i=3）插入一個結(jié)點(diǎn)3。（5）單鏈表的刪除：在一個包括頭結(jié)點(diǎn)和5個結(jié)點(diǎn)的單鏈表L=（5，4，3，2，1）中，刪除指定位置（i=2）的結(jié)點(diǎn)，實現(xiàn)的基本操作。（6）求單鏈表的表長：輸出單鏈表的所有元素和表長。（7）單鏈表的判空：判斷單鏈表是否為空表。（8）單鏈表的清空：釋放單鏈表的存儲空間。三、程

3、序源代碼1.線性表的基本操作#include #includeusing namespace std;#define OK 1#define OVERFLOW -2#define ERROR 0#define LIST_INIT_SIZE 100#define LISTINCEREMENT 10typedef int Status;typedef int Elemtype;typedef Elemtype *Triplet;typedef struct /定義結(jié)構(gòu)體類型：順序表Elemtype *elem;int length;int listsize; Sqlist;Status Initl

4、ist( Sqlist &L ) /int n,i;L.elem = (Elemtype*) malloc (LIST_INIT_SIZE*sizeof(Elemtype);if(!L.elem) return(OVERFLOW);cout n;for(int i=0; i L.elemi;L.length = n;L.listsize = LIST_INIT_SIZE;return OK;Status TraverList(Sqlist L) for(int i=0; iL.length; i+) cout L.elemi ;cout endl;Status ListInsert (Sqli

5、st &L,int i,Elemtype e) /插入Elemtype *newbase,*p,*q;if(iL.length+1) return ERROR;/i不合法if(L.length = L.listsize) /需要重新分配存儲空間newbase = (Elemtype *) realloc(L.elem,(L.listsize + LISTINCEREMENT)*sizeof (Elemtype);if(!newbase) exit(OVERFLOW);/分配失敗L.elem = newbase;L.listsize += LISTINCEREMENT;q = &(L.elemi

6、-1);for(p=&(L.elemL.length-1); p=q; -p)*(p+1)=*p;*q=e;+L.length;return OK;Status ListDelete(Sqlist &L,int i,Elemtype &e) /刪除Elemtype *p,*q;if(iL.length) return ERROR;p=&(L.elemi-1);e=*p;q=L.elem+L.length-1;for(+p; p=q; +p)*(p-1)=*p;-L.length;return OK;Status LocateElem(Sqlist L,Elemtype &e) /查找int i

7、;Elemtype *p;i=1;p=L.elem;while(i=L.length&*(p+)!=e) +i;if(i=L.length) return i;else return 0;Status ClearList(Sqlist &L) free(L.elem);cout 該表已被清空！;return OK;int main() Sqlist L;int i,z;Elemtype e;if(Initlist(L)=OVERFLOW) cout endl OVERFLOW;return 0;TraverList(L);while(1) cout - endl;cout 選擇要執(zhí)行的基本操作

8、： endl 1:插入元素 endl 2.刪除元素 endl 3.查找元素 endl 4.退出 z;switch(z) case 1:cout 輸入要插入元素的位置和值： i e;if(ListInsert(L,i,e)=OK)TraverList(L);elsecout 插入的位置不合法。 endl;break;case 2:cout 輸入要刪除元素的位置： i;if(ListDelete(L,i,e)=OK) TraverList(L);cout 刪除的元素值為： e endl; else cout 刪除的位置不合法。 endl;break;case 3:cout 輸入要查找元素的值： e

9、;if(LocateElem(L,e)cout 該元素的位置是第 LocateElem(L,e) 位 endl; else cout 該元素不存在！ endl;case 4:cout 操作結(jié)束 endl;ClearList(L);exit(0);default:cout 選擇有誤，請重新選擇！ endl;2.鏈表的基本操作#include#include#include#include#include#define OVERFLOW -2#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define INFEASIBLE -1#d

10、efine LIST_INIT_SIZE 100#define LISTINCREMENT 10using namespace std;typedef int Status;typedef int ElemType;typedef struct LNode ElemType data;struct LNode *next; LNode,*LinkList; /LNode結(jié)構(gòu)體類型別名，LinkList結(jié)構(gòu)體指針別名Status InitLNode(LinkList &L) /初始化鏈表，n個元素，線性表長度為nint n,i;LinkList p,r;L=(LinkList)malloc(si

11、zeof(LNode);/動態(tài)申請一個結(jié)點(diǎn)（頭節(jié)點(diǎn)）if(!L)return OVERFLOW;L-next=NULL;r=L;cout n;for(i=0; i p-data;r-next=p;r=p;r-next=NULL;return OK;/InitLNodevoid ListDisp(LinkList L) /遍歷單鏈表，依次輸出各元素LinkList p;p=L-next;cout endl The LinkList L:endl;/依次訪問L的每一個結(jié)點(diǎn)，直到結(jié)尾while(p!=NULL) cout data next;cout next;/p指針初值：NULL取值指向第一個元

12、素的值while(p&jnext;+j;/若p為空未找到，ji（i值不合法）,取值錯誤返回ERRORif(!p|ji)return ERROR;e=p-data;return OK;/GetElemStatus ListInsert(LinkList &L,int i,ElemType e) /往單鏈表L中第i個位置之前插入新的元素eLinkList p,s;int j=0;p=L;while(p&jnext;+j;if(!p|ji-1)return ERROR;s=(LinkList)malloc(sizeof(LNode);s-data=e;s-next=p-next;/1p-next=s

13、;/2,順序不能變return OK;/ListInsertStatus ListInse(LinkList &L,int i,ElemType &e) /刪除單鏈表L中第i個元素，用e返回其值LinkList p,q;int j;p=L;j=0;while(p-next&jnext;+j;if(!(p-next)|ji-1)return ERROR;q=p-next;p-next=q-next;e=q-data;free(q);return OK;/ListInseStatus ListLength(LinkList L) /求鏈表長度LinkList p;int i=0;p=L-next;

14、while(p!=NULL) i+;p=p-next;return i;/ListLengthStatus LNodeEmpty(LinkList L) /若單鏈表L為空表返回TRUE，否則返回FALSEif(L-next=NULL)return TRUE;elsereturn FALSE;/LNodeEmptyStatus ClearList(LinkList &L) /清空單鏈表LinkList p;p=L-next;while(p!=NULL) L-next=p-next;free(p);p=L-next;/ClearList;int main() LinkList L;int i,s;

15、ElemType e;InitLNode(L);if(ListLength(L)=0) ListDisp(L);cout 表為空。 endl;return 0;while(1) cout - endl;cout 選擇操作： endl 1:輸出某個元素的值； endl 2.在某個元素之前插入一個元素; endl 3.刪除某個元素; endl 4.輸出鏈表中的元素及其長度; endl 5.退出 s;switch(s) case 1:cout i;if(!GetElem(L,i,e)cout 該元素不存在！ endl;elsecout 第 i 個元素的值是： e endl;break;case 2:

16、cout i e;cout 當(dāng)前鏈表的所有元素為： endl;if(ListInsert(L,i,e)=OK)ListDisp(L);elsecout 插入的位置不合法。 endl;break;case 3:cout i;if(ListInse(L,i,e)=OK) cout 刪除的元素值為： e endl;cout 當(dāng)前鏈表的所有元素為： endl;ListDisp(L); else cout 刪除的位置不合法。 endl;break;case 4:cout 當(dāng)前鏈表的所有元素為： endl;ListDisp(L);cout 鏈表的長度為： ListLength(L) endl;break;case 5:cout 操作結(jié)束! 該表已被清空！ endl;ClearList(L);exit(0);default:cout 選擇有誤，請重新選擇！ endl;四、程序運(yùn)行結(jié)果1、順序表的實踐，運(yùn)行結(jié)果如下：2、單鏈表的實踐，運(yùn)行結(jié)果如下：五、實驗心得本次的實驗我經(jīng)過數(shù)個小時的練習(xí)，學(xué)會了一些語法和一些特殊結(jié)構(gòu)，對線性鏈表和順序鏈表更加熟悉了，主要收獲如下：對于線性鏈表和順序表都屬于線性表問題，但是線性鏈表的插入刪除比順序表要簡單，方便。順序表的查