《數(shù)據(jù)結(jié)構(gòu)C語言 胡學(xué)鋼線性表PPT課件》由會員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)C語言 胡學(xué)鋼線性表PPT課件（43頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、1第二章 線性表 第二章 線性表 2.1 線性表的定義和運算 2.2 順序表 2.3 鏈表 2.4 其它結(jié)構(gòu)形式的鏈表 2.5 串 第1頁/共43頁22.1 線性表的定義和運算 p定義： 線性表L是由n個元素a1，a2，an組成的 有限 序列。 記作 L =（a1，a2，an） 其中n=0為表長；n=0時為L空表，記作L=（）p特性： A、只有一個第一個元素和一個最后一個元素； B、除第一個元素外其他元素有且僅有一個直接前趨（前驅(qū)）； C、除最后一個元素外其他元素有且僅有一個直接后繼p元素ai的含義： 同一表中，元素類型相同。在不同的場合有不同的含義 例：字母表（A，B，C，D，Z）； 數(shù)字表

2、（0，1，2，3，4，9）； 每月天數(shù)（31,29,31,30,31,30,31,31,30,31,30,31）;第2頁/共43頁32.1 線性表的定義和運算 運算： (1)初始化 initial_List(L)建立線性表的初始結(jié)構(gòu)，即建空表 (2)求長度 List_length(L) 即求表中的元素個數(shù)(3)按序號取元素 get_element(L,i) 取出表中序號為i的元素 (4)按值查找元素 List_locate(L,x) 取出指定值為x的元素，若存在則返回其地址；否則返回特殊值(5)插入 List_insert(L,i,x) 在表L的第i個位置上插入值為x的元素( 1=i=n+1)

