線性表CPPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1線性表線性表C1.1. 鏈表的表示鏈表的表示( (包括有關(guān)術(shù)語、包括有關(guān)術(shù)語、結(jié)構(gòu)結(jié)構(gòu)等）等）2.2. 鏈表的實(shí)現(xiàn)（建表、輸出、修改、插入、刪除）鏈表的實(shí)現(xiàn)（建表、輸出、修改、插入、刪除）補(bǔ)充：其它鏈表形式補(bǔ)充：其它鏈表形式循環(huán)鏈表循環(huán)鏈表雙向鏈表雙向鏈表靜態(tài)鏈表靜態(tài)鏈表提問：提問： 怎樣讀取結(jié)點(diǎn)數(shù)據(jù)域中的信息？怎樣讀取結(jié)點(diǎn)數(shù)據(jù)域中的信息？ 鏈表的操作要用指針鏈表的操作要用指針如用如用p-data僅兩個(gè)動(dòng)作：找位置僅兩個(gè)動(dòng)作：找位置和改地址！和改地址！第1頁/共41頁 線性表的邏輯結(jié)構(gòu)線性表的邏輯結(jié)構(gòu) 線性表的順序存儲(chǔ)及實(shí)現(xiàn)線性表的順序存儲(chǔ)及實(shí)現(xiàn) 線性表的鏈接存儲(chǔ)及實(shí)現(xiàn)線性表的鏈接存儲(chǔ)

2、及實(shí)現(xiàn) 順序表和單鏈表的比較順序表和單鏈表的比較 線性表的其他存儲(chǔ)及實(shí)現(xiàn)線性表的其他存儲(chǔ)及實(shí)現(xiàn)本章的基本內(nèi)容是：本章的基本內(nèi)容是：第2頁/共41頁存儲(chǔ)分配方式比較存儲(chǔ)分配方式比較順序表順序表采用采用順序存儲(chǔ)順序存儲(chǔ)結(jié)構(gòu)，即用一段地址結(jié)構(gòu)，即用一段地址連續(xù)連續(xù)的的存儲(chǔ)單元存儲(chǔ)單元依次依次存儲(chǔ)線性表的數(shù)據(jù)元素，數(shù)據(jù)元素之存儲(chǔ)線性表的數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系通過間的邏輯關(guān)系通過存儲(chǔ)位置存儲(chǔ)位置來實(shí)現(xiàn)。來實(shí)現(xiàn)。單鏈表單鏈表采用采用鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，即用一組結(jié)構(gòu)，即用一組任意任意的存儲(chǔ)的存儲(chǔ)單元存放線性表的元素。用單元存放線性表的元素。用指針指針來反映數(shù)據(jù)元素之來反映數(shù)據(jù)元素之間的邏輯關(guān)系。

3、間的邏輯關(guān)系。第3頁/共41頁時(shí)間性能比較時(shí)間性能比較 時(shí)間性能時(shí)間性能是指實(shí)現(xiàn)基于某種存儲(chǔ)結(jié)構(gòu)的基本操作（即是指實(shí)現(xiàn)基于某種存儲(chǔ)結(jié)構(gòu)的基本操作（即算法）的時(shí)間復(fù)雜度。算法）的時(shí)間復(fù)雜度。 按位查找：按位查找：順序表的時(shí)間為順序表的時(shí)間為(1)(1)，是隨機(jī)存??；，是隨機(jī)存??；單鏈表的時(shí)間為單鏈表的時(shí)間為( (n n) )，是順序存取。，是順序存取。插入和刪除：插入和刪除：順序表平均需移動(dòng)表長一半的元素，時(shí)間為順序表平均需移動(dòng)表長一半的元素，時(shí)間為( (n n) )；單鏈表不需要移動(dòng)元素，在給出某個(gè)合適位置的指針單鏈表不需要移動(dòng)元素，在給出某個(gè)合適位置的指針后，插入和刪除操作所需的時(shí)間僅為后，

4、插入和刪除操作所需的時(shí)間僅為(1)(1)。第4頁/共41頁空間性能比較空間性能比較 空間性能空間性能是指某種存儲(chǔ)結(jié)構(gòu)所占用的存儲(chǔ)空間的大小。是指某種存儲(chǔ)結(jié)構(gòu)所占用的存儲(chǔ)空間的大小。 定義結(jié)點(diǎn)的存儲(chǔ)密度：定義結(jié)點(diǎn)的存儲(chǔ)密度： 數(shù)據(jù)域占用的存儲(chǔ)量數(shù)據(jù)域占用的存儲(chǔ)量整個(gè)結(jié)點(diǎn)占用的存儲(chǔ)量整個(gè)結(jié)點(diǎn)占用的存儲(chǔ)量存儲(chǔ)密度存儲(chǔ)密度第5頁/共41頁空間性能比較空間性能比較 結(jié)點(diǎn)的存儲(chǔ)密度：結(jié)點(diǎn)的存儲(chǔ)密度：順序表順序表中每個(gè)結(jié)點(diǎn)的中每個(gè)結(jié)點(diǎn)的存儲(chǔ)密度為存儲(chǔ)密度為1 1（只存儲(chǔ)數(shù)據(jù)元（只存儲(chǔ)數(shù)據(jù)元素），沒有浪費(fèi)素），沒有浪費(fèi)空間空間；單鏈表的每個(gè)結(jié)點(diǎn)的單鏈表的每個(gè)結(jié)點(diǎn)的存儲(chǔ)密度存儲(chǔ)密度11（包括數(shù)據(jù)域和指（包括數(shù)據(jù)

5、域和指針域），有指針的結(jié)構(gòu)性開銷。針域），有指針的結(jié)構(gòu)性開銷。整體結(jié)構(gòu)：整體結(jié)構(gòu)：順序表需要預(yù)分配存儲(chǔ)空間，如果預(yù)分配得過大，順序表需要預(yù)分配存儲(chǔ)空間，如果預(yù)分配得過大，造成浪費(fèi)，若估計(jì)得過小，又將發(fā)生上溢；造成浪費(fèi)，若估計(jì)得過小，又將發(fā)生上溢；單鏈表不需要預(yù)分配空間，只要有內(nèi)存空間可以分單鏈表不需要預(yù)分配空間，只要有內(nèi)存空間可以分配，單鏈表中的元素個(gè)數(shù)就沒有限制。配，單鏈表中的元素個(gè)數(shù)就沒有限制。 第6頁/共41頁結(jié)論結(jié)論總之總之，根據(jù)實(shí)際問題的具體需要，根據(jù)實(shí)際問題的具體需要, ,加以綜合平衡，才能加以綜合平衡，才能終選定終選定比較適宜比較適宜的實(shí)現(xiàn)方法。的實(shí)現(xiàn)方法。第7頁/共41頁特點(diǎn)：

6、特點(diǎn)： 3從單鏈表中某結(jié)點(diǎn)從單鏈表中某結(jié)點(diǎn)p p出發(fā)如何找到其前驅(qū)？出發(fā)如何找到其前驅(qū)？heada1ai-1anaip討論討論1：第8頁/共41頁如：帶頭結(jié)點(diǎn)的如：帶頭結(jié)點(diǎn)的空空循環(huán)鏈表樣式循環(huán)鏈表樣式head注：將單鏈表的首尾相接，將終端結(jié)點(diǎn)的指針域由空注：將單鏈表的首尾相接，將終端結(jié)點(diǎn)的指針域由空指針改為指向頭結(jié)點(diǎn)，構(gòu)成指針改為指向頭結(jié)點(diǎn)，構(gòu)成單循環(huán)鏈表單循環(huán)鏈表，簡稱，簡稱循環(huán)鏈循環(huán)鏈表表。結(jié)點(diǎn)結(jié)構(gòu)定義：結(jié)點(diǎn)結(jié)構(gòu)定義：/未變未變template class XLinkList;/前視定義前視定義,便于使用友元便于使用友元template class Node friend class L

7、inkList;/友元類友元類 private: datatype data; Node *next; data next第9頁/共41頁heada1ai-1anai循環(huán)鏈表循環(huán)鏈表插入插入xspxspxsp核心算法描述：核心算法描述：s=new Node; s-data=x; s-next=p-next; p-next=s;第10頁/共41頁template void XLinkList:Insert(int i, datatype x) Node *p; int j; p=head ; j=0; while (p-next!=head & jnext; j+; if (j!=i-1) th

8、row i不合法不合法; else Node *s; s=new Node; s-data=x; s-next=p-next; p-next=s; 循環(huán)鏈表循環(huán)鏈表插入實(shí)現(xiàn)插入實(shí)現(xiàn)與單鏈表的插入操作相比，差別是什么？與單鏈表的插入操作相比，差別是什么？第11頁/共41頁循環(huán)條件：循環(huán)條件：p!=NULLp!=headp-next!=NULLp-next!=head循環(huán)鏈表中沒有明顯的尾端循環(huán)鏈表中沒有明顯的尾端 如何避免死循環(huán)如何避免死循環(huán)注：注：第12頁/共41頁template void XLinkList:PrintList( )Node *p;p=head-next;while (p!

9、=head) coutdatanext;循環(huán)鏈表循環(huán)鏈表遍歷算法實(shí)現(xiàn)遍歷算法實(shí)現(xiàn)O(n)第13頁/共41頁reara1ai-1anai開始結(jié)點(diǎn)：開始結(jié)點(diǎn)：rear-next-next終端結(jié)點(diǎn)：終端結(jié)點(diǎn)：rear其它形式的循環(huán)鏈表如：帶尾指針的循環(huán)鏈表其它形式的循環(huán)鏈表如：帶尾指針的循環(huán)鏈表 一個(gè)存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)得是否合理，取決于基于該一個(gè)存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)得是否合理，取決于基于該存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)的運(yùn)算是否方便運(yùn)算是否方便，時(shí)間性能是否提高時(shí)間性能是否提高。 第14頁/共41頁如何求結(jié)點(diǎn)如何求結(jié)點(diǎn)p p的直接前驅(qū)，時(shí)間性能？的直接前驅(qū)，時(shí)間性能？heada1ai-1anaip如何快速求得結(jié)點(diǎn)如何快速求得

