【正文】 整的C 語言組成，將實驗內(nèi)容組合成如上所述的三個組成部分，功能清晰明了，其常量定義和常用系統(tǒng)函數(shù)原型聲明的文件“”代碼復用，不需另行建立。3．關于實驗內(nèi)容要完成的操作，一般都以獨立的算法出現(xiàn)，建立一個單鏈表的基本算法文件,將各種不同算法組合在一個文件之中，存儲為一個頭文件如取名為： ，后凡涉及到要使用本文件中的單鏈表算法，一定要在你的文件的前面加上一條include “” 即可，實現(xiàn)的算法函數(shù)，如ListInit_Link、ListInsert_Link、ListDelete_Link、等。四、基本實驗的參考程序（一）線性表的順序存儲結構的定義及其基本操作的參考程序（順序表）(1) 文件1： pubuse. h 是公共使用的常量定義和系統(tǒng)函數(shù)調(diào)用聲明，以后每個實驗中幾乎都涉及到此文件。 /* Status 是函數(shù)的類型,其值是函數(shù)結果狀態(tài)代碼，如OK 等*/typedef int Boolean。 /* 存儲空間基址*/int length。 /* 當前分配的存儲容量(以sizeof(ElemType)為單位) */}SqList。L) /* 算法2. 3 */{ /* 操作結果：構造一個空的順序線性表*/L. elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType))。 /* 存儲分配失敗*/L. length=0。 /* 初始存儲容量*/return OK。L,int i,ElemType e) /* 算法2. 4 */{ /* 初始條件：順序線性表L 已存在，1≤i≤ListLength(L)+1 *//* 操作結果：在L 中第i 個位置之前插入新的數(shù)據(jù)元素e，L 的長度加1 */ElemType *newbase,*q,*p。if(L. length=L. listsize) /* 當前存儲空間已滿,增加分配*/{newbase=(ElemType *)realloc(L. elem,(L. listsize+LISTINCREMENT)*sizeof(ElemType))。 /* 存儲分配失敗*/L. elem=newbase。 /* 增加存儲容量*/}q=L. elem+i1。p=q。*q=e。 /* 表長增1 */return OK。L,int i,ElemType *e) /* 算法2. 5 */{ /* 初始條件：順序線性表L 已存在，1≤i≤ListLength(L) *//* 操作結果：刪除L 的第i 個數(shù)據(jù)元素，并用e 返回其值，L 的長度減1 */ElemType *p,*q。p=L. elem+i1。 /* 被刪除元素的值賦給e */q=L. elem+L. length1。p=q。L. length。}Status ListPrint_Sq(SqList L){ /* 初始條件：順序線性表L 已存在*//* 操作結果：依次對L 的數(shù)據(jù)元素輸出*/int i。for(i=0。i++)printf(%d , L. elem[i])。}Status ListDestroy_Sq(SqList L){/*初始條件：順序線性表L已存在*//*操作結果：銷毀順序線性表L*/free()。=0。return OK。return OK。elsereturn FALSE。e){/*初始條件：順序線性表L已存在, 1≤i≤ListLength(L)*//*操作結果：用e返回L中第i個數(shù)據(jù)元素的值*/if(i1||iL. length) /* i 值不合法*/exit(ERROR)。return OK。 /*實現(xiàn)一組整數(shù)的操作,將int 型特定義為通用的ElemType 類型名*/includeseqlistDef. h /* 采用線性表的動態(tài)分配順序存儲結構定義*/includeseqlistAlgo. h /* 采用順序表的基本算法定義*/void main(){SqList L。int j。/* 首先一定要初始化順序表*/i=ListInit_Sq(L)。j=5。ListPrint_Sq(L)。/* 隨機指定插入點位置，假設在第二個元素前插入新的元素，其值為20 */ListDelete_Sq(L,4,amp。/* 隨機指定刪除點位置，假設對第四個元素進行刪除*/printf(\n The Deleted value is %d,t)。/* 檢驗一下插入和刪除后的結果，輸出表La 的內(nèi)容*/}（二）線性表的鏈式存儲結構的定義及其基本操作的參考程序（鏈表）1． 是線性表的單鏈表存儲結構的定義struct LNode{ElemType data。}。 /* 另一種定義LinkList 的方法*/2． 是單鏈表的基本算法描述/* 以下的算法均是針對帶表頭結點的單鏈表*/Status ListInit_Link(LinkList amp。 /* 產(chǎn)生頭結點,并使L 指向此頭結點*/if(!L) /* 存儲分配失敗*/exit(OVERFLOW)。 /* 指針域為空*/return OK。*//* 操作結果：銷毀線性表L */LinkList q。free(L)。}return OK。*//* 操作結果：將L 重置為空表*/LinkList p,q。 /* p 指向第一個結點*/while(p) /* 沒到表尾*/{q=pnext。p=q。 /* 頭結點指針域為空*/return OK。*//* 操作結果：若L 為空表，則返回TRUE，否則返回FALSE */if(Lnext) /* 非空*/return FALSE。}int ListLength_Link (LinkList L){ /* 初始條件：線性表L 已存在。LinkList p=Lnext。p=pnext。}Status GetElem_Link (LinkList L,int i,ElemType amp。 /* j 為計數(shù)器*/LinkList p=Lnext。amp。j++。e=pdata。}int LocateElem_Link (LinkList L,ElemType e,Status(*pare)(ElemType,ElemType)){ /* 初始條件: 線性表L 已存在,pare()是數(shù)據(jù)元素判定函數(shù)(滿足為1,否則為0) *//* 操作結果: 返回L 中第1 個與e 滿足關系pare()的數(shù)據(jù)元素的位序。LinkList p=Lnext。if(pare(pdata,e)) /* 找到這樣的數(shù)據(jù)元素*/return i。}return 0。LinkList p=L,s。amp。j++。s=(LinkList)malloc(sizeof(struct LNode))。 /* 插入L 中*/snext=pnext。return OK。e) /* ,不改變L */{ /* 在帶頭結點的單鏈線性表L 中，刪除第i 個元素,并由e 返回其值*/int j=0。while(pnextamp。ji1) /* 尋找第i 個結點,并令p 指向其前趨*/{p=pnext。}if(!pnext||ji1) /* 刪除位置不合理*/return ERROR。 /* 刪除并釋放結點*/pnext=qnext。free(q)。}Status ListTraverse_Link (LinkList L){ /* 初始條件：線性表L 已存在*//* 操作結果:依次對L 的每個數(shù)據(jù)元素的值進行輸出*/LinkList p=Lnext。p=pnext。return OK。L,int n) /* */{ /* 逆位序(插在表頭)輸入n 個元素的值，建立帶表頭結構的單鏈線性表L */int i。L=(LinkList)malloc(sizeof(struct LNode))。 /* 先建立一個帶頭結點的單鏈表*/printf(請輸入%d 個數(shù)據(jù)\n,n)。i0。 /* 生成新結點*/scanf(%d,amp。 /* 輸入元素值*/pnext=Lnext。}}3．將測試數(shù)據(jù)和主函數(shù)新定義一個文件,如取名為:./* 、*/includetypedef int ElemType。LinkList La,Lb,Lc。ElemType e。CreateList_Link (Lb,n)。 /* 輸出鏈表Lb 的內(nèi)容*/ListTraverse_Link (Lb)。scanf(%d %d,amp。e)。/* 在Lb 鏈表中第i 個結點處插入一個新的結點，其值為e。 /* 輸出鏈表Lc 的內(nèi)容*/ListTraverse_Link (Lb)。scanf(%d,amp。ListDelete_Link (Lb,i,e)。 /* 輸出被刪結點的內(nèi)容*/printf(Lb=)。}五、實驗環(huán)境和實驗步驟實驗環(huán)境： 利用Visual C++集成開發(fā)環(huán)境進行本實驗的操作。2. 新建工程/Win32 Console Application，選擇輸入位置：如“d:\”，輸入工程的名稱：如“SeqlistDemo”。4. 新建文件/C/C++ Header File，選中“添加到工程的復選按鈕”，輸入文件名“seqlistDef. h”，按“確定”按鈕，在顯示的代碼編輯區(qū)內(nèi)輸入如上的參考程序。6. 新建文件/C++ Source File，選中“添加到工程的復選按鈕”，輸入文件名“seqlistUse. cpp”，按“確定”按鈕，在顯示的代碼編輯區(qū)內(nèi)輸入如上的參考程序。8．按Ctrl+F5 鍵，或工具圖標進行工程的執(zhí)行。，選擇輸入位置：如“d:\”，輸入工程的名稱：如“l(fā)inklistDemo”。4. 新建文件/C/C++ Header File，選中“添加到工程的復選按鈕”，輸入文件名“”，按“確定”按鈕，在顯示的代碼編輯區(qū)內(nèi)輸入如上的參考程序。6. 新建文件/C++ Source File，選中“添加到工程的復選按鈕”，輸入文件名“”，按“確定”按鈕，在顯示的代碼編輯區(qū)內(nèi)輸入如上的參考程序。六、思考題1．寫出動態(tài)生成鏈表的算法或程序。實驗二：棧和隊列的定義及基本操作（必做： 2 學時）一、實驗目的：. 熟練掌握棧和隊列的特點. 掌握棧的定義和基本操作，熟練掌握順序棧的操作及應用. 掌握對列的定義和基本操作，熟練掌握鏈式隊列的操作及應用, 掌握環(huán)形隊列的入隊和出隊等基本操作. 加深對棧結構和隊列結構的理解，逐步培養(yǎng)解決實際問題的編程能力二、實驗內(nèi)容:定義順序棧，完成棧的基本操作：空棧、入棧、出棧、取棧頂元素。定義鏈式隊列，完成隊列的基本操作：入隊和出隊。. 完成一個元素的入棧操作，修改棧頂指針。. 讀取棧頂指針所指向的元素的值。例如：（1348）10=（2504）8N N div 8 N mod 81348 168 4168 21 021 2 52 0 2從中我們可以看出，最先產(chǎn)生的余數(shù)4 是轉換結果的最低位，這正好符合棧的特性即后進先出的特性。以此來實現(xiàn)十進制數(shù)與八進制數(shù)的轉換。（2）利用隊列的鏈式存儲結構,設計一組輸入數(shù)據(jù)（假定為一組整數(shù)），能夠對鏈式隊列進行如下操作：. 初始化一個空隊列，形成一個帶表頭結點的空隊。. 完成一個元素的出隊操作，修改隊頭指針。其他算法的描述省略，參見實現(xiàn)要求說明。.“初始化棧算法”操作結果：構造一個空棧S。.“置空棧算法” 操作結果：把S 置為空棧。.“求棧的長度算法” 操作結果：返回S 的元素個數(shù)，即棧的長度。否則返回ERROR。否則返回ERROR。對鏈式隊列的各項操作一定要編寫成為C（C++）語言函數(shù)，組合成模塊化的形式，每個算法的實現(xiàn)要從時間復雜度和空間復雜度上進行評價。.“銷毀隊列算法”操作結果：銷毀隊列Q(無論空否均可)。.“判隊列是否為空算法” 操作結果：若Q 為空隊列,則返回TRUE,否則返回FALSE。.“取隊頭元素算法” 操作結果：若隊列不空,則用e 返回Q 的隊頭元素,并返回OK,否則返回ERROR。.“出隊算法”操作結果：若隊列不空,刪除Q 的隊頭元素,用e 返回其值,并返回OK,否則返回ERROR。2． 將順序棧的基本操作算法也集中放在一個文件之中。3．將函數(shù)的測試和主函數(shù)組合成一個文件。2．將鏈式隊列的基本操作算法也集中放在一個文件之中。3．將函數(shù)的測試和主函數(shù)組合成一個文件。 /* 在棧構造之前和銷毀之后，base 的值為NULL */SElemType *top。 /* 當前已分配的存儲空間，以元素為單位*/}SqStack。S){ /* 構造一個空棧S */=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType))。 /* 存儲分配失敗*/=。return OK。S){ /* 銷毀棧S，S 不再存在*/free()。=NULL。return OK。S){ /* 把S 置為空棧*/=。}Status StackEmpty(SqStack S){ /* 若棧S 為空棧，則返回TRUE，否則返回FALSE */if(==)return TRUE。}int StackLength(SqStack S){ /* 返回S 的元素個數(shù)，即棧的長度*/retur