線性數(shù)據(jù)結(jié)構(gòu)線性表的應(yīng)用

1、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)UESTC 電子科技大學(xué)電子科技大學(xué) 計算機科學(xué)計算機科學(xué) 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法 主講主講：林劼：林劼 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)UESTC 電子科技大學(xué)電子科技大學(xué) 計算機科學(xué)計算機科學(xué) 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法 順序與鏈?zhǔn)酱鎯Y(jié)構(gòu)比較順存儲結(jié)構(gòu)的特點順存儲結(jié)構(gòu)的特點n邏輯上相鄰的元素，其物邏輯上相鄰的元素，其物理位置也相鄰；理位置也相鄰；n可隨機存取表中任一元素可隨機存取表中任一元素n必須按最大可能長度預(yù)分必須按最大可能長度預(yù)分存儲空間，存儲空間利用存儲空間，存儲空間利用率低，表的容量難以擴充率低，表的容量難以擴充，是一種靜態(tài)存儲結(jié)構(gòu)，是一種

2、靜態(tài)存儲結(jié)構(gòu)n插入刪除時，需移動大量插入刪除時，需移動大量元素，平均移動元素為元素，平均移動元素為n/2n/2鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點 邏輯上相鄰的元素，其物邏輯上相鄰的元素，其物理位置不一定相鄰；元素理位置不一定相鄰；元素之間的鄰接關(guān)系由指針域之間的鄰接關(guān)系由指針域指示指示 是非隨機存取存儲結(jié)構(gòu)；是非隨機存取存儲結(jié)構(gòu)；對鏈表的存取必須從頭指對鏈表的存取必須從頭指針開始針開始 是一種動態(tài)存儲結(jié)構(gòu)；是一種動態(tài)存儲結(jié)構(gòu)； 插入刪除運算非常方便；插入刪除運算非常方便；只需修改相應(yīng)指針值只需修改相應(yīng)指針值數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)UESTC 電子科技大學(xué)電子科技大學(xué) 計算機科學(xué)計算機科學(xué) 數(shù)據(jù)結(jié)構(gòu)與

3、算法數(shù)據(jù)結(jié)構(gòu)與算法 2.1.5 線性表的應(yīng)用線性表的應(yīng)用 n存儲結(jié)構(gòu)選擇原則存儲結(jié)構(gòu)選擇原則 各有優(yōu)缺點，選擇那一種存儲結(jié)構(gòu)由實際問題中各有優(yōu)缺點，選擇那一種存儲結(jié)構(gòu)由實際問題中的主要因素決定的主要因素決定 n(1)基于存儲空間的考慮：線性表的長度或存儲基于存儲空間的考慮：線性表的長度或存儲規(guī)模難以估計時，或數(shù)據(jù)元素動態(tài)變化較大時，規(guī)模難以估計時，或數(shù)據(jù)元素動態(tài)變化較大時，使用鏈表使用鏈表n(2)基于運算時間的考慮：經(jīng)常做的是訪問數(shù)據(jù)基于運算時間的考慮：經(jīng)常做的是訪問數(shù)據(jù)元素操作，插入刪除操作極少時用順序表元素操作，插入刪除操作極少時用順序表n(3)基于實現(xiàn)的考慮：順序表的實現(xiàn)較為簡單，基于實

4、現(xiàn)的考慮：順序表的實現(xiàn)較為簡單，鏈表的實現(xiàn)較為復(fù)雜鏈表的實現(xiàn)較為復(fù)雜 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)UESTC 電子科技大學(xué)電子科技大學(xué) 計算機科學(xué)計算機科學(xué) 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法 1. 線性表倒置線性表倒置 n問題：把線性表問題：把線性表(a1，a2，,an) 變?yōu)樽優(yōu)?an，an-1，,a1) n算法：算法：n算法算法1：對應(yīng)數(shù)據(jù)元素相交換，如：對應(yīng)數(shù)據(jù)元素相交換，如a1與與an交換、交換、a2與與an-1交換等等交換等等 n算法算法2：前驅(qū)后繼關(guān)系改變，即倒置前：前驅(qū)后繼關(guān)系改變，即倒置前a1是是a2的前驅(qū)、的前驅(qū)、a2是是a1后繼，倒置后后繼，倒置后a1是是a2的后繼、的后繼、a2是是a1前

