1. Toy模板网首页
  2. > Toy博客

数据结构之顺序表篇

9月前 作者：青山与你 分类：Toy博客 阅读(32) 违法举报

这篇具有很好参考价值的文章主要介绍了数据结构之顺序表篇。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、顺序表概念
二、顺序表各类接口实现
*顺序表初始化
**顺序表销毁
***顺序表插入操作
****顺序表删除操作
*****顺序表查找操作
******顺序表实现打印操作
三、顺序表整体实现源码
*SeqList.h
**SeqList.c
***test.c

一、顺序表概念

讲顺序表之前先引入线性表概念，线性表是n个有相同特性的数据元素的有限序列，而常见的线性表又有：顺序表、链表、栈、队列、串，而例如图、树就是非线性表；
顺序表概念：顺序表向内存中要了一块连续的空间，然后依次存储数据，就是一个一个的挨着存储，而且里面存放的数据类型是同一种类型，就是c语言中的一维数组。
而顺序表又可分为静态的和动态的，静态顺序表就是给定一个空间，这个空间大小就定死了，不可再修改，那样的话就会造成空间浪费或者空间不足，比如：电梯超重不能运行，就是给定人数为13人，多了就不能升降（当然这只是理论上的）；静态顺序表的空间不可改变，因此用动态顺序表比较合适，按照自己的需求向堆中申请空间一次不够再第二次第三次直到申请空间足够，这样不会造成空间过多的浪费。
在顺序表中要实现对数据的各种操作包括增、删、查、改。而其中增和删又可以在尾部，中间，头部进行

二、顺序表的各类接口实现

以下是顺序表存储的结构化以及常用头文件包含

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SDataType;//类型想换就换，不然在后面换时需要每一个都换类型
#define INIT_CAPACITY 4//对最开始空间容量为4
typedef struct SeqList
{
	SDataType *a;//动态分配数组
	int size;//有效数据个数
	int capacity;//数组容量
}SL;

*顺序表初始化代码

void SeqInit(SL* ps)
{
	ps->a = (SDataType*)malloc(sizeof(SDataType)*INIT_CAPACITY);//向堆动态申请内存空间
	if (ps->a == NULL)//但凡申请都有可能失败
	{
		perror("malloc fail");
		return;
	}
	ps->size = 0;//初始条件下数组中没有数据
	ps->capacity = INIT_CAPACITY;//一上来就先给数组4个空间大小
}

**顺序表销毁代码

void SeqDestory(SL* ps)
{
	free(ps->a);//堆中开辟的需要释放
	ps->a = NULL;//释放之后置空
	ps->size = ps->capacity = 0;//空间大小置为0
}

