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

数据结构入门指南：顺序表

9月前 作者：清水加冰 分类：Toy博客 阅读(50) 违法举报

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

目录

文章目录

前言

顺序表

静态顺序表

动态顺序表

总结

前言

        今天我们正式进入对数据结构的学习，顺序表是数据结构中最简单的一种线性数据结构，也是数据结构入门的试金石，如果对于顺序表中内容理解过难，可以先填补一下C语言中结构体、动态内存管理及指针部分的知识。这也是步入数据结构学习的基础。接下来我将向大家一一介绍顺序表以及实现。

顺序表

 概念及定义

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

 顺序表一般可以分为：

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

        顺序表的主要功能就是对数组数据进行管理，例如我想要增加、删除、修改数组中的数据时如果每次都手动输入就会很麻烦，于是就进阶到了顺序表，对数组数据进行管理操作。

静态顺序表

静态顺序表：使用定长数组存储元素

 定义一个顺序表：

#define N 100
typedef struct SeqList
{
	int data[N]
	int sz;//有效数据个数
}SL;

         这里使用typedef将我们自定义的结构体类型进行重命名，重命名为SL，所以在创建结构体变量时就可以使用SL来替代struct SeqList。

但是在大多数情况下我们都不会选择静态的顺序表，它是非常不实用的。静态顺序表存在的问题就在于它的静态：

  • 存储的容量是固定的
  • 当容量开辟过大，而仅仅使用了一小部分，就会造成空间的浪费。

 静态顺序表的实现相对简单，不需要动态开辟空间，扩容，初始化操作也比较简单，所以说我们今天主要对动态顺序表进行讲解介绍。

动态顺序表

         顺序表的动态存储就相对静态麻烦一点，不同点在于初始化，额外增加检查是否满添加一个扩容操作。如果是动态的顺序表，再使用静态定义的顺序表就不合适，因为需要判断顺序表是否满，所以这里再定义一个变量来记录顺序表的容量。

定义顺序表：

typedef int Datatype;//重定义数据类型，便于后续修改存储的数据类型
typedef struct SeqList
{
	Datatype* data;//Datatype*等价于 int*
	int sz;//有效数据个数
	int len;//容量
}SL;

         如果使用的是VS之类的这种集成式开发环境的编译器，本人推荐分装多文件进行编写程序，这样可以使代码更加清晰，最后我也会把多文件分装的代码附上。

        回到正题，已经创建好了顺序表，接下来就是顺序表的初始化。在进行该部分讲解之前，这里需要提到一个知识点，就是结构体传参，为什么要传结构体的地址，传值还是传址？早在C语言初阶就有提到，传值调用在函数内是数据的临时拷贝，出了函数机会被销毁，对原本的数据并不会有影响，对顺序表进行数据管理都是对表内数据进行修改，所以顺序表是使用传址调用。

         初始化需要将结构体的地址传过去，那要怎么传呢？很多初学者会搞混。认为定义的结构体就是顺序表，其实并不是，定义的结构体只是我们自己定义的顺序表类型，而顺序表我们还并没有创建。

int main()
{
	SL s;
    InitSeqList(&s);
    return 0;
}

        在主函数内创建一个结构体变量，这个结构体变量才是真正实质上的顺序表。在初始化时我们需要将顺序表的地址传过去，参数直接&s即可。

        我们传过去的是顺序表的地址，在函数定义时需要与之对应的形参进行接收，传过去的类型是结构体变量的地址（指针），所以这里需要一个结构类型的指针变量去接收。

void InitSeqList(SL* ps)

 接下来就是初始部分的实现：

