網(wǎng)站首頁 編程語言 正文
編程環(huán)境為 ubuntu 18.04。
順序表需要連續(xù)一片存儲空間，存儲任意類型的元素，這里以存儲 int 類型數(shù)據(jù)為例。
一、順序表的結(jié)構(gòu)定義
size 為容量，length 為當前已知數(shù)據(jù)表元素的個數(shù)
typedef struct Vector{
int *data; //該順序表這片連續(xù)空間的首地址
int size, length;
} Vec;二、順序表的結(jié)構(gòu)操作
1.初始化
Vec *init(int n){ //該順序表具有n個存儲單元
Vec *v = (Vec *)malloc(sizeof(Vec)); //在內(nèi)存棧上開辟一個空間 malloc在內(nèi)存的堆區(qū)，在函數(shù)外面也能訪問
v->data = (int *)malloc(sizeof(int) * n);
v->size = n;
v->length = 0;
return v;
}2.插入操作
int insert(Vec *v, int ind, int val) { //ind為插入元素的位置,val為插入元素的值
if(v == NULL) return 0;
if(ind < 0 || ind > v->length) return 0; //判斷要插入的位置是否合法
if(v->length == v->size) {
if(!expand(v)){ //擴容失敗
printf(RED("fail to expand!\n"));
}
printf(GREEN("success to expand! the size = %d\n"),v->size);
}
for(int i = v->length; i > ind; i--){
v->data[i] = v->data[i-1];
}
v->data[ind] = val;
v->length += 1;
return 1;
}為什么需要判斷插入的位置是否合法呢？這是因為順序表是連續(xù)一片存儲空間，所以內(nèi)存是連續(xù)的。
下圖以 length = 5，size = 9 為例，我們只能在下標為 0 到 4 之間的數(shù)中插入數(shù)據(jù)。
插入一個元素示意圖
3.刪除操作
int erase(Vec *v, int ind){ //把下標為ind的元素刪除
if(v == NULL) return 0;
if(ind < 0 || ind >= v->length) return 0;
for(int i = ind + 1; i < v->length; i++){
v->data[i - 1] = v->data[i];
}
v->length -= 1;
return 1;
}- 判斷需要刪除元素的下標是否合法，與插入元素類似
- 刪除一個元素示意圖
4.擴容操作
int expand(Vec *v){
//順序表的擴容
//malloc 動態(tài)申請空間，空間不一定干凈 calloc 動態(tài)申請空間，并且清空 realloc 重新申請空間
int extr_size = v->size;
int *p;
while(extr_size) {
p = (int *)realloc(v->data, sizeof(int) * (v->size + extr_size));
if(p != NULL) break; //p不為空，說明擴容成功，這個時候直接跳出循環(huán)
extr_size >>= 1; //否則就把額外擴容的空間除以2，降低要求
}
if(p == NULL) return 0; //判斷跳出循環(huán)究竟是擴容成功還是擴容失敗，如果擴容失敗，那就是p為空地址，找不到符合條件的內(nèi)存區(qū)域
v->size += extr_size;
v->data = p;
return 1;
}注意擴容這里寫的比較巧妙，首先 int extr_size = v->size;表示先將需要擴容的大小設(shè)置成原本的大小，然后就判斷能不能找到那么大的空間。 p = (int *)realloc(v->data, sizeof(int) * (v->size + extr_size)); 如果在系統(tǒng)中能找到這么大的容量，那么就返回找到的內(nèi)存地址的首地址，然后就可以結(jié)束跳出循環(huán)；要是找不到的話那只能降低要求，把 extr_size 除以 2，看看能不能知道，如果實在找不到，extr_size 為 0，就會跳出循環(huán)。然后可以通過判斷 p 是不是空指針來判斷程序是找到能夠擴容的空間退出的還是找不到退出的。
要是對 malloc、calloc 和 realloc 不熟悉的，可以看我這篇博文：C語言深入探索動態(tài)內(nèi)存分配的使用
5.釋放操作
void clear(Vec *v){ //釋放空間
if(v == NULL) return;
free(v->data);
free(v);
return;
}先釋放數(shù)據(jù)，再釋放整個順序表。
6.輸出
void output(Vec *v){
if(v == NULL) return ;
printf("[");
for(int i = 0; i < v->length; i++){
i && printf(", ");
printf("%d", v->data[i]);
}
printf("]\n");
return ;
}三、示例
#include <stdio.h>
#include<stdlib.h>
#include<time.h>
//#include<windows.h>
#define COLOR(a, b) "\033[" #b "m" a "\033[0m"
#define GREEN(a) COLOR(a, 32)
#define RED(a) COLOR(a, 31)
typedef struct Vector{
int *data; //該順序表這片連續(xù)空間的首地址
int size, length;
} Vec;
Vec *init(int n){ //該順序表具有n個存儲單元
Vec *v = (Vec *)malloc(sizeof(Vec)); //在內(nèi)存棧上開辟一個空間 malloc在內(nèi)存的堆區(qū)，在函數(shù)外面也能訪問
v->data = (int *)malloc(sizeof(int) * n);
v->size = n;
v->length = 0;
return v;
}
int expand(Vec *v){
//順序表的擴容
//malloc 動態(tài)申請空間，空間不一定干凈 calloc 動態(tài)申請空間，并且清空 realloc 重新申請空間
int extr_size = v->size;
int *p;
while(extr_size) {
p = (int *)realloc(v->data, sizeof(int) * (v->size + extr_size));
if(p != NULL) break; //p不為空，說明擴容成功，這個時候直接跳出循環(huán)
extr_size >>= 1; //否則就把額外擴容的空間除以2，降低要求
}
if(p == NULL) return 0; //判斷跳出循環(huán)究竟是擴容成功還是擴容失敗，如果擴容失敗，那就是p為空地址，找不到符合條件的內(nèi)存區(qū)域
v->size += extr_size;
v->data = p;
return 1;
}
int insert(Vec *v, int ind, int val) { //ind為插入元素的位置,val為插入元素的值
if(v == NULL) return 0;
if(ind < 0 || ind > v->length) return 0;
if(v->length == v->size) {
if(!expand(v)){
printf(RED("fail to expand!\n"));
}
printf(GREEN("success to expand! the size = %d\n"),v->size);
}
for(int i = v->length; i > ind; i--){
v->data[i] = v->data[i-1];
}
v->data[ind] = val;
v->length += 1;
return 1;
}
int erase(Vec *v, int ind){ //把下標為ind的元素刪除
if(v == NULL) return 0;
if(ind < 0 || ind >= v->length) return 0;
for(int i = ind + 1; i < v->length; i++){
v->data[i - 1] = v->data[i];
}
v->length -= 1;
return 1;
}
void output(Vec *v){
if(v == NULL) return ;
printf("[");
for(int i = 0; i < v->length; i++){
i && printf(", ");
printf("%d", v->data[i]);
}
printf("]\n");
return ;
}
void clear(Vec *v){ //釋放空間
if(v == NULL) return;
free(v->data);
free(v);
return;
}
int main(){
#define MAX_N 20
Vec *v = init(1);
srand(time(0)); //設(shè)置種子
for (int i = 0; i < MAX_N; i++){
int op = rand() % 4;
int ind = rand() % (v->length + 3) - 1; //取值范圍[-1, v->length + 1]
int val = rand() % 100; //val為1到99之間的數(shù)
switch(op){
case 0:
case 1:
case 2: {
printf("insert %d at %d to the Vector = %d\n", val, ind, insert(v, ind, val));
}break;
case 3:{
printf("erase a item at %d = %d\n",ind,erase(v, ind));
}break;
}
output(v);
printf("\n");
}
#undef MAX_N
clear(v);
return 0;
}輸出結(jié)果如下：
insert 82 at 0 to the Vector = 1
[82]
?
insert 38 at 2 to the Vector = 0
[82]
?
success to expand! the size = 2
insert 7 at 1 to the Vector = 1
[82, 7]
?
success to expand! the size = 4
insert 86 at 2 to the Vector = 1
[82, 7, 86]
?
erase a item at 4 = 0
[82, 7, 86]
?
erase a item at 4 = 0
[82, 7, 86]
?
insert 48 at 0 to the Vector = 1
[48, 82, 7, 86]
?
insert 65 at 5 to the Vector = 0
[48, 82, 7, 86]
?
success to expand! the size = 8
insert 92 at 4 to the Vector = 1
[48, 82, 7, 86, 92]
?
erase a item at 2 = 1
[48, 82, 86, 92]
?
insert 81 at 2 to the Vector = 1
[48, 82, 81, 86, 92]
?
insert 9 at 0 to the Vector = 1
[9, 48, 82, 81, 86, 92]
?
insert 99 at 1 to the Vector = 1
[9, 99, 48, 82, 81, 86, 92]
?
insert 29 at 7 to the Vector = 1
[9, 99, 48, 82, 81, 86, 92, 29]
?
success to expand! the size = 16
insert 38 at 0 to the Vector = 1
[38, 9, 99, 48, 82, 81, 86, 92, 29]
?
erase a item at 0 = 1
[9, 99, 48, 82, 81, 86, 92, 29]
?
erase a item at 8 = 0
[9, 99, 48, 82, 81, 86, 92, 29]
?
erase a item at 6 = 1
[9, 99, 48, 82, 81, 86, 29]
?
insert 57 at -1 to the Vector = 0
[9, 99, 48, 82, 81, 86, 29]
?
insert 32 at 4 to the Vector = 1
[9, 99, 48, 82, 32, 81, 86, 29]
原文鏈接：https://blog.csdn.net/weixin_43129713/article/details/124244476
相關(guān)推薦
- 2022-11-19 React組件的應(yīng)用介紹_React
- 2022-04-04 asp.net使用原生控件實現(xiàn)自定義列導(dǎo)出功能的方法_實用技巧
- 2022-01-31 （數(shù)據(jù)）圖像預(yù)處理——image augmentation圖像增廣之cutout、Mixup、Cut
- 2022-10-20 C++淺析虛函數(shù)使用方法_C 語言
- 2022-08-20 Python中range()與np.arange()的具體使用_python
- 2022-12-12 Kotlin字節(jié)碼層探究構(gòu)造函數(shù)與成員變量和init代碼塊執(zhí)行順序_Android
- 2022-10-01 C語言實現(xiàn)學(xué)生個人消費管理系統(tǒng)_C 語言
- 2022-07-26 注冊bean有多少種方式
- 最近更新
-
- window11 系統(tǒng)安裝 yarn
- 超詳細win安裝深度學(xué)習環(huán)境2025年最新版（
- Linux 中運行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎(chǔ)操作-- 運算符，流程控制 Flo
- 1. Int 和Integer 的區(qū)別，Jav
- spring @retryable不生效的一種
- Spring Security之認證信息的處理
- Spring Security之認證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權(quán)
- redisson分布式鎖中waittime的設(shè)
- maven:解決release錯誤：Artif
- restTemplate使用總結(jié)
- Spring Security之安全異常處理
- MybatisPlus優(yōu)雅實現(xiàn)加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務(wù)發(fā)現(xiàn)-Nac
- Spring Security之基于HttpR
- Redis 底層數(shù)據(jù)結(jié)構(gòu)-簡單動態(tài)字符串（SD
- arthas操作spring被代理目標對象命令
- Spring中的單例模式應(yīng)用詳解
- 聊聊消息隊列，發(fā)送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠程分支
提供CDN加速