5、驅(qū)，前驅(qū)， n實現(xiàn)：實現(xiàn)：n順序表上實現(xiàn)順序表上實現(xiàn)n單鏈表上實現(xiàn)單鏈表上實現(xiàn)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)UESTC 電子科技大學(xué)電子科技大學(xué) 計算機科學(xué)計算機科學(xué) 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法 1. 線性表倒置線性表倒置 在順序表上按算法在順序表上按算法1（對應(yīng)數(shù)據(jù)元素相交換）實現(xiàn)（對應(yīng)數(shù)據(jù)元素相交換）實現(xiàn)P.41：void List_Reverse(ListPtr L) int i=1, j=L-length; ElemType temp; while (ielemi; L-elemi=L-elemj; L-elemj=temp; i+; j-; 思考：思考：能否用能否用for循環(huán)？循環(huán)？數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)

6、結(jié)構(gòu)UESTC 電子科技大學(xué)電子科技大學(xué) 計算機科學(xué)計算機科學(xué) 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法 1. 線性表倒置線性表倒置 在單鏈表上按算法在單鏈表上按算法2（前驅(qū)后繼關(guān)系互換）實現(xiàn)（前驅(qū)后繼關(guān)系互換）實現(xiàn)P.42：void List_Reverse(ListPtr L) ListNodePtr q, p=(*L)-next; /*p指向第一個數(shù)據(jù)結(jié)點指向第一個數(shù)據(jù)結(jié)點*/ (*L)-next=NULL; /*將原鏈表置為空表將原鏈表置為空表*/ while (p) q=p; p=p-next; q-next=(*L)-next; /*插到頭結(jié)點的后面插到頭結(jié)點的后面*/ (*L)-next=q

7、; 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)UESTC 電子科技大學(xué)電子科技大學(xué) 計算機科學(xué)計算機科學(xué) 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法 線性表元素按照訪問頻度排序線性表元素按照訪問頻度排序n問題：設(shè)計一個在線性表中實現(xiàn)問題：設(shè)計一個在線性表中實現(xiàn)Locate運算的函數(shù)，使得運算的函數(shù)，使得線性表中所有結(jié)點按訪問頻度遞減的順序排列，以使訪問線性表中所有結(jié)點按訪問頻度遞減的順序排列，以使訪問頻繁高的結(jié)點總是靠近表頭頻繁高的結(jié)點總是靠近表頭 n分析：運算主要包括分析：運算主要包括n查找查找n如果該元素比前一個頻繁，則需要將其向前移動，也就如果該元素比前一個頻繁，則需要將其向前移動，也就是插入和刪除操作是插入和刪除操作n結(jié)構(gòu)選

8、擇結(jié)構(gòu)選擇n查找：順序或者鏈?zhǔn)骄?；插入刪除：鏈?zhǔn)酱鎯Σ檎遥喉樞蚧蛘哝準(zhǔn)骄?；插入刪除：鏈?zhǔn)酱鎯綜合：選擇鏈?zhǔn)骄C合：選擇鏈?zhǔn)絥哪種鏈?zhǔn)浇Y(jié)構(gòu)呢？哪種鏈?zhǔn)浇Y(jié)構(gòu)呢？n涉及前驅(qū)操作：雙向鏈表涉及前驅(qū)操作：雙向鏈表數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)UESTC 電子科技大學(xué)電子科技大學(xué) 計算機科學(xué)計算機科學(xué) 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法 線性表元素按照訪問頻度排序線性表元素按照訪問頻度排序n選用帶頭結(jié)點的雙向鏈表選用帶頭結(jié)點的雙向鏈表L，每個結(jié)點有，每個結(jié)點有4部分：部分：指向前驅(qū)結(jié)點的指針指向前驅(qū)結(jié)點的指針prior指向后繼結(jié)點的指針指向后繼結(jié)點的指針next存放數(shù)據(jù)的成員存放數(shù)據(jù)的成員data記載訪問頻度記載訪問頻度