10、結(jié)點(diǎn)p p的后繼？的后繼？如何快速求得結(jié)點(diǎn)如何快速求得結(jié)點(diǎn)p p的前驅(qū)？的前驅(qū)？討論討論2：p-next 引入一個(gè)輔助指針變量引入一個(gè)輔助指針變量q,從首結(jié)點(diǎn)開始遍歷，從首結(jié)點(diǎn)開始遍歷，至至q-next=p找到直接前驅(qū)結(jié)點(diǎn)找到直接前驅(qū)結(jié)點(diǎn);雙向鏈表：雙向鏈表：在單鏈表的每個(gè)結(jié)點(diǎn)中再設(shè)置一個(gè)指在單鏈表的每個(gè)結(jié)點(diǎn)中再設(shè)置一個(gè)指向其前驅(qū)結(jié)點(diǎn)的指針域。向其前驅(qū)結(jié)點(diǎn)的指針域。priordatanext第15頁/共41頁template class DLinkList;template class Node friend class DLinkList; private: type data; Node

11、*next,*prior;雙向鏈表雙向鏈表啟示？啟示？時(shí)空權(quán)衡時(shí)空權(quán)衡空間換取時(shí)間空間換取時(shí)間結(jié)點(diǎn)結(jié)構(gòu)定義（類的聲明）：結(jié)點(diǎn)結(jié)構(gòu)定義（類的聲明）：priordatanext常用雙向循環(huán)鏈表，如空的常用雙向循環(huán)鏈表，如空的雙向循環(huán)鏈表為：雙向循環(huán)鏈表為：ai-1第16頁/共41頁雙向鏈表的操作雙向鏈表的操作插入實(shí)現(xiàn)插入實(shí)現(xiàn)ai-1ai操作接口：操作接口： template void DLinkList:Insert(int i, type x)pxs注意指針修改的注意指針修改的相對(duì)相對(duì)順序順序核心語句：核心語句： DNode *s; s=new DNode; s-data=x; s-prior=

