1、第2章、基本線性表,2020/8/4,2,引 言 線性表是一種線性數(shù)據(jù)結(jié)構(gòu)，其用途非常廣泛，可用于信息檢索、存儲管理、模擬技術(shù)和通信等領(lǐng)域。,2020/8/4,3,2.1線性表的基本概念,線性表是最常用且最簡單的一種數(shù)據(jù)結(jié)構(gòu)。 線性表是具有相同屬性數(shù)據(jù)元素的一個有限序列。通常表示成下列形式： L=( a1, a2,.,ai-1,ai,ai+1,.,an) 在線性表L中， a1為開始結(jié)點， an為終端結(jié)點。結(jié)點ai-1是結(jié)點ai的前驅(qū)結(jié)點，結(jié)點ai+1是結(jié)點ai的后繼結(jié)點。 n（n0）表示線性表的長度 當n=0時，表示線性表是一個空表。,a1,a2,ai-1,ai,ai+1,an,2020/8/

2、4,4,線性表中數(shù)據(jù)元素的含義廣泛，在不同的具體情況下，可以有不同的含義。 英文字母表 （A，B，C，Z） 某公司2007年上半年每月產(chǎn)值表(單位：萬元) （400，320，450，500，480，600） 學生信息表,體現(xiàn)在 順序關(guān)系上,記錄排列為順序關(guān)系,2020/8/4,5,線性表的特點 開始結(jié)點只有后繼結(jié)點而沒有前驅(qū)結(jié)點 終端結(jié)點只有前驅(qū)結(jié)點而沒有后繼結(jié)點 除了開始結(jié)點和后繼結(jié)點以外，其余結(jié)點都有且只有一個前驅(qū)結(jié)點和一個后繼結(jié)點,線性結(jié)構(gòu)的基本特性為一對一的關(guān)系,2020/8/4,6,2.2 線性表的相關(guān)操作,線性表的基本操作 初始化線性表 求線性表的長度 取線性表L中的第i個元素 修

3、改線性表中的第個元素 刪除線性表中的第個元素 在線性表中第個元素之后（前）插入一個新元素,2020/8/4,7,2.3 線性表的順序存儲結(jié)構(gòu)及操作實現(xiàn),線性表的存儲方式有順序存儲和鏈式存儲。 線性表的順序存儲是指用一組地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素。 邏輯關(guān)系相鄰，物理位置相鄰 LOC(ai)=LOC(ai-1)+C LOC(ai)=LOC(a1)+(i-1)*C,一個元素所占的存儲量,基地址,2020/8/4,8,順序存儲結(jié)構(gòu)是一種隨機存取結(jié)構(gòu)。 在高級語言環(huán)境中，常用一維數(shù)組來存儲線性表。,2020/8/4,9,順序表的基本操作 初始化 為更好體現(xiàn)信息隱蔽原則和數(shù)據(jù)抽象原則，把

4、順序表封裝起來。(使用類模板) 模板分為類模板和函數(shù)模板 類模板就是建立一個通用類，其數(shù)據(jù)成員的類型、成員函數(shù)的返回類型和參數(shù)類型都不具體指定，用一個虛擬類型來代表。當使用類模板建立對象時，系統(tǒng)會根據(jù)實參的類型來取代類模板中的虛擬類型從而實現(xiàn)不同類的功能。,2020/8/4,10,類模板的一般說明形式是 templateclass className /類聲明體 ; 建立類模板后，可用下列方式創(chuàng)建類模板的實例 className object; 類模板是模板的定義，不是一個實實在在的類，定義中用到通用類型參數(shù)。 模板類是實實在在的類定義，是類模板的實例化。類定義中參數(shù)被實際類型所代替。,202

5、0/8/4,11,順序表類,/文件名sq_LList.h #include using namespace std; template /模板聲明，數(shù)據(jù)元素虛擬類型為T class sq_LList /順序表類 private: /數(shù)據(jù)成員 int mm; /存儲空間容量 int nn; /順序表長度 T *v; /順序表存儲空間首地址 public: /成員函數(shù) sq_LList() mm=0; nn=0; return; sq_LList(int); /建立空順序表，申請存儲空間 void prt_sq_LList(); /順序輸出順序表中的元素與順序表長度 int flag_sq_LLi

