目录
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 3SLDestroy(&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 4SLInsert(&sl, sl.size, 88);SLPrint(sl);//99 1 2 3 4 88SLInsert(&sl, 3, 88);SLPrint(sl);//99 1 2 88 3 4 88SLErase(&sl, 0);SLPrint(sl);//1 2 88 3 4 88printf("%d",SLFind(&sl, 88));//2SLDestroy(&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 100typedef 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. 顺序表的问题及思考
- 中间/头部的插入删除,时间复杂度为O(N)
- 增容需要申请新空间,拷贝数据,释放旧空间,会有不小消耗
- 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到200,我们再继续插入5个数据,后面就没有数据插入了,那么就浪费了95个数据空间