12、p; s-next=p-next; p-next-prior=s; p-next=s; 第17頁/共41頁雙向鏈表的操作雙向鏈表的操作刪除實(shí)現(xiàn)刪除實(shí)現(xiàn)操作接口：操作接口：template type DLinkList:Delete(int i)ai-1aiqai結(jié)點(diǎn)結(jié)點(diǎn)q q的指針是否需要修改？的指針是否需要修改？delete q; pDNode *q; int x;q=p-next; x=q-data; p-next=q-next;(q-next)-prior=p; delete q; 不需要！不需要！第18頁/共41頁答：能。答：能。用數(shù)組來表示單鏈表，用數(shù)組元素的下標(biāo)來模擬單用數(shù)組來表示

13、單鏈表，用數(shù)組元素的下標(biāo)來模擬單鏈表的指針，稱為鏈表的指針，稱為靜態(tài)鏈表靜態(tài)鏈表。數(shù)據(jù)元素由。數(shù)據(jù)元素由數(shù)據(jù)域數(shù)據(jù)域和和指示域指示域組成。組成。注：數(shù)據(jù)域含義與前面相同，注：數(shù)據(jù)域含義與前面相同，指示域指示域相當(dāng)于前面的相當(dāng)于前面的指針域。指針域。靜態(tài)鏈表的插入與刪除操作與普通鏈表一靜態(tài)鏈表的插入與刪除操作與普通鏈表一樣，不需要移動(dòng)元素，樣，不需要移動(dòng)元素，只需修改指示器只需修改指示器就可以了就可以了參考參考p79 data next數(shù)據(jù)數(shù)據(jù)域域指示指示域域第19頁/共41頁例如：線性表例如：線性表( (張，王，李，趙，吳張，王，李，趙，吳) )的靜態(tài)鏈表存儲(chǔ)的靜態(tài)鏈表存儲(chǔ)張張 2王王 3李李