6、st(); /檢測順序表的狀態(tài) void ins_sq_LList(int, T); /在表的指定元素前插入新元素 void del_sq_LList(int); /在表中刪除指定位置的元素 ;,2020/8/4,12,插入,2020/8/4,13,假設(shè)線性表的存儲空間為m個單元，線性表的長度為n（nn時，認為在最后一個元素之后插入； 當i1時，認為在第1個元素之前插入； 將第i個元素至尾元素逐一向后移動一個位置。 將新元素插入到第i個的位置上，并將順序表長度增加1。,2020/8/4,14,/在表的指定元素前插入新元素 template void sq_LList:ins_sq_LList(

7、int i, T b) int k; if (nn=mm) /存儲空間已滿，上溢錯誤 cout nn) i=nn+1; /默認為在最后一個元素之后插入 if (i=i; k-) vk=vk-1; /從最后一個元素直到第i個元素均后移一個位置 vi-1=b; /插入新元素 nn=nn+1; /順序表長度加1 return; ,2020/8/4,15,刪除,2020/8/4,16,假設(shè)線性表的存儲空間為m個單元，線性表的長度為n（nn或i1時，表示表中沒有這個元素。 將表中第i+1個元素至尾元素逐一向前移動一個位置，并將順序表長度減少1。,2020/8/4,17,/在順序表中刪除指定位置的元素 t

8、emplate void sq_LList:del_sq_LList(int i) int k; if (nn=0) /順序表為空，下溢錯誤 cout nn) /順序表中沒有這個元素 cout Not this element in the list! endl; return; for (k=i; knn; k+) vk-1=vk;/從第i+1個元素直到最后一個元素均前移一個位置 nn=nn-1; /順序表長度減1 return; ,2020/8/4,18,在實際應(yīng)用中，應(yīng)當在順序表中插入新元素時，先調(diào)用檢測函數(shù)flag_sq_LList()檢測一下順序表是否處于滿的狀態(tài)，如果順序表非滿，才

9、調(diào)用插入函數(shù)ins_sq_LList()進行插入；同樣道理在刪除輸出元素時檢測順序表是否為空，非空才調(diào)用刪除函數(shù)del_sq_LList()進行刪除。,2020/8/4,19,/檢測順序表的狀態(tài)（滿、空或正常） template int sq_LList:flag_sq_LList() if (nn=mn) return(-1); /存儲空間已滿，返回-1 if (nn=0) return(0); /順序表為空，返回0 return(1); /正常返回1 ,2020/8/4,20,/建立空順序表，申請存儲空間（使用函數(shù)模板） template sq_LList:sq_LList(int m)

10、mm=m; /存儲空間容量 v=new Tmm; /動態(tài)申請存儲空間 nn=0; /順序表長度為0，即建立空順序表 return; ,2020/8/4,21,/順序輸出順序表中的元素與順序表長度 template void sq_LList:prt_sq_LList() int i; cout nn= nn endl; for (i=0; inn; i+) cout vi endl; return; ,2020/8/4,22,時間復(fù)雜度分析 插入和刪除這兩種操作算法的執(zhí)行時間主要用在元素的移動操作上，而移動元素的次數(shù)取決于插入或刪除元素的位置。 假設(shè)Pi是在第i個元素之前插入一個元素的概率,

11、則在長度為n的線性表中插入一個元素時所需移動元素次數(shù)的平均次數(shù)為,2020/8/4,23,假設(shè)i是刪除第個元素的概率, 則在長度為的線性表中刪除一個元素時所需移動元素次數(shù)的平均次數(shù)為 假定在線性表的任何位置上插入和刪除元素都是等概率的，即,2020/8/4,24,則 可見, 在順序表中插入或刪除一個元素時, 平均要移動表中大約一半的數(shù)據(jù)元素。若表長為n, 前兩個算法的時間復(fù)雜度都為O(n)。,2020/8/4,25,練習 建立容量為100的空順序表，然后輸出該空順序表，在該順序表中依次在第0個元素前插入1.5，在第1個元素前插入2.5以及在第4個元素前插入3.5，再輸出該順序表。依次刪除該順序

12、表中的第0個元素以及第1個元素，再輸出該順序表。,2020/8/4,26,/sq_app1.cpp #include sq_LList.h int main() sq_LList s1(100); /建立容量為100的空順序表對象s1 cout 第1次輸出順序表對象s1: endl; s1.prt_sq_LList(); s1.ins_sq_LList(0,1.5);/在第0個元素前插入1.5 s1.ins_sq_LList(1,2.5);/在第1個元素前插入2.5 s1.ins_sq_LList(4,3.5);/在第4個元素前插入3.5 cout 第2次輸出順序表對象s1: endl; s1

