之前講了集合的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，今天接著聊下一個(gè)基本的數(shù)據(jù)結(jié)構(gòu)--線性表，線性表是線性數(shù)據(jù)結(jié)構(gòu)的一種表現(xiàn)形式
數(shù)據(jù)結(jié)構(gòu)之集合的順序存儲(chǔ)結(jié)構(gòu)
數(shù)據(jù)結(jié)構(gòu)之集合的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
線性表的定義
線性表是同一類型數(shù)據(jù)的一個(gè)有限序列，線性表中數(shù)據(jù)元素之間的關(guān)系是一對(duì)一的關(guān)系，即除了第一個(gè)和最后一個(gè)數(shù)據(jù)元素之外，其它數(shù)據(jù)元素都是首尾相接的。
線性表的順序存儲(chǔ)要求地址空間是連續(xù)的，地址必須一個(gè)接一個(gè)，不能中斷。如下圖為順序存儲(chǔ)結(jié)構(gòu)：
順序存儲(chǔ)結(jié)構(gòu)
線性表的順序存儲(chǔ)每個(gè)節(jié)點(diǎn)只包含數(shù)據(jù)部分，不需要額外包含數(shù)據(jù)之間的關(guān)系，因?yàn)閿?shù)據(jù)之間的關(guān)系通過地址連續(xù)來體現(xiàn)，所以非常省空間
它的優(yōu)點(diǎn)訪問非?？焖?，因?yàn)榈刂肥沁B續(xù)的，只要知道首地址，任意一個(gè)元素的地址都可以算出來。假設(shè)每個(gè)地址占c個(gè)空間,則第i個(gè)地址為(i-1)*c。
它的缺點(diǎn)是在插入和刪除數(shù)據(jù)時(shí)，可能要移動(dòng)許多數(shù)據(jù),比如一個(gè)10000個(gè)元素的有序數(shù)據(jù)，如果我刪除了第二個(gè)元素，為了繼續(xù)保持地址連續(xù)，所以要把后面9999個(gè)元素都向前移動(dòng)。
線性表的抽象數(shù)據(jù)類型定義如下：
ADT Set is
? Data:
? ? ? ? 采用任何一種存儲(chǔ)方法存儲(chǔ)的一個(gè)線性表
? ? Operation:
? ? ? initList() //初始化集合
? ? ? add(obj,pos)//向第pos個(gè)位置添加元素
? ? ? remove(pos)//刪除第pos個(gè)位置的元素
? ? ? find(obj)//查找元素并返回其位置
? ? ? value(pos)//返回第pos個(gè)位置元素的值
? ? ? modify(obj,pos)//修改第pos個(gè)位置的元素為obj
? ? ? size()//獲取線性表的長度
? ? ? isEmpty//判斷線性表是否為空
? ? ? clear()//清空線性表
? ? ? forward()//正向遍歷輸出線性表中的所有值
? ? ? backward()//反向遍歷輸出線性表中的所有值
? ? ? sort()//根據(jù)當(dāng)前線性表，返回一個(gè)排好序的線性表
線性表的順序存儲(chǔ)結(jié)構(gòu)和操作實(shí)現(xiàn)
下面把線性表用java實(shí)現(xiàn)，首先定義一個(gè)線性表操作的接口，List
下面對(duì)線性表進(jìn)行初始化
插入操作add，時(shí)間復(fù)雜度O（n）
刪除操作remove,時(shí)間復(fù)雜度O(n)
查找元素find,時(shí)間復(fù)雜度O(n)
獲取第i個(gè)位置元素,時(shí)間復(fù)雜度O(1)
修改某個(gè)位置元素modify,時(shí)間復(fù)雜度O(1)
判空isEmpty，清空線性表clear和獲取線性表元素長度size,時(shí)間復(fù)雜度O(1)
正向遍歷forward和反向遍歷backward,時(shí)間復(fù)雜度O(n)
根據(jù)當(dāng)前線性表，返回一個(gè)排好序的線性表sort,時(shí)間復(fù)雜度O(n*n)
其中用了插入排序?qū)€性表進(jìn)行排序，如果插入排序忘記了的話，可以看看我這篇博文
測試及結(jié)果
好了，今天就到這里了，后面接著講有序線性表的實(shí)現(xiàn)和線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
