【数据结构和算法】实现线性表中的静态、动态顺序表

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

本文是数据结构的开篇上文学习了关于使用C语言实现静态、动态、文件操作的通讯录其中使用到了结构体这一类型实际上是可以属于数据结构的内容接下来我们来了解一下顺序表的相关内容。

目录

前言

一、线性表

一、顺序表是什么

二、分析顺序表的实现

三、静态顺序表

1.顺序表初始化

2.增加元素

1.尾插

2.头插

3.删除元素

1.尾删

2.头删

4.改变数据和查找

5.打印和销毁顺序表

四、动态顺序表

1.初始化

2.扩容

3.销毁顺序表

五、完整代码演示

1.静态顺序表

1.test.c

2.Seqtable.h

3.Seqtable.c

2.动态顺序表

1.test.c

2.Seqtable.h

3.Seqtable.c

总结

前言

数据结构是什么

对于大家来说这是一个全新的内容模块数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。

我们接下来是对于数据结构的顺序表的实现的讲解

一、线性表

线性表linear list是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构常见的线性表顺序表、链表、栈、队列、字符串...

线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构上并不一定是连续的线性表在物理上存储时通常以数组和链式结构的形式存储。

实际上学会了顺序表和链表自然栈、队列、二叉树等各种结构就好学啦又称顺序表和链表是数据结构的基础是实现后序内容的基础。

一、顺序表是什么

1.将表中元素一个接一个的存入一组连续的存储单元中这种存储结构是顺序结构。

2.使用顺序结构存储的线性表叫做顺序表

总结

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

二、分析顺序表的实现

顺序表分为动态和静态两种顺序表顺序表的实际操作功能大致为增删改查又细分为头尾增删初始化、摧毁顺序表等操作。

我们接下来分别介绍静态和动态顺序表是如何实现的

三、静态顺序表

使用结构体为

1.顺序表初始化

如图所示

代码演示

//初始化函数
void InitSeqtable(Seqtable* st) {
	//for (int i = 0; i < MAX; i++) {
	//	st->date[i] = 0;//初始化为0  实际上可以不用初始化数组
	//}
	st->size = 0;
}

2.增加元素

分为头插入、尾插入

1.尾插

如图所示

代码演示

//尾插入
void BackSeqtable(Seqtable* st, int data) {
	//尾部插入的时候要进行判别是否为满
	if (st->size == MAX) {
		//表示满了
		perror("顺序表已经满员无法插入新数据\n");
		exit(-1);//退出就可以
	}
	//没有满员就加入数据即可
	st->date[st->size++] = data;
}

2.头插

如图所示

 代码如下

//头插入
void FrontSeqtable(Seqtable* st, int data) {
	//一样先进行判断是否满员
	if (st->size == MAX) {
		perror("满员无法插入");
		exit(-1);
	}
	//头部插入。就是将原有数据向后移动一个位置
	int num = st->size - 1;
	for (int i = num; i>=0; i--) {
		st->date[i + 1] = st->date[i];
	}
	//while (num>=0) {
	//	st->date[num + 1] = st->date[num];
	//	num--;
	//}
	//最后插入数据
	st->date[0] = data;
	st->size++;
}

3.删除元素

分为头删、尾删

1.尾删

如图所示

 代码如下

//尾删除
void SeqtablePopBack(Seqtable* st) {
	//尾删除需要判断是否为空
	assert(st->size > 0);//断言判断
	st->size--;//直接元素个数减去一个就可以

}

2.头删

如图所示

 代码如下

//头删除
void SeqtablePopFront(Seqtable* st) {
	//头部删除也要判空
	assert(st->size > 0);//断言
	//将后面的数据覆盖前面的数据
	for (int i = 0; i < st->size-1; i++) {
		st->date[i] = st->date[i + 1];
	}
	st->size--;//size减去一个元素即可
}

4.改变数据和查找

想要改变指定下标的数据输入要查找的元素更改这个的数据要先查找到对应坐标简易的更改数值不考虑重复的问题从左向右的顺序查询

代码如下

//查找
int SearchSeqtable(Seqtable* st) {
	assert(st->size > 0);//如果为空不用查找直接报错
	int num = 0;
	scanf("%d", &num);//输入查找的元素
	for (int i = 0; i < st->size; i++) {
		if (st->date[i] == num) {
			return i;//找到返回下标
		}
	}
	return -1;//没找到返回-1
	
}

void ChangeSeqtable(Seqtable* st) {
	int num=SearchSeqtable(st);//进入查找返回下标
	if (num == -1) {
		printf("顺序表中没有该元素无法修改\n");
		return;
	}
	int a = 0;
	scanf("%d", &a);//输入想要更改的数据
	st->date[num] = a;
}

5.打印和销毁顺序表

代码如下