14、 4趙趙 5吳吳 -1012345678 7 8 -1 1data next靜態(tài)鏈表靜態(tài)鏈表headavailhead：靜態(tài)鏈表頭指針靜態(tài)鏈表頭指針，為了方，為了方便插入和刪除操作，通常靜態(tài)鏈便插入和刪除操作，通常靜態(tài)鏈表表帶頭結(jié)點(diǎn)帶頭結(jié)點(diǎn)；avail：空閑鏈表頭指針空閑鏈表頭指針，空閑鏈空閑鏈表由于只在表頭操作，所以表由于只在表頭操作，所以不帶不帶頭結(jié)點(diǎn)頭結(jié)點(diǎn)；第20頁/共41頁例如：線性表例如：線性表( (張，王，李，趙，吳張，王，李，趙，吳) )的靜態(tài)鏈表存儲(chǔ)的靜態(tài)鏈表存儲(chǔ)張張 2王王 3李李 4趙趙 5吳吳 -1012345678 7 8 -1 1data nextheadavailS

15、LinkList S;第21頁/共41頁在線性表在線性表( (張，王，李，趙，吳張，王，李，趙，吳) )中中“王王”之后插入之后插入“孫孫”張張 2王王 3李李 4趙趙 5吳吳 -1012345678 7 8 -1 1data next張張 2王王 6李李 4趙趙 5吳吳 -1012345678 8 -1 1data next王之后王之后插入孫插入孫headavailheadavail孫孫3avail第22頁/共41頁在線性表在線性表( (張，王，李，趙，吳張，王，李，趙，吳) )中刪除中刪除“趙趙”張張 2王王 3李李 4趙趙 5吳吳 -1012345678 7 8 -1 1data nex

