網站首頁 編程語言 正文
一、順序表的概念與結構
1.線性表的解釋
首先我們在這里引入線性表的概念。線性表是n個具有相同特性的數據元素的有限序列。線性表是一種在實際中廣泛使用的數據結構。
常見的線性表：順序表、鏈表、棧、隊列、字符串……
線性表在邏輯上是線性結構，也就是說是連續的一條直線。但是在物理結構上并不一定是連續的，線性表在物理上存儲時，通常以數據和鏈式結構的形式存儲。
順序表就是線性表的一種，我們在這里詳細解釋一下順序表的實現，后續我們會更新鏈表等內容。
2.順序表概念解釋
順序表是用一段物理地址連續的存儲單元依次存儲數據元素的線性結構，一般情況下采用數組存儲。在數組上完成增刪查改。
而順序表一般可分為：
- 靜態順序表：使用定長數組存儲。
- 動態順序表：使用動態開辟的數組存儲。
二、順序表的思路及代碼實現詳解
1.靜態順序表的實現
我們先想出來一個靜態表整體的模板思路：
- 定義一個結構體，該結構體包含一個可以存放數據的數組和記錄數組中有效數字的變量。
- 初始化結構體。
- 打印結構體。
- 頭插。
- 尾插。
- 頭刪。
- 尾刪。
- 任意位置插入。
- 任意位置刪除。
這里需要有一點注意的是，我們在定義結構體中的數組時，我們可以用typedef進行變量名簡化，這也方便我們后期更改存儲類型的時候直接更改typedef處就行。同時我們會想到數組的大小需要define定義一個宏，這樣大大提高了代碼后期的可維護性。
但是我們仔細想一下，假如我們存儲的數據滿了，我們想要繼續存儲的話還要找到源碼進行更改大小。每次存儲滿了，都要更改。那是不是太麻煩了，且效率很低。這時候我們就聯想到了動態的順序表，可以自動開辟空間，從而大大提高效率。
這里我就給出大家靜態順序表定義及接口的代碼，不再詳細解釋接口的實現了。我們這里詳細解釋一下動態順序表的解釋。靜態順序表接口的實現與動態順序表接口實現大同小異，可參考動態順序表接口的詳解。
代碼如下：
#define MAX_SIZE 10
typedef int SQDataType;
typedef struct SeqList
{
SQDataType a[MAX_SIZE];
int size;
}SL;
//typedef struct SeqList SL;
typedef struct SeqList SL;
//初始化結構體
void SeqListInit(SL* ps);
//打印
void SeqListPrint(SL s);
//尾插
void SeqListPushBack(SL* ps, SQDataType x);
//尾刪
void SeqListPopBack(SL* ps);
//頭插
void SeqListPushFrint(SL* ps, SQDataType x);
//頭刪
void SeqListPopFrint(SL* ps);
//查找位置
int SeqListFind(SL s, SQDataType x);
//任意插入
void SeqListInsert(SL* ps, int pos, SQDataType x);
//任意刪
void SeqListErase(SL* ps, int pos);2.動態順序表思路及代碼實現
2.1 動態順序表的整體思路
動態順序表的思路與靜態大致相同，但也有所不同，我來給大家詳細解釋一下。我們先看動態順序表的整體思路模板：
- 定義一個結構體，該結構體包含一個可以存放數據的動態數組和記錄數組中有效數據的變量，兩外還需要一個變量記錄當前數組的大小。
- 初始化結構體。
- 打印結構體。
- 檢查數組容量
- 頭插。
- 尾插。
- 頭刪。
- 尾刪。
- 任意位置插入。
- 任意位置刪除。
- 釋放動態數組空間
我們上面提到了動態的數組，需要用malloc或realloc動態開辟空間。由于是動態開辟的，我們這里多了一項釋放動態開辟的空間。注意，記錄數組的有效數據和數組大小并不相同。有效數據是已經存儲的數據個數，而數組大小是指最能夠存儲數組的個數。我們為什么要記錄數組的大小呢？這里是用來判斷是否存儲滿了，滿了話要開辟空間。
我們來詳細看一下每個接口的實現。
2.2 定義結構體的實現
在定義結構體時，我們可以用typedef進行數組類型簡化，同時方便我們后期更改存儲類型的時候直接更改typedef處即可。同時我們也用typedef進行結構體類型簡化，方便我們以后編輯代碼。我們來看一下代碼的實現：
typedef int SQDataType;
struct SeqList
{
SQDataType* a;
int size;
int capacity;
};
typedef struct SeqList SL;通過上面的代碼我們可以發現，當我們不想存儲int型數據時，我們只需把‘typedef int SQDataType’改為‘typedef doubleSQDataType’即可。極大的提高了代碼的維護性。
2.3 初始化結構體
我們初始化結構體時，可以先將數組置空，我們后期插入數據時可再開辟空間。同時當然有效數據和數組大小都要初始化成零。我們看代碼的實現。
void SeqListInit(SL* ps)
{
ps->a = NULL;
ps->size = 0;
ps->capacity = 0;
}我們這里是改變了結構體的內容，所以需要傳地址，用指針變量來接收。
2.4 結構體打印
結構體打印方便我們觀察對動態數組的操作。打印的時數組的有效數據的內容。我們來看代碼的實現。
void SeqListPrint(SL s)
{
int i = 0;
for (i = 0; i < s.size; i++)
{
printf("%d ", s.a[i]);
}
printf("\n");
}2.5 檢查數組容量
我們仔細想一想，是不是在插入每個數據之前都要檢查數組是否已經滿了。如果滿了，則需要增容。如果沒有滿，就插入數據即可。在這里我們需要實現頭插、尾插、任意插入三個接口，所以我們就把檢查數組容量單獨分裝一個函數，這樣提高代碼的簡潔性。我們看一下代碼的實現。
void SQLCheckCapacity(SL* ps)
{
if (ps->size == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
SQDataType* tmp =(SQDataType*)realloc(ps->a, sizeof(SQDataType) * newcapacity);
if (tmp == NULL)
{
printf("realloc failed\n");
exit(-1);
}
ps->capacity = newcapacity;
ps->a = tmp;
}
}當我們檢查增容時，我們還要判斷一下之前的數組大小是否為零，如果是零的話，我們要給其賦一個值。因為我們剛開始初始化數組的時候把數組指針置空了。在動態順序表中我們增容一般會擴大到原來的2倍。
2.6 頭插
在插入之前要判斷數組是否已經滿了。頭插的思想就是把數組的內容整體后移一位，我們把要插入的數據放在第一位。我們結合著代碼一起理解。
void SeqListPushFrint(SL* ps, SQDataType x)
{
SQLCheckCapacity(ps);
int end = ps->size - 1;
while (end >= 0)
{
ps->a[end+1] = ps->a[end];
end--;
}
ps->a[0] = x;
ps->size++;
}2.7 尾插
同樣， 在插入之前要判斷數組是否已經滿了。尾插的思想很簡單。就是直接在數組尾部插入一個數據即可。我們看一下代碼的實現。
void SeqListPushBack(SL* ps, SQDataType x)
{
SQLCheckCapacity(ps);
ps->a[ps->size] = x;
ps->size++;
}2.8 頭刪
刪除時我們也有要注意的一點，就是檢查數組中是否有元素給我們刪除。頭刪的思想就是除去數組的第一個元素，我們將后面的元素整體向前移動一位，將第一位給覆蓋了。我們來看代碼。
void SeqListPopFrint(SL* ps)
{
assert(ps->size > 0);
int i = 0;
for (i = 0; i < ps->size - 1; i++)
{
ps->a[i] = ps->a[i + 1];
}
ps->size--;
}2.9 尾刪
同樣，在尾刪之前，我們要檢查數組中是否有元素給我們刪除。尾刪的思想十分簡單，就是把數組的有效數據減一即可。我們看一下代碼的實現。
void SeqListPopBack(SL* ps)
{
assert(ps->size > 0);
ps->size--;
}2.10 任意刪除
在任意刪除時，我們首先要判斷刪除的位置是否合理，不能違背順序表的規則。同樣，在尾刪之前，我們要檢查數組中是否有元素給我們刪除。任意刪除就是我們指出刪除位置的下標進行刪除。當然，我們想要刪除數組中指定元素時，我們可以先查出元素下標在進行刪除。這個相對來說較復雜一點，我們結合著代碼理解一下。
//查找位置
int SeqListFind(SL s, SQDataType x)
{
int i = 0;
for (i = 0; i < s.size; i++)
{
if (s.a[i] == x)
{
return i;
}
}
return -1;
}
void SeqListErase(SL* ps, int pos)
{
assert(pos >= 0 && pos < ps->size);
int begin = pos + 1;
while (begin < ps->size)
{
ps->a[begin - 1] = ps->a[begin];
begin++;
}
ps->size--;
}2.11 任意插入
在任意插入時時，我們也要判斷插入的位置是否合理，不能違背順序表的規則。插入時，我們不能忘記檢查數組是否滿了。任意插入的思想與任意刪除的思想基本相同。任意插入的思想就是在我們指出刪除位置的下標進行插入。我們看一下代碼實現。
void SeqListInsert(SL* ps, int pos, SQDataType x)
{
assert(pos >= 0 && pos <= ps->size);
SQLCheckCapacity(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 空間釋放
由于我們的數組是動態開辟的，所以當我們不用時，我們要及時釋放掉動態開辟的空間，避免內存泄漏。同時我們要把數組指針再次置空，避免產生野指針。我們看代碼實現。
void SeqListDestory(SL* ps)
{
free(ps->a);
ps->a = NULL;
ps->capacity = ps->size = 0;
}三、順序表代碼整合
由于代碼量相對來說有一點多，所以我們就將函數的聲明的定義分開，這樣有利于提高代碼的可讀性，同時會保持一個良好的思路，且方便編寫代碼。
我們將函數的聲明放在單獨的一個SeqList.h的頭文件，函數的實現放在一個單獨的SeqList.c源文件，函數的主方法及調用放在另一個單獨的test.c源文件。
SeqList.h
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SQDataType;
struct SeqList
{
SQDataType* a;
int size;
int capacity;
};
typedef struct SeqList SL;
//初始化結構體
void SeqListInit(SL* ps);
//打印
void SeqListPrint(SL s);
//尾插
void SeqListPushBack(SL* ps, SQDataType x);
//尾刪
void SeqListPopBack(SL* ps);
//頭插
void SeqListPushFrint(SL* ps, SQDataType x);
//頭刪
void SeqListPopFrint(SL* ps);
//查找位置
int SeqListFind(SL s, SQDataType x);
//任意插入
void SeqListInsert(SL* ps, int pos, SQDataType x);
//任意刪
void SeqListErase(SL* ps, int pos);
//銷毀空間
void SeqListDestory(SL* ps);SeqList.c
#include"SeqList.h"
//初始化結構體
void SeqListInit(SL* ps)
{
ps->a = NULL;
ps->size = 0;
ps->capacity = 0;
}
//打印
void SeqListPrint(SL s)
{
int i = 0;
for (i = 0; i < s.size; i++)
{
printf("%d ", s.a[i]);
}
printf("\n");
}
//查容增容
void SQLCheckCapacity(SL* ps)
{
if (ps->size == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
SQDataType* tmp =(SQDataType*)realloc(ps->a, sizeof(SQDataType) * newcapacity);
if (tmp == NULL)
{
printf("realloc failed\n");
exit(-1);
}
ps->capacity = newcapacity;
ps->a = tmp;
}
}
//尾插
void SeqListPushBack(SL* ps, SQDataType x)
{
SQLCheckCapacity(ps);
ps->a[ps->size] = x;
ps->size++;
}
//尾刪
void SeqListPopBack(SL* ps)
{
assert(ps->size > 0);
ps->size--;
}
//頭插
void SeqListPushFrint(SL* ps, SQDataType x)
{
SQLCheckCapacity(ps);
int end = ps->size - 1;
while (end >= 0)
{
ps->a[end+1] = ps->a[end];
end--;
}
ps->a[0] = x;
ps->size++;
}
//頭刪
void SeqListPopFrint(SL* ps)
{
assert(ps->size > 0);
int i = 0;
for (i = 0; i < ps->size - 1; i++)
{
ps->a[i] = ps->a[i + 1];
}
ps->size--;
}
//查找位置
int SeqListFind(SL s, SQDataType x)
{
int i = 0;
for (i = 0; i < s.size; i++)
{
if (s.a[i] == x)
{
return i;
}
}
return -1;
}
//任意插——在下標為pos的位置插入數據
void SeqListInsert(SL* ps, int pos, SQDataType x)
{
assert(pos >= 0 && pos <= ps->size);
SQLCheckCapacity(ps);
int end = ps->size-1;
while (end >= pos)
{
ps->a[end+1] = ps->a[end];
end--;
}
ps->a[pos] = x;
ps->size++;
}
//任意刪——刪除下標為pos的數據
void SeqListErase(SL* ps, int pos)
{
assert(pos >= 0 && pos < ps->size);
int begin = pos + 1;
while (begin < ps->size)
{
ps->a[begin - 1] = ps->a[begin];
begin++;
}
ps->size--;
}
//銷毀空間
void SeqListDestory(SL* ps)
{
free(ps->a);
ps->a = NULL;
ps->capacity = ps->size = 0;
}test.c
#include"SeqList.h"
void test()
{
SL s1;
SeqListInit(&s1);
SeqListPushBack(&s1, 1);
SeqListPushFrint(&s1, 1);
SeqListPushFrint(&s1, 2);
SeqListPushFrint(&s1, 3);
SeqListPushFrint(&s1, 4);
SeqListPushBack(&s1, 5);
SeqListPrint(s1);
SeqListPopFrint(&s1);
SeqListPrint(s1);
int pos = SeqListFind(s1, 1);
SeqListInsert(&s1, pos, 10);
SeqListInsert(&s1, 0, 20);
SeqListPrint(s1);
SeqListErase(&s1, 0);
SeqListPrint(s1);
SeqListDestory(&s1);
}
int main()
{
test();
return 0;
}原文鏈接：https://blog.csdn.net/weixin_67596609/article/details/127967719
相關推薦
- 2022-06-19 C#中的checksum計算公式_C#教程
- 2022-07-30 Linux secure 日志分析
- 2022-06-25 Gitlab-runner+Docker實現自動部署SpringBoot項目_docker
- 2022-10-09 React高階組件的使用淺析_React
- 2022-05-27 iOS實現拼圖小游戲_IOS
- 2024-03-15 docker刪除、停止所有容器或鏡像
- 2022-04-06 C語言函數調用的三種實現方法實例_C 語言
- 2022-11-30 React18?中的?Suspense?API使用實例詳解_React
- 最近更新
-
- window11 系統安裝 yarn
- 超詳細win安裝深度學習環境2025年最新版（
- Linux 中運行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎操作-- 運算符，流程控制 Flo
- 1. Int 和Integer 的區別，Jav
- spring @retryable不生效的一種
- Spring Security之認證信息的處理
- Spring Security之認證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權
- redisson分布式鎖中waittime的設
- maven:解決release錯誤：Artif
- restTemplate使用總結
- Spring Security之安全異常處理
- MybatisPlus優雅實現加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務發現-Nac
- Spring Security之基于HttpR
- Redis 底層數據結構-簡單動態字符串（SD
- arthas操作spring被代理目標對象命令
- Spring中的單例模式應用詳解
- 聊聊消息隊列，發送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠程分支
提供CDN加速