网站导航
> 文章列表 > 【数据结构】线性表之——“顺序表”

【数据结构】线性表之——“顺序表”

网友: 文章列表 2024-03-22 01:31:03

【数据结构】线性表之——“顺序表”

文章目录

  • 前言
  • 顺序表主体结构
  • 顺序表操作函数介绍
  • 顺序表操作函数实现
    • 实现顺序：
    • 顺序表的初始化：
    • 顺序表插入函数：
      • 头插
      • 尾插
      • 指定位置插入
    • 顺序表打印函数
    • 查找顺序表数据
    • 顺序表删除函数
      • 头删
      • 尾删
      • 指定位置删除
    • 修改顺序表
    • 销毁顺序表
  • 文件分类
    • test.c
    • SeqList.c
    • SeqList.h
  • 撒花

前言

  • 为什么有顺序表？由于数组定义之后不能扩充，我们需要一种更方便的结构来装载数据，顺序表诞生了。
  1. 顺序表是线性表的一种，线性表的存储都是形成一条线的，顺序表不仅仅在逻辑上是用一条线链接，在内存中也是连续的一块空间，因此可以进行下标随机访问。
  2. 顺序表不同于数组，顺序表在空间不够的情况下可以选择进行扩充。
  3. 顺序表不同于数组，顺序表开辟在堆空间中，不用担心栈空间不够用。
  4. 相对麻烦的就是，先对顺序表进行操作必须要自己实现增删改查等函数。
  5. 如果学会了顺序表可以试着自主完成通讯录小程序⭐

PS:需要源码直接通过目录跳转到最后

顺序表主体结构

默认大小与扩容大小还有类型都可以是任意大小或类型

#define SLDataType int
#define DEFAULT_SZ 5			//默认大小
#define DEFAULT_INC 3			//默认扩容大小typedef struct SeqList
{SLDataType* data;int sz;int capable;
}SeqList;

【数据结构】线性表之——“顺序表”

用define定义数据可以方便修改

顺序表操作函数介绍

  1. void SLInit(SeqList* SL); 顺序表初始化
  2. void SLprint(SeqList* SL); 打印顺序表
  3. void SLPushFront(SeqList* SL, SLDataType x); 顺序表投插
  4. void SLPushBack(SeqList* SL, SLDataType x); 顺序表尾插
  5. void SLPopFront(SeqList* SL); 顺序表头删
  6. void SLPopBack(SeqList* SL); 顺序表尾删
  7. void SLInsert(SeqList* SL, int pos, SLDataType x); ~指定位置插入
  8. void SLEarse(SeqList* SL, int pos); 指定位置删除
  9. int SLFind(SeqList* SL, SLDataType x); 查找指定数据下标
  10. void SLModify(SeqList* SL, int pos, SLDataType x); 修改指定位置数据
  11. void SLDestroy(SeqList* SL); 清楚数据包

为了代码方便阅读，讲顺序表操作函数全部放在Seqlist.c文件中，将头文件放在SeqList.h，测试文件test.c 🌞

顺序表操作函数实现

实现顺序：

为了方便调试，建议每写完1-2个函数就进行测试，初始化之后，首先实现print函数可以方便我们进行调试，建议按照顺序，插入-》打印-》查找-》删除-》销毁顺序表函数。

顺序表的初始化：

void SLInit(SeqList* SL)
{assert(SL);				//assert防止传进来的指针为空，进行断言SL->capable = DEFAULT_SZ;SL->sz = 0;int* ptr = malloc(sizeof(int) * DEFAULT_SZ);	//为顺序表开辟一段空间if (ptr == NULL)								//预防开辟失败进行判断{perror("malloc:");}SL->data = ptr;printf("初始化成功\\n");
}

必须先进性初始化，给顺序表开辟一个堆空间，并对其默认长度与默认最大长度进行初始化。

顺序表插入函数：

头插

头插从第一个位置插入，其余函数按顺序向后移动一格，

  • 既然有插入就一定会有空间不够用的问题，这里用到检查空间是否够用的一个函数
void CheckSL(SeqList* SL)
{assert(SL);	//assert防止传进来的指针为空，进行断言if (SL->sz == SL->capable)		//如果当前大小等于当前最大大小那么进行扩容{int* ptr = NULL;ptr = (int*)realloc(SL->data, sizeof(int) * (SL->capable + DEFAULT_INC));if (ptr == NULL){perror("check:realloc:");}SL->data = ptr;SL->capable += DEFAULT_INC;printf("扩容成功\\n");}
}

