自学内容网 自学内容网
自学内容网 > 正文

顺序表专题

🕗 发布于 2024-11-05 20:02 数据结构  

目录

0. 什么是数据结构？

0. 为什么需要数据结构？

1.顺序表的概念及结构

2.顺序表分类：

3.动态顺序表的实现

4. 顺序表的应用

5. 顺序表的问题及思考

0. 什么是数据结构？

数据结构是由“数据”和“结构”两词结合而来

什么是数据？常见的数值1、2、3...教务系统里保存的用户信息（姓名、性别、年龄、学历等）、网页里肉眼可见的信息（文字、图片、视频等），这些都是数据

什么是结构？当我们想要使用大量使用同一类型的数据时，通过手动定义大量的独立的变量对于程序来说，可读性非常差，我们可以借助数组这样的数据结构将大量的数据组织在一起，结构也可以理解为组织数据的方式

想要在草原上找到名叫“咩咩”的羊很难，但是从羊圈里找到1号羊就很简单，羊圈这样的结构有效将羊群组织起来

概念：数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。数据结构反应数据的内部组成，即数据由哪部分构成，以什么方式构成，以及数据元素之间呈现的结构

总结：

  • 能够存储数据（如顺序表、链表等结构）
  • 存储的数据能够方便查找

0. 为什么需要数据结构？

程序中如果不对数据进行管理，可能会导致数据丢失、操作数据困难、野指针等情况

通过数据结构，能够有效将数据组织和管理在一起，按照我们的方式任意对数据进行增删改查等操作

最基础的数据结构：数组

最基础的数据结构能够提供的操作已经不能完全满足复杂算法实现

顺序表底层就是数组，在数组的基础上增加了增删改查等方法

1.顺序表的概念及结构

顺序表是线性表的一种

线性表(linear list)是n个具有相同特性的数据元素的有限序列（集合）。

线性表是一种在实际中广泛使用的数据结构

常见的线性表：顺序表、链表、栈、队列、字符串...

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

由于顺序表底层是数组，所以顺序表在物理结构上是连续的，逻辑结构也是连续的

案例：蔬菜分为绿菜叶、瓜类、菌菇类。线性表指的是具有部分相同特性的一类数据结构的集合

2.顺序表分类：

3.动态顺序表的实现

头文件.h：顺序表结构，声明顺序表的方法

源文件.c：实现顺序表的方法

测试文件.c

如果初始化时，  指针指向空指针，并且使用了assert断言，则会发生以下报错：

void SLTest01()
{
SL sl;
SLInit(&sl);
//增删改查操作
//测试尾插
SLPushBack(&sl, 1);
SLPushBack(&sl, 2);
SLPushBack(&sl, 3);
SLPushBack(NULL, 4);
//...
SLDestroy(&sl);
}
//尾插
void SLPushBack(SL* ps, SLDataType x)
{
//ps->arr[ps->size]=x;
//++ps->size;
assert(ps);//等价于assert(ps!=NULL)
//插入数据之前先看空间够不够
if (ps->capacity == ps->size) {
//继续申请空间（增容）用realloc函数
//第一个问题：要申请多大的空间/一次增容多大？
//增容通常来说是成倍数的增加，一般是2倍或3倍（数学推理得出）
int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));//申请空间的大小
if (tmp == NULL)
{
perror("realloc fail!");
exit(1);
}
//空间申请成功
ps->arr = tmp;
ps->capacity = newCapacity;
}
ps->arr[ps->size++] = x;
}

 运行结果报错：

实现完整文件：

 test.c文件：

