快捷導(dǎo)航

c語言數(shù)據(jù)結(jié)構(gòu)與算法之順序表的定義實現(xiàn)詳解

更新時間：2023年08月08日 09:15:38 作者：程序喵正在路上

這篇文章主要介紹了c語言數(shù)據(jù)結(jié)構(gòu)與算法之順序表的定義實現(xiàn)詳解,用順序存儲的方式實現(xiàn)線性表順序存儲,把邏輯上相鄰的元素存儲在物理位置上也相鄰的存儲單元中，元素之間的關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn),需要的朋友可以參考下

順序表的定義

順序表 —— 用順序存儲的方式實現(xiàn)線性表順序存儲。

把邏輯上相鄰的元素存儲在物理位置上也相鄰的存儲單元中，元素之間的關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)

線性表是具有相同數(shù)據(jù)類型的 n (n≥0) 個數(shù)據(jù)元素的有限序列，數(shù)據(jù)類型相同說明每個數(shù)據(jù)元素所占的空間是一樣大的

我們假設(shè)線性表第一個元素的存放位置（即首地址）是 LOC(L) ，LOC 是 location 的縮寫

那么第二個元素的存放位置就是 LOC(L)+數(shù)據(jù)元素的大小

第三個元素的存放位置就是 LOC(L)+2*數(shù)據(jù)元素的大小，依此類推…

那么，我們又怎么知道所存放的數(shù)據(jù)元素的大小呢？

學(xué)過 C語言 的小伙伴肯定知道，C語言 中有一個函數(shù) sizeof() 可以幫上我們的忙，我們用 sizeof(ElemType) 這樣調(diào)用的方式就能得到對應(yīng)數(shù)據(jù)元素的大小，其中的 ElemType 就是你的順序表中存放的數(shù)據(jù)元素類型，比如 sizeof(int) = 4B ，一個整型一般是 4 個字節(jié)；此外，我們還可以傳自己定義的類型進去，比如，我們定義一個 Customer 類型

typedef struct {
	int num;	//號數(shù)
	int people; //人數(shù)
} Customer;

相應(yīng)地，我們使用 sizeof(Customer) 就可以得到這個數(shù)據(jù)類型的大小為 8B

順序表的實現(xiàn) —— 靜態(tài)分配

#define MaxSize 10				//定義最大長度
typedef struct {
	ElemType data[MaxSize];		//用靜態(tài)的 “數(shù)組” 存放數(shù)據(jù)元素
	int length;					//順序表的當(dāng)前長度
} SqList;						//順序表的類型定義（靜態(tài)分配方式）

ElemType data[MaxSize]; 會給各個數(shù)據(jù)元素分配連續(xù)的存儲空間，大小為 MaxSize*sizeof(ElemType)

Sq：sequence —— 順序，序列

#include <stdio.h>
#define MaxSize 10				//定義最大長度
typedef int ElemType;
typedef struct {
	ElemType data[MaxSize];		//用靜態(tài)的 “數(shù)組” 存放數(shù)據(jù)元素
	int length;					//順序表的當(dāng)前長度
} SqList;						//順序表的類型定義
//基礎(chǔ)操作 —— 初始化一個順序表
void InitList(SqList &L) {
	for(int i = 0; i < MaxSize; i++) {
		L.data[i] = 0;		//將所有數(shù)據(jù)元素設(shè)置為默認(rèn)初始值
	}
	L.length = 0;
}
//主函數(shù)
int main() {
	SqList L;		//聲明一個順序表
	InitList(L);	//初始化順序表
	//其他操作
	return 0;
}

如果在初始化順序表中不給 data 數(shù)組賦值為 0，會怎么樣呢？

#include <stdio.h>
#define MaxSize 10				//定義最大長度
typedef int ElemType;
typedef struct {
	ElemType data[MaxSize];		//用靜態(tài)的 “數(shù)組” 存放數(shù)據(jù)元素
	int length;					//順序表的當(dāng)前長度
} SqList;						//順序表的類型定義
//基礎(chǔ)操作 —— 初始化一個順序表
void InitList(SqList &L) {
	L.length = 0;
}
//主函數(shù)
int main() {
	SqList L;		//聲明一個順序表
	InitList(L);	//初始化順序表
	//嘗試“違規(guī)”打印整個數(shù)組
	for(int i = 0; i < MaxSize; i++) {
		printf("data[%d]=%d\n", i, L.data[i]);
	}
	return 0;
}

