您好，欢迎来到五一七教育网。
科技 教育 生活 旅游 时尚 美容 美食 健康 体育 游戏 汽车 家电
搜索
您的当前位置：首页数据结构实战篇之顺序表

数据结构实战篇之顺序表

来源：五一七教育网

前言

        顺序表是线性结构中的一种基本的数据结构，它将一组元素按照线性顺序存储在一块连续的内存空间中。

        顺序表可以通过数组或者是固定大小的静态数组实现。数组具有随机访问的特性，通过索引可以快速访问数组中的任意元素。这使得顺序表在查找、访问元素时具有较高的效率。

        顺序表在插入和删除元素时需要移动其他元素来腾出或填补位置。如果顺序表的元素数量比较大或者频繁地进行插入和删除操作，会导致效率下降。

实现原理

        顺序表的实现原理是将元素按顺序存储在一块连续的内存空间中，通过数组来表示。

具体实现原理如下：

代码实现

头文件linelist.h如下：

#ifndef     __LINELIST_H__
#define     __LINELIST_H__

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "debug.h"

//定义数组元素最大值
#define     MAX     128
typedef     int     data_t;

//定义线性表数据结构
//包含固定大小的数组(本工程仅用整型数组表示,后续应用可以使用结构体数组) + 记录
typedef struct{
    data_t num[MAX];//规定大小的顺序储存数组
    int    last;    //表征线性表数组最后一个元素的下标
}linelist,*linelink;//宏定义 线性表数据结构体和线性表数据结构指针

//函数声明
linelink linelist_creat(void);//线性表创建
int linelist_free(linelink L);//线性表内存释放

int linelist_empty(linelink L);//判断线性表是否为非满/满
int linelist_length(linelink L);//获取线性表长度
int linelist_insert(linelink L,int pos,int data);//线性表插入
int linelist_delete(linelink L,int pos);//线性表某数据删除
int linelist_change(linelink L,int pos,int data);//线性表数据更改
int linelist_locate(linelink L,int data);//线性表数据定位
int linelist_show(linelink L);//线性表遍历显示

#endif

C文件linelist.c如下：

#include "linelist.h"


//线性表/顺序表创建
linelink linelist_creat(void)
{
	linelink H;

	H = (linelink)malloc(sizeof(linelist));//堆开辟 sizeof(linelist) 字节大小的内存空间

	//判断malloc是否成功
	if(H == NULL){
		return NULL;
	}

	//申请的内存清空
	memset(H,0,sizeof(linelist));

	H->last = -1;//数组表尾下标为 -1,表征线性表数据为空

	return H;
}

//线性表内存释放
//ret:1 -- success 0 -- fail
int linelist_free(linelink L)
{
	//线性表指针参数检错
	if(L == NULL)
		return 0;

	L->last = -1;
	free(L);//释放内存
	L = NULL;

	return 1;
}


//判断线性表是否为非满/满
//ret: 0--非满	1--已满
int linelist_empty(linelink L)
{
	if(L->last < MAX){
		return 0;	
	}

	return 1;
}

//获取线性表长度
int linelist_length(linelink L)
{
	return L->last + 1;
}

//线性表任意插入
//ret：1--success  0--fail
int linelist_insert(linelink L,int pos,int data)
{
	//参数检错
	if(pos < 0 || pos > L->last + 1){
		pr_debug("Para have error!\n");
		return 0;
	}

	//判断线性表是否已满
	if(L->last == MAX - 1){
		pr_debug("The linelist is full!\n");
		return 0;
	}
	
	//move back:数组元素向后移动
	for(int i = L->last;i >= pos;i --)
	{
		L->num[i + 1] = L->num[i];
	}
	
	//更新填充数据
	L->num[pos] = data;
	L->last ++;

	return 1;
}

//线性表某数据删除
//ret：1--success  0--failed
int linelist_delete(linelink L,int pos)
{
	//判断线性表是否为空表
	if(L->last == -1)
	{
		pr_debug("The list is empty!\n");
		return 0;
	}

	//参数检错
	if(pos < 0 || pos > L->last)
	{
		pr_debug("Para have error!\n");
		return 0;
	}

	//向前移动数据
	for(int i = pos;i < L->last;i ++)
	{
		L->num[i] = L->num[i + 1];
	}
	
	L->num[L->last] = 0;//最后一个数据清零
	L->last --;
	
	return 1;
}

//线性表数据更改
//1--sucess  0-failed
int linelist_change(linelink L,int pos,int data)
{
	//参数检错
	if(pos < 0 || pos > L->last)
	{
		pr_debug("Para have error!\n");
		return 0;
	}
	
	//判断线性表是否为空表
	if(L->last == -1)
	{
		pr_debug("The list is empty!\n");
		return 0;
	}

	//改变某位置下数据
	L->num[pos] = data;

	return 1;
}

//线性表数据定位
//ret:success -- 查找到的元素下标索引 failed -- -1
int linelist_locate(linelink L,int data)
{
	//判断线性表是否为空表
	if(L->last == -1)
	{
		pr_debug("The list is empty!\n");
		return 0;
	}

	for(int i = L->last;i >= 0;i --)
	{
		if(data == L->num[i])
		{
			return i;
		}
	}
	return -1;
}


//线性表遍历显示
//ret:1 -- success 0 -- failed
int linelist_show(linelink L)
{
	if(L == NULL)
		return 0;

	for(int i = 0;i <= L->last;i ++)
	{
		printf("%d  ",L->num[i]);
	}
	puts("");

	return 1;
}

main.c代码如下：

#include "linelist.h"
#include "debug.h"

void insert(void);
void insert1(void);
void delete(void);
void change(void);
void locate(void);