//摧毁顺序表
void SeqtableDestory(Seqtable* st) {
	//摧毁的话静态表直接初始化为0
	st->size = 0;
}

//打印
void PrintSeqtable(Seqtable* st) {
	for (int i = 0; i < st->size; i++) {
		printf("%d ", st->date[i]);
	}
}

四、动态顺序表

动态顺序表和静态顺序表的差别就是结构体、初始化、摧毁顺序表、扩容

结构体如下

//动态顺序表
typedef struct Seqtable {
	int* data;//数据域
	int size;//个数
	int capacity;//容量
}Seqtable;

//实际上动态顺序表和静态顺序表只有在初始化、销毁、扩容的时候不一样

1.初始化

//初始化顺序表
void InitSeqtable(Seqtable* st) {
	st->size = st->capacity = 0;
	st->data = NULL;
}

2.扩容

如图所示 

代码演示

//扩容
void Expansion(Seqtable* st) {
	//1.直接扩容二倍这样防止后序一致扩容
	int newcapacity = st->capacity = 0 ? 4 : st->capacity * 2;
	int* tmp = (int*)realloc(st->data, newcapacity * sizeof(int));
	if (tmp == NULL) {
		//表示创建失败
		perror("realloc fail\n");
		exit(-1);
	}
	//创建成功  tmp给data
	st->data = tmp;
	st->capacity = newcapacity;
}

如图上另外一种扩容方法可以看这篇文章中动态通讯录扩容里面有介绍(24条消息) 【C语言】使用C语言实现静态、动态的通讯录简单易懂_小王学代码的博客-CSDN博客

3.销毁顺序表

void SeqListDestory(Seqtable* ps) {
	free(ps->data);//直接释放a的空间 
	ps->data = NULL;//然后指向NULL
	ps->capacity = ps->size = 0;
}

除此之外和静态顺序表都差不多一样了

五、完整代码演示

1.静态顺序表

所谓静态就是指不能更改顺序表最大存储元素个数可能剩下很多也可能不够

1.test.c

主函数的使用

#define _CRT_SECURE_NO_WARNINGS
#include"Seqtable.h"
//实现顺序表
void test1()
{
	Seqtable st;
	InitSeqtable(&st);//初始化
	//尾插
	BackSeqtable(&st, 1);
	BackSeqtable(&st, 2);
	BackSeqtable(&st, 3);
	BackSeqtable(&st, 4);
	BackSeqtable(&st, 5);
	//打印
	PrintSeqtable(&st);
	printf("\n");
	//头插
	FrontSeqtable(&st, 1);
	FrontSeqtable(&st, 2);
	FrontSeqtable(&st, 3);
	FrontSeqtable(&st, 4);
	FrontSeqtable(&st, 5);
	PrintSeqtable(&st);
	//尾巴删除
	SeqtablePopBack(&st);
	SeqtablePopBack(&st);
	SeqtablePopBack(&st);
	SeqtablePopBack(&st);
	SeqtablePopBack(&st);
	printf("\n");
	//打印
	PrintSeqtable(&st);
	//头删除
	SeqtablePopFront(&st);
	printf("\n");
	//打印
	PrintSeqtable(&st);

	摧毁顺序表
	//SeqtableDestory(&st);
	printf("\n");
	//打印
	ChangeSeqtable(&st);
	PrintSeqtable(&st);
}
int main()
{	//实现静态顺序表
	test1();
	return 0;
}

2.Seqtable.h

头文件的使用

#define _CRT_SECURE_NO_WARNINGS

//头文件进行函数的声明
//		结构体的实现

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

#define MAX 100
//静态顺序表的实现
typedef struct Seqtable {
	int date[MAX];//数据域
	int size;//数据个数
}Seqtable;



//实现函数声明

//初始化函数
void InitSeqtable(Seqtable* st);

//尾插入
void BackSeqtable(Seqtable* st, int data);

//头插入
void FrontSeqtable(Seqtable* st, int data);

//尾删除
void SeqtablePopBack(Seqtable* st);

//头删除
void SeqtablePopFront(Seqtable* st);

//摧毁顺序表
void SeqtableDestory(Seqtable* st);

//打印
void PrintSeqtable(Seqtable* st);

//查找指定元素
//有 返回 下标
//没有 返回 -1

int SearchSeqtable(Seqtable* st);
//更改数据
void ChangeSeqtable(Seqtable* st);

3.Seqtable.c

函数的实现

#define _CRT_SECURE_NO_WARNINGS
#include"Seqtable.h"
//实现方法
//顺序表的头插尾插头删尾删
//初始化和销毁

//静态顺序表

