当前位置：首页 » 《资源分享》 » 正文

数据结构：顺序表实现增删查改基本功能_lxkeepcoding的博客

11 人参与  2021年10月17日 10:23  分类 : 《资源分享》  评论

点击全文阅读


目录

  • 前言
  • 1. 顺序表概念及结构
  • 2. 静态顺序表的实现
    • 2.1 创建静态顺序表工程
    • 2.2 定义结构体
    • 2.3 初始化顺序表
      • 2.3.1 SeqList.h 声明接口
      • 2.3.2 SeqList.c 定义函数
    • 2.4 顺序表增加操作
      • 2.4.1 SeqList.h 声明接口
      • 2.4.2 SeqList.c 定义函数
    • 2.5 顺序表的删除操作
      • 2.5.1 SeqList.h 声明接口
      • 2.5.2 SeqList.c 定义函数
    • 2.6 顺序表查找操作
      • 2.6.1 SeqList.h 声明接口
      • 2.6.2 SeqList.c 定义函数
    • 2.7 顺序表修改操作
      • 2.7.1 SeqList.h 声明接口
      • 2.7.2 SeqList.c 定义函数
    • 2. 8 完整代码实现及运行测试
      • 2.8.1 SeqList.h
      • 2.8.2 SeqList.c
      • 2.8.3 test.c
      • 2.8.4 运行测试
  • 3. 动态顺序表的实现
    • 3.1 创建动态顺序表工程
    • 3.2 定义结构体
    • 3.3 初始化和释放顺序表
      • 3.3.1 SeqList.h 声明接口
      • 3.3.2 SeqList.c 定义函数
      • 3.3.3 加入断言完善
    • 3. 4 容量检查操作
      • 3.4.1 SeqList.h 声明接口
      • 3.4.2 SeqList.c 定义函数
    • 3. 5 顺序表增加操作
      • 3.5.1 SeqList.h 声明接口
      • 3.5.2 SeqList.c 定义函数
    • 3.6 顺序表删除操作
      • 3.6.1 SeqList.h 声明接口
      • 3.6.2 SeqList.c 定义函数
    • 3.7 顺序表查找查找
      • 3.7.1 SeqList.h 声明接口
      • 3.7.2 SeqList.c 定义函数
    • 3.8 顺序表修改操作
      • 3.8.1 SeqList.h 声明接口
      • 3.8.2 SeqList.c 定义函数
    • 3.9 完整代码展示及运行
      • 3.9.1 SeqList.h
      • 3.9.2 SeqList.c
      • 3.9.3 test.c
      • 3.9.4 运行测试
  • 后记

前言

写了很久C++的博客，数据结构方面的除了之前的两篇很久没有更新了，最近打算重新捡起来数据结构方面的博客，之前的博客中已经有介绍过顺序表和链表的文章，（数据结构——红玫瑰与白玫瑰之争）但是回头再看时，感觉还是有很多不足，于是决定重新写一下，希望可以达到更完美的效果。当然，文章仍会有许多不足，也欢迎大家批评指正。

1. 顺序表概念及结构

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

  1. 静态顺序表：使用定长数组存储。
  2. 动态顺序表：使用动态开辟的数组存储。

2. 静态顺序表的实现

2.1 创建静态顺序表工程

我们的工程采用多文件方式，分别为SeqList.h,SeqList.c,和test.c。
在这里插入图片描述

2.2 定义结构体

#define N 100//宏定义

typedef int SLDataType;

typedef struct SeqList
{
	SLDataType  _a[N];//定长数组
	size_t _size;//有效数据个数
}SeqList;

在静态顺序表的结构体定义中，我们用define定义了N，然后定义了_a[N]作为定长数组，而_size用来表示有效数据个数。我们用size_t,定义有效数据个数，size_t是定义无符号整形的，表示范围很大。为了使代码修改起来更加方便，我们采用typedef给int类型取别名为SLDataType，这样当我们想把int型换成其他类型时，只需要修改一初就好啦。同样地，我们将结构体起别名，为了在接下来的代码中写起来更方便。

