實驗名稱：線性表的存儲結(jié)構(gòu)定義及基本操作

班級 姓名 學(xué)號 實驗日期： 實驗機時：2 學(xué)時 實驗成績：

-------------------------------------------------------------------------------

一.實驗?zāi)康模?p>1. 掌握線性表的邏輯特征

2. 掌握線性表順序存儲結(jié)構(gòu)的特點，熟練掌握順序表的基本運算 3. 熟練掌握線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)定義及基本操作 4. 理解循環(huán)鏈表和雙鏈表的特點和基本運算

5. 加深對棧結(jié)構(gòu)的理解，培養(yǎng)解決實際問題的編程能力。

6. 加深對順序存儲數(shù)據(jù)結(jié)構(gòu)的理解和鏈?zhǔn)酱鎯?shù)據(jù)結(jié)構(gòu)的理解，逐步培養(yǎng)解決

實際問題的編程能力 二.實驗內(nèi)容： （1）基本實驗內(nèi)容：

建立順序表，完成順序表的基本操作：初始化、插入、刪除、逆轉(zhuǎn)、輸出、銷毀, 置空表、求表長、查找元素、判線性表是否為空；

建立單鏈表，完成鏈表（帶表頭結(jié)點）的基本操作：建立鏈表、插入、刪除、查找、輸出；其它基本操作還有銷毀鏈表、將鏈表置為空表、求鏈表的長度、獲取某位置結(jié)點的內(nèi)容、搜索結(jié)點。 （2）擴展實驗內(nèi)容：

查前驅(qū)元素、查后繼元素、順序表合并，兩個有序單鏈表的合并操作等。 三.程序及注釋： 1. 順序表：

#include #include #define TRUE 1

#define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef int status ; typedef int ElemType ; typedef struct{ ElemType *elem;

int length,listsize;}SqList; status InitList(SqList &L)//初始化

{L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!L.elem) exit(OVERFLOW); L.listsize=LIST_INIT_SIZE; L.length=0; return OK;}

status Build(SqList &L)//建立表 {int i,n;