//初始化函数
void InitSeqtable(Seqtable* st) {
	for (int i = 0; i < MAX; i++) {
		st->date[i] = 0;//初始化为0  实际上可以不用初始化数组
	}
	st->size = 0;
}
//尾插入
void BackSeqtable(Seqtable* st, int data) {
	//尾部插入的时候要进行判别是否为满
	if (st->size == MAX) {
		//表示满了
		perror("顺序表已经满员无法插入新数据\n");
		exit(-1);//退出就可以
	}
	//没有满员就加入数据即可
	st->date[st->size++] = data;
}
//头插入
void FrontSeqtable(Seqtable* st, int data) {
	//一样先进行判断是否满员
	if (st->size == MAX) {
		perror("满员无法插入");
		exit(-1);
	}
	//头部插入。就是将原有数据向后移动一个位置
	int num = st->size - 1;
	for (int i = num; i>=0; i--) {
		st->date[i + 1] = st->date[i];
	}
	//while (num>=0) {
	//	st->date[num + 1] = st->date[num];
	//	num--;
	//}
	//最后插入数据
	st->date[0] = data;
	st->size++;
}

//尾删除
void SeqtablePopBack(Seqtable* st) {
	//尾删除需要判断是否为空
	assert(st->size > 0);//断言判断
	st->size--;//直接元素个数减去一个就可以

}
//头删除
void SeqtablePopFront(Seqtable* st) {
	//头部删除也要判空
	assert(st->size > 0);//断言
	//将后面的数据覆盖前面的数据
	for (int i = 0; i < st->size-1; i++) {
		st->date[i] = st->date[i + 1];
	}
	st->size--;//size减去一个元素即可
}
//摧毁顺序表
void SeqtableDestory(Seqtable* st) {
	//摧毁的话静态表直接初始化为0
	st->size = 0;
}

//打印
void PrintSeqtable(Seqtable* st) {
	for (int i = 0; i < st->size; i++) {
		printf("%d ", st->date[i]);
	}
}

//查找
int SearchSeqtable(Seqtable* st) {
	assert(st->size > 0);//如果为空不用查找直接报错
	int num = 0;
	scanf("%d", &num);//输入查找的元素
	for (int i = 0; i < st->size; i++) {
		if (st->date[i] == num) {
			return i;//找到返回下标
		}
	}
	return -1;//没找到返回-1
	
}

void ChangeSeqtable(Seqtable* st) {
	int num=SearchSeqtable(st);//进入查找返回下标
	if (num == -1) {
		printf("顺序表中没有该元素无法修改\n");
		return;
	}
	int a = 0;
	scanf("%d", &a);//输入想要更改的数据
	st->date[num] = a;
}

2.动态顺序表

所谓动态就是使用realloc等函数动态开辟空间尽量使得顺序表的空间合理化使用

1.test.c

主函数进行测试和使用顺序表

#define _CRT_SECURE_NO_WARNINGS
#include"动态顺序表.h"

void test2() {
	Seqtable st;
	InitSeqtable(&st);//初始化
	//尾插
	BackSeqtable(&st, 1);
	BackSeqtable(&st, 2);
	BackSeqtable(&st, 3);
	BackSeqtable(&st, 4);
	BackSeqtable(&st, 5);
	//打印
	PrintSeqtable(&st);
	printf("\n");
	//头插
	FrontSeqtable(&st, 1);
	FrontSeqtable(&st, 2);
	FrontSeqtable(&st, 3);
	FrontSeqtable(&st, 4);
	FrontSeqtable(&st, 5);
	PrintSeqtable(&st);
	//尾巴删除
	SeqtablePopBack(&st);
	SeqtablePopBack(&st);
	SeqtablePopBack(&st);
	SeqtablePopBack(&st);
	SeqtablePopBack(&st);
	printf("\n");
	//打印
	PrintSeqtable(&st);
	//头删除
	SeqtablePopFront(&st);
	printf("\n");
	//打印
	PrintSeqtable(&st);
	摧毁顺序表
	SeqListDestory(&st);
	//printf("\n");
	打印
	//PrintSeqtable(&st);
}

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

2.Seqtable.h

函数声明和结构体创建

#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<malloc.h>
//动态顺序表
typedef struct Seqtable {
	int* data;//数据域
	int size;//个数
	int capacity;//容量
}Seqtable;

//实际上动态顺序表和静态顺序表只有在初始化、销毁、扩容的时候不一样


//实现函数声明

//初始化函数
void InitSeqtable(Seqtable* st);

//尾插入
void BackSeqtable(Seqtable* st, int data);

//头插入
void FrontSeqtable(Seqtable* st, int data);

//尾删除
void SeqtablePopBack(Seqtable* st);

//头删除
void SeqtablePopFront(Seqtable* st);

//摧毁顺序表
void SeqtableDestory(Seqtable* st);

//打印
void PrintSeqtable(Seqtable* st);

//查找
int SearchSeqtable(Seqtable* st);
//更改
void ChangeSeqtable(Seqtable* st);

