数据结构与算法—顺序表

2024-03-14 21:00:11 分类：前端 热度：72 评论： 0

数据结构与算法—顺序表

目录

一、线性表

二、顺序表概念

 三、实现顺序表

1、声明结构体

2、初始化

3、打印数据 

4、销毁 

5、尾插&头插

尾插

判断是否扩容 

 头插

6、尾删&头删

尾删

头删

7、 指定位置插入元素

8、 删除指定位置元素

9、 查找指定元素位置

10、修改指定位置元素

完整版附上：

Seqlist.h

Seqlist.c

 text.c

一、线性表

  • 线性表是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...
  • 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，
  • 线性表在物理上存储时，通常以数组和链式结构的形式存储。

二、顺序表概念

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

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

 三、实现顺序表

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用 动态顺序表 ，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。

 我们创建三个文件：

  1. Seqlist.h用于存放头文件、结构体和函数的声明
  2. text.c作为主程序进行运行和测试
  3. Seqlist.c存放函数主体

1、声明结构体

#include <stdio.h>

typedef int SLDatatype;
typedef struct SeqList
{
	SLDatatype* a;
	int size;
	int capacity;
}SL;
  • 在头文件中声明结构体struct SeqList，由于名字太长，我们用typedef自定义结构体名称的别名为SL。
  • 将顺序表的数据类型用SLDatatype这个别名代替int，以后程序中使用到元素数据类型时都替换成SLDatatype，方便日后修改顺序表数据类型。
  • 定义size存储当前元素个数，capacity存储顺序表容量。

2、初始化

void SLInit(SL* psl)
{
	assert(psl);
	psl->a = (SLDatatype*)malloc(sizeof(SLDatatype) * 4);
	if (psl->a == NULL) {
		perror("malloc fail");
		return;
	}
	psl->size = 0;
	psl->capacity = 4;
}
  • 需要改变结构体变量，则将其地址传入函数。
  • assert检测传参顺序表指针是否合法，如果传入参数为空则报错（具体哪行出错）。
  • 然后为结构体成员a分配4个成员类型空间，顺便检查是否分配成功。
  • 对成员size和capacity分别复制为0（当前元素个数）和4（顺序表容量）。

3、打印数据 

void SLPrint(SL* psl)
{
	assert(psl);
	for (int i = 0; i < psl->size; i++) {
		printf("%d ", psl->a[i]);
	}
}

  • assert检测传参顺序表指针是否合法，然后循环遍历输出。

4、销毁 

void SLDestroy(SL* psl)
{
	assert(psl);
	free(psl->a);
	psl->a = NULL;
	psl->size = 0;
	psl->capacity = 0;
}

  • assert检测传参顺序表指针是否合法。

  • 释放动态开辟a的空间，同时赋值为空，不置空可能会造成野指针的访问。

  • size和capacity分别赋值为0。

5、尾插&头插

尾插

void SLPushBack(SL* psl, SLDatatype x)
{
	assert(psl);
    SLCheckCapacity(psl);
	psl->a[psl->size] = x;
	psl->size++;
}

  • assert检测传参顺序表指针是否合法。

  • 判断数组是否已经装满，如果装满则进行扩容，这些操作我们在函数SLCheckCapacity内进行。

  • 将 x 赋值给 psl->a 数组中下一个可用的位置，即 psl->size 索引处。

  • 递增 psl->size，以便记录新元素的加入。

 接下来我们来讲解函数SLCheckCapacity：

判断是否扩容 

void SLCheckCapacity(SL* psl)
{
	if (psl->size == psl->capacity) {
		SLDatatype* tmp = (SLDatatype*)realloc(psl->a, sizeof(SLDatatype) * psl->capacity * 2);
		if (tmp == NULL) {
			perror("realloc fail");
			return;
		}
		psl->a = tmp;
		psl->capacity *= 2;
	}
}

  •  判断当前元素个数size与顺序表容量capacity是否相等，相等则对结构体成员指针a进行扩容。

  • 通过realloc函数对a的内存进行扩容，每次增加一倍容量，并将reallocd的返回值新空间的起始地址赋值给SLDatatype类型指针 tmp，这样避免直接对a开辟空间时发生错误丢失数据。

  • 检测是否成功扩容。

  • 最后将存放新空间地址的tmp赋值给a。

  • 顺序表的容量也随之扩大为原来的两倍。

我们还可以优化一下尾插函数，具体如下： 

void SLPushBack(SL* psl, SLDatatype x)//尾插
{
	SLCheckCapacity(psl);
	psl->a[psl->size++] = x;
}

 头插