13、.prt_sq_LList(); s1.del_sq_LList(0); /刪除順序表s1中的第0個元素 s1.del_sq_LList(2); /刪除順序表s1中的第0個元素 cout 第3次輸出順序表對象s1: endl; s1.prt_sq_LList(); return 0; ,2020/8/4,27,結(jié)論 線性表采用順序存儲結(jié)構(gòu)操作時，需大量移動數(shù)據(jù)元素，效率較低。 由于是靜態(tài)存儲結(jié)構(gòu)，需預(yù)先定義大小確定的數(shù)組，容量有限。 適于直接(隨機)存取操作。,2020/8/4,28,2.4 線性表的鏈式存儲結(jié)構(gòu)及其操作實現(xiàn),鏈式存儲是給每個結(jié)點附加指針字段，用于存儲相鄰結(jié)點的存儲地址，使線性

14、表容易修改。 用鏈接方式存儲的線性表稱為鏈表。 線性表的鏈表存儲結(jié)構(gòu)的特點, 是可用內(nèi)存空間中一組任意的存儲單元（可以是地址連續(xù)的, 也可以是不連續(xù)的）來存儲線性表的數(shù)據(jù)元素。,2020/8/4,29,在鏈表中，每個結(jié)點所占的存儲空間可以分為兩部分：數(shù)值域和指針域 數(shù)值域用來存放結(jié)點的數(shù)值 指針域用來存放結(jié)點之間的相鄰關(guān)系,2020/8/4,30,單鏈表,單鏈表 單鏈表的每個結(jié)點都由數(shù)值域和一個指針域組成。 結(jié)點的存儲結(jié)構(gòu)定義如下 struct node datatype data; node *next; ;,數(shù)值域,指針域,data,next,存儲每個結(jié)點的數(shù)值,存儲該結(jié)點后繼結(jié)點的地址,

15、struct linklist node *head； int n； ；,2020/8/4,31,頭指針 線性表中第一數(shù)據(jù)元素a1的存儲地址，稱為線性表的頭指針 在第一個結(jié)點之前虛加一個“頭結(jié)點”，以指向頭結(jié)點的指針為鏈表的頭指針 線性表為空表時，頭結(jié)點的指針域為空,2020/8/4,32,示例 node q,*p; q.data = 3; q.next = *; p = ,2020/8/4,33,單鏈表的查找（在單鏈表中查找第i個結(jié)點，若存在，則返回該結(jié)點的地址，否則返回表頭結(jié)點的地址。） 引入整型變量j和指針變量q，令j的初始值為0，q指向表頭結(jié)點； 在ji的情況下，反復(fù)向后移動指針q，并

16、且q每往后移動一次，j就加1； 當這個循環(huán)過程結(jié)束時，q指向第i個結(jié)點,2020/8/4,34,node *search（linklist L，int i） node *q; int j; q=L.head; j=0; if(i=1) ,思考，不帶頭結(jié)點時應(yīng)如何修改？,j = 1,2020/8/4,35,單鏈表的插入（在單鏈表的第i個結(jié)點的后面插入一個數(shù)值為x的新結(jié)點）,2020/8/4,36,插入新結(jié)點的合法位置為0iL.n時，才能正確插入；否則不能進行插入操作 為結(jié)點q分配存儲單元，將x存入新結(jié)點的數(shù)值字段中 將p結(jié)點指針字段的值存入q結(jié)點的指針字段中 將q結(jié)點地址存入p結(jié)點的指針字段中，

