🚩前言
在前面的文章中,写了关于C语言的各种知识点,也许内容不是很精炼,但对后面知识的学习还是有必要的。接下来就是用C语言实现数据结构的编程。
1. 数据结构的概念
我们从词组来看,数据结构就是两者组成,一是数据,二是结构。数据指的就是各种能表示对象的内容,比如C语言中用各种数据类型来表示标量的事物,比如价格、体重等,还有C语言中的自定义类型来表示各种具体的对象,比如学生对象等,这些都是数据。而结构就是把这些数据按照一定的规则存储起来,让数据内容在计算机中能有一定顺序结构的存储。
2. 数据结构的分类
今天所讲的名字叫做顺序表,它是属于线性结构的,用顺序存储的方式。底层是数组。
3. 顺序表
说白了,顺序表的底层就是数组,对数组的封装,实现增删查改的API;
3.1. 顺序表的分类
(1)静态顺序表
结构体定义如下:
#define N 10;//宏定义,方便修改数组的大小
typedef int DataType;//数据类型取别名
typedef struct SeqList
{
DataType elem[N];//此处就是一个整型数组,大小是固定的,定长数组。
int size;//表示该数组中的有效个数。
}SL;//用typedef给struct SeqList取别名。
//在后面用到就不用写struct SeqList,直接写SL;
图解如下:
静态顺序表的缺点:空间给多了造成浪费、空间给少了不够用!
(2)动态顺序表
结构体定义如下:
typedef int DataType;//数据类型取别名
typedef struct SeqList
{
DataType* elem;//此处变成指针,通过动态申请空间
int capacity;//表示申请的空间总大小,空间是可以增容的
int size;//表示该数组中的有效个数。
}SL;//用typedef给struct SeqList取别名。
图解如下:
动态的顺序表,就是要记住空间是动态申请的,到最后记得手动释放,free()释放函数
4. 动态顺序表实现
动态相比于静态的要复杂一点,此处就用动态的顺序表来详解。
4.1. 实现步骤
(1)框架结构
(2)SeqList.h头文件实现
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#define INIT_SIZE 2
//创建动态顺序表的结构体
typedef int DataType;
typedef struct SeqList
{
DataType* elem;
int capacity;
int size;
}SL;
//创建好后就初始化结构体
void init_seqlist(SL* sl);//初始化函数
void print_seqlist(SL sl);//打印函数
void PushBack(SL* sl, DataType data);//尾插函数
void PushFront(SL* sl, DataType data);//头插函数
void PopBack(SL* sl);//尾删函数
void PopFront(SL* sl);//头删函数
void InsertPosition(SL* ptr, int pos, DataType data);//指定位置插入数据函数
void DeletePosition(SL* ptr, int pos);//删除指定位置的元素
void ModifyPosition(SL* ptr, int pos, DataType data);//修改指定位置的数据
int FindPosition(SL ptr, DataType data);//查找函数
void DestroyCapacity(SL* ptr);//销毁函数
(3)SeqList.c源文件
①init_seqlist()初始化函数
//初始化函数
void init_seqlist(SL* sl)
{
assert(sl);
sl->elem = NULL;
sl->capacity = sl->size=0;
}
调试结果:
我们可以在初始化的时候就分配空间,代码如下:
//初始化函数
#define INIT_SIZE 2
void init_seqlist(SL* sl)
{
assert(sl);
sl->elem = (SL*)malloc(INIT_SIZE * sizeof(SL));
sl->capacity = INIT_SIZE;
sl->size = 0;
}
调试如下:
②print_seqlist()打印函数
//打印函数
void print_seqlist(SL sl)
{
if (sl.size == 0)
{
printf("顺序表内容为空,无法打印!\n");
return;
}
for (int i = 0; i < sl.size; i++)
{
printf("%d ",sl.elem[i]);
}
printf("\n");
}
由于打印函数不需要修改内容,所以不需要传递地址
③PushBack()尾插函数+图解
static check_capacity(SL* sl)
{
assert(sl);
//看空间里面实际的元素个数是否等于申请的空间大小,相等就说明满了;
if (sl->capacity == sl->size)
{
int new_capacity = sl->capacity == 0 ? 4 : 2 * sl->capacity;//以2倍数增容
DataType* temp = (DataType*)realloc(sl->elem, new_capacity * sizeof(DataType*));
if (temp == NULL)
{
perror("realloc fail");
exit(1);
}
//申请成功
sl->elem = temp;
sl->capacity = new_capacity;
}
}
//尾插函数
void PushBack(SL* sl, DataType data)
{
assert(sl);
//在插入的时候,必须判断空间是否满,是否需要扩容;
check_capacity(sl);
//插入数据
sl->elem[sl->size++] = data;
}
结果展示:
尾插图解
④PushFront()头插函数+图解
//头插函数
void PushFront(SL* sl, DataType data)
{
assert(sl);
//插入之前也是需要检测空间的
check_capacity(sl);
//插入,移动元素,从后往前移动
for (int i = sl->size; i > 0; i--)
{
sl->elem[i] = sl->elem[i - 1];
}
//第一个空出来后插入数据
sl->elem[0] = data;
sl->size++;
}
结果展示:
头插图解:
⑤PopBack()尾删函数+图解
//尾删函数
void PopBack(SL* sl)
{
assert(sl&&sl->size);//保证传入的空间有效和数据个数不为0
//尾删
sl->size--;
}
结果展示:
尾删图解:
⑥PopFront()头删函数+图解
//头删函数
void PopFront(SL* sl)
{
assert(sl && sl->size);
//头删
for (int i = 0; i < sl->size - 1; i++)
{
sl->elem[i] = sl->elem[i + 1];
}
sl->size--;
}
结果展示:
头删图解:
⑦DeletePosition()删除指定位置函数
//删除指定位置的元素
void DeletePosition(SL* sl, int pos)
{
assert(sl && sl->size);
assert(pos >= 0 && pos < sl->size);
for (int i = pos; i < sl->size; i++)
{
sl->elem[i] = sl->elem[i + 1];
}
sl->size--;
}
结果展示:
图解:
⑧InsertPosition()指定位置插入数据函数
//指定位置插入数据函数
void InsertPosition(SL* sl, int pos, DataType data)
{
assert(sl&&pos>=0&&pos<=sl->size);
//先移动位置,往后移动
//还得检查是否需要扩容
check_capacity(sl);
for (int i = sl->size; i > pos; i--)
{
sl->elem[i] = sl->elem[i - 1];
}
//位置空出来之后就加入数据
sl->elem[pos] = data;
//记得元素个数+1
sl->size++;
}
结果展示:
⑨ModifyPosition()修改指定位置数据函数
//修改指定位置的数据
void ModifyPosition(SL* sl, int pos, DataType data)
{
assert(sl&&pos>=0&&pos<sl->size);
//现找到修改数据的位置
for (int i = 0; i < sl->size; i++)
{
if (i == pos)
{
//修改
sl->elem[i] = data;
}
}
}
结果展示:
⑩FindPosition()查找函数
//查找函数
int FindPosition(SL sl, DataType data)
{
if (sl.size == 0)
{
printf("数据内容为空,无法查找!\n");
exit(1);
}
for (int i = 0; i < sl.size; i++)
{
if (sl.elem[i] == data)
{
return i;
}
}
return -1;
}
结果展示:
🚀DestroyCapacity()销毁函数
//销毁函数
void DestroyCapacity(SL* sl)
{
if (sl->elem != NULL)
{
free(sl->elem);
}
sl->elem = NULL;
sl->capacity = sl->size = 0;
}
调试结果:
5. 完整代码
SeqList.h
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#define INIT_SIZE 2
//创建动态顺序表的结构体
typedef int DataType;
typedef struct SeqList
{
DataType* elem;
int capacity;
int size;
}SL;
//创建好后就初始化结构体
void init_seqlist(SL* sl);//初始化函数
void print_seqlist(SL sl);//打印函数
void PushBack(SL* sl, DataType data);//尾插函数
void PushFront(SL* sl, DataType data);//头插函数
void PopBack(SL* sl);//尾删函数
void PopFront(SL* sl);//头删函数
void InsertPosition(SL* sl, int pos, DataType data);//指定位置插入数据函数
void DeletePosition(SL* sl, int pos);//删除指定位置的元素
void ModifyPosition(SL* sl, int pos, DataType data);//修改指定位置的数据
int FindPosition(SL sl, DataType data);//查找函数
void DestroyCapacity(SL* sl);//销毁函数
SeqList.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"
//打印函数
void print_seqlist(SL sl)
{
if (sl.size == 0)
{
printf("顺序表内容为空,无法打印!\n");
return;
}
for (int i = 0; i < sl.size; i++)
{
printf("%d ",sl.elem[i]);
}
printf("\n");
}
//初始化函数
void init_seqlist(SL* sl)
{
assert(sl);
sl->elem = NULL;
sl->capacity = sl->size=0;
/*assert(sl);
sl->elem = (SL*)malloc(INIT_SIZE * sizeof(SL));
sl->capacity = INIT_SIZE;
sl->size = 0;*/
}
static check_capacity(SL* sl)
{
assert(sl);
//看空间里面实际的元素个数是否等于申请的空间大小,相等就说明满了;
if (sl->capacity == sl->size)
{
int new_capacity = sl->capacity == 0 ? 4 : 2 * sl->capacity;//以2倍数增容
DataType* temp = (DataType*)realloc(sl->elem, new_capacity * sizeof(DataType*));
if (temp == NULL)
{
perror("realloc fail");
exit(1);
}
//申请成功
sl->elem = temp;
sl->capacity = new_capacity;
}
}
//尾插函数
void PushBack(SL* sl, DataType data)
{
assert(sl);
//在插入的时候,必须判断空间是否满,是否需要扩容;
check_capacity(sl);
//插入数据
sl->elem[sl->size++] = data;
}
//头插函数
void PushFront(SL* sl, DataType data)
{
assert(sl);
//插入之前也是需要检测空间的
check_capacity(sl);
//插入,移动元素,从后往前移动
for (int i = sl->size; i > 0; i--)
{
sl->elem[i] = sl->elem[i - 1];
}
//第一个空出来后插入数据
sl->elem[0] = data;
sl->size++;
}
//尾删函数
void PopBack(SL* sl)
{
assert(sl&&sl->size);//保证传入的空间有效和数据个数不为0
//尾删
sl->size--;
}
//头删函数
void PopFront(SL* sl)
{
assert(sl && sl->size);
//头删
for (int i = 0; i < sl->size - 1; i++)
{
sl->elem[i] = sl->elem[i + 1];
}
sl->size--;
}
//删除指定位置的元素
void DeletePosition(SL* sl, int pos)
{
assert(sl && sl->size);
assert(pos >= 0 && pos < sl->size);
for (int i = pos; i < sl->size-1; i++)
{
sl->elem[i] = sl->elem[i + 1];
}
sl->size--;
}
//指定位置插入数据函数
void InsertPosition(SL* sl, int pos, DataType data)
{
assert(sl&&pos>=0&&pos<=sl->size);
//先移动位置,往后移动
//还得检查是否需要扩容
check_capacity(sl);
for (int i = sl->size; i > pos; i--)
{
sl->elem[i] = sl->elem[i - 1];
}
//位置空出来之后就加入数据
sl->elem[pos] = data;
//记得元素个数+1
sl->size++;
}
//修改指定位置的数据
void ModifyPosition(SL* sl, int pos, DataType data)
{
assert(sl&&pos>=0&&pos<sl->size);
//现找到修改数据的位置
for (int i = 0; i < sl->size; i++)
{
if (i == pos)
{
//修改
sl->elem[i] = data;
}
}
}
//查找函数
int FindPosition(SL sl, DataType data)
{
if (sl.size == 0)
{
printf("数据内容为空,无法查找!\n");
exit(1);
}
for (int i = 0; i < sl.size; i++)
{
if (sl.elem[i] == data)
{
return i;
}
}
return -1;
}
//销毁函数
void DestroyCapacity(SL* sl)
{
if (sl->elem != NULL)
{
free(sl->elem);
}
sl->elem = NULL;
sl->capacity = sl->size = 0;
}
test.c
#define _CRT_SECUR_NO_WARNINGS 1
#include"SeqList.h"
void test01()
{
SL sl;
init_seqlist(&sl);//此处记得传地址。
//尾插
PushBack(&sl, 1);
PushBack(&sl, 2);
PushBack(&sl, 3);
PushBack(&sl, 4);
print_seqlist(sl);
//头插
PushFront(&sl, 5);
print_seqlist(sl);
/*PushFront(&sl, 6);
print_seqlist(sl);*/
尾删
//PopBack(&sl);
//print_seqlist(sl);
//PopBack(&sl);
//print_seqlist(sl);
//头删
/*PopFront(&sl);
print_seqlist(sl);
PopFront(&sl);
print_seqlist(sl);*/
//指定位置删除
/*printf("删除下标为2的数据:\n");
DeletePosition(&sl,2);
print_seqlist(sl);*/
//指定位置插入数据
/*printf("在下标为2的位置插入100数据:\n");
InsertPosition(&sl,2,100);
print_seqlist(sl);*/
修改
//printf("修改下标为3的数据:\n");
//ModifyPosition(&sl,3,666);
//print_seqlist(sl);
//查找
printf("查找数据为2的位置:\n");
int ret=FindPosition(sl, 2);
if (ret == -1)
{
printf("没找到!\n");
}
else
{
printf("找到了,在下标为%d位置处!",ret);
}
DestroyCapacity(&sl);
}
int main()
{
test01();//函数测试
return 0;
}
顺序表内容到此为止,蟹蟹: