目錄
- 前言
- 1. 順序表概念及結構
- 2. 靜態順序表的實作
- 2.1 創建靜態順序表工程
- 2.2 定義結構體
- 2.3 初始化順序表
- 2.3.1 SeqList.h 宣告介面
- 2.3.2 SeqList.c 定義函式
- 2.4 順序表增加操作
- 2.4.1 SeqList.h 宣告介面
- 2.4.2 SeqList.c 定義函式
- 2.5 順序表的洗掉操作
- 2.5.1 SeqList.h 宣告介面
- 2.5.2 SeqList.c 定義函式
- 2.6 順序表查找操作
- 2.6.1 SeqList.h 宣告介面
- 2.6.2 SeqList.c 定義函式
- 2.7 順序表修改操作
- 2.7.1 SeqList.h 宣告介面
- 2.7.2 SeqList.c 定義函式
- 2. 8 完整代碼實作及運行測驗
- 2.8.1 SeqList.h
- 2.8.2 SeqList.c
- 2.8.3 test.c
- 2.8.4 運行測驗
- 3. 動態順序表的實作
- 3.1 創建動態順序表工程
- 3.2 定義結構體
- 3.3 初始化和釋放順序表
- 3.3.1 SeqList.h 宣告介面
- 3.3.2 SeqList.c 定義函式
- 3.3.3 加入斷言完善
- 3. 4 容量檢查操作
- 3.4.1 SeqList.h 宣告介面
- 3.4.2 SeqList.c 定義函式
- 3. 5 順序表增加操作
- 3.5.1 SeqList.h 宣告介面
- 3.5.2 SeqList.c 定義函式
- 3.6 順序表洗掉操作
- 3.6.1 SeqList.h 宣告介面
- 3.6.2 SeqList.c 定義函式
- 3.7 順序表查找查找
- 3.7.1 SeqList.h 宣告介面
- 3.7.2 SeqList.c 定義函式
- 3.8 順序表修改操作
- 3.8.1 SeqList.h 宣告介面
- 3.8.2 SeqList.c 定義函式
- 3.9 完整代碼展示及運行
- 3.9.1 SeqList.h
- 3.9.2 SeqList.c
- 3.9.3 test.c
- 3.9.4 運行測驗
- 后記
前言
寫了很久C++的博客,資料結構方面的除了之前的兩篇很久沒有更新了,最近打算重新撿起來資料結構方面的博客,之前的博客中已經有介紹過順序表和鏈表的文章,(資料結構——紅玫瑰與白玫瑰之爭)但是回頭再看時,感徑訓是有很多不足,于是決定重新寫一下,希望可以達到更完美的效果,當然,文章仍會有許多不足,也歡迎大家批評指正,
1. 順序表概念及結構
順序表是用一段物理地址連續的存盤單元依次存盤資料元素的線性結構,一般情況下采用陣列存盤,在陣列
上完成資料的增刪查改,
順序表一般可以分為:
- 靜態順序表:使用定長陣列存盤,
- 動態順序表:使用動態開辟的陣列存盤,
2. 靜態順序表的實作
2.1 創建靜態順序表工程
我們的工程采用多檔案方式,分別為SeqList.h,SeqList.c,和test.c,