头插函数

  • 将所有数据向后移动，注意要从后面开始移动，不然数据会被覆盖掉

在这里插入图片描述

void SLPushFront(SeqList* SL, SLDataType x)
{assert(SL);	//assert防止传进来的指针为空，进行断言CheckSL(SL);int end = SL->sz - 1;while (end >= 0)		//将所有数据向后移动，注意要从后面开始移动，不然数据会被覆盖掉{SL->data[end + 1] = SL->data[end];end--;}SL->data[0] = x;		//所有数据都向后移动之后进行头插SL->sz++;				//当前大小+1
}

尾插

从最后进行插入数据

  • 尾插也会用到检查空间是否够用的函数，这里不重复了
void SLPushBack(SeqList* SL,SLDataType x)
{assert(SL);	//assert防止传进来的指针为空，进行断言CheckSL(SL);			//判断空间是否够用，够用直接将数据放在尾部即可SL->data[SL->sz] = x;SL->sz++;				//插入之后当前大小+1
}

指定位置插入

  • 只要有插入，就要检查空间是否够用
void SLInsert(SeqList* SL,int pos,SLDataType x)
{assert(SL);	//assert防止传进来的指针为空，进行断言assert(pos >= 0 && pos < SL->sz);CheckSL(SL);int end = SL->sz - 1;while (end >=pos-1)			//讲数据从后向后移动，避免被覆盖{SL->data[end + 1] = SL->data[end];end--;}SL->data[pos-1] = x;SL->sz++;			//插入之后当前大小+1
}

顺序表打印函数

写完插入立马写打印，方便进行调试

void SLprint(SeqList* SL)
{assert(SL);	//assert防止传进来的指针为空，进行断言for (int i = 0; i < SL->sz; i++){printf("%d ", SL->data[i]);}printf("\\n");
}

查找顺序表数据

int SLFind(SeqList* SL, SLDataType x)
{assert(SL);	//assert防止传进来的指针为空，进行断言for (int i = 0; i < SL->sz; i++){if (SL->data[i] == x){return i;}}return -1;
}

顺序表删除函数

头删

从头部删除数据，删除之后后面的数据依次向前移动一位，要从前往后移动，不然会被覆盖（同头插）

void SLPopFront(SeqList* SL)
{assert(SL);	//assert防止传进来的指针为空，进行断言if (SL->sz <= 0){printf("表为空，无需删除");return;}int start = 0;while (start < SL->sz - 1){SL->data[start] = SL->data[start + 1];start++;}SL->sz--;
}

尾删

void SLPopBack(SeqList* SL)
{assert(SL);	//assert防止传进来的指针为空，进行断言if (SL->sz <= 0){printf("表为空，无需删除");return;}SL->sz--;
}

指定位置删除

后面的数据依次向前移动

void SLEarse(SeqList* SL,int pos)
{assert(SL);	//assert防止传进来的指针为空，进行断言assert(pos >= 0 && pos < SL->sz);int start = pos-1;while (start < SL->sz - 1){SL->data[start] = SL->data[start + 1];start++;}SL->sz--;
}

修改顺序表

void SLModify(SeqList* SL, int pos, SLDataType x)
{assert(SL);	//assert防止传进来的指针为空，进行断言assert(pos >= 0 && pos < SL->sz);SL->data[pos - 1] = x;
}

销毁顺序表

void SLDestroy(SeqList* SL)
{assert(SL);	//assert防止传进来的指针为空，进行断言free(SL->data);//释放堆空间数据SL->data = NULL;//将指针置空预防野指针SL->sz = 0;SL->capable = 0;
}

文件分类

🌞🌞为了使代码更有阅读性，我们不建议把所有函数写在一个文件里，所以这里分成三个文件，模块化管理

test.c

测试文件

