【文章內容簡介】 第一個結點－＞ q 將 q 插入到 Lc 的尾部 將 q 插入到 Lc 的尾部 取 La 的第一個結點－＞ pa 取 Lb 的第一個結點－＞ pb N La 空？ Y 將 La 插入到 Lc 后面 將 Lb 插入到 Lc 后面 釋放 La 、 Lb 的頭結點 結束 Status MergeList_L(LinkList La,LinkList Lb,LinkList*Lc,int(*pare) (ElemType,ElemType)) { Link ha,hb,pa,pb,q。 ElemType a,b。 if(!InitList(Lc)) return ERROR。 ha=GetHead(La)。 hb=GetHead(Lb)。 pa=NextPos(ha)。 pb=NextPos(hb)。 while(!ListEmpty(La)amp。amp。!ListEmpty(Lb)) { a=GetCurElem(pa)。 b=GetCurElem(pb)。 if(pare(a,b)=0) { DelFirst(amp。La,ha,amp。q)。 InsFirst(Lc,(*Lc).tail,q)。 pa=NextPos(ha)。 } } else { DelFirst(amp。Lb,hb,amp。q)。 InsFirst(Lc,(*Lc).tail,q)。 pb=NextPos(hb)。 } } if(!ListEmpty(La)) Append(Lc,pa)。 else Append(Lc,pb)。 FreeNode(amp。ha)。 FreeNode(amp。hb)。 return OK。 } 主函數 ?在輸入 La和 Lb兩個線性表的數據元素時，要求按非遞減的順序輸入。請讀者嘗試添加相應的控制部分，判斷用戶輸入的線性表是否有序，或者進行初始輸入排序處理，這時需要在輸入數據時對ListInsert_L(amp。La,i,inputdata)中的 i進行定位。 ?本實驗實現的是將線性鏈表 La和 Lb合并成一個新的線性鏈表 Lc。假設需要將線性鏈表 Lb按值非遞減順序合并到 La中，請讀者考慮應如何實現。 進入 TC main() { LinkList La,Lb,Lc。 int len_a,len_b。 int i, inputdata。 clrscr()。 InitList(amp。La)。 printf(Please input LinkListA length:)。 scanf(%d,amp。len_a)。 printf(LinkListA elements:)。 for(i=1。i=len_a。i++) { scanf(%d,amp。inputdata)。 ListInsert_L(amp。La,i,inputdata)。 } ListTraverse(La,print)。 printf(Please input LinkListB length:)。 scanf(%d,amp。len_b)。 printf(LinkListB elements:)。 InitList(amp。Lb)。 for(i=1。i=len_b。i++) { scanf(%d,amp。inputdata)。 ListInsert_L(amp。Lb,i,inputdata)。 } ListTraverse(Lb,print)。 InitList(amp。Lc)。 MergeList_L(La,Lb,amp。Lc,pare)。 printf(Lc=)。 ListTraverse(Lc,print)。 DestroyList(amp。Lc)。 } 合并線性表執(zhí)行結果 實驗三：實驗目的及要求 ?理解特殊的線性結構順序棧的抽象數據類型的定義，及在 C語言環(huán)境中的表示方法。 ?理解順序棧的基本操作的算法，及在 C語言環(huán)境中一些主要基本操作的實現。 ?在 C語言環(huán)境下實現順序棧的應用操作： ?用棧實現十進制數轉換成八進制數。 ?利用棧實現一位數的加減乘除的表達式求解。 實驗內容 經過對實驗目的及要求的分析，本實驗仍然采用首先描述棧的基本操作集函數，然后分別在二個應用操作中使用基本操作集函數來實現。 由于棧是一種特殊的線性結構，僅在棧頂進行插入和刪除操作，即棧具有后進先出的特點，故其操作比一般的線性表更為容易，所以在本實驗中有關棧的基本操作集的實現都比較簡單，沒有做過多的說明，而是在數制轉換和表達式求解的應用操作中加入了更多的編程技巧，使讀者通過本實驗不僅了解棧這種特殊結構的線性表，而且掌握利用?？蓪崿F很多的應用，尤其是在實現表達式求解時用到了兩個順序棧，并且加入了運算符的優(yōu)先關系的判斷等，實現稍有難度。 在程序 ，只包含了數制轉換和一位數的表達式求解，多位數的表達式求解思想與一位數表達式求解思想一致，但需要添加多位數的接收處理，請讀者自行編寫代碼。 程序名為： 。 實驗內容 ? 定義順序棧結構 ? 初始化一個空棧 ? 數據元素入棧 ? 數據元素出棧 ? 判斷一個棧是否為空 ? 銷毀一個棧 ? 取棧頂元素 ? 定義算符優(yōu)先關系 ? 判斷輸入元素是否為算符 ? 計算兩個操作數 ? 十進制數轉換成八進制 ? 表達式求解 主函數 退出 基本操作集函數 應用函數 定義順序棧的結構 define STACK_INIT_SIZE 10 define STACKINCREMENT 2 define TRUE 1 define FALSE 0 define OK 1 define ERROR 0 define OVERFLOW 2 typedef int SElemType。 typedef int Status。 typedef struct SqStack { SElemType *base。 SElemType *top。 int stacksize。 }SqStack。 Status InitStack(SqStack *S) { (*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType))。 if(!(*S).base) exit(OVERFLOW)。 (*S).top=(*S).base。 (*S).stacksize=STACK_INIT_SIZE。 return OK。 } 初始化一個空棧 數據元素入棧 Status Push(SqStack *S,SElemType e) { if((*S).top(*S).base=(*S).stacksize) { (*S).base=(SElemType*)realloc ((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType))。 if(!(*S).base) exit(OVERFLOW)。 (*S).top=(*S).base+(*S).stacksize。 (*S).stacksize+=STACKINCREMENT。 } *((*S).top)++=e。 return OK。 } 數據元素出棧 Status Pop(SqStack *S,SElemType *e) { if((*S).top==(*S).base) return ERROR。 *e=*(*S).top。 return OK。 } 判斷一個棧是否為空 Status StackEmpty(SqStack S) { if(==) return TRUE。 else return FALSE。 } 銷毀一個棧 Status DestroyStack(SqStack *S) { free((*S).base)。 (*S).base=NULL。 (*S).top=NULL。 (*S).stacksize=0。 return OK。 } 十進制數轉換成八進制 本函數實現了無符號十進制數和八進制數間的轉換功能。 如輸入的是負數，由于系統(tǒng)使用補碼表示負數，會自動將其進行補碼轉換，再通過本函數對其實現八進制轉換。如，當輸入 1時，結果顯示 65535。 如果需要將十進制轉換成十六進制應該如何修改本函數，方法有兩種，第一種，在入棧時，存入十六進制數，第二種，在出棧時，輸出十六進制數。請讀者自己編寫代碼。 void conversion() { SqStack s。 unsigned n。 SElemType e。 InitStack(amp。s)。 printf(Please input a decimal number:)。 scanf(%u,amp。n)。 while(n) { Push(amp。s,n%8)。 n=n/8。 } printf(The corresponding octal number is:)。 while(!StackEmpty(s)) { Pop(amp。s,amp。e)。 printf(%d,e)。 } printf(\n)。 DestroyStack(amp。s)。 } 取棧頂的數據元素 Status GetTop(SqStack S,SElemType *e) { if() { *e=*()。 return OK。 } else return ERROR。 } 按照四則運算法則定義的運算符（包括：＋、－、＊、/、（）、＃）運算的優(yōu)先關系，即按照表 運算符與運算符棧中的運算符的優(yōu)先關系。 表 義的，也就是本函數的運行結果。如果讀者希望在運算中再加入其他運算符（如乘方等），則必須先定義它們的關系，豐富表 ，同時在函數中添加所加入的運算符的比較內容。其中 θ 1為棧頂元素， θ 2為輸入元素。定義“?！边\算符為輸入表達式時的結束符及存放運算符的棧的棧底元素。 本函數不包含任何數據結構的內容，僅是在輸入表達式的過程中，按照表 的運算符的關系 (、 、 =)。因一個表達式包含多個運算符，故將此部分做為一個獨立的函數進行編寫。 表 運算符間的優(yōu)先關系 SElemType Precede(SElemType t1,SElemType t2) { SElemType f。 switch(t2) { case 39。+39。: case 39。39。:if(t1==39。(39