數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告

1、編號(hào)： 江西理工大學(xué) 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 班 級(jí)： * 學(xué) 號(hào)： 09 姓 名： * 時(shí) 間： 2012年12月31日 2012年1月11日 指導(dǎo)教師： * 2013年01月30目 錄第一章 數(shù)制轉(zhuǎn)換1一、需求分析11、輸入的形式和輸入值的范圍12、輸出的形式13、程序所能達(dá)到的功能14、測(cè)試數(shù)據(jù)1二、概要設(shè)計(jì)21、抽象數(shù)據(jù)類型的定義22、主程序的流程以及各程序模塊之間的層次調(diào)用關(guān)系2三、詳細(xì)設(shè)計(jì)21、數(shù)據(jù)類型22、偽碼算法33、流程圖54、調(diào)試分析65、用戶使用說明66、測(cè)試結(jié)果77、附錄8第二章 一元多項(xiàng)式11一、需求分析111、輸入的形式和輸入值的范圍112、輸出的形式113、程序所能

2、達(dá)到的功能114、測(cè)試數(shù)據(jù)12二、概要設(shè)計(jì)121、抽象數(shù)據(jù)類型的定義122、主程序的流程以及各程序模塊之間的層次調(diào)用關(guān)系13三、詳細(xì)設(shè)計(jì)131、數(shù)據(jù)類型132、偽碼算法143、流程圖174、調(diào)試分析185、用戶使用說明186、測(cè)試結(jié)果197、附錄20第一章 數(shù)制轉(zhuǎn)換一、需求分析1、輸入的形式和輸入值的范圍n和f的輸入形式均為int型，n和f的輸入范圍均為1327672、輸出的形式十六進(jìn)制10-15輸出A-E，超過十六進(jìn)制時(shí)按16以上數(shù)值按原值輸出。3、程序所能達(dá)到的功能把十進(jìn)制數(shù)n轉(zhuǎn)換成任意進(jìn)制數(shù)f（對(duì)于輸入的任意一個(gè)非負(fù)十進(jìn)制整數(shù)，輸出與其等值的任意進(jìn)制數(shù)（如二，四，八，十六進(jìn)制）。4、測(cè)試

3、數(shù)據(jù)n（十進(jìn)制）f（進(jìn)制）輸出值22210110354411202537681240032767167FFF二、概要設(shè)計(jì)1、抽象數(shù)據(jù)類型的定義ADT Stack基本操作：InitStack(&S)操作結(jié)果：構(gòu)造一個(gè)空棧s。Push(&S,e)初始條件：棧s已存在。操作結(jié)果：插入元素e為新的棧頂元素。Pop(SqStack &S)初始操作：棧s已存在且非空。操作結(jié)果：刪除s的棧頂元素，并用e返回其值。StackEmpty(SqStack S)初始條件：棧s已存在。操作結(jié)果：若棧為空則返回1，否則返回0。ADT Stack2、主程序的流程以及各程序模塊之間的層次調(diào)用關(guān)系見（

4、三、詳細(xì)設(shè)計(jì)3、流程圖）三、詳細(xì)設(shè)計(jì)1、數(shù)據(jù)類型/ = = = = = ADT Stack 的表示與實(shí)現(xiàn) = = = = = / - - - - - 數(shù)制轉(zhuǎn)換 - - - - -/#define STACK_INIT_SIZE 100/存儲(chǔ)空間初始分配量#define STACKINCREMENT 10/存儲(chǔ)空間分配增量typedef struct int *base;int *top;int stacksize;SqStack;/ - - - - - 基本操作的函數(shù)原型說明 - - - - - /void InitStack(SqStack &S)/構(gòu)造一個(gè)空棧svoid Push(

