網站首頁 編程語言 正文
一、認識順序表
1.線性表
線性表是n個具有相同特性的數據元素的有限序列，線性表是一種在實際中廣泛使用的數據結構，常見的線性表有順序表、鏈表、棧、隊列、字符串……線性表在邏輯上是線性結構，也就是說是一條連續的直線。但是在物理結構上并不一定是連續的，線性表在物理上存儲時，通常以數組和鏈式結構的形式來存儲。
2.順序表的概念及結構
順序表是用一段物理地址連續的存儲單元依次存儲數據元素的線性結構，一般情況下采用數組存儲。在數組上完成數據的增刪改查。順序表一般可分為：靜態順序表和動態順序表（使用動態開辟的數組存儲）。
1.靜態順序表：使用定長數組存儲元素
#define MAX 10
typedef int SLDataType;//當存儲數據類型改變時，方便修改
typedef struct SeqList
{
SLDataType arr[MAX];//用來存儲數據
int size;//用來記錄數組中存儲有效數據元素的個數
}SL;
2.動態順序表：使用動態開辟的數組存儲
//動態順序表
typedef int SLDataType;//當存儲數據類型改變時，方便修改
typedef struct SeqList
{
SLDataType* arr;//指向動態開辟的數組
int size;//用來記錄數組中存儲有效數據元素的個數
int capacity;//用來記錄容量大小
}SL;
靜態順序表只適用于確定知道需要存多少數據的場景。靜態順序表的定長數組導致MAX定大了，空間開多了浪費，開少了不夠用。所以現實中基本都是用動態順序表，根據需要動態的分配空間大小，所以本文中使用動態開辟的順序表實現順序表的基本操作。
二、順序表的基本操作（接口實現）
1.初始化順序表
void SLInit(SL* ps)
{
assert(ps);
ps->arr = NULL;
ps->size = ps->capacity = 0;
}
初始化時設置其有效數據個數和容量都為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++;
}尾插就是在尾部插入數據，因為剛開始的時候沒有給數組分配空間，所以要考慮當沒有空間時要去申請空間，realloc函數是擴容函數，在指針為空的情況下作用和malloc相同，int NewCapacity =ps->capacity == 0 ? 4 : 2 * ps->capacity判斷當前容量大小并確定要開辟的空間大小。
SLDataType* tmp = (SLDataType*)realloc(ps->arr,sizeof(SLDataType) * NewCapacity)，用來在堆內存中開辟空間，realloc之后注意將其強制轉化成SLDataType*類型。當成功開辟空間之后賦給ps->arr，同時注意將NewCapacity賦給ps->capacity。
4.尾刪
void SLPopBack(SL* ps)
{
assert(ps);
//暴力的檢查
assert(ps->size > 0);//判斷ps->size是否大于0，當等于0時再刪的話ps->size就會變為-1，越界
//溫柔的檢查
//if (ps->size == 0)
//{
// return;
//}
ps->size--;
}
當ps->size等于0時直接返回，如果不返回，造成ps->size為負數，造成數組越界，當我們再次插入數據的時候可能會出現報錯，同時當越界時可能不會報錯，但是可能會在free時候報錯。所以要用assert(ps->size > 0)檢查ps->size大小，等于0時直接退出，并提示。
擴展：free時候報錯可能的錯誤原因有兩種，一是free時候指針不正確，可能是野指針，同時釋放的時候必須從起始位置釋放。二是越界時候free會報錯。當越界讀數組的時候基本不會被檢查出來報錯，但是改變它的值的時候就可能會報錯，是一種抽查行為，是在運行時檢查。
5.擴容
void SLCheckCapacity(SL* ps)
{
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->capacity = NewCapacity;
ps->arr = tmp;
}
}擴容函數，用于檢查數組空間大小是否適合繼續插入，當數組空間不足時進行擴容，定義此函數之后可以對上面尾插函數進行簡化，如下：
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;
//挪動數據
while (end > 0)
{
ps->arr[end] = ps->arr[end-1];
end--;
}
ps->arr[0] = x;
ps->size++;
}
利用擴容函數對其檢查，注意控制循環結束條件。
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--;
}
注意判斷當ps->size等于0時不能再進行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是數組下標，同時注意判斷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表示的是數組下標，有assert(pos >= 0)和assert(pos <= ps->size)兩個判斷條件之后不用再加assert(ps->size>0)，因為當ps->size等于0時，assert(pos <= ps->size)會報錯。
10.查找某個數的位置
int SLFind(SL* ps, SLDataType x)//返回類型為int,是數組下標
{
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是開始查找的位置
{
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>
//動態順序表
typedef int SLDataType;//當存儲數據類型改變時，方便修改
typedef struct SeqList
{
SLDataType* arr;//指向動態開辟的數組
int size;//用來記錄數組中存儲有效數據元素的個數
int capacity;//用來記錄容量大小
}SL;
void SLInit(SL* ps)//初始化順序表
{
assert(ps);
ps->arr = NULL;
ps->size = ps->capacity = 0;
}
void SLCheckCapacity(SL* ps)//檢查是否需要擴容
{
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->capacity = NewCapacity;
ps->arr = tmp;
}
}
void SLPushBack(SL* ps, SLDataType x)//尾插
{
SLCheckCapacity(ps);//檢查是否需要擴容
//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，當等于0時再刪的話ps->size就會變為-1，越界
//溫柔的檢查
if (ps->size == 0)
{
return;
}
ps->size--;
}
void SLPushFront(SL* ps, SLDataType x)//頭插
{
SLCheckCapacity(ps);
int end = ps->size;
//挪動數據
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)//查找某個數并返回下標
{
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開始查找某個數
{
assert(ps);
int i = 0;
for (i = begin; i < ps->size; i++)
{
if (ps->arr[i] == x)
return i;
}
return -1;
}
void menu()//菜單函數
{
printf("********************************\n");
printf("** 1.尾插 2.尾刪 **\n");
printf("** 3.頭插 4.頭刪 **\n");
printf("** 5.任意位置插入 **\n");
printf("** 6.任意位置刪除 **\n");
printf("** 7.查找某個數并返回其下標 **\n");
printf("** 8.刪除某個數 **\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結束：");
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結束：");
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("請輸入你想插入的位置和數值：");
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("請輸入你想要查找的數：");
scanf("%d", &ret);
int s = SLFind(&sl, ret);
printf("查找的數的數組下標為:%d！\n", s);
break;
case 8:
printf("請輸入你要刪除的數值：");
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
相關推薦
- 2023-07-03 Docker之容器導出為鏡像問題_docker
- 2022-11-18 阿里云kubernetes查找鏡像中jar包的方法(docker查看鏡像中的jar)_云其它
- 2022-12-31 Python中CSV文件的讀寫庫操作方法_python
- 2023-01-17 C#?wpf利用附加屬性實現界面上定義裝飾器_C#教程
- 2022-10-14 yum 倉庫管理 yum-config-manager
- 2022-02-04 防止點擊量頁面刷新增加的簡單處理方法
- 2022-11-17 Go語言學習教程之反射的示例詳解_Golang
- 2022-07-15 關于在Redis中使用Pipelining加速查詢的問題_Redis
- 最近更新
-
- 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加速