***顺序表插入代码（包含头插，尾插，任意位置插入）
顺序表插入过程就如插队一样，当中午下课后，去食堂排队吃饭，一个挨着一个排好，这时忽然走来一个人，他可以选择就在队伍末尾跟上，也可以在队头和其他位置插入俗称插队，当然在其后面的肯定不安逸，因为他们都要向后挪动一位，这时顺序表插入就比如排队
数据结构顺序表的数据,数据结构,链表
顺序表插入算法思路：从最末尾开始向后挪动，直到空出一个位置，然后将数据插入进去，顺序表长度加一
其中空间容量不够需要给它扩容
尾插时间复杂度为O(1）
最坏的情况下，每一个元素都要向后移到，所以时间复杂度为O(n)

当然在顺序表插入数据时需要考虑空间是否足够，以下是对顺序表增容代码
void Checkcpacity(SL* ps)
{
//扩容
if (ps->size == ps->capacity)
{
SDataType* tmp = (SDataType*)realloc(ps->a, sizeof(SDataType) * ps->capacity * 2);//扩容看自己喜欢，但是二倍较为合适
if (tmp == NULL)
{
printf(“realloc fail”);
exit(-1);
}

	ps->capacity *= 2;
	ps->a = tmp;//将新开辟的空间给数组a
}

}

*尾插代码

void SeqPushBack(SL* ps, SDataType x)
{
	扩容
	//if (ps->size == ps->capacity)
	//{
	//	SDataType* tmp = (SDataType*)realloc(ps->a, sizeof(SDataType) *ps->capacity*2);//扩容看自己喜欢，但是二倍较为合适
	//	if (tmp == NULL)
	//	{
	//		printf("realloc fail");
	//		exit(-1);
	//	}

	//	ps->capacity *= 2;
	//	ps->a = tmp;//将新开辟的空间给数组a
	//}

	Checkcpacity(ps);

	ps->a[ps->size++] = x;
}

头插代码

void SeqPushFront(SL* ps, SDataType x)
{
	assert(ps);
	Checkcpacity(ps);
	int begin = 0;
	int end = ps->size;
	while (end >= 0)
	{
		ps->a[end] = ps->a[end - 1];
		end--;
	}

	ps->a[0] = x;
	ps->size++;



}

任意位置插入

void SeqInsert(SL* ps, int pos, SDataType x)
{
	assert(ps);
	Checkcpacity(ps);
	assert(pos >= 0 && pos <= ps->size);

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

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

****顺序表删除操作
也包括头删尾删和任意位置删除，删除可以理解为是后一个把前一个覆盖，然后顺序表长度减一
数据结构顺序表的数据,数据结构,链表
删除算法在末尾删时间复杂度就是最好的情况为O(1)，它不必循环
最坏的情况是在头部删除，删除一个就要挪动n-1个数据，其时间复杂度为O(N)，删除操作的时间复杂度就为O(n)

头删

void SeqPopFront(SL* ps)
{
	assert(ps);
	int begin = 0;
	assert(ps->size > 0);
	while (begin < ps->size - 1)
	{
		ps->a[begin] = ps->a[begin + 1];
		begin++;
	}

	ps->size--;

}
**``尾删**

```c
void SeqPopBack(SL* ps)
{/*
	if (ps->size == 0)
	{
		return;
	}*/


	assert(ps->size > 0);//断言可以让你知道是哪里出了问题
	ps->size--;
}

任意位置删除

void SeqErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size - 1);
	assert(ps->size > 0);

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

	ps->size--;

}

*****顺序表查找与修改操作
查找

int SeqFind(SL* ps, SDataType x)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
		{
			return i;
		}
	}

	return -1;
}

修改

void SeqModify(SL* ps, int pos, SDataType x)
{
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (i == pos)
		{
			ps->a[i] = x;
		}
	}
}

******顺序表打印

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

	printf("\n");
}

****三、顺序表整体实现源码
SeqList.h

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


#define INIT_CAPACITY 4//初始容量
typedef int SDataType;//类型想换就换，不然在后面换时需要每一个都换类型

typedef struct SeqList
{
	SDataType *a;
	int size;//有效数据个数
	int capacity;//空间容量不够考虑扩容
}SL;

void SeqInit(SL* ps);//顺序表初始化

void SeqDestory(SL* ps);//顺序表销毁

void Seqprint(SL* ps);//顺序表输出

void SeqPushBack(SL* ps, SDataType x);//尾插

void SeqPopBack(SL* ps);//尾删

void SeqPushFront(SL* ps, SDataType x);//头插

void SeqPopFront(SL* ps);//头删

void SeqErase(SL* ps, int pos);//删除pos位置的元素

void SeqInsert(SL* ps, int pos, SDataType x);//在pos位置插入x

int SeqFind(SL* ps, SDataType x);//查找值为x的位置

void SeqModify(SL* ps, int pos, SDataType x);//修改

SeqList.c

#include"SeqList.h"

void SeqInit(SL* ps)
{
	ps->a = (SDataType*)malloc(sizeof(SDataType)*INIT_CAPACITY);
	if (ps->a == NULL)
	{
		perror("malloc fail");
		return;
	}
	ps->size = 0;
	ps->capacity = INIT_CAPACITY;
}

void SeqDestory(SL* ps)
{
	free(ps->a);//堆中开辟的需要释放
	ps->a = NULL;//释放之后置空
	ps->size = ps->capacity = 0;//空间大小置为0
}

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

	printf("\n");
}

void Checkcpacity(SL* ps)
{
	//扩容
	if (ps->size == ps->capacity)
	{
		SDataType* tmp = (SDataType*)realloc(ps->a, sizeof(SDataType) * ps->capacity * 2);//扩容看自己喜欢，但是二倍较为合适
		if (tmp == NULL)
		{
			printf("realloc fail");
			exit(-1);
		}

		ps->capacity *= 2;
		ps->a = tmp;//将新开辟的空间给数组a
	}
}


void SeqPushBack(SL* ps, SDataType x)
{
	扩容
	//if (ps->size == ps->capacity)
	//{
	//	SDataType* tmp = (SDataType*)realloc(ps->a, sizeof(SDataType) *ps->capacity*2);//扩容看自己喜欢，但是二倍较为合适
	//	if (tmp == NULL)
	//	{
	//		printf("realloc fail");
	//		exit(-1);
	//	}

	//	ps->capacity *= 2;
	//	ps->a = tmp;//将新开辟的空间给数组a
	//}

	Checkcpacity(ps);

	ps->a[ps->size++] = x;
}

void SeqPopBack(SL* ps)
{/*
	if (ps->size == 0)
	{
		return;
	}*/


	assert(ps->size > 0);//断言可以让你知道是哪里出了问题
	ps->size--;
}

void SeqPushFront(SL* ps, SDataType x)
{
	assert(ps);
	Checkcpacity(ps);
	int begin = 0;
	int end = ps->size;
	while (end >= 0)
	{
		ps->a[end] = ps->a[end - 1];
		end--;
	}

	ps->a[0] = x;
	ps->size++;



}

void SeqPopFront(SL* ps)
{
	assert(ps);
	int begin = 0;
	assert(ps->size > 0);
	while (begin < ps->size - 1)
	{
		ps->a[begin] = ps->a[begin + 1];
		begin++;
	}

	ps->size--;

}

void SeqInsert(SL* ps, int pos, SDataType x)
{
	assert(ps);
	Checkcpacity(ps);
	assert(pos >= 0 && pos <= ps->size);

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

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

void SeqErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size - 1);
	assert(ps->size > 0);

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

	ps->size--;

}

int SeqFind(SL* ps, SDataType x)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
		{
			return i;
		}
	}

	return -1;
}

void SeqModify(SL* ps, int pos, SDataType x)
{
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (i == pos)
		{
			ps->a[i] = x;
		}
	}
}

test.c

#include"SeqList.h"

void test()
{
	SL s;
	SeqInit(&s);//传结构体地址过去，形参改变实参
	SeqPushBack(&s, 1);
	SeqPushBack(&s, 2);
	SeqPushBack(&s, 3);
	SeqPushBack(&s, 4);
	SeqPushBack(&s, 5);
	Seqprint(&s);
	/*SeqPopBack(&s);
	SeqPopBack(&s);
	SeqPopBack(&s);
	SeqPopBack(&s);
	Seqprint(&s);
	SeqPopBack(&s);
	SeqPopBack(&s);
	SeqPopBack(&s);
	Seqprint(&s)*/;

	SeqPushFront(&s, 9);
	Seqprint(&s);
	/*SeqPopFront(&s);
	SeqPopFront(&s);
	SeqPopFront(&s);
	SeqPopFront(&s);*/
	//SeqPopFront(&s);
	//SeqPopFront(&s);
	//SeqPopFront(&s);
	//SeqPopFront(&s);
	//SeqPopFront(&s);
	//SeqPopFront(&s);
	//SeqPopFront(&s);
	SeqPopFront(&s);
	//SeqPopFront(&s);
	//Seqprint(&s);
	SeqInsert(&s, 3, 10);
	Seqprint(&s);

	SeqErase(&s, 3);
	Seqprint(&s);

	int pos = SeqFind(&s, 3);
	printf("%d\n", pos);

	if (pos != -1)
	{
		SeqModify(&s, pos, 10);
	}

	Seqprint(&s);
	SeqDestory(&s);
}

int main()
{
	test();

	return 0;
}

总结

顺序表有优点也有缺点
优点：尾插、尾删效率贼高，也可以按下表来访问顺序表中的元素
缺点：在顺序表中出了尾部上的插入删除外，在其他位置删除或者插入效率都极低，而且在空间不够扩容的时候容易造成空间浪费
好了数据结构顺序表篇就结束了，球球各位佬们一键四练叭！你们的支持对于我来说尤为重要文章来源地址https://www.toymoban.com/news/detail-783254.html

到了这里，关于数据结构之顺序表篇的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构和算法初阶(C语言)】复杂链表（随机指针，随机链表的复制）题目详解+链表顺序表结尾

    【数据结构和算法初阶(C语言)】复杂链表（随机指针，随机链表的复制）题目详解+链表顺序表结尾

    目录  1.随机链表的复制 1.2题目描述  1.3题目分析 1.4解题： 2.顺序表和链表对比 2.1cpu高速缓存利用率 3.结语 一个长度为  n  的链表，每个节点包含一个额外增加的随机指针  random   该指针可以指向链表中的任何节点或空节点。        构造这个链表的  深拷贝 。 深拷贝

    2024年03月10日
    浏览(83)
  • 数据结构刷题训练——链表篇（二）

    数据结构刷题训练——链表篇（二）

    目录 前言 1.题目一：链表分割 1.1 思路 1.2 分析  1.3 题解 2. 题目二：相交链表 2.1 思路 2.2 分析 2.3 题解 3. 题目三：环形链表 3.1 思路 3.2 分析 3.3 题解 总结         本期继续分享链表相关的OJ题目，在这个专栏博客中，我们将提供丰富的题目资源和解题思路，帮助读者逐步

    2024年02月14日
    浏览(39)
  • 数据结构刷题训练——链表篇（一）

    数据结构刷题训练——链表篇（一）

    目录 前言 题目一：链表的中间节点 思路 分析 题解  题目二：链表中倒数第k个结点 思路 分析  题解 题目三：合并两个有序链表 思路 分析 题解  方法二 题解  题目四：链表的回文结构 思路 分析 题解 总结         今天我将开启一个新的专栏，数据结构与算法刷题训练营

    2024年02月14日
    浏览(32)
  • 数据结构刷题训练——链表篇（三）

    数据结构刷题训练——链表篇（三）

    目录 文章目录 前言 1. 题目一：环形链表Ⅱ 1.1 思路 1.2 分析 1.3 题解 1.4 方法二 2. 题目二：复制带随机指针的链表 2.1 思路 2.2 分析 2.3 题解 总结         在这个专栏博客中，我们将提供丰富的题目资源和解题思路，帮助读者逐步提高解题能力。同时，我们也将分享一些刷题

    2024年02月13日
    浏览(36)
  • ＜数据结构＞ 链表 - 链表的概念及结构

    ＜数据结构＞ 链表 - 链表的概念及结构

    概念： 链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的 逻辑顺序 是通过链表中的 指针链接 次序实现的 1、链表由一系列结点（链表中每一个元素称为结点）组成。 2、结点可以在运行时动态(malloc)生成。 3、每个结点包括两个部分：一个是存储数据元素的

    2023年04月09日
    浏览(44)
  • 【数据结构】反转链表、链表的中间节点、链表的回文结构（单链表OJ题）

    【数据结构】反转链表、链表的中间节点、链表的回文结构（单链表OJ题）

    正如标题所说，本文会图文详细解析三道单链表OJ题，分别为：  反转链表 （简单）  链表的中间节点 （简单）  链表的回文结构 （较难） 把他们放在一起讲的原因是：  反转链表 和  链表的中间节点 是  链表的回文结构 的基础 为什么这样说？请往下看： 目录 1. 反转链

    2024年02月13日
    浏览(68)
  • 【数据结构】顺序表的学习

    【数据结构】顺序表的学习

    前言:在之前我们学习了C语言的各种各样的语法，因此我们今天开始学习数据结构这一个模块，因此我们就从第一个部分来开始学习\\\" 顺序表 \\\"。 💖 博主CSDN主页:卫卫卫的个人主页 💞 👉 专栏分类:数据结构 👈 💯代码仓库:卫卫周大胖的学习日记💫 💪关注博主和博主一起学

    2024年02月05日
    浏览(44)
  • 【数据结构】顺序表的定义

    【数据结构】顺序表的定义

    🎈个人主页：豌豆射手^ 🎉欢迎 👍点赞✍评论⭐收藏 🤗收录专栏：数据结构 🤝希望本文对您有所裨益，如有不足之处，欢迎在评论区提出指正，让我们共同学习、交流进步！ 在数据结构的世界里，顺序表是一种常见且基础的线性数据结构。它以其简洁、直观的特性，广

    2024年04月08日
    浏览(51)
  • 【（数据结构）- 顺序表的实现】

    【（数据结构）- 顺序表的实现】

    先来看两张图片 数据结构是由“数据”和“结构”两词组合⽽来。 什么是数据？ 常见的数值1、2、3、4…、教务系统里保存的用户信息（姓名、性别、年龄、学历等等）、网页里肉眼可以看到的信息（文字、图片、视频等等），这些都是数据 什么是结构？ 当我们想要使用大

    2024年02月07日
    浏览(48)
  • 数据结构--顺序表的查找

    数据结构--顺序表的查找

    目标： GetElem(L,i):按位查找操作。获取表L中第i个位置的元素的值。 代码实现 时间复杂度 O(1) 由于顺序表的各个数据元素在内存中连续存放，因此可以根据起始地址和数据元素大小立即找到第i个元素——“随机存取”特性 目标： LocateElem(Le):按值查找操作。在表L中查找具有给

    2024年02月11日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包