目录
前言
李柱明博客:https://www.cnblogs.com/lizhuming/p/15487297.html
线性表的定义
线性表:
- 线性表(list)- 零个或多个数据元素的有限序列。
- 序列:第一个元素无前驱,最后一个元素无后继,其他每个元素都有且只有一个前驱和后继。
- 有限:元素的个数是有限的。
- 元素类型:元素类型相同。
线性表的数据类型&操作
线性表操作
线性表的创建和初始化。
清空线性表。
获取线性表的数据元素。
按位置获取。
按自定义参考值获取。
插入数据。
删除数据。
线性表元素个数。
线性表空判。
线性表满判。
检查元素是否存在。
数据类型定义
- 数据空间。
- 自定义数据。如锁、长度记录等等。
- 常用操作。
/* 线性表数据结构 */typedef struct{ /* data_typde Data; 数据空间。 */ /* 自定义数据。 */ /* 数据操作。 */}
复杂操作
如合并集合 B 中的数据到集合 A 中:
/* 将所有在线性表 list_b 中但是不在 list_a 中的数据元素插入到 list_a 中 */void list_union(list *list_a, list *list_b){ int i = 0; int list_a_len = 0; int list_b_len = 0; elem_type elem = 0; list_a_len = list_lenght(list_a); list_b_len = list_lenght(list_b); for(i = 1; i <= list_b_len; i++) { list_get_elem(list_b, i, &elem); /* 取 list_b 中第 i 个数据元素赋给 elem */ if(!list_locate_elem(list_a, elem) /* list_a 中不存在和 elem 相同数据元素 */ { list_insert(list_a, ++list_a_len, elem); /* 插入 */ } }}
线性表的顺序存储结构
线性表的两种物理结构:
- 顺序存储结构。
- 链式存储结构。
顺序存储结构的定义
定义:
- 线性表的顺序存储结构,指用一段地址连续的存储单元依次存储线性表的数据元素。
顺序存储方式
若每个数据类型相同,可以用 C 语言的一维数组来实现顺序存储结构:
#define MAX_SIZE /* 数据空间 */typedef int elem_type; /* 元素类型 */typedef struct{ int length; /* 线性表长度 */ elem_type data[MAX_SIZE]; /* 实际空间 */}list_t;
描述顺序存储结构需要三个属性:
- 存储空间的起始位置:数组 data,它的存储位置就是存储空间的存储位置。
- 线性表的最大存储容量:数组长度 MAX_SIZE。
- 线性表的当前长度:length。
数据长度和线性表长度的区别
- 数据长度:是存放线性表的存储空间的长度,存储分配后这个量是一般不变的。
- 线性表长度:线性表中的数据元素的个数。随着元素的插入、删除操作的变化而变化。
- 注意:线性表的长度总是小于等于数组的长度。
地址的计算方法
地址:存储器中的每个存储单元都有自己的编号,这个编号称为地址。(内存地址)
计数:线性表从 1 开始,而 c 语言中的数组从 0 开始。
locate:获得存储位置的函数(假设每个数据元素占 c 个存储单元),参考公式:
- locate(Ai + n) = locate(Ai) + n*c;
- locate(Ai) = locate(A1) + (i-1)*c;
通过上述公式可以随时算出线性表中任意位置的地址,且都是相同时间。
由此可知时间复杂度为 O(1)。
每个位置存、取数据,都是相等的时间,也就是一个常数。
通常把具有这一特点的存储结构称为 随机存取结构。
顺序存储结构的插入与删除
注意:
- 线性表的第 i 个数是从 1 开始计数的,而数组小标是从 0 开始的。
- 分清应该是 i 还是 i-1。
- 注意指针丢失问题。
增删时间复杂度分析:
- 最好的情况:插入或删除尾部:O(1)
- 最坏情况:插入或删除头部:O(n)
- 平均情况:(n-1)/2
线性表顺序存储结构的优缺点
优点:
- 无须为表示表中元素之间的逻辑关系而增加额外的存储空间。
- 可以快速的存取表中的任一位置的元素。
缺点:
- 插入和删除操作需要搬移大量数据。
- 当线性表长度变化较大时,难以确定存储空间的容量。
- 容易造成存储空间的碎片。
线性表的链式存储结构
链式存储结构的定义
特点:
用一组任意的存储单元存储线性表的数据元素,这组存储单元可以连续,也可以不连续。(顺序存储要求地址连续)
空间、逻辑负担:顺序结构中,每个数据元素只需要存数据元素的信息,而链式结构中,还需要存储它的后继元素的存储地址。
即是顺序存储结构的前驱后继是地址相邻。
而链式存储结构的前驱后继是靠指针指向。
头指针与头结点的异同
头指针:
- 头指针是指指向第一个结点的指针。若链表有头结点(哨兵),则是指向头结点的指针。
- 头指针具有表示作用,所以通常当链表的句柄。头指针也冠以链表的名字。
- 无论链表是否为空,头指针都不为空,因为它指向链表的实体。
- 头指针是链表的必要元素。
头结点:
- 头结点是为了操作的统一和方便而设立的,就是不用考虑无结点时的链表操作。
- 头结点放在第一个元素的结点之前,其数据域一般无意义。可以添加一些自定义的数据,用于管理链表。可以扩展成这个链表的控制块。
- 头结点不是链表的必要元素。
链式存储结构的数据结构
双向非通用循环链表相关节点:
- 根节点可以扩展成链表的控制块。
- 在节点中挂载信息。信息结构可自定义。
/* mini 节点结构体 */struct LIST_MINI_ITEM_LSS_T{ /* 指向,(根据单、双链表删减以下内容) */ struct node *pxPrevious; // 上一个节点 struct node *pxNext; // 下一个节点 /* 节点属性,(根据个人需求增减以下内容) */ uint32_t xItemValue; // 记号值,在双向链表中为最大值};typedef struct LIST_MINI_ITEM_LSS_T ListMiniItem_t;/* 链表结构体,即根节点 */struct LIST_LSS_T{ /* 节点属性,(根据个人需求增减以下内容) \*/ uint32_t uxNumberOfItems; // 节点数,统计粘附在本链表上的节点数 struct LIST_ITEM_LSS_T * pxIndex; // 索引,链表索引,指向链表中的某个节点 struct LIST_MINI_ITEM_LSS_T xListEnd; // 链表根节点};typedef struct LIST_LSS_T List_t;/* * The linked list node */struct LIST_ITEM_LSS_T{ struct LIST_ITEM_LSS_T * pxNext; // 下一个 struct LIST_ITEM_LSS_T * pxPrevious; // 上一个 /* 节点属性,(根据个人需求增减以下内容) */ uint32_t xItemValue; // 记号值,一般用于排序 void * pvOwner; // 挂钩,即携带的信息 void * pvContainer; // 归属,即属于哪一个链表};typedef struct LIST_ITEM_LSS_T listItem_t;
双向通用循环链表相关节点:
- 把节点放置待结构体中即可。
- 链表的每个元素类型一致。
/* * Structure of a node in a doubly linked list. */typedef struct LSS_LIST{ struct LSS_LIST *pstPrev; /**< Current node's pointer to the previous node*/ struct LSS_LIST *pstNext; /**< Current node's pointer to the next node*/} LSS_LIST;typedef struct LSS_LIST listItem_t;
时间复杂度分析
- 单链表的插入和删除:首先是遍历查找第 i 个元素,其次是插入和删除操作。
- 所以时间复杂度是 O(n)。
- 增删元素时,顺序存储结构需要挪动数据,O(n)。而链式存储结构修改指向的指针 O(1)。
- 综上,对于对元素增删频繁的,链式存储结构比较好。
链表源码参考
顺序存储结构与链式存储结构使用建议
- 若线性表多查找,少插删,宜采用顺序存储结构;若多查删,宜采用单链表结构。
- 若线性表的元素个数变化大或不确定时,宜采用单链表;若确定或事先明确个数,用顺序存储效率更高。
静态链表
问题:C 语言有指针,python 等面向对象的语言有引用。但是有些语言没有指针也没有引用,如何实现链表结构?
解决方案:结合数组&链表。用数组下标代替指针。即是游标实现法。
静态链表的定义
定义:用数组描述的链表叫做静态链表,或曰“游标实现法”。
数组的元素都是由两个数据域组成的,data(数据)和 cur(游标)。
数组的每个下标都对应一个 data 和一个 cur。
数据域 data:用来存放数据元素,也就是我们要处理的数据。
游标 cur:相当于单链表中的 next 指针,存放该元素的后继在数组中的下标。
备用链表:通常把未被使用的数组元素称为备用链表。(即数组的后面还没填充数据的空闲空间)
两个特殊位置:
数组第一个元素空间用于存放备用链表的第一个节点。
space[0].cur 表示备用链表的第一个节点的下标。
space[0].cur == (max_size - 1) 时表示备用链表已无空间。
数组最后一个元素空间用于存放头结点。
space[max_size-1].cur 表示第一个有效数据元素的下标。
space[max_size-1].cur == 0 时表示数据链表为空。
静态链表的数据结构
/* 线性表的静态链表存储结构 */typedef struct { elem_type data; int cur; /* 游标(Cursor) ,为0时表示无指向 */} component_t;component_t static_link_list[MAX_SIZE];
代码实现
静态链表的实现
/** @file static_list.c * @brief 简要说明 * @details 详细说明 * @author lzm * @date 2021-09-05 22:12:22 * @version v1.0 * @copyright Copyright By lizhuming, All Rights Reserved * @blog https://www.cnblogs.com/lizhuming/ * ********************************************************** * @LOG 修改日志: ***********************************************************/#include <stdio.h>#include <stdlib.h>#include <string.h>/* 说明:链表操作的索引是 1 起的。 *//* 线性表的静态链表存储结构 */#define MAX_SIZE 100typedef int elem_type;typedef struct { elem_type data; int cur; /* 游标(Cursor) ,为0时表示无指向 */}static_list_t;static_list_t static_list[MAX_SIZE] = {0};/** * @name static_list_init * @brief 将一维数组space中各分量链成一个备用链表,space[0].cur为头指针,"0"表示空指针 * @param * @retval * @author lzm */int static_list_init(static_list_t *space) { int i = 0; if(space == NULL) { return -1; } for (i=0; i<MAX_SIZE-1; i++) space[i].cur = i+1; space[MAX_SIZE-1].cur = 0; /* 目前静态链表为空,最后一个元素的cur为0 */ return 0;}/** * @name static_list_malloc * @brief 从数组备用链表中模拟 malloc 一个数据空间出来 * @param * @retval 下标 * @author lzm */int static_list_malloc(static_list_t *space){ int index = 0; if(space == NULL) return -1; index = space[0].cur; if(space[0].cur) space[0].cur = space[index].cur; return index;}/** * @name static_list_free * @brief 把一个数据空间放会备用链表中 * @param * @retval * @author lzm */int static_list_free(static_list_t *space, int index){ if(space == NULL || index <= 0 || index >= MAX_SIZE) return -1; space[index].cur = space[0].cur; space[0].cur = index; return 0;}/** * @name static_list_length * @brief * @param * @retval * @author lzm */int static_list_length(static_list_t *space){ int cnt = 0; int index = 0; if(space == NULL) return -1; index = space[MAX_SIZE-1].cur; while(index) { cnt++; index = space[index].cur; } return cnt;}/** * @name static_list_inster * @brief 在space数据链表中第cur_inster个元素前插入新的元素。(编程技巧:找出前一个便好操作了) * @param * @retval * @author lzm */int static_list_inster(static_list_t *space, int cur_inster, elem_type elem){ int i = 0; int index = 0; int index_m = 0; if(space == NULL || cur_inster < 1 || cur_inster > (static_list_length(space) + 1)) return -1; index_m = static_list_malloc(space); if(index_m <= 0) return -1; space[index_m].data = elem; index = MAX_SIZE-1; for(i = 1; i < cur_inster; i++) index = space[index].cur; space[index_m].cur = space[index].cur; space[index].cur = index_m; return 0;}/** * @name static_list_delete * @brief 在space数据链表中删除第cur_delete个元素。 * @param * @retval * @author lzm */int static_list_delete(static_list_t *space, int cur_delete){ int i = 0; int index = 0; int index_d = 0; if(space == NULL) return -1; if(space == NULL || cur_delete < 1 || cur_delete > static_list_length(space)) return -1; index = MAX_SIZE - 1; for(i = 1; i < cur_delete; i++) // 获取实际需要删除的前一个 index = space[index].cur; index_d = space[index].cur; space[index].cur = space[index_d].cur; static_list_free(space, index_d); return 0;}