初级数据结构(一)——顺序表

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

文中代码源文件已上传:数据结构源码

<-上一篇 NULL        |        初级数据结构(二)——链表 下一篇->

1、顺序表的特点

1.1、数组

        现实中数据记录一般都记录在表格中,如进货单、菜单等,它们的最大特点就是有序。表述中可以用第一项、第二项、第 n 项来描述表格中某个数据或者某串数据。在 C 语言中,数组的特点恰好匹配此功能。

        由于数组在内存中的储存方式就如同列表依序排布,对数组可以用 arr[n] 或者 *(arr+n) 来迅速获得第 n-1 项数据。再加上而且数组是 C 语言的原生类型,创建数组极其便利,作为有序数据的载体着实是不二之选。

1.2、结构

        顺序表为了方便使用,除了用数组作为数据载体外,一般还包含记录数组空间大小和开辟空间大小的两个变量。常以结构体将这三个变量作为成员变量进行囊括。主要有两种创建方式:

        柔性数组顺序表( Sequence table with flexible array ):

初级数据结构(一)——顺序表,C语言,数据结构,c语言,数据结构,算法

#include <stdlib.h>

//重定义数据类型
typedef int DATA;

//创建并重定义结构体类型
typedef struct SeqTab
{
    int size;           //数据长度
    int capacity;       //数据空间大小
    DATA arr[];         //数据载体柔性数组
}SeqTab;

int main()
{
    //开辟结构体空间
    SeqTab* sqList = (SeqTab*)malloc(sizeof(SeqTab) + sizeof(DATA)*4);
    //初始化数据长度及空间大小
    sqList->size = 0;
    sqList->capacity = 4;

    return 0;
}

        数组指针顺序表( Sequence table with array pointer ):

初级数据结构(一)——顺序表,C语言,数据结构,c语言,数据结构,算法

#include <stdlib.h>

//重定义数据类型
typedef int DATA;

//创建并重定义结构体类型
typedef struct SeqTab
{
    int size;           //数据长度
    int capacity;       //数据空间大小
    DATA* arr;          //数据载体数组指针
}SeqTab;

int main()
{
    //创建结构体变量
    SeqTab sqList;
    //开辟数据载体数组空间
    sqList.arr = (DATA*)malloc(sizeof(DATA)*4);
    //初始化数据长度及空间大小
    sqList.size = 0;
    sqList.capacity = 4;

    return 0;
}

2、顺序表创建

        接下来以数组指针顺序表为例进行演示。

2.1、文件结构

初级数据结构(一)——顺序表,C语言,数据结构,c语言,数据结构,算法

        seqTab.h :用于创建结构体类型及声明函数;

        sqFunction.c :用于创建顺序表初始化及增删改查的函数;

        main.c :仅创建 main 函数,用作测试。

2.2、前期工作

        在 seqTab.h 中先写入以下内容:

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

//用于初始化顺序表时开辟空间
#define INIT_SIZE 4

//顺序表数据类型,方便顺序表储存数据类型修改
typedef int DATATYPE;

//创建顺序表结构体类型
typedef struct SeqTab
{
	DATATYPE* data;
	int size;
	int capacity;
}SeqTab;

//---------------------函数声明---------------------
//初始化顺序表
extern void DataInit(SeqTab*);

//销毁顺序表
extern void DataDestory(SeqTab*);

//打印顺序表
extern void DataPrint(const SeqTab*);

         在 sqFunction.c 中包含 seqTab.h 并分别创建一个初始化顺序表和销毁顺序表的函数:

#include "seqTab.h"

//初始化顺序表
void DataInit(SeqTab* sq)
{
    //断言确保结构体指针不为空
	assert(sq);
    //为顺序表开辟空间
	sq->data = (DATATYPE*)malloc(INIT_SIZE * sizeof(DATATYPE));
    //加入判断防止空间开辟失败
	if (sq->data == NULL)
	{
		perror("Malloc Fail");
		return;
	}
    //初始化记录数据长度及开辟空间长度的变量
	sq->size = 0;
	sq->capacity = INIT_SIZE;
}

//销毁顺序表
void DataDestory(SeqTab* sq)
{
    //断言确保结构体指针不为空
	assert(sq);
    //释放顺序表数据空间
	free(sq->data);
    //数组指针置空
	sq->data = NULL;
    //数组长度及空间尺寸全部置0
	sq->size = 0;
	sq->capacity = 0;
}