9、freq，初始時所有結(jié)點的，初始時所有結(jié)點的freq都為都為0。n首先在鏈表中查找指定數(shù)據(jù)，如找到，將其首先在鏈表中查找指定數(shù)據(jù)，如找到，將其freq加加1，然后向前尋找然后向前尋找freq大于它的結(jié)點，并在該結(jié)點后面進行大于它的結(jié)點，并在該結(jié)點后面進行插入。插入。 prior freqdatanext數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)UESTC 電子科技大學(xué)電子科技大學(xué) 計算機科學(xué)計算機科學(xué) 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法 線性表元素按照訪問頻度排序線性表元素按照訪問頻度排序void Locate ( DuList L, ElemType x ) pNode p = L-next, q;while ( p &a

10、mp; p-data != x ) p = p-next; /*定位定位*/if ( p ) /*鏈表中存在鏈表中存在x*/ p-freq+; /*該結(jié)點的訪問頻度加該結(jié)點的訪問頻度加1*/ q = p;/*從鏈表中摘下這個結(jié)點從鏈表中摘下這個結(jié)點*/ if(p-prior) p-prior-next = p-next; if(p-next) p-next-prior = p-proir; p =q-prior; while ( p != L & q-freq p-freq ) /*尋找插入位置尋找插入位置*/ p = p-prior; q-next = p-next;/*插入在插入在

11、p之后之后*/ q-prior = p; if(p-next)p-next-prior = q; p-next = q;else Error( Not found!n);/*沒找到?jīng)]找到*/prior freqdatanexttypedef struct nodeElemType data; int freq;struct node *prior,*next;*DuList, *pNode;思考：思考：能否不要第二個循環(huán)？能否不要第二個循環(huán)？數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)UESTC 電子科技大學(xué)電子科技大學(xué) 計算機科學(xué)計算機科學(xué) 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法 一元多項式的表示和相加一元多項式的表示和相加 n

12、一元多項式一元多項式n邏輯結(jié)構(gòu)選擇邏輯結(jié)構(gòu)選擇n要存放的是系數(shù)和相應(yīng)的指數(shù)，為一個數(shù)據(jù)元素要存放的是系數(shù)和相應(yīng)的指數(shù)，為一個數(shù)據(jù)元素n次序關(guān)系（？）次序關(guān)系（？）n線性表線性表n存儲結(jié)構(gòu)選擇存儲結(jié)構(gòu)選擇n順序表如何存？順序表如何存？n鏈表如何存？鏈表如何存？n各自的優(yōu)點各自的優(yōu)點/缺點？缺點？n運算運算/操作有哪些？操作有哪些？n綜合考慮的結(jié)果是：綜合考慮的結(jié)果是：數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)UESTC 電子科技大學(xué)電子科技大學(xué) 計算機科學(xué)計算機科學(xué) 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法 nnnxpxpxppxp.)(2210 在計算機中，可以用一個線性表來表示在計算機中，可以用一個線性表來表示: P = (p0

13、, p1, ，pn)一元多項式一元多項式但是對于形如但是對于形如 S(x) = 1 + 3x10000 2x20000的多項式，上述表示方法是否合適？的多項式，上述表示方法是否合適？一元多項式的表示和相加一元多項式的表示和相加 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)UESTC 電子科技大學(xué)電子科技大學(xué) 計算機科學(xué)計算機科學(xué) 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法 一般情況下的一般情況下的一元稀疏多項式一元稀疏多項式可寫成：可寫成： Pn(x) = p1xe1 + p2xe2 + + pmxem其中：其中：pi 是指數(shù)為是指數(shù)為ei 的項的非零系數(shù)，的項的非零系數(shù)， 0 e1 e2 em = n可用線性表表示：可用線性表表示：