void InitSeqList(SL* ps) {
	ps->data = (Datatype*)malloc(sizeof(Datatype) * N);//N为默认开辟的个数，这里N设置的值为3，便于测试增容
	if (ps->data == NULL)
	{
		perror("malloc");//输出错误原因
		exit(-1);//退出程序
	}
	ps->len = N;
	ps->sz = 0;
}

        初始化部分没有什么难点，主要需要大家注意：动态开辟时使用了malloc函数，可以参考一下博客：动态内存管理函数的使用与优化技巧。在动态内存分配时，可能开辟失败，开辟失败就会返回一个空指针（NULL），所以需要对返回值进行判断，如果为空就直接退出程序。sz有效的数据个数为0，len容量大小为N（3）。当然使用了malloc开辟空间就需要将空间释放，还给操作系统。

这里我们接着写一个函数对空间进行释放：

void DestorySL(SL* ps)
{
	free(ps->data);
	ps->len = 0;
	ps->sz = 0;
}

         顺序表的涉及的基础已经理解，那后续的操作就简单了我们接着继续对顺序表进行操作接口的实现，尾插：

void PushBackSL(SL* ps, Datatype x)
{
	SLCheck(ps);
	ps->data[ps->sz] = x;
	ps->sz++;
}

         从末尾插入是很简单的，但这里需要额外考虑的一点是，容量问题，容量是否够用，这里就需要进行扩容，在其他增加节点的操作时也需要扩容，为了便于使用，我们可以封装成一个函数检查容量是否满。

        检查函数都是在其他函数中调用的，所以就不能单纯&s，但是&s的值已经传给了ps（指针），所以我们可以将ps传过去。代码如下：

void SLCheck(SL* ps)
{
	if (ps->sz == ps->len)
	{
		Datatype* pc = (Datatype*)realloc(ps->data, sizeof(Datatype) * 2 * ps->len);
		if (pc == NULL)
		{
			perror("realloc");
			exit(-1);
		}
		ps->data = pc;
		ps->len *= 2;
	}

}

        从C语言转到对数据结构的学习，需要大家改变一下敲代码的习惯，C语言中的程序都相对较短，写完进行运行测试，但数据结构不同，一个程序可能存在多个接口，这就是需要我们写一部分测试一部分，这样避免在最后测试时发现几十个错误再改错高效的多。为了便于测试，我们继续封装一个打印数据的函数。

void printfSL(SL* ps)
{
	for (int i = 0; i < ps->sz; i++)
	{
		printf("%d ", ps->data[i]);
	}
	printf("\n");
}

测试时我们就朴实一点，直接传给它多个值：

int main()
{
	SL s;
	InitSeqList(&s);
	PushBackSL(&s, 6);
	PushBackSL(&s, 6);
	PushBackSL(&s, 6);
	PushBackSL(&s, 3);
	PushBackSL(&s, 3);
	PushBackSL(&s, 4);
	printfSL(&s);
	
	return 0;
}

 这样直接插入数据观察扩容和插入功能是否完善。接着继续尾插接口实现：

void PopBlackSL(SL* ps) {
	if (ps->sz == 0)
	{
		printf("顺序表为空\n");
		return;
	}
	ps->sz--;
}

        尾插也是很简单的，我们并不需要将原先的数据置为某个数字，只需要将sz也就是有效数据减一，这样下次插入数据时，就会将原先的数据自动覆盖。但是需要注意一点是，如果顺序表已经为空就不可以再减了（再减就会越界），所以增加一个判断顺序表的数据是否为空。后边的测试我就不再演示，可以在每个接口实现以后自主测试。

头插：

void PushFrontSL(SL* ps, Datatype x)
{
	SLCheck(ps);
	int end = ps->sz - 1;
	while (end >= 0)
	{
		ps->data[end + 1] = ps->data[end];
		end--;
	}
	ps->data[0] = x;
	ps->sz++;
}

         头插时我们需要将原先的数据向后移动一个位置，在第一个位置插入数据，在挪动数据的时候不能从头开始往后挪，那样会造成数据的覆盖，所以只能从后边开始一个一个的挪动。这里我们就能感受到，头插的效率是不高的。

 头删：