//打印顺序表
void DataPrint(const SeqTab* sq)
{
    //断言确保结构体指针不为空
	assert(sq);
    //遍历顺序表并逐个数据打印
	for (int i = 0; i < sq->size; i++)
	{
		printf("%d ", sq->data[i]);
	}
	printf("\n");
}

        最后在 main.c 中包含 seqTab.h,并创建一个顺序表及初始化:

#include "seqTab.h"

int main()
{
	//创建顺序表
	SeqTab sqList;

    //初始化顺序表
	DataInit(&sqList);

    return 0;
}

        至此,前期工作准备完毕,之后便是对顺序表的数据进行增删改查。

3、顺序表操作

3.1、增

        插入数据一般为头部插入数据、尾部插入数据及指定位置插入数据。插入数据时除了写入数据到数组中,还需时刻判断开辟的空间尺寸是否足以容纳已有数据。

        先将以下三个函数声明添加到 seqTab.h 中:

//指定位置插入数据
extern void DataInsert(SeqTab*, int, DATATYPE);
//头部插入数据
extern void DataPushHead(SeqTab*, DATATYPE);
//尾部插入数据
extern void DataPushTail(SeqTab*, DATATYPE);

        然后便是 DataInsert 函数。如图:

初级数据结构(一)——顺序表,C语言,数据结构,c语言,数据结构,算法

        据此可以轻松写出其代码。以下写入 sqFunction.c 中: 

void DataInsert(SeqTab* sq, int pos, DATATYPE data)
{
    //数据有效性判断
	assert(sq);
	if (pos < 0 || pos > sq->size)
	{
		printf("Illegal Position : %d\n", pos);
		return;
	}
    //空间不足则创建空间
	if (sq->size + 1 >= sq->capacity)
	{
        //申请新空间
		DATATYPE* ptr_newSqData = (DATATYPE*)realloc(sq->data, sizeof(DATATYPE) * (sq->capacity * 2));
        //空间申请结果判断
		if (ptr_newSqData == NULL)
		{
			perror("Realloc Fail");
			return;
		}
        //赋予新空间地址
		sq->data = ptr_newSqData;
        //空间大小记录翻倍
		sq->capacity *= 2;
	}
    //数据后移直至腾出 pos 位置的空间
	for (int i = sq->size; i > pos; i--)
	{
		sq->data[i] = sq->data[i - 1];
	}
    //写入数据
	*(sq->data + pos) = data;
    //数据长度+1
	sq->size++;
}

        至于头插尾插数据,只不过是上述函数 pos 位置的区别。因此:

//pos = 0 便是头插
void DataPushHead(SeqTab* sq, DATATYPE data)
{
	DataInsert(sq, 0, data);
}
//pos = 数据尺寸便是尾插
void DataPushTail(SeqTab* sq, DATATYPE data)
{
	DataInsert(sq, sq->size, data);
}

        在 main 函数里写入下列代码验证一下:

	DataInsert(&sqList, 10, 32);   //报错
	DataPushTail(&sqList, 10);
	DataPrint(&sqList);            //打印 10
	DataPushHead(&sqList, 20);
	DataPrint(&sqList);            //打印 20 10
	DataPushHead(&sqList, 3);
	DataPushTail(&sqList, 6);
	DataPushHead(&sqList, 8);
	DataPushHead(&sqList, 7);
	DataPushHead(&sqList, 2);
	DataPushTail(&sqList, 100);
	DataPushTail(&sqList, 432);
	DataPrint(&sqList);            //打印 2 7 8 3 20 10 6 10 432

初级数据结构(一)——顺序表,C语言,数据结构,c语言,数据结构,算法

        结果与预期无误。至此插入功能便已完成。

3.2、删

        正如插入数据分为头插、尾插及指定插,删除也分头删及任意位删。与插入相反,删除数据需要在数据删除结束后关注数据长度与开辟的数据空间,当空间分配过大时,对多余空间进行回收。

        同样先将以下三个函数声明添加到 seqTab.h 中:

//指定位置删除数据
extern void DataRemove(SeqTab*, int);
//删除头部数据
extern void DataPopHead(SeqTab*);
//删除尾部数据
extern void DataPopTail(SeqTab*);

         DataRemove 函数流程图如下:

初级数据结构(一)——顺序表,C语言,数据结构,c语言,数据结构,算法

        根据图中逻辑在 sqFunction.c 中写入以下:

