第2章數(shù)據(jù)結(jié)構(gòu)及應(yīng)用概念及順序表-文庫(kù)吧資料
2024-08-02 09:18本頁(yè)面
【正文】 // 加“ 1”后，結(jié)果為“ 9” ?最后，得到的結(jié)果數(shù)列是 {4,5,8,10,21,25,30,43,59} 下一頁(yè) 上一頁(yè) 停止放映 [第 34/42頁(yè) ] void Insert( SeqList *L, int i, ElemType x ) { if( i1 || iLlength+1 || Llength==Lmaxsize ) cout插入位置錯(cuò)誤或表滿(mǎn) 。 Ldata[i1] = x。 j ) // length 是元素個(gè)數(shù) (8) Ldata[j+1]=Ldata[j]。 算法描述： ?從數(shù)列右邊開(kāi)始，即從第 8個(gè)元素開(kāi)始； ?為在第 5個(gè)元素“ 21”后插入“ 25”，則要把其后的 3個(gè)元素右移，移動(dòng)元素個(gè)數(shù)是 3（ 85）； for( int j=Llength1。 ④最后還要將線(xiàn)性表長(zhǎng)度加一。 ②從最后一個(gè)元素開(kāi)始依次向前，將每個(gè)元素向后移動(dòng)一個(gè)位置，直到第 i個(gè)元素為止。 //申請(qǐng)空間 } else cout線(xiàn)性表初始化長(zhǎng)度錯(cuò)誤 。 Llength = 0。 下一頁(yè) 上一頁(yè) 停止放映 [第 29/42頁(yè) ] 線(xiàn)性表的基本操作 Setnull（ L） 置空表 Length（ L） 求表長(zhǎng)度；求表中元素個(gè)數(shù) Get（ L， i） 取表中第 i個(gè)元素（ 1?i ?n） Prior（ L， i） 取 i的前趨元素 Next（ L， i） 取 i的后繼元素 Locate（ L， x） 返回指定元素在表中的位置 Insert（ L， i， x） 插入元素 Delete（ L， x） 刪除元素 Empty（ L） 判別表是否為空 下一頁(yè) 上一頁(yè) 停止放映 [第 30/42頁(yè) ] 順序表的主要算法 （ 1）順序表的初始化 順序表的初始化主要是為 ElemType類(lèi)型的數(shù)組申請(qǐng)空間，下面的初始化函數(shù)為順序表申請(qǐng)了長(zhǎng)度為 size的空間。數(shù)組的下標(biāo)從 0開(kāi)始。 // 定義一個(gè)線(xiàn)性表 list （ 1） ElemType代表數(shù)組的類(lèi)型。 // 順序表最大允許長(zhǎng)度 int length。 假定元素 a1的物理地址是 Loc(a1)，每個(gè)元素占 d個(gè)存儲(chǔ)單元，則第 i個(gè)元素的存儲(chǔ)位置為 ： Loc(ai) = Loc(a1) + (i1) * d length=n maxsize 0 1 i2 i1 i n1 a2 … ai1 ai ai+1 a1 … an 下一頁(yè) 上一頁(yè) 停止放映 [第 27/42頁(yè) ] 線(xiàn)性表元素存儲(chǔ)示意圖 a1 a2 …. ai …. 元素序號(hào) 內(nèi)存狀態(tài) 存儲(chǔ)地址 1 2 …. i …. LOC(a1) LOC(a1)+1 …. LOC(a1)+(i1) …. 下一頁(yè) 上一頁(yè) 停止放映 [第 28/42頁(yè) ] 順序表類(lèi)型描述 struct SeqList { ElemType *data。 下一頁(yè) 上一頁(yè) 停止放映 [第 26/42頁(yè) ] 順序表 采用順序存儲(chǔ)結(jié)構(gòu)的線(xiàn)性表稱(chēng)為順序表，它的數(shù)據(jù)元素按照邏輯順序依次存放在一組連續(xù)的存儲(chǔ)單元中。 形式定義： 含有 n個(gè)數(shù)據(jù)元素的線(xiàn)性表是一種數(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)系的有限集合。 例如，一星期七天的英文縮寫(xiě)表示： （ Sun， Mon， The， wed， Thu， Fri， Sat） 是一個(gè)線(xiàn)性表，其中的元素是字符串，表的長(zhǎng)度為 7。除了 a1和 an之外，任意元素 ai都有一個(gè)直接前趨 ai1和一個(gè)直接后繼 ai+1。討論方法與時(shí)間復(fù)雜度類(lèi)似，不再贅述。 下一頁(yè) 上一頁(yè) 停止放映 [第 22/42頁(yè) ] 時(shí)間復(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號(hào)-1