16、t張張 2王王 3李李 4趙趙 5吳吳 -1012345678 7 8 -1 1data next刪除趙刪除趙摘鏈摘鏈headavailheadavail5第23頁/共41頁在線性表在線性表( (張，王，李，趙，吳張，王，李，趙，吳) )中刪除中刪除“趙趙”張張 2王王 3李李 4趙趙 5吳吳 -1012345678 7 8 -1 1data next張張 2王王 3李李 4趙趙 5吳吳 -1012345678 7 8 -1 1data next刪除趙刪除趙歸還空間歸還空間headavailheadavail56第24頁/共41頁SLinkList S;注注:S0.next指示第指示第1個(gè)個(gè)結(jié)

17、點(diǎn)在表中的位置。結(jié)點(diǎn)在表中的位置。當(dāng)當(dāng)S0.next=1時(shí)時(shí).則則S1.data為線性表第一為線性表第一個(gè)元素的值。個(gè)元素的值。Sk.next指示第指示第K+1個(gè)個(gè)結(jié)點(diǎn)在表中的位置。結(jié)點(diǎn)在表中的位置。則則SK.data為線性表第為線性表第K個(gè)元素的值。個(gè)元素的值。張張 2王王 3李李 4趙趙 5吳吳 -1012345678 7 8 -1 1data nextheadavail第25頁/共41頁/線性表的靜態(tài)單鏈表存儲(chǔ)結(jié)構(gòu)定義線性表的靜態(tài)單鏈表存儲(chǔ)結(jié)構(gòu)定義/SLinkList.h 聲明類聲明類SLinkList#ifndef SLinkList_H#define SLinkList_Hconst

18、 int maxsize=5;template class SLinkList;template class Node friend class SLinkList; private: type data; int next; /指示器指示器;第26頁/共41頁template class SLinkList public: SLinkList( ); /建立只有頭結(jié)點(diǎn)的靜態(tài)空鏈表建立只有頭結(jié)點(diǎn)的靜態(tài)空鏈表 SLinkList(type *a, int n); /建立有建立有n個(gè)元素的靜態(tài)單鏈表個(gè)元素的靜態(tài)單鏈表 SLinkList(); /析構(gòu)函數(shù)析構(gòu)函數(shù),為空為空 int Length()

19、; /求靜態(tài)單鏈表的長度求靜態(tài)單鏈表的長度 type Get(int i); /取靜態(tài)單鏈表中第取靜態(tài)單鏈表中第i個(gè)結(jié)點(diǎn)的元素值個(gè)結(jié)點(diǎn)的元素值 int Locate(type x); /求靜態(tài)單鏈表中值為求靜態(tài)單鏈表中值為x的元素序號(hào)的元素序號(hào) void Insert(int i, type x); /在靜態(tài)單鏈表中第在靜態(tài)單鏈表中第i個(gè)位置插入元素值為個(gè)位置插入元素值為x的結(jié)點(diǎn)的結(jié)點(diǎn) type Delete(int i); /在靜態(tài)單鏈表中刪除第在靜態(tài)單鏈表中刪除第i個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn) void PrintList( ); /遍歷靜態(tài)單鏈表，按序號(hào)依次輸出各元素遍歷靜態(tài)單鏈表，按序號(hào)依次輸出各元素