17、最后令線性表長度加1,2020/8/4,37,void insert(linklist /線性表的長度加1 ,2020/8/4,38,單鏈表的刪除（刪除線性表的第i個結(jié)點） 判斷參數(shù)i是否正確（iL.n時，不能刪除） 確定第i-1個結(jié)點的地址p 將p結(jié)點指針字段的值存入待刪除結(jié)點中，用變量q表示 將q結(jié)點指針字段的值存入p結(jié)點的指針字段中 釋放q結(jié)點所占用的存儲單元 線性表的長度L.n減1,2020/8/4,39,void delete(linklist ,2020/8/4,40,單鏈表的創(chuàng)建 建立一個線性鏈表，其元素值依次為從鍵盤輸入的正整數(shù)（以輸入一個非正整數(shù)為結(jié)束），然后依次輸出線性表中

18、的各元素值，并刪除各結(jié)點,2020/8/4,41,線性單鏈表類 將線性鏈表的數(shù)據(jù)和基本操作（初始化、掃描輸出、插入與刪除鏈頭元素等）封裝成一個線性單鏈表類,2020/8/4,42,單鏈表類 /文件名linked_List.h #include using namespace std; /定義結(jié)點類型 template /T為虛擬類型 struct node T data; node *next; ; template /模板聲明,數(shù)據(jù)元素虛擬類型為T class linked_List /單鏈表類 private: /數(shù)據(jù)成員 node *head; /鏈表頭指針 int n; /線性表的長度

19、為n public: /成員函數(shù) linked_List(); /構(gòu)造函數(shù),建立空鏈表 int flag_linked_List(); /檢測單鏈表狀態(tài)，是否為空鏈表 void prt_linked_List(); /從頭指針開始掃描輸出鏈表中的元素 void ins_linked_List(T); /將新元素插入到鏈頭 T del_linked_List(); /刪除鏈頭元素 ;,2020/8/4,43,/構(gòu)造函數(shù),建立空鏈表 template linked_List:linked_List() head=NULL; n=0; return; /檢測單鏈表狀態(tài) template int li

20、nked_List:flag_linked_List() if (head=NULL) return(0); /若空鏈表則函數(shù)返回0 return(1); /正常返回1 ,2020/8/4,44,/從頭指針開始掃描輸出鏈表中的元素 template void linked_List:prt_linked_List() node *p; p=head; if (p=NULL) cout data next; while (p!=NULL); return; ,2020/8/4,45,/將新元素插入到鏈頭 template void linked_List:ins_linked_List(T x)

21、 node *p; p=new node; p-data=x; p-next=head; head=p; n+; return; ,2020/8/4,46,/刪除鏈頭元素 template T linked_List:del_linked_List() T y; node *p; if (head=NULL) cout data; head=p-next; delete p; n-; return(y); /返回刪除的元素 ,2020/8/4,47,練習 定義一個空單鏈表，掃描輸出該單鏈表。 依次在單鏈表的鏈頭插入元素10、20、30、40，掃描輸出該單鏈表中的元素。 連續(xù)兩次刪除鏈頭元素，掃

22、描輸出該單鏈表中的元素,2020/8/4,48,/文件名linklist_App.cpp #include linked_List.h int main() linked_List s; /定義一個空單鏈表s cout第1次從頭指針開始掃描輸出單鏈表s中的元素：endl; s.prt_linked_List(); s.ins_linked_List(10); /在單鏈表s的鏈頭插入元素10 s.ins_linked_List(20); /在單鏈表s的鏈頭插入元素20 s.ins_linked_List(30); /在單鏈表s的鏈頭插入元素30 s.ins_linked_List(40); /在

23、單鏈表s的鏈頭插入元素40 cout第2次從頭指針開始掃描輸出單鏈表s中的元素：endl; s.prt_linked_List(); if(s.flag_linked_List() /若鏈表非空，則刪除鏈頭元素 cout刪除的鏈頭元素是：s.del_linked_List()endl; if(s.flag_linked_List() /若鏈表非空，則刪除鏈頭元素 cout刪除的鏈頭元素是：s.del_linked_List()endl; cout連續(xù)兩次刪除鏈頭元素后從頭指針開始掃描輸出單鏈表s中的元素：endl; s.prt_linked_List(); return 0; ,2020/8/

24、4,49,思考 在單鏈表類中請設(shè)計并實現(xiàn)成員函數(shù) void search_linked_List(int); 在單鏈表中查找第i個結(jié)點，若存在，打印該結(jié)點值 void ins_linked_List(int,T); 在單鏈表的第i個結(jié)點后面插入一個數(shù)值為x的新結(jié)點 void del_linked_List(int); 刪除線性表的第i個結(jié)點,如何查找值為x的某個元素呢？,2020/8/4,50,練習 定義一個空單鏈表，掃描輸出該單鏈表。 依次在單鏈表的鏈頭插入元素10、20、30、40，再掃描輸出該單鏈表中的元素。 在第3個元素后面插入元素50，掃描輸出該單鏈表中的元素。 連續(xù)兩次刪除鏈頭元素

25、，掃描輸出該單鏈表中的元素。 在第2個元素后面插入元素60，掃描輸出該單鏈表中的元素。 刪除第3個元素，掃描輸出該單鏈表中的元素。 查找單鏈表中第2個元素的值并輸出。,2020/8/4,51,循環(huán)單向鏈表,把單鏈表的首尾相連就構(gòu)成了“循環(huán)單向鏈表”，即使單鏈表的最后一個結(jié)點的指針字段指向第一個結(jié)點。,2020/8/4,52,使用循環(huán)鏈表的主要優(yōu)點是, 從表中任一結(jié)點出發(fā)均可找到表中其它結(jié)點。 在循環(huán)單鏈表中，用表尾指針Rear代替表頭指針Head的形式稱為“帶表尾指針的循環(huán)鏈表”,2020/8/4,53,兩個線性表進行首尾相連的合并操作,node *p; p = rear1-next; rear1-next = rear2-next; rear2-next = p;,2020/8/4,54,雙向鏈表,雙鏈表的每個結(jié)點由兩個指針域和一個數(shù)值域組成。,2020/8/4,55,雙鏈表的插入(P21)