C語言線性表順序表示及實現

Posted on by

線性表是最常用且最簡單的一種數據結構。簡而言之，一個線性表是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語言線性表順序表示及實現的文章就介紹到這瞭,更多相關C語言線性表內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：