printf(\"請輸入元素個數(shù)n和n個元素\\n\"); scanf(\"%d\

if(n>LIST_INIT_SIZE)//如果n大于當(dāng)前空間

{L.elem=(ElemType *)realloc(L.elem,(n+LISTINCREMENT)*sizeof(ElemType)); if(!L.elem) exit(OVERFLOW); L.listsize=n+LISTINCREMENT;} for(i=0;ivoid Print(SqList &L)//輸出表中元素和長度 {int i;

for(i=0;iprintf(\"\\n長度為:%d\\n\\n\void Tips()//提示函數(shù)

{printf(\"請選擇你的想要的操作：\\n\"); printf(\"<1> 輸出順序表及順序表的長度\\n\"); printf(\"<2> 刪除值為x的結(jié)點\\n\"); printf(\"<3> 刪除給定位置i的結(jié)點\\n\"); printf(\"<4> 將順序表逆置\\n\"); printf(\"<5> 將順序表按升序排序\\n\");

printf(\"<6> 將x插入到順序表的適當(dāng)位置上\\n\"); printf(\"<7> 將兩個有序表合并\\n\"); printf(\"<0> 退出\\n\\n\");}

status ListDelete1(SqList &L,int x)//刪除值為X的元素 {int i;

for(i=0;ifor(i++;istatus ListDelete2(SqList &L,int x)//刪除第X個元素 {int i;

if(x<0||x>=L.length) return ERROR;

for(i=x+1;ivoid Inverse(SqList &L)//逆置函數(shù) {int i,t;

for(i=0;i*(L.elem+i)=*(L.elem+L.length-i-1); *(L.elem+L.length-i-1)=t;}} void Sort(SqList &L)//冒泡排序（升序） {int i,j,t;

for(i=1;i*(L.elem+j+1)) {t=*(L.elem+j);

*(L.elem+j)=*(L.elem+j+1); *(L.elem+j+1)=t;}} printf(\"已按升序排列\(zhòng)\n\\n\");}

status ListInsert(SqList &L,int x)//將X插入，使仍然有序 {int i,k;

if(L.length>=L.listsize)

{L.elem=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType)); if(!L.elem) exit(OVERFLOW); L.listsize+=LISTINCREMENT;} for(i=0;iif(x<*(L.elem+i)) break; k=i;

for(i=L.length;i>k;i--) *(L.elem+i)=*(L.elem+i-1); *(L.elem+k)=x; L.length++; return OK;}

status Merger(SqList &L,SqList &Lb)//合并兩個線性表 {int i,j,k; SqList Lc; InitList(Lc);

if(Lc.listsize{Lc.elem=(ElemType *)realloc(Lc.elem,(L.length+Lb.length+LISTINCREMENT)*sizeof(ElemType)); if(!L.elem) exit(OVERFLOW);

Lc.listsize=L.length+Lb.length+LISTINCREMENT;} i=j=k=0;

while(i{*(Lc.elem+k)=*(Lb.elem+j); k++;j++;}} while(i{*(Lc.elem+k)=*(L.elem+i); k++;i++;} while(j{*(Lc.elem+k)=*(Lb.elem+j); k++;j++;}

Lc.length=L.length+Lb.length; L=Lc; return OK;} int main() {int op,x,flag; SqList L,Lb; InitList(L); Build(L); Tips();

scanf(\"%d\ while(op) {switch(op) {case 1: Print(L);

break; case 2:

printf(\"請輸入要刪除的數(shù)據(jù)X:\\n\"); scanf(\"%d\ flag=ListDelete1(L,x); if(flag)

printf(\"刪除成功!!\\n\\n\"); else

printf(\"元素不存在,刪除失敗!!\\n\\n\"); break; case 3:

printf(\"請輸入要刪除的位置i:\\n\"); scanf(\"%d\

flag=ListDelete2(L,x-1);//第i個元素對應(yīng)的下標(biāo)為i-1 if(flag)

printf(\"刪除成功!!\\n\\n\"); else

printf(\"元素不存在,刪除失敗!!\\n\\n\"); break; case 4: Inverse(L); break; case 5: Sort(L); break; case 6:

printf(\"請輸入要插入的數(shù)據(jù)X:\\n\"); scanf(\"%d\

flag=ListInsert(L,x); if(flag)

printf(\"插入成功!!\\n\\n\"); else

printf(\"插入失敗!!\\n\\n\"); break; case 7:

printf(\"請輸入Lb的內(nèi)容:\\n\"); InitList(Lb); Build(Lb); flag=Merger(L,Lb); if(flag)

printf(\"合并成功!!\\n\\n\"); break;} Tips();

scanf(\"%d\

return 0;}

2. 單鏈表

typedef int ElementType; #ifndef _List_H #define _List_H struct Node;

typedef struct Node *PtrToNode; typedef PtrToNode List; typedef PtrToNode Position; List MakeEmpty( List L ); int IsEmpty( List L );

int IsLast( Position P, List L ); Position Find( ElementType X, List L ); void Delete( ElementType X, List L );

Position FindPrevious( ElementType X, List L ); void Insert( ElementType X, List L, Position P ); void DeleteList( List L ); Position Header( List L ); Position First( List L ); Position Advance( Position P ); ElementType Retrieve( Position P ); #endif

#include #include

#define Error( Str ) FatalError( Str )

#define FatalError( Str ) fprintf( stderr, \"%s\\n\struct Node

{ElementType Element; Position Next;};

List MakeEmpty( List L ) //創(chuàng)建空鏈表 {if( L != NULL ) DeleteList( L );

L = malloc( sizeof( struct Node ) ); if( L == NULL )

FatalError( \"Out of memory!\" ); L->Next = NULL; return L;}

int IsEmpty( List L )//判斷鏈表是否為空 {return L->Next == NULL;} int IsLast( Position P, List L ) {return P->Next == NULL;}

Position Find( ElementType X, List L )//精確查找函數(shù) {Position P;

int n=1; P = L->Next;

while( P != NULL && P->Element != X ) {P = P->Next;n++;} if(P==NULL)

printf(\"查找的成員不存在??！\\n\\n\"); else

printf(\"查找的成員位于鏈表第%d位\\n\\n\void Delete( ElementType X, List L )//精確刪除函數(shù) {Position P, TmpCell; P = FindPrevious( X, L ); if( !IsLast( P, L ) ) {TmpCell=P->Next;

P->Next=TmpCell->Next;

free( TmpCell );}}

Position FindPrevious( ElementType X, List L )//前驅(qū)查找函數(shù) {Position P; P = L;

while( P->Next != NULL && P->Next->Element != X ) P = P->Next; return P;}

void Insert( ElementType X, List L, Position P )//元素插入函數(shù) {Position TmpCell;

TmpCell = malloc( sizeof( struct Node ) ); if( TmpCell == NULL )

FatalError( \"Out of space\" ); TmpCell->Element = X; TmpCell->Next = P->Next; P->Next = TmpCell;}

void DeleteList( List L )//清空鏈表函數(shù) {Position P, Tmp; P = L->Next; L->Next = NULL; while( P != NULL ) {Tmp = P->Next; free( P ); P = Tmp;} if(IsEmpty(L))

printf(\"鏈表清空成功！\\n\\n\");}

Position Header( List L )//表頭調(diào)用函數(shù) {return L;}

Position First( List L )//首元素調(diào)用函數(shù) {return L->Next;}

Position Advance( Position P )//元素遞進(jìn)函數(shù)

{return P->Next;}

void show(List L)//顯示鏈表函數(shù) {if(!IsEmpty(L)) {Position p; p=First(L);

printf(\"當(dāng)前鏈表成員如下：\\n\"); while(p!=NULL)

{printf(\"%d \

if(Advance(p)) p=Advance(p); else

{printf(\"\\n\\n\");break;}}}

else

printf(\"當(dāng)前鏈表為空??！\\n\\n\"); } void join(List L) //插入函數(shù)調(diào)用函數(shù) {int x,n,i;

Position p=Header(L);

printf(\"請輸入需要插入的成員：\\n\"); scanf(\"%d\

printf(\"需要將成員插入到第幾位呢？\\n\"); scanf(\"%d\ for(i=1;iNext;} Insert(x,L,p); show(L);}

void find(List L)//查找函數(shù)調(diào)用函數(shù) {printf(\"請輸入需要查找的成員：\\n\"); int x;

scanf(\"%d\ Find(x,L);}

void count(List L)//鏈表長度統(tǒng)計函數(shù) {Position p; p=First(L); int n=0; while(p!=NULL) {n++;

if(Advance(p)) p=Advance(p); else break;}

printf(\"當(dāng)前鏈表長度為：%d\\n\\n\void direction(List L)//位置訪問函數(shù) {int n,i;

Position p=Header(L);

printf(\"請輸入n的值：\\n\"); scanf(\"%d\ for(i=0;iNext;}

printf(\"第%d位成員為：%d\\n\\n\void change(List L)//修改元素函數(shù) {printf(\"請輸入n的值：\\n\"); int x,n,i; scanf(\"%d\

printf(\"請輸入修改后的值：\\n\"); scanf(\"%d\ Position p=Header(L); for(i=0;iNext;} p->Element=x; show(L);}

void deletion(List L)//刪除函數(shù)調(diào)用函數(shù) {printf(\"你要刪除的成員是：\\n\"); int x;

scanf(\"%d\ Delete(x,L); show(L);} void main() { List L;

L=MakeEmpty(NULL);

printf(\"請輸入需要插入的成員個數(shù)：\\n\"); int n;

scanf(\"%d\

printf(\"請輸入需要插入的成員以空格隔開：\\n\"); int i;

Position p; p=Header(L); for(i=0;iscanf(\"%d\Insert(x,L,p); p=Advance(p);}

show(L);

printf(\"請選擇需要進(jìn)行的操作：\\n 1.計算鏈表長度\\n 2.取第n個位置成員\\n 3.修改第n個位置成員\\n 4.在第n位插入新成員\\n 5.刪除成員\\n 6.搜索成員\\n 7.銷毀鏈表\\n 8.退出\\n你輸入的選項是：\"); scanf(\"%d\

while(n!=8) {switch(n)

{case 1:count(L);break;

case 2:direction(L);break; case 3:change(L);break; case 4:join(L);break; case 5:deletion(L);break; case 6:find(L);break; case 7:DeleteList(L);break;}

printf(\"請選擇需要進(jìn)行的操作：\\n 1.計算鏈表長度\\n 2.取第n個位置成員\\n 3.修改第n個位置成員\\n 4.在第n位插

入新成員\\n 5.刪除成員\\n 6.搜索成員\\n 7.銷毀鏈表\\n 8.退出\\n你輸入的選項是：\"); scanf(\"%d\

四.運行結(jié)果： 1.順序表：

3. 單鏈表：

五.實驗心得：

通過這次寫實驗報告，我深切的理解了這門課的本質(zhì)。剛開始學(xué)這門課時，當(dāng)時還不清楚這門課程的目的，現(xiàn)在，我真正的理解了：數(shù)據(jù)結(jié)構(gòu)像是身體的骨骼，而C是填充這骨骼的肉體，二者相結(jié)合才能使整個程序更加完整，健全。數(shù)據(jù)結(jié)構(gòu)是個框架，模型，抽象數(shù)據(jù)類型中列舉了各種操作，而所用的C語言，將各種操作描述出來構(gòu)成算法。數(shù)據(jù)結(jié)構(gòu)+算法=程序設(shè)計。 這次的實驗報告，讓我受益匪淺，不僅有知識方面的，還有生活和精神上的?？傊視^續(xù)我的興趣編程，相信在編程的過程中，能不斷的提高自己。