2.3 初始化顺序表

2.3.1 SeqList.h 声明接口

//初始化
void SeqListInit(SeqList *seq);

2.3.2 SeqList.c 定义函数


//初始化
void SeqListInit(SeqList *seq)
{
	seq->_size = 0;
}

2.4 顺序表增加操作

2.4.1 SeqList.h 声明接口

//尾插
void SeqListPushBack(SeqList *seq, SLDataType x);
//头插
void SeqListPushFront(SeqList *seq, SLDataType x);

2.4.2 SeqList.c 定义函数

//头插
void SeqListPushFront(SeqList *seq, SLDataType x)
{
	if (seq->_size >= N)
	{
		return;
	}
	int end= seq->_size - 1;
	while (end >= 0)
	{
		seq->_a[end + 1] = seq->_a[end];
		end--;
	}
	seq->_a[0] = x;
	seq->_size++;
}
//尾插
void SeqListPushBack(SeqList *seq, SLDataType x)
{
	if (seq->_size >= N)
	{
		return;
	}
	seq->_a[seq->_size] = x;
	seq->_size++;
}

注意，要验证容量是不是已经满了。

2.5 顺序表的删除操作

2.5.1 SeqList.h 声明接口

//头删
void SeqListPopFront(SeqList *seq);
//尾删
void SeqListPopBack(SeqList *seq);

2.5.2 SeqList.c 定义函数

//头删
void SeqListPopFront(SeqList *seq)
{
	if (seq->_size == 0)
	{
		return;
	}
	for (int i = 1; i < seq->_size; i++)
	{
		seq->_a[i - 1] = seq->_a[i];
	}
	seq->_size--;
}
//尾删
void SeqListPopBack(SeqList *seq)
{
	if (seq->_size == 0)
	{
		return;
	}
	seq->_size--;
}

注意要检查此时顺序表是否为空。

2.6 顺序表查找操作

2.6.1 SeqList.h 声明接口

//查找
int SeqListSearch(SeqList *seq, SLDataType x);

2.6.2 SeqList.c 定义函数

//查找
int SeqListSearch(SeqList *seq, SLDataType x)
{
	for (int i = 0; i < seq->_size; i++)
	{
		if (seq->_a[i] == x)
		{
			return i;
		}
	}
	return -1;
}

在这里，我们令找到之后返回的是下标。

2.7 顺序表修改操作

2.7.1 SeqList.h 声明接口

//修改
void SeqListModify(SeqList *seq, int pos,SLDataType x);

这里的三个参数分别为顺序表结构体、要修改的位置和修改后的值。

2.7.2 SeqList.c 定义函数

//修改
void SeqListModify(SeqList *seq, int pos,SLDataType x)
{
	if (pos >= 0 && pos < seq->_size)
	{
		seq->_a[pos] = x;
	}
	else
	{
		printf("该位置不存在\n");
	}
}

注意要检查这个位置是不是合法的。

2. 8 完整代码实现及运行测试

2.8.1 SeqList.h

#include<stdio.h>


#define N 100
typedef int SLDataType;
typedef struct SeqList
{
	SLDataType _a[N];
	size_t _size;
}SeqList;


//初始化
void SeqListInit(SeqList *seq);

//打印
void SeqListShow(SeqList *seq);

//头插
void SeqListPushFront(SeqList *seq,SLDataType x);
//尾插
void SeqListPushBack(SeqList *seq, SLDataType x);

//头删
void SeqListPopFront(SeqList *seq);
//尾删
void SeqListPopBack(SeqList *seq);

//查找
int SeqListSearch(SeqList *seq, SLDataType x);

//修改
void SeqListModify(SeqList *seq, int pos,SLDataType x);

2.8.2 SeqList.c

#include"SeqList.h"

//初始化
void SeqListInit(SeqList *seq)
{
	seq->_size = 0;
}

//打印
void SeqListShow(SeqList *seq)
{
	for (int i = 0; i < seq->_size; i++)
	{
		printf("%d  ", seq->_a[i]);
	}
	printf("\n");
}