14、（p1, e1）, (p2, e2), ., (pm,em) ）數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)UESTC 電子科技大學(xué)電子科技大學(xué) 計算機科學(xué)計算機科學(xué) 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法 P999(x) = 7x3 - 2x12 - 8x999例如例如: ( (7, 3), (-2, 12), (-8, 999) )數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)UESTC 電子科技大學(xué)電子科技大學(xué) 計算機科學(xué)計算機科學(xué) 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法 ADT Polynomial 數(shù)據(jù)對象數(shù)據(jù)對象： 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系：抽象數(shù)據(jù)類型一元多項式的定義如下：抽象數(shù)據(jù)類型一元多項式的定義如下：D ai | ai TermSet, i=1,2,.,m,

15、 m0 TermSet 中的中的每個元素包含一個每個元素包含一個 表示系數(shù)的實數(shù)和表示指數(shù)的整數(shù)表示系數(shù)的實數(shù)和表示指數(shù)的整數(shù) R1 |ai-1 ,aiD, i=2,.,n 且且ai-1中的指數(shù)值中的指數(shù)值ai中的指數(shù)值，中的指數(shù)值，按指數(shù)的升冪有序按指數(shù)的升冪有序 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)UESTC 電子科技大學(xué)電子科技大學(xué) 計算機科學(xué)計算機科學(xué) 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法 鏈表定義鏈表定義typedef struct node / 多項式類型多項式類型的表示的表示 float coef; / 某項的某項的系數(shù)系數(shù) int expn; / 某項的某項的指數(shù)指數(shù) struct node *next;

16、 / 某項的后繼某項的后繼指針指針 node,polynomial; / 多項式類型定義完成多項式類型定義完成typedef polynomial *p1,*p2; /定義了兩個多項式定義了兩個多項式數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)UESTC 電子科技大學(xué)電子科技大學(xué) 計算機科學(xué)計算機科學(xué) 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法 2 3 -3 7 6 123 156 25-4 5 3 7 7 12 9 13-8 14 hahbhtpapbPA: 2x3-3x7+6x12+3x15+6x25PB: -4x5+3X7+7X12+9X13-8X1413數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)UESTC 電子科技大學(xué)電子科技大學(xué) 計算機科學(xué)計算機科學(xué)

17、 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法 作業(yè)一作業(yè)一 2.6習(xí)題（習(xí)題（P80）一、選擇題一、選擇題1-4二、填空題二、填空題1-4三、簡答題三、簡答題1-2四、算法設(shè)計題四、算法設(shè)計題1-2數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)UESTC 電子科技大學(xué)電子科技大學(xué) 計算機科學(xué)計算機科學(xué) 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法 回顧：線性表：回顧：線性表：n個相同元素的有限序列個相同元素的有限序列DS=（D，L，O，S）線性表的邏輯結(jié)構(gòu)線性表的邏輯結(jié)構(gòu)L：1對對1（前驅(qū)、后繼）（前驅(qū)、后繼）線性表的基本操作線性表的基本操作O：創(chuàng)建、取元素、插入、刪除等創(chuàng)建、取元素、插入、刪除等線性表的存儲結(jié)構(gòu)線性表的存儲結(jié)構(gòu)S：順序、鏈?zhǔn)巾樞颉㈡準(zhǔn)剑▎捂湵?、雙向鏈（單鏈表、雙向鏈表、循環(huán)、雙向循環(huán)）表、循環(huán)、雙向循環(huán)）數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)UESTC 電子科技大學(xué)電子科技大學(xué) 計算機科學(xué)計算機科學(xué) 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法 數(shù)據(jù)結(jié)構(gòu)關(guān)聯(lián)圖數(shù)據(jù)結(jié)構(gòu)關(guān)聯(lián)圖 串串n n個字符的有限序列個字符的有限序列前驅(qū)后繼數(shù)前驅(qū)后繼數(shù)數(shù)據(jù)元素限制數(shù)據(jù)元素限制線性表的變型線性表的變型帶頭結(jié)點、循環(huán)、雙向帶頭結(jié)點、循環(huán)、雙向結(jié)點變化結(jié)點變化2.22.2棧棧 插入、刪除限插入、刪除限定在一端進行定在一端進行的線性表的線