【数据结构】C语言实现顺序表_定义一个1.定义顺序表的结构 (struck) 2.初始化顺序表 3.赋值(不规定具体的元素个-程序员宅基地

一、顺序表的定义

顺序表是用顺序存储方式存放的线性表（可以理解为数组的存储方式），表中的元素在内存中彼此相邻。

静态存储：在定义时就确定了顺序表的大小，并且之后顺序表的大小不会改变（即使之后空间不够用了，也无法增加）
动态存储：线性表的大小可以根据需要更改（顺序表满了，可以增加顺序表的大小）

二、基本操作

0. 基本的定义

说明：定义的顺序表是动态存储的，静态的基本操作也是一样的，只是没有增加空间的操作

#include<stdio.h>
#include<stdlib.h>
#define INITSIZE 10	// 初始顺序表可以存放的最大元素个数

#define ERROR 0     //执行遇到错误
#define OK 1    	//成功执行
typedef int status;     // 返回的状态，1表示成功，0表示错误

// 顺序表的定义
typedef struct {
    	
    int *data;	// 指向顺序表数据
    int len;	// 顺序表的元素个数（长度）
    int maxSize;	// 顺序表可以存放的最大元素个数(最大长度)
}SqList;

1. 初始化顺序表

功能：构造一个空的顺序表list，分配内存空间

说明：

malloc() 函数如果内存空间不够了，会返回 NULL，这时如果再继续往后就没有意义了
为什么 list->data 为 NULL 时，不直接退出程序?
1. 如果想要在 list->dat = NULL 时退出，可以在使用时进行判断
2. 如果想在返回 list->dat = NULL 时执行某些操作，难么如果直接退出程序就没办法实现了

status InitList(SqList* list)
{
    
    list->data = (int *)malloc(INITSIZE * sizeof(int));

    // 如果没有成功开辟内存，就返回 ERROR
    if(list->data == NULL)  
    {
    
        return ERROR;
    }

    list->len = 0;
    list->maxSize = INITSIZE;

    return OK;
}

2. 销毁顺序表

功能：销毁线性表，并释放线性表list所占用的内存空间

说明：

在对顺序表操作时，先判断顺序表是否指向 NULL，如果是 NULL ,那么后面的操作就没有意义了
当释放了 list-data 指向的内存后，为什么要将 list->data 指向 NULL ？
1. 因为虽然释放了该内存，但是 list->data 仍然指向该内存地址，如果后续不小心对该地址进行操作，那么后果会很严重。
2. 有人可能会说我一定不会在释放内存后再使用的，可是万一呢？反正将 list->data 指向 NULL 又不复杂，又可以避免错误的发生，为什么不这么做呢？

status DestroyList(SqList* list)
{
    
    if(list->data == NULL)
    {
    
        return ERROR;
    }

    free(list->data);
    list->data = NULL;      // 设置为 NULL, 为了防止后续非法访问
    list->len = 0;
    list->maxSize = 0;

    return OK;
}

3. 插入元素

功能：在表中的第 pos 个位置插入指定元素 e

说明：

首先要判断是否可以插入数据
- 当 list->data = NULL 时，无法插入数据
- 当 list->len = MaxSize 时，表示顺序表已经放满了数据，也无法继续插入数据了
- 当要插入的位置不正确，也就是要插入的小于1和超出当前顺序表的长度+1时，也是无法插入的
插入元素时，只要弄清楚位置与下标的关系，就会变得很简单
- 上图中，data表示顺序表中的数据（空白表示没有数据），pos表示数据位置（从1开始），index表示元素的下标（从0开始）
- 如果想要将 300 插入到第 3 位（pos = 3），那就要将当前第3位以及后面的元素（也就是第3、4、5位）往后移动1位
  1. 先将 300 插入到顺序表的末尾，也就是第六位（pos = 6）。
  2. 然后 300 依次和前面的元素交换位置，直到 300 到达第三位（此时的index = 2）
  3. pos - 1 = index

status ListInsert(SqList* list, int pos, int e)
{
    
    if(list->data == NULL)
    {
    
        return ERROR;
    }

    if(list->len == list->maxSize)  // 判断当前的顺序表是否以及满了
    {
    
        return ERROR;
    }

    if (pos> (list->len + 1) || pos<= 0)  // 判断插入的位置是否有效
    {
    
        return ERROR;
    }

    list->data[list->len] = e;
    for(int index = list->len; index > pos - 1; index--)
    {
    
        int temp = list->data[index];
        list->data[index] = list->data[index - 1];
        list->data[index - 1] = temp;
    }
    list->len++;

    return OK;
}

4. 删除元素

功能：删除顺序表中第 pos 个位置的元素，并用 e 返回删除元素的值

说明：

首先还是判断是否能够删除
删除时先找到要删除的位置（弄清楚下标与位置的关系），再将后面的元素往前移
为什么最后只需要将长度 - 1，不将最后一位设置为 0？
- 因为当长度 - 1时，就不应该可以访问到比顺序表长度以外的位置，所以可以不用修改原来最后一位的值

status ListDelete(SqList* list, int pos, int* e)
{
    
    if(list->data == NULL)
    {
    
        return ERROR;
    }

    if (pos> list->len || pos<= 0)  // 判断插入的位置是否有效
    {
    
        return ERROR;
    }

    *e = list->data[pos- 1];
    int index;

    // 指定位置 pos后面的元素前移
    for(index = pos- 1; index < list->len; index++)
        list->data[index] = list->data[index + 1];

    // 长度 -1，让后面的元素无法被正常访问
    list->len--;
    return OK;
}

5. 按值查找

功能：在顺序表中查找指定值 e

说明：

一位一位的比较，遇到相等的值就返回该位置，需要注意访问的时候用的是下标，而要返回的是元素的位置（也就是下标 + 1 的值）
找不到指定值时就返回 -1，因为不可能有元素的位置是负的

int locateElem(SqList* const list, int e)
{
    
    if(list->data == NULL)
    {
    
        return -1;
    }

    int i;
    for(i = 0; i < list->len; i++)
        if(list->data[i] == e)
            return i+1;     // 返回的是位置，不是下标，所以要 加1
    
    return -1;  // 返回 -1 表示没有后找到找到
}

6. 按位查找

功能：获取表list中第i个位置的元素

说明：

先判断位置是否合法
只要位置合法就可以直接返回该位置的值（位置 - 1 就是该元素的下标）

int GetElem(SqList* const list, int pos)
{
    
    if(list->data == NULL)
    {
    
        return 0;
    }

    if (pos > list->len || pos <= 0)
    {
    
        return 0;
    }
    
    return list->data[pos - 1];   // 返回第 i 位元素的值
}

7. 求表长

功能：返回线性表L的长度

说明：

只要顺序表存在就直接返回该顺序表的长度

int Length(SqList* const list)
{
    
    if(list->data == NULL)
    {
    
        return -1;
    }

    return list->len;
}

8. 打印顺序表的内容

功能：按前后顺序输出线性表的所有元素

说明：

使用循环将顺序表打印，下标不超过表的长度即可

status PrintList(SqList* const list)
{
    
    if(list == NULL)
    {
    
        return ERROR;
    }
    int i;
    for(i = 0; i < list->len; i++)
    {
    
        printf("%d ",list->data[i]);
    }
    printf("\n");
}

9. 判空

功能：判断表是否为空

说明：

只需要判断顺序表的长度是否为0，就可以知道顺序表是否为空

int Empty(SqList* const list)
{
    
    if(list->data == NULL)
    {
    
        return -1;
    }

    if(list->len == 0)
        return 1;   // 返回 1，表示顺序表为空
    else
        return 0;   // 返回 0，表示顺序表不为空
}

10. 扩容

功能：增加顺序表的空间，使顺序表可以存放更多的数据

说明：

realloc() 函数可以扩容时，有三种情况：
1. 当前指向的内存空间后面有足够的空间，直接扩展当前的内存，返回的还是 list->data 的指针
2. 当前指向的内存空间后面没有足够的空间，但其他位置有足够的空间，这时会分配新的内存空间，并将当前内存中的数据复制过去，然后释放旧的内存，返回新内存地址
3. 内存中没有足够的空间可以使用，这时会返回 NULL，原来的地址依然有用
如果直接使用 list->data 接收扩容后的地址，当出现第三种情况时，之前的内存空间就再也找不到了，所以要使用新的变量接收返回的地址，以防内存不足时，旧的地址丢失

status ModifyCap(SqList* list)
{
    
    if(list->data == NULL)
    {
    
        return 0;
    }

    int* temp = (int *)realloc(list->data, (list->maxSize + 10) * sizeof(int));
    if(temp == NULL)
    {
    
        return ERROR;
    }
    if(temp != list->data)
    {
    
        free(list->data);
        list->data = temp;
    }

    list->maxSize += 10;
}

三、完整代码

SeqList.h 文件代码

#pragma once

#include<stdio.h>
#include<stdlib.h>
#define INITSIZE 10

#define ERROR 0     //执行遇到错误
#define OK 1    //成功执行

typedef int status;     // 返回的状态，1表示成功，0表示错误

// 0. 定义
typedef struct {
    
    int *data;
    int len;
    int maxSize;
}SqList;

// 1. 初始化顺序表，构造一个空的线性表list，分配内存空间
status InitList(SqList* list);

// 2. 销毁顺序表，销毁线性表，并释放线性表list所占用的内存空间
status DestroyList(SqList* list);

// 3. 插入元素，在表中的第pos个位置插入指定元素e
status ListInsert(SqList* list, int pos, int e);

// 4. 删除元素，删除表list中第pos个位置的元素，并用e返回删除元素的值
status ListDelete(SqList* list, int pos, int* e);

// 5. 按值查找，在表list中查找指定值e
int locateElem(SqList* const list, int e);

// 6. 按位查找，获取表list中第pos个位置的元素
int GetElem(SqList* const list, int pos);

// 7. 求表长,返回线性表L的长度
int Length(SqList* const list);

// 8. 打印顺序表的内容，按前后顺序输出线性表的所有元素
status PrintList(SqList* const list);

// 9. 判空，判断表是否为空
int Empty(SqList* const list);

// 10. 扩容
status Expansion(SqList* list);

SeqList.c 文件代码

#include "./head/SeqList.h"

// 初始化（InitList）
status InitList(SqList* list)
{
    
    list->data = (int *)malloc(INITSIZE * sizeof(int));

    // 如果没有成功开辟内存，就返回 ERROR
    if(list->data == NULL)  
    {
    
        return ERROR;
    }

    list->len = 0;
    list->maxSize = INITSIZE;

    return OK;
}

// 销毁（DestroyList）
status DestroyList(SqList* list)
{
    
    if(list->data == NULL)
    {
    
        return ERROR;
    }

    free(list->data);
    list->data = NULL;      // 设置为 NULL, 为了防止后续非法访问
    list->len = 0;
    list->maxSize = 0;

    return OK;
}

// 插入（ListInsert）
status ListInsert(SqList* list, int pos, int e)
{
    
    if(list->data == NULL)
    {
    
        return ERROR;
    }

    if(list->len == list->maxSize)  // 判断当前的顺序表是否以及满了
    {
    
        return ERROR;
    }

    if (pos> (list->len + 1) || pos<= 0)  // 判断插入的位置是否有效
    {
    
        return ERROR;
    }

    list->data[list->len] = e;
    for(int index = list->len; index > pos - 1; index--)
    {
    
        int temp = list->data[index];
        list->data[index] = list->data[index - 1];
        list->data[index - 1] = temp;
    }
    list->len++;

    return OK;
}

// 删除（ListDelete）
status ListDelete(SqList* list, int pos, int* e)
{
    
    if(list->data == NULL)
    {
    
        return ERROR;
    }

    if (pos> list->len || pos<= 0)  // 判断插入的位置是否有效
    {
    
        return ERROR;
    }

    *e = list->data[pos- 1];
    int index;

    // 指定位置 pos后面的元素前移
    for(index = pos- 1; index < list->len; index++)
        list->data[index] = list->data[index + 1];

    // 长度 -1，让后面的元素无法被正常访问
    list->len--;
    return OK;
}

// 按值查找（LocateElem）
int locateElem(SqList* const list, int e)
{
    
    if(list->data == NULL)
    {
    
        return -1;
    }

    int i;
    for(i = 0; i < list->len; i++)
        if(list->data[i] == e)
            return i+1;     // 返回的是位置，不是下标，所以要 加1
    
    return -1;  // 返回 -1 表示没有后找到找到
}

// 按位查找（GetElem）
int GetElem(SqList* const list, int pos)
{
    
    if(list->data == NULL)
    {
    
        return 0;
    }

    if (pos > list->len || pos <= 0)
    {
    
        return 0;
    }
    
    return list->data[pos- 1];   // 返回第 i 位元素的值
}

// 求表长（Length）
int Length(SqList* const list)
{
    
    if(list->data == NULL)
    {
    
        return -1;
    }

    return list->len;
}

// 打印顺序表（PrintList）
status PrintList(SqList* const list)
{
    
    if(list == NULL)
    {
    
        return ERROR;
    }
    int i;
    for(i = 0; i < list->len; i++)
    {
    
        printf("%d ",list->data[i]);
    }
    printf("\n");
}

// 判断表是否为空（Empty）
int Empty(SqList* const list)
{
    
    if(list->data == NULL)
    {
    
        return -1;
    }

    if(list->len == 0)
        return 1;   // 返回 1，表示顺序表为空
    else
        return 0;   // 返回 0，表示顺序表不为空
}

// 修改容量（ModifyCap）
status ModifyCap(SqList* list)
{
    
    if(list->data == NULL)
    {
    
        return 0;
    }

    int* temp = (int *)realloc(list->data, (list->maxSize + 10) * sizeof(int));
    if(temp == NULL)
    {
    
        return ERROR;
    }
    if(temp != list->data)
    {
    
        list->data = temp;
    }

    list->maxSize += 10;
}

本文链接：https://blog.csdn.net/weixin_44104992/article/details/131948269

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

oracle 12c 集群安装后的检查_12c查看crs状态-程序员宅基地

文章浏览阅读1.6k次。安装配置gi、安装数据库软件、dbca建库见下：http://blog.csdn.net/kadwf123/article/details/784299611、检查集群节点及状态：[root@rac2 ~]# olsnodes -srac1 Activerac2 Activerac3 Activerac4 Active[root@rac2 ~]_12c查看crs状态

解决jupyter notebook无法找到虚拟环境的问题_jupyter没有pytorch环境-程序员宅基地

文章浏览阅读1.3w次，点赞45次，收藏99次。我个人用的是anaconda3的一个python集成环境，自带jupyter notebook，但在我打开jupyter notebook界面后，却找不到对应的虚拟环境，原来是jupyter notebook只是通用于下载anaconda时自带的环境，其他环境要想使用必须手动下载一些库：1.首先进入到自己创建的虚拟环境(pytorch是虚拟环境的名字)activate pytorch2.在该环境下下载这个库conda install ipykernelconda install nb__jupyter没有pytorch环境

国内安装scoop的保姆教程_scoop-cn-程序员宅基地

文章浏览阅读5.2k次，点赞19次，收藏28次。选择scoop纯属意外，也是无奈，因为电脑用户被锁了管理员权限，所有exe安装程序都无法安装，只可以用绿色软件，最后被我发现scoop，省去了到处下载XXX绿色版的烦恼，当然scoop里需要管理员权限的软件也跟我无缘了（譬如everything）。推荐添加dorado这个bucket镜像，里面很多中文软件，但是部分国外的软件下载地址在github，可能无法下载。以上两个是官方bucket的国内镜像，所有软件建议优先从这里下载。上面可以看到很多bucket以及软件数。如果官网登陆不了可以试一下以下方式。_scoop-cn

Element ui colorpicker在Vue中的使用_vue el-color-picker-程序员宅基地

文章浏览阅读4.5k次，点赞2次，收藏3次。首先要有一个color-picker组件 <el-color-picker v-model="headcolor"></el-color-picker>在data里面data() { return {headcolor: ’ #278add ’ //这里可以选择一个默认的颜色} }然后在你想要改变颜色的地方用v-bind绑定就好了，例如：这里的:sty..._vue el-color-picker

迅为iTOP-4412精英版之烧写内核移植后的镜像_exynos 4412 刷机-程序员宅基地

文章浏览阅读640次。基于芯片日益增长的问题，所以内核开发者们引入了新的方法，就是在内核中只保留函数，而数据则不包含，由用户（应用程序员）自己把数据按照规定的格式编写，并放在约定的地方，为了不占用过多的内存，还要求数据以根精简的方式编写。boot启动时，传参给内核，告诉内核设备树文件和kernel的位置，内核启动时根据地址去找到设备树文件，再利用专用的编译器去反编译dtb文件，将dtb还原成数据结构，以供驱动的函数去调用。firmware是三星的一个固件的设备信息，因为找不到固件，所以内核启动不成功。_exynos 4412 刷机

Linux系统配置jdk_linux配置jdk-程序员宅基地

文章浏览阅读2w次，点赞24次，收藏42次。Linux系统配置jdkLinux学习教程，Linux入门教程（超详细）_linux配置jdk

随便推点

matlab(4)：特殊符号的输入_matlab微米怎么输入-程序员宅基地

文章浏览阅读3.3k次，点赞5次，收藏19次。xlabel('\delta');ylabel('AUC');具体符号的对照表参照下图：_matlab微米怎么输入

C语言程序设计-文件(打开与关闭、顺序、二进制读写)-程序员宅基地

文章浏览阅读119次。顺序读写指的是按照文件中数据的顺序进行读取或写入。对于文本文件，可以使用fgets、fputs、fscanf、fprintf等函数进行顺序读写。在C语言中，对文件的操作通常涉及文件的打开、读写以及关闭。文件的打开使用fopen函数，而关闭则使用fclose函数。在C语言中，可以使用fread和fwrite函数进行二进制读写。‍ Biaoge 于2024-03-09 23:51发布阅读量：7 ️文章类型：【 C语言程序设计】在C语言中，用于打开文件的函数是____，用于关闭文件的函数是____。

Touchdesigner自学笔记之三_touchdesigner怎么让一个模型跟着鼠标移动-程序员宅基地

文章浏览阅读3.4k次，点赞2次，收藏13次。跟随鼠标移动的粒子以grid（SOP）为partical（SOP）的资源模板，调整后连接【Geo组合+point spirit（MAT)】，在连接【feedback组合】适当调整。影响粒子动态的节点【metaball(SOP)+force(SOP)】添加mouse in（CHOP)鼠标位置到metaball的坐标，实现鼠标影响。..._touchdesigner怎么让一个模型跟着鼠标移动

【附源码】基于java的校园停车场管理系统的设计与实现61m0e9计算机毕设SSM_基于java技术的停车场管理系统实现与设计-程序员宅基地

文章浏览阅读178次。项目运行环境配置：Jdk1.8 + Tomcat7.0 + Mysql + HBuilderX（Webstorm也行）+ Eclispe（IntelliJ IDEA,Eclispe,MyEclispe,Sts都支持）。项目技术：Springboot + mybatis + Maven +mysql5.7或8.0+html+css+js等等组成，B/S模式 + Maven管理等等。环境需要1.运行环境：最好是java jdk 1.8，我们在这个平台上运行的。其他版本理论上也可以。_基于java技术的停车场管理系统实现与设计

Android系统播放器MediaPlayer源码分析_android多媒体播放源码分析时序图-程序员宅基地

文章浏览阅读3.5k次。前言对于MediaPlayer播放器的源码分析内容相对来说比较多，会从Java-&amp;gt;Jni-&amp;gt;C/C++慢慢分析，后面会慢慢更新。另外，博客只作为自己学习记录的一种方式，对于其他的不过多的评论。MediaPlayerDemopublic class MainActivity extends AppCompatActivity implements SurfaceHolder.Cal..._android多媒体播放源码分析时序图

java 数据结构与算法 ——快速排序法-程序员宅基地

文章浏览阅读2.4k次，点赞41次，收藏13次。java 数据结构与算法 ——快速排序法_快速排序法