1、第二章線性表，2020/8/3，DS，線性結(jié)構(gòu)特征：數(shù)據(jù)元素的非空有限集合1 )存在唯一的被稱(chēng)為“第一”的數(shù)據(jù)元素2 )存在唯一的被稱(chēng)為“最后”的數(shù)據(jù)元素3 )除外。 最后，2020/8/3、DS、主要內(nèi)容、2020/8/3、DS、2.1線性表的定義和抽象數(shù)據(jù)類(lèi)型、2.1.1線性表的定義2.1.2線性表所包含的元素的個(gè)數(shù)是表的長(zhǎng)度，用n表示，為n0。 n=0表示一個(gè)空表。 一般來(lái)說(shuō)，(a1，a2，ai-1，ai，ai 1，an )或A=(a1，a2，ai-1，ai，ai 1，an )表示a1為第一元素的線性表中的元素根據(jù)前后位置而線性有序，即第I個(gè)元素ai在邏輯上為第i-1個(gè)元素2020/8/

2、3，DS，2.1.1線性表的定義，二元組表示線性列表=(a，R) A=ai|1in，n0， 例如：類(lèi)型空間元素； 邏輯圖：2020/8/3，DS，2.1.1線性表的定義，如果存在按值的升序或降序排列的字段則稱(chēng)為已排序字段，否則如果沒(méi)有已排序的字段則稱(chēng)為已排序表，否則如果沒(méi)有已排序的字段則稱(chēng)為已排序表假定c=(25、38、12、49、63、54、20、18“聯(lián)系人電話”、“E-mail”) F=(a、b、c、d、e、f、g、h、I、j、k、x、y、z )數(shù)據(jù)部分是線性表，并且用標(biāo)識(shí)符l表示操作部是對(duì)線性表的各種操作(運(yùn)算)，如在線性表中插入要素，從線性表中刪除要素，求線性表的長(zhǎng)度，判斷線性表是否

