【数据结构详解】——线性表之顺序表（多图详解）

admin • 2024-02-05 19:32 • 程序人生

前言：本期我们正式进入线性表中顺序表的学习。之后内容都会以C语言的方式实现，对于数据结构而言最重要的是思想哦

1.线性表

1.1 什么是线性表

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

1.2 小结

线性表顾名思义，是具有像线一样的性质的表，比如排队的人群，有头有尾。

2. 顺序表

2.1 概念及结构

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

顺序表一般可分为：

静态顺序表：使用定长数组存储元素。
动态顺序表：使用动态开辟的数组存储。

2.2 静态版顺序表

静态版：固定的存储空间，使用定长数组存储

#define N 100

typedef int SLDataType;

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

缺点：存储的过程中不能进行增容，定义太多又会造成浪费，十分不灵活

因此，我们现在更常用的是动态版顺序表，下面我们就详细介绍动态顺序表与其接口实现。

2.3 动态版顺序表

动态版：实现了增容，使用动态开辟的数组存储

Tips：关于内存开辟不熟悉的同学可以去【C语言详解】——动态内存管理复习哦~

typedef int SLDataType;

typedef struct SeqList
{
	SLDataType* arr;  // 指向动态开辟的数组
	size_t size ; 	  // 有效数据个数
	size_t capicity ; // 容量空间的大小
}SeqList;

与静态版本的区别，就是将定长数组，改为改为可以接收动态开辟内存地址的指针，且增加了一个变量

小结：由于静态顺序表长度限制的局限性，现实中基本都是使用动态顺序表，根据需要动态分配空间，接下来我们实现动态顺序表的各接口函数。

3. 顺序表的接口实现

对于数据结构的接口实现，一般围绕着增、删、查、改的内容

typedef struct SeqList
{
	SLDataType *a;
	int size;	//存储数据的个数
	int capacity;	//存储空间的大小
}SL;

对于之后学习数据结构的过程中，我们在实现每一步时都要进行测试，测试的时候可以通过写一个test函数分块测试，只需要在main函数改变该函数名即可快捷调试，无需一一注释代码，如下图

void TestSeqList1()
{
	SeqList s;
}

int main()
{
	TestSeqList1();
	//顺序表一般不要自己去动它
	//而是交给函数去 初始化，去操纵

	return 0;
}

3.1 初始化顺序表

void SeqListInit(SL* psl)
{
	assert(psl);	//断言判空

	psl->a = NULL;
	psl->capacity = psl->size = 0;
}

3.2 销毁顺序表

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

	if (psl->a)		//如果不为空，这条if语句可以不写，因为free会检查NULL并做出判断
	{
		free(psl->a);	
		psl->a = NULL;
		psl->capacity = psl->size = 0;
	}
}

3.3 打印顺序表

思路：传址调用，节省空间，循环遍历。

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

3.4 检查容量

之后实现的接口都需要检查顺序表是否需要扩容，如果不够就以2倍进行增容，这个大小是比较合适的。我们便可以将其集成为一个函数，方便后续调用。

大致思路：先判断在数据个数与容量是否相同，如果相同就进行扩容，这里就用realloc来动态申请内存。

void SeqListCheckCapacity(SL* psl)
{
	//检查容量
	if (psl->size == psl->capacity)	//当数据个数与容量相同就是满了，进入下面扩容，else就不用写了，空间够了直接过
	{
		//psl->capacity *= 2;		//考虑为0的情况不能这么用
		int newCapcity = psl->capacity == 0 ? 4 : psl->capacity * 2;	如果capacity为0就给他4个空间,否则进行2倍增容.
		SLDataType* tmp = (SLDataType*)realloc(psl->a, newCapcity * sizeof(SLDataType));	//两倍扩容
		if (tmp == NULL)		//担心返回空指针导致原数组数据丢失
		{
			perror("realloc fail");
			return;		//或者exit(-1);		//结束程序
		}

		psl->a = tmp;	//tmp初始化与否不重要
		psl->capacity = newCapcity;
	}
}

3.5 尾插顺序表

思路：先检查容量，在顺序表中有效数据的后面增加一个新的数据，然后size增加。

void SeqListPushBack(SL* psl, SLDataType x)
{
	assert(psl);

	SeqListCheckCapacity(psl);	//调用增容函数

	psl->a[psl->size] = x;	//直接访问顺序表的最后一个元素进行插入
	psl->size++;
}

3.6 头插顺序表

思路：头部插入和尾部插入刚好相反，先检查容量，将顺序表中有效数据向后移动一位，然后将需要插入的新数据放在第一位上。

void SeqListPushFront(SL* psl, SLDataType x)
{
	assert(psl);
	SeqListCheckCapacity(psl);

	//挪动数据
	int end = psl->size - 1;
	while (end >= 0)	//需要将顺序表整体往后移动，空出头部一个位置给插入
	{
		psl->a[end + 1] = psl->a[end];
		end--;
	}
	psl->a[0] = x;
	psl->size++;
}