void DataRemove(SeqTab* sq, int pos)
{
    //数据有效性判断
	assert(sq);
	if (pos < 0 || pos > sq->size - 1)
	{
		printf("Illegal Position : %d\n", pos);
		return;
	}
    //列表不为空则执行
	if (sq->size - 1 >= 0)
	{
        //由 pos 位开始,之后所有数据前移 1 位
		for (int i = pos; i < sq->size - 1; i++)
		{
			sq->data[i] = sq->data[i + 1];
		}
        //数据长度-1
		sq->size--;
	}
    //开辟空间过大则执行
	if (sq->size < sq->capacity / 2)
	{
        //申请新空间
		DATATYPE* ptr_newSqData = (DATATYPE*)realloc(sq->data, sizeof(DATATYPE) * (sq->capacity / 2));
        //空间申请结果判断
		if (ptr_newSqData == NULL)
		{
			perror("Realloc Fail");
			return;
		}
        //赋予新空间地址
		sq->data = ptr_newSqData;
        //空间大小记录减半
		sq->capacity /= 2;
	}
}

         至于头删尾删数据,也同样是上述函数 pos 位置的区别:

//头删 pos = 0
void DataPopHead(SeqTab* sq)
{
	DataRemove(sq, 0);
}
//尾删 pos = 数据长度-1
void DataPopTail(SeqTab* sq)
{
	DataRemove(sq, sq->size - 1);
}

        之后同样是验证,将以下代码写到之前测试代码之后:

	DataRemove(&sqList, 100);    //报错
	DataRemove(&sqList, 3);
	DataPrint(&sqList);          //打印 2 7 8 20 10 6 100 432
	DataPopHead(&sqList);
	DataPrint(&sqList);          //打印 7 8 20 10 6 100 432
	DataPopTail(&sqList);
	DataPrint(&sqList);          //打印 7 8 20 10 6 100
	DataPopTail(&sqList);
	DataPopTail(&sqList);
	DataPopTail(&sqList);
	DataPopTail(&sqList);
	DataPopTail(&sqList);
	DataPrint(&sqList);          //打印 7
	DataPopTail(&sqList);
	DataPopTail(&sqList);
	DataPrint(&sqList);          //因为 size = 0 ,pos = -1 , 报错

初级数据结构(一)——顺序表,C语言,数据结构,c语言,数据结构,算法         删除数据功能完毕。

3.3、改

        改数据的功能实现起来,逻辑上毫无难度可言。以下函数声明添加到 seqTab.h 中:

//修改指定位置数据
extern void DataModify(SeqTab*, int, DATATYPE);

         在 sqFunction.c 中写入:

void DataModify(SeqTab* sq, int pos, DATATYPE data)
{
    //数据有效性判断
	assert(sq);
	if (pos < 0 || pos > sq->size - 1)
	{
		printf("Illegal Position : %d\n", pos);
		return;
	}
    //修改数据
	sq->data[pos] = data;
}

        在 main 函数中追加以下代码验证:

	for (int i = 0; i < 10; i++)
	{
		DataPushTail(&sqList, i);
	}
	DataPrint(&sqList);            //打印 0 1 2 3 4 5 6 7 8 9
	DataModify(&sqList, 100, 30);  //报错
	DataModify(&sqList, 3, 30);
	DataPrint(&sqList);            //打印 0 1 2 30 4 5 6 7 8 9

初级数据结构(一)——顺序表,C语言,数据结构,c语言,数据结构,算法

         完毕。

3.4、查

        查到数据返回该数据的位置,查不到返回 -1 。同样很简单。 seqTab.h 中写入声明:

//在表中查找数据
extern int DataSearch(SeqTab*, DATATYPE);

        然后是 sqFunction.c 中写入:

int DataSearch(SeqTab* sq, DATATYPE data)
{
    //数据有效性判断
	assert(sq);
    //遍历数组
	for (int i = 0; i < sq->size; i++)
	{
        //如果找到数据则返回下标
		if (sq->data[i] == data)
		{
			return i;
		}
	}
    //遍历完毕仍找不到数据返回 -1
	return -1;
}

        main 函数中验证:

	int num = 1200;
	int pos = DataSearch(&sqList, num);
	if (pos == -1)
	{
		printf("The number \"%d\" is not exist!\n", num);
	}
	else
	{
		printf("The position of number \"%d\" is %d\n", num, pos);
	}//打印不存在

	num = 9;
	pos = DataSearch(&sqList, num);
	if (pos == -1)
	{
		printf("The number \"%d\" is not exist!\n", num);
	}
	else
	{
		printf("The position of number \"%d\" is %d\n", num, pos);
	}//打印 9

	DataModify(&sqList, DataSearch(&sqList, 8), 11001);
	DataPrint(&sqList);    //打印 0 1 2 30 4 5 6 7 11001 9

