目录
1、顺序表
数组在数据结构中是属于线性表的一种，线性表是由一组具有n个相同类型的数据元素组成的。线性表中的任何一个数据元素
- 有且只有一个直接前驱
- 有且只有一个直接后继
- 首元素是没有前驱的
- 尾元素是没有后继的
- 某个元素的左侧相邻元素被称为“直接前驱”，
- 元素左侧所有的数据元素被称为“前驱元素”。
- 某个元素的右侧相邻元素被称为“直接后继”，
- 元素右侧所有的数据元素被称为“后继元素”。
满足这种数学关系的一组元素，逻辑关系就是线性结构，并且逻辑关系是一对一的，比如一个教室学生的学号、一个排队的队伍、一摞堆好的盘子.....都属于线性结构，当然线性结构和存储方式是无关的，简单理解：只有逻辑关系是一对一的，就是线性结构。
所以，根据数据的存储方式可以把线性表分为两种
- 顺序存储的线性表
- 链式存储的线性表。
顺序表指的是使用一组内存地址连续的内存单元来依次存储线性表中的数据元素，使用这种存储结构的线性表就被称为顺序表。
简单理解：数据存储在一块连续的内存中，在C语言中可以具名的数组，也可以使用匿名的数组（堆内存）。
顺序表的特点：数据元素之间的逻辑关系是相邻的，并且内存地址也是相邻的，所以只要知道存储线性表的第一个数据元素的内存地址，就可以对线性表中的任意一个元素进行随机访问。通常用户使用动态分配的数组来实现顺序表,也就是使用堆内存实现。
2、随机访问&顺序访问
随机访问指的是在同等时间内具有访问任意元素的能力
- 随机访问相对立的就是顺序访问
- 顺序访问花费的时间要高于随机访问
比如卷轴（顺序）和书籍（随机）、磁带（顺序）和唱片（随机）。
3、思考
思考：既然数组可以作为线性表来使用，请问如何对数组中的元素进行增加和删除以及访问?
回答：如果打算使用数组实现线性表的特性，需要知道三个条件：
- 数组首元素地址address；
- 数组元素的容量size；
- 数组中元素的个数count。
4、顺序表的封装
/****************************************************
* @file 顺序表.c
* @brief 顺序表的实现
* @author [email protected]
* @date 2024-6-15
* @version V1.0
* @note
* 数组下标从0开始，到size-1结束；
* 数组下标从0开始，有效元素个数为count，则最后一个元素的下标是count-1；
* 从末尾插入元素时，count+1，如果count==size，则需要扩容；
* 从末尾删除元素时，count-1，如果count==size，则需要缩容；
* @history
* Date Version Author Notes
* 2024-6-15 0.0.1 zuozhenxing first version
* Copyright (c) 2024,[email protected] All rights reserved.
***********************************************/
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
// 1.定义顺序表数据类型
typedef int ElemType;
// 2.设计一个顺序表结构体
typedef struct Sqlist
{
ElemType *data; // 保存数据首地址
int count; // 保存存储的数据个数
int size; // 保存容量
} Sqlist_t;
// 3.创建一个顺序表
Sqlist_t *createSq(int size);
// 4.销毁顺序表
void destroySq(Sqlist_t *sq);
// 5.在指定位置插入数据
bool insertSq(Sqlist_t *sq, ElemType data, int pos);
// 6.查询数据--返回数据位置，没找到返回-1
int indexSq(Sqlist_t *sq, ElemType data);
// 7.删除数据
bool deleteSq(Sqlist_t *sq, ElemType data);
// 8.遍历显示
void displaySq(Sqlist_t *sq);
/*********************createSq*****************************
* @function:createSq
* @brief:创建一个顺序表
* @param
* size 顺序表的容量
* @return
* Sqlist_t* 返回顺序表结构体指针
* @author: demon_xing
* @date:2024-6-15
* @version:V1.0
* @note:notes
* @history:
* Date Version Author Notes
* 2020-04-26 0.0.1 demon_xing first version
* *******************END****************************/
// 1.创建一个顺序表
Sqlist_t *createSq(int size)
{
// (1)申请结构体空间
Sqlist_t *sq = (Sqlist_t *)malloc(sizeof(Sqlist_t));
if (sq == NULL)
{
return NULL;
}
// (2)初始化结构体成员，
sq->size = size;
sq->count = 0;
// (3)申请数据空间
sq->data = calloc(sq->size, sizeof(ElemType));
if (sq->data == NULL)
{
// 数据空间申请失败，则将其结构体空间释放,返回NULL
perror("申请数据空间失败");
free(sq);
return NULL;
}
// （4）如果数据空间申请成功，则返回结构体指针
return sq;
}
/*********************destroySq*****************************
* @function:destroySq
* @brief:销毁顺序表
* @param
* sq 顺序表结构体指针
* @return
* void
* @author: demon_xing
* @date:2024-6-15
* @version:V1.0
* @note:notes
* @history:
* Date Version Author Notes
* 2020-04-26 0.0.1 demon_xing first version
* **********************END*************************/
// 2.销毁顺序表
void destroySq(Sqlist_t *sq)
{
// （1）如果sq为NULL，则直接返回
if (sq == NULL)
{
return;
}
// （2）如果sq不为NULL，则释放数据空间和结构体空间
// 释放数据空间
free(sq->data);
// 释放结构体空间
free(sq);
}
/*********************insertSq*****************************
* @function:insertSq
* @brief:在指定位置插入数据
* @param
* sq 顺序表结构体指针
* data 插入的数据
* pos 插入的位置
* @return
* bool 插入成功返回true，否则返回false
* @author: demon_xing
* @date:2024-6-15
* @version:V1.0
* @note:
* 插入数据后，count++
* @history:
* Date Version Author Notes
* 2020-04-26 0.0.1 demon_xing first version
* **********************END*************************/
// 3.在指定位置插入数据
bool insertSq(Sqlist_t *sq, ElemType data, int pos)
{
//(1)判断sq是否为空,如果为空，则直接返回false，如果不为空，则继续执行
if (sq == NULL || pos < 0)
{
perror("顺序表为NULL");
return false;
}
// （2)判断顺序表是否已满，如果已满，则直接返回false，如果不满，则继续执行
if (sq->count == sq->size)
{
perror("顺序表满");
return false;
}
// （3）判断pos是否在0-count中间，如果在就要进行挪位，如果不在0-count中间就直接插入末尾
// pos不在0-count中间，末尾插入
if (pos >= sq->count)
{
// 把数据放在pos位置，因为pos是最后一个位置，所以直接放在count位置，数组从0开始计数
sq->data[sq->count] = data;
// 插入数据后，count++
sq->count++;
}
// pos在0-count中间，需要进行挪位
else
{
for (int i = sq->count; i > pos; i--)
{
// pos以后的数据后移一位
sq->data[i] = sq->data[i - 1];
}
// （4）把数据放在pos位置
sq->data[pos] = data;
// （5）插入数据后，count++
sq->count++;
}
return true;
}
/*********************indexSq*****************************
* @function:indexSq
* @brief:查询数据
* @param
* sq 顺序表结构体指针
* data 查询的数据
* @return
* int 返回数据位置下标，没找到返回-1
* @author: demon_xing
* @date:2024-6-15
* @version:V1.0
* @note:notes
* @history:
* Date Version Author Notes
* 2020-04-26 0.0.1 demon_xing first version
* **********************END*************************/
// 4.查询数据
int indexSq(Sqlist_t *sq, ElemType data)
{
// （1）遍历数组， 查到就返回数组下标，查不到就返回-1
if (sq == NULL)
{
perror("顺序表为NULL,请先创建");
return -1; // 没找到数据
}
for (int i = 0; i < sq->count; i++)
{
if (sq->data[i] == data)
{
return i; // 找到数字，返回该数据的下标
}
}
return -1;
}
/*********************deleteSq*****************************
* @function:deleteSq
* @brief:删除数据
* @param
* sq 顺序表结构体指针
* data 删除的数据
* @return
* bool 删除成功返回true，否则返回false
* @author: demon_xing
* @date:2024-6-15
* @version:V1.0
* @note:
* 删除数据之后，count--
* @history:
* Date Version Author Notes
* 2020-04-26 0.0.1 demon_xing first version
* **********************END*************************/
// 5.删除数据
bool deleteSq(Sqlist_t *sq, ElemType data)
{
// （1）调用indexSq查询
int pos = indexSq(sq, data);
if (pos == -1)
{
return false;
}
// （2）挪位删除
for (int i = pos; i < sq->count - 1; i++)
{
sq->data[i] = sq->data[i + 1];
}
// （3）删除数据之后，count--
sq->count--;
return true;
}
/*********************displaySq*****************************
*
* @function:displaySq
* @brief:遍历显示
* @param
* sq 顺序表结构体指针
* @return
* void
* @author: demon_xing
* @date:2024-6-15
* @version:V1.0
* @note:notes
* @history:
* Date Version Author Notes
* 2020-04-26 0.0.1 demon_xing first version
* **********************END*************************/
// 遍历显示
void displaySq(Sqlist_t *sq)
{
// 遍历数组输出
if (sq == NULL)
return;
for (int i = 0; i < sq->count; i++)
{
printf("%d ", sq->data[i]);
}
printf("\n");
}
/*********************main*****************************
* @function:main
* @brief:主函数，测试顺序表
* @param
* void
* @return
* int
* @author: demon_xing
* @date:2024-6-15
* @version:V1.0
* @note:notes
* @history:
* Date Version Author Notes
* 2020-04-26 0.0.1 demon_xing first version
* **********************END*************************/
int main(void)
{
// 1.创建顺序表
Sqlist_t *sq = createSq(10);
// 2.插入数据
for (int i = 0; i < 10; i++)
{
int data = random() % 100;
insertSq(sq, data, i);
}
// 3.显示
displaySq(sq);
// 4.删除数据
deleteSq(sq, 21);
// 5.显示
displaySq(sq);
// 6.销毁
destroySq(sq);
// 7.显示，如果段错误，说明销毁成功，否则销毁失败
displaySq(sq);
// 也可以用valgrind内存检测工具或内存泄漏检测器来证所有的内存已经被正确释放，确保没有内存泄漏。
return 0;
}