void SLPushFront(SL* psl, SLDatatype x)
{
	assert(psl);
	SLCheckCapacity(psl);
	int end = psl->size - 1;
	while (end >= 0) {
		psl->a[end + 1] = psl->a[end];
		end--;
	}
	psl->a[0] = x;
	psl->size++;
}

  • assert检测传参顺序表指针是否合法。

  • 判断数组是否已经装满，如果装满则进行扩容，这些操作在函数SLCheckCapacity内进行。

  • 定义end表示当前顺序表中最后一个元素的下标。

  • while循环用于从后向前将顺序表中的元素依次向后移动一个位置，为新元素 x 腾出空间

  • 将新元素 x 插入到顺序表的开头

  • 顺序表元素个数 size 增加1

6、尾删&头删

尾删

void SLPopBack(SL* psl)
{
	assert(psl);

	//暴力判断
	assert(psl->size == 0);

	//常规判断
	//if (psl->size == 0)
	//	return;

	psl->a[psl->size - 1] = 0;
	psl->size--;
}

  • 第一个assert检测传参顺序表指针是否合法。

  • 第二个assert检测顺序表是否为空，为空没有元素则不需要删除，程序报错。

  • 我们还可以通过顺序表元素个数判断，if语句判断size为0时，函数停止运行。

  • 顺序表大小不为空，则对最后一个元素进行删除，赋值为0。

  • 顺序表大小size减1.

头删

void SLPopFront(SL* psl)
{
	assert(psl);
	assert(psl->size > 0);
	int start = 0;
	while (start < psl->size) {
		psl->a[start] = psl->a[start + 1];
		start++;
	}
	psl->size--;
}

  • 第一个assert检测传参顺序表指针是否合法。

  • 第二个assert检测顺序表是否为空，为空没有元素则不需要删除，程序报错。

  • 定义变量start为首元素下标.

  • 头删不用赋值为0，直接从第一个元素开始后项赋值给前项。

7、指定位置插入元素

void SLInsert(SL* psl, int pos, SLDatatype x)
{
	assert(psl);
	assert(0 <= pos && pos <= psl->size);
	SLCheckCapacity(psl);
	int end = psl->size - 1;
	while (end >= pos) {
		psl->a[end + 1] = psl->a[end];
		end--;
	}
	psl->size++;
	psl->a[pos] = x;
}

  • 参数pos为要在第几个元素后插入。

  • 第一个assert检测传参顺序表指针是否合法。

  • 第二个assert检测传参pos的位置是否合法。

  • 判断数组是否已经装满，如果装满则进行扩容，这些操作在函数SLCheckCapacity内进行。

  • 定义end表示当前顺序表中最后一个元素的下标。

  • while循环用于从后向前将顺序表中的元素依次向后移动一个位置，为新元素 x 腾出空间

  • 顺序表元素个数 size 增加1。

  • 将新元素 x 插入到顺序表指定元素位置之后。

 SLInsert这个函数可以代替头插尾插函数进行顺序表元素的增加。

8、删除指定位置元素

void SLErase(SL* psl, int pos)
{
	assert(psl);
	assert(0 <= pos && pos <= psl->size);
	int start = pos + 1;
	while (start < psl->size) {
		psl->a[start - 1] = psl->a[start];
		start++;
	}
	psl->size--;
}

  • 第一个assert检测传参顺序表指针是否合法。

  • 第二个assert检测传参pos的位置是否合法。

  • 定义变量start存储pos位置后一项的下标。

  • 将删除元素后一项位置的值开始从pos+1向后依次前移一位，顶替pos位置。

  • 顺序表元素个数减一。

这个函数就可以完全代替头删尾删了。

9、查找指定元素位置

int SLFind(SL* psl, SLDatatype x)
{
	assert(psl);
	for (int i = 0; i < psl->size; i++) {
		if (psl->a[i] == x)
			return i+1;
	}
	return -1;
}

  •  assert检测传参顺序表指针是否合法。

  • 循环遍历顺序表找出于x相等的元素，返回其下标。

  • 找不到返回-1。

10、修改指定位置元素

void SLModify(SL* psl, int pos, SLDatatype x)
{
	assert(psl);
	assert(0 <= pos && pos <= psl->size);
	psl->a[pos] = x;
}

  • 第一个assert检测传参顺序表指针是否合法。

  • 第二个assert检测传参pos的位置是否合法。

  • 将pos位置的值修改为x。

完整版附上：

Seqlist.h

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLDatatype;
typedef struct SeqList
{
	SLDatatype* a;
	int size;
	int capacity;
}SL;

void SLInit(SL* psl);
void SLDestroy(SL* psl);
void SLPrint(SL* psl);
void SLPushBack(SL* psl, SLDatatype x);
void SLPushFront(SL* psl, SLDatatype x);
void SLPopBack(SL* psl);
void SLPopFront(SL* psl);
void SLInsert(SL* psl, int pos, SLDatatype x);
void SLErase(SL* psl, int pos);
int SLFind(SL* psl, SLDatatype x);
void SLModify(SL* psl, int pos, SLDatatype x);