void SListPopFront(SL* ps) {
	for (int i = 0; i < ps->sz - 1; i++)
	{
		ps->data[i] = ps->data[i + 1];
	}
	assert(ps->sz > 0);//断言，判断有效数据个数是否大于0，小于0就直接报错
	ps->sz--;
}

         头删的实现就是将后一位的数据向前挪动，覆盖前一个数据，但这里需要注意数据被覆盖的问题，头删需要从下标为1的位置开始向前挪动，此外还需要注意sz的大小。

 位置插入：

void SLInsert(SL* ps, int pos, Datatype x) {
	assert(pos >= 0 && pos <= ps->sz);
	int end = ps->sz - 1;
	SLCheck(ps);
	while(end>=pos)
	{
		ps->data[end + 1] = ps->data[end];
		end--;
	}
	ps->data[pos] = x;
	ps->sz++;
}

         位置插入的原理和头插的思路相似，不同点在于停止的位置，数据插入位置，数据停止挪动的位置在下标为pos处，把下标为pos的数据修改为要插入的数据，此外还增加了一个判断，pos >= 0 和 pos <= ps->sz，pos=0就相当于头插，pos=sz就相当于尾插。

位置删除：

void SLErase(SL* ps, int pos)
{
	assert(pos >= 0 && pos < ps->sz);
	for (int i = pos; i < ps->sz-1; i++)
	{
		ps->data[i] = ps->data[i + 1];
	}
	ps->sz--;
}

         位置删除的原理就是将要删除位置后边的数据向前挪动，将该位置数据覆盖。挪动数据的部分操作，用for循环和while循环都是可以的，但是需要注意访问越界的问题，断言时pos是否合法问题，在插入删除操作中一定要注意。

查找：

int SqLFind(SL* ps, Datatype x) {
	
	for (int i = 0; i < ps->sz; i++)
	{
		if (x == ps->data[i])
			return i;
	}
	return -1;
}

        查找操作也是比较简单的，遍历这个顺序表，如果值相同就返回下标，否则返回-1。

修改：

void SLModify(SL* ps, int pos,Datatype x)
{
	assert(pos >= 0 && pos < ps->sz);
	ps->data[pos] = x;

}

        修改操作也是很简单的，唯一需要注意的点是断言的条件，注意是否越界访问，位置是否合法。全部的接口完成实现，完整代码附下：

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

