從本篇開始,我們進入資料結構的真正重點內容,話不多說,我們開始吧!

文章目錄
- 一、線性表
- 二、順序表
- 1、概念及結構
- 2、順序表介面的實作
- 2.1 順序表的創建
- 2.2 順序表的初始化SeqListInit
- 2.3 順序表的尾插SeqListPushBack
- 2.4 順序表的尾刪SeqListPopBack
- 2.5 順序表的列印SeqListPrint
- 2.6 順序表的銷毀SeqListDestory
- 2.7 順序表的頭插SeqListPushFront
- 2.8 順序表的增容SeqListCheckCapacity
- 2.9 順序表的頭刪SeqListPopFront
- 2.10 順序表之查找元素SeqListFind
- 2.11 順序表之在指定位置插入元素SeqListInsert
- 2.12 順序表之洗掉指定位置的資料SeqListErase
- 三、綜合
- SeqList.h
- SeqList.c
一、線性表
線性表(linear list)是n個具有相同特性的資料元素的有限序列, 線性表是一種在實際中廣泛使用的資料結構,常見的線性表:順序表、鏈表、堆疊、佇列、字串…
線性表在邏輯上是線性結構,也就說是連續的一條直線,但是在物理結構上并不一定是連續的,線性表在物理上存盤時,通常以陣列和鏈式結構的形式存盤,
接下來,我們進入今天的主講內容:順序表
二、順序表
1、概念及結構
何為順序表?
順序表是用一段物理地址連續的存盤單元依次存盤資料元素的線性結構,一般情況下采用陣列存盤,在陣列上完成資料的增刪查改,
簡單理解:順序表就是陣列,但是在陣列的基礎上,還要求資料是從頭開始存并且連續存盤的,不能有跳躍間隔
順序表一般可以分為:
1.靜態順序表:使用定長陣列存盤元素
順序表的靜態存盤
#define N 100
typedef int SLDataType;
typedef struct SeqList
{
SLDataType array[N]; // 定長陣列
size_t size; // 有效資料的個數
}SeqList;
圖示:

2.動態順序表:使用動態開辟的陣列存盤
順序表的動態存盤
typedef struct SeqList
{
SLDataType* array; // 指向動態開辟的陣列
size_t size ; // 有效資料個數
size_t capicity ; // 容量空間的大小
}SeqList;
圖示:

這兩種哪個更好一點呢?
- 靜態順序表
只適用于確定知道需要存多少資料的場景
局限:靜態順序表的定長陣列,若N定大了,空間開多了浪費,若N定小了不夠用,
- 動態順序表
現實使用時多采用動態順序表
優勢:需要多少用多少
2、順序表介面的實作
我們以vs2019為環境搭建順序表工程
- 創建一個SeqList.h順序表頭檔案
- 創建一個SeqList.c順序表實作檔案
- 創建一個test.c測驗檔案

說明: - SeqList.h頭檔案用來創建順序表,和一些函式方法的宣告
- SeqList.c檔案用來實作順序表函式的定義
- test.c檔案用來測驗每次實作一個函式后是否成功
2.1 順序表的創建
我們以整型順序表為例:
//靜態版本的順序表
#define N 1000 //方便以后修改大小
struct SeqList
{
int a[N];
int size;//表示陣列中存盤了多少個有效資料
};
//動態版本的順序表
struct SeqList
{
int* a; //動態開辟陣列.
int size; //表示陣列中已存盤了多少個資料
int capacity; //陣列實際能存資料的空間容量是多大
};
上面就是我們創建的兩種形式的順序表,我們會以實作動態順序表為例(靜態順序表可以依法炮制~),
看到上面定義的順序表,其實還有一個小小的問題,就是當我們不再需要整型,而是要換成其他型別,那就需要去改int,要知道一個專案里,當用到結構體次數過多時,我們則需要一個個的去修改,這樣太麻煩,
那有沒有很好的辦法解決呢? 有,那就是typedef.
修改如下:
typedef int SLDataType
//動態順序表
typedef struct SeqList
{
SLDataType* a; //動態開辟陣列.
int size; //表示陣列中已存盤了多少個資料
int capacity; //陣列實際能存資料的空間容量是多大
}SL;//將結構體也重命名,后面定義結構體變數也方便,
這樣的話,以后如果不需要int型,我們就可以直接修改typedef定義的int,非常便捷
定義好后,我們該將這段程式放在哪里呢?
上面已經講解了:SeqList.h頭檔案用來創建順序表,和一些函式方法的宣告
所以我們將它放在SeqList.h頭檔案中.
2.2 順序表的初始化SeqListInit
//順序表的初始化
void SeqListInit(SL* ps)
{
ps->a = NULL;
ps->size = ps->capacity = 0;
}
我們將其定義好后,怎么放呢?
SeqList.h中放程式初始化宣告: void SeqListInit(SL* ps);
SeqList.c中放上面的函式定義.
2.3 順序表的尾插SeqListPushBack
什么叫做尾插呢?請看下面一副動圖:

顧名思義,尾插,即在最后面插入.接下來我們看看是如何實作的,
在SeqList.h檔案中宣告
//順序表的尾插
void SeqListPushBack(SL* ps, SLDataType x);
在SeqList.c檔案中定義
//順序表的尾插
void SeqListPushBack(SL* ps, SLDataType x)
{
//如果沒有空間或者空間不足,我們就擴容
if (ps->size == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);//結束程式--例外退出
}
ps->a = tmp;
ps->capacity = newcapacity;
}
ps->a[ps->size] = x;
ps->size++;
}
2.4 順序表的尾刪SeqListPopBack
我們了解尾插是如何進行的之后,就可以了解尾刪了,顧名思義,尾刪,即從最后面開始洗掉資料.如圖:

接下來我們看看是如何實作的,
在SeqList.h檔案中宣告
//順序表的尾刪
void SeqListPopBack(SL* ps, SLDataType x);
在SeqList.c檔案中定義
//順序表的尾刪
void SeqListPopBack(SL* ps, SLDataType x)
{
//溫柔的方式
//if (ps->size > 0)//防止越界,當陣列中的資料全部洗掉之后,不可在刪
//{
// //ps->a[ps->size - 1] = 0;//這一句可以不要
// ps->size--;
//}
//暴力的方式
assert(ps->size > 0);//斷言
ps->size--;
}
2.5 順序表的列印SeqListPrint
列印就非常簡單了,如下:
在SeqList.h檔案中宣告
//順序表的列印
void SeqListPrint(SL* ps);
在SeqList.c檔案中定義
//順序表的列印
void SeqListPrint(SL* ps)
{
for (int i = 0; i < ps->size; i++)
{
printf("%d ", ps->a[i]);
}
printf("\n");
}
2.6 順序表的銷毀SeqListDestory
我們都知道,當我們向記憶體申請了一塊記憶體空間后,若我們不再使用,則需要歸還系統,不然會造成記憶體泄漏等問題,
在SeqList.h中宣告
//順序表的銷毀
void SeqListDestory(SL* ps);
在SeqList.c中定義
//順序表的銷毀
void SeqListDestory(SL* ps)
{
free(ps->a);
ps->a = NULL;
ps->capacity = ps->size = 0;
}
我們完成上面這些介面之后,就可以進行一下測驗了,如下:

2.7 順序表的頭插SeqListPushFront
頭插演示:

在SeqList.h中宣告
//順序表的頭插
void SeqListPushFront(SL* ps, SLDataType x);
在SeqList.c中定義
//順序表的頭插
void SeqListPushFront(SL* ps, SLDataType x)
{
//如果沒有空間或者空間不足,我們就擴容
if (ps->size == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);//結束程式--例外退出
}
ps->a = tmp;
ps->capacity = newcapacity;
}
//挪動資料
int end = ps->size - 1;
while (end >= 0)
{
ps->a[end + 1] = ps->a[end];
end--;
}
ps->a[0] = x;
ps->size++;
}
2.8 順序表的增容SeqListCheckCapacity
由于我們無論是在進行尾插還是頭插,都必須檢查順序表的容量是否足夠,若不夠,則需要進行增容,所以我們將順序表的檢查增容單獨寫成一個函式,我們只需在尾插和頭插時呼叫它即可,如下:
在SeqList.h中宣告
//順序表檢查增容
void SeqListCheckCapacity(SL* ps);
在SeqList.c中定義
//順序表檢查增容
void SeqListCheckCapacity(SL* ps)
{
//如果沒有空間或者空間不足,我們就擴容
if (ps->size == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);//結束程式--例外退出
}
ps->a = tmp;
ps->capacity = newcapacity;
}
}
2.9 順序表的頭刪SeqListPopFront
頭刪演示:

在SeqList.h中宣告
//順序表的頭刪
void SeqListPopFront(SL* ps, SLDataType x);
在SeqList.c中定義
//順序表的頭刪
void SeqListPopFront(SL* ps, SLDataType x)
{
assert(ps->size > 0);
int begin = 1;//把第二個元素的下標賦給begin,這樣到了size的位置的時候就可停止
while (begin < ps->size)
{
ps->a[begin - 1] = ps->a[begin];
begin++;
}
ps->size--;
}
這里我們來測驗一下頭插與頭刪是否成功:

