數(shù)據結構(二)線性表

1、第二章第二章 線性表線性表 2.1 線性表的類型定義 2.2 線性表的順序表示和實現(xiàn) 2.3 線性表的鏈式表示和實現(xiàn) 2.3.1 線性鏈表 2.3.2 循環(huán)鏈表 2.3.3 雙向鏈表 2.4 一元多項式的表示及相加 2.1 線性表的邏輯結構 線性表：由n(n0)個數(shù)據元素(結點)a1，a2， an組 成的有限序列。其中數(shù)據元素的個數(shù)n定義為表的長 度。當n=0時稱為空表，常常將非空的線性表(n0)記 作： (a1，a2，an) 這里的數(shù)據元素ai(1in)只是一個抽象的符號，其 具體含義在不同的情況下可以不同。 例1、26個英文字母組成的字母表 （A，B，C、Z） 例2、某校從1978年到19

2、83年各種型號的計算機擁有 量的變化情況。 （6，17，28，50，92，188） . . . 神經衰弱 17 男790634張立立 健康 21 男790633劉建平 一般 20 女790632陳 紅 健康 18 男790631王小林 健康情況年齡性 別學 號 姓 名 例3、學生健康情況登記表如下： 從以上例子可看出線性表的邏輯特征是： (1)對非空的線性表，有且僅有一個開始結點a1，它沒有直接前驅， 而僅有一個直接后繼a2； (2)有且僅有一個終端結點an，它沒有直接后繼，而僅有一個直接 前驅an-1； (3)其余的內部結點ai(2in-1)都有且僅有一個直接前驅ai-1和一個 直接后繼ai

3、+1。 線性表是一種典型的線性結構。 數(shù)據的運算是定義在邏輯結構上的，而運算的具體實現(xiàn)則是在 存儲結構上進行的。 2.2 線性表的順序存儲結構 2.2.1 線性表 把線性表的結點按邏輯順序依次存放在一組地址連續(xù)的存 儲單元里。用這種方法存儲的線性表簡稱順序表。 假設線性表的每個元素需占用m個存儲單元，并以所占的 第一個單元的存儲地址作為數(shù)據元素的存儲位置作為參考點。 則線性表中第i+1個數(shù)據元素的存儲位置Loc(ai+1)和第i個數(shù)據 元素的存儲位置Loc(ai)之間滿足下列關系： Loc(ai+1)=Loc(ai)+m ai ai+1 Loc(ai+1) m個字節(jié) Loc(ai) 線性表的第

4、i個數(shù)據元素ai的存儲位置為 : a1 a2 ai an Loc(a1) i-1個元素 Loc(ai)=(i-1)*m+Loc(a1) =Loc(a1)-m+i*m 由于Loc(a1)和m都是已知的 所以：V0= Loc(a1)-m Loc(ai)=V0+i*m 由于在高級語言中的一維數(shù)組也是采用順序存儲表示， 故可以用數(shù)組類型來描述順序表。又因為除了用數(shù)組來 存儲線性表的元素之外，順序表還應該用一個變量來表 示線性表的長度屬性，利用C+語言的結構類型來定義 順序表類型。 # define ListSize 100 /表容量 typedef int DataType;/以int為例 struc

5、t Sqlist DataType dataListSize; int lenth;/當前表中元素數(shù) ; lenth . Sqlist data ListSize個 2.2.2 順序表上實現(xiàn)的基本操作 在順序表存儲結構中，很容易實現(xiàn)線性表的一些操作，如線性 表的構造、第i個元素的訪問。 注意：C/C+語言中的數(shù)組下標從“0”開始，因此，若L是 Sqlist類型的順序表，則表中第i個元素位置是L.datai-1。 線性表的插入和刪除兩種運算。 1、插入 線性表的插入運算是指在表的i(1in+1)個位置上，插入一個新 結點x， 使長度為n的線性表 (a1，a i-1，ai，an) 變成長度為n+1

6、的線性表 (a1，a i-1，x，ai，an) 注： 可用memmove(L.data+i,L.dada+i-1,(L.lenth-i+1)*sizeof(DataType) 代替for循環(huán)（包含文件： string.h,一般格式 格式： memmove(目的地址，源地址，移動字節(jié)數(shù)) void InsertList(L,x,i) /在線性表L中第i個位置插入元素x if(iL.length+1) cout“插入序號錯誤”=ListSize) 溢出處理； else for(j=L.length-1;j=i-1;j-) /第i個元素（下標為i-1)開始 L.dataj+1=L.dataj;/順序