#define N 3
typedef int Datatype;
typedef struct SeqList
{
	Datatype* data;
	int sz;//有效数据个数
	int len;//容量
}SL;
void InitSeqList(SL* ps) {
	ps->data = (Datatype*)malloc(sizeof(Datatype) * N);
	if (ps->data == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	ps->len = N;
	ps->sz = 0;
}
void DestorySL(SL* ps)
{
	free(ps->data);
	ps->len = 0;
	ps->sz = 0;
}
void SLCheck(SL* ps)
{
	if (ps->sz == ps->len)
	{
		Datatype* pc = (Datatype*)realloc(ps->data, sizeof(Datatype) * 2 * ps->len);
		if (pc == NULL)
		{
			perror("realloc");
			exit(-1);
		}
		ps->data = pc;
		ps->len *= 2;
	}

}
void PushBackSL(SL* ps, Datatype x)
{
	SLCheck(ps);
	ps->data[ps->sz] = x;
	ps->sz++;
}
void printfSL(SL* ps)
{
	for (int i = 0; i < ps->sz; i++)
	{
		printf("%d ", ps->data[i]);
	}
	printf("\n");
}
void PopBlackSL(SL* ps) {
	if (ps->sz == 0)
	{
		printf("顺序表为空\n");
		return;
	}
	ps->sz--;
}

void PushFrontSL(SL* ps, Datatype x)
{
	SLCheck(ps);
	int end = ps->sz - 1;
	while (end >= 0)
	{
		ps->data[end + 1] = ps->data[end];
		end--;
	}
	ps->data[0] = x;
	ps->sz++;
}
void SListPopFront(SL* ps) {
	for (int i = 0; i < ps->sz - 1; i++)
	{
		ps->data[i] = ps->data[i + 1];
	}
	assert(ps->sz > 0);
	ps->sz--;
}
int SqLFind(SL* ps, Datatype x) {
	for (int i = 0; i < ps->sz; i++)
	{
		if (x == ps->data[i])
			return i;
	}
	return -1;
}
void SLInsert(SL* ps, int pos, Datatype x) {
	assert(pos >= 0 && pos <= ps->sz);
	int end = ps->sz - 1;
	SLCheck(ps);
	while(end>=pos)
	{
		ps->data[end + 1] = ps->data[end];
		end--;
	}
	ps->data[pos] = x;
	ps->sz++;
}
void SLErase(SL* ps, int pos)
{
	assert(pos >= 0 && pos <= ps->sz);
	for (int i = pos; i < ps->sz-1; i++)
	{
		ps->data[i] = ps->data[i + 1];
	}
	ps->sz--;
}
void SLModify(SL* ps, int pos,Datatype x)
{
	assert(pos >= 0 && pos < ps->sz);
	ps->data[pos] = x;

}
int main()
{
	SL s;
	InitSeqList(&s);
	PushBackSL(&s, 1);
	PushBackSL(&s, 2);
	PushBackSL(&s, 3);
	PushBackSL(&s, 4);
	PushBackSL(&s, 5);
	PushBackSL(&s, 6);
	printfSL(&s);        //输出：1 2 3 4 5 6
	SLInsert(&s, 1, 20);
	printf("首次出现的位置下标是%d\n", SqLFind(&s, 6));//6
	printfSL(&s);        //输出：1 20 2 3 4 5 6
	PushFrontSL(&s, 10);
	printfSL(&s);        //输出：10 1 20 2 3 4 5 6
	SListPopFront(&s);
	printfSL(&s);        //输出：1 20 2 3 4 5 6
	SLErase(&s, 1);
	printfSL(&s);        //输出：1 2 3 4 5 6
	return 0;
}

文件分装代码如下：

文件创建：

数据结构入门指南：顺序表,数据结构,c语言,经验分享,其他

 SeqList.c

#include"SeqList.h"
void InitSeqList(SL* ps) {
	ps->data = (Datatype*)malloc(sizeof(Datatype) * N);
	if (ps->data == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	ps->len = N;
	ps->sz = 0;
}
void DestorySL(SL* ps)
{
	free(ps->data);
	ps->len = 0;
	ps->sz = 0;
}
void SLCheck(SL* ps)
{
	if (ps->sz == ps->len)
	{
		Datatype* pc = (Datatype*)realloc(ps->data, sizeof(Datatype) * 2 * ps->len);
		if (pc == NULL)
		{
			perror("realloc");
			exit(-1);
		}
		ps->data = pc;
		ps->len *= 2;
	}

}
void PushBackSL(SL* ps, Datatype x)
{
	SLCheck(ps);
	ps->data[ps->sz] = x;
	ps->sz++;
}
void printfSL(SL* ps)
{
	for (int i = 0; i < ps->sz; i++)
	{
		printf("%d ", ps->data[i]);
	}
	printf("\n");
}
void PopBlackSL(SL* ps) {
	if (ps->sz == 0)
	{
		printf("顺序表为空\n");
		return;
	}
	ps->sz--;
}

void PushFrontSL(SL* ps, Datatype x)
{
	SLCheck(ps);
	int end = ps->sz - 1;
	while (end >= 0)
	{
		ps->data[end + 1] = ps->data[end];
		end--;
	}
	ps->data[0] = x;
	ps->sz++;
}
void SListPopFront(SL* ps) {
	for (int i = 0; i < ps->sz - 1; i++)
	{
		ps->data[i] = ps->data[i + 1];
	}
	assert(ps->sz > 0);
	ps->sz--;
}
int SqLFind(SL* ps, Datatype x) {
	for (int i = 0; i < ps->sz; i++)
	{
		if (x == ps->data[i])
			return i;
	}
	return -1;
}
void SLInsert(SL* ps, int pos, Datatype x) {
	assert(pos >= 0 && pos <= ps->sz);
	int end = ps->sz - 1;
	SLCheck(ps);
	while (end >= pos)
	{
		ps->data[end + 1] = ps->data[end];
		end--;
	}
	ps->data[pos] = x;
	ps->sz++;
}
void SLErase(SL* ps, int pos)
{
	assert(pos >= 0 && pos <= ps->sz);
	for (int i = pos; i < ps->sz - 1; i++)
	{
		ps->data[i] = ps->data[i + 1];
	}
	ps->sz--;
}
void SLModify(SL* ps, int pos, Datatype x)
{
	assert(pos >= 0 && pos < ps->sz);
	ps->data[pos] = x;

}

 test.c

#include"SeqList.h"
int main()
{
	SL s;
	InitSeqList(&s);
	PushBackSL(&s, 1);
	PushBackSL(&s, 2);
	PushBackSL(&s, 3);
	PushBackSL(&s, 4);
	PushBackSL(&s, 5);
	PushBackSL(&s, 6);
	printfSL(&s);        //输出：1 2 3 4 5 6
	SLInsert(&s, 1, 20);
	printf("首次出现的位置下标是%d\n", SqLFind(&s, 6));//6
	printfSL(&s);        //输出：1 20 2 3 4 5 6
	PushFrontSL(&s, 10);
	printfSL(&s);        //输出：10 1 20 2 3 4 5 6
	SListPopFront(&s);
	printfSL(&s);        //输出：1 20 2 3 4 5 6
	SLErase(&s, 1);
	printfSL(&s);        //输出：1 2 3 4 5 6
	return 0;
}

 SeqList.h

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

#define N 3
typedef int Datatype;
typedef struct SeqList
{
	Datatype* data;
	int sz;//有效数据个数
	int len;//容量
}SL;
void InitSeqList(SL* ps);
void DestorySL(SL* ps);
//尾插
void PushBackSL(SL* ps, Datatype x);
//尾删
void PopBlackSL(SL* ps);
void SLCheck(SL* ps);
//头插
void PushFrontSL(SL* ps,Datatype x);
//头删
void SListPopFront(SL* ps);
//位置插入
void SLInsert(SL* ps, int pos, Datatype x);
//位置删除
void SLErase(SL* ps, int pos);
//位置查找
int SqLFind(SL* ps, Datatype x);
//顺序表数据输出
void printfSL(SL* ps);
//数据修改
void SLModify(SL* ps, int pos, Datatype x);

总结

        通过深入学习顺序表，我们可以了解它的内部结构和操作，如创建、插入、删除、查找、修改等。这些基本概念为我们理解和学习其他更复杂的数据结构打下了坚实的基础。文章来源地址https://www.toymoban.com/news/detail-609707.html

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

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

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

相关文章

  • 【数据结构入门指南】单链表

    【数据结构入门指南】单链表

     由于顺序表插入和删除元素需要移动大量数据，导致运行效率下降。因此引入了另一种数据结构 —— 链表 。链表又分为单链表和双链表。单链表结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在

    2024年02月14日
    浏览(45)
  • 【数据结构入门指南】二叉树

    【数据结构入门指南】二叉树

    二叉树是一棵特殊的树。一棵二叉树是结点的一个有限集合，该节点： ①：或者为空。 ②： 由一个根节点加上两棵别称为左子树和右子树的二叉树组成。 从上图可以看出： 二叉树不存在度大于2的结点. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树。 Tip

    2024年02月11日
    浏览(37)
  • 数据结构入门指南：单链表（附源码）

    数据结构入门指南：单链表（附源码）

    目录 前言 尾删 头删 查找 位置前插入  位置后插入  位置删除  位置后删除  链表销毁 总结         前边关于链表的基础如果已经理解透彻，那么接下来就是对链表各功能的实现，同时也希望大家能把这部分内容熟练于心，这部分内容对有关链表部分的刷题很有帮助。废话

    2024年02月14日
    浏览(61)
  • Python基础数据结构入门必读指南

    Python基础数据结构入门必读指南

    作者主页：涛哥聊Python 个人网站：涛哥聊Python 大家好，我是涛哥，今天为大家分享的是Python中常见的数据结构。 含义：数组是一种有序的数据结构，其中的元素可以按照索引来访问。数组的大小通常是固定的，一旦创建就不能更改。 基本操作： 含义：列表是Python中内置的

    2024年02月07日
    浏览(56)
  • 数据结构入门指南：带头双向循环链表

    数据结构入门指南：带头双向循环链表

    目录 文章目录 前言 1.结构与优势 2.链表实现       2.1 定义链表 2.2 创建头节点 2.3 尾插 2.4 输出链表 2.5 尾删 2.6 头插 2.7头删 2.8 节点个数 2.9 查找 2.10 位置插入 2.11 位置删除 2.12 销毁链表  3. 源码 总结         链表一共有8种结构，但最常用的就是无头单向链表、和带头

    2024年02月14日
    浏览(51)
  • 【数据结构入门指南】二叉树链式结构的实现（保姆级代码思路解读，非常经典）

    【数据结构入门指南】二叉树链式结构的实现（保姆级代码思路解读，非常经典）

    其他数据结构不同，二叉树的增删查改接口实现的意义不大（后续搜索树的增删查改才有意义）。普通初阶二叉树更重要的是学习控制结构，为后续的AVL树、红黑树等高级数据结构打下基础。同时大部分OJ题也出在此处。 所谓二叉树遍历(Traversal)是按照某种特定的规则，依次

    2024年02月11日
    浏览(47)
  • 【Java--数据结构】提升你的编程段位：泛型入门指南，一看就会！

    【Java--数据结构】提升你的编程段位：泛型入门指南，一看就会！

    泛型是一种编程概念，它允许我们编写可以适用于多种数据类型的代码。通过使用泛型，我们可以在编译时期将具体的 数据类型作为参数 传递给代码，从而实现代码 的复用和灵活性 。 在传统的编程中，我们通常需要为不同的数据类型编写不同的代码，这样会导致代码冗余

    2024年04月26日
    浏览(64)
  • 数据结构入门(C语言)顺序表的增删查改

    数据结构入门(C语言)顺序表的增删查改

    本章会用C语言来描述数据结构中的顺序表，实现简单的增删查改操作，其中头文件包含在新建的头文件SeqList.h内，顺序表的实现在新建的Seqlist.c内，主函数Text.c将会实现菜单，方便我们进行功能的选择。 顺序表是用一段物理地址 连续 的存储单元依次存储数据元素的线性结构

    2024年02月03日
    浏览(48)
  • 数据结构入门（C语言版）二叉树的顺序结构及堆的概念及结构实现应用

    数据结构入门（C语言版）二叉树的顺序结构及堆的概念及结构实现应用

    普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用 顺序结构的数组来存储 ，需要注意的是 这里的堆和操作系统虚拟进程地址空间中的堆是两回事 ，一个是 数据结构 ，一

    2023年04月19日
    浏览(53)
  • 数据结构入门（C语言版）线性表中顺序表介绍及接口实现

    数据结构入门（C语言版）线性表中顺序表介绍及接口实现

    C语言的学习结束，就该入门数据结构了呦 不论在程序员的工作上，还是在学习或是考研上，数据结构都是一门非常重要且值得我们一直研究探索的学科，可以说数据结构和算法就是编程的核心。OK，接下来我们来到数据结构的入门第一步就是学习线性表，接下来由作者来详细

    2023年04月12日
    浏览(48)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包