數據結構實驗報告

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

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

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

4、三、詳細設計3、流程圖）三、詳細設計1、數據類型/ = = = = = ADT Stack 的表示與實現 = = = = = / - - - - - 數制轉換 - - - - -/#define STACK_INIT_SIZE 100/存儲空間初始分配量#define STACKINCREMENT 10/存儲空間分配增量typedef struct int *base;int *top;int stacksize;SqStack;/ - - - - - 基本操作的函數原型說明 - - - - - /void InitStack(SqStack &S)/構造一個空棧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)/對于輸入的任意一個非負十進制整數，打印輸出與其等值的八進制數 2、偽碼算法/ - - - - - 基本操作的算法描述 - - - - - /void InitStack(SqStack &S)/構造一個空棧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/對于輸入的任意一個非負十進制整數，打印輸出與其等值的八進制數 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打印標題開始輸出：要換轉的十進制數錯誤Yn>0輸入qNf>0 Y輸出：請輸入正確的進制位！NInitStack()初始化棧 Yn!=0NPush(S,n%f) YNNn=n/f!StackEmpty(S) Y輸出轉換后的數值結束4、調試分析（1）調試過程中遇到的問題和解決方法在調試過程中主要遇到一些符號打錯或輸出、輸出和函數之類的名稱打錯或漏打，根據第一行提示的錯誤然后進

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

10、否則結束） 結束。6、測試結果7、附錄（1）帶注釋的源程序#include <stdio.h>#include <stdlib.h>#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef struct int *base;int *top;int stacksize;SqStack;/構造一個空棧 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;/對于輸入的任意一個非負十進制整數，打印輸出與其等值的八進制數 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、作，輸入要轉換的十進制數與要轉換成的進制位 void Operate()int n,f;char q = 'y'while(q = 'y' | q = 'Y')printf("請輸入要轉換的十進制數值：");scanf("%d",&n);printf("n請輸入要轉換成的進制位：");scanf("%d",&f);printf("n%d轉換成%d進制數：",n,f);if(n > 0)if(f > 0)conversio

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

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

17、元多項式結果-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二、概要設計1、抽象數據類型的定義ADT Polynomial基本操作： CreatPolyn(&P,m)操作結果：輸入m項的系數和指數，建立一個一元多項式pDestroyPolyn (&P)初始條件：一元多項式P已存在。操作結果：銷毀一元多項式P。 PrintPolyn(P)初始條件：一元多項式P已存在。操作結果：打印輸出一元多項式P。 AddPolyn(

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

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

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

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

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

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

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

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

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

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

28、y | f=Y打印菜單YNchoose輸入f0 1、2InitList(P)輸入mSetCurElem(h,e)（輸入第二個一元多項式）2將一元多項式Pb的全部系數取反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的升序轉換成降序0刪除Pa和Pb系數和指數將Pb的系數加到Pa的系數YMakeNode(&s,e)Append(Pa,qb)FreeNode(&

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

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

31、define DestroyPolyn DestroyList#define PolynLength ListLengthtypedef struct /項的表示，多項式的項作為LinkList的數據元素 float coef;/系數 int expn;/指數 term,ElemType;/term用于本ADT，ElemType用于LinkList的數據對象名typedef struct LNode /結點類型 ElemType data;struct LNode *next;*Link,*Position;typedef struct _LinkList /鏈表類型 Link head,ta

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

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

34、GetCurElem(Link p)return p->data;/若升序鏈表L中存在與e滿足判定函數compare()取值為0的元素，則q指示L中/第一個值為e地結點的位置，并返回1；否則q指示第一個與e滿足判定函數/compare()取值>0地元素地前驅地位置。并返回0.（用于一元多項式） 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地結點，并返回1；若分配失敗。則返回0 int MakeNode(Link *p,ElemType e) *p = (Link)malloc(sizeof(LNode);/動態(tài)分配一個Link空間 if(!*p) return 0;(*p)->da

36、ta = e;return 1;/h指向L地一個結點，把h當做頭結點，將s所指結點插入在第一個結點之前 int InsFirst(LinkList *L,Link h,Link s) s->next = h->next;h->next = s;if(h = (*L).tail)/如果h指向尾結點 (*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、一個結點，返回p所指結點地直接后繼地位置/若無后繼，則返回NULL Position NextPos(Link p)return p->next;/h指向L地一個結點，把h當做頭結點，刪除鏈表中地第一個結點并以q返回。/若鏈表為空（h指向表尾結點），q = NULL,返回0 int DelFirst(LinkList *L,Link h,Link *q)*q = h->next;if(*q)/鏈表非空 h->next = (*q)->next;if(!h->next)/刪除尾結點 (*L).tail = h;/修改尾指針 (*L).len-;return 1;el

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

39、(*L).len += i;return 1;/將線性鏈表L重置為空表（頭尾結點相同為空表），并釋放遠鏈表地結點/空間，不釋放頭尾即誒但，只是置空 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);/清空鏈表（頭尾結點并沒有釋放） FreeNode(&(*L).head);/再釋放頭尾結點 (*L).tail = NULL;(*L).len = 0;return 1;/輸入m項的系數和指數，建立表示一元多項式的有序鏈表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);/設置頭結點的數據元素 printf("系數 指數n");for(i = 1;i <= m;+i) /一次輸入m個非零項 scanf("%f%d",&e.coef,&e.expn);if(!LocateElemP(P,e,&q,cmp)/當前鏈表中不存在該指數項 if(MakeNode(&s,e)InsFirst(&P,q,s);/生成結點并插入鏈表 /多項式加法：Pa=Pa+Pb，并銷毀一元多項式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地頭結點 qa = NextPos(ha);qb = NextPos(hb);/qa和qb分別指向Pa和Pb中當前結點（現為第一個結點） while(!ListEmpty(*Pa)&&!ListEmpty(*Pb)&&qa)/Pa和Pb均非空且ha沒指向尾結點（qa！=0） a = GetCurElem(qa);b = GetCurElem(qb);/a和b為兩表中當前比較元素 switch(cmp(a,b)

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

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

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

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