指針構成鏈表及鏈表用途

1、Linear ListLinear List & Sequential ListsLinear ListsConception of Linear ListThe ADT of Linear ListWhat is Sequential ListHow to build a Sequential ListTo Implement Polynomial Addition Using Sequential ListLinear Lists1Conception of Linear ListnLinear List is a finite, ordered sequence of data item

2、s known as elements.qData items must belong to same data type. qOperations do not depend on the elemental data type.qEmpty lists, sorted lists, and unsorted lists.qthe length, head, tail4線性表的定義及特點線性表n(n0)個具有相同特性的數(shù)據(jù)元素的有限序列其中n表示線性表的長度長度，即數(shù)據(jù)元素的個數(shù)n=0時表為空表空表n0時記為:（a1, a2， ai-1， ai， ai+1， an）基本特征有且只有一個“第一

3、元素”，有且只有一個“最后元素”除第一元素之外，其它元素都有唯一的直接前驅前驅（前趨）除最后元素之外，其它元素都有唯一的直接后繼后繼Linear Lists元素的含義n數(shù)據(jù)元素在不同問題中的含義各不相同n可以是一個數(shù)、一個符號，一個記錄，或其它更復雜的信息n這里的學生成績表是一個線性表n數(shù)據(jù)元素是每一個學生的信息，包括：學號、姓名、成績共三個數(shù)據(jù)項學號學號姓名姓名計算機導論計算機導論04081101陳小潔陳小潔8004081102馬麗麗馬麗麗7504081103林春英林春英8204081104王澄娟王澄娟9004081150張吉祥張吉祥70Linear ListsADT LinearList

4、Data object：D ai | ai ElemType, i=1,2,.,n, n0 Relation ：R1 |ai-1 ,aiD, i=2,.,n Operations ：Create (); 創(chuàng)建一個線性表Destroy(); 銷毀一個線性表IsEmpty(); 判斷線性表是否為空Length(); 獲得線性表的長度GetValue(k,i);求線性表中第i個元素IndexOf(x); 查找滿足給定條件的數(shù)據(jù)元素Del(k,i); 刪除線性表中的第i個數(shù)據(jù)元素Add(k,i); 在線性表的第i個位置之前插入一個新的數(shù)據(jù)元素7n基本運算qInit（）；初始化線性表qClear（）；表

5、置空qPre（）；查找表中第i個元素的前驅qNext（）；查找表中第i個元素的后繼qPrint（）；顯示表中的數(shù)據(jù)qSetStart（）；定位線性表第一個元素qSetEnd（）；定位線性表最后一個元素n實際應用中，根據(jù)不同的要求選擇適當?shù)幕具\算解決問題Linear ListsLinear Listsnha和hb分別是兩個線性表，他們代表兩個的數(shù)據(jù)元素排列非遞減有序的數(shù)字序列串，要求使用線性表的基本操作，實現(xiàn)這兩個數(shù)字串的合并操作Merge ()，產生一個新的數(shù)據(jù)元素非遞減有序的數(shù)字串hc。 Linear ListsnMerge()ha.setstart(); hc.setStart();fo

6、r(int i = 1 ;i= ha.length; i+)tmpdata = ha.getValue();hc.insert(tmpdata);hc.next(); ha.next();hb.setStart();for(int i = 1; i = hb.length; i+)tmpdata = hb.getValue();hc.setStart(); tmpdata2 = hc.getValue();while(tmpdata2 tmpdata) hc.next(); tmpdata2 = hc.getValue(); hc.insert(tmpdata);hb.next()nnTime

7、 Cost ha.length + ha.length*hb.lengthLinear ListsnMerge()ha.setStart(); hb.setStart();hc.setStart();int i= 1,j=1;While(i= ha.Length & j=hb.Length)tmp1= ha.getValue(i); tmp2 = hb.getValue(j);if(tmp1= tmp2) hc.insert(tmp1); ha.next(); else hc.insert(tmp2); hb.next();hc.next(); While(i= ha.Length) tmp1

8、= ha.getValue(i); ha.next(); hc.insert(tmp1); hc.next(); While(j= hb.Length) tmp2= hb.getValue(j); hb.next(); hc.insert(tmp2); hc.next(); nnTime Cost: ha.length + hb.lengthLinear Lists4Implementation of ListsnThere are two standard approaches to implementing lists, qthe array-based list, （順序存儲結構）qth

