C语言实现顺序表--数据结构

news/2024/11/26 11:54:41/

在这里插入图片描述

  • 魔王的介绍：😶‍🌫️一名双非本科大一小白。
  • 魔王的目标：🤯努力赶上周围卷王的脚步。
  • 魔王的主页：🔥🔥🔥大魔王.🔥🔥🔥
    请添加图片描述
    ❤️‍🔥大魔王与你分享：“提亚马特都有失去主动的一天，更何况是满身破绽的你呢”。

文章目录

  • 一、前言
  • 二、顺序表实现
    • 1、创建结构体
    • 2、初始化
    • 3、销毁
    • 4、检查
    • 5、打印
    • 6、尾插
    • 7、尾删
    • 8、头插
    • 9、头删
    • 10、查找
    • 11、插入
    • 12、删除
    • 13、注意事项
  • 三、总代码
    • SeqList.h
    • SeqList.c
    • Test.c
  • 四、总结

一、前言

顺序表是线性表的一种，它就如同字面意思一般，在内存是按顺序存储的，如果你还不理解，那你想想你一直用的数组，它就是顺序表的原理，在内存中连续存放的，因此地址也是连续的。如图：在这里插入图片描述

二、顺序表实现

1、创建结构体

虽然顺序表只是单纯的一个数组，但是要知道，我们在使用顺序表时，需要增删查改这些操作，那么对于在内存中连续存贮的顺序表，我们怎样快速找到它呢，我们怎样确定这个顺序表有几个元素呢，那就需要定义一个变量来记录这个顺序表的元素。至于为什么让他们俩连起来弄在结构体里，那当然是因为这样可以避免传一堆参数，没弄好自己就蒙了，命名了一堆的变量名，所以我们让他们放在结构体里，方便一起操作。

当然，因为要实现的顺序表是动态的，也就是会自己扩容，避免空间不够或者空间浪费，所以我们在结构体里还需要弄一个新的变量，那就是记录当前顺序表的大小。当元素个数与顺序表的大小相等时，我们就需要扩容了。

代码：

#define InitCapacity 5typedef int SLDateType;typedef struct SeqList
{SLDateType* a;int size;int capacity;
}SL;

2、初始化

创建完这个结构体，我们需要给结构体里的元素初始化，封装成一个函数，在给数组指针初始化时，我们给他一个初始大小，等以后不够再自动扩容。

代码：

void SLInit(SL* pc)
{assert(pc);pc->a = (SLDateType*)malloc(sizeof(SLDateType) * InitCapacity);pc->size = 0;pc->capacity = InitCapacity;
}

3、销毁

因为是动态开辟的，所以内存是再堆区的，当我们用完如果不销毁，那么只能等程序结束才会自动销毁，如果没结束不会自动释放，所以当我们用完后需要手动释放。

代码：

void SLDestroy(SL* pc)
{assert(pc);free(pc->a);pc->size = 0;pc->capacity = 0;pc->a = NULL;
}

4、检查

现在我们来实现刚才一直说的扩容，当顺序表容量满的时候，我们需要扩容，那么怎样检查又怎样扩容呢，请看下面代码实现。

代码：

