当前位置：首页 » 《随便一记》 » 正文

【数据结构与算法】：带你手搓顺序表（C/C++篇）

7 人参与  2024年04月26日 09:43  分类 : 《随便一记》  评论

点击全文阅读


文章目录

一、顺序表1.1 线性表 二、顺序表2.1 概念及结构2.2 实现方法1. 顺序表的初始化2. 顺序表的销毁3. 扩容4. 尾部插入/尾部删除5. 头部插入/头部删除6. 指定位置插入/删除7. 顺序表的查找8. 顺序表元素的索引9. 顺序表元素的修改10. SeqList.c完整代码

一、顺序表

1.1 线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
在这里插入图片描述

二、顺序表

在这里插入图片描述

2.1 概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表一般可以分为：

静态顺序表：使用定长数组存储。 
typedef int SLDataType;//便于类型的改动#define N 100// 静态顺序表typedef struct SeqList{SLDataType arr[N];  // 定长数组int size; //  有效数据个数}SL;

静态顺序表缺陷：空间给少了不够用，给多了造成空间浪费

动态顺序表：使用动态开辟的数组存储。 
typedef int SLDataType;//便于类型的改动// 动态顺序表typedef struct SeqList{SLDataType* arr;int size;  // 有效数据的个数int capacity;  // 空间大小}SL;
2.2 实现方法

首先要创建三个文件，创建一个SeqList.h的头文件用于函数的声明， SeqList.c用于函数的实现，test.c用于代码测试

SeqList.h文件

#pragma once#include<stdio.h>#include<stdlib.h>#include<assert.h>// 定义顺序表的结构typedef int SLDataType;  //便于类型的改动//#define N 100 静态顺序表//typedef struct SeqList//{//SLDataType arr[N];  // 定长数组//int size; //  有效数据个数//}SL;// 动态顺序表typedef struct SeqList{SLDataType* arr;int size;  // 有效数据的个数int capacity;  // 空间大小}SL;// 顺序表的初始化void SLInit(SL* ps);// 顺序表的销毁void SeqListDestory(SL* ps);// 顺序表的打印void SLPrint(SL s);// 扩容void SLCheckCapacity(SL* ps);// 顺序表的增删查改等接口函数// 尾插法void SeqListPopBack(SL* ps, SLDataType x);// 头插法void SLPushFront(SL* ps, SLDataType x);// 尾部删除void SLPopBack(SL* ps);// 头部删除void SLPopFront(SL* ps);// 指定位置插入void SLInsert(SL* ps, int pos, SLDataType x);// 指定位置删除void SLErase(SL* ps, int pos);// 顺序表的查找int SLFind(SL* ps, SLDataType x);// 顺序表元素的索引int SLIndex(SL* ps, int index);// 顺序表元素的修改void SLMod(SL* ps, int index, SLDataType x);

SeqList.c文件

1. 顺序表的初始化
// 顺序表的初始化void SLInit(SL* ps){ps->arr = NULL;ps->size = ps->capacity = 0;  // 开始空间为0 }

初始化的时候，可以选择申请原始空间大小，也可以选择不申请空间。

2. 顺序表的销毁
// 顺序表的销毁void SeqListDestory(SL* ps){if (ps->arr) // arr不为空，释放空间{free(ps->arr);}ps->arr = NULL;  // 置为空指针ps->size = ps->capacity = 0;}

代码测试：
test.c文件

#include"SeqList.h"void SLTest01() {SL sl;// 初始化SLInit(&sl);// 销毁SeqListDestory(&sl);}int main(){SLTest01();return 0;}

在这里插入图片描述

3. 扩容

注意：每次扩容新空间不能太大，也不能太小，太大容易造成空间浪费，太小则会导致频繁扩容而影响程序效率。

这里采用的是成倍扩容：

// 扩容void SLCheckCapacity(SL* ps){if (ps->capacity == ps->size){// 申请空间// 三目运算来判断原始空间是否为0int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;   // 如果为0，默认申请4个空间大小SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));if (tmp == NULL)  // 申请失败{perror("realloc");return 1;}// 申请成功ps->arr = tmp;ps->capacity = newCapacity;}}

在这里插入图片描述