9、e linked list.（鏈式存儲結構）Sequential Listsn在內存中開辟連續(xù)的存儲空間，用連續(xù)的存儲單元依次存放線性表的數(shù)據(jù)元素n順序存儲的線性表，稱為順序表 特點 邏輯上相鄰的數(shù)據(jù)元素，其物理位置也相鄰 利用物理位置上的關系，反映元素的邏輯關系The elements are stored in a consecutive storage area one by one Sequential ListsnWith ordered pair to express “Storage is adjacent to” ， nLoc(ai)=loc(ai-1)+CnUnnecessa

10、ry to store logic relationship nFirst data component location can decide all data elements locations nData members :Datatype elementsMaxNumber;int size ;Sequential ListsnBasic operations:/* Initialize a List, Set size to 0, Set space to NULL*/Void Init()int i = 0;size = 0;for(i = 0;i MaxNumber; i+)e

11、lementsi = NULL;Sequential ListsThe Method isEmptyn/* return true if the List is empty */ boolean isEmpty() if(size = = 0) retun true;elsereturn false;The Method getValuen/* return element with specified index*/datatype getValue(int index)if(index = size)printf(“the input error”)；return NULL;elseret

12、urn elements index;The Method IndexOfn /* return index of first occurrence of the Element, return -1 if theElement not in list */int IndexOf(datatype theElement)/ search element for theElementint i = 0;for (int i = 0; i size; i+)if (element i .equals(theElement)return i;/ theElement not foundreturn

13、-1; n插入算法q在線性表的第i個數(shù)據(jù)元素前，插入一個新數(shù)據(jù)元素，使線性表的長度從n變成n+1n(a1, , ai-1, ai, , an)n(a1, , ai-1, x, ai, , an) The Method Add內存a1a2aiai+1an01i-1 下標len-1ilen12i元素序號i+1lenlen+1內存a1a2aiai+1an01i-1 下標len-1ilen12i元素序號i+1lenlen+1an-1xThe Method Addn判斷線性表的存儲空間是否已滿，若已滿，則進行“溢出”處理n檢查i值是否超出允許的范圍(1ilen+1)，若超出，則進行“超出”處理n如果上述

14、條件都允許,則將最后一個元素到第i個元素依次向后移動一個位置n將新的數(shù)據(jù)元素寫到第i個位置上n線性表的長度增加1,插入成功The Method AddThe Method Addvoid add(Object theElement, int index)if(index size)printf(“the index error”)；else/ right one positionfor (int i = size - 1; i = index; i-) elementi + 1 = elementi;elementindex = theElement;size+;Time cost of Ad

15、dn插入算法的主要時間用于移動數(shù)據(jù)元素，該語句循環(huán)執(zhí)行的次數(shù)為n-i+1n當i=n+1時，移動次數(shù)為0n當i=1時,移動次數(shù)為nn算法的最壞情況時間復雜度：O(n)n算法的最好情況時間復雜度：O(1)Average time cost of AddnTo get the average shift times of the insertnSet to insert an element at the position i, the shift times is size i +1nAnd the probability of this operation is 1/size+1nThe ave

16、rage cost is =size/211)1(11sizeiisizesizeThe Method Deln刪除操作q將線性表的第i個數(shù)據(jù)元素刪去，使長為n的線性表變成長為n-1的線性表q(a1 ,.,ai-1 ,ai ,ai+1 ,.,an )q(a1 ,.,ai-1 ,ai+1 ,.,an )The Method Del內存a1a2aiai+1an01i-1 下標n-1in12i元素序號i+1nn+1內存a1a2ai+1 下標01i-1n-2in-112i元素序號i+1n-1nanai+2The Method Deln算法思路q判斷i值是否超出允許的范圍(1ilen），若是，則進行“超

17、出范圍”處理；q否則，保存第i個元素的值；q將第i個元素后的所有元素依次向前移動一個位置；q線性表長度減1，刪除成功The Method Deldatatype Del(int index)if(index = size)打印輸出(“the input error”)；return NULL;else/ valid index, shift elements with higher indexdatatype delElement = elementindex;for (int i = index + 1; i Max - 1) output (“Error”); exit(-1);ck .coef = co; ck .exp = e;poly polyAdd(struct poly a, struct poly b, struct poly c, int at, int bt) in