#include"SeqList.h"
void SLTest01()
{
SL sl;
SLInit(&sl);
//增删改查操作
//测试尾插
SLPushBack(&sl, 1);
SLPushBack(&sl, 2);
SLPushBack(&sl, 3);
SLPushBack(&sl, 4);
SLPrint(sl);//1 2 3 4
//测试头插
SLPushFront(&sl, 5);
//SLPushFront(NULL, 5);
SLPrint(sl);//5 1 2 3 4
//测试尾删
SLPopBack(&sl);
SLPrint(sl);//5 1 2 3
//测试头删
SLPopFront(&sl);
SLPrint(sl);//1 2 3
SLDestroy(&sl);
}
void SLTest02()
{
SL sl;
SLInit(&sl);
SLPushBack(&sl, 1);
SLPushBack(&sl, 2);
SLPushBack(&sl, 3);
SLPushBack(&sl, 4);//1 2 3 4
//测试指定位置前插入数据
SLInsert(&sl, 0, 99);
SLPrint(sl);//99 1 2 3 4
SLInsert(&sl, sl.size, 88);
SLPrint(sl);//99 1 2 3 4 88
SLInsert(&sl, 3, 88);
SLPrint(sl);//99 1 2 88 3 4 88
SLErase(&sl, 0);
SLPrint(sl);//1 2 88 3 4 88
printf("%d",SLFind(&sl, 88));//2
SLDestroy(&sl);

}
int main()
{
//SLTest01();
SLTest02();
return 0;
}

SeqList.h文件：

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//定义顺序表的结构

//静态顺序表（不推荐使用）
//#define N 100
//struct SeqList
//{
//int arr[N];
//int size;//有效数据个数
//};

//动态顺序表
typedef int SLDataType;//为了方便后续类型的替换
typedef struct SeqList
{
SLDataType *arr;
int size;//有效数据个数
int capacity;//空间大小
}SL;
//顺序表的初始化
void SLInit(SL* ps);
//顺序表的销毁
void SLDestroy(SL* ps);
//顺序表的打印
void SLPrint(SL s);
//头部插入删除/尾部插入删除
void SLPushBack(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);

SeqList.c文件：

#include"SeqList.h"
void SLInit(SL *ps)
{
ps->arr = NULL;
ps->size = ps->capacity = 0;
}
//顺序表的销毁
void SLDestroy(SL* ps)
{
//if (ps->arr)//等价于 if(ps->arr!=NULL)
//{
//free(ps->arr);
//}
ps->arr = NULL;
ps->size = ps->capacity = 0;
}
void SLCheckCapacity(SL* ps)
{
//插入数据之前先看空间够不够
if (ps->capacity == ps->size) {
//继续申请空间（增容）用realloc函数
//第一个问题：要申请多大的空间/一次增容多大？
//增容通常来说是成倍数的增加，一般是2倍或3倍（数学推理得出）
int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));//申请空间的大小
if (tmp == NULL)
{
perror("realloc fail!");
exit(1);
}
//空间申请成功
ps->arr = tmp;
ps->capacity = newCapacity;
}
}
//尾插
void SLPushBack(SL* ps, SLDataType x)
{
//ps->arr[ps->size]=x;
//++ps->size;
assert(ps);//等价于assert(ps!=NULL)
SLCheckCapacity(ps);
ps->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];
}
ps->arr[0] = x;
ps->size++;
}
void SLPrint(SL s)
{
for (int i = 0; i < s.size; i++)
{
printf("%d ", s.arr[i]);
}
printf("\n");
}
//尾删
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);
//插入数据：空间够不够
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);
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;
}

4. 顺序表的应用

基于动态顺序表实现通讯录：

Contact.h文件：

#pragma once
//定义联系人数据结构
#define NAME_MAX 20
#define GENDER_MAX 10
#define TEL_MAX 20
#define ADDR_MAX 100

typedef struct personInfo
{
char name[NAME_MAX];
char gender[GENDER_MAX];
int age;
char tel[TEL_MAX];
char addr[ADDR_MAX];
}peoInfo;

//要用到顺序表相关方法，对通讯录的操作就是对顺序表进行操作
//给顺序表改个名字，叫做通讯录：
typedef struct SeqList Contact;//前置声明

//通讯录相关的方法：
//通讯录的初始化
void ContactInit(Contact* con);
//通讯录的销毁
void ContactDestroy(Contact* con);
//通讯录添加数据
void ContactAdd(Contact* con);
//通讯录删除数据
void ContactDel(Contact* con);
//通讯录的修改
void ContactModify(Contact* con);
//通讯录的查找
void ContactFind(Contact* con);
//展示通讯录数据
void ContactShow(Contact* con);

