【正文】 86 60 78 75 55 90 90 55 78 60 86 例如：插入元素 75，插入位置為 4，則 90和 55兩個元素應(yīng)向后移。 Llength++ 。j) Lelem[j+1]=Lelem[j]。 } for ( j=Llength。 } if (i1 || iLlength+1) /* 檢查插位置的正確性 */ {printf(＂ 位置錯＂ )。 if (Llength==MAXSIZE1) {printf(＂ 表滿＂ )。 } 2. 插入運算 a1 a2 … ai1 ai ai+1 … an a1 a２ … ai1 x ai ai+1 … an 1 2 … i1 i i+1 … n n+1 856078559078數(shù)據(jù)結(jié)構(gòu) (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 12頁 【算法 】在順序表的第 i個位置上插入一個值為 x的新元素。 data 數(shù)組下標 a1 a2 … ai1 ai ai+1 … an … 1 2 … i1 i i+1 … length ... MAXSIZE1 b b+d … … b+(i1)d … b+( length 1)d 存儲地址 數(shù)據(jù)結(jié)構(gòu) (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 11頁 (1) 將 an～ ai 按從后向前的順序向下移動，為新元素讓出位置； (2) 將 x置入空出的第 i個位置； (3) 修改 length值。 數(shù)據(jù)元素是 Ldata[1]～ Ldata[Llength]。 /* 線性表長度 */ } SeqList。 順序存儲結(jié)構(gòu)可描述如下： typedef struct { ElemType elem[MAXSIZE]。} 數(shù)據(jù)結(jié)構(gòu) (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 9頁 線性表的順序存儲結(jié)構(gòu)及運算實現(xiàn) 順序表 是指在內(nèi)存中用一塊地址連續(xù)的存儲空間按順序存儲線性表的各個數(shù)據(jù)元素。 L , i , e）： 在第 i 個位置插入元素 e ； ListDelete（ amp。 ,n1 ,n ≥0 } 基本操作 ： InitList（ amp。 數(shù)據(jù)結(jié)構(gòu) (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 8頁 ADT List { 數(shù)據(jù)對象 ： D={ai|ai∈ ELEMTP i=1,2, ⑸ 插入操作 ： Insert_List(L, i, x)； ——在線性表 L的第 i個位置上插入一個值為 x的數(shù)據(jù)元素。 ⑶ 取表中元素 ： Get_Elem(L, i)； ——返回線性表 L中第ｉ個數(shù)據(jù)元素的值或地址。 /* 成績域 */ }ElemType 。 /* 姓名域 */ char Sex。 例如 ， 學(xué)生信息表中數(shù)據(jù)元素可以定義為一個結(jié)構(gòu)類型： typedef struct std_info { long int Num。 關(guān)鍵點 : (1) 相同類型 (2) 線性表的長度 n (n≥0) (3) 有限序列 數(shù)據(jù)結(jié)構(gòu) (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 5頁 線性表中所包含的元素個數(shù) n (n≥0) ； 線性表的長度 n=0 ； 3.（ 直接）前驅(qū)和后繼 在相鄰元素中， ai 是 ai+1的前驅(qū)（第一個元素 a1無前驅(qū)） 在相鄰元素中， ai+1是 ai的后繼（最后一個元素 an無后繼） ： 長度為 10的奇數(shù)序列 (1,3,5,7,9,11,13,15,17,19) 線性表可以看作是除 第一個元素 無前驅(qū)， 最后一個元素 無后繼外，其余元素都有唯一的直接前驅(qū)和直接后繼的一組元素構(gòu)成的有序集合。 bn) 該線性表的長度為 n ：具有 相同類型 的 n 個 數(shù)據(jù)元素組成的 有限序列 。數(shù)據(jù)結(jié)構(gòu) (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 1頁 線性表的邏輯結(jié)構(gòu) 線性表的順序存儲結(jié)構(gòu)及運算實現(xiàn) 線性表的 鏈式 存儲結(jié)構(gòu)及運算實現(xiàn) 線性表的典型應(yīng)用 小結(jié) 數(shù)據(jù)結(jié)構(gòu) (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 2頁 本章學(xué)習(xí)目標 線性表 是最簡單、最基本、最常用的一種數(shù)據(jù)結(jié)構(gòu) 通過本章學(xué)習(xí)，應(yīng)掌握如下內(nèi)容： 線性表的概念及表示方法 線性表的 兩種 存儲方式： 順序存儲 和 鏈式存儲 線性表的基本運算及其實現(xiàn)算法 線性表的典型應(yīng)用 數(shù)據(jù)結(jié)構(gòu) (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 3頁 例 2:奇數(shù)序列 (1,3,5,7,9,11) 例 1:字母序列 (A,B,C,D,E,F) 例 3：隨機的學(xué)生成績序列 線性表的邏輯結(jié)構(gòu) 線性表的定義 問題的引入 學(xué) 號 姓 名 性 別 成 績 20220601 張 三 男 518 20220602 李一寧 女 496 20220603 吳 磊 女 …… … … … 20220636 梁 磊 男 529 數(shù)據(jù)結(jié)構(gòu) (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 4頁 ： A=(１ ,３ ,５ ,７ ,９ ) 該線性表的長度為 5 B=(a1 ,a2 ,a3 , am) 該線性表的長度為 m C=(b1 ,b2 ,b3 , 記為 (a1， a2， … a i1， ai， ai+1， …a n) 其中 n為表長，當 n=0 時稱為空表。 數(shù)據(jù)結(jié)構(gòu) (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 6頁 通常將 ai的數(shù)據(jù)類型抽象為 ElemType。 /* 學(xué)號域 */ char Name[8]。 /* 性別域 */ float Score。 學(xué) 號 姓 名 性 別 成 績 20220601 張 三 男 518 20220602 李一寧 女 496 20220603 吳 磊 女 …… … … … 20220636 梁 磊 男 529 數(shù)據(jù)結(jié)構(gòu) (C語言版 ) 第 2章 線性表 2022年 8月 18日星期四 第 7頁 線性表的基本操作 ⑴ 線性表初始化 ： Init_List(L)； ——建立一個空的線性表； ⑵ 求線性表的長度 ： Length_List(L)； ——返回線性表中數(shù)據(jù)元素的個數(shù)。 ⑷ 按值查找 ： Locate_List(L, x)； ——在表 L中查找值為ｘ的數(shù)據(jù)元素的位置。 ⑹ 刪除操作 ： Delete_List(L, i)；