網(wǎng)站首頁 編程語言 正文
一、認(rèn)識順序表
1.線性表
線性表是n個(gè)具有相同特性的數(shù)據(jù)元素的有限序列，線性表是一種在實(shí)際中廣泛使用的數(shù)據(jù)結(jié)構(gòu)，常見的線性表有順序表、鏈表、棧、隊(duì)列、字符串……線性表在邏輯上是線性結(jié)構(gòu)，也就是說是一條連續(xù)的直線。但是在物理結(jié)構(gòu)上并不一定是連續(xù)的，線性表在物理上存儲時(shí)，通常以數(shù)組和鏈?zhǔn)浇Y(jié)構(gòu)的形式來存儲。
2.順序表的概念及結(jié)構(gòu)
順序表是用一段物理地址連續(xù)的存儲單元依次存儲數(shù)據(jù)元素的線性結(jié)構(gòu)，一般情況下采用數(shù)組存儲。在數(shù)組上完成數(shù)據(jù)的增刪改查。順序表一般可分為：靜態(tài)順序表和動(dòng)態(tài)順序表（使用動(dòng)態(tài)開辟的數(shù)組存儲）。
1.靜態(tài)順序表：使用定長數(shù)組存儲元素
#define MAX 10
typedef int SLDataType;//當(dāng)存儲數(shù)據(jù)類型改變時(shí)，方便修改
typedef struct SeqList
{
SLDataType arr[MAX];//用來存儲數(shù)據(jù)
int size;//用來記錄數(shù)組中存儲有效數(shù)據(jù)元素的個(gè)數(shù)
}SL;
2.動(dòng)態(tài)順序表：使用動(dòng)態(tài)開辟的數(shù)組存儲
//動(dòng)態(tài)順序表
typedef int SLDataType;//當(dāng)存儲數(shù)據(jù)類型改變時(shí)，方便修改
typedef struct SeqList
{
SLDataType* arr;//指向動(dòng)態(tài)開辟的數(shù)組
int size;//用來記錄數(shù)組中存儲有效數(shù)據(jù)元素的個(gè)數(shù)
int capacity;//用來記錄容量大小
}SL;
靜態(tài)順序表只適用于確定知道需要存多少數(shù)據(jù)的場景。靜態(tài)順序表的定長數(shù)組導(dǎo)致MAX定大了，空間開多了浪費(fèi)，開少了不夠用。所以現(xiàn)實(shí)中基本都是用動(dòng)態(tài)順序表，根據(jù)需要?jiǎng)討B(tài)的分配空間大小，所以本文中使用動(dòng)態(tài)開辟的順序表實(shí)現(xiàn)順序表的基本操作。
二、順序表的基本操作（接口實(shí)現(xiàn)）
1.初始化順序表
void SLInit(SL* ps)
{
assert(ps);
ps->arr = NULL;
ps->size = ps->capacity = 0;
}
初始化時(shí)設(shè)置其有效數(shù)據(jù)個(gè)數(shù)和容量都為0，指針指向NULL。
2.打印順序表
void SLPrint(SL* ps)
{
int i = 0;
for (i = 0; i < ps->size; i++)
{
printf("%d ", ps->arr[i]);
}
printf("\n");
}
3.尾插
void SLPushBack(SL* ps, SLDataType x)
{
assert(ps);
if (ps->size == ps->capacity)
{
int NewCapacity =ps->capacity == 0 ? 4 : 2 * ps->capacity;//判斷剛開始是否有空間
SLDataType* tmp = (SLDataType*)realloc(ps->arr,sizeof(SLDataType) * NewCapacity);
if (tmp == NULL)
{
perror("realloc");
exit(-1);
}
ps->arr = tmp;
ps->capacity = NewCapacity;
}
ps->arr[ps->size] = x;
ps->size++;
}尾插就是在尾部插入數(shù)據(jù)，因?yàn)閯傞_始的時(shí)候沒有給數(shù)組分配空間，所以要考慮當(dāng)沒有空間時(shí)要去申請空間，realloc函數(shù)是擴(kuò)容函數(shù)，在指針為空的情況下作用和malloc相同，int NewCapacity =ps->capacity == 0 ? 4 : 2 * ps->capacity判斷當(dāng)前容量大小并確定要開辟的空間大小。
SLDataType* tmp = (SLDataType*)realloc(ps->arr,sizeof(SLDataType) * NewCapacity)，用來在堆內(nèi)存中開辟空間，realloc之后注意將其強(qiáng)制轉(zhuǎn)化成SLDataType*類型。當(dāng)成功開辟空間之后賦給ps->arr，同時(shí)注意將NewCapacity賦給ps->capacity。
4.尾刪
void SLPopBack(SL* ps)
{
assert(ps);
//暴力的檢查
assert(ps->size > 0);//判斷ps->size是否大于0，當(dāng)?shù)扔?時(shí)再刪的話ps->size就會變?yōu)?1，越界
//溫柔的檢查
//if (ps->size == 0)
//{
// return;
//}
ps->size--;
}
當(dāng)ps->size等于0時(shí)直接返回，如果不返回，造成ps->size為負(fù)數(shù)，造成數(shù)組越界，當(dāng)我們再次插入數(shù)據(jù)的時(shí)候可能會出現(xiàn)報(bào)錯(cuò)，同時(shí)當(dāng)越界時(shí)可能不會報(bào)錯(cuò)，但是可能會在free時(shí)候報(bào)錯(cuò)。所以要用assert(ps->size > 0)檢查ps->size大小，等于0時(shí)直接退出，并提示。
擴(kuò)展：free時(shí)候報(bào)錯(cuò)可能的錯(cuò)誤原因有兩種，一是free時(shí)候指針不正確，可能是野指針，同時(shí)釋放的時(shí)候必須從起始位置釋放。二是越界時(shí)候free會報(bào)錯(cuò)。當(dāng)越界讀數(shù)組的時(shí)候基本不會被檢查出來報(bào)錯(cuò)，但是改變它的值的時(shí)候就可能會報(bào)錯(cuò)，是一種抽查行為，是在運(yùn)行時(shí)檢查。
5.擴(kuò)容
void SLCheckCapacity(SL* ps)
{
assert(ps);
//檢查是否需要擴(kuò)容
if (ps->size == ps->capacity)
{
int NewCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
SLDataType* tmp = (SLDataType*)realloc(ps->arr, sizeof(SLDataType) * NewCapacity);
if (tmp == NULL)
{
perror("realloc");
exit(-1);
}
ps->capacity = NewCapacity;
ps->arr = tmp;
}
}擴(kuò)容函數(shù)，用于檢查數(shù)組空間大小是否適合繼續(xù)插入，當(dāng)數(shù)組空間不足時(shí)進(jìn)行擴(kuò)容，定義此函數(shù)之后可以對上面尾插函數(shù)進(jìn)行簡化，如下：
void SLPushBack(SL* ps, SLDataType x)
{
SLCheckCapacity(ps);
ps->arr[ps->size] = x;
ps->size++;
}
6.頭插
void SLPushFront(SL* ps, SLDataType x)
{
SLCheckCapacity(ps);
int end = ps->size;
//挪動(dòng)數(shù)據(jù)
while (end > 0)
{
ps->arr[end] = ps->arr[end-1];
end--;
}
ps->arr[0] = x;
ps->size++;
}
利用擴(kuò)容函數(shù)對其檢查，注意控制循環(huán)結(jié)束條件。
7.頭刪
void SLPopFront(SL* ps)
{
assert(ps);
assert(ps->size > 0);
int begin = 0;
while (begin < ps->size-1)
{
ps->arr[begin] = ps->arr[begin + 1];
begin++;
}
ps->size--;
}
注意判斷當(dāng)ps->size等于0時(shí)不能再進(jìn)行ps->size--，要加上一條判斷語句assert(ps->size > 0)。
8.任意位置插入
void SLInsert(SL* ps, int pos, SLDataType x)//任意位置插入
{
assert(ps);
assert(pos >= 0);
assert(pos <= ps->size);
SLCheckCapacity(ps);
int end = ps->size;
while (end>pos)
{
ps->arr[end] = ps->arr[end - 1];
end--;
}
ps->arr[pos] = x;
ps->size++;
}
pos是數(shù)組下標(biāo)，同時(shí)注意判斷pos的范圍。
9.任意位置刪除
void SLErase(SL* ps, int pos)//任意位置刪除
{
assert(ps);
assert(pos >= 0);
assert(pos < ps->size);
while (pos < ps->size-1)
{
ps->arr[pos] = ps->arr[pos + 1];
pos++;
}
ps->size--;
}
pos表示的是數(shù)組下標(biāo)，有assert(pos >= 0)和assert(pos <= ps->size)兩個(gè)判斷條件之后不用再加assert(ps->size>0)，因?yàn)楫?dāng)ps->size等于0時(shí)，assert(pos <= ps->size)會報(bào)錯(cuò)。
10.查找某個(gè)數(shù)的位置
int SLFind(SL* ps, SLDataType x)//返回類型為int,是數(shù)組下標(biāo)
{
assert(ps);
int i = 0;
for (i = 0; i < ps->size; i++)
{
if (ps->arr[i] == x)
return i;
}
return -1;
}
返回值是數(shù)組下標(biāo)。
思考：當(dāng)我們想刪除某個(gè)值時(shí)應(yīng)該怎么做？當(dāng)被刪除的值有多個(gè)時(shí)又要怎么做呢？
我們可以通過下面的代碼實(shí)現(xiàn)：
int SLNFind(SL* ps, SLDataType x, int begin)//begin是開始查找的位置
{
assert(ps);
int i = 0;
for (i = begin; i < ps->size; i++)
{
if (ps->arr[i] == x)
return i;
}
return -1;
}三、順序表演示及代碼（含源碼）
1.演示效果
2.完整源代碼
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
//動(dòng)態(tài)順序表
typedef int SLDataType;//當(dāng)存儲數(shù)據(jù)類型改變時(shí)，方便修改
typedef struct SeqList
{
SLDataType* arr;//指向動(dòng)態(tài)開辟的數(shù)組
int size;//用來記錄數(shù)組中存儲有效數(shù)據(jù)元素的個(gè)數(shù)
int capacity;//用來記錄容量大小
}SL;
void SLInit(SL* ps)//初始化順序表
{
assert(ps);
ps->arr = NULL;
ps->size = ps->capacity = 0;
}
void SLCheckCapacity(SL* ps)//檢查是否需要擴(kuò)容
{
assert(ps);
//檢查是否需要擴(kuò)容
if (ps->size == ps->capacity)
{
int NewCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
SLDataType* tmp = (SLDataType*)realloc(ps->arr, sizeof(SLDataType) * NewCapacity);
if (tmp == NULL)
{
perror("realloc");
exit(-1);
}
ps->capacity = NewCapacity;
ps->arr = tmp;
}
}
void SLPushBack(SL* ps, SLDataType x)//尾插
{
SLCheckCapacity(ps);//檢查是否需要擴(kuò)容
//assert(ps);
//if (ps->size == ps->capacity)
//{
// int NewCapacity =ps->capacity == 0 ? 4 : 2 * ps->capacity;//判斷剛開始是否有空間
// SLDataType* tmp = (SLDataType*)realloc(ps->arr,sizeof(SLDataType) * NewCapacity);
// if (tmp == NULL)
// {
// perror("realloc");
// exit(-1);
// }
// ps->arr = tmp;
// ps->capacity = NewCapacity;
//}
ps->arr[ps->size] = x;
ps->size++;
}
void SLPrint(SL* ps)//打印
{
int i = 0;
for (i = 0; i < ps->size; i++)
{
printf("%d ", ps->arr[i]);
}
printf("\n");
}
void SLDestroy(SL* ps)//銷毀
{
assert(ps);
if (ps->arr != NULL)
{
free(ps->arr);
ps->arr = NULL;
}
ps->size = ps->capacity = 0;
}
void SLPopBack(SL* ps)//尾刪
{
assert(ps);
//暴力的檢查
assert(ps->size > 0);//判斷ps->size是否大于0，當(dāng)?shù)扔?時(shí)再刪的話ps->size就會變?yōu)?1，越界
//溫柔的檢查
if (ps->size == 0)
{
return;
}
ps->size--;
}
void SLPushFront(SL* ps, SLDataType x)//頭插
{
SLCheckCapacity(ps);
int end = ps->size;
//挪動(dòng)數(shù)據(jù)
while (end > 0)
{
ps->arr[end] = ps->arr[end - 1];
end--;
}
ps->arr[0] = x;
ps->size++;
}
void SLPopFront(SL* ps)//頭刪
{
assert(ps);
assert(ps->size > 0);
int begin = 0;
while (begin < ps->size - 1)
{
ps->arr[begin] = ps->arr[begin + 1];
begin++;
}
ps->size--;
}
void SLInsert(SL* ps, int pos, SLDataType x)//任意位置插入
{
assert(ps);
assert(pos >= 0);
assert(pos <= ps->size);
SLCheckCapacity(ps);
int end = ps->size;
while (end > pos)
{
ps->arr[end] = ps->arr[end - 1];
end--;
}
ps->arr[pos] = x;
ps->size++;
}
void SLErase(SL* ps, int pos)//任意位置刪除
{
assert(ps);
assert(pos >= 0);
assert(pos < ps->size);
while (pos < ps->size - 1)
{
ps->arr[pos] = ps->arr[pos + 1];
pos++;
}
ps->size--;
}
int SLFind(SL* ps, SLDataType x)//查找某個(gè)數(shù)并返回下標(biāo)
{
assert(ps);
int i = 0;
for (i = 0; i < ps->size; i++)
{
if (ps->arr[i] == x)
return i;
}
return -1;
}
int SLNFind(SL* ps, SLDataType x, int begin)//從begin開始查找某個(gè)數(shù)
{
assert(ps);
int i = 0;
for (i = begin; i < ps->size; i++)
{
if (ps->arr[i] == x)
return i;
}
return -1;
}
void menu()//菜單函數(shù)
{
printf("********************************\n");
printf("** 1.尾插 2.尾刪 **\n");
printf("** 3.頭插 4.頭刪 **\n");
printf("** 5.任意位置插入 **\n");
printf("** 6.任意位置刪除 **\n");
printf("** 7.查找某個(gè)數(shù)并返回其下標(biāo) **\n");
printf("** 8.刪除某個(gè)數(shù) **\n");
printf("** 9.打印 **\n");
printf("** 0.退出程序 **\n");
}
int main()
{
int input = 0;
int ret = 0;
int pos = 0;
SL sl;
SLInit(&sl);
do {
menu();
printf("請選擇：");
scanf("%d", &input);
switch (input)
{
case 1:
printf("請輸入你要尾插的值，以-1結(jié)束：");
scanf("%d", &ret);
while (ret != -1)
{
SLPushBack(&sl, ret);
scanf("%d", &ret);
}
printf("尾插成功！\n");
break;
case 2:
SLPopBack(&sl);
printf("尾刪成功！\n");
break;
case 3:
printf("請輸入你要頭插的值，以-1結(jié)束：");
scanf("%d", &ret);
while (ret != -1)
{
SLPushFront(&sl, ret);
scanf("%d", &ret);
}
printf("頭插成功！\n");
break;
case 4:
SLPopFront(&sl);
printf("頭刪成功！\n");
break;
case 5:
printf("請輸入你想插入的位置和數(shù)值：");
scanf("%d%d", &pos, &ret);
SLInsert(&sl, pos - 1, ret);
printf("插入成功！\n");
break;
case 6:
printf("請輸入你想刪除的位置：");
scanf("%d", &pos);
SLErase(&sl, pos - 1);
printf("刪除成功！\n");
break;
case 7:
printf("請輸入你想要查找的數(shù)：");
scanf("%d", &ret);
int s = SLFind(&sl, ret);
printf("查找的數(shù)的數(shù)組下標(biāo)為:%d！\n", s);
break;
case 8:
printf("請輸入你要?jiǎng)h除的數(shù)值：");
scanf("%d", &ret);
int tmp = SLNFind(&sl, ret, 0);
while (tmp != -1)
{
SLErase(&sl, tmp);
tmp = SLNFind(&sl, ret, tmp);
}
printf("刪除成功！\n");
break;
case 9:
SLPrint(&sl);
break;
default:
printf("請重新選擇！\n");
break;
}
} while (input);
SLDestroy(&sl);
return 0;
}
原文鏈接：https://blog.csdn.net/weixin_53943591/article/details/127628288
相關(guān)推薦
- 2024-07-15 解決`idea`中`database`工具查詢起別名亂碼問題
- 2022-04-06 關(guān)于Redis數(shù)據(jù)庫三種持久化方案介紹_Redis
- 2022-07-26 當(dāng)本地ping通虛擬機(jī)，虛擬機(jī)ping不通本地時(shí)。
- 2023-02-15 go性能分析工具pprof的用途及使用詳解_Golang
- 2022-04-05 Python利用prettytable庫輸出好看的表格_python
- 2022-10-24 C#中GDI+繪制圓弧及圓角矩形等比縮放的繪制_C#教程
- 2022-05-13 C++ Poco庫的編譯和使用
- 2023-08-01 React之組件的分類、使用,事件對象,this指向問題,修改狀態(tài)以及受控組件與非受控組件
- 最近更新
-
- window11 系統(tǒng)安裝 yarn
- 超詳細(xì)win安裝深度學(xué)習(xí)環(huán)境2025年最新版（
- Linux 中運(yùn)行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎(chǔ)操作-- 運(yùn)算符，流程控制 Flo
- 1. Int 和Integer 的區(qū)別，Jav
- spring @retryable不生效的一種
- Spring Security之認(rèn)證信息的處理
- Spring Security之認(rèn)證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權(quán)
- redisson分布式鎖中waittime的設(shè)
- maven:解決release錯(cuò)誤：Artif
- restTemplate使用總結(jié)
- Spring Security之安全異常處理
- MybatisPlus優(yōu)雅實(shí)現(xiàn)加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務(wù)發(fā)現(xiàn)-Nac
- Spring Security之基于HttpR
- Redis 底層數(shù)據(jù)結(jié)構(gòu)-簡單動(dòng)態(tài)字符串（SD
- arthas操作spring被代理目標(biāo)對象命令
- Spring中的單例模式應(yīng)用詳解
- 聊聊消息隊(duì)列，發(fā)送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠(yuǎn)程分支
提供CDN加速