4. 尾部插入/尾部删除
// 尾插法void SeqListPopBack(SL* ps, SLDataType x){assert(ps);  // 判断传入的是否是空指针 // 插入数据前先查看空间够不够SLCheckCapacity(ps);// ps->arr[ps->size] = x;// ++ps->size;  // 插入数据之后size要加1ps->arr[ps->size++] = x;}// 尾部删除void SLPopBack(SL* ps){assert(ps);  // 判断传入的是否是空指针assert(ps->size); // 确保数据域不为空--ps->size;  // 删除最后一个元素}

在这里插入图片描述

5. 头部插入/头部删除
// 头插法void SLPushFront(SL* ps, SLDataType x){assert(ps);  // 判断传入的是否是空指针// 先判断空间是否足够SLCheckCapacity(ps);// 先让顺序表中的元素整体往后挪动一位for (int i = ps->size; i > 0; i--){ps->arr[i] = ps->arr[i - 1]; // arr[1] = arr[0];}ps->arr[0] = x; // 将元素插在下标为0的位置ps->size++; // 插入数据后数据要加一}// 头部删除void SLPopFront(SL* ps){assert(ps);assert(ps->size);  // 确保数据域不为空// 顺序表中所有的元素往前挪一位for (int i = 0; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];}--ps->size;  // 删除后大小减一}

在这里插入图片描述

6. 指定位置插入/删除

1. 元素指定位置插入
顺序表的元素插入，就是指给定一个索引和一个元素，将这个元素插入到对应的索引位置上，这个位置以后的所有元素都要往后移动一个位置。
在这里插入图片描述
2. 元素指定位置删除
顺序表的元素删除，就是指给定一个索引，将这个索引上的元素删除，并且把这个索引位置以后的所有元素都往前移动一个位置。
在这里插入图片描述

// 指定位置插入void SLInsert(SL* ps, int pos, SLDataType x){assert(ps);  // 判断传入的是否是空指针assert(pos >= 0 && pos <= ps->size);// 先判断空间是否足够，不够就扩容SLCheckCapacity(ps);// 让pos及其之后的元素往后挪for (int i = ps->size; i > pos; i--){ps->arr[i] = ps->arr[i - 1];}// 插入数据ps->arr[pos] = x;// 插入元素后，数据域大小要加一ps->size++;}// 指定位置删除void SLErase(SL* ps, int pos){assert(ps);  // 判断传入的是否是空指针assert(pos >= 0 && pos < ps->size);// pos之后的元素往前挪for (int i = pos;i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];}// 删除元素后，数据域大小要减一ps->size--;}
7. 顺序表的查找

顺序表的元素查找，是指在顺序表中查找指定元素是否存在，如果存在则返回该元素的索引，否则返回-1。由于需要遍历整个顺序表进行元素对比，所以查找的时间复杂度为 O(n) 。
在这里插入图片描述
元素查找的顺序：
第1步、遍历整个顺序表，对顺序表中的每个元素，和指定元素进行比较，如果相等则返回当前的索引；
第2步、如果遍历完所有的顺序表元素，都没有找到相等的元素，则返回 -1；

// 顺序表的查找int SLFind(SL* ps, SLDataType x){assert(ps);  // 判断传入的是否是空指针for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x)  // 找到了return i;}// 未找到return -1;}
8. 顺序表元素的索引

顺序表的元素索引，是指给定一个索引值，通过下标访问，直接在顺序表中获取元素的值，时间复杂度 O(1)。
在这里插入图片描述

// 顺序表元素的索引int SLIndex(SL* ps, int index){assert(index >= 0 && index < ps->size);return ps->arr[index];}
9. 顺序表元素的修改

顺序表的元素修改是指将顺序表中指定位置的元素更新为新的值。
在这里插入图片描述

