当前位置：首页 > news >正文

数据结构(顺序表)

news 来源：原创 2025/5/12 4:30:59

文章目录

- 数据结构概述
- - 什么是数据结构
  - 数据结构的类型
  - 常见的数据结构
- 线性表
- - 概念
  - 举例
- 顺序表
- - 基本概念
  - 基本操作
- 完整代码
- - 顺序表优缺点总结

数据结构概述

什么是数据结构

数据结构：数据结构就是计算机存储，组织，管理数据的方式方法

数据结构的类型

①根据数据的逻辑结构划分(数据间关系)

集合:数据结构的元素之间除了“同属一个组织”之外，别无其他关系
线性数据结构：数据之间“一对一”的关系，数据具有唯一的前驱和后继，典型代表是链表
非线性数据结构:数据之间不具有唯一的前驱和后继。例如：二维数组，二叉树…，典型代表是二叉树

②根据数据在内存中的存储方式划分
顺序结构：各个元素存储在连续的内存空间，典型代表是数组
链式结构：各个元素存储在不连续的内存空间，典型代表是链表
索引结构：元素在存储时，不仅存储元素数据，还建立元素附加的索引表来标识元素的地址
哈希(散列)结构:元素在存储时，为元素提供关键字，在元素访问时，可根据关键字来访问数据

常见的数据结构

链表顺序表树图映射栈队列

线性表

概念

对于一组拥有n个数据元素的线性表，其严格数学定义是：其中任何一个数据元素 ai，有且仅有一个直接前驱 ai-1，有且仅有一个直接后继ai+1 。首元素a0无直接前驱，尾元素an-1 无直接后继。满足这种数学关系的一组数据，当中的数据是一个挨着一个的，常被称为一对一关系。反之，如果数据之间的关系不是一对一的，就是非线性的

举例

生活中的线性表例子非常多，比如一个班级中的以学号编排的学生，一座图书馆中的以序号编排的图书、一条正常排队等候的队列、一摞从上到下堆叠的餐盘，这些都是线性表。他们的特点都是：除了首尾两个元素，其余任何一个元素前后都对应相邻的另一个元素。

注意：

线性表是一种数据内部的逻辑关系，与存储形式无关

线性表既可以采用连续的顺序存储（顺序表），也可以采用离散的链式存储（链表）

顺序表

基本概念

顺序表:顺序存储的线性表
链式表：链式存储的线性表，简称链表

顺序存储就是将数据存储到一片连续的内存中，在C语言环境下，可以是具名的栈数组，或者是匿名的堆数组

存储方式不仅仅只是提供数据的存储空间，而是必须要能体现数据之间的逻辑关系。当采用顺序存储的方式来存放数据时，唯一能用来表达数据间本身的逻辑关系的就是存储位置。比如队列中的两个人，小明和小花，如果小明在逻辑上排在相邻的小花的前面，那么在存储位置上也必须把小明存放在相邻的小花的前面

基本操作

顺序表设计

一般而言，为了方便操作顺序表，需要一个专门管理顺序表的“管理结构体”，管理结构体中一般会包含：

1. 顺序表总容量
1. 顺序表当前最末元素下标位置
1. 顺序表指针

下面是管理结构体示例代码：

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>typedef struct
{int capacity;//顺序表容量int last;	//最末元素下标int* data;	//顺序表，以整型数据为例
}sequenceList;

初始化

所谓初始化就是建立一个不包含任何元素的顺序表，设置好管理结构体中的表的总容量、末元素下标，申请好顺序表内存空间等系列准备工作

下面是初始化顺序表的示例代码：

sequenceList *init_list(int cap)
{sequenceLits *list = malloc(sizeof(sequenceList));if(list != NULL){list -> data = malloc(sizeof(int)*cap);if(list -> data == NULL){free(list);return NULL;}list -> capacity = cap;list -> last = -1;}return list;
}

测试

int main()
{sequenceList *list = init_list(10);if(list == NULL){perror("初始化顺序表失败!");return -1;}else{printf("初始化顺序表成功!\n");}
}

增删节点

在顺序表中增加一个数据，可以有多种方式，比如在原数组的末尾增加，或者在原数组的头部增加，或者在数组中间任意一个位置增加。根据实际需要来定

下面以在顺序表头部增删数据为例，示例代码如下：

//判定顺序表是否为空
bool isEmpty(sequenceList *s)
{return s ->last == -1;
}//判断顺序表是否已满
bool isFull(sequenceList *s)
{return s->last == s->capacity-1;
}//在顺序表表头插入一个新数据
bool insert(sequenceLits *s,int data)
{if(isFull(s))return false;//将原有数据全部往后挪一位for(int i = s->last;i>=0;i--)s->data[i+1] = s->data[i];//将新数据置入表头s->data[0] = data;s->last++;return true;
}//将顺序表表头的数据删除掉
bool removeNode(sequenceLits *s)
{if(isEmpty(s))rerurn false;//将所有数据全部往前挪一位for(int i = 0;i<s->last;i++)s->data[i] = s->data[i+1];s->last--;return true;
}