3.7 尾删顺序表

思路：尾删就和尾插差不多咯，直接找到顺序表中有效数据的最后一个，并将size减1就可以了。注意检查是否只剩一个元素，防止越界访问。

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

	//温柔的检查
	if (psl->size == 0)
	{
		return;
	}

	//暴力的检查
	//assert(psl->size > 0);	//为假终止运行

	psl->size--;	//如果顺序表只剩下一个元素的时候，会越界访问哦，因此需要检查
}

3.8 头删顺序表

思路：头删就是把顺序表中有效数据从左到右一次向左移动一位，直接覆盖就行了。

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

	int begin = 0;
	while (begin < psl->size - 1)
	{
		psl->a[begin] = psl->a[begin + 1];
		begin++;
	}
	psl->size--;
}

3.9 查找元素

思路：直接遍历循环查找

int SeqListFind(SL* psl, SLDataType x)
{
	assert(psl);

	for (int i = 0; i < psl->size; i++)
	{
		if (psl->a[i] == x)
		{
			return i;	//返回下标
		}
	}

	return -1;
}

3.10 任意位置前插入元素

思路：检查容量，pos 是我们要插入位置的数组下标，它后面的数据（包括这一位）从右到左依次向右移动一位，然后将需要插入的新数据放在 pos 上。

//写法1
void SeqListInsert(SL* psl, size_t pos, SLDataType x)
{
	assert(psl);
	assert(pos <= psl->size);

	SeqListCheckCapacity(psl);

	// 挪动数据
	int end = psl->size - 1;
	
	while (end >= (int)pos)			//pos不建议用size_t，否则会产生整形提升，从而产生越界，但是我们要跟着STL的风格走，于是还得用size_t
	//while (end > pos)		//如果传参是int类型就用这个	
	{
		psl->a[end + 1] = psl->a[end];
		end--;
	}

	psl->a[pos] = x;
	psl->size++;
}


//写法2
void SeqListInsert(SL* psl, size_t pos, SLDataType x)	

{
	assert(psl);
	assert(pos <= psl->size);

	SeqListCheckCapacity(psl);

	// 挪动数据
	size_t end = psl->size;
	while (end > pos)			
	{
		psl->a[end] = psl->a[end - 1];
		end--;
	}

	psl->a[pos] = x;
	psl->size++;
}

有了任意位置插入元素函数的实现，我们的头插、尾插函数便可以复用这个函数来实现了

3.10.1 【复用】头插顺序表

void SeqListPushFront(SL* psl, SLDataType x)
{
	SeqListInsert(psl, 0, x);
}

3.10.2 【复用】尾插顺序表

void SeqListPushBack(SL* psl, SLDataType x)
{
	SeqListInsert(psl, psl->size, x);
}

3.11 任意位置删除元素

思路：检查容量，pos 是我们要插入位置的数组下标，它后面的数据（包括这一位）从左到右依次向左移动一位，然后将需要插入的新数据放在 pos 上。

void SeqListErase(SL* psl, size_t pos)
{
	assert(psl);
	assert(pos < psl->size);

	size_t begin = pos;
	while (begin < psl->size - 1)
	{
		psl->a[begin] = psl->a[begin + 1];
		begin++;
	}

	psl->size--;
}

有了任意位置删除元素函数的实现，我们的头删、尾删函数便可以复用这个函数来实现了

3.11.1 【复用】头删顺序表

void SeqListPopFront(SL* psl)
{
	SeqListErase(psl, 0);
}

3.11.2 【复用】尾删顺序表

void SeqListPopBack(SL* psl)
{
	SeqListErase(psl, psl->size - 1);
}

3.12 修改顺序表

思路：直接找到需要更改数据的下标，然后把新数据放进去就好了。

void SeqListModify(SL* psl, size_t pos, SLDataType x)
{
	assert(psl);
	assert(pos < psl->size);

	psl->a[pos] = x;
}

4. 顺序表的优缺点

优点：

可以按下标进行随机访问

缺点：

动态增容有性能缺陷（且伴随着一定的空间浪费，有内存碎片）
头部或者中间插入删除数据，需要挪动数据，效率比较低（O(N)）

5. 完整源码

// SeqList.h
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int SLDataType;

//动态顺序表
typedef struct SeqList
{
	SLDataType *a;
	int size;	//存储数据的个数
	int capacity;	//存储空间的大小
}SL;

void SeqListInit(SL* psl);

void SeqListDestroy(SL* psl);

void SeqListPrint(const SL* psl);

//尾插（推荐）（时间复杂度为：O(1)）
void SeqListPushBack(SL* psl, SLDataType x);

//头插（时间复杂度为：O(N)）
void SeqListPushFront(SL* psl, SLDataType x);

//尾删
void SeqListPopBack(SL* psl);

//头删
void SeqListPopFront(SL* psl);

// 没有找到就返回-1
int SeqListFind(SL* psl, SLDataType x);

// 顺序表在pos位置插入x
void SeqListInsert(SL* psl, int pos, SLDataType x);

