C語言簡單實作線性表的順序存盤
線性表的順序存盤結構，指的是用一段地址連續的存盤單元依次存盤線性表的資料元素，
線性表的順序存盤結構，實際上就是在記憶體中找一塊連續的存盤空間，然后將相同資料型別的資料元素存盤在這塊存盤空間中，所以用C語言中的一維陣列就可以實作順序存盤結構，
線性表的順序存盤結構優點在于可以快速隨機訪問表中任意位置的元素，并且因為其占用的一段連續的存盤空間，所以不需要為表示元素之間的邏輯關系來增加額外的存盤空間節省空間（相對） ，
而線性表的順序存盤結構的缺點就在于插入和洗掉操作需要移動大量元素，執行效率低，并且陣列的容量需要提前確定，因此可能造成空間浪費，
線性表的基本結構：
- 要存盤的資料
- 線性表長度
- 陣列的最大值
typedef struct{
ElemType data[MAX];
int length;
}SqList;
準備作業：
#include<stdio.h>
#define MAX 20
//陣列的最大長度
#define OK 1
#define error 0
//OK和error代表函式狀態，分別為1（函式成功運行），0（函式出錯）
typedef int Status;
//Status是函式型別，其值是函式結果狀態代碼，如OK代表成功，error代表出錯，
typedef int ElemType;
//ElemType代表陣列型別，根據實際情況確定，這里假設為int型
線性表的順序存盤結構的8種基本操作：
- 初始化
- 判斷線性表是否為空
- 清空線性表
- 回傳線性表的給定位置元素值
- 插入元素
- 洗掉元素
- 查找元素
- 合并線性表
下面給出具體分析：
線性表的初始化：
即將線性表的長度賦值為0
Status initList(SqList *L){
L->length = 0;
return OK;
}
判斷線性表是否為空:
這里我稍微做了一點改進，直接用bool回傳線性表為空的真偽：
長度為真，回傳 true，
長度為假，回傳 false，
//判斷線性表是否為空
bool ListEmpty(SqList L){
if(L.length == 0)
return true;
else
return false;
}
清空線性表：
與初始化一樣，將線性表的長度置為0，
Status ClearList(SqList *L){
L->length = 0;
return OK;
}
回傳線性表的給定位置元素值：
1.首先判斷該元素是否合理
- 最小位置不能小于1
- 最大位置不能大于線性表的長度
- 線性表的長度不能為0
2.然后將該位置元素的值賦值給e，
（因為要保留e的值，不能使e所占記憶體空間在函式呼叫完成后自動釋放，所以這里采用指標）
Status GetElem(SqList L,int i,ElemType *e){
if(i < 1 || i > L.length || L.length == 0)
return error;
*e = L.data[i-1];
return OK;
}
插入元素：
1.判斷限制條件，如果線性表已滿，插入位置不合理，則插入失敗，
2.如果是在最后一個位置，直接賦值即可
3.如果不在最后一個位置，從最后一個位置開始，全部后移一位，
4.長度加一，給即將插入的元素賦值
PS：因為陣列是從0開始計數的，所以對應線性表的位置，永遠減一
線性表改變，所以需要傳指標，
//插入操作：在 L中的第 i 個位置插入新元素 e
Status ListInsert(SqList *L,int i,ElemType e){
if(L.length == MAX)
return error;
//判斷線性表長度是否大于陣列長度
if(i < 1 || i > L.length + 1)
return error;
//判斷插入位置是否合理
if(i <= L.length){
for(int k = L.length - 1;k >= i - 1;k--)
L->data[k+1] = L->data[k];
//如果插入位置不在表的末尾，則從線性表的最后一個位置開始，所有元素向后移動一位
//一直到插入位置的前一個元素
}
L.length++;
L->data[i-1] = e;
//長度加一，為新插入的元素賦值
}
洗掉元素：
1.先判斷洗掉位置是否合理，具體如上，
2.將要洗掉的元素的值賦值給e，
3.如果是在最后一個位置，直接洗掉即可
4.如果不在最后一個位置，從該位置的后一位開始，全部前移一位，
4.長度減一，給即將插入的元素賦值
PS：因為陣列是從0開始計數的，所以對應線性表的位置，永遠減一，線性表改變，所以需要傳指標，需要獲得e的值，e也要傳指標，
//洗掉操作：洗掉 L 的第一個資料元素，并用 e回傳其值
Status ListDelete(SqList *L,int i,ElemType *e){
if(L->length == 0)
return error;
if(i < 1 || i > length)
return error;
*e = L->data[i-1];
if(i < L->length){
for(int k = i; k < L->length ;k++){
L->data[k-1] = L->data[k];
}
}
L->length--;
return OK;
}
查找元素：
1.線性表長度為0，查找失敗
2.遍歷陣列，成功則回傳其在線性表中的位置
Status LocateElem(SqList L,ElemType e){
if(L.length == 0)
return 0;
for(int i = 0;i < L.length;i++){
if(e == L.data[i])
return i + 1;
}
return 0;
}
合并兩個線性表（將Lb中的元素插入La）：
1.遍歷Lb中陣列，得到第i個位置對應元素的值，賦與e，
2.如果La中沒有對應的元素，將e的值插入到La的最后一個位置，
3.La長度加一，
//合并兩個陣列
Status ListUnion(SqList *La,SqList Lb){
ElemType e;
int La_len = La->length;
int Lb_len = Lb.length;
for(int i = 1 ; i <= Lb_len ; i++){
GetElem(Lb,i,&e);
if(!LocateElem(*La,e))
ListInsert(La,++La_len,e);
}
}
完整代碼實作（加入測驗）：
#include<stdio.h>
#define MAX 20
//陣列的最大長度
#define OK 1
#define error 0
typedef int Status;
//Status是函式型別，其值是函式結果狀態代碼，如OK代表成功，error代表出錯，
typedef int ElemType;
//ElemType代表陣列型別，根據實際情況確定，這里假設為int型
typedef struct{
ElemType data[MAX];
int length;
}SqList;
//初始化線性表
Status initList(SqList *L){
L->length = 0;
return OK;
}
//判斷線性表是否為空
bool ListEmpty(SqList L){
if(L.length == 0)
return true;
else
return false;
}
//輸出陣列資料
void ListTraverse(SqList L){
for(int i = 0; i < L.length; i++)
printf("%d ",L.data[i]);
printf("\n");
}
//清空線性表
Status ClearList(SqList *L){
L->length = 0;
return OK;
}
//用e回傳L中第 i個資料元素的值
Status GetElem(SqList L,int i,ElemType *e){
if(i < 1 || i > L.length || L.length == 0)
return error;
*e = L.data[i-1];
return OK;
}
//查找元素 e
Status LocateElem(SqList L,ElemType e){
if(L.length == 0)
return 0;
for(int i = 0;i < L.length;i++){
if(e == L.data[i])
return i + 1;
}
return 0;
}
//插入操作：在 L中的第 i 個位置插入新元素 e
Status ListInsert(SqList *L,int i,ElemType e){
if(L->length == MAX)
return error;
//判斷線性表長度是否大于陣列長度
if(i < 1 || i > L->length + 1)
return error;
//判斷插入位置是否合理
if(i <= L->length){
for(int k = L->length - 1;k >= i - 1;k--)
L->data[k+1] = L->data[k];
//如果插入位置不在表的末尾，則從線性表的最后一個位置開始，所有元素向后移動一位
//一直到插入位置的前一個元素
}
L->length++;
L->data[i-1] = e;
//長度加一，為新插入的元素賦值
}
//洗掉操作：洗掉 L 的第一個資料元素，并用 e回傳其值
Status ListDelete(SqList *L,int i,ElemType *e){
if(L->length == 0)
return error;
if(i < 1 || i > L->length)
return error;
*e = L->data[i-1];
if(i < L->length){
for(int k = i; k < L->length ;k++){
L->data[k-1] = L->data[k];
}
}
L->length--;
return OK;
}
//合并兩個陣列
Status ListUnion(SqList *La,SqList Lb){
ElemType e;
int La_len = La->length;
int Lb_len = Lb.length;
for(int i = 1 ; i <= Lb_len ; i++){
GetElem(Lb,i,&e);
if(!LocateElem(*La,e))
ListInsert(La,La_len++,e);
}
}
int main(){
SqList L,Lb;
ElemType e;
Status r;
r = initList(&L);
int k;
printf("初始化L后,L.length = %d\n",L.length);
for(int i = 1; i <= 5 ; i++){
r = ListInsert(&L,1,i);
}
printf("在L的表頭依次插入1-5后：L.data = ");
ListTraverse(L);
printf("L.length = %d\n",L.length);
if(ListEmpty(L))
printf("L為空\n");
else
printf("L不為空\n");
r = ClearList(&L);
printf("清空L后,L.length = %d\n",L.length);
if(ListEmpty(L))
printf("L為空\n");
else
printf("L不為空\n");
for(int i = 1; i <= 10 ; i++){
ListInsert(&L,i,i);
}
printf("在L的表頭插入1-10后，L.data = ");
ListTraverse(L);
printf("L.length = %d\n",L.length);
ListInsert(&L,1,0);
printf("在L的表頭插入0后：L.data= ");
ListTraverse(L);
printf("L.length=%d\n",L.length);
GetElem(L,5,&e);
printf("第5個元素的值為:%d\n",e);
for(int i = 3;i <= 4; i++){
r = LocateElem(L,i);
if(r == 0)
printf("沒有值為%d的元素\n",r);
else
printf("第%d個元素的值為:%d\n",r,i);
}
k = L.length;
for(int i = k + 1 ; i >= k ;i--){
r = ListDelete(&L,i,&e);
if(r == error)
printf("洗掉第%d個元素失敗！\n",i);
else
printf("洗掉第%d個元素的值為%d\n",i,e);
}
printf("依次輸出L的元素: ");
ListTraverse(L);
r = 5;
ListDelete(&L,r,&e);
printf("洗掉第%d個元素的值為%d\n",r,e);
printf("依次輸出L的元素: ");
ListTraverse(L);
r = initList(&Lb);
for(int i = 6;i <= 15; i++){
r = ListInsert(&Lb,1,i);
}
ListUnion(&L,Lb);
printf("依次輸出合并了Lb的L的元素：");
ListTraverse(L);
return 0;
}
第一次發布博客，有問題還望大家指出，
（水平菜的一批，哈哈）
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/277719.html
標籤：其他