销毁顺序表

一个顺序表最后不再需要，应当要释放其所占用的内存空间，这被称为顺序表的销毁

下面是销毁操作的示例代码:

void destroy(sequenceList *s)
{if(s == NULL)rerurn;free(s->data);free(s);
}

完整代码

seqlist.h

#ifndef _SEQLIST_H//防止头文件重复
#define _SEQLIST_H#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>//定义一个顺序表的结构体
typedef struct 
{int capacity; //顺序表容量int last;     //最末元素下标int *data;    //顺序表数据， {0,0,0}
} SequenceList;/*
* 初始化顺序表
* @param cap 初始化容量
*/SequenceList *init_list(int cap);/*
*判断顺序表是否为空(删除的时候判断用)
*@param list 待判断的顺序表
*/
bool is_empty(SequenceList *list);/*
*判断顺序表是否已满(插入的时候判断用)
*@param list 待判断的顺序表
*/
bool is_full(SequenceList *list);/*
*向顺序表插入数据(头插法)
* @param list 待插入的顺序表* @param data 待插入的数据
*/
bool insert(SequenceList *list,int data);/*** 遍历顺序表* @param list 待插入的顺序表*/
void show(SequenceList *list);/*** 删除顺序表数据* @param list 待删除的顺序表* @param data 待删除数据*/
bool remove_node(SequenceList *list,int data);/*** 释放内存* @param list 待释放的顺序表*/
void destroy(SequenceList *list);#endif

seqlist.c

#include "seqlist.h"/*** 初始化顺序表* @param cap 初始化容量*/
SequenceList *init_list(int cap)
{// 创建顺序表（堆内存）SequenceList *list = malloc(sizeof(SequenceList));if(list!=NULL){// 给顺序表中的元素分配存储空间（顺序表就是数组，数据是存储在元素中的）list->data = malloc(sizeof(int) * cap);// 校验元素空间是否分配成功if(list->data == NULL){free(list);return NULL;}// 初始化list->capacity = cap;list->last = -1;}return list;
}/*** 判断顺序表是否为空（删除的时候判断用）*/
bool is_empty(SequenceList *list)
{return list->last == -1;
}/*** 判断顺序表是否已满（插入的时候判断用）*/
bool is_full(SequenceList *list)
{return list->last == list->capacity -1;
}/** * 向顺序表插入数据（头插法）* @param list 待插入的顺序表* @param data 待插入的数据*/
bool insert(SequenceList *list, int data)
{// 插入数据前，先判断是否已满if(is_full(list))return false;// 将原有的数据全部后移一位for(int i = list->last; i >= 0; i--){list->data[i+1] = list->data[i];}// 将新数据置入表头（也就是索引0的位置）list->data[0] = data;list->last++;
}/*** 遍历顺序表* @param list 待插入的顺序表*/
void show(SequenceList *list)
{// 判断顺表表是否为空if(is_empty(list))return;// 使用for循环进行遍历for(int i = 0; i <= list->last; i++){printf("%d\t",list->data[i]);}printf("\n");
}/*** 删除顺序表数据* @param list 待删除的顺序表* @param data 待删除数据*/bool remove_node(SequenceList *list, int data)
{// 判断是否为空if(is_empty(list))return false;// 找到要删除数据（节点）的位置（下标）int i, pos = -1;// 通过一个循环，查找数据对应的位置for(i = 0; i <= list->last; i++){if(list->data[i]== data){pos = i;break;// 找到之后，就结束循环 }}// 找不到要删除的数据if(i > list->last){return false;}// 将要删除的索引后的数据全部往前移动一位for(i = pos; i < list->last;i++){list->data[i] = list->data[i+1];}// 改变索引list->last--;return true;
}/*** 释放内存* @param list 待释放的顺序表*/
void destroy(SequenceList *list)
{if(list == NULL){return;}free(list->data);free(list);list = NULL;
}

顺序表优缺点总结

顺序存储中，由于逻辑关系是用物理位置来表达的，因此从上述示例代码可以很清楚看到，增删数据都非常困难，需要成片地移动数据。顺序表对数据节点的增删操作是很不友好的。

总结其特点如下：

优点:

不需要多余的信息来记录数据间的关系，存储密度高
所有数据顺序存储在一片连续的内存中，支持立即访问任意一个随机数据，比如上述顺序表中第i个节点是 s->data[i]

缺点:

插入、删除时需要保持数据的物理位置反映其逻辑关系，一般需要成片移动数据
当数据节点数量较多时，需要一整片较大的连续内存空间
当数据节点数量变化剧烈时，内存的释放和分配不灵活