// 顺序表删除pos位置的值
void SeqListErase(SL* psl, size_t pos);

// 修改数据
void SeqListModify(SL* psl, size_t pos, SLDataType x);



// SeqList.c
#include"SeqList.h"

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

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

	psl->a = NULL;
	psl->capacity = psl->size = 0;
}

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

	/*if (psl->a)
	{*/
		free(psl->a);
		psl->a = NULL;
		psl->capacity = psl->size = 0;
	//}
}

void SeqListCheckCapacity(SL* psl)
{
	//检查容量
	if (psl->size == psl->capacity)
	{
		//psl->capacity *= 2;
		int newCapcity = psl->capacity == 0 ? 4 : psl->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(psl->a, newCapcity * sizeof(SLDataType));
		if (tmp == NULL)		//担心返回空指针导致原数组数据丢失
		{
			perror("realloc fail");
			return;
		}

		psl->a = tmp;
		psl->capacity = newCapcity;
	}
}


void SeqListPushBack(SL* psl, SLDataType x)
{
	/*assert(psl);

	SeqListCheckCapacity(psl);

	psl->a[psl->size] = x;
	psl->size++;*/

	SeqListInsert(psl, psl->size, x);
}

void SeqListPushFront(SL* psl, SLDataType x)
{
	/*assert(psl);
	SeqListCheckCapacity(psl);

	//挪动数据
	int end = psl->size - 1;
	while (end >= 0)
	{
		psl->a[end + 1] = psl->a[end];
		end--;
	}
	psl->a[0] = x;
	psl->size++;*/

	SeqListInsert(psl, 0, x);
}

void SeqListPopBack(SL* psl)
{
	/*
	assert(psl);

	//温柔的检查
	if (psl->size == 0)
	{
		return;
	}

	//暴力的检查
	//assert(psl->size > 0);

	psl->size--;*/
	SeqListErase(psl, psl->size - 1);
}

void SeqListPopFront(SL* psl)
{
	/*
	assert(psl);

	int begin = 0;
	while (begin < psl->size - 1)
	{
		psl->a[begin] = psl->a[begin + 1];
		begin++;
	}
	psl->size--;*/
	SeqListErase(psl, 0);
}

int SeqListFind(SL* psl, SLDataType x)
{
	assert(psl);

	for (int i = 0; i < psl->size; i++)
	{
		if (psl->a[i] == x)
		{
			return i;
		}
	}

	return -1;
}
 
void SeqListInsert(SL* psl, size_t pos, SLDataType x)	
//void SeqListInsert(SL* psl, int pos, SLDataType x)
{
	assert(psl);
	assert(pos <= psl->size);

	SeqListCheckCapacity(psl);

	// 挪动数据
	/*int end = psl->size - 1;
	while (end >= (int)pos)			//pos不建议用size_t，否则会产生整形提升，从而产生越界，但是我们要跟着STL的风格走，于是还得用size_t
	{
		psl->a[end + 1] = psl->a[end];
		end-- ;
	}*/

	size_t end = psl->size;
	while (end > pos)			
	{
		psl->a[end] = psl->a[end - 1];
		end--;
	}

	psl->a[pos] = x;
	psl->size++;
}

void SeqListErase(SL* psl, size_t pos)
{
	assert(psl);
	assert(pos < psl->size);

	size_t begin = pos;
	while (begin < psl->size - 1)
	{
		psl->a[begin] = psl->a[begin + 1];
		begin++;
	}

	psl->size--;
}

void SeqListModify(SL* psl, size_t pos, SLDataType x)
{
	assert(psl);
	assert(pos < psl->size);

	psl->a[pos] = x;
}



// Test.c
#include"SeqList.h"

void memu()
{
	printf("****************************************n");
	printf("1、尾插数据 2、头插数据n");
	printf("7、打印数据 -1、退出n");
	printf("****************************************n");
}

int main()
{
	SL s;
	SeqListInit(&s);
	int option = 0;
	int x = 0;
	do
	{
		memu();
		printf("请输入你的操作:>");
		scanf("%d", &option);
		switch (option)
		{
		case 1:
			printf("请连续输入你要插入的数据，以-1结束n");
			scanf("%d", &x);
			while (x != -1)
			{
				SeqListPushBack(&s, x);
				scanf("%d", &x);
			}
			break;
		case 2:
			break;
		case 3:
			break;
		case 7:
			SeqListPrint(&s);
			break;
		default:
			break;
		}

	} while (option != -1);

	SeqListDestroy(&s);

	return 0;
}

OK，以上就是本期知识点“顺序表”的知识啦~~ ，感谢友友们的阅读。后续还会继续更新，欢迎持续关注哟~
如果觉得收获满满，可以点点赞👍支持一下哟~

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。

THE END

c语言数据结构程序人生算法经验分享

二维码

Vue中间件的讲解案例分析

< <上一篇

)">

随机测试 Monkey Test

下一篇>>

搜索内容