首頁 > 軟體

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

2022-07-03 14:00:21

線性表是最常用且最簡單的一種資料結構。簡而言之,一個線性表是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("線性表長度為%dn",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個位置的元素為:%dn",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個位置的直接前驅為:%dn",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個位置的直接後繼為:%dn",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("線性表長度為%dn",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個位置的元素為:%dn",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個位置的直接前驅為:%dn",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個位置的直接後繼為:%dn",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語言線性表內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com!


IT145.com E-mail:sddin#qq.com