線性表的基礎(一)
線性表的儲存結構分為:順序表和連結串列
今天我們先介紹順序表:
線性表的順序儲存是指在記憶體中用地址連續 的一塊儲存空間順序存放線性表的各個元素,用這種儲存方式儲存的線性表也稱為順序表。
因為用連續的一塊儲存空間來存放,所以用陣列 datatype data [MAXSIZE] 來儲存,其中MAXSIZE是一個根據實際問題定義的足夠大的整數。
順序表的初始化:
SeqList*init-SeqList()
{ SeqList *L;
L= (SeqList*)malloc(sizeof(SeqList)); //L為指標變數,通過此操作獲得順序表的儲存空間
L->last = -1;//last起一個指標的作用,始終指向線性表中最後一個元素的位置,所以當表空時last的值為-1
return L;
}
設呼叫函式為主函式,主函式對初始化函式的呼叫如下
main()
{
SeqList*L;
L= Init-SeqList();
...
}
當然在初始化之前要將指標last 和 資料儲存區data封裝成一個結構體作為順序表的型別:
typedef struct
{
datatype data [MAXSIZE];
int last;
}SeqList;
所以也就容易知道
線性表的表長表示為:(*L).last+1,記為:L->last+1。
線性表中資料元素順序儲存的基址為:L->data。
線性表中資料元素的儲存或表示為:L->data[0]] ~ L->data[L->last]。
線性表的插入
線性表的插入是指在表的第i個位置插入一個值為x的新元素,插入後使原表長為n的表成為表長為n+1條
順序表上完成這一操作需要以下步驟。
1.將a[i]~a[n]順序向下移動,為新元素讓出位置。
2.將x置入空出的第i個位置。
3.修改last指標(相當於修改表長),使之仍指向最後一個元素。
下面是演算法:
int Insert-SeqList(SeqList*L,int i,datatape x)
{
int j;
if(L->last == MAXSIZE -1)
{ printf("表滿");
return (-1); //表空間已滿不能插入
}
if(i<1 || i> L->last + 2)
{ printf("位置錯");
return(0);
}
for(j=L->last;j>=i-1;j--)
L->data[j+1] = L->data[j]; //結點移動
L->data[i-1]=x; //新元素插入
L->last++; //last 仍指向最後元素 ,修改表長
return(1);
}
效能分析:順序表的插入運算,時間組要消耗在了資料的移動上,在第i個位置上插入,從a[i]~a[n]都要向後移動一個位置,也就一共需要移動n-i+1個元素,而 i>= 1 && i<=n+1 所以平均下來就移動了 n/2次,時間複雜度為O(n)。
本演算法注意以下問題。
1.順序表的儲存區域有MAXSIZE個儲存單元,所以在向順序表中做插入時先檢查表的空間是否滿了,在表滿的情況下做插入會產生溢位錯誤。
2.檢驗插入位置的有效性,這裡i的有效範圍是:i>= 1 && i<=n+1 ,其中n為表長。
3.注意資料移動的方向。
線性表的刪除
線性表的刪除運算是指將表中第i個元素從線性表中去掉,刪除後使原表長為n的線性表成為表長為n-1的線性表
順序表上完成這一操作需要以下步驟。
1.將a[i+1]~a[n]順序向前移動,為新元素讓出位置。
2.修改last指標相當於修改表長)使之仍指向最後一個元素。
演算法如下:
int Delete-SeqList(SeqList*L,int i)
{
int j;
if(i<1 || i> L->last + 1) //檢驗表空及刪除位置的合法性
{ printf("不存在第i個元素");
return(0);
}
for(j=i;j<=L->last;j++)
L->data[j-1] = L->data[j]; //結點移動
L->last--; //last 仍指向最後元素 ,修改表長
return(1);
}
效能分析:順序表的刪除運算,時間組要消耗在了資料的移動上,刪除第i個元素時,從a[i+1]~a[n]都要向前移動一個位置,也就一共需要移動n-i個元素,而 i>= 1 && i<=n 所以平均下來就移動了 n/2次,時間複雜度為O(n)。
本演算法注意以下問題。
1.刪除第i個元素,i的取值為 i>= 1 && i<=n,否則第i個元素不存在,因此,要檢查刪除位置的有效性。
2.當表空時不能做刪除,因表空時L->last =-1,條件(i<1 || i> L->last + 1)也包括了對錶空的檢查。
3.刪除完a[i]之後,該資料已不存在,如果需要,先取出a[i],再做刪除。
線性表的按值查詢
線性表的按值查詢是指線上性表中查詢與給定值x相等的元素。在順序表中完成該運算最簡單的方法是:從第一個元素起依次和x比較,直到找到一個與x相等的資料元素,返回他在順序表中的儲存下標或序號(二者差一,即序號=下標+1),或者查遍整個表都沒有找到與x相等的元素,返回-1。
演算法如下
int Location-SeqList(SeqList*L,datatype x)
{ int i= 0;
while(i<=L->last && L->data[i] != x)
i++;
if(i>L->last)
return -1; // 查詢失敗,返回值為-1。
else
return i; // 查詢成功,返回儲存位置。
}
效能分析:本演算法的主要運算是給定值x與表中的元素相比較。顯然,比較的次數與x在表中的位置有關,也與表長有關。當a[1]=x時,比較一次成功。當a[n]=x時,比較n次成功,所以平均下來就移動了 n/2次,時間複雜度為O(n)。
當然,查詢失敗的情況下,需要比較n次。顯然時間複雜度為O(n)。
============================================================================================================================================================
本篇是我第一次寫,寫的不好還請見諒,如果有問題的話可以留言,我一定會回覆,對了,我寫這個是每日一更的哦~