溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇“C語言線性順序表如何實現”文章的知識點大部分人都不太理解，所以小編給大家總結了以下內容，內容詳細，步驟清晰，具有一定的借鑒價值，希望大家閱讀完這篇文章能有所收獲，下面我們一起來看看這篇“C語言線性順序表如何實現”文章吧。
線性表是最常用且最簡單的一種數據結構。簡而言之，一個線性表是n個數據元素的有限序列
線性表的順序表示指的是用一組地址連續的存儲單元依次存儲線性表的數據元素。 實現工具：dev 順序表示要實現的功能：
1.構造一個空的線性表
2. 對線性表進行賦值
3. 對線性表進行銷毀
4. 對線性表進行重置
5. 判斷線性表是否為空
6. 獲取線性表的長度
7. 獲取線性表某一位置對應的元素
8. 在線性表某一位置插入元素
9. 刪除線性表某一位置的元素
10. 求線性表某一元素的前驅
11. 求線性表某一元素的后繼
12. 打印線性表
13. 退出
1.在dev新建一個Source File文件即可 File>new>Source File
在實現程序時導入的頭文件有
#include<stdio.h> #include<stdlib.h> #include<malloc.h> #include<windows.h>
在這里我調用windows頭文件是為了在后面的代碼中修改控制臺的名稱，在實現線性表的順序結構時真正用到的只有前三個頭文件
在寫代碼之前先對一些表示結果狀態的字符進行預定義：
//函數結果狀態字符 #define TRUE 1 //代碼中出現TRUE相當于出現了1 #define FALSE 0 //出現FALSE相當于出現了0 #define OK 1 //出現OK相當于出現了1 #define ERROR 0 //出現ERROR相當于出現了0 #define INFEASIBLE -1 #define OVERFLOW -2 . typedef int Status; typedef int ElemType;
在這里使用了typedef定義了Status和ElemType為int類型，也就是說之后的代碼當中如果出現了Status和ElemType，它們與int作用相同
#define LIST_INIT_SIZE 100 //線性表存儲空間的初始分配量
#define LISTINCREMENT 10 //線性表存儲空間的分配增量
typedef struct{
ElemType *elem; //存儲空間的基址
int length; //當前線性表的長度
int listsize; //當前線性表的存儲容量
}SqList;//構造一個空的線性表
Status InitList_Sq(SqList &L){
L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType)); //L.elem為首元素的地址
if(!L.elem){ //如果存儲空間分配失敗，L.elem為NULL
printf("存儲空間分配失敗\n");
exit(OVERFLOW);
}
L.length = 0; //當前線性表為空表，即線性表長度為0
L.listsize = LIST_INIT_SIZE; //給線性表分配初始容量
printf("一個空的線性表已經構建成功\n"); //輸出空線性表構建成功的提示消息
return OK;
}在構造空線性表時參數加&符號表示引用傳遞，確保形參和實參同時改變 L.elem為線性表首元素的地址，L.length為當前線性表的長度，L.listsize為順序表當前分配空間的大小 我們現在來簡單的介紹一下sizeof函數 sizeof函數：獲取數據在內存中所占用的存儲空間（以字節為單位來計數） 圖示：
Status ValueList_Sq(SqList &L){
int i,j;
printf("請輸入線性表元素的個數：");
scanf("%d",&i);
if(i > L.listsize) //如果當要輸入的元素個數大于內存大小時
{
while(1) //一直開辟新空間，直到開辟的空間大于需要的空間為止
{
if(i > L.listsize){
L.elem = (ElemType *)realloc(L.elem,LISTINCREMENT * sizeof(ElemType));
L.listsize += LISTINCREMENT;
}
else
break;
}
}
for(j = 0;j < i;j++){
printf("請輸入第%d個元素：",j + 1);
scanf("%d",&L.elem[j]);
}
L.length = i; //賦值完成后，修改并保存線性表的長度
printf("賦值成功\n");
return OK;
}這里的形參同樣要加&符號來確保形參與實參同時改變 進行線性表賦值操作時用到了realloc函數，在這里簡單的介紹一下realloc函數的作用 realloc()函數：重新分配空間
參數：原空間基址，現需空間大小
返回值：1. 成功：新空間地址(本質上是一個數值) 2. 失敗：NULL 當我們在輸入線性表元素個數大于構造空線性表給線性表分配初始容量時，要一直開辟新空間，直到開辟的空間大于需要的空間為止
Status DistoryList_Sq(SqList &L){
if(!L.elem){
printf("您還未建立線性表，請先建立線性表\n");
return ERROR;
}
free(L.elem); //使用free函數，將之前動態分配的內存還給系統
L.elem = NULL; //重置elem的值為Null
L.length = 0; //將線性表的元素個數重置為0
L.listsize = 0; //將線性表的存儲容量重置為0
printf("線性表已經銷毀\n");
return OK;
}在銷毀線性表時，首先先對線性表是否存在進行判斷，如果線性表不存在，L.elem為NULL，所以此時！L.elem為true，執行后面的return ERROR; L.elem中存儲的是初始化是動態分配內存首元素的地址，free函數的作用就是將之前動態分配的內存還給系統，但是在調用free函數之后，雖然歸還了內存，但是L.elem中仍然指向原來的地址，而這個地址在歸還內存之后程序便無權進行訪問，所以此時L.elem就成了一個野指針，我們重置L.elem為NULL就是為了防止發生野指針訪問的情況，接著將線性表元素的個數L.length和存儲容量L.listsize重置為0
//對線性表進行重置
Status ClearList_Sq(SqList &L){
if(L.elem){ //如果線性表存在
L.length = 0; //將線性表的元素個數重置為0
printf("線性表已重置\n");
return OK;
}
else
printf("線性表不存在，無法重置\n");
return OK;
}重置線性表時仍然先對線性表是否存在進行判斷，如果線性表存在只需將線性表元素個數L.length重置為0即可，不需要改變其它變量
//判斷線性表是否為空
Status ListEmpty_Sq(SqList L){
if(L.elem){ //判斷線性表是否為空的前提是線性表存在，當首元素地址即L.elem存在時說明線性表存在
if(L.length != 0){ //如果線性表中元素為0，即L.length的值為0時說明線性表是空表
printf("線性表不是空表\n");
return FALSE;
}
else
printf("線性表是空表\n");
return TRUE;
}
else
printf("線性表不存在，無法判斷\n");
return OK;
}判斷線性表是否為空只需要看線性表當中的元素個數L.length是否為0即可，如果為0，則說明線性表是空表；不等于0則說明該線性表不為空
//獲取線性表的長度
Status ListLength_Sq(SqList L){
if(L.elem){ //判斷當前線性表存在
int K;
K = L.length; //將線性表的元素個數賦值給K
printf("線性表長度為%d\n",K);
return OK;
}
else
printf("線性表不存在，無法判斷\n");
return OK;
}線性表的長度是由當前線性表中的元素個數來體現的，所以獲取線性表的長度僅需定義一個int類型變量，并將L.length賦值給K即可
//獲取線性表某一位置對應的元素
Status GetElem_Sq(SqList L,int index){
int Num;
if(index <= 0 || index > L.length){ //如果要獲取元素的位置是否出界
printf("請輸入一個有效的數字\n");
return ERROR;
}
else
Num = L.elem[index - 1];
printf("第%d個位置的元素為：%d\n",index,Num);
return OK;
}同樣地，獲取線性表某一位置對應的元素時先判斷要獲取的位置是否合法，和判斷線性表的長度一樣，只需要將L.elem[index-1]位置的元素賦值給一個int型變量Num即可（index-1是因為數組元素的下標是從0開始的）
//在線性表某一位置插入元素
Status ListInsert_Sq(SqList &L,int i,ElemType e){
ElemType *newbase;
int *q,*p;
if(i < 1 || i > L.length+1) //判斷插入位置的index值是否合法
return ERROR;
if(L.length >= L.listsize){ //如果當前線性表存儲空間已滿，增加分配
newbase = (ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));
if(!newbase) { //如果存儲空間分配失敗，則執行異常退出
printf("存儲空間分配失敗\n");
exit(OVERFLOW);
}
L.elem = newbase; //新的存儲空間基址
L.listsize += LISTINCREMENT;
}
q = &(L.elem[i-1]); //L.elem[index-1]為數組中的最后一個元素，q為要插入的位置
for(p = &(L.elem[L.length - 1]);p >= q;--p)
*(p+1) = *p; //要插入位置以及之后的位置向后移
*q = e; //將e插入到想要插入的位置
++L.length; //插入新的元素之后表長加1
printf("元素插入成功\n");
return OK;
}在線性表中的某一位置插入一個元素，同樣要先判斷要插入的位置是否合法，接著就是判斷線性表是否已滿，如果線性表沒有存儲位置，則需要通過realloc函數重新分配一塊空間，要想在某一位置插入一個元素，首先要將這個想要插入元素的位置空出來，所以在插入元素時要先從表尾開始到想要插入元素的位置將元素依次向后移動一位 realloc函數如果分配空間成功的話返回的就是新空間的地址，但是本質上是一個數值，因此就需要進行強制類型轉換，將數值改成指針類型
圖示：
在這里要強調一點這一條語句，為什么不直接將newbase直接賦值給L.elem，要先進行判斷是否分配存儲成功？
if(!newbase) { //如果存儲空間分配失敗，則執行異常退出
printf("存儲空間分配失敗\n");
exit(OVERFLOW);
}
L.elem = newbase;如果分配空間失敗，此時的newbase的值為NULL，所以此時L.elem就會被賦值為NULL，原信息丟失 插入元素后，表長加一
//刪除線性表某一位置的元素
Status DeleteList_Sq(SqList &L,int i){
int *p,*q;
if(i < 1 || i > L.length){ //如果要刪除的位置不合法
printf("請輸入一個有效數字\n");
return ERROR;
}
p = &(L.elem[i - 1]); //p為被刪除元素的位置
q = L.elem + L.length - 1; //將表尾元素的位置賦值給q
for(++p;p <= q;p++)
*(p - 1) = *p; //被刪除的元素之后的元素全部左移
--L.length; //表長減1
printf("第%d個元素刪除成功\n",i);
return OK;
}L.elem + L.length - 1為表尾元素，刪除元素相比起插入元素要簡便些，不需要進行后移操作，數據向前覆蓋，刪除完成后表長減1即可。如果有需要的話，可以單獨定義一個int類型的變量在進行刪除操作之前將要刪除的元素賦值給該變量。
//求線性表某一元素的前驅
Status PriorElem_Sq(SqList L,int i){
int K;
if(L.elem){ //判斷線性表是否為空的前提是線性表存在，當首元素地址即L.elem存在時說明線性表存在
if(i <= 1 || i > L.length + 1) //判斷輸入的i值是否合法
printf("請輸入一個有效數字\n");
K = L.elem[i - 2]; //將第i個元素的前一個元素賦值給K
printf("第%d個位置的直接前驅為：%d\n",i,K);
}
else
printf("線性表不存在，無法判斷\n");
return OK;
}求前驅時除了要判斷線性表是否存在外，只需要將L.elem[i-2]賦給int型變量K即可
//求線性表某一元素的后繼
Status NextElem_Sq(SqList L,int i){
int K;
if(L.elem){ //判斷線性表是否為空的前提是線性表存在，當首元素地址即L.elem存在時說明線性表存在
if(i <= 1 || i > L.length - 1) //判斷輸入的i值是否合法
printf("請輸入一個有效數字\n");
K = L.elem[i]; //將第i個元素的后一個元素賦值給K
printf("第%d個位置的直接后繼為：%d\n",i,K);
}
else
printf("線性表不存在，無法判斷\n");
return OK;
}求后繼和求前驅除了在元素位置上有區別外，其余的思路都一致，在此不多做贅述
//打印線性表
Status PrintList_Sq(SqList L){
printf("當前線性表的元素為：");
for(int K = 0;K < L.length;K++) //遍歷當前線性表
printf(" %d",L.elem[K]);
printf("\n"); //換行
return OK;
}為了方便演示，在這里線性表一次賦值為1,2,3,4,5
構建一個空線性表
賦值操作
判斷此時的線性表是否為空
獲取線性表的長度
獲取2號位置的元素
在3號位置插入520并打印線性表
刪除3號位置的520并打印線性表
求3號位置的前驅和后繼
以上便是線性表順序表示和實現，由于高級程序設計語言中的數組類型也有隨機存取的特性，因此，通常用數組來描述數據結構中的順序存儲結構。在這種結構中，很容易實現線性表的某些操作，但是需要特別注意的是C語言的數組下標是從“0”開始。
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<windows.h>
//函數結果狀態代碼
#define TRUE 1 //代碼中出現TRUE相當于出現了1
#define FALSE 0 //出現FALSE相當于出現了0
#define OK 1 //出現OK相當于出現了1
#define ERROR 0 //出現ERROR相當于出現了0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef int ElemType;
#define LIST_INIT_SIZE 100 //線性表存儲空間的初始分配量
#define LISTINCREMENT 10 //線性表存儲空間的分配增量
typedef struct{
ElemType *elem; //存儲空間的基址
int length; //當前線性表的長度
int listsize; //當前線性表的存儲容量
}SqList;
//構造一個空的線性表
Status InitList_Sq(SqList &L){
L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType)); //L.elem為首元素的地址
if(!L.elem){ //如果存儲空間分配失敗，L.elem為NULL
printf("存儲空間分配失敗\n");
exit(OVERFLOW);
}
L.length = 0; //當前線性表為空表，即線性表長度為0
L.listsize = LIST_INIT_SIZE; //給線性表分配初始容量
printf("一個空的線性表已經構建成功\n"); //輸出空線性表構建成功的提示消息
return OK;
}
//對線性表進行賦值
Status ValueList_Sq(SqList &L){
int i,j;
printf("請輸入線性表元素的個數：");
scanf("%d",&i);
if(i > L.listsize) //如果當要輸入的元素個數大于內存大小時
{
while(1) //一直開辟新空間，直到開辟的空間大于需要的空間為止
{
if(i > L.listsize){
L.elem = (ElemType *)realloc(L.elem,LISTINCREMENT * sizeof(ElemType));
L.listsize += LISTINCREMENT;
/*realloc()函數：重新分配空間
參數：原空間基址，現需空間大小
返回：1.成功：新空間地址(本質上是一個數值)
2.失敗：Null
*/
}
else
break;
}
}
for(j = 0;j < i;j++){
printf("請輸入第%d個元素：",j + 1);
scanf("%d",&L.elem[j]);
}
L.length = i; //賦值完成后，修改并保存線性表的長度
printf("賦值成功\n");
return OK;
}
//對線性表進行銷毀
Status DistoryList_Sq(SqList &L){
if(!L.elem){
printf("您還未建立線性表，請先建立線性表\n");
return ERROR;
}
free(L.elem); //使用free函數，將之前動態分配的內存還給系統
L.elem = NULL; //重置elem的值為Null
L.length = 0; //將線性表的元素個數重置為0
L.listsize = 0; //將線性表的存儲容量重置為0
printf("線性表已經銷毀\n");
return OK;
}
//對線性表進行重置
Status ClearList_Sq(SqList &L){
if(L.elem){ //如果線性表存在
L.length = 0; //將線性表的元素個數重置為0
printf("線性表已重置\n");
return OK;
}
else
printf("線性表不存在，無法重置\n");
return OK;
}
//判斷線性表是否為空
Status ListEmpty_Sq(SqList L){
if(L.elem){ //判斷線性表是否為空的前提是線性表存在，當首元素地址即L.elem存在時說明線性表存在
if(L.length != 0){ //如果線性表中元素為0，即L.length的值為0時說明線性表是空表
printf("線性表不是空表\n");
return FALSE;
}
else
printf("線性表是空表\n");
return TRUE;
}
else
printf("線性表不存在，無法判斷\n");
return OK;
}
//獲取線性表的長度
Status ListLength_Sq(SqList L){
if(L.elem){ //判斷當前線性表存在
int K;
K = L.length; //將線性表的元素個數賦值給K
printf("線性表長度為%d\n",K);
return OK;
}
else
printf("線性表不存在，無法判斷\n");
return OK;
}
//獲取線性表某一位置對應的元素
Status GetElem_Sq(SqList L,int index){
int Num;
if(index <= 0 || index > L.length){ //如果要獲取元素的位置是否出界
printf("請輸入一個有效的數字\n");
return ERROR;
}
else
Num = L.elem[index - 1];
printf("第%d個位置的元素為：%d\n",index,Num);
return OK;
}
//在線性表某一位置插入元素
Status ListInsert_Sq(SqList &L,int i,ElemType e){
ElemType *newbase;
int *q,*p;
if(i < 1 || i > L.length+1) //判斷插入位置的index值是否合法
return ERROR;
if(L.length >= L.listsize){ //如果當前線性表存儲空間已滿，增加分配
newbase = (ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));
if(!newbase) { //如果存儲空間分配失敗，則執行異常退出
printf("存儲空間分配失敗\n");
exit(OVERFLOW);
}
L.elem = newbase; //新的存儲空間基址
L.listsize += LISTINCREMENT;
}
q = &(L.elem[i-1]); //L.elem[index-1]為數組中的最后一個元素，q為要插入的位置
for(p = &(L.elem[L.length - 1]);p >= q;--p)
*(p+1) = *p; //要插入位置以及之后的位置向后移
*q = e; //將e插入到想要插入的位置
++L.length; //插入新的元素之后表長加1
printf("元素插入成功\n");
return OK;
}
//打印線性表
Status PrintList_Sq(SqList L){
printf("當前線性表的元素為：");
for(int K = 0;K < L.length;K++) //遍歷當前線性表
printf(" %d",L.elem[K]);
printf("\n"); //換行
return OK;
}
//刪除線性表某一位置的元素
Status DeleteList_Sq(SqList &L,int i){
int *p,*q;
if(i < 1 || i > L.length){ //如果要刪除的位置不合法
printf("請輸入一個有效數字\n");
return ERROR;
}
p = &(L.elem[i - 1]); //p為被刪除元素的位置
q = L.elem + L.length - 1; //將表尾元素的位置賦值給q
for(++p;p <= q;p++)
*(p - 1) = *p; //被刪除的元素之后的元素全部左移
--L.length; //表長減1
printf("第%d個元素刪除成功\n",i);
return OK;
}
//求線性表某一元素的前驅
Status PriorElem_Sq(SqList L,int i){
int K;
if(L.elem){ //判斷線性表是否為空的前提是線性表存在，當首元素地址即L.elem存在時說明線性表存在
if(i <= 1 || i > L.length + 1) //判斷輸入的i值是否合法
printf("請輸入一個有效數字\n");
K = L.elem[i - 2]; //將第i個元素的前一個元素賦值給K
printf("第%d個位置的直接前驅為：%d\n",i,K);
}
else
printf("線性表不存在，無法判斷\n");
return OK;
}
//求線性表某一元素的后繼
Status NextElem_Sq(SqList L,int i){
int K;
if(L.elem){ //判斷線性表是否為空的前提是線性表存在，當首元素地址即L.elem存在時說明線性表存在
if(i <= 1 || i > L.length - 1) //判斷輸入的i值是否合法
printf("請輸入一個有效數字\n");
K = L.elem[i]; //將第i個元素的后一個元素賦值給K
printf("第%d個位置的直接后繼為：%d\n",i,K);
}
else
printf("線性表不存在，無法判斷\n");
return OK;
}
int main(){
SetConsoleTitle("Dream_飛翔");
SqList L;
int choose,index,e;
while(1){
printf("*****************************************\n");
printf("* *\n");
printf("* 線性表的順序表示和實現： *\n");
printf("* *\n");
printf("* 1. 構造一個空的線性表 *\n");
printf("* 2. 對線性表進行賦值 *\n");
printf("* 3. 對線性表進行銷毀 *\n");
printf("* 4. 對線性表進行重置 *\n");
printf("* 5. 判斷線性表是否為空 *\n");
printf("* 6. 獲取線性表的長度 *\n");
printf("* 7. 獲取線性表某一位置對應的元素 *\n");
printf("* 8. 在線性表某一位置插入元素 *\n");
printf("* 9. 刪除線性表某一位置的元素 *\n");
printf("* 10. 求線性表某一元素的前驅 *\n");
printf("* 11. 求線性表某一元素的后繼 *\n");
printf("* 12. 打印線性表 *\n");
printf("* 13. 退出 *\n");
printf("* *\n");
printf("*****************************************\n");
printf("請做出您的選擇：");
scanf("%d",&choose);
switch(choose){
case 1:InitList_Sq(L);break;
case 2:ValueList_Sq(L);break;
case 3:DistoryList_Sq(L);break;
case 4:ClearList_Sq(L);break;
case 5:ListEmpty_Sq(L);break;
case 6:ListLength_Sq(L);break;
case 7:{
printf("請輸入要獲取元素的位置：");
scanf("%d",&index);
GetElem_Sq(L,index);
}
break;
case 8:{
printf("請輸入要插入元素的位置：");
scanf("%d",&index);
printf("請輸入要插入的元素：");
scanf("%d",&e);
ListInsert_Sq(L,index,e);
}
break;
case 9:{
printf("請輸入要刪除元素的位置：");
scanf("%d",&index);
DeleteList_Sq(L,index);
}
break;
case 10:{
printf("請輸入想要查找哪一個元素的前驅：");
scanf("%d",&index);
PriorElem_Sq(L,index);
}
break;
case 11:{
printf("請輸入想要查找哪一個元素的后繼：");
scanf("%d",&index);
NextElem_Sq(L,index);
}
break;
case 12:PrintList_Sq(L);break;
case 13:exit(0);
}
}
return 0;
}以上就是關于“C語言線性順序表如何實現”這篇文章的內容，相信大家都有了一定的了解，希望小編分享的內容對大家有幫助，若想了解更多相關的知識內容，請關注億速云行業資訊頻道。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