運行這段代碼，你會看到很奇怪的數(shù)據(jù)，或許和我的運行結(jié)果不太一樣，這是正常的

在這里插入圖片描述

為什么會顯示這些奇怪的數(shù)據(jù)呢？

其實啊，程序在給我們這個數(shù)組分配內(nèi)存的時候，我們并不知道這塊內(nèi)存里面之前存儲過什么，如果我們不設(shè)置數(shù)據(jù)元素的默認(rèn)值，就會出現(xiàn)這樣的結(jié)果

其實，我們這樣訪問也是違規(guī)的，因為初始化順序表的時候 length 是為 0 的，我們要遍歷的條件應(yīng)該是 i < L.length; 才對，所以數(shù)據(jù)元素的初始化是可以省略的，不過 length 的初始化這一步驟就不能省略了

如果我們定義的 “數(shù)組” 存滿了，怎么辦呢？

建議直接放棄治療，順序表的表長剛開始確定后就無法更改了，因為我們是靜態(tài)分配空間

有小伙伴就說，那我一開始就聲明一個很長的順序表不就行了，但這樣的后果是會浪費我們的內(nèi)存空間，從這里我們就可以看出來靜態(tài)分配的局限性了

順序表的實現(xiàn) —— 動態(tài)分配

#define InitSize 10			//順序表的初始長度
typedef struct {
	ElemType *data;			//指示動態(tài)分配數(shù)組的指針
	int MaxSize;			//順序表的最大容量
	int length;				//順序表的當(dāng)前長度
} SqList;					//順序表的類型定義

C語言 中提供了 malloc 和 free 這兩個函數(shù)來讓我們動態(tài)申請和釋放內(nèi)存空間

malloc 會申請一整片連續(xù)的存儲空間，然后返回一個指向這一片存儲空間開始地址的指針，同時需要我們強制轉(zhuǎn)型為定義的數(shù)據(jù)元素類型指針

malloc 函數(shù)的參數(shù)，指明了要分配多大的連續(xù)內(nèi)存空間

L.data = (ElemType *) malloc(sizeof(ElemType) * InitSize);

如果你學(xué)習(xí)過 C++，那你也可以使用 new 和 delete 這兩個函數(shù)來實現(xiàn)同樣的功能

#include <stdio.h>
#include <stdlib.h>				//使用 malloc 和 free 函數(shù)所需的頭文件
#define InitSize 10				//默認(rèn)最大長度
typedef int ElemType;			//方便我們改變類型
typedef struct {
	ElemType *data;				//指示動態(tài)分配數(shù)組的指針
	int MaxSize;				//順序表的最大容量
	int length;					//順序表的當(dāng)前長度
} SqList;						//順序表的類型定義
//初始化順序表
void InitList(SqList &L);
//增加動態(tài)數(shù)組的長度
void IncreaseSize(SqList &L, int len);
//主函數(shù)
int main() {
	SqList L;			//聲明一個順序表
	InitList(L);		//初始化順序表
	IncreaseSize(L, 5);
	return 0;
}
//初始化順序表
void InitList(SqList &L) {
	//用 malloc 函數(shù)申請一片連續(xù)的存儲空間
	L.data = (ElemType *)malloc(sizeof(ElemType)* InitSize);
	L.length = 0;
	L.MaxSize = InitSize;
}
//增加動態(tài)數(shù)組的長度
void IncreaseSize(SqList &L, int len) {
	ElemType *p = L.data;				//將L數(shù)據(jù)存儲起來
	L.data = (ElemType *)malloc(sizeof(ElemType)* (L.MaxSize + len));
	for (int i = 0; i < L.length; i++) {
		L.data[i] = p[i];				//將數(shù)據(jù)復(fù)制到新區(qū)域
	}
	L.MaxSize = L.MaxSize + len;		//順序表最大長度增加 len
	free(p);							//釋放臨時的內(nèi)存空間
}

注意：realloc 函數(shù)也可以實現(xiàn)，但建議初學(xué)者使用 malloc 和 free 更能理解背后的過程

順序表的特點：