//头插
void SeqListPushFront(SeqList *seq, SLDataType x)
{
	if (seq->_size >= N)
	{
		return;
	}
	int end= seq->_size - 1;
	while (end >= 0)
	{
		seq->_a[end + 1] = seq->_a[end];
		end--;
	}
	seq->_a[0] = x;
	seq->_size++;
}
//尾插
void SeqListPushBack(SeqList *seq, SLDataType x)
{
	if (seq->_size >= N)
	{
		return;
	}
	seq->_a[seq->_size] = x;
	seq->_size++;
}

//头删
void SeqListPopFront(SeqList *seq)
{
	if (seq->_size == 0)
	{
		return;
	}
	for (int i = 1; i < seq->_size; i++)
	{
		seq->_a[i - 1] = seq->_a[i];
	}
	seq->_size--;
}
//尾删
void SeqListPopBack(SeqList *seq)
{
	if (seq->_size == 0)
	{
		return;
	}
	seq->_size--;
}

//查找
int SeqListSearch(SeqList *seq, SLDataType x)
{
	for (int i = 0; i < seq->_size; i++)
	{
		if (seq->_a[i] == x)
		{
			return i;
		}
	}
	return -1;
}



//修改
void SeqListModify(SeqList *seq, int pos,SLDataType x)
{
	if (pos >= 0 && pos < seq->_size)
	{
		seq->_a[pos] = x;
	}
	else
	{
		printf("该位置不存在\n");
	}
}

2.8.3 test.c

#include"SeqList.h"

void TestOne()
{
	SeqList s;
	SeqListInit(&s);
	SeqListPushBack(&s, 2);
	SeqListPushFront(&s, 1);
	SeqListPushBack(&s, 2);
	SeqListPushFront(&s, 1);
	SeqListShow(&s);
	SeqListPopBack(&s);
	SeqListPopFront(&s);
	SeqListShow(&s);
	int pos=SeqListSearch(&s, 1);
	if (pos == -1)
	{
		printf("您查找的数字不存在\n");
	}
	else
	{
		printf("您要查找的数字的下标为%d \n", pos);
	}
	SeqListModify(&s, 1, 9);
	SeqListShow(&s);
	SeqListDestory(&s);
}

int main()
{
	TestOne();
	return 0;
}

2.8.4 运行测试

在这里插入图片描述

3. 动态顺序表的实现

3.1 创建动态顺序表工程

参考2.1动态顺序表工程的创建

3.2 定义结构体

typedef int SLDataType;

typedef struct SeqList
{
	SLDataType  *_a;//动态开辟的动态数组
	size_t _size;//有效数据个数
	size_t _capacity;//容量空间的大小
}SeqList;

和静态顺序表相比，这里数组我们换成了指针，用来指向开辟的动态数组，又定义了_capacity也就是容量空间的大小。这样当我们发现容量不够时，便可以动态增容。

3.3 初始化和释放顺序表

3.3.1 SeqList.h 声明接口

//初始化
void SeqListInit(SeqList *seq);
//释放
void SeqListDestory(SeqList *seq);

一定要有内存释放函数，否则可能会造成内存泄露。

3.3.2 SeqList.c 定义函数

//初始化
void SeqListInit(SeqList *seq)
{
	seq->_a = NULL;
	seq->_size = seq->_capacity=0;
}

//释放
void SeqListDestory(SeqList *seq)
{
	free(seq->_a);
	seq->_a = NULL;
	seq->_size = seq->_capacity = 0;
}

3.3.3 加入断言完善

//初始化
void SeqListInit(SeqList *seq)
{
	assert(seq);
	seq->_a = NULL;
	seq->_size = seq->_capacity=0;
}


//释放
void SeqListDestory(SeqList *seq)
{
	assert(seq);
	free(seq->_a);
	seq->_a = NULL;
	seq->_size = seq->_capacity = 0;
}

在我们引入断言的时候，头文件要引入assert.h。可以通过断言来检查空指针，提高程序的安全性。