初级数据结构(一)——顺序表,C语言,数据结构,c语言,数据结构,算法

        至此增删改查功能实现均已完毕。除此之外,还有排序、截断等其他一系列可以自定的操作。总之,操作顺序表就是操作数组,实现起来难度几乎为 0 。文章来源地址https://www.toymoban.com/news/detail-753991.html

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

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

领支付宝红包 赞助服务器费用

相关文章

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

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

    2024年03月10日
    浏览(85)
  • 数据结构与算法——顺序表(顺序存储结构)及初始化详解

    顺序表 ,全名 顺序存储结构 ,是线性表的一种。通过《什么是线性表》一节的学习我们知道,线性表用于存储逻辑关系为“一对一”的数据,顺序表自然也不例外。 不仅如此,顺序表对数据的物理存储结构也有要求。 顺序表存储数据时,会提前申请一整块足够大小的物理

    2024年02月16日
    浏览(39)
  • 数据结构——顺序表(C语言)

    1.线性表 (1).线性表是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表,链表,栈,队列,字符串... (2).线性表在逻辑上是线性结构,也就是说连续的一条直线。但是在物理结构上并不是一定是连续的,线性表

    2024年02月13日
    浏览(48)
  • 【数据结构<顺序表>】C语言

    线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上

    2024年02月05日
    浏览(40)
  • [数据结构 - C语言] 顺序表

    目录 1、线性表 2、顺序表 2.1 顺序表的概念 2.2 接口 3、接口实现 3.1 初始化 3.2 销毁 3.3 容量检测 3.4 打印数据 3.5 顺序表的头插 3.6 顺序表的尾插 3.7 顺序表的头删、尾删 3.8 顺序表查找 3.9 指定位置插入数据 线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性

    2023年04月21日
    浏览(35)
  • 数据结构与算法—顺序表

    目录 一、线性表 二、顺序表概念  三、实现顺序表 1、声明结构体 2、初始化 3、打印数据  4、销毁  5、尾插头插 尾插 判断是否扩容   头插 6、尾删头删 尾删 头删 7、 指定位置插入元素 8、 删除指定位置元素 9、 查找指定元素位置 10、修改指定位置元素 完整版附上: S

    2024年02月08日
    浏览(35)
  • 【数据结构】顺序表---C语言版

    顺序表是一种常见的数据结构,今天就让我来带领大家一起学习一下吧! 不会再休息,一分一毫了,OK,let’s go! 线性表(linear list)是n个具有 相同特性的数据元素 的有限序列。 线性表是一种在实际中广泛使 用的数据结构, 常见的线性表:顺序表、链表、栈、队列、字符

    2024年02月04日
    浏览(36)
  • 数据结构顺序表(C语言实现)

            从本章开始就是开始数据结构的开端,本章将会写出数据结构中的顺序表的代码实现,多会以注释的方法来描述一些细节(注释是我们程序员必须常用的工具)。         话不多说安全带系好,发车啦(建议电脑观看)。 附:红色,部分为重点部分;蓝颜色为需

    2024年02月10日
    浏览(50)
  • 【数据结构】C语言实现顺序栈

    大家好,很高兴又和大家见面啦!!! 在上一个篇章中,我们介绍了栈的基本概念,以及栈中的重要术语。通过介绍我们知道了栈的本质也是一种线性表,只不过它是一种操作受限的线性表。因此栈的实现方式与线性表的实现实际上是大同小异的。下面我们就来介绍一下如何

    2024年01月19日
    浏览(40)
  • 数据结构(C语言)——顺序表详解

    数据结构是计算机存储和组织数据的方式。常用的数据结构有:数组(Array)、栈(Stack)、队列(Queue)、链表(Linked List)、树(Tree)、图(Graph)、堆(Heap)等;而数据结构又可以通过逻辑结构与物理结构进行分类,逻辑结构是指数据元素之间的逻辑关系,也就是数据元

    2024年04月16日
    浏览(38)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包