第2章數(shù)據(jù)結(jié)構(gòu)及應(yīng)用概念及順序表-文庫吧資料
2024-08-02 09:18本頁面
【正文】 // 加“ 1”后，結(jié)果為“ 9” ?最后，得到的結(jié)果數(shù)列是 {4,5,8,10,21,25,30,43,59} 下一頁 上一頁 停止放映 [第 34/42頁 ] void Insert( SeqList *L, int i, ElemType x ) { if( i1 || iLlength+1 || Llength==Lmaxsize ) cout插入位置錯誤或表滿 。 Ldata[i1] = x。 j ) // length 是元素個數(shù) (8) Ldata[j+1]=Ldata[j]。 算法描述： ?從數(shù)列右邊開始，即從第 8個元素開始； ?為在第 5個元素“ 21”后插入“ 25”，則要把其后的 3個元素右移，移動元素個數(shù)是 3（ 85）； for( int j=Llength1。 ④最后還要將線性表長度加一。 ②從最后一個元素開始依次向前，將每個元素向后移動一個位置，直到第 i個元素為止。 //申請空間 } else cout線性表初始化長度錯誤 。 Llength = 0。 下一頁 上一頁 停止放映 [第 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的空間。數(shù)組的下標(biāo)從 0開始。 // 定義一個線性表 list （ 1） ElemType代表數(shù)組的類型。 // 順序表最大允許長度 int length。 假定元素 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。 下一頁 上一頁 停止放映 [第 26/42頁 ] 順序表 采用順序存儲結(jié)構(gòu)的線性表稱為順序表，它的數(shù)據(jù)元素按照邏輯順序依次存放在一組連續(xù)的存儲單元中。 形式定義： 含有 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)系的有限集合。 例如，一星期七天的英文縮寫表示： （ Sun， Mon， The， wed， Thu， Fri， Sat） 是一個線性表，其中的元素是字符串，表的長度為 7。除了 a1和 an之外，任意元素 ai都有一個直接前趨 ai1和一個直接后繼 ai+1。討論方法與時間復(fù)雜度類似，不再贅述。 下一頁 上一頁 停止放映 [第 22/42頁 ] 時間復(fù)雜度舉例 （ a） X： =X+1 ； （ b） FOR I： =1 TO n DO X： = X+1； （ c） FOR I： = 1 TO n DO FOR J： = 1 TO n DO X： = X+1； O（
試題試卷相關(guān)推薦
鄂ICP備17016276號-1