【正文】 第二章 線性表 ? 學(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)。 ? 熟練掌握線性表的兩種存儲(chǔ)結(jié)構(gòu) ， 即順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 。 ? 熟練掌握線性表的兩種存儲(chǔ)結(jié)構(gòu)的基本算法 :查找 、 插入 、 刪除等 。 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 ）。 姓名 電話號(hào)碼 蔡穎 63214444 陳紅 63217777 劉建平 63216666 王小林 63218888 張力 63215555 ... 例 數(shù)學(xué)中的數(shù)列（ 11， 13， 15， 17， 19， 21） 例 英文字母表（ A, B, C, D, E? Z ）。 例 某單位的電話號(hào)碼簿。 說(shuō)明： 設(shè) A=（ a0, a1, ... , ai 1, ai , ai+1, …, a n1 ）是一線性表 1) 不同線性表中數(shù)據(jù)元素的類型可以是各種各樣的，但同一線性表中的元素必須是 同一類型 的； 2) 在表中 ai1 領(lǐng)先于 ai ， ai 領(lǐng)先于 ai+1 ，稱 ai1 是 ai 的直接前驅(qū)， ai+1 是 ai 的直接后繼； 3) 在線性表中，除第一個(gè)元素和最后一個(gè)元素之外，其他元素都有且僅有一個(gè)直接前驅(qū)，有且僅有一個(gè)直接后繼，這是所有 線性結(jié)構(gòu) 的共同特征。線性表是一種線性數(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ù)元素 。 ? 刪除操作 ： 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ù)元素。 a0 a1 … ai1 ai ai+1 … an1 線性表（ a0, a1,a2 ... an1 ） 的順序存儲(chǔ)結(jié)構(gòu) 用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的線性表 ——稱為順序表 說(shuō)明： ? 在順序存儲(chǔ)結(jié)構(gòu)下，線性表元素之間的邏輯關(guān)系，通過(guò)元素的存儲(chǔ)順序反映（表示）出來(lái)，即邏輯關(guān)系相鄰，物理位置也相鄰； ? 假設(shè)線性表中每個(gè)數(shù)據(jù)元素占用 d 個(gè)存儲(chǔ)單元，那么，在順序存儲(chǔ)結(jié)構(gòu)中，線性表的第 i個(gè)元素的存儲(chǔ)位置與第 1個(gè)元素的存儲(chǔ)位置的關(guān)系是： Loc(ai1 ) = Loc( a0 )+ ( i – 1) *d d個(gè)單元 Loc( a0 ) Loc(ai1 ) a0 a1 … ai1 ai ai+1 … an1 怎樣在計(jì)算機(jī)上實(shí)現(xiàn) 線性表的順序存儲(chǔ)結(jié)構(gòu)？ 因?yàn)楦呒?jí)語(yǔ)言中的一維數(shù)組是采用順序結(jié)構(gòu)儲(chǔ)存的，因此我們使用一維數(shù)組來(lái)表示線性表，數(shù)組的類型由線性表中的數(shù)據(jù)元素的性質(zhì)決定。 順序表的類型定義 define Maxnum 200 /*分配的順序表總長(zhǎng)度 */ elementtype element[Maxnum]； /* 定義元素類型數(shù)組 */ int n； /* 當(dāng)前順序表存儲(chǔ)數(shù)據(jù)的個(gè)數(shù) */ 為了把線性表的表元素和當(dāng)前長(zhǎng)度整合作為該線性表的特性，我們定義一個(gè)結(jié)構(gòu)體如下： struct sqlist { elementtype element[Maxnum]。/*順序表數(shù)組 */ int n。 /*當(dāng)前線性表長(zhǎng)度 */ }。 typedef struct sqlist *ptsqlist； 設(shè) A = （ a0 , a1,a2 ,... an1 ）是一線性表， L是 sqlist 類型的結(jié)構(gòu)變量，用于存放線性表 A，則 L在內(nèi)存中的狀態(tài)如圖所示： 1 2 i1 i i+1 n [i] n 存放線性表元素 的一維數(shù)組 順序表通過(guò) 元素的存儲(chǔ)順序 反映線性表元素間的邏輯關(guān)系 a0 a1 … ai1 ai ai+1 … an1 二、順序表的基本操作算法 i的元素（ 0≤i≤n 1）并返回該元素 int Empty(ptsqlist list) { if listn==0 return(1)。 return(0)。 } ptsqlist Initiate(void) ptsqlist list。 list=(ptsqlist) malloc (sizeof(struct sqlist)) if !list {printf(overflow!\n)。 return(null)。} else {listn=0。 return(list)。 } } elementtype Get(ptsqlist list,int i) if (i0||i=listn) { printf(not exist\n)。 return(null)。 } return(listelement[i])。 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,