20、 void clear(); void Pdisplay();/遍歷整個(gè)存儲(chǔ)區(qū)域的內(nèi)容遍歷整個(gè)存儲(chǔ)區(qū)域的內(nèi)容 private: Int head; /靜態(tài)單鏈表的頭指針靜態(tài)單鏈表的頭指針 int avail; /可利用空間表的頭指針可利用空間表的頭指針 Node sllmaxsize;/存儲(chǔ)區(qū)域存儲(chǔ)區(qū)域;#endif第27頁/共41頁靜態(tài)鏈表算法實(shí)現(xiàn)實(shí)例靜態(tài)鏈表算法實(shí)現(xiàn)實(shí)例(1)在靜態(tài)鏈表中實(shí)現(xiàn)在靜態(tài)鏈表中實(shí)現(xiàn)定位函數(shù)定位函數(shù)算法如下：算法如下：template int SLinkList:Locate(T x) /在靜態(tài)單鏈表在靜態(tài)單鏈表S查找第查找第1個(gè)值為個(gè)值為x的元素的位置。的元素的位

21、置。/若找到，則返回位序，否則為若找到，則返回位序，否則為-1； int i; i=sllhead.next ; while(i !=-1& abs(strcmp(Si.data,x) i=Si.next;return i;/#include /#include math.h第28頁/共41頁(2)在靜態(tài)鏈表中實(shí)現(xiàn)在靜態(tài)鏈表中實(shí)現(xiàn)插入算法插入算法如下：如下：template void SLinkList:Insert(int i, T x) /在靜態(tài)單鏈表中第在靜態(tài)單鏈表中第i個(gè)位置插入元素值為個(gè)位置插入元素值為x的結(jié)點(diǎn)的結(jié)點(diǎn) int p; int j; p=head; j=0; /指示器指示

22、器p初始化初始化 while (p!=-1 & ji-1) p=sllp.next; /指示器指示器p后移后移 j+; /找插入點(diǎn)找插入點(diǎn) if (p=-1) throw i的位置不合法的位置不合法; else int s;/存儲(chǔ)放新結(jié)點(diǎn)存儲(chǔ)放新結(jié)點(diǎn) s=avail; avail=sllavail.next;/從從avail鏈中刪除鏈中刪除 slls.data=x; /數(shù)據(jù)域?yàn)閿?shù)據(jù)域?yàn)閤 slls.next=sllp.next; /插入到插入到head鏈中。鏈中。 sllp.next=s;與動(dòng)態(tài)鏈表算法與動(dòng)態(tài)鏈表算法相似相似, ,但其利用但其利用指示器實(shí)現(xiàn)指示器實(shí)現(xiàn)! !第29頁/共41頁在靜

23、態(tài)鏈表中實(shí)現(xiàn)在靜態(tài)鏈表中實(shí)現(xiàn)刪除算法刪除算法如下：如下：template T SLinkList:Delete(int i) int p; int j; p=head ; j=0; /指示器指示器p初始化初始化 while (p!=-1 & ji-1) /查找第查找第i-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn) p=sllp.next; j+; if (p=-1 | sllp.next=-1) throw “i不合法不合法; else int q; int x; q=sllp.next; x=sllq.data; /暫存被刪結(jié)點(diǎn)暫存被刪結(jié)點(diǎn) sllp.next=sllq.next; /摘鏈摘鏈 sllq.next=av

24、ail;/avail收回收回 avail=q; return x;與動(dòng)態(tài)鏈表算法與動(dòng)態(tài)鏈表算法相似相似, ,但其利用但其利用指示器實(shí)現(xiàn)指示器實(shí)現(xiàn)! !第30頁/共41頁相對(duì)于順序表而言，靜態(tài)鏈表有什么優(yōu)點(diǎn)？相對(duì)于順序表而言，靜態(tài)鏈表有什么優(yōu)點(diǎn)？ 優(yōu)點(diǎn)：優(yōu)點(diǎn)：在執(zhí)行插入和刪除操作時(shí)，在執(zhí)行插入和刪除操作時(shí)，只需修改游標(biāo)只需修改游標(biāo)，不需要移動(dòng)表不需要移動(dòng)表中的元素，從而改進(jìn)了在順序表中的元素，從而改進(jìn)了在順序表中插入和刪除操作需要移動(dòng)大量元素的缺點(diǎn)。中插入和刪除操作需要移動(dòng)大量元素的缺點(diǎn)。缺點(diǎn)缺點(diǎn):(1):(1)表長難以確定表長難以確定； (2)(2)靜態(tài)鏈表靜態(tài)鏈表還需要維護(hù)還需要維護(hù)一個(gè)一個(gè)