SeqList.h文件：

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1 
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include"Contact.h"
//定义顺序表的结构

//静态顺序表（不推荐使用）
//#define N 100
//struct SeqList
//{
//int arr[N];
//int size;//有效数据个数
//};

//动态顺序表
//typedef int SLDataType;//为了方便后续类型的替换
typedef peoInfo SLDataType;//数据类型的替换
typedef struct SeqList
{
SLDataType* arr;
int size;//有效数据个数
int capacity;//空间大小
}SL;
//顺序表的初始化
void SLInit(SL* ps);
//顺序表的销毁
void SLDestroy(SL* ps);
//顺序表的打印
void SLPrint(SL s);
//头部插入删除/尾部插入删除
void SLPushBack(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);

Contact.c文件：

#include "Contact.h"
#include "SeqList.h"
//通讯录的初始化
void ContactInit(Contact* con)
{
//实际上是顺序表的初始化：
SLInit(con);
}
//通讯录的销毁
void ContactDestroy(Contact* con)
{
SLDestroy(con);
}
//通讯录添加数据
void ContactAdd(Contact* con)
{
//获取用户输入的内容：姓名+性别+年龄+电话+地址
peoInfo info;
printf("请输入要添加的联系人姓名：\n");
scanf("%s", info.name);
printf("请输入要添加的联系人性别：\n");
scanf("%s", info.gender);
printf("请输入要添加的联系人年龄：\n");
scanf("%d", &info.age);
printf("请输入要添加的联系人电话：\n");
scanf("%s", info.tel);
printf("请输入要添加的联系人地址：\n");
scanf("%s", info.addr);
//添加联系人数据
SLPushBack(con, info);
}
int FindByName(Contact* con, char name[])
{
for (int i = 0; i < con->size; i++)
{
if (0 == strcmp(con->arr[i].name, name))//找到
{
return i;
}
}
//没有找到
return -1;
}
//通讯录删除数据
void ContactDel(Contact* con)
{
//删除的数据必须存在才能执行删除操作
//查找
char name[NAME_MAX];
printf("请输入要删除的联系人姓名：\n");
scanf("%s", name);
int find = FindByName(con, name);//保存要删除联系人的下标
if (find < 0)
{
printf("联系人不存在！");
return;
}
SLErase(con, find);
printf("删除成功！\n");
}
//展示通讯录数据
void ContactShow(Contact* con)
{
printf("%s\t%s\t%s\t%s\t\t%s\n", "姓名", "性别", "年龄", "电话", "地址");
for (int i = 0; i < con->size; i++)
{
printf("%s\t%s\t%d\t%s\t\t%s\n", con->arr[i].name,
con->arr[i].gender, con->arr[i].age,
con->arr[i].tel, con->arr[i].addr);
}
}
//通讯录的修改
void ContactModify(Contact* con)
{
char name[NAME_MAX];
char gender[GENDER_MAX];
char tel[TEL_MAX];
char addr[ADDR_MAX];
int age;
printf("请输入要修改的联系人姓名：\n");
scanf("%s", name);
int find = FindByName(con, name);//保存要删除联系人的下标
if (find < 0)
{
printf("联系人不存在！");
return;
}
//修改
int chos = 0;
printf("请输入要修改的选项：1.姓名 2.性别 3.年龄 4.电话 5.地址\n");
scanf("%d", &chos);
switch (chos)
{
case 1:
printf("请输入修改后的姓名：");
scanf("%s", con->arr[find].name);
break;
case 2:
printf("请输入修改后的性别：");
scanf("%s", con->arr[find].gender);
break;
case 3:
printf("请输入修改后的年龄：");
scanf("%d", con->arr[find].age);
break;
case 4:
printf("请输入修改后的电话：");
scanf("%s", con->arr[find].tel);
break;
case 5:
printf("请输入修改后的地址：");
scanf("%s", con->arr[find].addr);
break;
}
printf("修改成功！\n");
}
//通讯录的查找
void ContactFind(Contact* con)
{
char name[NAME_MAX];
printf("请输入要查找的联系人姓名：\n");
scanf("%s", name);
int find = FindByName(con, name);//保存要删除联系人的下标
if (find < 0)
{
printf("联系人不存在！\n");
return;
}
printf("%s\t%s\t%s\t%s\t\t%s\n", "姓名", "性别", "年龄", "电话", "地址");
printf("%s\t%s\t%d\t%s\t\t%s\n", con->arr[find].name,
con->arr[find].gender, con->arr[find].age,
con->arr[find].tel, con->arr[find].addr);
return;
}