// 顺序表元素的修改void SLMod(SL* ps, int index, SLDataType x){assert(ps); // 判断传入的是否是空指针assert(index >= 0 && index < ps->size);ps->arr[index] = x;  // 指定下标元素修改}
10. SeqList.c完整代码
#include"SeqList.h"// 顺序表的初始化void SLInit(SL* ps){ps->arr = NULL;ps->size = ps->capacity = 0;  // 开始空间为0 }// 顺序表的销毁void SeqListDestory(SL* ps){if (ps->arr) {free(ps->arr);}ps->arr = NULL;ps->size = ps->capacity = 0;}// 打印void SLPrint(SL s){for (int i = 0; i < s.size; i++){printf("%d ", s.arr[i]);}printf("\n");}// 扩容void SLCheckCapacity(SL* ps){if (ps->capacity == ps->size){// 申请空间// 三目运算来判断原始空间是否为0int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;   // 如果为0，默认申请4个空间大小SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));if (tmp == NULL)  // 申请失败{perror("realloc");return 1;}// 申请成功ps->arr = tmp;ps->capacity = newCapacity;}}// 尾插法void SeqListPopBack(SL* ps, SLDataType x){assert(ps);  // 判断传入的是否是空指针 // 插入数据前先查看空间够不够SLCheckCapacity(ps);// ps->arr[ps->size] = x;// ++ps->size;  // 插入数据之后size要加1ps->arr[ps->size++] = x;}// 头插法void SLPushFront(SL* ps, SLDataType x){assert(ps);  // 判断传入的是否是空指针// 先判断空间是否足够SLCheckCapacity(ps);// 先让顺序表中的元素整体往后挪动一位for (int i = ps->size; i > 0; i--){ps->arr[i] = ps->arr[i - 1]; // arr[1] = arr[0];}ps->arr[0] = x; // 将元素插在下标为0的位置ps->size++; // 插入数据后数据要加一}// 尾部删除void SLPopBack(SL* ps){assert(ps);  // 判断传入的是否是空指针assert(ps->size); // 确保数据域不为空--ps->size;  // 删除最后一个元素}// 头部删除void SLPopFront(SL* ps){assert(ps);assert(ps->size);  // 确保数据域不为空// 顺序表中所有的元素往前挪一位for (int i = 0; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];}--ps->size;  // 删除后大小减一}// 指定位置插入void SLInsert(SL* ps, int pos, SLDataType x){assert(ps);  // 判断传入的是否是空指针assert(pos >= 0 && pos <= ps->size);// 先判断空间是否足够，不够就扩容SLCheckCapacity(ps);// 让pos及其之后的元素往后挪for (int i = ps->size; i > pos; i--){ps->arr[i] = ps->arr[i - 1];}// 插入数据ps->arr[pos] = x;// 插入元素后，数据域大小要加一ps->size++;}// 指定位置删除void SLErase(SL* ps, int pos){assert(ps);  // 判断传入的是否是空指针assert(pos >= 0 && pos < ps->size);// pos之后的元素往前挪for (int i = pos;i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];}// 删除元素后，数据域大小要减一ps->size--;}// 顺序表的查找int SLFind(SL* ps, SLDataType x){assert(ps);  // 判断传入的是否是空指针for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x)  // 找到了return i;}// 未找到return -1;}// 顺序表元素的索引int SLIndex(SL* ps, int index){assert(index >= 0 && index < ps->size);return ps->arr[index];}// 顺序表元素的修改void SLMod(SL* ps, int index, SLDataType x){assert(ps); // 判断传入的是否是空指针assert(index >= 0 && index < ps->size);ps->arr[index] = x;  // 指定下标元素修改}

点击全文阅读


本文链接：http://zhangshiyu.com/post/100342.html

<< 上一篇 下一篇 >>

  • 评论（0）
  • 赞助本站

◎欢迎参与讨论，请在这里发表您的看法、交流您的观点。

最新文章

  • 我有最强修炼体夜天涯天翔秦天翔岑红尘，我有最强修炼体在线无弹窗阅读
  • 《女皇在上，国师心不良》小说章节列表免费试读，欧阳庄静欧阳妮妮诸葛瑾小说在线阅读
  • 孟暖孟瑾沈逸枫小说在线全文免费阅读（娇妻不乖：将军家的小祖宗无弹窗无删减）
  • 男女主人公苏晚晴阎洛生阎爹地小说龙凤双宝：爹地，快追你媳妇全文免费阅读
  • 完整版《偏执大佬的病娇宝贝又飒又撩》全文阅读
  • 我，古剑宗，签到一百年！诸葛小力诸葛唐绝王富贵小说免费阅读
  • 主角叶君豪叶承乾小说少年相腰师免费阅读
  • 快穿：又被病娇男主撩到了主角演员苏浪小说完整版全文在线阅读
  • 豪门龙婿全章节免费在线阅读，福伯陈阳宋雅欣完结版
  • 已完结小说《禁入之地：荒漠鸣沙》全文免费阅读
  • 完整版《武道争锋》免费阅读
  • 见证奇迹免费阅读，见证奇迹全文在线阅读

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1