25、空閑鏈空閑鏈； (3)(3)靜態(tài)鏈表靜態(tài)鏈表不能隨機(jī)存取不能隨機(jī)存取。 第31頁/共41頁、間接尋址、間接尋址方法之一：將數(shù)組和指針結(jié)合起來。方法之一：將數(shù)組和指針結(jié)合起來。數(shù)組數(shù)組中存儲(chǔ)數(shù)據(jù)元素的單元改為中存儲(chǔ)數(shù)據(jù)元素的單元改為存儲(chǔ)指向該存儲(chǔ)指向該元素的指針元素的指針 。0 1 2 i-1 n-1 Max-1 空閑空閑 長度長度 a1 ai an a2插入操作移動(dòng)的不是元素而是指向元素的指針。當(dāng)元素插入操作移動(dòng)的不是元素而是指向元素的指針。當(dāng)元素本身占用的空間較多時(shí)，比順序表的插入操作快得多。本身占用的空間較多時(shí)，比順序表的插入操作快得多。 第32頁/共41頁一元多項(xiàng)式的計(jì)算一元多項(xiàng)式的計(jì)算

26、第33頁/共41頁一元多項(xiàng)式的通式可表示為：一元多項(xiàng)式的通式可表示為：A xaxaxa xmemeemm().120120分析：分析：一元多項(xiàng)式在計(jì)算機(jī)內(nèi)存儲(chǔ)時(shí)，既可用一元多項(xiàng)式在計(jì)算機(jī)內(nèi)存儲(chǔ)時(shí)，既可用順序表順序表存儲(chǔ)存儲(chǔ)，又可用，又可用鏈表鏈表存儲(chǔ)。但當(dāng)多項(xiàng)式的存儲(chǔ)。但當(dāng)多項(xiàng)式的次數(shù)很高且零系數(shù)項(xiàng)很多次數(shù)很高且零系數(shù)項(xiàng)很多時(shí)，則更適于用鏈表存儲(chǔ)（時(shí)，則更適于用鏈表存儲(chǔ)（通常設(shè)計(jì)兩個(gè)數(shù)據(jù)域和一個(gè)指針通常設(shè)計(jì)兩個(gè)數(shù)據(jù)域和一個(gè)指針域域）。）。a0a1a2am-2am-1順序表順序表鏈表鏈表am-1 em-1am-2 em-2 a0 e0 或或0.0 -1 am-1 em-1 a0 e0第34頁/共41頁coefexpnextclass termpublic:float coef;/系數(shù)系數(shù)int exp;/指數(shù)指數(shù);結(jié)點(diǎn)包含兩個(gè)域結(jié)點(diǎn)包含兩個(gè)域data和和next,并且并且data又包又包含兩個(gè)域含兩個(gè)域coef和和exp。如結(jié)點(diǎn)如結(jié)點(diǎn)e為：為：Node e;e第35頁/共41頁bxxx8310141063 142 81 0a8 143 1010 6b例：例：123814xxa運(yùn)算規(guī)則：兩多項(xiàng)式中運(yùn)算規(guī)則：兩多項(xiàng)式中指數(shù)相同的項(xiàng)指數(shù)相同的項(xiàng)對(duì)應(yīng)對(duì)應(yīng)系系數(shù)相加，數(shù)相加，若若和不為和不為0,則則構(gòu)成多項(xiàng)式構(gòu)成多項(xiàng)式c=(a+b)中的一項(xiàng)；中的一項(xiàng)；a和和b中所有指數(shù)不相