SeqList.c文件：

#include"SeqList.h"
void SLInit(SL* ps)
{
ps->arr = NULL;
ps->size = ps->capacity = 0;
}
//顺序表的销毁
void SLDestroy(SL* ps)
{
//if (ps->arr)//等价于 if(ps->arr!=NULL)
//{
//free(ps->arr);
//}
ps->arr = NULL;
ps->size = ps->capacity = 0;
}
void SLCheckCapacity(SL* ps)
{
//插入数据之前先看空间够不够
if (ps->capacity == ps->size) {
//继续申请空间（增容）用realloc函数
//第一个问题：要申请多大的空间/一次增容多大？
//增容通常来说是成倍数的增加，一般是2倍或3倍（数学推理得出）
int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));//申请空间的大小
if (tmp == NULL)
{
perror("realloc fail!");
exit(1);
}
//空间申请成功
ps->arr = tmp;
ps->capacity = newCapacity;
}
}
//尾插
void SLPushBack(SL* ps, SLDataType x)
{
//ps->arr[ps->size]=x;
//++ps->size;
assert(ps);//等价于assert(ps!=NULL)
SLCheckCapacity(ps);
ps->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];
}
ps->arr[0] = x;
ps->size++;
}
//void SLPrint(SL s)
//{
//for (int i = 0; i < s.size; i++)
//{
//printf("%d ", s.arr[i]);
//}
//printf("\n");
//}
//尾删
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);
//插入数据：空间够不够
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);
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;
//}

test.c文件：

#include"SeqList.h"
//void SLTest01()
//{
//SL sl;
//SLInit(&sl);
////增删改查操作
////测试尾插
//SLPushBack(&sl, 1);
//SLPushBack(&sl, 2);
//SLPushBack(&sl, 3);
//SLPushBack(&sl, 4);
//SLPrint(sl);//1 2 3 4
////测试头插
//SLPushFront(&sl, 5);
////SLPushFront(NULL, 5);
//SLPrint(sl);//5 1 2 3 4
////测试尾删
//SLPopBack(&sl);
//SLPrint(sl);//5 1 2 3
////测试头删
//SLPopFront(&sl);
//SLPrint(sl);//1 2 3
//SLDestroy(&sl);
//}
//void SLTest02()
//{
//SL sl;
//SLInit(&sl);
//SLPushBack(&sl, 1);
//SLPushBack(&sl, 2);
//SLPushBack(&sl, 3);
//SLPushBack(&sl, 4);//1 2 3 4
////测试指定位置前插入数据
//SLInsert(&sl, 0, 99);
//SLPrint(sl);//99 1 2 3 4
//SLInsert(&sl, sl.size, 88);
//SLPrint(sl);//99 1 2 3 4 88
//SLInsert(&sl, 3, 88);
//SLPrint(sl);//99 1 2 88 3 4 88
//SLErase(&sl, 0);
//SLPrint(sl);//1 2 88 3 4 88
//printf("%d",SLFind(&sl, 88));//2
//SLDestroy(&sl);
//
//}
//void ContactTest01()
//{
//Contact con;//创建的通讯录对象，实际上就是顺序表对象，等价于 SL sl
//ContactInit(&con);
//ContactAdd(&con);
//ContactShow(&con);
//ContactModify(&con);
////ContactDel(&con);
//ContactShow(&con);
//ContactFind(&con);
//ContactDestroy(&con);
//}
//int main()
//{
////SLTest01();
////SLTest02();
//ContactTest01();
//return 0;
//}