void SLCheck(SL* pc)
{assert(pc);if (pc->capacity == pc->size){int* str = realloc(pc->a, pc->capacity * sizeof(SLDateType) * 2);if (str == NULL){perror("realloc fail");return;//返回之后的流程是什么:会打印出开辟失败的一行信息，但接下来的步骤还会进行，比如越界什么的，强行执行后面的操作。}else{pc->a = str;str = NULL;}pc->capacity = pc->capacity * 2;}
}

注意在扩容时，需要先用一个临时指针操作，否则如果开辟失败，返回一个空指针，空指针的值赋给了原本的指针，那么这个数组的地址就找不到了，那么损失就大了。所以当开辟成功时，再把这个临时指针的值赋给新指针，并把临时指针置空，防止野指针。

5、打印

为了验证等会下面的增删查改，我们先实现一个打印函数，然后等写好功能后来验证。

代码：

void SLPrint(SL* pc)
{assert(pc);for (int i = 0; i < pc->size; i++){printf("%d ", pc->a[i]);}
}

6、尾插

首先来实现一下尾插，在尾插时，第一步当然是判断顺序表是否满了，如果，满了我们还插入内容，那就越界访问了。这一步弄完，我们直接插入值就行了，插入到下标为元素个数的位置即可，因为数组下标是从0开始的。最后就是让我们结构体里统计个数的那个变量加一就行了。

代码：

void SLPushBack(SL* pc, SLDateType x)
{assert(pc);SLCheck(pc);pc->a[pc->size] = x;pc->size++;
}

7、尾删

尾删特别简单，先判断该顺序表是否有内容，如果有，那么直接让个数减一就ok了，其他不用管，因为打印是根据个数打印的。

代码：

void SLPopBack(SL* pc)
{assert(pc);assert(pc->size);pc->size--;
}

8、头插

头插比较麻烦，说的麻烦是效率麻烦，因为需要逐个遍历，全部都向后移动一位，然后让size+1。实现并不难，因为顺序表整体都是简单的。

代码：

void SLPushFront(SL* pc, SLDateType x)
{assert(pc);SLCheck(pc);for (int end = pc->size - 1; end >= 0; end--){pc->a[end + 1] = pc->a[end];}pc->a[0] = x;pc->size++;
}

9、头删

头删和头插一样，都是需要逐个遍历，这个是都向前移动一位，然后让size-1。

代码：

void SLPopFront(SL* pc)
{assert(pc);assert(pc->size);for (int begin = 1; begin <= pc->size - 1; begin++){pc->a[begin - 1] = pc->a[begin];}pc->size--;
}

10、查找

查找也和简单，就是从第一个元素逐个遍历，然后返回找到的位置下标，如果没有找到，就返回-1。

代码：

int SLFind(SL* pc, SLDateType x)
{assert(pc);assert(pc->size);for (int i = 0; i < pc->size; i++){if (x == pc->a[i]){return i;}}return -1;
}

11、插入

实现了头插尾插， 那如果我们想从内部插入呢，其实原理是一样的，让某个地方之后的都向后移动一位，当然这之前需要判断是否满了。最后size+1。

代码：

void SLInsert(SL* pc, int pos, SLDateType x)
{assert(pc);int end = pc->size - 1;if (pos >= 0 && pos <= pc->size){SLCheck(pc);while (end >= pos){pc->a[end + 1] = pc->a[end];end--;}pc->a[pos] = x;pc->size++;}
}

12、删除

实现了头删和尾删，如果我们想从内部某个位置删除，就需要再写一个代码了，原理也是一样的，先判断有没有元素，然后让从这个位置之后的都向前进一。最后size-1。

代码：

void SLErase(SL* pc, int pos)
{assert(pc);assert(pc->size);//可有可无int begin = pos + 1;if (pos >= 0 && pos < pc->size){while (begin < pc->size){pc->a[begin - 1] = pc->a[begin];begin++;}pc->size--;}
}

13、注意事项

  • 我们在进行插入时，挪动元素位置需要先挪后边再挪前边，否则会覆盖原数组的值，移动后所对应的就不是原来的值了。
  • 相同的，在进行删除时，也需要考虑这方面，不过跟插入是相反的，我们需要先挪动前边的，不然会覆盖原数组的值，移动后就不是原来数组的值了。

三、总代码

SeqList.h

SeqList.h

#pragma once#include <stdio.h>
#include <assert.h>
#include <stdlib.h>#define InitCapacity 5typedef int SLDateType;typedef struct SeqList
{SLDateType* a;int size;int capacity;
}SL;//初始化
void SLInit(SL* pc);//结束，销毁
void SLDestroy(SL* pc);//检查是否需要扩容
void SLCheck(SL* pc);//打印
void SLPrint(SL* pc);//尾插
void SLPushBack(SL* pc, SLDateType x);//尾删
void SLPopBack(SL* pc);//头插
void SLPushFront(SL* pc, SLDateType x);//头删
void SLPopFront(SL* pc);//查找
int SLFind(SL* pc, SLDateType x);//插入(从0开始，也就是按照的是下标而不是个数)
void SLInsert(SL* pc, int pos, SLDateType x);//删除(从0开始，也就是按照的是下标而不是个数)
void SLErase(SL* pc, int pos);

SeqList.c

SeqList.c

#define _CRT_SECURE_NO_WARNINGS 1#include "SeqList.h"void SLInit(SL* pc)
{assert(pc);pc->a = (SLDateType*)malloc(sizeof(SLDateType) * InitCapacity);pc->size = 0;pc->capacity = InitCapacity;
}void SLDestroy(SL* pc)
{assert(pc);free(pc->a);pc->size = 0;pc->capacity = 0;pc->a = NULL;
}void SLCheck(SL* pc)
{assert(pc);if (pc->capacity == pc->size){int* str = realloc(pc->a, pc->capacity * sizeof(SLDateType) * 2);if (str == NULL){perror("realloc fail");return;//返回之后的流程是什么:会打印出开辟失败的一行信息，但接下来的步骤还会进行，比如越界什么的，强行执行后面的操作。}else{pc->a = str;str = NULL;}pc->capacity = pc->capacity * 2;}
}void SLPrint(SL* pc)
{assert(pc);for (int i = 0; i < pc->size; i++){printf("%d ", pc->a[i]);}
}void SLPushBack(SL* pc, SLDateType x)
{assert(pc);SLCheck(pc);pc->a[pc->size] = x;pc->size++;
}void SLPopBack(SL* pc)
{assert(pc);assert(pc->size);pc->size--;
}void SLPushFront(SL* pc, SLDateType x)
{assert(pc);SLCheck(pc);for (int end = pc->size - 1; end >= 0; end--){pc->a[end + 1] = pc->a[end];}pc->a[0] = x;pc->size++;
}void SLPopFront(SL* pc)
{assert(pc);assert(pc->size);for (int begin = 1; begin <= pc->size - 1; begin++){pc->a[begin - 1] = pc->a[begin];}pc->size--;
}int SLFind(SL* pc, SLDateType x)
{assert(pc);assert(pc->size);for (int i = 0; i < pc->size; i++){if (x == pc->a[i]){return i;}}return -1;
}void SLInsert(SL* pc, int pos, SLDateType x)
{assert(pc);int end = pc->size - 1;if (pos >= 0 && pos <= pc->size){SLCheck(pc);while (end >= pos){pc->a[end + 1] = pc->a[end];end--;}pc->a[pos] = x;pc->size++;}
}void SLErase(SL* pc, int pos)
{assert(pc);assert(pc->size);//可有可无int begin = pos + 1;if (pos >= 0 && pos < pc->size){while (begin < pc->size){pc->a[begin - 1] = pc->a[begin];begin++;}pc->size--;}
}

Test.c

Test.c

#define _CRT_SECURE_NO_WARNINGS 1#include "SeqList.h"void test1()
{SL s;SLInit(&s);SLPushBack(&s, 0);SLPushBack(&s, 1);SLPushBack(&s, 2);SLPushBack(&s, 3);SLPushBack(&s, 4);SLPushBack(&s, 5);SLPushBack(&s, 6);SLPopBack(&s);SLPushFront(&s, 9);SLPopFront(&s);SLPopFront(&s);SLPopFront(&s);SLPopFront(&s);int i = 0;i = SLFind(&s, 4);if (i != -1){printf("下标为%d\n", i);}SLPrint(&s);
}
void test2()
{SL s;SLInit(&s);SLPushFront(&s, 3);SLInsert(&s, 0, 0);SLInsert(&s, 0, 1);SLInsert(&s, 0, 5);SLInsert(&s, 0, 6);SLInsert(&s, 0, 7);SLInsert(&s, 2, 8);SLInsert(&s, 0, 9);SLErase(&s, 2);SLPrint(&s);
}void test3()
{SL s;SLInit(&s);SLPushFront(&s, 0);SLPushFront(&s, 1);SLPushFront(&s, 2);SLPushFront(&s, 3);SLPushFront(&s, 4);SLPushFront(&s, 5);SLPushFront(&s, 6);SLPrint(&s);
}
int main()
{//test1();//test2();test3();return 0;
}

四、总结

在这里插入图片描述

✨请点击下面进入主页关注大魔王
如果感觉对你有用的话，就点我进入主页关注我吧！


http://www.ppmy.cn/news/46956.html

相关文章

如何使用Tensorflow神经网络模型来完成兰州房价预测分析？

如何使用Tensorflow神经网络模型来完成兰州房价预测分析？

兰州房价预测是一个非常热门的话题，许多人都对如何预测兰州房价感兴趣。在本文中，我将介绍如何使用TensorFlow来预测兰州房价，并提供Python源代码。 首先，我们需要收集兰州的房价数据。我们可以从房地产网站或政府统计数据中获取。在本文中，我们将使用Kaggle上提供的兰州…
阅读更多...
收音机知识，调谐（选频/滤波），调制（升频）

收音机知识，调谐（选频/滤波），调制（升频）

参考&#xff1a;https://www.bilibili.com/video/BV1d14y1N7nm/?spm_id_from333.999.0.0&vd_source00bd76f9d6dc090461cddd9f0deb2d51 有关知识提纲 整个信号的传输变化调谐人耳听到声音的频率范围&#xff08;20~20000Hz&#xff09;天线和传送信号的波长关系波长和天线…
阅读更多...
RHCE第一次作业at和cront两个任务管理程序的区别

RHCE第一次作业at和cront两个任务管理程序的区别

1.at 单一执行的例行性工作&#xff1a;仅处理执行一次就结束了 -m 当任务完成之后&#xff0c;即使没有标准输出&#xff0c;将给用户发送邮件 -l atq的别名&#xff0c;可列出目前系统上面的所有该用户的at调度 -d atrm的别名,可以取消一个在at调度中的工作 -v 使用较明显的…
阅读更多...
pandas中df.groupby详解？

pandas中df.groupby详解？

df.groupby 是 pandas 库用于实现按照某些列进行拆分&#xff0c;应用函数和组合的一个功能。步骤如下&#xff1a; 1. 按照指定的一列或多列进行分组 (grouping) 2. 对每个分组应用一个聚合函数 (aggregation) 3. 将每个分组的聚合结果合并成一个数据结构 语法&#xff1a; df…
阅读更多...
Session详解（重点）

Session详解（重点）

类似于去服务器注册账号&#xff0c;只要服务器不停机&#xff0c;自己注册的账号一直会存在服务器。 什么是Session&#xff1a; 1.服务器会给每一个用户&#xff08;浏览器&#xff09;创建一个对象&#xff1b; 2.一个Session独占一个浏览器&#xff0c;只要浏览器没有关…
阅读更多...
***大论文中插入Visio不失真方法：word插入viso图片方法

***大论文中插入Visio不失真方法：word插入viso图片方法

***大论文中插入Visio不失真方法&#xff1a;word插入viso图片方法 1、可以直接导出emf2、如果利用emf导致字符间距过大&#xff0c;可以选择下面方式 1、可以直接导出emf 导出emf方法&#xff1a; 打开visio --> 另存为 --> 选择emf格式文件 打开word --> 插入图片…
阅读更多...
[API]ListList方法集合排序Lambda表达式（四）

[API]ListList方法集合排序Lambda表达式（四）

List接口&#xff1a; 继承自Collection接口&#xff0c;List集合是可重复集合&#xff0c;并且有序&#xff0c;还提供了一套可以通过下标来操作元素的方法 常见的实现类&#xff1a; ArrayList&#xff1a;内部使用数组实现&#xff0c;查询性能更好(直接下标找到物理地址)、…
阅读更多...
开源GPT-4小羊驼(Vicuna)快速上手指南

开源GPT-4小羊驼(Vicuna)快速上手指南

小羊驼&#xff08;Vicuna)是什么 Vicuna: 一个开源的GPT&#xff0c;宣称实现了GPT-4 90%的功能。 UC伯克利学者联手CMU、斯坦福等&#xff0c;再次推出一个全新模型70亿/130亿参数的Vicuna&#xff0c;俗称「小羊驼」&#xff08;骆马&#xff09;。 并且和其他以往不同的是…
阅读更多...
最新文章

Copyright @ 2022~2023