2.10 順序表之查找元素SeqListFind
在SeqList.h中宣告
// 順序表查找
int SeqListFind(SL* ps, SLDataType x);
在SeqList.c中定義
//順序表之查找元素,找到回傳下標,沒找到回傳-1
int SeqListFind(SL* ps, SLDataType x)
{
for (int i = 0; i < ps->size; i++)
{
if (ps->a[i] == x)
{
return i;
}
}
return -1;
}
2.11 順序表之在指定位置插入元素SeqListInsert
思路:
- 輸入指定下標, 想要插入的元素,就在此下標位置插入
- 實作方法: 輸入的下標位置及其后,所有資料都往后面挪
- 然后插入資料,size加1
在SeqList.h中宣告
//在指定下標位置插入
void SeqListInsert(SL* ps, int pos, SLDataType x);
在SeqList.c中定義
//在指定下標位置插入
void SeqListInsert(SL* ps, int pos, SLDataType x)
{
//在插入之前需判斷pos的位置是否符合順序表的特征(必須保持連續)
//溫柔處理方式
//if (pos > ps->size || pos < 0)
//{
// printf("pos invalid\n");
// return;
//}
//暴力處理方式
assert(pos <= ps->size && pos >= 0);
SeqListCheckCapacity(ps);
int end = ps->size - 1;
while (end >= pos)
{
ps->a[end + 1] = ps->a[end];
end--;
}
ps->a[pos] = x;
ps->size++;
}
2.12 順序表之洗掉指定位置的資料SeqListErase
在SeqList.h中宣告
//洗掉指定位置的資料
void SeqListErase(SL* ps, int pos);
在SeqList.c中定義
//洗掉指定位置的資料
void SeqListErase(SL* ps, int pos)
{
assert(pos < ps->size && pos >= 0);
int begin = pos + 1;
while (begin < ps->size)
{
ps->a[begin - 1] = ps->a[begin];
begin++;
}
ps->size--;
}
三、綜合
SeqList.h
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
//#define N 1000 //方便以后修改大小
//靜態順序表
//struct SeqList
//{
// int a[N];
// int size;//表示陣列中存盤了多少個有效資料
//};
//動態順序表
typedef int SLDataType;//方便后期修改資料型別
typedef struct SeqList
{
SLDataType* a; //動態開辟陣列.
int size; //表示陣列中已存盤了多少個資料
int capacity; //陣列實際能存資料的空間容量是多大
}SL;//將結構體也重命名,后面定義結構體變數也方便,
//順序表的列印
void SeqListPrint(SL* ps);
//順序表的初始化
void SeqListInit(SL* ps);
//順序表的銷毀
void SeqListDestory(SL* ps);
//順序表檢查增容
void SeqListCheckCapacity(SL* ps);
//順序表的尾插
void SeqListPushBack(SL* ps, SLDataType x);
//順序表的尾刪
void SeqListPopBack(SL* ps, SLDataType x);
//順序表的頭插
void SeqListPushFront(SL* ps, SLDataType x);
//順序表的頭刪
void SeqListPopFront(SL* ps, SLDataType x);
// 順序表查找
int SeqListFind(SL* ps, SLDataType x);
//在指定下標位置插入
void SeqListInsert(SL* ps, int pos, SLDataType x);
//洗掉指定位置的資料
void SeqListErase(SL* ps, int pos);
SeqList.c
#include "SeqList.h"
//順序表的列印
void SeqListPrint(SL* ps)
{
for (int i = 0; i < ps->size; i++)
{
printf("%d ", ps->a[i]);
}
printf("\n");
}
//順序表的初始化
void SeqListInit(SL* ps)
{
ps->a = NULL;
ps->size = ps->capacity = 0;
}
//順序表檢查增容
void SeqListCheckCapacity(SL* ps)
{
//如果沒有空間或者空間不足,我們就擴容
if (ps->size == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);//結束程式--例外退出
}
ps->a = tmp;
ps->capacity = newcapacity;
}
}
//順序表的銷毀
void SeqListDestory(SL* ps)
{
free(ps->a);
ps->a = NULL;
ps->capacity = ps->size = 0;
}
//順序表的尾插
void SeqListPushBack(SL* ps, SLDataType x)
{
SeqListCheckCapacity(ps);
ps->a[ps->size] = x;
ps->size++;
}
//順序表的尾刪
void SeqListPopBack(SL* ps, SLDataType x)
{
//溫柔的方式
//if (ps->size > 0)//防止越界,當陣列中的資料全部洗掉之后,不可在刪
//{
// //ps->a[ps->size - 1] = 0;//這一句可以不要
// ps->size--;
//}
//暴力的方式
assert(ps->size > 0);
ps->size--;
}
//順序表的頭插
void SeqListPushFront(SL* ps, SLDataType x)
{
SeqListCheckCapacity(ps);
//挪動資料
int end = ps->size - 1;//將最后一個數的下標賦給end
while (end >= 0)
{
ps->a[end + 1] = ps->a[end];
end--;
}
ps->a[0] = x;
ps->size++;
}
//順序表的頭刪
void SeqListPopFront(SL* ps, SLDataType x)
{
assert(ps->size > 0);
int begin = 1;
while (begin < ps->size)
{
ps->a[begin - 1] = ps->a[begin];
begin++;
}
ps->size--;
}
//順序表之查找元素,找到回傳下標,沒找到回傳-1
int SeqListFind(SL* ps, SLDataType x)
{
for (int i = 0; i < ps->size; i++)
{
if (ps->a[i] == x)
{
return i;
}
}
return -1;
}
//在指定下標位置插入
void SeqListInsert(SL* ps, int pos, SLDataType x)
{
//判斷pos的位置是否符合順序表的特征(必須保持連續)
//溫柔處理方式
//if (pos > ps->size || pos < 0)
//{
// printf("pos invalid\n");
// return;
//}
//暴力處理方式
assert(pos <= ps->size && pos >= 0);
SeqListCheckCapacity(ps);
int end = ps->size - 1;
while (end >= pos)
{
ps->a[end + 1] = ps->a[end];
end--;
}
ps->a[pos] = x;
ps->size++;
}
//洗掉指定位置的資料
void SeqListErase(SL* ps, int pos)
{
assert(pos < ps->size && pos >= 0);
int begin = pos + 1;
while (begin < ps->size)
{
ps->a[begin - 1] = ps->a[begin];
begin++;
}
ps->size--;
}
總結:
以上就是順序表的實作,
歡迎大家評論區留言,點贊支持和指正~

轉載請註明出處,本文鏈接:https://www.uj5u.com/qita/323445.html
標籤:其他