//线性表/顺序表学习和使用
int main(int agrc,const char *agrv[])
{
//	insert();
//	insert1();
//	delete();
//	change();
	locate();

	return 0;
}


void insert(void)
{
	linelink L1;

	//创建线性表/顺序表
	L1 = linelist_creat();

	//创建线性表失败,打印ERROR
	if(L1 == NULL){
		pr_debug("malloc failed!\n");
	}
	
	linelist_insert(L1,0,74);
	linelist_insert(L1,0,58);
	linelist_insert(L1,0,);
	linelist_insert(L1,0,75);
	linelist_insert(L1,0,88);
	
	linelist_show(L1);
	printf("L1->last = %d\n",L1->last);

	linelist_insert(L1,1,99);
	linelist_insert(L1,5,100);

	linelist_show(L1);
	printf("L1->last = %d\n",L1->last);
	
	linelist_free(L1);
	
}

void insert1(void)
{
	linelink L1;

	//创建线性表/顺序表
	L1 = linelist_creat();

	//创建线性表失败,打印ERROR
	if(L1 == NULL){
		pr_debug("malloc failed!\n");
	}
	
	linelist_insert(L1,0,74);
	linelist_insert(L1,1,58);
	linelist_insert(L1,2,);
	linelist_insert(L1,3,75);
	linelist_insert(L1,4,88);
	
	linelist_show(L1);
	printf("L1->last = %d\n",L1->last);

	linelist_insert(L1,1,99);
	linelist_insert(L1,5,100);

	linelist_show(L1);
	printf("L1->last = %d\n",L1->last);

	
	linelist_free(L1);
}
void delete(void)
{
	linelink L1;

	//创建线性表/顺序表
	L1 = linelist_creat();

	//创建线性表失败,打印ERROR
	if(L1 == NULL){
		pr_debug("malloc failed!\n");
	}
	
	linelist_insert(L1,0,74);
	linelist_insert(L1,0,58);
	linelist_insert(L1,0,);
	linelist_insert(L1,0,75);
	linelist_insert(L1,0,88);//空表头插入
	
	linelist_insert(L1,1,99);//中间位置插入
	linelist_insert(L1,5,100);

	linelist_show(L1);
	printf("L1->last = %d\n",L1->last);
	
	linelist_delete(L1,0);
	linelist_delete(L1,5);//删除任意位置元素

	linelist_show(L1);
	printf("L1->last = %d\n",L1->last);

	linelist_free(L1);
	
}

void change(void)
{
	linelink L1;

	//创建线性表/顺序表
	L1 = linelist_creat();

	//创建线性表失败,打印ERROR
	if(L1 == NULL){
		pr_debug("malloc failed!\n");
	}
	
	linelist_insert(L1,0,74);
	linelist_insert(L1,1,58);
	linelist_insert(L1,2,);
	linelist_insert(L1,3,75);
	linelist_insert(L1,4,88);//空表头插入
	
	linelist_insert(L1,1,99);//中间位置插入
	linelist_insert(L1,5,100);

	linelist_show(L1);
	printf("L1->last = %d\n",L1->last);

	linelist_change(L1,1,33);
	linelist_change(L1,2,44);

	linelist_show(L1);
	printf("L1->last = %d\n",L1->last);

	linelist_free(L1);
	
}

void locate(void)
{
	linelink L1;

	//创建线性表/顺序表
	L1 = linelist_creat();

	//创建线性表失败,打印ERROR
	if(L1 == NULL){
		pr_debug("malloc failed!\n");
	}
	
	linelist_insert(L1,0,74);
	linelist_insert(L1,1,58);
	linelist_insert(L1,2,);
	linelist_insert(L1,3,75);
	linelist_insert(L1,4,88);//空表头插入
	
	linelist_insert(L1,1,99);//中间位置插入
	linelist_insert(L1,5,100);

	linelist_show(L1);
	printf("L1->last = %d\n",L1->last);

	linelist_change(L1,1,33);
	linelist_change(L1,2,44);

	linelist_show(L1);
	printf("L1->last = %d\n",L1->last);

	printf("locate(44) = %d\n",linelist_locate(L1,44));

	linelist_free(L1);
	
}

顺序表应用场景

        顺序表（或称为数组）是一种线性数据结构，它使用连续的内存空间来存储相同类型的数据。由于其在内存中的紧凑性和直接访问元素的能力，顺序表被广泛应用于各种场景中。

以下是一些顺序表常见的应用场景：

  1. 数据存储与检索：顺序表适用于需要频繁进行数据的存储和检索的情况。例如，在图书管理系统中，可以使用顺序表来存储图书的信息，通过索引号快速定位和检索图书。

  2. 线性表操作：顺序表是线性表的一种实现方式，适用于需要按顺序访问元素的场景。比如，在学生成绩管理系统中，可以使用顺序表来存储学生成绩，并按学号排序或按成绩查找学生。

  3. 缓存机制：顺序表也可用于实现缓存机制。利用顺序表的连续存储特性，可以将最频繁访问的数据存储在顺序表中，以提高数据的读取效率。

  4. 算法实现：顺序表在算法实现过程中经常被使用。例如，排序算法中的快速排序、归并排序等都可以使用顺序表进行实现。

  5. 简单的数据库：对于小规模的数据存储需求，顺序表可以作为简单的数据库来使用。例如，在一个学生信息管理系统中，可以使用顺序表来存储学生信息。

总的来说，顺序表适用于需要频繁存取和操作元素的场景，在内存空间较为有限且元素数量不会频繁变化的情况下尤其适用。

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文

Copyright © 2019- 517ttc.cn 版权所有 赣ICP备2024042791号-8

违法及侵权请联系：TEL:199 18 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务