《數(shù)據(jù)結(jié)構(gòu)與算法》課件chap02

1、第二章 線性表Company Logo1、集合中必存在唯一的一個(gè)“第一元素”；2、集合中必存在唯一的一個(gè)“最后元素”；3、除了最后元素之外，均有唯一的后繼；4、除了第一個(gè)元素之外，均有唯一的前驅(qū)。線性結(jié)構(gòu)的基本特征Company Logo 線性表是最簡(jiǎn)單常用的線性數(shù)據(jù)結(jié)構(gòu)，順序存儲(chǔ)結(jié)構(gòu) 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)也是應(yīng)用中最常用的存儲(chǔ)方法，這一部分內(nèi)容和方法掌握了，有助于理解和掌握后續(xù)章節(jié)的內(nèi)容，如棧隊(duì)列串是特殊的線性表，數(shù)組和廣義表是線性表的擴(kuò)展；有助于理解和掌握樹(shù)和圖等復(fù)雜的數(shù)據(jù)結(jié)構(gòu) 存儲(chǔ)結(jié)構(gòu)和圖等復(fù)雜結(jié)構(gòu)的操作算法，因?yàn)闃?shù)和圖的存儲(chǔ)結(jié)構(gòu)大多或是這兩種存儲(chǔ)結(jié)構(gòu)的擴(kuò)充，或是它們的組合，因此這一章的內(nèi)容非常

2、重要，同學(xué)們要很好地學(xué)習(xí)理解和掌握。第二章 線性表Company Logo 2.1 線性表概念及基本操作2.2 線性表的順序存儲(chǔ)和實(shí)現(xiàn)2.3 線性表的鏈?zhǔn)酱鎯?chǔ)和實(shí)現(xiàn) 2.3.1 線性鏈表 2.3.2 循環(huán)鏈表 2.3.3 雙向鏈表2.4 一元多項(xiàng)式的表示及相加第二章 線性表Company Logo 線性表是n 個(gè)類型相同數(shù)據(jù)元素的有限序列，通常記作（a1, a2, a3, , an ）。 姓名 電話號(hào)碼 蔡穎 63214444 陳紅 63217777 劉建平 63216666 王小林 63218888 張力 63215555 .2. 1 線性表的概念例1、數(shù)學(xué)中的數(shù)列（11，13，15，17，

3、19，21）例2、英文字母表（A, B, C, D, E Z ）。例3、某單位的電話號(hào)碼簿。一 線性表的邏輯結(jié)構(gòu) Company Logo2.1 線性表的概念說(shuō)明：設(shè) A=（a1, a2, . , ai -1, ai , ai+1, , an ）是一線性表1） 線性表的數(shù)據(jù)元素可以是各種各樣的，但同一線性表中的元素必須是同一類型的；2） 在表中 ai-1 領(lǐng)先于ai ，ai 領(lǐng)先于ai+1 ，稱ai-1 是ai 的直接前驅(qū)，ai+1 是ai 的直接后繼；3） 在線性表中，除第一個(gè)元素和最后一個(gè)元素之外，其他元素都有且僅有一個(gè)直接前驅(qū)，有且僅有一個(gè)直接后繼，具有這種結(jié)構(gòu)特征的數(shù)據(jù)結(jié)構(gòu)稱為線性結(jié)構(gòu)

4、。線性表是一種線性數(shù)據(jù)結(jié)構(gòu)；4） 線性表中元素的個(gè)數(shù)n 稱為線性表的長(zhǎng)度，n=0 時(shí)稱為空表；5） ai是線性表的第i 個(gè)元素，稱i 為數(shù)據(jù)元素ai 的序號(hào)，每一個(gè)元素在線性表中的位置，僅取決于它的序號(hào)；Company Logo2.1 線性表的概念 線性表的其他表示方式 二元組表示 L= ，其中D= a1,a2, a3, . an S= R R=, , 圖示表示ai+1a1ai-1a2aian頂點(diǎn)：表示數(shù)據(jù)邊：表示是數(shù)據(jù)間的順序結(jié)構(gòu)關(guān)系Company Logo抽象數(shù)據(jù)類型線性表的定義：ADT List 數(shù)據(jù)對(duì)象：ai|ai ElemSet,i=1,2,n,n=0 稱n為線性表的表長(zhǎng)； 稱n0時(shí)

