数据结构之动态顺序表（附带完整程序）

  • 阿里云国际版折扣https://www.yundadi.com

    • 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6

    基本概念

    一.线性表、顺序表的定义

    ☀️1线性表

    是n个具有相同特性的数据元素的有限序列。线性表在逻辑上是线性结构但在物理上存储时通常以数组和链式结构的形式存储。

    ☀️2顺序表

    顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。在数组上完成数据的增删查改。

    二.顺序表的分类

    ☀️1静态顺序表

    1.概念使用定长数组存储元素
    2.定义方法数组使用方括号法例如

    typedef struct
{
	int age;
	int height;
	double weight;
}Student;
typedef struct
{
	Student stu[100];//Student类型的数组
	int length;//元素的有效个数
	int listsize;//最多容纳多少个元素
}SqList;

    3.缺陷方括号[ ]内只能是定值一旦定义了大小就不可改变

    ☀️2动态顺序表

    1.概念使用动态开辟的数组存储元素
    2.定义方法用指针指向数组例如

    typedef struct
{
	int age;
	int height;
	double weight;
}Student;
typedef struct
{
	Student* stu;//Student类型的数组
	int length;//元素的有效个数
	int listsize;//最多容纳多少个元素
}SqList;

    3.相较于静态顺序表动态顺序表可以改变数组大小更合理的利用空间

    动态顺序表相关操作函数

    为方便理解以一个学生信息表为例。最开始先开辟5个结构体大小的位置如果后面不够则每次多开辟2个位置学生信息由年龄、身高、体重3个数据组成。

    定义部分

    #define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#define LIST_INIT_SIZE 5
#define INCREASE 2
typedef struct
{
	int age;
	int height;
	double weight;
}Student;
typedef struct
{
	Student* stu;//Student类型的数组
	int length;//元素的有效个数
	int listsize;//最多容纳多少个元素
}SqList;

    一.初始化顺序表

    int InitList(SqList* L)
{
	//1.申请空间
	L->stu = (Student*)malloc(LIST_INIT_SIZE * sizeof(Student));
	//2.判断是否申请成功
	if (!L->stu)
		exit(-1);//exit(-1)表示退出程序
	//3.如果拿到了内存空间就初始化顺序表
	L->length = 0;
	L->listsize = LIST_INIT_SIZE;
	return 1;
}

    步骤
    1.用malloc申请空间
    2.判断是否申请成功
    补exit和return的区别exit(-1)表示终止程序而return只是结束当下函数
    3.如果拿到了内存空间就初始化顺序表
    length表示有效元素个数目前为0listsize表示数组当前最大容量假设初始最大容量LIST_INIT_SIZE为5

    二.销毁顺序表

    int DeleteList(SqList* L)
{
	//1.判断顺序表是否存在
	if (L->stu == NULL)//说明不存在
		return 0;//不可以解引用NULL
	//2.如果存在则释放对应的内存
	free(L->stu);
	L->stu = NULL;
	//3.释放内存后恢复表的初始值
	L->length = 0;
	L->listsize = 0;
	return 1;
}

    步骤
    1.判断顺序表是否存在
    如果不存在直接退出程序没必要进行后续操作
    2.如果存在则释放对应的内存
    注好习惯是只要用完free就将指针置为NULL
    3.释放内存后恢复表的初始值

    三.辅助操作函数

    以下两个函数是增删查改过程中频繁用到的操作为防止代码冗余将重复工作的代码封装成相应的两个函数

    ☀️1元素复制函数CopyValue

    //元素复制
void CopyValue(Student* s1, Student* s2)
{
	s1->age = s2->age;
	s1->height = s2->height;
	s1->weight = s2->weight;
}

    注需要传两组数据的地址因为形参的改变不影响实参
    s1是元素复制后的位置s2是元素复制前的位置

    ☀️2输入信息函数Print

    void Print(Student* onestu)
{
	printf("请输入\n");
	printf("年龄");
	scanf("%d", &onestu->age);
	printf("身高");
	scanf("%d", &onestu->height);
	printf("体重");
	scanf("%lf", &onestu->weight);
}

    在首次大规模插入信息、插入单个信息、查找信息、改动信息等时候都需要输入信息

    四.增扩大顺序表长度

    //扩大数组长度