Seqlist.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "Seqlist.h"

void SLInit(SL* psl)//初始化
{
	assert(psl);
	psl->a = (SLDatatype*)malloc(sizeof(SLDatatype) * 4);
	if (psl->a == NULL) {
		perror("malloc fail");
		return;
	}
	psl->size = 0;
	psl->capacity = 4;//每次开辟的容量为四个
}

void SLPrint(SL* psl)//打印数据
{
	assert(psl);
	for (int i = 0; i < psl->size; i++) {
		printf("%d ", psl->a[i]);
	}
}

void SLDestroy(SL* psl)//结束使用需要销毁
{
	assert(psl);
	free(psl->a);
	psl->a = NULL;
	psl->size = 0;
	psl->capacity = 0;
}

void SLCheckCapacity(SL* psl)
{
	if (psl->size == psl->capacity) {
		//增加一倍容量
		SLDatatype* tmp = (SLDatatype*)realloc(psl->a, sizeof(SLDatatype) * psl->capacity * 2);
		if (tmp == NULL) {
			perror("realloc fail");
			return;
		}
		psl->a = tmp;
		psl->capacity *= 2;
	}
	
}

void SLPushBack(SL* psl, SLDatatype x)//尾插
{
	assert(psl);
	//psl->a[psl->size] = x;
	//psl->size++;
	//插入需要判断a是否已满，已满需要扩容
	SLCheckCapacity(psl);
	//或者写成一句
	psl->a[psl->size++] = x;//后置自增
}

void SLPushFront(SL* psl, SLDatatype x)//头插
{
	assert(psl);
	SLCheckCapacity(psl);
	int end = psl->size - 1;
	while (end >= 0) {
		psl->a[end + 1] = psl->a[end];
		end--;
	}
	psl->a[0] = x;
	psl->size++;
}
void SLPopBack(SL* psl)
{
	assert(psl);//尾删
	//暴力判断
	//assert(psl->size == 0);
	//常规判断
	if (psl->size == 0)
		return;
	psl->a[psl->size - 1] = 0;
	psl->size--;
}

void SLPopFront(SL* psl)//头删
{
	assert(psl);
	assert(psl->size > 0);
	int start = 0;
	while (start < psl->size) {
		psl->a[start] = psl->a[start + 1];
		start++;
	}
	psl->size--;
}

void SLInsert(SL* psl, int pos, SLDatatype x)//指定位置插入元素,可代替头插尾插
{
	assert(psl);
	assert(0 <= pos && pos <= psl->size);//判读插入位置是否合法
	SLCheckCapacity(psl);
	int end = psl->size - 1;
	while (end >= pos) {
		psl->a[end + 1] = psl->a[end];
		end--;
	}
	psl->size++;
	psl->a[pos] = x;
}

void SLErase(SL* psl, int pos)//删除指定位置元素，代替头删尾删
{
	assert(psl);
	assert(0 <= pos && pos <= psl->size);
	int start = pos + 1;
	while (start < psl->size) {
		psl->a[start - 1] = psl->a[start];
		start++;
	}
	psl->size--;
}

int SLFind(SL* psl, SLDatatype x)//查找指定元素位置
{
	assert(psl);
	for (int i = 0; i < psl->size; i++) {
		if (psl->a[i] == x)
			return i+1;
	}
	return -1;//找不到返回-1
}

void SLModify(SL* psl, int pos, SLDatatype x)//修改指定位置元素
{
	assert(psl);
	assert(0 <= pos && pos <= psl->size);
	psl->a[pos] = x;
}

 text.c

这里大家可以自行发挥！

#define _CRT_SECURE_NO_WARNINGS 1
#include "Seqlist.h"

void test1()
{
	SL s;
	SLInit(&s);
	SLPushBack(&s, 5);
	SLPushBack(&s, 9);
	SLPushBack(&s, 50);
	SLPushFront(&s, 1);
	SLPushFront(&s, 15);
	SLPushFront(&s, 0);
	SLPopBack(&s, 50);
	SLPopFront(&s, 0);
	SLInsert(&s, 2, 555);
	SLErase(&s, 4);


	SLPrint(&s);

	int a=SLFind(&s, 15);
	printf("\n%d\n", a);
	if (a != -1)
		SLErase(&s, a);
	SLPrint(&s);

	SLDestroy(&s);
}

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

转载请说明出处内容投诉
CSS教程_站长资源网 » 数据结构与算法—顺序表
红袖添香

红袖添香

分享到：

相关推荐

发表评论

欢迎 访客 发表评论

一个令你着迷的主题！

查看演示 官网购买