2.2 定義結構體
#define N 100//宏定義
typedef int SLDataType;
typedef struct SeqList
{
SLDataType _a[N];//定長陣列
size_t _size;//有效資料個數
}SeqList;
在靜態順序表的結構體定義中,我們用define定義了N,然后定義了_a[N]作為定長陣列,而_size用來表示有效資料個數,我們用size_t,定義有效資料個數,size_t是定義無符號整形的,表示范圍很大,為了使代碼修改起來更加方便,我們采用typedef給int型別取別名為SLDataType,這樣當我們想把int型換成其他型別時,只需要修改一初就好啦,同樣地,我們將結構體起別名,為了在接下來的代碼中寫起來更方便,
2.3 初始化順序表
2.3.1 SeqList.h 宣告介面
//初始化
void SeqListInit(SeqList *seq);
2.3.2 SeqList.c 定義函式
//初始化
void SeqListInit(SeqList *seq)
{
seq->_size = 0;
}
2.4 順序表增加操作
2.4.1 SeqList.h 宣告介面
//尾插
void SeqListPushBack(SeqList *seq, SLDataType x);
//頭插
void SeqListPushFront(SeqList *seq, SLDataType x);
2.4.2 SeqList.c 定義函式
//頭插
void SeqListPushFront(SeqList *seq, SLDataType x)
{
if (seq->_size >= N)
{
return;
}
int end= seq->_size - 1;
while (end >= 0)
{
seq->_a[end + 1] = seq->_a[end];
end--;
}
seq->_a[0] = x;
seq->_size++;
}
//尾插
void SeqListPushBack(SeqList *seq, SLDataType x)
{
if (seq->_size >= N)
{
return;
}
seq->_a[seq->_size] = x;
seq->_size++;
}
注意,要驗證容量是不是已經滿了,
2.5 順序表的洗掉操作
2.5.1 SeqList.h 宣告介面
//頭刪
void SeqListPopFront(SeqList *seq);
//尾刪
void SeqListPopBack(SeqList *seq);
2.5.2 SeqList.c 定義函式
//頭刪
void SeqListPopFront(SeqList *seq)
{
if (seq->_size == 0)
{
return;
}
for (int i = 1; i < seq->_size; i++)
{
seq->_a[i - 1] = seq->_a[i];
}
seq->_size--;
}
//尾刪
void SeqListPopBack(SeqList *seq)
{
if (seq->_size == 0)
{
return;
}
seq->_size--;
}
注意要檢查此時順序表是否為空,
2.6 順序表查找操作
2.6.1 SeqList.h 宣告介面
//查找
int SeqListSearch(SeqList *seq, SLDataType x);
2.6.2 SeqList.c 定義函式
//查找
int SeqListSearch(SeqList *seq, SLDataType x)
{
for (int i = 0; i < seq->_size; i++)
{
if (seq->_a[i] == x)
{
return i;
}
}
return -1;
}
在這里,我們令找到之后回傳的是下標,
2.7 順序表修改操作
2.7.1 SeqList.h 宣告介面
//修改
void SeqListModify(SeqList *seq, int pos,SLDataType x);
這里的三個引數分別為順序表結構體、要修改的位置和修改后的值,
2.7.2 SeqList.c 定義函式
//修改
void SeqListModify(SeqList *seq, int pos,SLDataType x)
{
if (pos >= 0 && pos < seq->_size)
{
seq->_a[pos] = x;
}
else
{
printf("該位置不存在\n");
}
}
注意要檢查這個位置是不是合法的,
2. 8 完整代碼實作及運行測驗
2.8.1 SeqList.h
#include<stdio.h>
#define N 100
typedef int SLDataType;
typedef struct SeqList
{
SLDataType _a[N];
size_t _size;
}SeqList;
//初始化
void SeqListInit(SeqList *seq);
//列印
void SeqListShow(SeqList *seq);
//頭插
void SeqListPushFront(SeqList *seq,SLDataType x);
//尾插
void SeqListPushBack(SeqList *seq, SLDataType x);
//頭刪
void SeqListPopFront(SeqList *seq);
//尾刪
void SeqListPopBack(SeqList *seq);
//查找
int SeqListSearch(SeqList *seq, SLDataType x);
//修改
void SeqListModify(SeqList *seq, int pos,SLDataType x);
2.8.2 SeqList.c
#include"SeqList.h"
//初始化
void SeqListInit(SeqList *seq)
{
seq->_size = 0;
}
//列印
void SeqListShow(SeqList *seq)
{
for (int i = 0; i < seq->_size; i++)
{
printf("%d ", seq->_a[i]);
}
printf("\n");
}
//頭插
void SeqListPushFront(SeqList *seq, SLDataType x)
{
if (seq->_size >= N)
{
return;
}
int end= seq->_size - 1;
while (end >= 0)
{
seq->_a[end + 1] = seq->_a[end];
end--;
}
seq->_a[0] = x;
seq->_size++;
}
//尾插
void SeqListPushBack(SeqList *seq, SLDataType x)
{
if (seq->_size >= N)
{
return;
}
seq->_a[seq->_size] = x;
seq->_size++;
}
//頭刪
void SeqListPopFront(SeqList *seq)
{
if (seq->_size == 0)
{
return;
}
for (int i = 1; i < seq->_size; i++)
{
seq->_a[i - 1] = seq->_a[i];
}
seq->_size--;
}
//尾刪
void SeqListPopBack(SeqList *seq)
{
if (seq->_size == 0)
{
return;
}
seq->_size--;
}
//查找
int SeqListSearch(SeqList *seq, SLDataType x)
{
for (int i = 0; i < seq->_size; i++)
{
if (seq->_a[i] == x)
{
return i;
}
}
return -1;
}
//修改
void SeqListModify(SeqList *seq, int pos,SLDataType x)
{
if (pos >= 0 && pos < seq->_size)
{
seq->_a[pos] = x;
}
else
{
printf("該位置不存在\n");
}
}
2.8.3 test.c
#include"SeqList.h"
void TestOne()
{
SeqList s;
SeqListInit(&s);
SeqListPushBack(&s, 2);
SeqListPushFront(&s, 1);
SeqListPushBack(&s, 2);
SeqListPushFront(&s, 1);
SeqListShow(&s);
SeqListPopBack(&s);
SeqListPopFront(&s);
SeqListShow(&s);
int pos=SeqListSearch(&s, 1);
if (pos == -1)
{
printf("您查找的數字不存在\n");
}
else
{
printf("您要查找的數字的下標為%d \n", pos);
}
SeqListModify(&s, 1, 9);
SeqListShow(&s);
SeqListDestory(&s);
}
int main()
{
TestOne();
return 0;
}
2.8.4 運行測驗