void ExpandList(SqList* L)
{
	//1.申请内存
	Student* p = (Student*)realloc(L->stu, (L->listsize + INCREASE) * sizeof(Student));
	//2.判断是否申请成功
	if (!p)
		exit(-1);
	//3.如果申请到了内存更新顺序表的信息包括学生数组、最大容纳学生量
	L->stu = p;
	L->listsize += INCREASE;
}

    步骤
    1.申请内存
    由于初始化时已经由malloc初次申请了部分空间以后每次增加空间都是在初始基础上增加因此用realloc来扩大顺序表。
    realloc使用时的注意事项
    ①realloc的第二个参数不是增加了多少空间而是要扩大至多大的空间即整个大空间的大小
    ②用一个新的Student类型的指针接收realloc的返回值当返回值不为NULL时再将值赋给指向数组的指针L->stu
    2.判断是否申请成功
    3.如果申请到了内存更新顺序表的信息包括学生数组位置、最大容纳学生量

    ☀️1对顺序表大规模插入信息

    int InsertValue(SqList* L, int n)
{
	//1.确保有足够空间存放信息
	while (L->listsize < n)
	{
		ExpandList(L);
		if (L->listsize >= n)
			break;
	}
	//2.有足够空间开始插入信息
	for (int i = 0;i < n;i++)
	{
		Print(&L->stu[i]);
		printf("已成功增加一组信息\n");
		L->length++;
	}
	return 1;
}

    步骤
    1.确保有足够空间存放信息
    2.有足够空间开始插入信息

    ☀️2在顺序表尾部插入元素

    //在顺序表尾部插入元素
void InsertLastList(SqList* L, Student* onestu)
{
	//1.判断数组满没满满就扩大数组长度
	if (L->length >= L->listsize)
		ExpandList(L);
	//2.有足够空间在尾部插入新元素将新元素拷贝到数组末尾
	CopyValue(&L->stu[L->length], onestu);
	//3.更新学生数量
	L->length++;
}

    第二个参数onestu是被插入的信息
    步骤
    1.判断数组满没满满就用ExpandList函数扩大数组长度。
    2.有足够空间在尾部插入新元素将新元素拷贝到数组末尾
    3.更新学生数量

    ☀️3在顺序表头部插入元素

    //在顺序表头部插入元素
void InsertFirstList(SqList* L, Student* onestu)
{
	//1.判断数组满没满满就扩大数组长度
	if (L->length >= L->listsize)
		ExpandList(L);
	//2.有足够空间先将所有元素向后挪动1位
	//  从后往前挪要不然会被覆盖
	for (int i = L->length-1;i>=0;i--)
	{
		CopyValue(&L->stu[i + 1], &L->stu[i]);
	}
	//3.将新元素拷贝到数组开头
	CopyValue(&L->stu[0], onestu);
	//4.更新学生数量
	L->length++;
}

    第二个参数onestu是被插入的信息
    步骤
    1.判断数组满没满满就用ExpandList函数扩大数组长度。
    2.有足够空间先将所有元素向后挪动1位。
    注要从最后一个元素开始往前挪如果从前往后挪的话会将数组中的所有元素全部覆盖成第一个元素。
    3.将新元素拷贝到数组开头
    4.更新学生数量

    ☀️4在顺序表指定位置插入元素

    //在顺序表指定位置插入元素
