網站首頁 編程語言 正文
順序表的基本操作
順序表是用一段物理地址連續的存儲單元依次存儲數據元素的線性結構，一般情況下采用數組存儲。
在數組上完成數據的增刪查改等基本操作。
初始化
初始化結構體，開辟空間
void SeqListInit(SeqList* ps, size_t inite_capicity)
{
assert(ps);
ps->arr = (SLDataType*)malloc(sizeof(SLDataType) * inite_capicity);
if (NULL == ps->arr)
{
exit(1);
}
ps->capicity = inite_capicity;
ps->size = 0;
}
清空
因為動態內存申請用完空間必須釋放，所以存在這個函數
void SeqListDestory(SeqList* ps)
{
assert(ps);
if (ps->arr)
{
free(ps->arr);
ps->arr = NULL;
ps->capicity = 0;
ps->size = 0;
}
}
打印
打印順序表內容
void SeqListPrint(SeqList* ps)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
printf("%d ", ps->arr[i]);
}
printf("\n");
}
擴容
增加順序表的容量
static void SeqListRealloc(SeqList* ps)
{
SLDataType* temp = ps->arr;
temp = (SLDataType*)realloc(ps->arr, ps->capicity * 2);
if (temp != NULL)
{
// 若申請則將擴容后的地址賦給ps->size
// 這樣做的目的是防止空間申請失敗后原有空間的地址無法找回
ps->arr = temp;
}
ps->capicity *= 2;
}
尾插法
尾插法只需要將元素放入最會一個位置，并對size加上1即可
void SeqListPushBack(SeqList* ps, SLDataType data)
{
assert(ps);
//先判斷是否已滿，如果已滿則需要擴容
if (ps->size == ps->capicity)
{
SeqListRealloc( ps);//調用擴容函數
}
ps->arr[ps->size] = data;//將數據放到順序表的結尾
ps->size++;//有效元素增加一個
}
判空
插入操作前都要判斷順序表是否已滿
static int IsSeqListEmpty(SeqList* ps)
{
assert(ps);
if (0==ps->size)
{
return 1;
}
else
{
return 0;
}
}
尾刪法
尾刪只需要將實際元素個數減一即可
void SeqListPopBack(SeqList* ps)
{
assert(ps);
if (!IsSeqListEmpty(ps))
{
ps->size--;
}
}
頭插法
順序表所有元素向后移動一個單位，在第一個位置插入數據
void SeqListPushFront(SeqList* ps, SLDataType data)
{
assert(ps);
if (ps->size == ps->capicity)
{
SeqListRealloc(ps);//若順序表空間已滿調用擴容函數
}
//***將ps->size強轉成int類型，否則計算時會發生類型提升***
for (int i = (int)ps->size - 1; i >= 0; i--)
{
ps->arr[i + 1] = ps->arr[i];//所有元素向后移動一個單位
}
ps->arr[0] = data;//將元素插入順序表頭部
ps->size ++;//元素個數加1
}
頭刪法
將第一個元素以后的所有元素向前移動一個單位
void SeqListPopFront(SeqList* ps)
{
assert(ps);
if (!IsSeqListEmpty(ps))
{
for (int i = 0; i < (int)ps->size - 1; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
ps->size--;//元素個數減1
}
}
查詢
查詢表中是否有某一元素，若存在則返回其下標
int SeqListFind(SeqList* ps, SLDataType data)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
if (ps->arr[i] == data)
{
return i;
}
}
return -1;//未找到返回-1
}
任意位置插入
函數的第二個參數為要插入的位置，第三個參數為要插入的數據，與頭插原理相似
void SeqListInsert(SeqList* ps, size_t pos, SLDataType data)
{
assert(ps);
if (ps->size == ps->capicity)
{
SeqListRealloc(ps);//若順序表空間已滿調用擴容函數
}
for (int i = (int)ps->size - 1; i >= pos; i--)
{
ps->arr[i + 1] = ps->arr[i];//pos位置及其以后所有元素向后移動一個單位
}
ps->arr[pos] = data;//將元素插入順序表頭部
ps->size++;//元素個數加1
}
任意位置刪除
從某一要刪除的元素位置開始，后面所有元素向前移動一個單位
void SeqListErase(SeqList* ps, size_t pos)
{
assert(ps);
if (!IsSeqListEmpty(ps))
{
for (int i = (int)pos; i < (int)ps->size - 1; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
ps->size--;//元素個數減1
}
}
完整代碼
下面給出線性表操作的完整代碼，代碼的注釋對每步的作用有詳細的介紹：
- 其中work.h頭文件主要完成包含頭文件和結構體、各個函數的聲明
- main.c源文件是程序的入口，并在這里實現測試用例，具體使用時，結構體變量在main.c中定義
- work.c源文件是各個操作的具體函數的實現
work.h
#pragma once
#include<stdio.h>
#include<windows.h>
#include<stdlib.h>
#include<assert.h>
#define MAXSIZE 50
typedef int SLDataType;
typedef struct SeqList
{
SLDataType* arr;//起始地址
size_t capicity;//容量
size_t size;//有效數據
}SeqList;
//下面這些都是函數聲明
void SeqListInit(SeqList* ps,size_t inite_capicity);//初始化
void SeqListDestory(SeqList* ps);//空間釋放
void SeqListPushBack(SeqList* ps, SLDataType data);//尾插
void SeqListPopBack(SeqList* ps);//尾刪
void SeqListPushFront(SeqList* ps,SLDataType data);//頭插法
void SeqListPopFront(SeqList* ps);//頭刪法
int SeqListFind(SeqList* ps, SLDataType data);//查找
void SeqListInsert(SeqList* ps, size_t pos, SLDataType x);//任意位置插入
void SeqListErase(SeqList* ps, size_t pos);//任意位置刪除
void SeqListPrint(SeqList* ps);//順序表打印
main.c
#include"work.h"
//測試用例
void TestSeqList()
{
SeqList s;
SeqList* ps = &s;
SeqListInit(ps, MAXSIZE);
SeqListPushBack(ps, 1);//尾插法增加5個元素
SeqListPushBack(ps, 2);
SeqListPushBack(ps, 3);
SeqListPushBack(ps, 4);
SeqListPushBack(ps, 5);
SeqListPrint(ps);//打印輸出
SeqListPopBack(ps);//尾刪法刪除一個元素
SeqListPrint(ps);//打印輸出
SeqListPushFront(ps, 0); //頭插法增加一個元素
SeqListPrint(ps); //打印輸出
SeqListPopFront(ps);//頭刪法刪除一個元素
SeqListPrint(ps); //打印輸出
//調用查找函數并返回下標，若不存在返回值為-1
printf("%d\n", SeqListFind(ps, 2));
printf("%d\n", SeqListFind(ps, 10));
SeqListInsert(ps, 4, 5);//第4個位置插入
SeqListPrint(ps);
SeqListErase(ps, 5);//第5個位置刪除
SeqListPrint(ps);
SeqListDestory(ps);
}
int main()
{
TestSeqList();//調用測試函數
system("pause");
return 0;
}
work.c
#include"work.h"
//初始化函數
void SeqListInit(SeqList* ps, size_t inite_capicity)
{
assert(ps);
ps->arr = (SLDataType*)malloc(sizeof(SLDataType) * inite_capicity);
if (NULL == ps->arr)
{
exit(1);
}
ps->capicity = inite_capicity;
ps->size = 0;
}
//堆空間釋放釋放函數
void SeqListDestory(SeqList* ps)
{
assert(ps);
if (ps->arr)
{
free(ps->arr);
ps->arr = NULL;
ps->capicity = 0;
ps->size = 0;
}
}
//順序表打印函數
void SeqListPrint(SeqList* ps)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
printf("%d ", ps->arr[i]);
}
printf("\n");
}
//擴容函數
static void SeqListRealloc(SeqList* ps)
{
SLDataType* temp = ps->arr;
temp = (SLDataType*)realloc(ps->arr, ps->capicity * 2);
if (temp != NULL)
{
// 若申請則將擴容后的地址賦給ps->size
// 這樣做的目的是防止空間申請失敗后原有空間的地址無法找回
ps->arr = temp;
}
ps->capicity *= 2;
}
//尾插法
void SeqListPushBack(SeqList* ps, SLDataType data)
{
assert(ps);
//先判斷是否已滿，如果已滿則需要擴容
if (ps->size == ps->capicity)
{
SeqListRealloc( ps);//調用擴容函數
}
ps->arr[ps->size] = data;//將數據放到順序表的結尾
ps->size++;//有效元素增加一個
}
//判空函數
static int IsSeqListEmpty(SeqList* ps)
{
assert(ps);
if (0==ps->size)
{
return 1;
}
else
{
return 0;
}
}
//尾刪法
void SeqListPopBack(SeqList* ps)
{
assert(ps);
if (!IsSeqListEmpty(ps))
{
ps->size--;//尾刪只需要將實際元素個數減一即可
}
}
//頭插法
void SeqListPushFront(SeqList* ps, SLDataType data)
{
assert(ps);
if (ps->size == ps->capicity)
{
SeqListRealloc(ps);//若順序表空間已滿調用擴容函數
}
//***將ps->size強轉成int類型，否則計算時會發生類型提升***
for (int i = (int)ps->size - 1; i >= 0; i--)
{
ps->arr[i + 1] = ps->arr[i];//所有元素向后移動一個單位
}
ps->arr[0] = data;//將元素插入順序表頭部
ps->size ++;//元素個數加1
}
//頭刪法
void SeqListPopFront(SeqList* ps)
{
assert(ps);
if (!IsSeqListEmpty(ps))
{
for (int i = 0; i < (int)ps->size - 1; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
ps->size--;//元素個數減1
}
}
//查詢
int SeqListFind(SeqList* ps, SLDataType data)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
if (ps->arr[i] == data)
{
return i;
}
}
return -1;//未找到返回-1
}
//任意位置插入
void SeqListInsert(SeqList* ps, size_t pos, SLDataType data)
{
assert(ps);
if (ps->size == ps->capicity)
{
SeqListRealloc(ps);//若順序表空間已滿調用擴容函數
}
for (int i = (int)ps->size - 1; i >= pos; i--)
{
ps->arr[i + 1] = ps->arr[i];//pos位置及其以后所有元素向后移動一個單位
}
ps->arr[pos] = data;//將元素插入順序表頭部
ps->size++;//元素個數加1
}
//任意位置刪除
void SeqListErase(SeqList* ps, size_t pos)
{
assert(ps);
if (!IsSeqListEmpty(ps))
{
for (int i = (int)pos; i < (int)ps->size - 1; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
ps->size--;//元素個數減1
}
}
總結
原文鏈接：https://blog.csdn.net/qq_44631587/article/details/121413843
相關推薦
- 2022-10-26 Golang?基于flag庫實現一個簡單命令行工具_Golang
- 2022-10-24 IOS開發Swift?與?OC相互調用詳解_IOS
- 2022-03-17 C#實現多文件打包壓縮(.Net?Core)_C#教程
- 2023-05-06 C++?lambda函數詳解_C 語言
- 2022-07-14 python修改包導入時搜索路徑的方法_python
- 2024-07-18 MybatisPlus優雅實現加密？
- 2022-07-10 jQuery表格添加數據并Ajax提交數據
- 2022-07-10 TypeError: Cannot read property ‘forceUpdate‘ of u
- 最近更新
-
- 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加速