3. 動態順序表的實作
3.1 創建動態順序表工程
參考2.1動態順序表工程的創建
3.2 定義結構體
typedef int SLDataType;
typedef struct SeqList
{
SLDataType *_a;//動態開辟的動態陣列
size_t _size;//有效資料個數
size_t _capacity;//容量空間的大小
}SeqList;
和靜態順序表相比,這里陣列我們換成了指標,用來指向開辟的動態陣列,又定義了_capacity也就是容量空間的大小,這樣當我們發現容量不夠時,便可以動態增容,
3.3 初始化和釋放順序表
3.3.1 SeqList.h 宣告介面
//初始化
void SeqListInit(SeqList *seq);
//釋放
void SeqListDestory(SeqList *seq);
一定要有記憶體釋放函式,否則可能會造成記憶體泄露,
3.3.2 SeqList.c 定義函式
//初始化
void SeqListInit(SeqList *seq)
{
seq->_a = NULL;
seq->_size = seq->_capacity=0;
}
//釋放
void SeqListDestory(SeqList *seq)
{
free(seq->_a);
seq->_a = NULL;
seq->_size = seq->_capacity = 0;
}
3.3.3 加入斷言完善
//初始化
void SeqListInit(SeqList *seq)
{
assert(seq);
seq->_a = NULL;
seq->_size = seq->_capacity=0;
}
//釋放
void SeqListDestory(SeqList *seq)
{
assert(seq);
free(seq->_a);
seq->_a = NULL;
seq->_size = seq->_capacity = 0;
}
在我們引入斷言的時候,頭檔案要引入assert.h,可以通過斷言來檢查空指標,提高程式的安全性,
3. 4 容量檢查操作
這個操作用來檢查容量是否已滿,當容量滿時進行擴容,
3.4.1 SeqList.h 宣告介面
//檢查容量
void SeqListCherk(SeqList *seq);
3.4.2 SeqList.c 定義函式
//檢查容量
void SeqListCherk(SeqList *seq)
{
assert(seq);
if (seq->_capacity == seq->_size)
{
//_capacity剛開始有可能是0,如果是0,開辟容量為4,如果不是0,擴容為2倍
int newcapacity = seq->_capacity == 0 ? 4 : seq->_capacity * 2;
SLDataType *newA = realloc(seq->_a, sizeof(SLDataType)*newcapacity);
//檢查擴容是否失敗
if (newA == NULL)
{
printf("realloc fail\n");
exit(-1);
}
seq->_a = newA;
seq->_capacity = newcapacity;
}
}
注意擴容有可能失敗,要進行檢驗是否擴容成功,
3. 5 順序表增加操作
3.5.1 SeqList.h 宣告介面
//頭插
void SeqListPushFront(SeqList *seq, SLDataType x);
//尾插
void SeqListPushBack(SeqList *seq, SLDataType x);
3.5.2 SeqList.c 定義函式
//頭插
void SeqListPushFront(SeqList *seq, SLDataType x)
{
assert(seq);
SeqListCherk(seq);
int end = seq->_size - 1;
while (end >= 0)
{
seq->_a[end + 1] = seq->_a[end];
end--;
}
seq->_a[0] = x;
seq->_size++;
}
//尾插
void SeqListPushBack(SeqList *seq, SLDataType x)
{
assert(seq);
SeqListCherk(seq);
seq->_a[seq->_size] = x;
seq->_size++;
}
3.6 順序表洗掉操作
3.6.1 SeqList.h 宣告介面
//頭刪
void SeqListPopFront(SeqList *seq);
//尾刪
void SeqListPopBack(SeqList *seq);
3.6.2 SeqList.c 定義函式
//頭刪
void SeqListPopFront(SeqList *seq)
{
assert(seq);
for (int first = 0; first < seq->_size-1; first++)
{
seq->_a[first] = seq->_a[first + 1];
}
seq->_size--;
}
//尾刪
void SeqListPopBack(SeqList *seq)
{
assert(seq);
seq->_size--;
}
3.7 順序表查找查找
3.7.1 SeqList.h 宣告介面
//查找
int SeqListSearch(SeqList *seq, SLDataType x);
3.7.2 SeqList.c 定義函式
//查找
int SeqListSearch(SeqList *seq, SLDataType x)
{
for (int i = 0; i < seq->_size; i++)
{
if (seq->_a[i] == x)
return i;
}
return -1;
}
3.8 順序表修改操作
3.8.1 SeqList.h 宣告介面
//修改
void SeqListModify(SeqList *seq, int pos, SLDataType x);
3.8.2 SeqList.c 定義函式
//修改
void SeqListModify(SeqList *seq, int pos, SLDataType x)
{
if (pos < seq->_size&&pos >= 0)
{
seq->_a[pos] = x;
}
else
{
printf("位置非法\n");
}
}
3.9 完整代碼展示及運行
3.9.1 SeqList.h
#include<stdio.h>
#include<malloc.h>
#include<assert.h>
typedef int SLDataType;
typedef struct SeqList
{
SLDataType *_a;//動態開辟的動態陣列
size_t _size;//有效資料個數
size_t _capacity;//容量空間的大小
}SeqList;
//初始化
void SeqListInit(SeqList *seq);
//釋放
void SeqListDestory(SeqList *seq);
//列印
void SeqListShow(SeqList *seq);
//檢查容量
void SeqListCherk(SeqList *seq);
//頭插
void SeqListPushFront(SeqList *seq, SLDataType x);
//尾插
void SeqListPushBack(SeqList *seq, SLDataType x);
//頭刪
void SeqListPopFront(SeqList *seq);
//尾刪
void SeqListPopBack(SeqList *seq);
//查找
int SeqListSearch(SeqList *seq, SLDataType x);
//修改
void SeqListModify(SeqList *seq, int pos, SLDataType x);
3.9.2 SeqList.c
#include"SeqList.h"
//初始化
void SeqListInit(SeqList *seq)
{
assert(seq);
seq->_a = NULL;
seq->_size = seq->_capacity = 0;
}
//釋放
void SeqListDestory(SeqList *seq)
{
assert(seq);
free(seq->_a);
seq->_a = NULL;
seq->_size = seq->_capacity = 0;
}
//列印
void SeqListShow(SeqList *seq)
{
assert(seq);
for (int i = 0; i < seq->_size; i++)
{
printf("%d ", seq->_a[i]);
}
printf("\n");
}
//檢查容量
void SeqListCherk(SeqList *seq)
{
assert(seq);
if (seq->_capacity == seq->_size)
{
//_capacity剛開始有可能是0,如果是0,開辟容量為4,如果不是0,擴容為2倍
int newcapacity = seq->_capacity == 0 ? 4 : seq->_capacity * 2;
SLDataType *newA = realloc(seq->_a, sizeof(SLDataType)*newcapacity);
//檢查擴容是否失敗
if (newA == NULL)
{
printf("realloc fail\n");
exit(-1);
}
seq->_a = newA;
seq->_capacity = newcapacity;
}
}
//頭插
void SeqListPushFront(SeqList *seq, SLDataType x)
{
assert(seq);
SeqListCherk(seq);
int end = seq->_size - 1;
while (end >= 0)
{
seq->_a[end + 1] = seq->_a[end];
end--;
}
seq->_a[0] = x;
seq->_size++;
}
//尾插
void SeqListPushBack(SeqList *seq, SLDataType x)
{
assert(seq);
SeqListCherk(seq);
seq->_a[seq->_size] = x;
seq->_size++;
}
//頭刪
void SeqListPopFront(SeqList *seq)
{
assert(seq);
for (int first = 0; first < seq->_size-1; first++)
{
seq->_a[first] = seq->_a[first + 1];
}
seq->_size--;
}
//尾刪
void SeqListPopBack(SeqList *seq)
{
assert(seq);
seq->_size--;
}
//查找
int SeqListSearch(SeqList *seq, SLDataType x)
{
for (int i = 0; i < seq->_size; i++)
{
if (seq->_a[i] == x)
return i;
}
return -1;
}
//修改
void SeqListModify(SeqList *seq, int pos, SLDataType x)
{
if (pos < seq->_size&&pos >= 0)
{
seq->_a[pos] = x;
}
else
{
printf("位置非法\n");
}
}
3.9.3 test.c
#include"SeqList.h"
void TestOne()
{
SeqList s;
SeqListInit(&s);
SeqListPushFront(&s, 1);
SeqListPushFront(&s, 2);
SeqListShow(&s);
SeqListPushBack(&s, 3);
SeqListPushBack(&s, 4);
SeqListShow(&s);
SeqListPopBack(&s);
SeqListPopFront(&s);
SeqListShow(&s);
int pos = SeqListSearch(&s,1);
if (pos == -1)
{
printf("find fail\n");
}
else
{
printf("該元素的位置為%d\n", pos);
}
SeqListShow(&s);
SeqListModify(&s, 0, 0);
SeqListShow(&s);
}
int main()
{
TestOne();
return 0;
}
3.9.4 運行測驗

后記
好的,這期誠意滿滿的博文就先分享到這里,希望對大家有所幫助,感謝大家支持,也歡迎大家批評指正,
轉載請註明出處,本文鏈接:https://www.uj5u.com/qita/299673.html
標籤:其他
上一篇:劍指offer系列——劍指 Offer 22. 鏈表中倒數第k個節點(C語言)
下一篇:LeetCode重建二叉樹詳解