int InsertLocList(SqList* L, int i, Student* onestu)
{
	//1.判断位置是否合法
	if (i < 0 || i >= L->length)
	{
		return 0;
	}
	//2.判断数组是否有空位没有的话扩容
	if (L->length == L->listsize)
	{
		ExpandList(L);
	}
	//3.将插入点及后面的元素向后移动1位
	for (int j = L->length - 1;j >= i;j--)//j>=i+1
	{
		//注1要从数组的最后一个元素依次向后挪动1位如果从插入点
		//     开始挪动的话数组原先的内容会被覆盖
		//注2j必须要能等于i因为i是插入点要连同插入点往后挪1位
		CopyValue(&L->stu[j + 1], &L->stu[j]);
	}
	//4.插入元素
	CopyValue(&L->stu[i], onestu);
	//5.更新表中的信息
	L->length++;
	return 1;
}

    第二个参数onestu是被插入的信息
    步骤
    1.判断位置是否合法
    2.判断数组是否有空位没有的话扩容
    3.将插入点及后面的元素向后移动1位
    注
    ①要从数组的最后一个元素依次向后挪动1位如果从插入点开始挪动的话数组原先的内容会被覆盖
    ②j必须要能等于i因为i是插入点要连同插入点往后挪1位
    4.插入元素
    5.更新表中的信息

    五.删删除顺序表中的信息

    void DropOneValue(SqList*L,Student* onestu4)
{
	//1.判断是否有该组数据
	int ret = FindOneList(L, onestu4);
	if (ret == -1)
	{
		printf("没有该信息\n");
		return;
	}
	//2.进行删除
	for (int i = ret + 1;i <= L->length - 1;i++)
	{
		CopyValue(&L->stu[i - 1], &L->stu[i]);
	}
	printf("删除成功\n");
	//3.成员数量信息变动
	L->length--;
}

    第二个参数onestu4是要被删除的信息
    步骤
    1.判断是否有该组数据
    2.有信息的话进行删
    将删除点后面的所有元素向前挪动1位
    3.成员数量信息变动

    六.查查找顺序表中的某个元素

    int FindOneList(SqList* L, Student* onestu3)
{
	int i = 0;
	while (i < L->length)
	{
		if ((L->stu[i].age == onestu3->age)
			&& (L->stu[i].height == onestu3->height)
			&& (L->stu[i].weight == onestu3->weight))
		return i;
		i++;
	}
	return -1;
}

    第二个参数onestu3是被查找的信息
    1.找到的话返回这个元素在数组中的下标找不到的话返回-1为什么不返回0因为下标也有可能是0
    2.需要增加一组Student类型的数据作为对照信息你肯定要先告诉我你要找的人的信息我才能找到这个人存不存在、存在的话是几号

    七.改改变顺序表中某元素信息

    void ModifyOneValue(SqList* L, Student* onestu5, Student* onestu6)
{
	//1.判断该信息是否存在
	int ret=FindOneList(L, onestu5);
	if (ret == -1)
	{
		printf("没有该信息\n");
		return;
	}
	//2.信息存在进行修改
	printf("请输入修改后信息\n");
	Print(onestu6);
	CopyValue(&L->stu[ret], onestu6);
}

    参数二onestu5是改变前的信息第三个参数onestu6是改变后的信息
    步骤
    1.判断该信息是否存在
    2.信息存在进行修改

    八.遍历顺序表打印出所有元素

    //遍历顺序表
void FindAllList(SqList* L)
{
	int i = 0;
	for (i = 0;i < L->length;i++)
	{
		printf("age=%d,height=%d,weight=%lf\n", L->stu[i].age,
			L->stu[i].height, L->stu[i].weight);
	}
}

    用动态顺序表实现学生信息操作程序

    完整程序连着的三部分

    一.声明与定义

    #define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#define LIST_INIT_SIZE 5
#define INCREASE 2
typedef struct
{
	int age;
	int height;
	double weight;
}Student;
typedef struct
{
	Student* stu;//Student类型的数组
	int length;//元素的有效个数
	int listsize;//最多容纳多少个元素
}SqList;

    二.被调用函数

    //初始化顺序表
