【正文】 ead=NULL(第 1個結(jié)點 ),head=s 3)、否則 pnext=s 4)、指針 p始終指向 s,p=s step3 結(jié)束循環(huán) ,pnext =NULL, 返回頭指針 head。 ?找其前趨結(jié)點的時間復(fù)雜度是 O（ n）。 } else { t = p next。 pnext=s。 } 下一頁 上一頁 停止放映 第 66 頁 單鏈表插入算法 13 單鏈表插入算法操作步驟 : step1 找到 ai1的位置 ,使指針 p指向 ai1 step2 申請并生成新結(jié)點 s step3 使 s插入到 ai1和 ai之間 ai1 ai p x s 示例 snext=pnext pnext=s sdata=x 下一頁 上一頁 停止放映 第 67 頁 單鏈表的插入算法程序 insert(NODE *head, int i, int x) { NODE *p,*s。 else return NULL。 p=headnext。 /* 指針右移一位 */ counter++。 ?空表形式 : head = NULL ?非空表形式 : head ? . next = address head head a1 下一頁 上一頁 停止放映 第 52 頁 鏈表舉例 ? 由食品組成的單鏈表（不帶頭結(jié)點 ） （ biscuit,butter,cheese,eggs,grapes,jam) biscuit butter cheese jam grapes eggs ^ head 頭指針 下一頁 上一頁 停止放映 第 53 頁 單鏈表在存儲區(qū)的物理狀態(tài) Grapes 60 biscuit 61 cheese 13 eggs 1 jam NULL butter 12 存儲地址 數(shù)據(jù)域（ data）指針域（ next） 1 11 12 13 60 61 11 頭指針 head …… 下一頁 上一頁 停止放映 第 54 頁 2. 單鏈表的操作 ?指針的基本操作 ?單鏈表的查找 get ?單鏈表長度計數(shù) Count ?單鏈表的的插入 insert ?單鏈表的刪除 delete 下一頁 上一頁 停止放映 第 55 頁 指針的基本操作 ? 設(shè)指針變量 p、 q的定義為： NODE *p， *q； ? 對鏈表的操作實際上是對指針的操作。 鏈表存儲結(jié)構(gòu)形式為： 鏈表結(jié)構(gòu)的 C語言描述為： struct node { int data 。 /* 刪除操作子函數(shù) */ for (j=0。 main（） { int j,loc。 if( i 1 || i last ) { printf(“表中不存在位置為 i的元素 \n”)。 } 下一頁 上一頁 停止放映 第 42 頁 算法 12 線性表刪除算法 算法步驟 : step1 判別指定的位置是否合法； step2 若合法，則將位置 i+1至 n上的元素前 移一個存儲位置 。loc)。 list [i1] =x。 list [i+1] =x。 step2 將 x插入到 ai1之后 。 下一頁 上一頁 停止放映 第 33 頁 （一）線性表的邏輯結(jié)構(gòu) 定義： 線性表是 n（ n?0）個元素 a1,a2,…,a n 的有限序列；表中每個數(shù)據(jù)元素，除了第 1個和最后 1個外，有且僅有一個前趨元素和后繼元素。 下一頁 上一頁 停止放映 第 29 頁 算法的描述 算法的描述方式（常用的）： 自然語言 流程圖 特定的表示算法的圖形 符號 算法描述 偽語言 包括程序設(shè)計語言的三 大基本結(jié)構(gòu)及自然語言 的一種語言 類語言 類似高級語言的語言， 例如，類 PASCAL、類 C語言。 下一頁 上一頁 停止放映 第 22 頁 算法（ Algorithm） – 是對特定問題求解步驟的一種描述； – 是一組指令的有限集合。 下一頁 上一頁 停止放映 第 19 頁 索引存儲結(jié)構(gòu) 數(shù)據(jù)按索引形式存放。 下一頁 上一頁 停止放映 第 16 頁 數(shù)據(jù)存儲結(jié)構(gòu)分類 ?順序存儲結(jié)構(gòu) ?鏈?zhǔn)酱鎯Y(jié)構(gòu) ?索引存儲結(jié)構(gòu) ?散列存儲結(jié)構(gòu) 下一頁 上一頁 停止放映 第 17 頁 順序存儲結(jié)構(gòu) 把數(shù)據(jù)元素按某種順序存放在一塊連續(xù)的存儲單元中的存儲形式。 按某種邏輯關(guān)系組織起來的一批數(shù)據(jù)，按一定的存儲方式把它存儲在計算機存儲器中，并在這些數(shù)據(jù)上定義了一個運算的集合，叫做一個數(shù)據(jù)結(jié)構(gòu) (Data Structures)。它是客觀事物的符號表示。 數(shù)據(jù)庫中的數(shù)據(jù)存放在計算機中的物理位置 下一頁 上一頁 停止放映 第 15 頁 邏輯結(jié)構(gòu)和物理結(jié)構(gòu)的關(guān)系 ? 數(shù)據(jù)的 邏輯結(jié)構(gòu) 是從邏輯關(guān)系（某種順序）上觀察數(shù)據(jù)，它是獨立于計算機的；可以在理論上、形式上進行研究、推理、運算等各種操作。 下一頁 上一頁 停止放映 第 18 頁 鏈?zhǔn)酱鎯Y(jié)構(gòu) 以鏈表形式將數(shù)據(jù)元素存放于任意存儲單元中，可連續(xù)存放，也可以不連續(xù)存放，以指針實現(xiàn)鏈表間的聯(lián)系。 特點： – 數(shù)據(jù)元素間無內(nèi)在聯(lián)系； – 存儲形式不定。 下一頁 上一頁 停止放映 第 26 頁 可讀性（ Readability） ?算法的第一目的是為了閱讀和交流； ?可讀性有助于對算法的理解； ?可讀性有助于對算法的調(diào)試和修改。 下一頁 上一頁 停止放映 第 31 頁 時間復(fù)雜度舉例 （ a） X： =X+1 ； O（ 1） （ b） FOR I： =1 TO n DO X： = X+1； O（ n） （ c） FOR I： = 1 TO n DO FOR J： = 1 TO n DO O（ n2 ） X： = X+1； 下一頁 上一頁 停止放映 第 32 頁 二、線性表 是指數(shù)據(jù)元素之間的關(guān)系為一一對應(yīng)的線性關(guān)系的數(shù)據(jù)結(jié)構(gòu)。 采用順序存儲結(jié)構(gòu)的線性表簡稱為“順序表”。ki。 } else { for (k=last1。 printf(“Enter x、 loc\n”)。 /* 插入操作子函數(shù) */ for (j=0。k=last。 last。jMAXLENGTH,j++) printf(“%d “,list[j])。 ? 順序表 缺點是： – 難于插入、刪除操作； – 需要預(yù)先分配空間，不管這些空間能否最大限度地利用。 頭結(jié)點 為方便操作，在頭指針和頭結(jié)點之間設(shè)置的結(jié)點。 算法描述： ?從數(shù)列左邊開始（即從第 1個元素開始）進行處理； ?每次處理，將計數(shù)器值加“ 1”、指針右移，共處理 i次； while((p!=NULL)amp。 /* 返回 i的值 */ else return NULL。 } if((p!=NULL)amp。 while( p!=NULL) { p