數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言 胡學(xué)鋼線性表PPT課件

1第二章 線性表 第二章 線性表 2.1 線性表的定義和運(yùn)算 2.2 順序表 2.3 鏈表 2.4 其它結(jié)構(gòu)形式的鏈表 2.5 串 第1頁(yè)/共43頁(yè)22.1 線性表的定義和運(yùn)算 p定義： 線性表L是由n個(gè)元素a1，a2，an組成的 有限 序列。 記作 L =（a1，a2，an） 其中n=0為表長(zhǎng)；n=0時(shí)為L(zhǎng)空表，記作L=（）p特性： A、只有一個(gè)第一個(gè)元素和一個(gè)最后一個(gè)元素； B、除第一個(gè)元素外其他元素有且僅有一個(gè)直接前趨（前驅(qū)）； C、除最后一個(gè)元素外其他元素有且僅有一個(gè)直接后繼p元素ai的含義： 同一表中，元素類型相同。在不同的場(chǎng)合有不同的含義 例：字母表（A，B，C，D，Z）； 數(shù)字表（0，1，2，3，4，9）； 每月天數(shù)（31,29,31,30,31,30,31,31,30,31,30,31）;第2頁(yè)/共43頁(yè)32.1 線性表的定義和運(yùn)算 運(yùn)算： (1)初始化 initial_List(L)建立線性表的初始結(jié)構(gòu)，即建空表 (2)求長(zhǎng)度 List_length(L) 即求表中的元素個(gè)數(shù)(3)按序號(hào)取元素 get_element(L,i) 取出表中序號(hào)為i的元素 (4)按值查找元素 List_locate(L,x) 取出指定值為x的元素，若存在則返回其地址；否則返回特殊值(5)插入 List_insert(L,i,x) 在表L的第i個(gè)位置上插入值為x的元素( 1=i=n+1)(6)刪除 List_delete（L,i）刪除表L中序號(hào)為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-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條件：順序表不滿； 序號(hào)正確，在1, n+1中操作：ai an后移; 填入x; listlen +算法分析第6頁(yè)/共43頁(yè)72.2 順序表 刪除void List_delete(seqlist *L,int i) int j; if (L-listlenL-listlen|i=0) error(“刪除位置出錯(cuò)”); 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頁(yè)/共43頁(yè)82.2 順序表 算法分析：插入時(shí) 在i=1,2,n+1，元素移動(dòng)的次數(shù)分別為n,n-1,0。 在等概率的情況下，平均移動(dòng)(n+1)n/2(n+1)=n/2次刪除時(shí) 在i=1,2,n，元素移動(dòng)的次數(shù)分別為n-1,n-2,0。 在等概率的情況下，平均移動(dòng)(n-1)n/2n=(n-1)/2次結(jié)論：n較大時(shí)，大量移動(dòng)元素，耗時(shí)解決：考慮不移動(dòng)元素教材P17例第8頁(yè)/共43頁(yè)92.3 鏈表基本結(jié)構(gòu)以鏈接形式連接元素次序。a1a2a3a4 L=(a1,a2,a3,a4)結(jié)點(diǎn)包括 元素和地址。datanext第9頁(yè)/共43頁(yè)102.3 鏈表存儲(chǔ)實(shí)現(xiàn)（靜態(tài)鏈表）1、靜態(tài)鏈表用數(shù)組C3A2B0D5F-1E4data next012345L=(A,B,C,D,E,F)head第10頁(yè)/共43頁(yè)112.3 鏈表存儲(chǔ)實(shí)現(xiàn)（動(dòng)態(tài)鏈表）2、動(dòng)態(tài)鏈表用指針和動(dòng)態(tài)變量實(shí)現(xiàn)（1）結(jié)點(diǎn)結(jié)構(gòu)datanext（2）類型定義 typedef struct elementtype data; node *next; node; 引用：node *head；第11頁(yè)/共43頁(yè)122.3 鏈表圖例a1a2a3a4 Head*HeadHead-next首元素第12頁(yè)/共43頁(yè)132.3 鏈表基本運(yùn)算 運(yùn)算： (1)初始化 initial_List(L)建立表的初始結(jié)構(gòu)，即建空表 (2)求長(zhǎng)度 List_length(L) 即求表中的元素個(gè)數(shù)(3)按序號(hào)取元素 get_element(L,i) 取出表中序號(hào)為i的元素 (4)按值查找元素 List_locate(L,x) 取出指定值為x的元素，若存在則返回其地址；否則返回特殊值(5)插入 List_insert(L,i,x) 在表L的第i個(gè)位置上插入值為x的元素( 1=i=n+1)(6)刪除 List_delete（L,i）刪除表L中序號(hào)為i的元素1=inext=P-next; P-next=S;注意：兩個(gè)操作不能交換p 如果是作為第一個(gè)結(jié)點(diǎn)插入，過(guò)程如下：S-next=head; head=S;a1a2a3 a4 headxS第14頁(yè)/共43頁(yè)152.3 鏈表討論 (引入頭結(jié)點(diǎn))為保持插入操作一致，引入頭結(jié)點(diǎn)。注意：頭結(jié)點(diǎn)與首元素的區(qū)別。a1a2a3 xh e adSPS-next=P-next; P-next=S;第15頁(yè)/共43頁(yè)162.3 鏈表討論(刪除操作)p 刪除（一般位置）：假設(shè)被刪除的前一個(gè)結(jié)點(diǎn)的指針P已找到：Pa1a2a3a5 h e ada4 P-next=P-next-next;p 如果是刪除第一個(gè)結(jié)點(diǎn)，過(guò)程如下：head=head-next;a1a2a3a5 h e ada4 p 討論結(jié)果：引入頭結(jié)點(diǎn)P-next=P-next-next;a1a2a4 h e ada3 P第16頁(yè)/共43頁(yè)172.3 鏈表運(yùn)算的實(shí)現(xiàn)（有頭結(jié)點(diǎn)） 1、初始化單鏈表（建空表）Lvoid initial_List(node &*L) L = new node; /L = (node *)malloc(sizeof(node);L - next = NULL;第17頁(yè)/共43頁(yè)182.3 鏈表求表長(zhǎng)（1）2、求單鏈表表長(zhǎng)a1a2a3 LPlen=0P=L-next;len=0;P!=NULLreturn(len);P=P-next;len+;YNint List_length(node *L)P=L-next; len=0; while(P!=NULL) P=P-next; len+; return(len);第18頁(yè)/共43頁(yè)192.3 鏈表求表長(zhǎng)（2）2、求單鏈表表長(zhǎng)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頁(yè)/共43頁(yè)202.3 鏈表按序號(hào)取值3、按序號(hào)取值返回指向結(jié)點(diǎn)的指針,否則返回NULLa1a2a3 LPj=0P=L;j=0;P-next!=NULLreturn(P);P=P-next;j+;YNj=iYNreturn(P);第20頁(yè)/共43頁(yè)212.3 鏈表按值查詢 4、按值查詢 返回元素結(jié)點(diǎn)指針，否則返回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(P); 第21頁(yè)/共43頁(yè)222.3 鏈表 插入5、插入ai-1aixSP分析：A、搜索位置；B、裝入x；C、插入x；P=get(L,i-1);if(P=NULL) error(“序號(hào)錯(cuò)”);else S = new node; S-data=x; S-next=P-next; P-next=S; void insert(node &*L,elementtype x,int i)第22頁(yè)/共43頁(yè)232.3 鏈表 刪除6、刪除Pai-1aiai+1 分析：A、搜索位置；B、刪除結(jié)點(diǎn)；C、釋放結(jié)點(diǎn)；P=get(L,i-1);if(P=NULL) error(“序號(hào)錯(cuò)”);else u=P-next; P-next=P-next-next; delete u; /free(u); void delete(node &*L,int i)第23頁(yè)/共43頁(yè)242.3 鏈表單鏈表的應(yīng)用(頭結(jié)點(diǎn))鏈表的遍歷：訪問(wèn)鏈表每個(gè)結(jié)點(diǎn)一次且僅一次?；舅惴ㄈ缦拢簐oid print(node *L) P=L-next; while(P!=NULL) visit(P-data); P=P-next; a1a2a3 LP第24頁(yè)/共43頁(yè)252.3 鏈表單鏈表的應(yīng)用(頭結(jié)點(diǎn)) 設(shè)計(jì)算法，判斷帶頭結(jié)點(diǎn)單鏈表L是否遞增？若遞增，則返回true，否則返回false。分析：（1）鏈表空，返回true；（2）只有一個(gè)結(jié)點(diǎn)，返回true；（3）每個(gè)元素都小于其直接后繼，返回true；否則，返回false；第25頁(yè)/共43頁(yè)262.3 鏈表單鏈表的應(yīng)用(頭結(jié)點(diǎn))由分析得如下流程圖：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); 第26頁(yè)/共43頁(yè)272.3 鏈表構(gòu)造鏈表 構(gòu)造鏈表 基本方法：從鍵盤輸入數(shù)據(jù)，每讀入一個(gè)元素，產(chǎn)生結(jié)點(diǎn)裝入，插入鏈表中，重復(fù)上述操作X不是結(jié)束符cin xs = new node;s - data = x;插入操作n 討論：產(chǎn)生結(jié)點(diǎn)：s= new node; s-data=x;插入鏈表：插入位置如何確定， 有 表頭/表尾 兩個(gè)位置可選 頭插法 尾插法重復(fù)上述操作： 何時(shí)結(jié)束?a1a2a3 L第27頁(yè)/共43頁(yè)282.3 鏈表頭插法頭插法運(yùn)算實(shí)現(xiàn)：void create_List(node *&L)L= new node; L-next=NULL;cin x;while( x != End_of_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頁(yè)/共43頁(yè)292.3 鏈表尾插法尾插法運(yùn)算實(shí)現(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 uLR第29頁(yè)/共43頁(yè)302.3 鏈表練習(xí)題P 31 例2.6、2.7、2.81）鏈表A，B，設(shè)計(jì)算法求CAB，并分析其時(shí)間復(fù)雜度2）遞增鏈表A，B，設(shè)計(jì)算法求CAB，并分析其時(shí)間復(fù)雜度第30頁(yè)/共43頁(yè)312.4 其他結(jié)構(gòu)形式的鏈表 單循環(huán)鏈表（優(yōu)點(diǎn)：可在表中反復(fù)搜索 ）初始化操作為： head = new node; head - next = head;求長(zhǎng)度： p = head - next; n = 0; while ( p != head ) p = p - next; n + ;應(yīng)用： m人開(kāi)m把鎖問(wèn)題（每人一把鑰匙，要求所有鎖都能開(kāi)） 約瑟夫環(huán)問(wèn)題（利用循環(huán)隊(duì)列，不帶頭結(jié)點(diǎn)的循環(huán)鏈表都可）a1a2an headhead第31頁(yè)/共43頁(yè)322.4 其他結(jié)構(gòu)形式的鏈表 帶尾指針的單循環(huán)鏈表（優(yōu)點(diǎn)：表尾操作方便 ） 應(yīng)用：將A、B兩鏈表首尾相連 實(shí)現(xiàn)部分語(yǔ)句為： 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頁(yè)/共43頁(yè)332.4 其他結(jié)構(gòu)形式的鏈表p雙鏈表（優(yōu)點(diǎn)：求前驅(qū)后繼都方便） 帶頭結(jié)點(diǎn) 或者 不帶頭結(jié)點(diǎn) typedef struct elementtype data; dnode * prior, * next; dnode; p雙循環(huán)鏈表prior data next a1a2 an head第33頁(yè)/共43頁(yè)342.4 其他結(jié)構(gòu)形式的鏈表初始化： head = new node; head - prior = head - next = head;求長(zhǎng)度查找類似插入時(shí)： s - prior = p - prior; s - next = p; p - prior = s; s - prior - next = s;刪除時(shí)： p - prior - next = p - next; p - next - prior = p - prior; delete p;應(yīng)用：判斷雙循環(huán)鏈表是否對(duì)稱 雙循環(huán)鏈表倒置（動(dòng)指針、動(dòng)結(jié)點(diǎn)值）head ai ai+1 xsp ai-1 ai ai+1p第34頁(yè)/共43頁(yè)352.4 其他結(jié)構(gòu)形式的鏈表 小結(jié)： 線性表 邏輯上相鄰的元素 順序表 物理上也相鄰 插入、刪除需移動(dòng)元素 鏈表 物理上不一定相鄰 插入、刪除不需移動(dòng)元素第35頁(yè)/共43頁(yè)362.5 串 定義： 串：由n個(gè)字符a1,a2,an組成的有限序列（n=0）元素是字符的線性表，記作 S=“a1,a2,an”，其中n為串長(zhǎng)度。n=0時(shí)為空串。 注意：空串和空格串的區(qū)別?？沾疀](méi)有元素?？崭翊厥强崭穹Ｗ哟?串S中若干個(gè)連續(xù)的字符組成的序列。書上書上P37例例第36頁(yè)/共43頁(yè)372.5 串 運(yùn)算： 基本運(yùn)算 賦值=：將一個(gè)串值S1傳送給一個(gè)串名S。如：S=S1 求長(zhǎng)度length(S)：返回串S的長(zhǎng)度值。 連接運(yùn)算+：將S1和S2連接成一個(gè)新串（如S1+S2） 求子串substr（S,i,j）：返回串S從第i個(gè)元素開(kāi)始的j個(gè)元素所組成的子串。 串比較strcmp(S1,S2)：比較兩個(gè)串的大小。對(duì)齊按ASCII碼進(jìn)行比較。結(jié)果為-1、0、1第37頁(yè)/共43頁(yè)382.5 串常用運(yùn)算：可由基本運(yùn)算實(shí)現(xiàn) 插入（insert（S,i,S1）：將子串S1插入到串S的從第i個(gè)字符開(kāi)始的位置上。 刪除（deletestr（S,i,len）：刪除串S中從第i個(gè)字符開(kāi)始的len個(gè)字符。 替換（replace(S,i,len,S1)）：用字串S1替換串S中從第i個(gè)字符開(kāi)始的len個(gè)字符。 定位（index（S,S1）/模式匹配 例：S=“a1,a2,an”，在S的第i個(gè)位置插入S1 運(yùn)算為 insert(S,i,S1)，為常用運(yùn)算 可操作為：X1=substr(S,1,i-1,) X2 =substr(S,i, length() - (i - 1),) S = X1 + S1 + X2 /為基本運(yùn)算 兩者可互換第38頁(yè)/共43頁(yè)392.5 串 存儲(chǔ)結(jié)構(gòu) 順序串 緊湊格式： 優(yōu)點(diǎn)：節(jié)省空間； 缺點(diǎn)：運(yùn)算不方便。 非緊湊格式：優(yōu)點(diǎn)：運(yùn)算方便； 缺點(diǎn)：浪費(fèi)空間。 鏈串 結(jié)點(diǎn)大?。ㄒ?guī)模）：大于1： 等于1： S a1 a2 a3ana4.a3.a2.a1a8.a7.a6.a5ana1a2a3a4a5a6a7a8an 第39頁(yè)/共43頁(yè)40第二章 線性表 第二章 線性表 2.1 線性表的定義和運(yùn)算 2.2 順序表 2.3 鏈表 2.4 其它結(jié)構(gòu)形式的鏈表 2.5 串 第40頁(yè)/共43頁(yè)41第二章第二章 線性表線性表 重點(diǎn)重點(diǎn) 掌握順序存儲(chǔ)結(jié)構(gòu)的描述方法。掌握順序存儲(chǔ)結(jié)構(gòu)的描述方法。 掌握線性表在順序存儲(chǔ)結(jié)構(gòu)中實(shí)現(xiàn)基本運(yùn)算（查找、插掌握線性表在順序存儲(chǔ)結(jié)構(gòu)中實(shí)現(xiàn)基本運(yùn)算（查找、插入、刪除、合并等）的算法及分析入、刪除、合并等）的算法及分析 掌握鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的描述方法。掌握鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的描述方法。 掌握線性表在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中實(shí)現(xiàn)基本運(yùn)算（查找、插掌握線性表在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中實(shí)現(xiàn)基本運(yùn)算（查找、插入、刪除、合并等）的算法及分析。入、刪除、合并等）的算法及分析。 掌握并學(xué)會(huì)何時(shí)選用何種鏈表的方法。掌握并學(xué)會(huì)何時(shí)選用何種鏈表的方法。 串的存儲(chǔ)結(jié)構(gòu)及基本運(yùn)算的實(shí)現(xiàn)。串的存儲(chǔ)結(jié)構(gòu)及基本運(yùn)算的實(shí)現(xiàn)。41第41頁(yè)/共43頁(yè)42第二章 第二章結(jié)束第42頁(yè)/共43頁(yè)43感謝您的觀看！第43頁(yè)/共43頁(yè)