void menu()
{
int op;
Contact* con;
ContactInit(&con);
do {
printf("---------------------通讯录---------------------\n");
printf("--------1.添加联系人2.删除联系人----\n");
printf("--------3.修改联系人信息4.查找联系人----\n");
printf("--------5.显示所有联系人0.退出----------\n");
printf("------------------------------------------------\n");
printf("请选择您的操作：");

scanf("%d", &op);
switch (op)
{
case 1:
ContactAdd(&con);
break;
case 2:
ContactDel(&con);
break;
case 3:
ContactModify(&con);
break;
case 4:
ContactFind(&con);
break;
case 5:
ContactShow(&con);
break;
case 0:
printf("已退出！");
break;
default:
printf("输入错误，请重新输入：");
break;
}
} while (op != 0);
ContactDestroy(&con);
}
int main()
{
menu();
return 0;
}

5. 顺序表的问题及思考

  1. 中间/头部的插入删除，时间复杂度为O(N)
  2. 增容需要申请新空间，拷贝数据，释放旧空间，会有不小消耗
  3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入5个数据，后面就没有数据插入了，那么就浪费了95个数据空间

原文地址：https://blog.csdn.net/2301_80802299/article/details/138010781

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

相关文章

  • TiDB 概念简述

    TiDB 是一个适用于互联网和传统行业大规模数据处理需求的分布式数据库解决方案。它结合了传统 RDBMS 的易用性和 NoSQL 的可扩展性，提供了一种新的数据库技术选择。

    阅读更多2024-11-06
  • 记录一个跳跃的小游戏

    【代码】记录一个跳跃的小游戏。

    阅读更多2024-11-06
  • 优化文本嵌入，大幅提升RAG检索速度

    大家好，文本嵌入技术能够将文字信息转换成高维向量表示的数字，提供了一种理解和处理文本数据的新方式，帮助我们更好地理解和处理文本数据。这些向量能够捕捉文本的深层特征，进而支持多种应用，比如理解语义、进行

    阅读更多2024-11-06
  • Ubuntu22.04在Docker下安装Mysql5.7

    使用Ubuntu22.04在docker下安装mysql5.7的详细过程

    阅读更多2024-11-06
  • SpringFactoriesLoader

    SpringFactoriesLoader类的主要作用是通过类路径下的文件获取工厂类接口的实现类，初始化并保存在缓存中，以供Springboot启动过程中各个阶段的调用。Spring的自动化配置功能，

    阅读更多2024-11-06
  • 深度学习基础—双向RNN和深层RNN

    要识别Teddy是否是人名的一部分，普通RNN在第3个时间步时只能学习到Teddy以前的内容，而比较关键的词在第4个时间步，因此要想解决这个问题，就需要让网络有预知“未来”的能力，双向循环神经网络正是

    阅读更多2024-11-06
  • Python软体中使用Pandas库读取数据并绘制柱状图的实用指南

    通过本教程，我们学习了如何使用Pandas库读取CSV文件，并利用Matplotlib库绘制柱状图。我们从数据读取、处理到可视化的整个过程进行了详细的讲解，并提供了优化图表的技巧和保存图表的方法。数据

    阅读更多2024-11-06
  • 如何使用python完成时间序列的数据分析？

    时间序列是指在时间上有序的一组数据点。时间序列数据可以是定期收集的（如每日、每月、每年）或不定期收集的。时间序列的主要特征包括趋势、季节性、周期性和随机性。

    阅读更多2024-11-06
  • 数据结构 C/C++(实验一:线性表)

    1．掌握线性表的顺序存储表示和链式存储表示。2．掌握顺序表和链表的基本操作算法，包括创建、取值、查找、插入、删除等基本操作的实现。3．了解线性表两种不同存储结构的特点，会灵活运用线性表解决某些实际问题

    阅读更多2024-11-06
  • 数据库-＞视图

    视图是⼀个虚拟的表，它是基于⼀个或多个基本表或其他视图的查询结果集。视图本⾝不存储数据，⽽是通过执⾏查询来动态⽣成数据。⽤⼾可以像操作普通表⼀样使⽤视图进⾏查询、更新和管理。视图本⾝并不占⽤物理存储空

    阅读更多2024-11-06
自学内容网
Copyright © 2015-2024