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

心中带点小风骚

11 月前

本文是数据结构的开篇，上文学习了关于使用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;
}

总结

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

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

文章出处登录后可见！

已经登录？立即刷新