int InitList(SqList* L)
{
	//1.申请空间
	L->stu = (Student*)malloc(LIST_INIT_SIZE * sizeof(Student));
	//2.判断是否申请成功
	if (!L->stu)
		exit(-1);//exit(-1)表示退出程序
	//3.如果拿到了内存空间就初始化顺序表
	L->length = 0;
	L->listsize = LIST_INIT_SIZE;
	return 1;
}
//销毁顺序表
int DeleteList(SqList* L)
{
	//1.判断顺序表是否存在
	if (L->stu == NULL)//说明不存在
		return 0;//不可以解引用NULL
	//2.如果存在则释放对应的内存
	free(L->stu);
	L->stu = NULL;
	//3.释放内存后恢复表的初始值
	L->length = 0;
	L->listsize = 0;
	return 1;
}
//遍历顺序表
void FindAllList(SqList* L)
{
	int i = 0;
	for (i = 0;i < L->length;i++)
	{
		printf("age=%d,height=%d,weight=%lf\n", L->stu[i].age,
			L->stu[i].height, L->stu[i].weight);
	}
}
//查找学生数组中的某个元素,找到返回元素对应下标找不到返回0
int FindOneList(SqList* L, Student* onestu3)
{
	int i = 0;
	while (i < L->length)
	{
		if ((L->stu[i].age == onestu3->age)
			&& (L->stu[i].height == onestu3->height)
			&& (L->stu[i].weight == onestu3->weight))
		return i;
		i++;
	}
	return -1;
}
//扩大数组长度
void ExpandList(SqList* L)
{
	//1.申请内存
	Student* p = (Student*)realloc(L->stu, (L->listsize + INCREASE) * sizeof(Student));
	//2.判断是否申请成功
	if (!p)
		exit(-1);
	//3.如果申请到了内存更新顺序表的信息包括学生数组、最大容纳学生量
	L->stu = p;
	L->listsize += INCREASE;
}
//元素复制
void CopyValue(Student* s1, Student* s2)
{
	s1->age = s2->age;
	s1->height = s2->height;
	s1->weight = s2->weight;
}
//在顺序表尾部插入元素
void InsertLastList(SqList* L, Student* onestu)
{
	//1.判断数组满没满满就扩大数组长度
	if (L->length >= L->listsize)
		ExpandList(L);
	//2.有足够空间在尾部插入新元素将新元素拷贝到数组末尾
	CopyValue(&L->stu[L->length], onestu);
	//3.更新学生数量
	L->length++;
}
//在顺序表头部插入元素
void InsertFirstList(SqList* L, Student* onestu)
{
	//1.判断数组满没满满就扩大数组长度
	if (L->length >= L->listsize)
		ExpandList(L);
	//2.有足够空间先将所有元素向后挪动1位
	//  从后往前挪要不然会被覆盖
	for (int i = L->length-1;i>=0;i--)
	{
		CopyValue(&L->stu[i + 1], &L->stu[i]);
	}
	//3.将新元素拷贝到数组开头
	CopyValue(&L->stu[0], onestu);
	//4.更新学生数量
	L->length++;
}
//在顺序表指定位置插入元素
int InsertLocList(SqList* L, int i, Student* onestu)
{
	//1.判断位置是否合法
	if (i < 0 || i >= L->length)
	{
		return 0;
	}
	//2.判断数组是否有空位没有的话扩容
	if (L->length == L->listsize)
	{
		ExpandList(L);
	}
	//3.将插入点及后面的元素向后移动1位
	for (int j = L->length - 1;j >= i;j--)//j>=i+1
	{
		//注1要从数组的最后一个元素依次向后挪动1位如果从插入点
		//     开始挪动的话数组原先的内容会被覆盖
		//注2j没必要等于ij--时值为i-1会把插入点之前的值也往后移动1位
		CopyValue(&L->stu[j + 1], &L->stu[j]);
	}
	//4.插入元素
	CopyValue(&L->stu[i], onestu);
	//5.更新表中的信息
	L->length++;
	return 1;
}
//提示输入信息
void Print(Student* onestu)
{
	printf("请输入\n");
	printf("年龄");
	scanf("%d", &onestu->age);
	printf("身高");
	scanf("%d", &onestu->height);
	printf("体重");
	scanf("%lf", &onestu->weight);
}
//大规模插入数据
int InsertValue(SqList* L, int n)
{
	//1.确保有足够空间存放信息
	while (L->listsize < n)
	{
		ExpandList(L);
		if (L->listsize >= n)
			break;
	}
	//2.有足够空间开始插入信息
	for (int i = 0;i < n;i++)
	{
		Print(&L->stu[i]);
		printf("已成功增加一组信息\n");
		L->length++;
	}
	return 1;
}
//删除一个元素一组学生信息
void DropOneValue(SqList*L,Student* onestu4)
{
	//1.判断是否有该组数据
	int ret = FindOneList(L, onestu4);
	if (ret == -1)
	{
		printf("没有该信息\n");
		return;
	}
	//2.有信息的话进行删除
	for (int i = ret + 1;i <= L->length - 1;i++)
	{
		CopyValue(&L->stu[i - 1], &L->stu[i]);
	}
	printf("删除成功\n");
	//3.成员数量信息变动
	L->length--;
}
//更改一个元素一组学生信息
void ModifyOneValue(SqList* L, Student* onestu5, Student* onestu6)
{
	//1.判断该信息是否存在
	int ret=FindOneList(L, onestu5);
	if (ret == -1)
	{
		printf("没有该信息\n");
		return;
	}
	//2.信息存在进行修改
	printf("请输入修改后信息\n");
	Print(onestu6);
	CopyValue(&L->stu[ret], onestu6);
}

    三.主函数

    int main()
{
	//1.创建变量
	SqList L;
	Student onestu, onestu2,onestu3,
	onestu4,onestu5,onestu6,onestu7;
	//2.初始化初步申请空间
	InitList(&L);
	//3.初步整体性插入学生信息
	printf("1.整体插入信息\n");
	int n = 0;
	printf("请输入学生个数\n");
	scanf("%d", &n);
	InsertValue(&L, n);
	//4.在末尾处插入学生信息
	printf("2.在数组末尾处插入学生信息\n");
	Print(&onestu);
	InsertLastList(&L, &onestu);
	//5.在开头处插入学生信息
	printf("3.在数组开头处插入学生信息\n");
	Print(&onestu7);
	InsertFirstList(&L, &onestu7);
	//6.在指定位置插入学生信息
	printf("4.在指定位置处插入学生信息\n");
	printf("请输入要插入的位置");
	int i = 0;
	scanf("%d", &i);
	Print(&onestu2);
	InsertLocList(&L, i, &onestu2);
	//7.查找学生数组中的某个元素
	printf("5.查找某名学生\n");
	Print(&onestu3);
	int ret = FindOneList(&L, &onestu3);
	if (ret == 0)
		printf("没有该名学生\n");
	else
		printf("该名学生的编号是%d\n", ret);
	//8.删除表中元素
	printf("6.删除表中一组信息\n");
	printf("请输入要删除的学生信息:\n");
	Print(&onestu4);
	DropOneValue(&L, &onestu4);
	//9.修改信息
	printf("7.修改表中信息\n");
	printf("请输入被修改学生信息\n");
	Print(&onestu5);
	ModifyOneValue(&L, &onestu5, &onestu6);
	//10.展示最终顺序表所有插入的信息
	printf("8.展示最终学生信息表\n");
	FindAllList(&L);
	//10.释放空间
	DeleteList(&L);
}

    运行结果

    我在输入学生信息的时候用数字代替了
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    感谢浏览如有错误请及时指正❤️

  • 阿里云国际版折扣https://www.yundadi.com

    • 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6
    返回列表

    上一篇：数据库原理1——《小猫猫大课堂》数据库原理篇

    下一篇：驱动开发 day3 (模块化驱动启动led,蜂鸣器,风扇,震动马达)

    “数据结构之动态顺序表（附带完整程序）” 的相关文章

    ML LightGBM详细原理讲解+面试必考知识点1年前 (2023-02-02)
    跨域：后端工程师最熟悉的陌生“人”1年前 (2023-02-02)
    算法学习笔记(8.1): 网络最大流算法 EK, Dinic, ISAP1年前 (2023-02-02)
    你可能不知道的20个Git命令，但真的很实用1年前 (2023-02-02)
    Numpy基本使用方法1年前 (2023-02-02)
    《RPC实战与核心原理》学习笔记Day31年前 (2023-02-02)
    8、CSS权威指南--第四章（p121）值和单位1年前 (2023-02-02)
    Laravel + Vue 3（Vite、TypeScript）SPA 设置1年前 (2023-02-02)
    学习ASP.NET Core Blazor编程系列二十二——登录（1）1年前 (2023-02-02)
    分布式协议与算法-Quorum NWR1年前 (2023-02-02)

    阿里云国际版