5、的線性表為空表 數(shù)據(jù)關(guān)系：R1=|ai-1,aiD，i=1,2,n設(shè)線性表為（a1,a2,ai,an）稱i為ai在線性表中的位序 基本操作： InitList(&L) 操作結(jié)果：構(gòu)造一個(gè)空的線性表。 DestroyList(&L) 初始條件：線性表L已存在。 操作結(jié)果：銷毀線性表LCompany Logo2.1 線性表的概念線性表的基本操作(描述見(jiàn)課本p19)1 存取操作：存取線性表中第i 個(gè)數(shù)據(jù)元素；2 查找操作 ：在線性表中查找滿足條件元素；3 插入操作 ：在線性表的第i個(gè)元素之前插入一個(gè)新元素;4 刪除操作 ：刪除線性表的第i個(gè)元素；5 分解操作 ：將一個(gè)線性表拆分為多個(gè)線性表；6 合并

6、操作: 7 排序 Company Logo2.1 線性表的概念說(shuō)明1 上面列出的操作，只是線性表的一些常用的基本操作；2 不同的應(yīng)用，基本操作可能是不同；3 線性表的復(fù)雜操作可通過(guò)基本操作實(shí)現(xiàn)；Company Logo 假設(shè):有兩個(gè)集合 A 和 B 分別用兩個(gè)線性表 LA 和 LB 表示，即：線性表中的數(shù)據(jù)元素即為集合中的成員。 現(xiàn)要求一個(gè)新的集合AAB。例 2-1 Company Logo 要求對(duì)線性表作如下操作：擴(kuò)大線性表 LA，將存在于線性表LB 中而不存在于線性表 LA 中的數(shù)據(jù)元素插入到線性表 LA 中去。上述問(wèn)題可演繹為：Company Logo1從線性表LB中依次察看每個(gè)數(shù)據(jù)元素