3.Seqtable.c

代码实现

#define _CRT_SECURE_NO_WARNINGS
#include"动态顺序表.h"
//动态顺序表

//初始化顺序表
void InitSeqtable(Seqtable* st) {
	st->size = st->capacity = 0;
	st->data = NULL;
}
//扩容
void Expansion(Seqtable* st) {
	//1.直接扩容二倍这样防止后序一致扩容
	int newcapacity = st->capacity = 0 ? 4 : st->capacity * 2;
	int* tmp = (int*)realloc(st->data, newcapacity * sizeof(int));
	if (tmp == NULL) {
		//表示创建失败
		perror("realloc fail\n");
		exit(-1);
	}
	//创建成功  tmp给data
	st->data = tmp;
	st->capacity = newcapacity;
}

//尾插入
void BackSeqtable(Seqtable* st, int data) {
	//判断是否满员
	if (st->size == st->capacity) {
		//满员进行扩容
		//两个方法
		//1.直接扩容二倍这样防止后序一致扩容
		Expansion(st);
	}
	//如果没有满员,就正常使用
	st->data[st->size++] = data;
}
//头插入
void FrontSeqtable(Seqtable* st, int data) {
	//使用动态的
	if (st->size == st->capacity) {
		Expansion(st);
	}
	int end = st->size - 1;
	while (end >= 0) {
		st->data[end + 1] = st->data[end];
		--end;
	}
	st->data[0] = data;
	st->size++;
}
//尾删除
void SeqtablePopBack(Seqtable* st) {
	//尾删除需要判断是否为空
	assert(st->size > 0);//断言判断
	st->size--;//直接元素个数减去一个就可以

}
//头删除
void SeqtablePopFront(Seqtable* st) {
	//头部删除也要判空
	assert(st->size > 0);//断言
	//将后面的数据覆盖前面的数据
	for (int i = 0; i < st->size - 1; i++) {
		st->data[i] = st->data[i + 1];
	}
	st->size--;//size减去一个元素即可
}
//打印
void PrintSeqtable(Seqtable* st) {
	for (int i = 0; i < st->size; i++) {
		printf("%d ", st->data[i]);
	}
}
//摧毁动态顺序表
//void SeqtableDestory(Seqtable* st) {
//	//先释放空间
//	free(st->data);
//	st->data = NULL;
//	free(st);
//	st->size = st->capacity = 0;
//}
void SeqListDestory(Seqtable* ps) {
	free(ps->data);//直接释放a的空间 
	ps->data = NULL;//然后指向NULL
	ps->capacity = ps->size = 0;
}

//查找
int SearchSeqtable(Seqtable* st) {
	assert(st->size > 0);//如果为空不用查找直接报错
	int num = 0;
	scanf("%d", &num);//输入查找的元素
	for (int i = 0; i < st->size; i++) {
		if (st->data[i] == num) {
			return i;//找到返回下标
		}
	}
	return -1;//没找到返回-1

}

void ChangeSeqtable(Seqtable* st) {
	int num = SearchSeqtable(st);//进入查找返回下标
	if (num == -1) {
		printf("顺序表中没有该元素无法修改\n");
		return;
	}
	int a = 0;
	scanf("%d", &a);//输入想要更改的数据
	st->data[num] = a;
}

总结

我们本文讲解了线性表中的顺序表的使用我们分别实现了静态和动态的顺序表这是数据结构的基础我们接下来讲解的内容是线性表中的链表。

好了行文至此感谢这一段时间来大家的鼓励和支持小王会继续努力学习代码的一起加油啊

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

上一篇：李宏毅2021&2022机器学习

下一篇：FPGA：Verilog HDL程序的基本结构

“【数据结构和算法】实现线性表中的静态、动态顺序表” 的相关文章

[python]pybullet安装后测试代码1年前 (2023-02-02)
MyBatis（三）使用MyBatis完成CRUD（增删改查）1年前 (2023-02-02)
CF大陆斗C战士（一）1年前 (2023-02-02)
前端经典面试题 | 吊打面试官系列 之 说说你对TypeScript 和 JavaScript的理解1年前 (2023-02-02)
微信小程序 | 小程序组件化开发1年前 (2023-02-02)
Redis数据库 ---- 五种数据类型常用命令汇总_redis unlike key1年前 (2023-02-02)
欠你们的 → k8s 集群搭建，除夕奉上！1年前 (2023-02-02)
【云原生-K8s】kubeadm搭建安装k8s集群v1.25版本完整教程【docker、网络插件calico、中间层cri-docker】_kubeadmin安装k8s1年前 (2023-02-02)
System1年前 (2023-02-02)
渗透测试工具Kali Linux安装与使用1年前 (2023-02-02)

阿里云国际版