【文章內(nèi)容簡介】 第一個結(jié)點(diǎn)－＞ q 將 q 插入到 Lc 的尾部 將 q 插入到 Lc 的尾部 取 La 的第一個結(jié)點(diǎn)－＞ pa 取 Lb 的第一個結(jié)點(diǎn)－＞ pb N La 空？ Y 將 La 插入到 Lc 后面 將 Lb 插入到 Lc 后面 釋放 La 、 Lb 的頭結(jié)點(diǎn) 結(jié)束 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。 } 主函數(shù) ?在輸入 La和 Lb兩個線性表的數(shù)據(jù)元素時，要求按非遞減的順序輸入。請讀者嘗試添加相應(yīng)的控制部分，判斷用戶輸入的線性表是否有序，或者進(jìn)行初始輸入排序處理，這時需要在輸入數(shù)據(jù)時對ListInsert_L(amp。La,i,inputdata)中的 i進(jìn)行定位。 ?本實(shí)驗(yàn)實(shí)現(xiàn)的是將線性鏈表 La和 Lb合并成一個新的線性鏈表 Lc。假設(shè)需要將線性鏈表 Lb按值非遞減順序合并到 La中，請讀者考慮應(yīng)如何實(shí)現(xiàn)。 進(jìn)入 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í)行結(jié)果 實(shí)驗(yàn)三：實(shí)驗(yàn)?zāi)康募耙? ?理解特殊的線性結(jié)構(gòu)順序棧的抽象數(shù)據(jù)類型的定義，及在 C語言環(huán)境中的表示方法。 ?理解順序棧的基本操作的算法，及在 C語言環(huán)境中一些主要基本操作的實(shí)現(xiàn)。 ?在 C語言環(huán)境下實(shí)現(xiàn)順序棧的應(yīng)用操作： ?用棧實(shí)現(xiàn)十進(jìn)制數(shù)轉(zhuǎn)換成八進(jìn)制數(shù)。 ?利用棧實(shí)現(xiàn)一位數(shù)的加減乘除的表達(dá)式求解。 實(shí)驗(yàn)內(nèi)容 經(jīng)過對實(shí)驗(yàn)?zāi)康募耙蟮姆治?，本?shí)驗(yàn)仍然采用首先描述棧的基本操作集函數(shù)，然后分別在二個應(yīng)用操作中使用基本操作集函數(shù)來實(shí)現(xiàn)。 由于棧是一種特殊的線性結(jié)構(gòu)，僅在棧頂進(jìn)行插入和刪除操作，即棧具有后進(jìn)先出的特點(diǎn)，故其操作比一般的線性表更為容易，所以在本實(shí)驗(yàn)中有關(guān)棧的基本操作集的實(shí)現(xiàn)都比較簡單，沒有做過多的說明，而是在數(shù)制轉(zhuǎn)換和表達(dá)式求解的應(yīng)用操作中加入了更多的編程技巧，使讀者通過本實(shí)驗(yàn)不僅了解棧這種特殊結(jié)構(gòu)的線性表，而且掌握利用棧可實(shí)現(xiàn)很多的應(yīng)用，尤其是在實(shí)現(xiàn)表達(dá)式求解時用到了兩個順序棧，并且加入了運(yùn)算符的優(yōu)先關(guān)系的判斷等，實(shí)現(xiàn)稍有難度。 在程序 ，只包含了數(shù)制轉(zhuǎn)換和一位數(shù)的表達(dá)式求解，多位數(shù)的表達(dá)式求解思想與一位數(shù)表達(dá)式求解思想一致，但需要添加多位數(shù)的接收處理，請讀者自行編寫代碼。 程序名為： 。 實(shí)驗(yàn)內(nèi)容 ? 定義順序棧結(jié)構(gòu) ? 初始化一個空棧 ? 數(shù)據(jù)元素入棧 ? 數(shù)據(jù)元素出棧 ? 判斷一個棧是否為空 ? 銷毀一個棧 ? 取棧頂元素 ? 定義算符優(yōu)先關(guān)系 ? 判斷輸入元素是否為算符 ? 計算兩個操作數(shù) ? 十進(jìn)制數(shù)轉(zhuǎn)換成八進(jìn)制 ? 表達(dá)式求解 主函數(shù) 退出 基本操作集函數(shù) 應(yīng)用函數(shù) 定義順序棧的結(jié)構(gò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。 } 初始化一個空棧 數(shù)據(jù)元素入棧 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。 } 數(shù)據(jù)元素出棧 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。 } 十進(jìn)制數(shù)轉(zhuǎn)換成八進(jìn)制 本函數(shù)實(shí)現(xiàn)了無符號十進(jìn)制數(shù)和八進(jìn)制數(shù)間的轉(zhuǎn)換功能。 如輸入的是負(fù)數(shù)，由于系統(tǒng)使用補(bǔ)碼表示負(fù)數(shù)，會自動將其進(jìn)行補(bǔ)碼轉(zhuǎn)換，再通過本函數(shù)對其實(shí)現(xiàn)八進(jìn)制轉(zhuǎn)換。如，當(dāng)輸入 1時，結(jié)果顯示 65535。 如果需要將十進(jìn)制轉(zhuǎn)換成十六進(jìn)制應(yīng)該如何修改本函數(shù)，方法有兩種，第一種，在入棧時，存入十六進(jìn)制數(shù)，第二種，在出棧時，輸出十六進(jìn)制數(shù)。請讀者自己編寫代碼。 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)。 } 取棧頂?shù)臄?shù)據(jù)元素 Status GetTop(SqStack S,SElemType *e) { if() { *e=*()。 return OK。 } else return ERROR。 } 按照四則運(yùn)算法則定義的運(yùn)算符（包括：＋、－、＊、/、（）、＃）運(yùn)算的優(yōu)先關(guān)系，即按照表 運(yùn)算符與運(yùn)算符棧中的運(yùn)算符的優(yōu)先關(guān)系。 表 義的，也就是本函數(shù)的運(yùn)行結(jié)果。如果讀者希望在運(yùn)算中再加入其他運(yùn)算符（如乘方等），則必須先定義它們的關(guān)系，豐富表 ，同時在函數(shù)中添加所加入的運(yùn)算符的比較內(nèi)容。其中 θ 1為棧頂元素， θ 2為輸入元素。定義“?！边\(yùn)算符為輸入表達(dá)式時的結(jié)束符及存放運(yùn)算符的棧的棧底元素。 本函數(shù)不包含任何數(shù)據(jù)結(jié)構(gòu)的內(nèi)容，僅是在輸入表達(dá)式的過程中，按照表 的運(yùn)算符的關(guān)系 (、 、 =)。因一個表達(dá)式包含多個運(yùn)算符，故將此部分做為一個獨(dú)立的函數(shù)進(jìn)行編寫。 表 運(yùn)算符間的優(yōu)先關(guān)系 SElemType Precede(SElemType t1,SElemType t2) { SElemType f。 switch(t2) { case 39。+39。: case 39。39。:if(t1==39。(39