7、后移 L.datai-1=x; L.length+; memcpy(目的地址,源地址，字節(jié)數(shù)） memset(目的地址,字符，字節(jié)數(shù)） int a5050,b5050; a清0 for(i=0;i50;i+) for(j=0;j50;j+) aij=0; 拷貝： for(i=0;i50;i+) for(j=0;j最好情況； 當=1時，需移動表中所有結點-最壞情況， a1，a i-1，ai，an x 移動數(shù)據：n-i+1 算法的平均移動 由于插入可能在表中任何位置上進行，在長度為n 的線性表中第i個位置上插入一個結點，令Eis(n)表示移 動結點的期望值（即移動的平均次數(shù)），則在第i個位 置上插

8、入一個結點的移動次數(shù)為n-i+1。 Pi代表在第i 個位置插入概率，則 Eis(n)= p1 n+p2 (n-1)+ .+ pn 1+pn+1 0 若表中任何位置(1in+1)上插入結點的概率是 均等的，則 p1=p2=p3=p n+1=1/(n+1) 因此，在等概率插入的情況下： Eis(n)=1/(n+1)n+(n-1)+1+0=n/2 a1，a i-1，ai，an 可能的插入點有n+1處 結論：在順序表上做插入運算，平均要移動表上一半結 點。當表長n較大時，算法的效率相當?shù)汀ｋm然Eis(n)中n 的系數(shù)較小，但就數(shù)量級而言，它仍然是線性階的。因 此算法的平均時間復雜度為O(n)。 2、刪

9、除 線性表的刪除運算是指將表的第i(1in)結點刪除， 使長度為n的線性表：(a1，a i-1，ai，a i+1，an) 變成長度為n-1的線性表 (a1，a i-1，a i+1，an) void deleteList(L,i)/表L中刪除第i個元素 if(iL.length) cout“刪除序號錯”endl; return ERROR; for(j=i; jch; while (ch!=$) p=new LNode; pdata=ch; pnext=h; h=p; cin ch; LNode *CreateList( ) char ch; LNode *h,*p; h=NULL; cinch

10、; while (ch!= $) p=new LNode; pdata=ch; pnext=h; h=p; cin ch; return h; #include struct LNode char data; LNode *next; ; LNode *CreateList( ) char ch; LNode *h,*p; h=NULL; cinch; while (ch!= $) p=new LNode; pdata=ch; pnext=h; h=p; cin ch; return h; void CreateList1( LNode * LNode *p; h=NULL; cinch; w

11、hile (ch!=$) p=new LNode; pdata=ch; pnext=h; h=p; cin ch; void print(LNode *h) LNode *p=h; while(p!=NULL) coutdatanext; coutch; while(ch!=$) p=new LNode; pdata=ch; if(head=NULL) head=p; else r-next=p; r=p; cinch; if(r!=NULL) r-next=NULL; return head; 頭結點（哨兵結點）引入： 增加一個表頭結點，數(shù)據域可根據需要使用或不用。 特點： a、表中第一個結

12、點和在表的其它位置上的操作一致，無需進 行特殊處理； b、無論鏈表是否為空，其頭指針是指向頭結點。因此空表和 非空表的處理統(tǒng)一。 NULL head 有頭結點的空表 head= 無頭結點的空表 LNode *creat() LNode *r,*h; char ch; h=new LNode; r=h; cinch; while(ch!=$) r-next=new LNode; r=r-next; r-data=ch; cinch; r-next=NULL; return h; 上述算法里動態(tài)申請新結點空間時未加錯誤處理，在 實際使用時間，可作下列判定與處理： p= new LNode; if(

13、p= =NULL) 錯誤處理； 二、查找運算 1、按序號查找 在鏈表中，即使知道被訪問結點的序號i，也不能 象順序表中那樣直接按序號i訪問結點，而只能從鏈 表的頭指針出發(fā)，順鏈域next逐個結點往下搜索，直 到搜索到第i個結點為止。因此，鏈表不是隨機存取 結構。 設單鏈表的長度為n，要查找表中第i個結點，僅 當1in時，i的值是合法的。但有時需要找頭結點的 位置，故我們將頭結點看做是第0個結點，其算法如 下： LNode * getnode( head ，i)/ i1 /在鏈表head中取第i個數(shù)據，鏈表有頭結點 p=head; j=0; /計數(shù)用 while(pnext j+; if (i=

14、j) return p; else return NULL; 2、按值查找 按值查找是在鏈表中，查找是否有結點值等于給定值key 的結點，若有，則返回首次找到的其值為key的結點的存儲位 置；否則返回NULL。查找過程從開始結點出發(fā)，順著鏈表逐 個將結點的值和給定值key作比較。其算法如下： LNode *locatenode(head，key) p=headnext; while( p return p; 該算法的執(zhí)行時間亦與輸入實例中的的取值key有關，其 平均時間復雜度的分析類似于按序號查找。 三、插入運算 插入運算是將值為x的新結點插入到表的第i個結點的位置上， 即插入到ai-1與ai

15、之間。因此，必須首先找到ai-1的存儲位置p，然 后生成一個數(shù)據域為x的新結點，并令q指針指向該新結點，新結 點的指針域指向結點ai。從而實現(xiàn)三個結點ai-1，x和ai之間的邏輯 關系的變化 x ai-1ai ai-1ai x 三、插入運算 插入運算是將值為x的新結點插入到表的第i個結點的位置上， 即插入到ai-1與ai之間。因此，必須首先找到ai-1的存儲位置p，然 后生成一個數(shù)據域為x的新結點，并令q指針指向該新結點，新結 點的指針域指向結點ai。從而實現(xiàn)三個結點ai-1，x和ai之間的邏輯 關系的變化 ai-1ai x 三、插入運算 插入運算是將值為x的新結點插入到表的第i個結點的位置上

16、， 即插入到ai-1與ai之間。因此，必須首先找到ai-1的存儲位置p，然 后生成一個數(shù)據域為x的新結點，并令q指針指向該新結點，新結 點的指針域指向結點ai。從而實現(xiàn)三個結點ai-1，x和ai之間的邏輯 關系的變化 ai-1ai x p q q-next=p-next; 三、插入運算 插入運算是將值為x的新結點插入到表的第i個結點的位置上， 即插入到ai-1與ai之間。因此，必須首先找到ai-1的存儲位置p，然 后生成一個數(shù)據域為x的新結點，并令q指針指向該新結點，新結 點的指針域指向結點ai。從而實現(xiàn)三個結點ai-1，x和ai之間的邏輯 關系的變化 ai-1ai x p q q-next=

17、p-next; p-next=q; 三、插入運算 插入運算是將值為x的新結點插入到表的第i個結點的位置上， 即插入到ai-1與ai之間。因此，必須首先找到ai-1的存儲位置p，然 后生成一個數(shù)據域為x的新結點，并令q指針指向該新結點，新結 點的指針域指向結點ai。從而實現(xiàn)三個結點ai-1，x和ai之間的邏輯 關系的變化 ai-1ai x p q q-next=p-next; p-next=q; 三、插入運算 插入運算是將值為x的新結點插入到表的第i個結點的位置上， 即插入到ai-1與ai之間。因此，必須首先找到ai-1的存儲位置p，然 后生成一個數(shù)據域為x的新結點，并令q指針指向該新結點，新結

18、 點的指針域指向結點ai。從而實現(xiàn)三個結點ai-1，x和ai之間的邏輯 關系的變化 ai-1ai x p q q-next=p-next; p-next=q; 定位ai-1并將指針p指向它； 三、插入運算 插入運算是將值為x的新結點插入到表的第i個結點的位置上， 即插入到ai-1與ai之間。因此，必須首先找到ai-1的存儲位置p，然 后生成一個數(shù)據域為x的新結點，并令q指針指向該新結點，新結 點的指針域指向結點ai。從而實現(xiàn)三個結點ai-1，x和ai之間的邏輯 關系的變化 ai-1ai x p q q = new LNode; q-data=x; q-next=p-next; p-next=q

19、; 定位ai-1并將指針p指向它； 三、插入運算 插入運算是將值為x的新結點插入到表的第i個結點的位置上， 即插入到ai-1與ai之間。因此，必須首先找到ai-1的存儲位置p，然 后生成一個數(shù)據域為x的新結點，并令q指針指向該新結點，新結 點的指針域指向結點ai。從而實現(xiàn)三個結點ai-1，x和ai之間的邏輯 關系的變化 ai-1ai x p q q = new LNode; q-data=x; q-next=p-next; p-next=q; p=getnode(head，i-1); 功能：在頭指針為head的鏈表中定位第 i-1個結點,并返回結點位置。 三、插入運算 插入運算是將值為x的新結

20、點插入到表的第i個結點的位置上， 即插入到ai-1與ai之間。因此，必須首先找到ai-1的存儲位置p，然 后生成一個數(shù)據域為x的新結點，并令q指針指向該新結點，新結 點的指針域指向結點ai。從而實現(xiàn)三個結點ai-1，x和ai之間的邏輯 關系的變化 三、插入運算 void insertnode(head， x， i) LNode * p，*q; p=getnode(head，i-1); if(p=NULL) cout“position error”data=x; qnext=pnext; pnext=q; LNode * getnode( head ，i) p=head; j=0; /計數(shù)用 w

21、hile(pnext j+; if (i=j) return p; else return NULL; 四、刪除運算 刪除運算是將表的第i個結點刪去。因為在單鏈表中結點ai的 存儲地址是在其直接前趨結點ai-1的指針域next中，所以必須首 先找到ai-1的存儲位置p。然后令pnext指向ai的直接后繼結點， 即把ai從鏈上摘下。最后釋放結點ai的空間。此過程為： ai-1aiai+1 ai-1aiai+1 四、刪除運算 刪除運算是將表的第i個結點刪去。因為在單鏈表中結點ai的 存儲地址是在其直接前趨結點ai-1的指針域next中，所以必須首 先找到ai-1的存儲位置p。然后令pnext指向a

22、i的直接后繼結點， 即把ai從鏈上摘下。最后釋放結點ai的空間。此過程為： ai-1aiai+1 四、刪除運算 刪除運算是將表的第i個結點刪去。因為在單鏈表中結點ai的 存儲地址是在其直接前趨結點ai-1的指針域next中，所以必須首 先找到ai-1的存儲位置p。然后令pnext指向ai的直接后繼結點， 即把ai從鏈上摘下。最后釋放結點ai的空間。此過程為： ai-1aiai+1 p p-next=p-next-next; 四、刪除運算 刪除運算是將表的第i個結點刪去。因為在單鏈表中結點ai的 存儲地址是在其直接前趨結點ai-1的指針域next中，所以必須首 先找到ai-1的存儲位置p。然后令

23、pnext指向ai的直接后繼結點， 即把ai從鏈上摘下。最后釋放結點ai的空間。此過程為： ai-1aiai+1 p p-next=p-next-next; 問題：鏈表的邏輯結構已正確 了，但結點ai空間丟了。 四、刪除運算 刪除運算是將表的第i個結點刪去。因為在單鏈表中結點ai的 存儲地址是在其直接前趨結點ai-1的指針域next中，所以必須首 先找到ai-1的存儲位置p。然后令pnext指向ai的直接后繼結點， 即把ai從鏈上摘下。最后釋放結點ai的空間。此過程為： ai-1aiai+1 p p-next=p-next-next; r=p-next; p-next=r-next; dele

24、te r; 四、刪除運算 刪除運算是將表的第i個結點刪去。因為在單鏈表中結點ai的 存儲地址是在其直接前趨結點ai-1的指針域next中，所以必須首 先找到ai-1的存儲位置p。然后令pnext指向ai的直接后繼結點， 即把ai從鏈上摘下。最后釋放結點ai的空間。此過程為： ai-1aiai+1 p p-next=p-next-next; r=p-next; p-next=r-next; delete r; r 四、刪除運算 刪除運算是將表的第i個結點刪去。因為在單鏈表中結點ai的 存儲地址是在其直接前趨結點ai-1的指針域next中，所以必須首 先找到ai-1的存儲位置p。然后令pnext指

25、向ai的直接后繼結點， 即把ai從鏈上摘下。最后釋放結點ai的空間。此過程為： ai-1aiai+1 p p-next=p-next-next; r=p-next; p-next=r-next; delete r; r 四、刪除運算 刪除運算是將表的第i個結點刪去。因為在單鏈表中結點ai的 存儲地址是在其直接前趨結點ai-1的指針域next中，所以必須首 先找到ai-1的存儲位置p。然后令pnext指向ai的直接后繼結點， 即把ai從鏈上摘下。最后釋放結點ai的空間。此過程為： ai-1aiai+1 p p-next=p-next-next; p=getnode(head，i-1); r=p-

26、next; p-next=r-next; delete r; r 四、刪除運算 刪除運算是將表的第i個結點刪去。因為在單鏈表中結點ai的 存儲地址是在其直接前趨結點ai-1的指針域next中，所以必須首 先找到ai-1的存儲位置p。然后令pnext指向ai的直接后繼結點， 即把ai從鏈上摘下。最后釋放結點ai的空間。此過程為： 四、刪除運算 void deletelist(head， i) LNode *p， *r; p=getnode(head，i-1); if(p= =NULL | pnext= =NULL) return ERROR; r=pnext; pnext=rnext; dele

27、te r; 從上面的討論可以看出，鏈表上實現(xiàn)插入和刪除運算，無須移 動結點，僅需修改指針。 五、靜態(tài)鏈 1、靜態(tài)鏈表的概念 用一維數(shù)組來實現(xiàn)線性鏈表，這種用一維數(shù)組表示的線 性鏈表，稱為靜態(tài)鏈表。 靜態(tài)：體現(xiàn)在表的容量是一定的。（數(shù)組的大?。?鏈表：插入與刪除同前面所述的動態(tài)鏈表方法相同 2、靜態(tài)鏈表的類型定義 #define MAXSIZE 1000 / 鏈表的最大長度 struct Component ElemType data; int cur; ; Component VListMAXSIZE; SLinkList類型的數(shù)組變量是結構數(shù)組，每一數(shù)組分量包括兩個域： data：用于存儲線

28、性表元素； cur： 用于存儲直接后繼元素在數(shù)組中的位置 靜態(tài)鏈表圖示 0 h=5 數(shù)組 下標 靜態(tài)鏈表與 線性鏈表 的區(qū)別？ 線性鏈表圖示 地址 a1 8 a2 2 a4 -1 a3 0 1 2 3 4 5 6 7 8 9 10 1010 a1 1026 a2 1014 a4 0 a3 1010 1012 1014 1022 1024 1026 1028 1030 1020 1018 1016 h=1020 例：靜態(tài)鏈表的操作 設插入和刪除只在表的頭上進行（棧） h=7（5，7，2，3） （8，5，7，2，3） h=0 表中加入x 0 1 2 3 4 79 3-1 51 23 5 6 7 8

29、 9 10 0 1 2 3 4 79 3-1 51 23 5 6 7 8 9 10 2.(1)VListi.data=x; 1.在VList中找空位置 i(比如0) (2)VListi.cur=h; x 7 (3)h=i; 空位置的標識：將所有空位置構成鏈表，用av表示鏈首 0 1 2 3 4 2 79 3-1 10 5 8 4 51 -1 23 6 5 6 7 8 9 10 av=0 2.(1)Vlisti.data=x; 1.在VList中找空位置 i (2)Vlisti.cur=h; (3)h=i; if(av= -1) 無空間處理 else i=av; av=VListi.cur VL

30、isti.data=x; VListi.cur=h; h=i; 刪除： if(h!=-1) x=VListh.data; i=h; h=VListi.cur; VListi.cur=av; av=i; h=7 空表初始化： 開始，表是空的，所以： for(i=0;inextnext和rear，顯然，查找時間都是O(1)。因 此，實際中也常采用尾指針表示單循環(huán)鏈表.。 a1 an rear 由于循環(huán)鏈表中沒有NULL指針，故涉及遍歷操 作時，其終止條件就不再像非循環(huán)鏈表那樣判斷p 或pnext是否為空，而是判斷它們是否等于某 一指定指針，如頭指針或尾指針等。 2.3.3 雙向鏈表 雙向鏈表(Do

31、uble linked list):在單鏈表的每個結 點里再增加一個指向其直接前趨的指針域prior。 這樣就形成的鏈表中有兩個方向不同的鏈，故稱 為雙向鏈表。形式描述為： struct DuLNode datatype data; DuLNode *prior，*next; ; 結點 存儲前趨結點 的地址 存儲數(shù)據元素 存儲后繼結點 的地址 指針域數(shù)據域指針域 雙鏈表一般由頭指針唯一確定的，將頭結點和尾結點鏈接 起來構成循環(huán)鏈表，并稱之為雙向鏈表。 設指針p指向某一結點，則雙向鏈表結構的對稱性可用下式 描述： ppriornext=p=pnextprior L （c）非空的雙向循環(huán)鏈表 (b

32、)空的雙向循環(huán)鏈表 L p abc 雙向鏈表結點p前的插如數(shù)據x的操作： p q x ai-1ai q= new DuLNode; q-data=x; q-prior=p-prior; q-next=p; p-prior-next=q; p-prior=q; 雙向鏈表結點p前的插如數(shù)據x的操作： p q x q= new DuLNode; q-data=x; q-prior=p-prior; q-next=p; p-prior-next=q; p-prior=q; ai-1ai 雙向鏈表結點p前的插如數(shù)據x的操作： p q x ai-1ai q= new DuLNode; q-data=x;

33、q-prior=p-prior; q-next=p; p-prior-next=q; p-prior=q; ai+1ai ppriornext=pnext; pnextprior=pprior; delete p; p 刪除p指針所指的結點： ai-1 ai+1ai ppriornext=pnext; pnextprior=pprior; delete p; p 刪除p指針所指的結點： ai-1 ai+1ai ppriornext=pnext; pnextprior=pprior; delete p; p 刪除p指針所指的結點： ai-1 雙向鏈表的插入、刪除靈 活；鏈表維護的工作量大， 所需

34、的存儲空間較大。 24 一元多項式的表示及相加 P n (x) = pn xn + pn-1 xn-1 + p1 x + p0 Q m (x) = qm xm + qm-1 xm-1+ q1x + q0 一、一元多項式的表示 多項式的操作是表處理的典型用例。數(shù)學上,一元多項式可按 降冪寫成：（指數(shù)為正整數(shù)的情況） 其中：pn 、qm不為0 存儲結構：用線性鏈表表示。增加頭結點，每個結點有 coef:系數(shù) exp指數(shù) next：指針其中，頭結點的exp為-1。 coefexpnext 多項式 A (x) = 5 x 17 + 9 x 8 + 3x +7 ha 5 179 8317 0-1 例：求

35、兩多項式的和多項式 A (x) = 5 x 17 + 9 x 8 +3x+7 B (x) = 9 x 8 +22 x 7 +8 x 二、一元多項式的相加算法 一元多項式相加運算規(guī)則：指數(shù)相同的項系數(shù)相加 A (x) B (x)相加的和多項式為 C (x) = A (x) + B (x) = 5 x 17+ 22 x 7 + 11x +7 設多項式A (x) ，B (x)分別用帶表頭結點的線性鏈表 ha,hb表示,完成:ha=ha+hb 一元多項式加法算法主要步驟 分別對兩個鏈表ha 、hb進行掃描，設 工作指針pa 、 pb分別指向兩個多項式當前進 行比較的結點，q指針指向pa的前驅，初始：

36、q=ha; pa=ha-next; pb=hb-next; 若pa,pb都不為空：則比較兩者指數(shù)： pa-exp pb-exp： q,pa后移； pa-exp = pb-exp：將pb所指結點的系數(shù)“加”到pa所指結點 的系數(shù)上；若和為0，則pa所指結點刪除。 q , pa, pb調整 pa-exp exp ： 從表hb中復制pb所指結點的coef,exp，并將其插入到 ha表pa所指結點之前； 若pb不空：hb表中從pb開始的結點插入到ha表尾上 int comp(int a,int b) if(ab) return -1; if(a=b) return 0; else return 1;

37、PloyAdd(ha,hb) q=ha;pa=ha-next; pb=hb-next; while(pa!=NULL pa=pa-next; break; case 0: pa-coef+=pb-coef; if(pa-coef=0) q-next=pa-next; delete pa; pa=q; else q=pa; pa=pa-next; pb=pb-next; break; case 1: r=new Node; r-coef=pb-coef; r-exp=pb-exp; q-next=r; r-next=pa; q=r; pb=pb-next; break; while(pb!=NU

38、LL) r=new Node; r-coef=pb-coef; r-exp=pb-exp; q-next=r; r-next=pa; q=r; pb=pb-next; while改成： while(pb!=hb) 在改成循環(huán)鏈后， 此while可省去。 1、線性表v的數(shù)據遞增有序，試將x插入表中并保持有序性 （1）表順序表示 （2）鏈表表示 （3）帶有頭結點的鏈表 2、寫一個線性表的轉置算法（順序和鏈表（無頭結點）表示兩種情 況） （a1,a2,.,an)變?yōu)椋╝n,an-1,.,a1) 3、寫一個類（用模板）實現(xiàn)順序表示的線性表。 template class Li T *p; int len; int max; public: . 實習題目： hc=ha*hb 要求： （1） 輸入形式： 以 系數(shù) 指數(shù)的遞減序輸