第2章數(shù)據(jù)結(jié)構(gòu)及應用概念及順序表(編輯修改稿)
2024-08-16 09:18 本頁面
【文章內(nèi)容簡介】 例如，一星期七天的英文縮寫表示： （ Sun， Mon， The， wed， Thu， Fri， Sat） 是一個線性表，其中的元素是字符串，表的長度為 7。 下一頁 上一頁 停止放映 [第 25/42頁 ] 線性表的邏輯結(jié)構(gòu) 定義： 線性表是 n（ n?0）個元素 a1,a2,… ,an 的有限序列；表中每個數(shù)據(jù)元素，除了第 1個和最后 1個外，有且僅有一個前趨元素和后繼元素。 形式定義： 含有 n個數(shù)據(jù)元素的線性表是一種數(shù)據(jù)結(jié)構(gòu)，表示為： Linear_list=( D , R ) 其中 : D={ai | ai?D0,i=1,2,3,… ,n,n ?0} R={N}, N={ai1,ai|ai1,ai ?D0 ,i=1,… ,n} D是數(shù)據(jù)元素的有限集合， R是 D上邏輯關(guān)系的有限集合。關(guān)系 N是一個有序偶對的集合。 下一頁 上一頁 停止放映 [第 26/42頁 ] 順序表 采用順序存儲結(jié)構(gòu)的線性表稱為順序表，它的數(shù)據(jù)元素按照邏輯順序依次存放在一組連續(xù)的存儲單元中。邏輯上相鄰的數(shù)據(jù)元素，其存儲位置也彼此相鄰。 假定元素 a1的物理地址是 Loc(a1)，每個元素占 d個存儲單元，則第 i個元素的存儲位置為 ： Loc(ai) = Loc(a1) + (i1) * d length=n maxsize 0 1 i2 i1 i n1 a2 … ai1 ai ai+1 a1 … an 下一頁 上一頁 停止放映 [第 27/42頁 ] 線性表元素存儲示意圖 a1 a2 …. ai …. 元素序號 內(nèi)存狀態(tài) 存儲地址 1 2 …. i …. LOC(a1) LOC(a1)+1 …. LOC(a1)+(i1) …. 下一頁 上一頁 停止放映 [第 28/42頁 ] 順序表類型描述 struct SeqList { ElemType *data。 // 順序表存儲數(shù)組的地址 int maxsize。 // 順序表最大允許長度 int length。 // 順序表當前長度 }； SeqList list。 // 定義一個線性表 list （ 1） ElemType代表數(shù)組的類型。 （ 2）數(shù)組 data需要在初始化函數(shù)中利用 new操作動態(tài)申請， maxsize為其長度。數(shù)組的下標從 0開始。 （ 3） length表示線性表當前長度，初始長度為 0（空表），最大不超過 maxsize。 下一頁 上一頁 停止放映 [第 29/42頁 ] 線性表的基本操作 Setnull（ L） 置空表 Length（ L） 求表長度；求表中元素個數(shù) Get（ L， i） 取表中第 i個元素（ 1?i ?n） Prior（ L， i） 取 i的前趨元素 Next（ L， i） 取 i的后繼元素 Locate（ L， x） 返回指定元素在表中的位置 Insert（ L， i， x） 插入元素 Delete（ L， x） 刪除元素 Empty（ L） 判別表是否為空 下一頁 上一頁 停止放映 [第 30/42頁 ] 順序表的主要算法 （ 1）順序表的初始化 順序表的初始化主要是為 ElemType類型的數(shù)組申請空間，下面的初始化函數(shù)為順序表申請了長度為 size的空間。 void Init( SeqList *L, int size ) { if( size 0 ) { Lmaxsize = size。 Llength = 0。 Ldata = new ElemType[size]。 //申請空間 } else cout線性表初始化長度錯誤 。 } 下一頁 上一頁 停止放映 [第 31/42頁 ] （ 2） 在表中第 i 個位置插入新元素 x 算法實現(xiàn)的主要步驟： ①判斷插入位置的合理性以及表是否已滿。 ②從最后一個元素開始依次向前，將每個元素向后移動一個位置，直到第 i個元素為止。 ③向空出的第 i個位置存入新元素 x。 ④最后還要將線性表長度加一。 示例 下一頁 上一頁 停止放映 [第 32/42頁 ]
試題試卷相關(guān)推薦
鄂ICP備17016276號-1