#include "SeqList.h"void test(SeqList* SL)
{SLPushBack(SL, 10);SLPushBack(SL, 11);SLPushBack(SL, 11);SLPushBack(SL, 11);SLPushBack(SL, 11);SLPushBack(SL, 11);SLPushBack(SL, 11);SLPushBack(SL, 11);SLPushBack(SL, 19);SLprint(SL);SLPushFront(SL, 12);SLPushFront(SL, 13);SLPushFront(SL, 14);SLprint(SL);SLPopBack(SL);SLprint(SL);SLPopFront(SL);SLprint(SL);SLInsert(SL, 5, 99);SLprint(SL);SLModify(SL, 5, 22);SLprint(SL);//SLEarse(SL, 5);//SLprint(SL);SLFind(SL,5);SLDestroy(SL);}
int main()
{SeqList SL;SLInit(&SL);test(&SL);
}

SeqList.c

i将所有函数封装在此文件下

#include "SeqList.h"void SLInit(SeqList* SL)
{assert(SL);SL->capable = DEFAULT_SZ;SL->sz = 0;int* ptr = malloc(sizeof(int) * DEFAULT_SZ);if (ptr == NULL){perror("malloc:");}SL->data = ptr;printf("初始化成功\\n");
}void SLprint(SeqList* SL)
{assert(SL);for (int i = 0; i < SL->sz; i++){printf("%d ", SL->data[i]);}printf("\\n");
}void CheckSL(SeqList* SL)
{assert(SL);if (SL->sz == SL->capable){int* ptr = NULL;ptr = (int*)realloc(SL->data, sizeof(int) * (SL->capable + DEFAULT_INC));if (ptr == NULL){perror("check:realloc:");}SL->data = ptr;SL->capable += DEFAULT_INC;printf("扩容成功\\n");}
}void SLPushBack(SeqList* SL,SLDataType x)
{assert(SL);CheckSL(SL);SL->data[SL->sz] = x;SL->sz++;
}void SLPushFront(SeqList* SL, SLDataType x)
{assert(SL);CheckSL(SL);int end = SL->sz - 1;while (end >= 0){SL->data[end + 1] = SL->data[end];end--;}SL->data[0] = x;SL->sz++;
}void SLPopBack(SeqList* SL)
{assert(SL);if (SL->sz <= 0){printf("表为空，无需删除");return;}SL->sz--;
}void SLPopFront(SeqList* SL)
{assert(SL);if (SL->sz <= 0){printf("表为空，无需删除");return;}int start = 0;while (start < SL->sz - 1){SL->data[start] = SL->data[start + 1];start++;}SL->sz--;
}void SLInsert(SeqList* SL,int pos,SLDataType x)
{assert(SL);assert(pos >= 0 && pos < SL->sz);int end = SL->sz - 1;while (end >=pos-1){SL->data[end + 1] = SL->data[end];end--;}SL->data[pos-1] = x;SL->sz++;
}void SLEarse(SeqList* SL,int pos)
{assert(SL);assert(pos >= 0 && pos < SL->sz);int start = pos-1;while (start < SL->sz - 1){SL->data[start] = SL->data[start + 1];start++;}SL->sz--;
}void SLDestroy(SeqList* SL)
{assert(SL);free(SL->data);SL->data = NULL;SL->sz = 0;SL->capable = 0;
}int SLFind(SeqList* SL, SLDataType x)
{assert(SL);for (int i = 0; i < SL->sz; i++){if (SL->data[i] == x){return i;}}return -1;
}void SLModify(SeqList* SL, int pos, SLDataType x)
{assert(SL);assert(pos >= 0 && pos < SL->sz);SL->data[pos - 1] = x;
}

SeqList.h

将主程序所需要的函数全部在头文件中声明，增加代码阅读性

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>#define SLDataType int
#define DEFAULT_SZ 5
#define DEFAULT_INC 3typedef struct SeqList
{SLDataType* data;int sz;int capable;
}SeqList;void SLInit(SeqList* SL);
void SLprint(SeqList* SL);
void SLPushFront(SeqList* SL, SLDataType x);
void SLPushBack(SeqList* SL, SLDataType x);
void SLPopFront(SeqList* SL);
void SLPopBack(SeqList* SL);
void SLInsert(SeqList* SL, int pos, SLDataType x);
void SLEarse(SeqList* SL, int pos);
int SLFind(SeqList* SL, SLDataType x);
void SLModify(SeqList* SL, int pos, SLDataType x);
void SLDestroy(SeqList* SL);

撒花

这就是实现顺序表的全部内容了，创作不易，还请各位小伙伴多多点赞👍关注收藏⭐，以后也会更新各种关于c语言，数据结构的博客，撒花！

网络标签：

相关问题