5、SqStack &S,int e)/插入e為新的棧頂元素int Pop(SqStack &S)/刪除s的棧頂元素，并用e返回其值int StackEmpty(SqStack S)/若棧為空則返回1，否則返回0void conversion(int n,int f)/對(duì)于輸入的任意一個(gè)非負(fù)十進(jìn)制整數(shù)，打印輸出與其等值的八進(jìn)制數(shù) 2、偽碼算法/ - - - - - 基本操作的算法描述 - - - - - /void InitStack(SqStack &S)/構(gòu)造一個(gè)空棧sS.base = (int *)malloc(STACK_INIT_SIZE * sizeof(int

6、);if(!S.base) exit(-2);S.top = S.base;S.stacksize = STACK_INIT_SIZE;/ InitStackvoid Push(SqStack &S,int e)/插入元素e為新的棧頂元素if(S.top- S.base >= S.stacksize)S.base = (int *)realloc(S.base,(S.stacksize + STACKINCREMENT)*sizeof(int);if(!S.base) exit(-2);S.top = S.base + S.stacksize;S.stacksize += STA

7、CKINCREMENT;*S.top+ = e;/ Pushint Pop(SqStack &S)/刪除s的棧頂元素，并用e返回其值 int e;if(S.top = S.base) return 0;e = *-S.top;return e;/Popint StackEmpty(SqStack S)/若棧為空則返回1，否則返回0if(S.top = S.base) return 1;else return 0;/ StackEmpty/對(duì)于輸入的任意一個(gè)非負(fù)十進(jìn)制整數(shù)，打印輸出與其等值的八進(jìn)制數(shù) void conversion(int n,int f)InitStack(S);whi

8、le(n)Push(S,n%f);n = n/f;while(!StackEmpty(S)Pop(S,e)printf("%d",e);/ conversion3、流程圖輸入n和fq=y|q=Y打印標(biāo)題開始輸出：要換轉(zhuǎn)的十進(jìn)制數(shù)錯(cuò)誤Yn>0輸入qNf>0 Y輸出：請(qǐng)輸入正確的進(jìn)制位！NInitStack()初始化棧 Yn!=0NPush(S,n%f) YNNn=n/f!StackEmpty(S) Y輸出轉(zhuǎn)換后的數(shù)值結(jié)束4、調(diào)試分析（1）調(diào)試過程中遇到的問題和解決方法在調(diào)試過程中主要遇到一些符號(hào)打錯(cuò)或輸出、輸出和函數(shù)之類的名稱打錯(cuò)或漏打，根據(jù)第一行提示的錯(cuò)誤然后進(jìn)

9、行修改，修改之后再運(yùn)行調(diào)試，如此循環(huán)，直到徹底正常運(yùn)行，后面就是優(yōu)化見面的問題了。（2）算法的時(shí)空分析和改進(jìn)設(shè)想算法時(shí)間復(fù)雜度：f(n)改進(jìn)設(shè)想：可在輸出時(shí)將>10的數(shù)字用A-Z輸出。（3）經(jīng)驗(yàn)和體會(huì)等從這是實(shí)驗(yàn)當(dāng)中，我體會(huì)最深的是編程要特別仔細(xì)，因?yàn)樯圆蛔⒁饩涂赡艽蝈e(cuò)字母，這些錯(cuò)誤有時(shí)在調(diào)試當(dāng)中特別難找，就是一個(gè)小小的字母可能也要讓你花上好長時(shí)間來修改，還有就是要形成自己的編程風(fēng)格，這樣的代碼看起來不至于那么亂，給有人條理的感覺，也便于代碼的維護(hù)。5、用戶使用說明運(yùn)行輸入n和f（n和f均大于0） n和f正確輸入，然后打印輸出n轉(zhuǎn)換成f進(jìn)制后的數(shù)值 輸入q（輸入q=（y|Y）則繼續(xù)轉(zhuǎn)換，

10、否則結(jié)束） 結(jié)束。6、測(cè)試結(jié)果7、附錄（1）帶注釋的源程序#include <stdio.h>#include <stdlib.h>#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef struct int *base;int *top;int stacksize;SqStack;/構(gòu)造一個(gè)空棧 void InitStack(SqStack &S)S.base = (int *)malloc(STACK_INIT_SIZE * sizeof(int);if(!S.base) exit(-2);S.

11、top = S.base;S.stacksize = STACK_INIT_SIZE;/插入e為新的棧頂元素 void Push(SqStack &S,int e)if(S.top- S.base >= S.stacksize)S.base = (int *)realloc(S.base,(S.stacksize + STACKINCREMENT)*sizeof(int);if(!S.base) exit(-2);S.top = S.base + S.stacksize;S.stacksize += STACKINCREMENT;*S.top+ = e;/刪除s的棧頂元素，并用e

12、返回其值 int Pop(SqStack &S)int e;if(S.top = S.base) return 0;e = *-S.top;return e;/若棧為空則返回1，否則返回0 int StackEmpty(SqStack S)if(S.top = S.base) return 1;else return 0;/對(duì)于輸入的任意一個(gè)非負(fù)十進(jìn)制整數(shù)，打印輸出與其等值的八進(jìn)制數(shù) void conversion(int n,int f)int e;SqStack S;InitStack(S);while(n)Push(S,n%f);n = n/f;while(!StackEmpty

13、(S)switch(e = Pop(S)case 10:printf("A");break;case 11:printf("B");break;case 12:printf("C");break;case 13:printf("D");break;case 14:printf("E");break;case 15:printf("F");break;default:printf("%d",e);break;printf("nn");/操

14、作，輸入要轉(zhuǎn)換的十進(jìn)制數(shù)與要轉(zhuǎn)換成的進(jìn)制位 void Operate()int n,f;char q = 'y'while(q = 'y' | q = 'Y')printf("請(qǐng)輸入要轉(zhuǎn)換的十進(jìn)制數(shù)值：");scanf("%d",&n);printf("n請(qǐng)輸入要轉(zhuǎn)換成的進(jìn)制位：");scanf("%d",&f);printf("n%d轉(zhuǎn)換成%d進(jìn)制數(shù)：",n,f);if(n > 0)if(f > 0)conversio

15、n(n,f);elseprintf("請(qǐng)輸入正確的進(jìn)制位！nn");elseprintf("要換轉(zhuǎn)的十進(jìn)制數(shù)錯(cuò)誤。nn");printf("是否繼續(xù)？（y/n）：");scanf("%s",&q);printf("n");/標(biāo)題 void title()printf("ttt*n");printf("ttt*t數(shù) 制 轉(zhuǎn) 換t *n");printf("ttt*n");int main()title();printf("

16、;n");Operate();（2）程序文件名的清單數(shù)制轉(zhuǎn)換.cpp第二章 一元多項(xiàng)式一、需求分析1、輸入的形式和輸入值的范圍choose、m（非零項(xiàng)個(gè)數(shù)）和expn（指數(shù)）的輸入形式均為int型，coef（系數(shù)） 的輸入形式為float型，choose的輸入值為1、2和0，m和expn的輸入范圍均為132767，coef的輸入范圍為±3.4E38。2、輸出的形式例：3.00X8+8.00X7-5.00X5+1.00X2-2.35X13、程序所能達(dá)到的功能任務(wù)：能夠按照指數(shù)降序排列建立并輸出多項(xiàng)式。能夠完成兩個(gè)多項(xiàng)式的相加、相減，并將結(jié)果輸入。4、測(cè)試數(shù)據(jù) 一元多項(xiàng)式運(yùn)算一

17、元多項(xiàng)式結(jié)果-x2+x3+2x2+3x3+4x54x5+4x3+1x2x3-2x4+5.2x+x25x4+3.2x-7x4+1x3+1x2+8.4x1-2x2+3x3+4x4-xx2+4x3+x43x4-1x3-1x2-x1二、概要設(shè)計(jì)1、抽象數(shù)據(jù)類型的定義ADT Polynomial基本操作： CreatPolyn(&P,m)操作結(jié)果：輸入m項(xiàng)的系數(shù)和指數(shù)，建立一個(gè)一元多項(xiàng)式pDestroyPolyn (&P)初始條件：一元多項(xiàng)式P已存在。操作結(jié)果：銷毀一元多項(xiàng)式P。 PrintPolyn(P)初始條件：一元多項(xiàng)式P已存在。操作結(jié)果：打印輸出一元多項(xiàng)式P。 AddPolyn(

18、&Pa,&Pb)初始條件：一元多項(xiàng)式Pa和Pb已存在。操作結(jié)果：多項(xiàng)式加法：Pa=Pa+Pb，并銷毀一元多項(xiàng)式Pb SubtractPolyn(&Pa,&Pb)初始條件：一元多項(xiàng)式Pa和Pb已存在。操作結(jié)果：多項(xiàng)式減法：Pa=Pa-Pb，并銷毀一元多項(xiàng)式PbADT Polynomial2、主程序的流程以及各程序模塊之間的層次調(diào)用關(guān)系見（三、詳細(xì)設(shè)計(jì)3、流程圖）三、詳細(xì)設(shè)計(jì)1、數(shù)據(jù)類型/ = = = = = ADT Polynomial的表示與實(shí)現(xiàn) = = = = = / - - - - - 一元多項(xiàng)式 - - - - -/typedef struct /項(xiàng)的表示

19、，多項(xiàng)式的項(xiàng)作為LinkList的數(shù)據(jù)元素 float coef;/系數(shù) int expn;/指數(shù) term,ElemType;/term用于本ADT，ElemType用于LinkList的數(shù)據(jù)對(duì)象名typedef LinkList polynomial;/用帶表頭結(jié)點(diǎn)的有序鏈表表示多項(xiàng)式/ - - - - - 基本操作的函數(shù)原型說明 - - - - - / void CreatPolyn(polynomial &P,int m)/輸入m項(xiàng)的系數(shù)和指數(shù)，建立表示一元多項(xiàng)式的有序鏈表p int DestroyPolyn(polynomial p)/銷毀一元多項(xiàng)式p void PrintP

20、olyn(polynomial P)/打印輸出一元多項(xiàng)式pvoid AddPolyn(polynomial *Pa,polynomial *Pb)/多項(xiàng)式加法：Pa=Pa+Pb，并銷毀一元多項(xiàng)式Pb void SubtractPolyn(polynomial *Pa,polynomial *Pb)/多項(xiàng)式減法：Pa=Pa-Pb，并銷毀一元多項(xiàng)式Pb 2、偽碼算法/ - - - - - 基本操作的算法描述(部分重要操作) - - - - - / int cmp(term a,term b) /依a的指數(shù)值<(或=)(或>)b的指數(shù)值，分別返回-1，0，和+1 /cmpvoid Cre

21、atPolyn(polynomial &P,int m) /輸入m項(xiàng)的系數(shù)和指數(shù)，建立表示一元多項(xiàng)式的有序鏈表p InitList(P);h = GetHead(P);e.coef = 0.0;e.expn = -1;SetCurElem(h,e);/設(shè)置頭結(jié)點(diǎn)的數(shù)據(jù)元素 printf("系數(shù) 指數(shù)n");for(i = 1;i <= m;+i) /一次輸入m個(gè)非零項(xiàng) scanf(e.coef, e.expn);if(!LocateElemP(P,e,&q,cmp)/當(dāng)前鏈表中不存在該指數(shù)項(xiàng) if(MakeNode(&s,e)InsFirst(

22、&P,q,s);/生成結(jié)點(diǎn)并插入鏈表 /if/for/ CreatPolynvoid AddPolyn(polynomial *Pa,polynomial *Pb)/多項(xiàng)式加法：Pa=Pa+Pb，并銷毀一元多項(xiàng)式Pb ha = GetHead(*Pa); hb = GetHead(*Pb); /ha和hb分別指向Pa和Pb地頭結(jié)點(diǎn) qa = NextPos(ha); qb = NextPos(hb);/qa和qb分別指向Pa和Pb中當(dāng)前結(jié)點(diǎn)（現(xiàn)為第一個(gè)結(jié)點(diǎn)） while(!ListEmpty(*Pa)&&!ListEmpty(*Pb)&&qa)/Pa和P

23、b均非空且ha沒指向尾結(jié)點(diǎn)（qa！=0） a = GetCurElem(qa); b = GetCurElem(qb); /a和b為兩表中當(dāng)前比較元素 switch(cmp(a,b)case -1:/多項(xiàng)式Pa中當(dāng)前結(jié)點(diǎn)地指數(shù)值小 ha = qa;qa = NextPos(ha);/ha和qa均向后移一個(gè)結(jié)點(diǎn) break;case 0:/兩者地指數(shù)值相等sum = a.coef + b.coef;/修改Pa當(dāng)前結(jié)點(diǎn)地系數(shù)值 if(sum != 0.0)SetCurElem(qa,sum);ha = qa;else /刪除多項(xiàng)式Pa中當(dāng)前結(jié)點(diǎn) DelFirst(Pa,ha,&qa);Fr

24、eeNode(&qa);DelFirst(Pb,hb,&qb);FreeNode(&qb);qb = NextPos(hb);qa = NextPos(ha);break;case 1:/多項(xiàng)式Pb中當(dāng)前結(jié)點(diǎn)地指數(shù)值小 DelFirst(Pb,hb,&qb);InsFirst(Pa,ha,qb);qb = NextPos(hb);ha = NextPos(ha);break;/switch/whileif(!ListEmpty(*Pb)Append(Pa,qb);/鏈接Pb中剩余結(jié)點(diǎn)FreeNode(&hb);/釋放Pb頭結(jié)點(diǎn) /ifDestroyPol

25、yn(Pb);/銷毀Pb /AddPolynvoid Opposite(polynomial Pa)/一元多項(xiàng)式系數(shù)取反 p = Pa.head;while(p->next) /為一元多項(xiàng)式減法做準(zhǔn)備，將系數(shù)全部取反，然后執(zhí)行一元多項(xiàng)式的加法。 p = p->next;p->data.coef *= -1;/while/ Oppositevoid SubtractPolyn(polynomial *Pa,polynomial *Pb)/多項(xiàng)式減法：Pa=Pa-Pb，并銷毀一元多項(xiàng)式PbOpposite(*Pb);/先為一元多項(xiàng)式Pb系數(shù)全部取反AddPolyn(Pa,Pb);

26、/執(zhí)行一元多項(xiàng)式的加法，取反后相當(dāng)于減法。/ SubtractPolynvoid Sort(polynomial P) /將鏈表升序排序轉(zhuǎn)換成降序排序 tailNode = P.tail;/tailNode標(biāo)記P鏈表的尾結(jié)點(diǎn) while(P.head->next != tailNode)/當(dāng)P的頭結(jié)點(diǎn)下一個(gè)結(jié)點(diǎn)（第一個(gè)元素從是頭結(jié)點(diǎn)的下一個(gè)元素）不等/于尾結(jié)點(diǎn)時(shí)執(zhí)行 curNode = P.head->next;while(curNode != tailNode)/if(curNode->data.expn < curNode->next->data.exp

27、n)/當(dāng)當(dāng)前元素的指數(shù)小于下一個(gè)元素的指數(shù)時(shí)執(zhí)行交換 e = curNode->data;curNode->data = curNode->next->data;curNode->next->data = e;/ifnewNode = curNode;/while循環(huán)到最后時(shí)newNode指向tailNode的前一個(gè)結(jié)點(diǎn) curNode = curNode->next;/將eNode結(jié)點(diǎn)下移 /whiletailNode = newNode;/將tailNode結(jié)點(diǎn)前移（此時(shí)最大的指數(shù)已經(jīng)移到尾結(jié)點(diǎn)） /while/ Sort開始3、流程圖打印標(biāo)題f=

28、y | f=Y打印菜單YNchoose輸入f0 1、2InitList(P)輸入mSetCurElem(h,e)（輸入第二個(gè)一元多項(xiàng)式）2將一元多項(xiàng)式Pb的全部系數(shù)取反i = 1;i <= m;+iN1（第1次N執(zhí)行輸入m）!Pa&&! Pb&&qaY輸入e.coef和e.expn Y打印輸出Pacmp(a,b)!LocateElemP(P,e,&q,cmp) N -1 -2Sort()將Pa的升序轉(zhuǎn)換成降序0刪除Pa和Pb系數(shù)和指數(shù)將Pb的系數(shù)加到Pa的系數(shù)YMakeNode(&s,e)Append(Pa,qb)FreeNode(&

29、;hb) N! Pb銷毀鏈表PbInsFirst(&P,q,s)結(jié)束YY4、調(diào)試分析（1）調(diào)試過程中遇到的問題和解決方法在調(diào)試過程中主要遇到一些符號(hào)打錯(cuò)或輸出、輸出和函數(shù)之類的名稱打錯(cuò)或漏打，根據(jù)第一行提示的錯(cuò)誤然后進(jìn)行修改，修改之后再運(yùn)行調(diào)試，如此循環(huán)，直到徹底正常運(yùn)行，后面就是優(yōu)化見面的問題了。（2）改進(jìn)設(shè)想增加兩個(gè)一元多項(xiàng)式的乘法和除法操作，簡化代碼，減少時(shí)間和空間復(fù)雜度。（3）經(jīng)驗(yàn)和體會(huì)等從這是實(shí)驗(yàn)當(dāng)中，我體會(huì)最深的是編程要特別仔細(xì)，因?yàn)樯圆蛔⒁饩涂赡艽蝈e(cuò)字母，這些錯(cuò)誤有時(shí)在調(diào)試當(dāng)中特別難找，就是一個(gè)小小的字母可能也要讓你花上好長時(shí)間來修改，還有就是要形成自己的編程風(fēng)格，這樣的

30、代碼看起來不至于那么亂，給有人條理的感覺，也便于代碼的維護(hù)，還有就是函數(shù)調(diào)用的問題，函數(shù)調(diào)用多了容易出現(xiàn)錯(cuò)誤，函數(shù)寫多了也容易忘記，這就要求程序員有良好的注釋習(xí)慣。5、用戶使用說明運(yùn)行 選擇操作（1，2，0） 輸入第一個(gè)一元多項(xiàng)式非零項(xiàng)的個(gè)數(shù)m輸入第一個(gè)一元多項(xiàng)式的系數(shù)和項(xiàng)數(shù)（系數(shù) 項(xiàng)數(shù)） 輸入第一個(gè)二元多項(xiàng)式非零項(xiàng)的個(gè)數(shù)m 輸入第二個(gè)一元多項(xiàng)式的系數(shù)和項(xiàng)數(shù)（系數(shù) 項(xiàng)數(shù)） 打印輸出運(yùn)算后的一元多項(xiàng)式 輸入f 若f=y|f=Y 則繼續(xù)選擇操作 否則結(jié)束程序。6、測(cè)試結(jié)果7、附錄（1）帶注釋的源程序#include <stdio.h>#include <stdlib.h>#

31、define DestroyPolyn DestroyList#define PolynLength ListLengthtypedef struct /項(xiàng)的表示，多項(xiàng)式的項(xiàng)作為LinkList的數(shù)據(jù)元素 float coef;/系數(shù) int expn;/指數(shù) term,ElemType;/term用于本ADT，ElemType用于LinkList的數(shù)據(jù)對(duì)象名typedef struct LNode /結(jié)點(diǎn)類型 ElemType data;struct LNode *next;*Link,*Position;typedef struct _LinkList /鏈表類型 Link head,ta

32、il;/head指向頭結(jié)點(diǎn)，tail指向最后一個(gè)結(jié)點(diǎn) int len;/指向線性鏈表中數(shù)據(jù)元素的個(gè)數(shù) LinkList;typedef LinkList polynomial;/用帶表頭結(jié)點(diǎn)的有序鏈表表示多項(xiàng)式/依a的指數(shù)值<(或=)(或>)b的指數(shù)值，分別返回-1，0，和+1 int cmp(term a,term b) if(a.expn = b.expn)return 0;else return (a.expn > b.expn) ? 1:-1; /構(gòu)造一個(gè)空地線性鏈表 Lvoid InitList(LinkList &L) Link p;p = (Link)m

33、alloc(sizeof(LNode);/生成頭結(jié)點(diǎn) if(p)p->next = NULL;/將頭尾結(jié)點(diǎn)都分配好，并將其下一結(jié)點(diǎn)置空 L.head = L.tail = p;L.len = 0;/初始為0 /返回線性鏈表L中頭結(jié)點(diǎn)的位置 Position GetHead(LinkList L) return L.head;/已知p指向線性鏈表中的一個(gè)結(jié)點(diǎn)，返回e更新p所指結(jié)點(diǎn)中數(shù)據(jù)元素的值void SetCurElem(Link &p,ElemType e) p->data = e; /已知p指向線性鏈表中地一個(gè)結(jié)點(diǎn)，返回p所指結(jié)點(diǎn)中數(shù)據(jù)元素地位置地值 ElemType

34、GetCurElem(Link p)return p->data;/若升序鏈表L中存在與e滿足判定函數(shù)compare()取值為0的元素，則q指示L中/第一個(gè)值為e地結(jié)點(diǎn)的位置，并返回1；否則q指示第一個(gè)與e滿足判定函數(shù)/compare()取值>0地元素地前驅(qū)地位置。并返回0.（用于一元多項(xiàng)式） int LocateElemP(LinkList L,ElemType e,Position *q,int(*compare)(ElemType,ElemType) Link p = L.head,pp;dopp = p;p = p->next;while(p&&(co

35、mpare(p->data,e)<0);/沒到表尾且p->data.expn<e.expn if(!p | compare(p->data,e)>0)/到表尾或compare(p->data,e)>0 *q = pp;return 0;else*q = p;return 1;/分配由p指向地值為e地結(jié)點(diǎn)，并返回1；若分配失敗。則返回0 int MakeNode(Link *p,ElemType e) *p = (Link)malloc(sizeof(LNode);/動(dòng)態(tài)分配一個(gè)Link空間 if(!*p) return 0;(*p)->da

36、ta = e;return 1;/h指向L地一個(gè)結(jié)點(diǎn)，把h當(dāng)做頭結(jié)點(diǎn)，將s所指結(jié)點(diǎn)插入在第一個(gè)結(jié)點(diǎn)之前 int InsFirst(LinkList *L,Link h,Link s) s->next = h->next;h->next = s;if(h = (*L).tail)/如果h指向尾結(jié)點(diǎn) (*L).tail = h->next;/修改尾指針 (*L).len+;return 1;/若線性鏈表L為空表，則返回1，否則返回0 int ListEmpty(LinkList L)if(L.len) return 0;else return 1;/已知p指向線性鏈表L中地

37、一個(gè)結(jié)點(diǎn)，返回p所指結(jié)點(diǎn)地直接后繼地位置/若無后繼，則返回NULL Position NextPos(Link p)return p->next;/h指向L地一個(gè)結(jié)點(diǎn)，把h當(dāng)做頭結(jié)點(diǎn)，刪除鏈表中地第一個(gè)結(jié)點(diǎn)并以q返回。/若鏈表為空（h指向表尾結(jié)點(diǎn)），q = NULL,返回0 int DelFirst(LinkList *L,Link h,Link *q)*q = h->next;if(*q)/鏈表非空 h->next = (*q)->next;if(!h->next)/刪除尾結(jié)點(diǎn) (*L).tail = h;/修改尾指針 (*L).len-;return 1;el

38、se return 0;/鏈表空 /釋放p所指結(jié)點(diǎn) void FreeNode(Link *p)free(*p);/先釋放存儲(chǔ)空間，然后置空 *p = NULL;/將指針s(s->data為第一個(gè)數(shù)據(jù)元素)所指(彼此以指針項(xiàng)鏈，以NULL結(jié)尾)地/一串結(jié)點(diǎn)連接在線性鏈表L地最后一個(gè)結(jié)點(diǎn)之后，并改變鏈表L地尾指針指向新地尾結(jié)點(diǎn) int Append(LinkList *L,Link s)int i = 1;/記錄s為頭地串結(jié)點(diǎn)個(gè)數(shù) (*L).tail->next = s;/尾結(jié)點(diǎn)指向s while(s->next)s = s->next;i+;(*L).tail = s;

39、(*L).len += i;return 1;/將線性鏈表L重置為空表（頭尾結(jié)點(diǎn)相同為空表），并釋放遠(yuǎn)鏈表地結(jié)點(diǎn)/空間，不釋放頭尾即誒但，只是置空 int ClearList(LinkList *L)Link p,q;if(*L).head != (*L).tail)/不是空表 p = q = (*L).head->next;(*L).head->next = NULL;while(p != (*L).tail)p = q->next;free(q);q = p;free(q);(*L).tail = (*L).head;(*L).len = 0;return 1;/銷毀線性

40、鏈表L，L不再存在 int DestroyList(LinkList *L)ClearList(L);/清空鏈表（頭尾結(jié)點(diǎn)并沒有釋放） FreeNode(&(*L).head);/再釋放頭尾結(jié)點(diǎn) (*L).tail = NULL;(*L).len = 0;return 1;/輸入m項(xiàng)的系數(shù)和指數(shù)，建立表示一元多項(xiàng)式的有序鏈表p void CreatPolyn(polynomial &P,int m) Position h,q,s;term e;int i;InitList(P);h = GetHead(P);e.coef = 0.0;e.expn = -1;SetCurElem

41、(h,e);/設(shè)置頭結(jié)點(diǎn)的數(shù)據(jù)元素 printf("系數(shù) 指數(shù)n");for(i = 1;i <= m;+i) /一次輸入m個(gè)非零項(xiàng) scanf("%f%d",&e.coef,&e.expn);if(!LocateElemP(P,e,&q,cmp)/當(dāng)前鏈表中不存在該指數(shù)項(xiàng) if(MakeNode(&s,e)InsFirst(&P,q,s);/生成結(jié)點(diǎn)并插入鏈表 /多項(xiàng)式加法：Pa=Pa+Pb，并銷毀一元多項(xiàng)式Pb void AddPolyn(polynomial *Pa,polynomial *Pb)Pos

42、ition ha,hb,qa,qb;term a,b;ha = GetHead(*Pa);hb = GetHead(*Pb);/ha和hb分別指向Pa和Pb地頭結(jié)點(diǎn) qa = NextPos(ha);qb = NextPos(hb);/qa和qb分別指向Pa和Pb中當(dāng)前結(jié)點(diǎn)（現(xiàn)為第一個(gè)結(jié)點(diǎn)） while(!ListEmpty(*Pa)&&!ListEmpty(*Pb)&&qa)/Pa和Pb均非空且ha沒指向尾結(jié)點(diǎn)（qa！=0） a = GetCurElem(qa);b = GetCurElem(qb);/a和b為兩表中當(dāng)前比較元素 switch(cmp(a,b)

43、case -1:/多項(xiàng)式Pa中當(dāng)前結(jié)點(diǎn)地指數(shù)值小 ha = qa;qa = NextPos(ha);/ha和qa均向后移一個(gè)結(jié)點(diǎn) break;case 0:/兩者地指數(shù)值相等qa->data.coef += qb->data.coef;/修改Pa當(dāng)前結(jié)點(diǎn)地系數(shù)值 if(qa->data.coef != 0.0)SetCurElem(qa,qa->data);ha = qa;else /刪除多項(xiàng)式Pa中當(dāng)前結(jié)點(diǎn) DelFirst(Pa,ha,&qa);FreeNode(&qa);DelFirst(Pb,hb,&qb);FreeNode(&q

44、b);qb = NextPos(hb);qa = NextPos(ha);break;case 1:/多項(xiàng)式Pb中當(dāng)前結(jié)點(diǎn)地指數(shù)值小 DelFirst(Pb,hb,&qb);InsFirst(Pa,ha,qb);qb = NextPos(hb);ha = NextPos(ha);break;if(!ListEmpty(*Pb)Append(Pa,qb);/鏈接Pb中剩余結(jié)點(diǎn)FreeNode(&hb);/釋放Pb頭結(jié)點(diǎn) DestroyPolyn(Pb);/銷毀Pb /一元多項(xiàng)式系數(shù)取反 void Opposite(polynomial Pa)Position p;p = Pa.h

45、ead;while(p->next) /為一元多項(xiàng)式減法做準(zhǔn)備，將系數(shù)取反，然后執(zhí)行一元多項(xiàng)式的加法。 p = p->next;p->data.coef *= -1;/多項(xiàng)式減法：Pa=Pa-Pb，并銷毀一元多項(xiàng)式Pb void SubtractPolyn(polynomial *Pa,polynomial *Pb)Opposite(*Pb);AddPolyn(Pa,Pb);/將鏈表升序排序轉(zhuǎn)換成降序排序void Sort(polynomial P) Link curNode,tailNode,newNode; term e; tailNode = P.tail;/tailN

46、ode標(biāo)記P鏈表的尾結(jié)點(diǎn) while(P.head->next != tailNode)/當(dāng)P的頭結(jié)點(diǎn)下一個(gè)結(jié)點(diǎn)（第一個(gè)元素從是頭結(jié)點(diǎn)的下一個(gè)元素）不等/于尾結(jié)點(diǎn)時(shí)執(zhí)行 curNode = P.head->next;while(curNode != tailNode)/if(curNode->data.expn < curNode->next->data.expn)/當(dāng)當(dāng)前元素的指數(shù)小于下一個(gè)元素的指數(shù)時(shí)執(zhí)行交換 e = curNode->data;curNode->data = curNode->next->data;curNode->next->data = e;newNode = curNode;/while循環(huán)到最后時(shí)newNode指向tailNode的前一個(gè)結(jié)點(diǎn) curNode = curNode-