3、(6)刪除 List_delete（L,i）刪除表L中序號為i的元素1=ilistlen=0; int List_length（seqlist L） return L.listlen ; void get_element（seqlist L，int i, elementtype &x） if（ i L.listlen） error(“超出范圍”); else x = L.datai-1; int List_locate（seqlist L，elementtype x） int i; for (i=0; ilistlen=maxlen）error（“overflow”）; else if（iL-

4、listlen+1） error(“position error”）; else for（j=L-listlen-1;j=i-1;j-） L-dataj+1=L-dataj; L-datai-1=x; L-listlen+; a1 a2 a3 ai an 0 1 2 i-1 n-1 maxlen-1x條件：順序表不滿； 序號正確，在1, n+1中操作：ai an后移; 填入x; listlen +算法分析第6頁/共43頁72.2 順序表 刪除void List_delete(seqlist *L,int i) int j; if (L-listlenL-listlen|i=0) error(“

5、刪除位置出錯”); else for ( j=i;jlistlen-1;j+) L-data j-1=L-data j; L-listlen-; a1 a2 a3 ai an 0 1 2 i-1 n-1 maxlen-1算法分析第7頁/共43頁82.2 順序表 算法分析：插入時 在i=1,2,n+1，元素移動的次數(shù)分別為n,n-1,0。 在等概率的情況下，平均移動(n+1)n/2(n+1)=n/2次刪除時 在i=1,2,n，元素移動的次數(shù)分別為n-1,n-2,0。 在等概率的情況下，平均移動(n-1)n/2n=(n-1)/2次結(jié)論：n較大時，大量移動元素，耗時解決：考慮不移動元素教材P17例第

6、8頁/共43頁92.3 鏈表基本結(jié)構(gòu)以鏈接形式連接元素次序。a1a2a3a4 L=(a1,a2,a3,a4)結(jié)點包括 元素和地址。datanext第9頁/共43頁102.3 鏈表存儲實現(xiàn)（靜態(tài)鏈表）1、靜態(tài)鏈表用數(shù)組C3A2B0D5F-1E4data next012345L=(A,B,C,D,E,F)head第10頁/共43頁112.3 鏈表存儲實現(xiàn)（動態(tài)鏈表）2、動態(tài)鏈表用指針和動態(tài)變量實現(xiàn)（1）結(jié)點結(jié)構(gòu)datanext（2）類型定義 typedef struct elementtype data; node *next; node; 引用：node *head；第11頁/共43頁122.3

7、 鏈表圖例a1a2a3a4 Head*HeadHead-next首元素第12頁/共43頁132.3 鏈表基本運算 運算： (1)初始化 initial_List(L)建立表的初始結(jié)構(gòu)，即建空表 (2)求長度 List_length(L) 即求表中的元素個數(shù)(3)按序號取元素 get_element(L,i) 取出表中序號為i的元素 (4)按值查找元素 List_locate(L,x) 取出指定值為x的元素，若存在則返回其地址；否則返回特殊值(5)插入 List_insert(L,i,x) 在表L的第i個位置上插入值為x的元素( 1=i=n+1)(6)刪除 List_delete（L,i）刪除表

8、L中序號為i的元素1=inext=P-next; P-next=S;注意：兩個操作不能交換p 如果是作為第一個結(jié)點插入，過程如下：S-next=head; head=S;a1a2a3 a4 headxS第14頁/共43頁152.3 鏈表討論 (引入頭結(jié)點)為保持插入操作一致，引入頭結(jié)點。注意：頭結(jié)點與首元素的區(qū)別。a1a2a3 xh e adSPS-next=P-next; P-next=S;第15頁/共43頁162.3 鏈表討論(刪除操作)p 刪除（一般位置）：假設(shè)被刪除的前一個結(jié)點的指針P已找到：Pa1a2a3a5 h e ada4 P-next=P-next-next;p 如果是刪除第一

9、個結(jié)點，過程如下：head=head-next;a1a2a3a5 h e ada4 p 討論結(jié)果：引入頭結(jié)點P-next=P-next-next;a1a2a4 h e ada3 P第16頁/共43頁172.3 鏈表運算的實現(xiàn)（有頭結(jié)點） 1、初始化單鏈表（建空表）Lvoid initial_List(node &*L) L = new node; /L = (node *)malloc(sizeof(node);L - next = NULL;第17頁/共43頁182.3 鏈表求表長（1）2、求單鏈表表長a1a2a3 LPlen=0P=L-next;len=0;P!=NULLreturn(le

10、n);P=P-next;len+;YNint List_length(node *L)P=L-next; len=0; while(P!=NULL) P=P-next; len+; return(len);第18頁/共43頁192.3 鏈表求表長（2）2、求單鏈表表長a1a2a3 Lint List_length(node *L)P=L;len=0; while(P-next!=NULL) P=P-next; len+; return(len);Plen=0P=L;len=0;P-next!=NULLreturn(len);P=P-next;len+;YN第19頁/共43頁202.3 鏈表按序

11、號取值3、按序號取值返回指向結(jié)點的指針,否則返回NULLa1a2a3 LPj=0P=L;j=0;P-next!=NULLreturn(P);P=P-next;j+;YNj=iYNreturn(P);第20頁/共43頁212.3 鏈表按值查詢 4、按值查詢 返回元素結(jié)點指針，否則返回NULL；a1a2a3 LPP=L-next;P-data!=xreturn(P);P=P-next;YNP!=NULLNYreturn(P);node *locate(node *L,elementtype x) P=L-next; while(P!=NULL&P-data!=x) P=P-next; return

12、(P); 第21頁/共43頁222.3 鏈表 插入5、插入ai-1aixSP分析：A、搜索位置；B、裝入x；C、插入x；P=get(L,i-1);if(P=NULL) error(“序號錯”);else S = new node; S-data=x; S-next=P-next; P-next=S; void insert(node &*L,elementtype x,int i)第22頁/共43頁232.3 鏈表 刪除6、刪除Pai-1aiai+1 分析：A、搜索位置；B、刪除結(jié)點；C、釋放結(jié)點；P=get(L,i-1);if(P=NULL) error(“序號錯”);else u=P-ne

13、xt; P-next=P-next-next; delete u; /free(u); void delete(node &*L,int i)第23頁/共43頁242.3 鏈表單鏈表的應(yīng)用(頭結(jié)點)鏈表的遍歷：訪問鏈表每個結(jié)點一次且僅一次?；舅惴ㄈ缦拢簐oid print(node *L) P=L-next; while(P!=NULL) visit(P-data); P=P-next; a1a2a3 LP第24頁/共43頁252.3 鏈表單鏈表的應(yīng)用(頭結(jié)點) 設(shè)計算法，判斷帶頭結(jié)點單鏈表L是否遞增？若遞增，則返回true，否則返回false。分析：（1）鏈表空，返回true；（2）只有一

14、個結(jié)點，返回true；（3）每個元素都小于其直接后繼，返回true；否則，返回false；第25頁/共43頁262.3 鏈表單鏈表的應(yīng)用(頭結(jié)點)由分析得如下流程圖：P=L-next;P=P-next;P!=NULLP-next!=NULLP-datanext-dataYYY返回true返回trueNN返回fasleNbool Judge(node *L) P=L-next; if(P=NULL) return(true); while(P-next!=NULL) if(P-datanext-data) P=P-next; else return(false); return(true); 第

15、26頁/共43頁272.3 鏈表構(gòu)造鏈表 構(gòu)造鏈表 基本方法：從鍵盤輸入數(shù)據(jù)，每讀入一個元素，產(chǎn)生結(jié)點裝入，插入鏈表中，重復(fù)上述操作X不是結(jié)束符cin xs = new node;s - data = x;插入操作n 討論：產(chǎn)生結(jié)點：s= new node; s-data=x;插入鏈表：插入位置如何確定， 有 表頭/表尾 兩個位置可選 頭插法 尾插法重復(fù)上述操作： 何時結(jié)束?a1a2a3 L第27頁/共43頁282.3 鏈表頭插法頭插法運算實現(xiàn)：void create_List(node *&L)L= new node; L-next=NULL;cin x;while( x != End_of

16、_Num ) u = new node; u-data=x; u-next=L-next; L-next=u; cinx;a1a2an UxLX不是結(jié)束符cin xu= new node;u - data = x;u-next=L-next;L-next = u;第28頁/共43頁292.3 鏈表尾插法尾插法運算實現(xiàn)：void create_List(node * & L)L=new node;R=L; /尾指針cinx;while(x!=End_of_Numo) u=new node; u-data=x; R-next=u; R=u; cinx;R-next=NULL;a1a2an x uL

17、R第29頁/共43頁302.3 鏈表練習(xí)題P 31 例2.6、2.7、2.81）鏈表A，B，設(shè)計算法求CAB，并分析其時間復(fù)雜度2）遞增鏈表A，B，設(shè)計算法求CAB，并分析其時間復(fù)雜度第30頁/共43頁312.4 其他結(jié)構(gòu)形式的鏈表 單循環(huán)鏈表（優(yōu)點：可在表中反復(fù)搜索 ）初始化操作為： head = new node; head - next = head;求長度： p = head - next; n = 0; while ( p != head ) p = p - next; n + ;應(yīng)用： m人開m把鎖問題（每人一把鑰匙，要求所有鎖都能開） 約瑟夫環(huán)問題（利用循環(huán)隊列，不帶頭結(jié)點的循環(huán)

18、鏈表都可）a1a2an headhead第31頁/共43頁322.4 其他結(jié)構(gòu)形式的鏈表 帶尾指針的單循環(huán)鏈表（優(yōu)點：表尾操作方便 ） 應(yīng)用：將A、B兩鏈表首尾相連 實現(xiàn)部分語句為： u = A - next; 1:A - next = B - next - next; 2: free(B-next) ; 3:B - next = u; 4:A = B; a1a2an reara1a2an a1a2an BAu123第32頁/共43頁332.4 其他結(jié)構(gòu)形式的鏈表p雙鏈表（優(yōu)點：求前驅(qū)后繼都方便） 帶頭結(jié)點 或者 不帶頭結(jié)點 typedef struct elementtype data; d

19、node * prior, * next; dnode; p雙循環(huán)鏈表prior data next a1a2 an head第33頁/共43頁342.4 其他結(jié)構(gòu)形式的鏈表初始化： head = new node; head - prior = head - next = head;求長度查找類似插入時： s - prior = p - prior; s - next = p; p - prior = s; s - prior - next = s;刪除時： p - prior - next = p - next; p - next - prior = p - prior; delete p

20、;應(yīng)用：判斷雙循環(huán)鏈表是否對稱 雙循環(huán)鏈表倒置（動指針、動結(jié)點值）head ai ai+1 xsp ai-1 ai ai+1p第34頁/共43頁352.4 其他結(jié)構(gòu)形式的鏈表 小結(jié)： 線性表 邏輯上相鄰的元素 順序表 物理上也相鄰 插入、刪除需移動元素 鏈表 物理上不一定相鄰 插入、刪除不需移動元素第35頁/共43頁362.5 串 定義： 串：由n個字符a1,a2,an組成的有限序列（n=0）元素是字符的線性表，記作 S=“a1,a2,an”，其中n為串長度。n=0時為空串。 注意：空串和空格串的區(qū)別?？沾疀]有元素。空格串元素是空格符。子串 串S中若干個連續(xù)的字符組成的序列。書上書上P37例例

21、第36頁/共43頁372.5 串 運算： 基本運算 賦值=：將一個串值S1傳送給一個串名S。如：S=S1 求長度length(S)：返回串S的長度值。 連接運算+：將S1和S2連接成一個新串（如S1+S2） 求子串substr（S,i,j）：返回串S從第i個元素開始的j個元素所組成的子串。 串比較strcmp(S1,S2)：比較兩個串的大小。對齊按ASCII碼進行比較。結(jié)果為-1、0、1第37頁/共43頁382.5 串常用運算：可由基本運算實現(xiàn) 插入（insert（S,i,S1）：將子串S1插入到串S的從第i個字符開始的位置上。 刪除（deletestr（S,i,len）：刪除串S中從第i個字

22、符開始的len個字符。 替換（replace(S,i,len,S1)）：用字串S1替換串S中從第i個字符開始的len個字符。 定位（index（S,S1）/模式匹配 例：S=“a1,a2,an”，在S的第i個位置插入S1 運算為 insert(S,i,S1)，為常用運算 可操作為：X1=substr(S,1,i-1,) X2 =substr(S,i, length() - (i - 1),) S = X1 + S1 + X2 /為基本運算 兩者可互換第38頁/共43頁392.5 串 存儲結(jié)構(gòu) 順序串 緊湊格式： 優(yōu)點：節(jié)省空間； 缺點：運算不方便。 非緊湊格式：優(yōu)點：運算方便； 缺點：浪費空間

23、。 鏈串 結(jié)點大?。ㄒ?guī)模）：大于1： 等于1： S a1 a2 a3ana4.a3.a2.a1a8.a7.a6.a5ana1a2a3a4a5a6a7a8an 第39頁/共43頁40第二章 線性表 第二章 線性表 2.1 線性表的定義和運算 2.2 順序表 2.3 鏈表 2.4 其它結(jié)構(gòu)形式的鏈表 2.5 串 第40頁/共43頁41第二章第二章 線性表線性表 重點重點 掌握順序存儲結(jié)構(gòu)的描述方法。掌握順序存儲結(jié)構(gòu)的描述方法。 掌握線性表在順序存儲結(jié)構(gòu)中實現(xiàn)基本運算（查找、插掌握線性表在順序存儲結(jié)構(gòu)中實現(xiàn)基本運算（查找、插入、刪除、合并等）的算法及分析入、刪除、合并等）的算法及分析 掌握鏈?zhǔn)酱鎯Y(jié)構(gòu)的描述方法。掌握鏈?zhǔn)酱鎯Y(jié)構(gòu)的描述方法。 掌握線性表在鏈?zhǔn)酱鎯Y(jié)構(gòu)中實現(xiàn)基本運算（查找、插掌握線性表在鏈?zhǔn)酱鎯Y(jié)構(gòu)中實現(xiàn)基本運算（查找、插入、刪除、合并等）的算法及分析。入、刪除、合并等）的算法及分析。 掌握并學(xué)會何時選用何種鏈表的方法。掌握并學(xué)會何時選用何種鏈表的方法。 串的存儲結(jié)構(gòu)及基本運算的實現(xiàn)。串的存儲結(jié)構(gòu)及基本運算的實現(xiàn)。41第41頁/共43頁42第二章 第二章結(jié)束第42頁/共43頁43感謝您的觀看！第43頁/共43頁