3、為空等。2020/8/3、DS、2.1.2線性表的抽象數(shù)據(jù)類(lèi)型、具有adtlinearlistisdata : listtype類(lèi)型的線性表l operation : voidinitlist () boolfindlist (listtypeendt 2.1.2線性表的抽象數(shù)據(jù)類(lèi)型，插入時(shí)pos約定為pos1且posn 1，插入第pos的pos=-1，插入表末尾的pos=0，線性表是規(guī)則表，插入后也是規(guī)則的。 刪除時(shí)pos取值，承諾pos1和posn，刪除第pos位置的元素pos=-1，刪除腳注元素pos=0，線性表是規(guī)則表，刪除表的第一個(gè)值等于指定值的元素。 設(shè)定為2020/8/3、DS、

4、2.1.3操作例、例2-1線性表l1=(25、38、19、42、33 )、i=2、x列表(l1)； 實(shí)體列表(l1)； 獲得者(l 1，I )； 插入列表(l 1、x、6 )； 插入列表(l 1、54、1 )； 刪除列表(l 1，y，0 )； 刪除列表(l 1、y、3 )； SortList(L1)； 插入列表(l 1，35，0 )； 五、假，(25、38、19、42、33、60 )、(54、25、38、19、42、33、60 )和(38 )。 2.1.3操作示例，示例2-2過(guò)程(course )記錄的結(jié)構(gòu)包括Struct course char Cname20； /課程名稱(chēng)int Chour

5、； 開(kāi)講時(shí)int Cterm； /開(kāi)課學(xué)期，對(duì)2020/8/3、DS、L2進(jìn)行一組操作： Course x=、72； Course y=“編程基礎(chǔ)”Course z=“英語(yǔ)”，80，1； Course w=“數(shù)據(jù)結(jié)構(gòu)”，72，4； 獲得者(l 2，3，3 )； 查找列表(l 2，x )； 查找列表(l 2，y )； 更新列表(l 2，z )； 插入列表(l 2、w、6 )； 刪除列表(l 2，y，0 )； SortList(L2)；2.1.3操作示例、2020/8/3、DS、2.2線性表的順序存儲(chǔ)和操作實(shí)現(xiàn)、2.2.1線性表的順序存儲(chǔ)結(jié)構(gòu)2.2.2順序存儲(chǔ)下的線性表操作實(shí)現(xiàn)、2020/8順序存

6、儲(chǔ)結(jié)構(gòu)圖：下標(biāo)位置排列(線性表)存儲(chǔ)空間、 各要素占有的存儲(chǔ)器空間大小為sizeof(ElemType )線性表整體占有的存儲(chǔ)器空間大小為n*sizeof(ElemType )第二要素的存儲(chǔ)器位置為a(I-的2.2.1線性表的順序存儲(chǔ)結(jié)構(gòu)，具體實(shí)現(xiàn)：在C/C中，將一個(gè)數(shù)組所分配的數(shù)組空間的數(shù)目確定存儲(chǔ)線性表的最大長(zhǎng)度，并且當(dāng)線性表的長(zhǎng)度超過(guò)所分配的最大尺寸時(shí)，該數(shù)組空間在末尾無(wú)法存儲(chǔ)，因此需要重新分配存儲(chǔ)空間。 類(lèi)型定義：結(jié)構(gòu)列表元素列表最大化； 英寸； /當(dāng)前路線表的長(zhǎng)度靜態(tài)分配一旦分配了空格，就無(wú)法擴(kuò)展。 只有MaxSize個(gè)。 要?jiǎng)討B(tài)分配數(shù)組空間以存儲(chǔ)2020/8/3、DS和線性表，并根

7、據(jù)需要增加數(shù)組長(zhǎng)度，請(qǐng)定義以下列表類(lèi)型： 結(jié)構(gòu)列表元素*列表； /指向存儲(chǔ)線性表元素的動(dòng)態(tài)存儲(chǔ)空間的指針int size； /存儲(chǔ)線的長(zhǎng)度int MaxSize； 定義list陣列的長(zhǎng)度的2.2.1線性表順序存儲(chǔ)結(jié)構(gòu)，在2020/8/3、DS、2.2.2順序存儲(chǔ)中實(shí)現(xiàn)線性表操作，1 .線性表初始化線性表完成動(dòng)態(tài)存儲(chǔ)空間的初始分配，并且線性表必須空白。 void InitList(List，2020/8/3，DS，2.2.2在順序存儲(chǔ)中實(shí)現(xiàn)線性表操作，2 .刪除線性表的所有元素使之為空的操作釋放動(dòng)態(tài)存儲(chǔ)空間，線性表的void cless DS，2.2.2依次存儲(chǔ)中的線性列表操作的實(shí)現(xiàn)，3 .得到

8、線性列表的長(zhǎng)度int LenthList(List，4 .的2.2.2依次存儲(chǔ)中的線性表操作的實(shí)現(xiàn)，5 .得到線性表中指定編號(hào)pos的要素這個(gè)操作首先判斷給出的pos是否輸出線性表操作的實(shí)現(xiàn)，按ElemType GetList(List，2020/8/3，DS，2.2.2順序存儲(chǔ)；6 .線性表的遍歷，這是從線性表的第一個(gè)元素到元素之間的邏輯次序；void trid 注意：如果表中的元素類(lèi)型是記錄類(lèi)型，則必須重新加載該類(lèi)型的操作符函數(shù)插入支持。實(shí)現(xiàn)按2020/8/3、DS、2.2.2順序存儲(chǔ)的線性表操作；7 .從線性表中查找具有特定值的第一個(gè)元素從線性表中查找等于item值或域值的元素時(shí)，item返回該元素的整體值如果布爾查找列表(列表，注意： ElemType為字符串類(lèi)型，則必須將if表達(dá)式更改為(strcmp(L.lesti，item)=0)。2020/8/3、DS、2.2.2依次存儲(chǔ)線性表操作的實(shí)現(xiàn)、8 .更新線性表中具有規(guī)定值的第1要素的操作與檢索的定義類(lèi)似，檢索在檢索成功后在item中帶回要素值，更新在