線性表是什么樣子呢？
類似這種，可以當作生活中流水線作業是一樣的，
線性表是由n(N>=0）個資料元素（結點）比如a1,a2,a3....an組成的有限序列
資料元素的個數n定義為表的長度，
當n=0時為空表（null)
當n>0時為非空表 L=（a1....an）
a1稱為起始點 ，an為終端結點，
對任意一堆相鄰結點ai和ai+1 （1<i<n) ai是ai+1的直接前驅，ai+1是ai的直接后繼
（圖片來源于網路）
如果吧線性表當作火車就更加明顯了，火車只有一個火車頭（起始節點）一個車尾（終端結點）
火車頭（起始節點）前面沒有車廂（直接前驅） 但是后面又一節車廂 （直接后繼），車尾（終端結點）后面沒有多余的車尾（直接后繼） ，但是車尾的前面有一節車廂（直接前驅），
綜上可以了解出每一個結點且都有一個直接前驅和一個直接后繼
線性表的邏輯結構特征
對于非空的線性表：線性表中結點具有一對一的關系(具體可以看上面的火車例子）
1）線性表中有且僅有一個其實結點a1,沒有直接前驅，有且僅有一個直接后繼a2;
2)有且僅有一個終端結點an,沒有直接后繼，有些僅有一個直接前驅an-1;
3)其余的內部結點ai(a<=i<=n-1)都有且僅有一個直接前驅ai-1和一個直接后繼ai+1;
線性表的基本運算
初始化 Initiate 秋表長度Length 取表元 get 定位 Locate 插入Insert 洗掉Delete
線性表順序存盤的方法是：將表中的結點依次存放在計算機記憶體中一組連續的存盤單元中，資料元素在線性表中的鄰接關系決定它們在存盤空間中的存盤位置，即邏輯結構中相鄰的結點其存盤位置也相鄰，
用順序存盤實作的線性表稱為順序表，一般使用陣列來表示順序表，
假定有一組資料，資料間有順序：13 4 5 15 9 53 24 50 88 42 11
此處資料間的順序即表示資料間的邏輯關系即線性關系，這一組資料為線性表：
假設已知a1地址為loc(a1),每個資料占c個單元，則計算ai地址
Loc(ai)=Loc(a1)+c*(i-1)
比如 a3 的地址
1 a1=0 2 3 Loc(a3)=a1+(3-1) 4 5 =0+2 6 7 =2
初始化
strudt student{
int ID；//ID
char name[30];//姓名
char sex; //性別
int class;//班級
int age;//年齡
}
student={"01"，“zhangsan”,"m","201","20"}；
插入
線性表的插入運算是指在表的第i（1<=i<=n+1)個位置上，插入一個新結點x，使長度為n的線性表“:(a1,....ai-1,ai,ai+1,....an)
變成長度為n+1的線性表：
（a1,...ai-1,x,ai,ai+1,....an)
1)當表空間已滿，不可在做插入操作
2）當插入位置為非法位置，不可做正常插入操作
void InsertSeqlist (SeqList l,dataType x,int i){ if (l.length==Maxsize)exit("表已滿"）； if(i<1||l.length+1) exit (”位置錯誤“);//插入位置是否正確 for(j=l.length;j>=i;j--){//初始化i=l.length l.data[j]=l.data[j-1];//依次后移 l.data[i-1]=x;//元素x置入到下標為i-1的位置 l.length++;}//表長度加1
假設線性表中含有n個資料元素，
在進行插入操作時，有 n+1個位置可插入
在每個位置插入資料的概率是：1/(n+1)
在i位置插入時，要移動n-i+1 個資料
平均時間復雜度為O(n)
洗掉
線性表的洗掉運算是指將表的i的結點刪去，使長度為n的線性表長度”減一“
當要洗掉元素的位置I不在表長范圍內（即i<1或i->length）時，為非法位置，不能做正常的洗掉操作
操作程序：
1，若i=n,則只要洗掉終端結點，無需移動結點；
2，若1<=i<=n-1,則必須將表中位置i+1,i+2,,,,,n的結點，依次前移到位置I
3,該表長度減1
void DeleteSeqList(SeqList L,int i) {
//洗掉線性表L中的第i個資料結點
if(i<1 || i>L.length) //檢查位置是否合法
exit(“非法位置”);
for(j=i;j<L.length;j ++) //第i個元素的下標為i-1
L.data[j-1]=L.data[j]; //依次左移
L.length--; //表長度減1
}
洗掉演算法的分析
假設線性表中含有n個資料元素，
在進行洗掉操作時，有 n位置可洗掉
在每個位置洗掉資料的概率是：1/n
在i位置洗掉時，要移動 n-i+1個資料
假定在n個位置上洗掉元素的可能性均等，
平均時間復雜度為O(n)順序存盤結構表示的線性表，在做插入或洗掉操作時，平均需要移動大約一半的資料元素，
當線性表的數據元素量較大，并且經常要對其做插入或洗掉操作時，這一點需要值得考慮
定位（查找）
定位運算LocateSeqlist(L,X)的功能是
求L中值等于X的結點序號的最小值，
當不存在這種結點時結果為0 從第一個元素 a1 起依次和x比較，直到找到一個與x相等的資料元素，則回傳它在順序表中的存盤下標或序號；或者查遍整個表都沒有找到與 x 相等的元素，回傳0
int LocateSeqlist(SeqList L, DataType x)
{
int i=0;
while ((i<L. length) && (L.data[i]!=x) ) //在順序表中查找值為 x 的結點
i++;
if(i<L.length) return i+1; //若找到值為x的元素，回傳元素的序號
else return 0; //未查找到值為x的元素，回傳0
}
//順序表的求表長操作，直接輸出L.length即可
（1）設表的長度length=n，在插入演算法中，元素的移動次數不僅與順序表的長度
n有關， 還與插入的位置i有關， 插入演算法在最壞情況下，其時間復雜度為O(n)，
一般情況下元素比較和移動的次數為n-i+1次，插入演算法的平均移動次數約為n/2，
其時間復雜度是O(n)，
（2）洗掉演算法DeleteSeqlist，可得其在最壞情況下元素移動次數為n-1，時間復雜
度為O(n)，元素平均移動次數約為（n-1） /2，時間復雜度為O(n)，
（3）對于定位演算法，需要掃描順序表中的元素，以引數x與表中結點值的比較為
標準操作，平均時間復雜度為O(n)，求表長和讀表元素演算法的時間復雜度為O(1)，
就階數而言，己達到最低
順序表的優點：
無需為表示結點間的邏輯關系而增加額外存盤空間
可以方便地隨機存取表中的任一結點
順序表的缺點：
? 插入和洗掉運算不方便，必須移動大量的結點
? 順序表要求占用連續的空間，存盤分配只能預先進
行，因此當表長變化較大時，難以確定合適的存盤
規模
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/117892.html
標籤：其他