首页 > 其他分享 >数据结构~~顺序表

数据结构~~顺序表

时间：2024-07-27 23:25:09浏览次数：13  
标签：数据结构 int void SLDatatype 顺序 SL ps1 size

目录

一、顺序表的概念

二、顺序表的接口实现 

1.顺序表初始化

2.顺序表销毁

3.检查空间并扩容

4.顺序表尾插、顺序表头插

5.顺序表尾删、顺序表头删

6.顺序表查找

7.顺序表在pos位置插入x、删除pos位置的值

三、完整代码

四、总结

一、顺序表的概念

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

顺序表一般可以分为：

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

#define N 10
typedef int SLDataType;
typedef struct SeqList
{
  SLDateType a[N];//定长数组
  size_t size;         //有效数据的个数
}SL;

这个就是静态的顺序表的结构体，但是静态的是存在缺陷的，比如我们如果要存11个数据，这样就存不下来，如果我们这个N给的太大，就浪费内存空间，所以我们用动态开辟的方法来实现才是最好的。

动态：使用动态开辟的数组存储

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

二、顺序表的接口实现 

SeqList.h:内容包括头文件的包含，结构体定义和接口函数的声明。顺序表的接口包括顺序表的初始化、增 (头插、尾插、指定下标）删（头删、尾删、指定下标）查改。

//SeqLish.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
typedef int SLDatatype;
typedef struct SeqLish
{	
	SLDatatype* a;
	int size;
	int capacity;
}SL;

void SLInit(SL* ps1);//初始化

void SLDesttoy(SL* ps1);//结束 释放顺序表

void SLPrint(SL* ps1);//打印
void SLCheckCapacity(SL* ps1);//扩容
void SLPushBack(SL* ps1,SLDatatype x);  //尾插
void SLPushFront(SL* ps1,SLDatatype x);//头插

void SLPopBack(SL* ps1); //尾删
void SLPopFront(SL* ps1);//头删

void SLInsert(SL* ps1, int pos,SLDatatype x);//指定增加
void SLErase(SL* ps1, int pos);//指定删除

//找到返回下标，没有找到返回-1
int SLFind(SL* ps1, SLDatatype x);//查
void SLModify(SL* ps1, int pos, SLDatatype x);//改

 SeqList.c:主要内容为函数接口的实现。

1.顺序表初始化

一般先初始化四个元素

void SLInit(SL* ps1)
{
	ps1->a = (SLDatatype*)malloc(sizeof(SLDatatype*) * 4);
	if (ps1->a == NULL)
	{
		perror("malloc err");
		return;
	}
	ps1->capacity = 4;
	ps1->size = 0;
}
2.顺序表销毁
void SLDesttoy(SL* ps1)
{
	free(ps1->a);
	ps1->a = NULL;
	ps1->capacity = 0;
	ps1->size = 0;
}
3.检查空间并扩容
void SLCheckCapacity(SL* ps1)
{
	if (ps1->size == ps1->capacity)
	{
		SLDatatype* tmp = (SLDatatype*)realloc(ps1->a, sizeof(SLDatatype) * ps1->capacity * 2);
		if (tmp == NULL)
		{
			perror("realloc err");
			return;
		}
		ps1->a = tmp;
		ps1->capacity *= 2;
	}
}
4.顺序表尾插、顺序表头插

尾插：

void SLPushBack(SL* ps1, SLDatatype x)
{
	SLCheckCapacity(ps1);
	ps1->a[ps1->size] = x;
	ps1->size++;
}

头插：

void SLPushFront(SL* ps1, SLDatatype x)
{
	SLCheckCapacity(ps1);
	int end = ps1->size - 1;
	while (end >= 0)
	{
		ps1->a[end + 1] = ps1->a[end];
		end--;
	}
	ps1->a[0] = x;
	ps1->size++;
}
5.顺序表尾删、顺序表头删

尾删：

size直接--就是尾插

void SLPopBack(SL* ps1)
{
	assert(ps1->size > 0);
	ps1->size--;
}

头删：

后往前覆盖数据

void SLPopFront(SL* ps1)
{
	assert(ps1->size > 0);
	int strat = 0;
	while (strat < ps1->size - 1)
	{
		ps1->a[strat] = ps1->a[strat + 1];
		strat++;
	}
	ps1->size--;
}
6.顺序表查找
int SLFind(SL* ps1, SLDatatype x)
{
	for (int i = 0; i < ps1->size; i++)
	{
		if (ps1->a[i] == ps1->a[x])
		{
			return i;
		}
	}
	return -1;
}
7.顺序表在pos位置插入x、删除pos位置的值

pos插入x

void SLInsert(SL* ps1, int pos, SLDatatype x)
{
	assert(0 <= pos && pos <= ps1->size);
	SLCheckCapacity(ps1);
	int end = ps1->size - 1;
	while (end >= pos)
	{
		ps1->a[end + 1] = ps1->a[end];
		end--;
	}
	ps1->a[pos] = x;
	ps1->size++;
}

删除pos

void SLErase(SL* ps1, int pos)
{
	assert(0 <= pos && pos < ps1->size);
	int strat = pos + 1;
	while (strat < ps1->size)
	{
		ps1->a[strat - 1] = ps1->a[strat];
		strat++;
	}
	ps1->size--;
}

三、完整代码

SeqLish.h:

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
typedef int SLDatatype;
typedef struct SeqLish
{	
	SLDatatype* a;
	int size;
	int capacity;
}SL;
void SLInit(SL* ps1);//初始化
void SLDesttoy(SL* ps1);//结束 释放顺序表
void SLPrint(SL* ps1);//打印
void SLCheckCapacity(SL* ps1);//扩容
void SLPushBack(SL* ps1,SLDatatype x);  //尾插
void SLPushFront(SL* ps1,SLDatatype x);//头插
void SLPopBack(SL* ps1); //尾删
void SLPopFront(SL* ps1);//头删
void SLInsert(SL* ps1, int pos,SLDatatype x);//指定增加
void SLErase(SL* ps1, int pos);//指定删除
//找到返回下标，没有找到返回-1
int SLFind(SL* ps1, SLDatatype x);//查
void SLModify(SL* ps1, int pos, SLDatatype x);//改

SeqLish.c: 

#include"SeqList.h"
void SLInit(SL* ps1)
{
	ps1->a = (SLDatatype*)malloc(sizeof(SLDatatype*) * 4);
	if (ps1->a == NULL)
	{
		perror("malloc err");
		return;
	}
	ps1->capacity = 4;
	ps1->size = 0;
}

void SLDesttoy(SL* ps1)
{
	free(ps1->a);
	ps1->a = NULL;
	ps1->capacity = 0;
	ps1->size = 0;
}

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

void SLCheckCapacity(SL* ps1)
{
	if (ps1->size == ps1->capacity)
	{
		SLDatatype* tmp = (SLDatatype*)realloc(ps1->a, sizeof(SLDatatype) * ps1->capacity * 2);
		if (tmp == NULL)
		{
			perror("realloc err");
			return;
		}
		ps1->a = tmp;
		ps1->capacity *= 2;
	}
}

void SLPushBack(SL* ps1, SLDatatype x)
{
	SLCheckCapacity(ps1);
	ps1->a[ps1->size] = x;
	ps1->size++;
}
void SLPushFront(SL* ps1, SLDatatype x)
{
	SLCheckCapacity(ps1);
	int end = ps1->size - 1;
	while (end >= 0)
	{
		ps1->a[end + 1] = ps1->a[end];
		end--;
	}
	ps1->a[0] = x;
	ps1->size++;
}

void SLPopBack(SL* ps1)
{
	assert(ps1->size > 0);
	ps1->size--;
}
void SLPopFront(SL* ps1)
{
	assert(ps1->size > 0);
	int strat = 0;
	while (strat < ps1->size - 1)
	{
		ps1->a[strat] = ps1->a[strat + 1];
		strat++;
	}
	ps1->size--;
}

void SLInsert(SL* ps1, int pos, SLDatatype x)
{
	assert(0 <= pos && pos <= ps1->size);
	SLCheckCapacity(ps1);
	int end = ps1->size - 1;
	while (end >= pos)
	{
		ps1->a[end + 1] = ps1->a[end];
		end--;
	}
	ps1->a[pos] = x;
	ps1->size++;
}
void SLErase(SL* ps1, int pos)
{
	assert(0 <= pos && pos < ps1->size);
	int strat = pos + 1;
	while (strat < ps1->size)
	{
		ps1->a[strat - 1] = ps1->a[strat];
		strat++;
	}
	ps1->size--;
}

int SLFind(SL* ps1, SLDatatype x)
{
	for (int i = 0; i < ps1->size; i++)
	{
		if (ps1->a[i] == ps1->a[x])
		{
			return i;
		}
	}
	return -1;
}
void SLModify(SL* ps1, int pos, SLDatatype x)
{
	assert(0 <= pos && pos < ps1->size);
	ps1->a[pos] = x;
}

四、总结

定义：顺序表是用一组连续的存储单元依次存储数据元素的线性结构。

特点：

1. 逻辑顺序与物理顺序一致：元素顺序存储，相邻元素物理位置相邻。

2. 可以快速访问任意元素：通过索引直接访问元素。

优点：

1. 实现简单。

2. 随机访问方便。

缺点：

1. 插入、删除操作可能需要移动大量元素，效率较低。

2. 需要预先确定固定的存储空间，可能造成空间浪费或不足。

基本操作：包括初始化、插入、删除、查找、遍历等。

标签：数据结构,int,void,SLDatatype,顺序,SL,ps1,size
From： https://blog.csdn.net/2301_78029441/article/details/140619340

相关文章

  • 数据结构——链式二叉树(C语言版)
    链式二叉树的结构⽤链表来表⽰⼀棵⼆叉树，即⽤链来指⽰元素的逻辑关系。通常的⽅法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别⽤来给出该结点左孩⼦和右孩⼦所在的链结点的存储地址。                                ......
  • CTF-PWN 堆的相关数据结构
    文章连接： 《堆的相关数据结构》参考：1.ctf.wiki:堆相关数据结构-CTFWiki2.星盟pwn佬:0011.哔哩哔哩-【个人向】CTFpwn入门-P11[高清版]_哔哩哔哩_bilibilimalloc_chunk概念：通过malloc申请的内存称为chunk，也可以将chunk称作堆的一个单位(自己随意理解)。free......
  • 关于链表、顺序表、栈和队列的一些总结
    关于链表、顺序表、栈和堆的一些总结1.顺序表2.链表2.1单向链表2.1带哨兵位双向循环链表3.栈4.队列1.顺序表2.链表2.1单向链表2.1带哨兵位双向循环链表3.栈4.队列......
  • 数据结构—红黑树
    红黑树的概念红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。红黑树的性质每个结点不是红色就......
  • Python 教程（二）：语法与数据结构
    目录前言专栏列表语法特点实例代码基本数据类型变量命名规则赋值动态类型作用域示例代码运算符`list`、`set`和`dict`数据结构区别1.list（列表）2.set（集合）3.dict（字典）总结前言Python是一种计算机编程语言。每种编程语言都有自己的语法规则。在本教程中，我们将学......
  • 数据结构-二叉树（顺序结构）
    引言顺序结构存储就是使⽤数组来存储，⼀般只适合表⽰完全⼆叉树，因为不是完全⼆叉树会有空间的浪费，完全⼆叉树更适合使⽤顺序结构存储。一、堆的概念将一个元素集合k里，所有数据按照完成二叉树的顺序存储方式存储。并且数组中的元素，满足以下关系i=0、1、2...，则称为......
  • 数据结构:顺序表
    顺序表的概述与实现顺序表（SequentialList）是计算机科学中一种常用的数据结构，其特点是用一段连续的存储单元依次存储数据元素。顺序表的底层实现通常采用数组，但与数组不同的是，顺序表封装了对数据的插入、删除、查找等操作，使其使用起来更加灵活和方便。本文将详细介绍顺序表的概......
  • 数据结构:算法复杂度
    目录前言数据结构和算法的基本概念数据结构和算法的重要性衡量算法的好坏时间复杂度空间复杂度例子分析例子1：冒泡排序例子2：对数时间复杂度总结前言在编程学习中，理解数据结构和算法是至关重要的。这不仅是计算机科学的基础知识，也是解决复杂问题和优化代码效率的关......
  • EEG数据结构
    基本数据集信息：EEG.setname-数据集的描述性名称/标题EEG.filename-磁盘上数据集文件的文件名EEG.filepath–数据集文件的文件路径（目录/文件夹EEG.trials-数据集中的历时（或试验）数。如果数据是连续的，则该数字为1。EEG.pnts-每次试验（历元）的时间点（或数据帧）数。如......
  • 数据结构篇——栈的操作实现（顺序栈、链栈）！
    一：前言对于栈的操作，虽不及其他数据结构一样多，但是栈的实际应用却是十分广泛。比如在我们进行代码编写的编译器中，对于函数调用、递归操作、表达式求值以及编译器的括号匹配等问题均是通过反复的入栈和出栈操作进行控制的。栈结构在计算机科学的历史上，地位是举重若轻的，值得我们......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99