3. 4 容量检查操作

这个操作用来检查容量是否已满，当容量满时进行扩容。

3.4.1 SeqList.h 声明接口

//检查容量
void SeqListCherk(SeqList *seq);

3.4.2 SeqList.c 定义函数

//检查容量
void SeqListCherk(SeqList *seq)
{
	assert(seq);
	if (seq->_capacity == seq->_size)
	{
		//_capacity刚开始有可能是0，如果是0，开辟容量为4，如果不是0，扩容为2倍
		int newcapacity = seq->_capacity == 0 ? 4 : seq->_capacity * 2;
		SLDataType *newA = realloc(seq->_a, sizeof(SLDataType)*newcapacity);
		//检查扩容是否失败
		if (newA == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		seq->_a = newA;
		seq->_capacity = newcapacity;
	}
}

注意扩容有可能失败，要进行检验是否扩容成功。

3. 5 顺序表增加操作

3.5.1 SeqList.h 声明接口

//头插
void SeqListPushFront(SeqList *seq, SLDataType x);
//尾插
void SeqListPushBack(SeqList *seq, SLDataType x);

3.5.2 SeqList.c 定义函数

//头插
void SeqListPushFront(SeqList *seq, SLDataType x)
{
	assert(seq);
	SeqListCherk(seq);
	int end = seq->_size - 1;
	while (end >= 0)
	{
		seq->_a[end + 1] = seq->_a[end];
		end--;
	}
	seq->_a[0] = x;
	seq->_size++;
}
//尾插
void SeqListPushBack(SeqList *seq, SLDataType x)
{
	assert(seq);
	SeqListCherk(seq);
	seq->_a[seq->_size] = x;
	seq->_size++;
}

3.6 顺序表删除操作

3.6.1 SeqList.h 声明接口

//头删
void SeqListPopFront(SeqList *seq);
//尾删
void SeqListPopBack(SeqList *seq);

3.6.2 SeqList.c 定义函数

//头删
void SeqListPopFront(SeqList *seq)
{
	assert(seq);
	for (int first = 0; first < seq->_size-1; first++)
	{
		seq->_a[first] = seq->_a[first + 1];
	}
	seq->_size--;
}
//尾删
void SeqListPopBack(SeqList *seq)
{
	assert(seq);
	seq->_size--;
}

3.7 顺序表查找查找

3.7.1 SeqList.h 声明接口

//查找
int SeqListSearch(SeqList *seq, SLDataType x);

3.7.2 SeqList.c 定义函数

//查找
int SeqListSearch(SeqList *seq, SLDataType x)
{
	for (int i = 0; i < seq->_size; i++)
	{
		if (seq->_a[i] == x)
			return i;
	}
	return -1;
}

3.8 顺序表修改操作

3.8.1 SeqList.h 声明接口


//修改
void SeqListModify(SeqList *seq, int pos, SLDataType x);

3.8.2 SeqList.c 定义函数

//修改
void SeqListModify(SeqList *seq, int pos, SLDataType x)
{
	if (pos < seq->_size&&pos >= 0)
	{
		seq->_a[pos] = x;
	}
	else
	{
		printf("位置非法\n");
	}
}

3.9 完整代码展示及运行

3.9.1 SeqList.h

#include<stdio.h>
#include<malloc.h>
#include<assert.h>

typedef int SLDataType;

typedef struct SeqList
{
	SLDataType  *_a;//动态开辟的动态数组
	size_t _size;//有效数据个数
	size_t _capacity;//容量空间的大小
}SeqList;

//初始化
void SeqListInit(SeqList *seq);
//释放
void SeqListDestory(SeqList *seq);

//打印
void SeqListShow(SeqList *seq);

//检查容量
void SeqListCherk(SeqList *seq);

//头插
void SeqListPushFront(SeqList *seq, SLDataType x);
//尾插
void SeqListPushBack(SeqList *seq, SLDataType x);

//头删
void SeqListPopFront(SeqList *seq);
//尾删
void SeqListPopBack(SeqList *seq);

//查找
int SeqListSearch(SeqList *seq, SLDataType x);

//修改
void SeqListModify(SeqList *seq, int pos, SLDataType x);

3.9.2 SeqList.c

#include"SeqList.h"

//初始化
void SeqListInit(SeqList *seq)
{
	assert(seq);
	seq->_a = NULL;
	seq->_size = seq->_capacity = 0;
}


//释放
void SeqListDestory(SeqList *seq)
{
	assert(seq);
	free(seq->_a);
	seq->_a = NULL;
	seq->_size = seq->_capacity = 0;
}

//打印
void SeqListShow(SeqList *seq)
{
	assert(seq);
	for (int i = 0; i < seq->_size; i++)
	{
		printf("%d  ", seq->_a[i]);
	}
	printf("\n");
}

//检查容量
void SeqListCherk(SeqList *seq)
{
	assert(seq);
	if (seq->_capacity == seq->_size)
	{
		//_capacity刚开始有可能是0，如果是0，开辟容量为4，如果不是0，扩容为2倍
		int newcapacity = seq->_capacity == 0 ? 4 : seq->_capacity * 2;
		SLDataType *newA = realloc(seq->_a, sizeof(SLDataType)*newcapacity);
		//检查扩容是否失败
		if (newA == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		seq->_a = newA;
		seq->_capacity = newcapacity;
	}
}


//头插
void SeqListPushFront(SeqList *seq, SLDataType x)
{
	assert(seq);
	SeqListCherk(seq);
	int end = seq->_size - 1;
	while (end >= 0)
	{
		seq->_a[end + 1] = seq->_a[end];
		end--;
	}
	seq->_a[0] = x;
	seq->_size++;
}
//尾插
void SeqListPushBack(SeqList *seq, SLDataType x)
{
	assert(seq);
	SeqListCherk(seq);
	seq->_a[seq->_size] = x;
	seq->_size++;
}

//头删
void SeqListPopFront(SeqList *seq)
{
	assert(seq);
	for (int first = 0; first < seq->_size-1; first++)
	{
		seq->_a[first] = seq->_a[first + 1];
	}
	seq->_size--;
}
//尾删
void SeqListPopBack(SeqList *seq)
{
	assert(seq);
	seq->_size--;
}

//查找
int SeqListSearch(SeqList *seq, SLDataType x)
{
	for (int i = 0; i < seq->_size; i++)
	{
		if (seq->_a[i] == x)
			return i;
	}
	return -1;
}

//修改
void SeqListModify(SeqList *seq, int pos, SLDataType x)
{
	if (pos < seq->_size&&pos >= 0)
	{
		seq->_a[pos] = x;
	}
	else
	{
		printf("位置非法\n");
	}
}

3.9.3 test.c

#include"SeqList.h"

void TestOne()
{
	SeqList s;
	SeqListInit(&s);
	SeqListPushFront(&s, 1);
	SeqListPushFront(&s, 2);
	SeqListShow(&s);
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 4);
	SeqListShow(&s);
	SeqListPopBack(&s);
	SeqListPopFront(&s);
	SeqListShow(&s);
	int pos = SeqListSearch(&s,1);
	if (pos == -1)
	{
		printf("find fail\n");
	}
	else
	{
		printf("该元素的位置为%d\n", pos);
	}
	SeqListShow(&s);
	SeqListModify(&s, 0, 0);
	SeqListShow(&s);
}

int main()
{
	TestOne();
	return 0;
}

3.9.4 运行测试

在这里插入图片描述

后记

好的，这期诚意满满的博文就先分享到这里。希望对大家有所帮助，感谢大家支持，也欢迎大家批评指正。


点击全文阅读


本文链接：http://zhangshiyu.com/post/29952.html

顺序  定义  函数  
<< 上一篇 下一篇 >>

  • 评论（0）
  • 赞助本站

◎欢迎参与讨论，请在这里发表您的看法、交流您的观点。

最新文章

关于我们 | 我要投稿 | 免责申明

Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1