【正文】 構(gòu)的基本特征和基本運(yùn)算 線(xiàn)性表的存儲(chǔ)結(jié)構(gòu) 雙向鏈表 循環(huán)鏈表 ?難 點(diǎn) 循環(huán)鏈表 利用本章的基本知識(shí)設(shè)計(jì)有效的算法解決與線(xiàn)性相關(guān)的應(yīng)用問(wèn)題 ?要 求 熟練掌握以下內(nèi)容： 線(xiàn)性表的基本運(yùn)算 線(xiàn)性表的特征 、 基本運(yùn)算并能設(shè)計(jì)簡(jiǎn)單算法 了解以下內(nèi)容： 線(xiàn)性表運(yùn)算時(shí)間復(fù)雜性分析 第 二 章 目錄 ? 線(xiàn)性表的邏輯結(jié)構(gòu) ? 線(xiàn)性表的順序存儲(chǔ) ? 線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ) ? 循環(huán)鏈表 ? 雙向鏈表 ?小 結(jié) ?習(xí)題與練習(xí) 2 線(xiàn)性表 （ Linear List） ?線(xiàn)性表是由有限數(shù)目的相同類(lèi)型元素組成的序列。 線(xiàn)性表元素之間是有序的，而集合元素 之間是無(wú)序的。 順序存儲(chǔ)下線(xiàn)性表的運(yùn)算 1. 數(shù)據(jù)元素的插入 (insert) 在順序表 L=（ a1,a2,… ,ai,…,an ）中第 i個(gè)元素前插入元素 b，使成為 L=（ a1,a2,…, b ,ai,…, an ） 基本思想 ：把順序表表中第 I個(gè)元素至第 n個(gè)元素后移一個(gè)位置，把元素 b插入到第 i個(gè)位置上，線(xiàn)性表的長(zhǎng)度加 1。 /*順序表長(zhǎng)度加 1*/ return(0)。 算法的時(shí)間復(fù)雜性 ?可以用數(shù)據(jù)元素的移動(dòng)次數(shù)來(lái)度量這兩個(gè)算法的時(shí)間復(fù)雜性。 else { for (j=I+1。 data next ?所有結(jié)點(diǎn)通過(guò)指針的鏈接而構(gòu)成的線(xiàn)性表稱(chēng)為單鏈表。 結(jié)點(diǎn) *p是由兩個(gè)域組成的記錄，這兩個(gè)域分別用p?data域和 p?next域來(lái)標(biāo)識(shí)，它們各有自己的值，p?data的值是一個(gè)數(shù)據(jù)元素， p?next的值是一個(gè)指針。 /*返回表長(zhǎng)值 */ } 算法分析 ?此算法的關(guān)鍵是 while循環(huán)語(yǔ)句，開(kāi)始時(shí) p指針指向頭結(jié)點(diǎn)，每一循環(huán)都修改指針值，讓它指向下一個(gè)結(jié)點(diǎn)，同時(shí)將計(jì)數(shù)鏈表長(zhǎng)度的變量 count加 1。 3) 將新結(jié)點(diǎn)鏈入單鏈表中 。 pnext=s。 /*結(jié)點(diǎn) pre j++ } 插入算法續(xù) if(j!=k) { printf(“k超出鏈表的長(zhǎng)度 ” )。主要操作 是： 1) 用遍歷的方法在單鏈表上找到該結(jié)點(diǎn)； 2) 從單鏈表上刪除該結(jié)點(diǎn)。 while((p!=null) amp。 } 返回 靜態(tài)鏈表 ?在某些語(yǔ)言中，沒(méi)有指針類(lèi)型，就不能實(shí)現(xiàn)鏈表，可用一數(shù)組來(lái)模擬鏈表，這就是靜態(tài)鏈表。 循環(huán)鏈表 ?循環(huán)鏈表（ circular linked list）是一種首尾相接的鏈表，將單鏈表表尾結(jié)點(diǎn)原來(lái)的空指針改為指向表頭結(jié)點(diǎn)，就成為循環(huán)鏈表。 首先給定一正整數(shù) m，從第 1個(gè)人開(kāi)始(順時(shí)針），槍斃第 m個(gè)人，之后，以該人的密碼作為 m的新值，繼續(xù)下去 ,…… 基本思想： 首先建立一個(gè)帶頭結(jié)點(diǎn)，有 n個(gè)結(jié)點(diǎn)的循環(huán)鏈表，頭指針為 head。 i0。 pr i or da t a next ?如果循環(huán)鏈表的結(jié)點(diǎn)再采用雙向指針，就成為 雙向循環(huán)鏈表 。 qnext=p。 設(shè)一個(gè)一元多項(xiàng)式為 4 0 6 1 5 4 0 1 2 3 4 5 6 4654)( 2345 ????? xxxxxA? 2. 用 單鏈表表 示一元多項(xiàng)式 將單鏈表的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)著一元多項(xiàng)式中的一個(gè)非零項(xiàng)，它由三個(gè)域組成，分別表示非零項(xiàng)的系數(shù)、指數(shù)和指向下一個(gè)結(jié)點(diǎn)的指針。 A,B后移。 qnext=p。 p=head1。 例3.3算法 void insert(dnode *head,int i,x) { dnode *s,*p。 /*查找第 i個(gè)結(jié)點(diǎn) ， 由 p指向 */ j=1。 } else { snext=pnext。 5. 寫(xiě)出在單鏈表中的 p所指結(jié)點(diǎn)之前插入一個(gè) s所指結(jié)點(diǎn)的操作。 8. 與上題相同的單鏈表，設(shè)計(jì)一個(gè)函數(shù)，將此單鏈表分成兩個(gè)單鏈表，要求其中一個(gè)仍以原表頭指針head1作表頭指針，表中順序包括原線(xiàn)性表的第一、三等奇數(shù)號(hào)結(jié)點(diǎn)；另一個(gè)鏈表以 head2為表頭指針，表中順序包括原單鏈表第二、四等號(hào)結(jié)點(diǎn)。 10. 已知一個(gè)單循環(huán)鏈表，編寫(xiě)一個(gè)函數(shù)，將所有箭頭方向取反。 2. 設(shè)計(jì)一個(gè)函數(shù)，查找單鏈表中數(shù)值為 x的結(jié)點(diǎn)。 pnext=s。amp。 s=(dnode *)malloc(sizeof(dnode))。 q=head2。 q=r。 ?基本思想：從頭到尾遍歷單鏈表 L，并設(shè)置 3個(gè)附加指針 p、 q、 r, p指向當(dāng)前處理的結(jié)點(diǎn)， q指向 p的后繼， r指向 q的后繼， q、 r的作用是為了防止倒置指針時(shí)，下一個(gè)結(jié)點(diǎn)丟失而設(shè)置的。 4654)( 2345 ????? xxxxxAxxxxxB ???? 245 623)(結(jié)點(diǎn)的定義如下： typedef struct pnode { real coef。 pprior=q。 ?雙鏈表結(jié)構(gòu)是一種對(duì)稱(chēng)結(jié)構(gòu)，設(shè)指針 p指向雙鏈表的某一結(jié)點(diǎn)，則雙鏈表的對(duì)稱(chēng)性可用下式來(lái)表示： p=(pprior)next=(pnext)prior 即結(jié)點(diǎn) *p的地址存放在其前趨結(jié)點(diǎn) *(pprior)的后繼指針域中，又存放在它的后繼結(jié)點(diǎn) *(pnext)的前趨指針域中。 w=josephus_seqdata[s1]。 ?結(jié)點(diǎn)定義為： Typedef struct Jnode { int no。 head 1. 帶頭結(jié)點(diǎn)的循環(huán)鏈表 ?通常在循環(huán)鏈表的表頭結(jié)點(diǎn)前面再加一個(gè)空結(jié)點(diǎn) ,也叫空表頭結(jié)點(diǎn)。 int next。 (pdata!=x)) { q=p。 假設(shè)指針 q指向待刪除結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)，指針 p指向要?jiǎng)h除的結(jié)點(diǎn)，刪除該結(jié)點(diǎn)的操作如下：將該結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn) *q的鏈域指向 *p的后繼結(jié)點(diǎn)（即 qnext=pnext）。 } s=(linklist