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

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

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

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

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

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

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

7、;2依值在線性表LA中進行查訪; 3若不存在，則插入之。GetElem(LB, i)e LocateElem(LA, e, equal( ) ListInsert(LA, n+1, e)操作步驟：Company Logo GetElem(Lb, i, e); / 取Lb中第i個數(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); / 求線性表的長度 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歸并為一個新的線性表LC，且LC中的元素仍按值非遞減有序排列，設 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) / 當La不空時 GetElem(La, i+, ai); ListInsert(Lc, +k, ai); / 插入 La 表中剩余元素while (j = Lb_len) / 當Lb不空時 GetElem(Lb, j+, bj); ListInsert(Lc, +k, bj); / 插入 Lb 表中剩余元素 / merge_li

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

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

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

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

15、輯關(guān)系 a1 a2ai-1 aiai+1 an01i-2i-1in-199L.elemL.lengthL.listsizen99Company Logo2.2 線性表的順序存儲和實現(xiàn)二、順序表的基本操作算法插入 insert(v, x, i)功能：在順序表v 中的第 i ( 1=i=n+1)個數(shù)據(jù)元素之前插入一個新元素x, 插入前線性表為 (a1, a2, a3, ai-1 ,ai, an ) 插入后,線性表長度為n+1, 線性表為 (a1, a2, a3, ai-1 , x, ai, an ) Company Logo2.2 線性表的順序存儲和實現(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 線性表的順序存儲和實現(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 , 表長增1 return (1); 插入操作算法Company Log

17、o刪除算法的主要步驟1）若i 不合法或表L空，算法結(jié)束，并返回 0；否則轉(zhuǎn)2）2）將第i個元素之后的元素（不包括第i個元素）依次向前移動一個位置;3）表長-1 2.2 線性表的順序存儲和實現(xiàn)Company Logo2.2 線性表的順序存儲和實現(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; /* 將基準置入 x 中*/ for(i=1;ilast;i+) if(L-dataidatai; for(j=i-1;j=0;j-) /*移

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