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