線性表
線性表是包含若干資料元素的一個線性序列
- 線性表L可用二元組形式描述：
記為：L=(a0, … ai-1, ai, ai+1 … an-1)
L為表名，ai (0≤i≤n-1) 為資料元素；
n為表長,n>0 時，線性表L為非空表，否則為空表，
L=（D，R） D=date R=relation
即線性表L包含陣列元素集合D和關系集合R
D={ai | ai∈datatype ,i=0,1,2, ?????????n-1,n≥0}
R={<ai , ai+1> | ai , ai+1∈D, 0≤i≤n-2}
- 關系符<ai, ai+1>在這里稱為有序對
- 表示任意相鄰的兩個元素之間的一種先后次序關系
- ai是ai+1的直接前驅, ai+1是ai的直接后繼
線性表的特征
- 對非空表,a0是表頭,無前驅；
- an-1是表尾,無后繼；
- 其它的每個元素ai有且僅有一個直接前驅ai-1和一個直接后繼ai+1，
線性表的順序存盤
- 若將線性表L=(a0,a1, ……,an-1)中的各元素依次存盤于計算機一片連續的存盤空間，設Loc(ai)為ai的地址，Loc(a0)=b，每個元素占d個單元 則：Loc(ai)=b+i*d
順序存盤結構的不足：
線性表的順序存盤結構有存盤密度高及能夠隨機存取等優點，但存在以下不足：
- 要求系統提供一片較大的連續存盤空間，
- 插入、洗掉等運算耗時，且存在元素在存盤器中成片移動的現象.
順序存盤結構的特點
- 邏輯上相鄰的元素 ai, ai+1，其存盤位置也是相鄰的
- 對資料元素ai的存取為隨機存取或按地址存取
- 存盤密度高
- 存盤密度D=(資料結構中元素所占存盤空間)/（整個資料結構所占空間）
順序存盤結構的表示
- 在C語言中，可借助于一維陣列型別來描述線性表的順序存盤結構
#define N 100
typedef int data_t;
typedef struct
{ data_t data[N]； //表的存盤空間
int last;
} sqlist, *sqlink;
線性表的基本運算
設線性表 L=(a0,a1, ……,an-1)，對 L的基本運算有：
1.建立一個空表：list_create(L)
2.置空表：list_clear(L)
3.判斷表是否為空：list_empty (L)，若表為空，回傳值為1 , 否則回傳 0
4.求表長：length (L)
5.取表中某個元素：GetList(L , i ), 即ai，要求0≤i≤length(L)-1
6.定位運算：Locate(L,x)，確定元素x在表L中的位置（或序號）
定位：確定給定元素x在表L中第一次出現的位置（或序號），即實作Locate(L,x)，演算法對應的存盤結構如圖所示，
Locate(L,x)=
- i 當元素x=ai∈L,且ai是第一個與x相等時
- -1 x不屬于L時
7.插入：
Insert(L,x,i)，將元素x插入到表L中第i個元素ai之前,且表長+1，
插入前: (a0,a1,—,ai-1,ai,ai+1-------,an-1) 0≤i≤n,i=n時,x插入表尾
插入后: (a0,a1,—,ai-1, x, ai,ai+1-------,an-1)
演算法思路：若表存在空閑空間，且引數i滿足：0≤i≤L->last+1,則可進行正常插入，插入前，將表中（L->data[L->last]～L->data[i]）部分順序下移一個位置，然后將x插入L->data[i]處即可，演算法對應的表結構，
8.洗掉：
Delete(L,i)，洗掉表L中第i個元素ai，且表長減1, 要求0≤i≤n-1，
洗掉前: (a0,a1,—,ai-1,ai,ai+1-------,an-1)
洗掉后: (a0,a1,—,ai-1，ai+1-------,an)
洗掉：將表中第i個元素ai從表中洗掉，即實作DeleteSqlist(L, i)，
演算法思路： 若引數i滿足：0≤i≤L->last, 將表中L->data[i+1]∽L->data[L->last] 部分順序向上移動一個位置，覆寫L->data[i]，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/249474.html
標籤：其他
上一篇：字符大小寫轉換