【正文】 printf(“not exist!\n”)。 listelement[i]=x。return (0)。 4. 插入 insert(L, i, x) 功能： 在順序表 L中第 i個(gè)位置后插入一元素插入 一 個(gè)新 元素 x, 插入前線性表為 (a0, a1, a2, … , ai1, ai,… an1 ) 插入后 ,線性表長(zhǎng)度為 n+1, 線性表為 (a0, a1, a2, … , ai1, x, ai,… an1 ) 插入前 n=7 插入后 n=8 插入操作示意圖： insert(p,3,11) 12 34 3 11 27 16 147 44 a0 a1 a2 a3 a4 a5 a6 a7 11 12 34 3 27 16 147 44 a0 a1 a2 a3 a4 a5 a6 a7 插入操作算法 int Insert(ptsqlist list,int i,elementtype x) { int j。 return(list)。 } ptsqlist Initiate(void) ptsqlist list。/*順序表數(shù)組 */ int n。線性表是一種線性數(shù)據(jù)結(jié)構(gòu)； 4) 線性表中元素的個(gè)數(shù) n 稱為 線性表的長(zhǎng)度 ， n=0 時(shí)稱空表； 5) ai是線性表的第 i +1個(gè)元素，稱 i+1 為數(shù)據(jù)元素 ai 的序號(hào)，每一個(gè)元素在線性表中的位置，僅取決于它的序號(hào)； 線性表的其他表示方式 二元組表示 L= D,S ，其中 D={ a0,a1, a2, ... an1} S= {R} R={ a 0,a1 , a1,a2, a2,a3 … a n2, an1 } 圖示表示 ai+1 a0 ai1 a1 ai an1 頂點(diǎn)：表示一個(gè)數(shù)據(jù)元素 邊：表示是數(shù)據(jù)間的順序結(jié)構(gòu)關(guān)系 ? 線性表的基本操作 ? 初始化操作 ： Initiate（ L） 設(shè)定一個(gè)空的線性表 L ； ? 求長(zhǎng)度函數(shù) ： Length（ L） 求線性表 L中數(shù)據(jù)元素的個(gè)數(shù) ； ? 查找函數(shù) ： Get（ L,i） 取得線性表 L的第 i個(gè)數(shù)據(jù)元素 ； ? 定位函數(shù) ： Locate（ L,x） 求數(shù)據(jù)元素 x在線性表 L中的位置 ； ? 插入操作 ： Insert（ L,i,x） 在線性表中第 i個(gè)位置插入一個(gè)數(shù)據(jù)元素 。 2. 1 線性表的基本概念 ? 線性表的定義 線性表是 n 個(gè)類型相同數(shù)據(jù)元素的有限序列， Linearlist=(D,R) 其中： D={ai | ai ∈ datatype , i=0,1,…n 1} R={ai,ai+1| ai ,ai+1 ∈ D, 1≤i≤n1 } 或記作（ a0, a1, a2, …, a n1 ）。第二章 線性表 ? 學(xué)習(xí)要點(diǎn) ? 了解線性表的邏輯結(jié)構(gòu)是數(shù)據(jù)元素之間存在著線性關(guān)系，在計(jì)算機(jī)中表示這種關(guān)系的兩種不同的存儲(chǔ)結(jié)構(gòu)是順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 姓名 電話號(hào)碼 蔡穎 63214444 陳紅 63217777 劉建平 63216666 王小林 63218888 張力 63215555 ... 例 數(shù)學(xué)中的數(shù)列（ 11， 13， 15， 17， 19， 21） 例 英文字母表（ A, B, C, D, E? Z ）。 ? 刪除操作 ： Delete（ L,i） 在線性表中第 i（ 0≤i≤n1）個(gè)結(jié)點(diǎn)； 為了存儲(chǔ)線性表，至少要保存兩類信息： 1）線性表中的數(shù)據(jù)元素； 2）線性表中數(shù)據(jù)元素的順序關(guān)系； 如何在計(jì)算機(jī)中存儲(chǔ)線性表？如何在計(jì)算機(jī)中實(shí)現(xiàn)線性表的基本操作？ 線性表的順序存儲(chǔ)結(jié)構(gòu) 一、線性表的順序存儲(chǔ)結(jié)構(gòu) —順序表 線性表的順序存儲(chǔ)結(jié)構(gòu)，就是用一組 連續(xù)的 內(nèi)存單元 依次 存放線性表的數(shù)據(jù)元素。 /*當(dāng)前線性表長(zhǎng)度 */ }。 list=(ptsqlist) malloc (sizeof(struct sqlist)) if !list {printf(overflow!\n)。 } } elementtype Get(ptsqlist list,int i) if (i0||i=listn) { printf(not exist\n)。 if (i0||i=listn){ /*位置不合理 */ printf(“not exit!\n”)。 } for (j=listn1。 /*插入元素 */ listn++。 return (0)。 listn。 a=0。a++,z) /*逆轉(zhuǎn)順序表 */ { mid=listelement[a]。 1 2 i1 i i+1 n a0 a1 … ai1 ai ai+1 … an1 假設(shè)在線性表的任何位置插入元素的概率相同，即 pi= 1/(n+1) 則有： 假設(shè) pi是在第 i個(gè)元素之前插入元素的概率，在長(zhǎng)度為 n的順序表中插入一個(gè)元素，所需移動(dòng)元素個(gè)數(shù)數(shù)學(xué)期望值為： ninnEnii 21)(110???? ??????niii pinE0*)(假設(shè)在線性表的任何位置刪除元素的概率相同，即 pd= 1/n 則有： 刪除下標(biāo)為 i的元素（第 i+1個(gè)）需移動(dòng) ni1個(gè)元素，設(shè)在相應(yīng)位置刪除元素的概率是 pd，則刪除的平均移動(dòng)次數(shù)是： 21)1(1 10????? ???ninnEnid??????10*)1(nidd pinE在順序表中插入或刪除元素的 時(shí)間時(shí)間復(fù)雜度 為 O(n) 相關(guān)例題 例 1 利用順序表設(shè)計(jì)一算法，用以清除表 L中的多余的重復(fù)結(jié)點(diǎn)。 while (jlistn) { if (listelement[i]==listelement[j]) { for (k=j+1。 }else j=j+1。為了表示線性表中元素的先后關(guān)系，每個(gè)結(jié)點(diǎn)除了需要存儲(chǔ)自身的信息外，還需存儲(chǔ)一個(gè)指示其直接后繼的信息（直接后繼的存儲(chǔ)位置）。 struct Node *next。 H=NULL。) { p=(LinkList)malloc(sizeof(LNode))。 q=p。 } head是頭指針 頭結(jié)點(diǎn) 空指針 head ? 頭指針： 用于存放線性鏈表中第一個(gè)結(jié)點(diǎn)的存儲(chǔ)地址 。 L an a1 p X pnext=Lnext。 L=(LinkList)malloc(sizeof(LNode))。i) { p=(LinkList)malloc(sizeof(LNode))。 Lnext=p。 p=head。ji) { p=pnext。 } 3. 按值查找 L an a1 LNode* Locate_List_Node(LinkList head,Etype x) /*在單鏈表中查找值為 x的結(jié)點(diǎn) ,返回其指針 ,查找失敗返回空 */ { LNode *p。(pdata!=x)) p=pnext。 pnext=s。 s=(LinkList)malloc(sizeof(LNode))。 return OK。 int ListDelete(LinkList L,int i,Etype e)