数据结构-顺序表及其应用
文章目录
- 一、数据结构的相关概念
- 1.什么是数据结构？
- 2.为什么需要数据结构?
- 二、顺序表
- 1.顺序表的概念及结构
- 1.1线性表
- 2.顺序表分类
- 三、顺序表增删查改操作的实现
- 四、通讯录的实现
- 1.顺序表的问题及思考
一、数据结构的相关概念
1.什么是数据结构？
数据结构是由“数据”和“结构”两词组合而来的。
🍉什么是数据?
常见的数值1、2、3、4、教务系统里保存的用户信息(姓名、性别、年龄、学历等等)、网页里肉眼可以看到的信息(文字、图片、视频等等)，这些都是数据。
🍉什么是结构?
当我们想要使用大量同一类型的数据时，通过手动定义大量的独立变量对于程序来说，可读性非常差，我们可以借助数组这样的数据结构将大量的数据组织在一起，结构也可以理解为组织数据的方式。
就像上图中，想要找到草原上名叫“咩咩”的羊很难，但是从羊圈里找到1号羊就很简单，有了羊圈这样的结构，就能有效地将羊群组织起来进行管理。
🍉概念：🔑数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。数据结构反映数据的内部构成，即数据由哪部分构成，以什么方式构成，以及数据元素之间呈现的结构。
总结：
🍇 (1) 能够存储数据(如顺序表、链表等结构)
🍇 (2) 存储的数据能够方便查找
2.为什么需要数据结构?
如图中所示，不借助排队的方式来管理客户，会导致客户就餐感受差、等餐时间长、餐厅营业混乱等情况。同理，程序中如果不对数据进行管理，就可能会导致数据丢失、操作数据困难、野指针等情况。而通过数据结构，能够有效地将数据组织和管理在一起。按照我们的方式任意对数据进行增删查改等操作。
比如我们学过最基础的数据结构：数组。
【思考】有了数组，为什么还要学习其他的数据结构?
假定数组有10个空间，已经使用了5个，那向数组中插入数据步骤:
求数组的长度，求数组的有效数据个数，向下标为数据有效个数的位置插入数据(注意：这里是否要判断数组是否满了？满了还能继续插入吗？)……
比如现在有一个数组：
🥥int arr[100] = {1,2,3,4,5};
如果需要修改数组中的某个数据：
arr[pos] = x;
🥥如果要向数组最后插入一个数据, 那么要先找到数组中已有元素的个数, 再在最后的位置插入数据
🥥如果要删除数组中的最后一个数据, 也要先找到数组中已有元素的个数, 再删除最后一个数据
🍊所以数组只是能存储这些相同类型的数据，但是涉及到数据的增删改查这些特殊操作时，那数组使用起来就比较麻烦，如果涉及到数组元素的增删改查等操作，就可能需要写循环遍历数组，要是有很多个不同的数组，那每种操作都要单独实现的话，就很麻烦也很影响程序的运行效率。所以出现了顺序表。
假设数据量非常庞大，频繁地获取数组的有效数据个数会影响程序的执行效率。
结论：最基础的数据结构能够提供的操作已经不能完全满足复杂算法的实现了。
二、顺序表
1.顺序表的概念及结构
顺序表(sequence list)是属于线性表的一种。那什么又是线性表呢？
1.1线性表
线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性有：顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的。线性表在物理上存储时，通常以数组和链式结构的形式存储。
案例：蔬菜分为绿叶类、瓜类、菌菇类。线性表指的是具有部分相同特性的一类数据结构的集合，如何理解逻辑结构和物理结构?
线性表的物理结构就是在内存中实际存储的样子(地址是不是连续的)，不一定是连续的。
而线性表在逻辑结构上是连续的(也就是我们肉眼看到的像一条连续的直线一样的结构)。
2.顺序表分类
(1) 顺序表和数组的区别：
顺序表的底层结构就是数组，对数组进行了封装，在数组的基础上增加了常用的增删改查等操作。
那对于顺序表来说是属于线性表的一种，那顺序表在逻辑结构上一定是连续的，而在物理结构上也是连续的(因为顺序表的底层是数组，数组在内存中是连续存储的)
我们学习过几种向内存申请空间的方法：创建变量、创建数组、动态内存开辟。如果我们想创建一个定长数组：
int arr[10] = { 0 };
但是当我们还不确定数组到底需要多长时，我们可以先创建一个指针：
int* arr;
当我们确定需要多长的空间后，就可以通过动态内存开辟空间：
arr = (int*)malloc(5*sizeof(int))
因为动态内存开辟的空间在物理上也是连续的，所以可以把动态申请的内存空间看做数组。
(2) 顺序表分类
❶🍑静态顺序表🍑定义：
struct SeqList
{
int arr[100];//定长数组
int size;//用来记录数组当前的有效数据个数
};
所以静态顺序表的底层是定长数组。静态顺序表的缺陷：空间给少了不够用，给多了造成空间浪费。
❷🍑动态顺序表🍑定义：
struct SeqList
{
int* arr;
int size;//用来记录数组当前的有效数据个数
int capacity;//用来记录当前动态开辟空间的大小(空间容量)
};
由于动态顺序表是通过动态内存分配空间的，所以到后面如果发现申请的空间小了，我们还可以动态的更改空间大小(动态地增容)。所以更推荐使用动态顺序表。
注意：对于静态顺序表中的定长数组的长度，使用#define定义的符号N，这样写的好处是：如果以后代码中有很多的静态顺序表，我们需要更改定长数组的长度，就可以直接更改#define定义的符号即可。用typedef对struct SeqList进行重命名为SL，以后在代码中就可以直接使用SL来创建结构体变量，这样更简洁方便一些。
三、顺序表增删查改操作的实现
1.将关于顺序表结构声明，顺序表方法的声明放在SeqList.h的头文件中：
//SeqList.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
静态顺序表
//typedef int SLDataType;
//#define N 10
//typedef struct SeqList
//{
// SLDataType arr[N];
// int size; //有效数据个数
//}SL;
//动态顺序表
typedef int SLDataType;
typedef struct SeqList
{
SLDataType* arr;
int size; //有效数据个数
int capacity;//空间容量
}SL;
//1.顺序表的初始化
void SLInit(SL* ps);
//2.检查空间是否够用
void SLCheckCapacity(SL* ps);
//3.打印顺序表中arr的内容
void SLPrint(SL ps);
//4.顺序表的尾插(从有效数据的后面插入数据)
void SLPushBack(SL* ps, SLDataType x);
//5.顺序表的头插(从arr指向的起始位置开始插入数据)
void SLPushFront(SL* ps, SLDataType x);
//6.顺序表的尾删
void SLPopBack(SL* ps);
//7.顺序表的头删
void SLPopFront(SL* ps);
//8.在指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType x);
//9.删除指定位置的数据
void SLErase(SL* ps, int pos);
//10.顺序表的查找
int SLFind(SL* ps, SLDataType x);
//11.顺序表的销毁
void SLDestory(SL* ps);
2.将顺序表方法的实现放在SeqList.c文件中：
//SeqList.c
#include"SeqList.h"
void SLInit(SL* ps)
{
ps->arr = NULL;
ps->size = 0;
ps->capacity = 0;
}
void SLCheckCapacity(SL* ps)
{
if (ps->size == ps->capacity)
{
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->arr
ps->capacity = newCapacity;
}
}
void SLPrint(SL sl)
{
for (int i = 0; i < sl.size; i++)
{
printf("%d ", sl.arr[i]);
}
printf("\n");
}
void SLPushBack(SL* ps, SLDataType x)
{
assert(ps);
//插入数据之前先检查空间够不够用，不够需要增容
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[1]=ps->arr[0]时挪动完毕，则i>0
}
ps->arr[0] = x;
ps->size++;//头插数据以后记得要让size自增1
}
void SLPopBack(SL* ps)
{
assert(ps);
//尾删之前要确保有效数据个数不为0
assert(ps->size != 0);
ps->size--;
}
void SLPopFront(SL* ps)
{
assert(ps);
//头删之前要确保有效数据的个数不为0
assert(ps->size != 0);
for (int i = 0; i<ps->size-1; i++)
{
ps->arr[i] = ps->arr[i + 1];//当ps->arr[size-2]=ps->arr[size-1]时完毕，所以i<ps->size-1
}
ps->size--;
}
void SLInsert(SL* ps, int pos, SLDataType x)
{
assert(ps);
//在指定位置插入数据，要考边界位置处的情况
assert(pos >= 0 && pos <= ps->size);
//插入的时候先检查空间够不够
SLCheckCapacity(ps);
for (int i = ps->size; i>pos; i--)
{
ps->arr[i] = ps->arr[i - 1];//当ps->arr[pos+1]=ps->arr[pos]时完毕
}
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->arr[size-2]=ps->arr[size-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;
}
void SLDestory(SL* ps)
{
if (ps->arr != NULL)
{
free(ps->arr);
ps->arr = NULL;
}
ps->size = 0;
ps->capacity = 0;
}
3.对于上面顺序表各种方法的测试，我们在test.c文件中进行测试：(注意：每写完一个方法就要马上进行调试测试，以确保方法中没有bug)
//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);
//头插
SLPushFront(&sl, 5);
SLPrint(sl);
SLPushFront(&sl, 6);
SLPrint(sl);
//尾删
SLPopBack(&sl);
SLPrint(sl);
SLPopBack(&sl);
SLPrint(sl);
//头删
SLPopFront(&sl);
SLPrint(sl);
SLPopFront(&sl);
SLPrint(sl);
SLPopFront(&sl);
SLPrint(sl);
SLPopFront(&sl);
SLPrint(sl);
//销毁顺序表
SLDestory(&sl);
}
void SLTest02()
{
SL sl;
SLInit(&sl);
//尾插
SLPushBack(&sl, 1);
SLPushBack(&sl, 2);
SLPushBack(&sl, 3);
SLPushBack(&sl, 4);
SLPrint(sl);
//在指定的位置之前插入数据
SLInsert(&sl, 0, 99);
SLPrint(sl);
SLInsert(&sl, sl.size, 100);
SLPrint(sl);
SLInsert(&sl, 2, 98);
SLPrint(sl);
//删除指定位置的数据
SLErase(&sl, 0);
SLPrint(sl);
SLErase(&sl, 2);
SLPrint(sl);
//顺序表的查找
int find = SLFind(&sl, 4);
if (find < 0)
{
printf("没有找到！\n");
}
else
{
printf("找到了，下标为%d\n", find);
}
//销毁顺序表
SLDestory(&sl);
}
int main()
{
SLTest01();
//SLTest02();
return 0;
}
代码库：Sequence_List
四、通讯录的实现
上面学习了有关顺序表的概念和顺序表中的各种增删查改方法的实现，现在基于顺序表的底层结构，我们来实现一个通讯录功能：
(1) 我们大致描述一下一个联系人的信息有姓名、性别、年龄、电话和地址这五个。那我们就可以使用结构体来描述一个联系人的数据。这样顺序表中arr指向的空间中存储的每个元素就是结构体类型。我们把通讯录各种增删查改方法的声明放在Contact.h的头文件中：
//Contact.h
#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#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];
}perInfo;
//前置声明(因为顺序表的定义在SeqList.h中,而头文件不能相互包含,所以要进行结构体的前置声明)
typedef struct SeqList Contact;
//1.通讯录的初始化
void ContactInit(Contact* con);
//2.通讯录联系人的添加
void ContactAdd(Contact* con);
//3.通讯录联系人的删除
void ContactDel(Contact* con);
//4.展示通讯录数据
void ContactShow(Contact* con);
//5.通讯录的修改
void ContactModify(Contact* con);
//6.查找联系人
void ContactFind(Contact* con);
//7.通讯录的销毁
void ContactDestory(Contact* con);
(2) 把通讯录方法的实现放在Contact.c的源文件中：(注意：通讯录的底层就是顺序表，所以要包含SeqList.h的头文件)
//Contact.c
#include"Contact.h"
#include"SeqList.h"
//保存联系人数据
void ContactSave(Contact* con)
{
//打开文件
FILE* Cpf = fopen("contact.txt", "wb");
if (Cpf == NULL)
{
perror("fopen fail!");
return 1;
}
//循环保存联系人数据到文件中
for (int i = 0; i < con->size; i++)
{
fprintf(Cpf, "%s %s %d %s %s\n", con->arr[i].name,
con->arr[i].gender,
con->arr[i].age,
con->arr[i].tel,
con->arr[i].addr
);
}
printf("通讯录数据保存成功！\n");
//关闭文件
fclose(Cpf);
Cpf = NULL;
}
//导入联系人数据到通讯录中
void ContactLoad(Contact* con)
{
//打开文件
FILE* Cpf = fopen("contact.txt", "rb");
if (Cpf == NULL)
{
perror("fopen fail!");
return 1;
}
//循环导入文件数据
perInfo info;
while (fscanf(Cpf, "%s %s %d %s %s", info.name, info.gender, &(info.age), info.tel, info.addr) != EOF)
{
SLPushBack(con, info);
}
printf("历史通讯录数据导入成功！\n");
//关闭文件
fclose(Cpf);
Cpf = NULL;
}
void ContactInit(Contact* con)
{
//通讯录的初始化即顺序表的初始化
SLInit(con);
//将历史数据导入通讯录中
ContactLoad(con);
}
void ContactAdd(Contact* con)
{
perInfo 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("要删除的联系人不存在！\n");
return;
}
//找到了要删除的联系人-->下标为find
SLErase(con, find);
printf("删除成功！\n");
}
void ContactShow(Contact* con)
{
//先打印表头
printf("%s %8s %8s %8s %8s\n", "姓名", "性别", "年龄", "电话", "地址");
//逐个打印联系人数据
for (int i = 0; i < con->size; i++)
{
printf("%-9s %-8s %-7d %-8s %-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];
printf("请输入要修改的联系人姓名:\n");
scanf("%s", name);
int find = FindByName(con, name);
if (find < 0)
{
printf("要修改的联系人数据不存在！\n");
return;
}
//要修改的联系人数据存在
printf("请输入新的姓名:\n");
scanf("%s", con->arr[find].name);
printf("请输入新的性别:\n");
scanf("%s", con->arr[find].gender);
printf("请输入新的年龄:\n");
scanf("%d", &con->arr[find].age);
printf("请输入新的电话:\n");
scanf("%s", con->arr[find].tel);
printf("请输入新的地址:\n");
scanf("%s", con->arr[find].addr);
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 %8s %8s %8s %8s\n", "姓名", "性别", "年龄", "电话", "地址");
printf("%-9s %-8s %-7d %-8s %-s\n", con->arr[find].name,
con->arr[find].gender,
con->arr[find].age,
con->arr[find].tel,
con->arr[find].addr
);
}
void ContactDestory(Contact* con)
{
//销毁通讯录之前要先保存通讯录中的数据，以防丢失
ContactSave(con);
//销毁通讯录
SLDestory(con);
}
(3) 我们在test.c的源文件中进行通讯录方法的测试：
//test.c
#include"SeqList.h"
//通讯录菜单
void menu()
{
printf("******************通讯录*******************\n");
printf("*********1.添加联系人 2.删除联系人*********\n");
printf("*********3.修改联系人 4.查找联系人*********\n");
printf("*********5.展示联系人 0. 退出 **********\n");
printf("*******************************************\n");
}
int main()
{
int option = -1;
Contact con;
ContactInit(&con);
do
{
menu();
printf("请选择您的操作:\n");
scanf("%d", &option);
switch (option)
{
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("退出通讯录！\n");
break;
default:
printf("输入错误，请重新输入！\n");
break;
}
} while (option != 0);
ContactDestory(&con);
return 0;
}
程序执行的过程如下：
代码库：Contact
1.顺序表的问题及思考
🍊(1) 中间/头部的插入删除，时间复杂度为O(N)
🍓(2) 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
🍑(3) 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
那上面的问题要如何解决呢? 对于顺序表链表的增容可能会出现空间过剩的情况，还可以再改进顺序表。等到后面学习链表的知识以后就能知道链表比起顺序表就没有增容的概念。