7、;2依值在線性表LA中進(jìn)行查訪; 3若不存在，則插入之。GetElem(LB, i)e LocateElem(LA, e, equal( ) ListInsert(LA, n+1, e)操作步驟：Company Logo GetElem(Lb, i, e); / 取Lb中第i個(gè)數(shù)據(jù)元素賦給e if (!LocateElem(La, e, equal( ) ) ListInsert(La, +La_len, e); / La中不存在和 e 相同的數(shù)據(jù)元素，則插入之void union(List &La, List Lb) La_len = ListLength(La); / 求線性表的長(zhǎng)度 Lb

8、_len = ListLength(Lb); for (i = 1; i = Lb_len; i+) / unionCompany Logo若線性表中的數(shù)據(jù)元素相互之間可以比較，并且數(shù)據(jù)元素在線性表中依值非遞減或非遞增有序排列，即 aiai-1 或 aiai-1(i = 2,3, n)，則稱該線性表為有序表(Ordered List)。試改變結(jié)構(gòu)，以有序表表示集合。Company Logo 已知線性表LA和LB中的數(shù)據(jù)元素按值非遞減有序排列，現(xiàn)要求將LA和LB歸并為一個(gè)新的線性表LC，且LC中的元素仍按值非遞減有序排列，設(shè) LA=（3，5，8，11） LB=（2，6，8，9，11，15，20）

9、 LC=（2，3，5，6，8，8，9，11，11，15，20）例 2-2Company Logovoid MergeList(List La, List Lb, List &Lc) / 本算法將非遞減的有序表 La 和 Lb 歸并為 Lcwhile (i = La_len) & (j = Lb_len) / La 和 Lb 均不空 GetElem(La, i, ai); GetElem(Lb, j, bj); InitList(Lc); / 構(gòu)造空的線性表 Lci = j = 1; k = 0;La_len = ListLength(La);Lb_len = ListLength(Lb);Co

10、mpany Logoif (ai = bj) / 將 ai 插入到 Lc 中 ListInsert(Lc, +k, ai); +i; else / 將 bj 插入到 Lc 中ListInsert(Lc, +k, bj); +j; while (i = La_len) / 當(dāng)La不空時(shí) GetElem(La, i+, ai); ListInsert(Lc, +k, ai); / 插入 La 表中剩余元素while (j = Lb_len) / 當(dāng)Lb不空時(shí) GetElem(Lb, j+, bj); ListInsert(Lc, +k, bj); / 插入 Lb 表中剩余元素 / merge_li

11、stCompany Logo為了存儲(chǔ)線性表，至少要保存兩類信息：1）線性表中的數(shù)據(jù)元素；2）線性表中數(shù)據(jù)元素的順序關(guān)系；如何在計(jì)算機(jī)中存儲(chǔ)線性表？如何在計(jì)算機(jī)中實(shí)現(xiàn)線性表的基本操作？Company Logo 2.2 線性表的順序存儲(chǔ)和實(shí)現(xiàn) 一 線性表的順序存儲(chǔ)結(jié)構(gòu)順序表 二 順序表的基本操作算法 三 效率分析Company Logo 線性表的順序存儲(chǔ)結(jié)構(gòu)，就是用一組連續(xù)的內(nèi)存單元依次存放線性表的數(shù)據(jù)元素。a1a2ai-1aiai+1an 線性表（a1,a2, a3, . an ） 的順序存儲(chǔ)結(jié)構(gòu)用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的線性表稱為順序表以“存儲(chǔ)位置相鄰”表示有序?qū)矗篖OC(ai)=LOC(ai-1

12、)+t 2.2 線性表的順序存儲(chǔ)和實(shí)現(xiàn)一 線性表的順序存儲(chǔ)結(jié)構(gòu)順序表 線性表的順序存儲(chǔ)結(jié)構(gòu)Company Logo2.2 線性表的順序存儲(chǔ)和實(shí)現(xiàn)說(shuō)明： 在順序存儲(chǔ)結(jié)構(gòu)下，線性表元素之間的邏輯關(guān)系，通過(guò)元素的存儲(chǔ)順序反映（表示）出來(lái)； 假設(shè)線性表中每個(gè)數(shù)據(jù)元素占用 t 個(gè)存儲(chǔ)單元，那么，在順序存儲(chǔ)結(jié)構(gòu)中，線性表的第i個(gè)元素的存儲(chǔ)位置與第1個(gè)元素的存儲(chǔ)位置的關(guān)系是： Loc(ai ) = Loc( a1 )+ ( i 1) ta1a2ai-1aiai+1ant個(gè)單元Loc( a1 )Loc(ai )基地址Company Logo2.2 線性表的順序存儲(chǔ)和實(shí)現(xiàn)怎樣在計(jì)算機(jī)上實(shí)現(xiàn)線性表的順序存儲(chǔ)結(jié)構(gòu)？

13、 可用C語(yǔ)言中的一維數(shù)組來(lái)表示,但數(shù)組不是線性表,數(shù)組存放的是線性表,數(shù)組的類型由線性表中的數(shù)據(jù)元素的性質(zhì)決定.如: #define MAX 100 int vMAX;Company Logo2.2 線性表的順序存儲(chǔ)和實(shí)現(xiàn)順序表的類型定義#define LIST_INIT_SIZE 100 / 線性表存儲(chǔ)空間的初始分配量#define LISTINCREMENT 10 / 線性表存儲(chǔ)空間的分配增量typedef structElemType * elem; /線性表存儲(chǔ)空間基址int length; /當(dāng)前線性表長(zhǎng)度int listsize; /當(dāng)前分配的線性表存儲(chǔ)空間大小 /（以sizeof

14、(ElemType)為單位）SqList;Company LogoSqList ：類型名，SqList類型的變量是結(jié)構(gòu)變量，它的三個(gè)域分別是：*elem：存放線性表元素的一維數(shù)組基址；其存儲(chǔ)空間在初始化操作（建空表）時(shí)動(dòng)態(tài)分配 length：存放線性表的表長(zhǎng)； listsize：用于存放當(dāng)前分配（存放線性表元素）的存儲(chǔ)空間的大小。Company Logo2.2 線性表的順序存儲(chǔ)和實(shí)現(xiàn)存放線性表元素 的一維數(shù)組設(shè) A = （a1,a2 , a3 , . an ）是一線性表，L是SqList 類型的結(jié)構(gòu)變量，用于存放線性表A，則L在內(nèi)存中的狀態(tài)如圖所示：順序表通過(guò)元素的存儲(chǔ)順序反映線性表元素間的邏

15、輯關(guān)系 a1 a2ai-1 aiai+1 an01i-2i-1in-199L.elemL.lengthL.listsizen99Company Logo2.2 線性表的順序存儲(chǔ)和實(shí)現(xiàn)二、順序表的基本操作算法插入 insert(v, x, i)功能：在順序表v 中的第 i ( 1=i=n+1)個(gè)數(shù)據(jù)元素之前插入一個(gè)新元素x, 插入前線性表為 (a1, a2, a3, ai-1 ,ai, an ) 插入后,線性表長(zhǎng)度為n+1, 線性表為 (a1, a2, a3, ai-1 , x, ai, an ) Company Logo2.2 線性表的順序存儲(chǔ)和實(shí)現(xiàn)插入前插入后插入操作示意圖： a1 a2ai

16、-1 aiai+1 an01i-2i-1in-1MAX-1nP_len a1 a2 ai-1 x ai an01i-2i-1n-2n-1nMAX-1n+1P_lenCompany Logo2.2 線性表的順序存儲(chǔ)和實(shí)現(xiàn)int insert ( int v , int i, int x, int * p_len) int j; if (i*p_len) return ( 0 ); /* i 值不合法 for ( j=*p_len , j= i; j-) vj= v j-1; vi-1=x ; *p_len+; /* 插入x , 表長(zhǎng)增1 return (1); 插入操作算法Company Log

17、o刪除算法的主要步驟1）若i 不合法或表L空，算法結(jié)束，并返回 0；否則轉(zhuǎn)2）2）將第i個(gè)元素之后的元素（不包括第i個(gè)元素）依次向前移動(dòng)一個(gè)位置;3）表長(zhǎng)-1 2.2 線性表的順序存儲(chǔ)和實(shí)現(xiàn)Company Logo2.2 線性表的順序存儲(chǔ)和實(shí)現(xiàn)int delete ( int v , int i, int * p_len) int j; if (i*p_len) return ( 0 ); /* i 值不合法 for ( j=i+1 , jdata0; /* 將基準(zhǔn)置入 x 中*/ for(i=1;ilast;i+) if(L-dataidatai; for(j=i-1;j=0;j-) /*移

18、動(dòng)*/ Ldataj+1=L-dataj; L-data0=y; 算法2.5Company Logo本算法中，有兩重循環(huán)，外循環(huán)執(zhí)行n1次，內(nèi)循環(huán)中移動(dòng)元素的次數(shù)與當(dāng)前數(shù)據(jù)的大小有關(guān)，當(dāng)?shù)趥€(gè)元素小于 a1 時(shí)，要移動(dòng)它上面的 i-1個(gè)元素，再加上當(dāng)前結(jié)點(diǎn)的保存及置入，所以移動(dòng) i-1+2次，在最壞情況下，a1 后面的結(jié)點(diǎn)都小于 a1 ，故總的移動(dòng)次數(shù)為 ： 即最壞情況下移動(dòng)數(shù)據(jù)時(shí)間性能為()。這個(gè)算法簡(jiǎn)單但效率低，在第章的快速排序中時(shí)我們將介紹另一種劃分算法，它的性能為(n)。 Company Logo2.2 線性表的順序存儲(chǔ)和實(shí)現(xiàn) 順序表是線性表最簡(jiǎn)單的一種存儲(chǔ)結(jié)構(gòu) 小結(jié)順序表的特點(diǎn)：1 通過(guò)元素的存儲(chǔ)順序反映 線性表中 數(shù)據(jù)元素之間的邏輯關(guān)系；2 可隨機(jī)存取順序表的元素；3 順序表的插入、刪除操作要通過(guò)移動(dòng)元素實(shí)現(xiàn)；Company Logo作 業(yè)1、有順序表A和B，其元素均按從小到大的升序排列，編寫(xiě)一個(gè)算法將它們合并成一個(gè)順序表C，要求C的元素也是從小到大的升序排列。（要求：寫(xiě)出算法思路，用類C寫(xiě)出算法并對(duì)算法的時(shí)間復(fù)雜度進(jìn)行分析）2、比較兩個(gè)線性表的大小。兩個(gè)線性表的比較依據(jù)下列方法：設(shè)A、B是兩個(gè)線性表，均用向量表示，表長(zhǎng)分別為m和n。 A和