数据结构(次序表)
数据结构概述什么是数据结构
数据结构：数据结构就是计算机存储，构造，管理数据的方式方法
数据结构的范例
①根据数据的逻辑结构划分(数据间关系)
[*] 集合:数据结构的元素之间除了“同属一个构造”之外，别无其他关系
[*] 线性数据结构：数据之间“一对一”的关系，数据具有唯一的前驱和后继，典型代表是链表
[*] 非线性数据结构:数据之间不具有唯一的前驱和后继。例如：二维数组，二叉树…，典型代表是二叉树
https://i-blog.csdnimg.cn/direct/0a6a498707bf466fb769eb1721594970.png
②根据数据在内存中的存储方式划分
[*] 次序结构：各个元素存储在连续的内存空间，典型代表是数组
[*] 链式结构：各个元素存储在不连续的内存空间，典型代表是链表
[*] 索引结构：元素在存储时，不仅存储元素数据，还建立元素附加的索引表来标识元素的地点
[*] 哈希(散列)结构:元素在存储时，为元素提供关键字，在元素访问时，可根据关键字来访问数据
常见的数据结构
链表 次序表 树 图 映射 栈 队列
线性表
概念
对于一组拥有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 = s->data;
//将新数据置入表头
s->data = data;
s->last++;
return true;
}
//将顺序表表头的数据删除掉
bool removeNode(sequenceLits *s)
{
if(isEmpty(s))
rerurn false;
//将所有数据全部往前挪一位
for(int i = 0;i<s->last;i++)
s->data = s->data;
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 = list->data;
}
// 将新数据置入表头（也就是索引0的位置）
list->data = 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);
}
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== data)
{
pos = i;
break;// 找到之后，就结束循环
}
}
// 找不到要删除的数据
if(i > list->last)
{
return false;
}
// 将要删除的索引后的数据全部往前移动一位
for(i = pos; i < list->last;i++)
{
list->data = list->data;
}
// 改变索引
list->last--;
return true;
}
/**
* 释放内存
* @param list 待释放的顺序表
*/
void destroy(SequenceList *list)
{
if(list == NULL)
{
return;
}
free(list->data);
free(list);
list = NULL;
}
次序表优缺点总结
次序存储中，由于逻辑关系是用物理位置来表达的，因此从上述示例代码可以很清晰看到，增删数据都非常困难，必要成片地移动数据。次序表对数据节点的增删操纵是很不友好的。
总结其特点如下：
[*]长处:
[*]不必要多余的信息来记载数据间的关系，存储密度高
[*]所有数据次序存储在一片连续的内存中，支持立刻访问恣意一个随机数据，比如上述次序表中第i个节点是 s->data
[*]缺点:
[*]插入、删除时必要保持数据的物理位置反映其逻辑关系，一般必要成片移动数据
[*]当数据节点数量较多时，必要一整片较大的连续内存空间
[*]当数据节点数量变化剧烈时，内存的释放和分配不机动
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]