【数据结构&算法】04-线性表

2021 年 11 月 4 日
筆記
/label/dataStructure, /label/lzm, 书籍笔记, 博文, 教程集合, 数据结构, 数据结构与算法, 算法, 线性表

前言

李柱明博客：//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         //www.cnblogs.com/lizhuming/
 *
 **********************************************************
 *  @LOG 修改日志:
 **********************************************************
*/

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

/* 说明：链表操作的索引是 1 起的。 */

/* 线性表的静态链表存储结构 */
#define MAX_SIZE 100
typedef 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;
}

【数据结构&算法】04-线性表

前言

线性表的定义

线性表的数据类型&操作

线性表操作

数据类型定义

复杂操作

线性表的顺序存储结构

顺序存储结构的定义

顺序存储方式

数据长度和线性表长度的区别

地址的计算方法

顺序存储结构的插入与删除

线性表顺序存储结构的优缺点

线性表的链式存储结构

链式存储结构的定义

头指针与头结点的异同

链式存储结构的数据结构

时间复杂度分析

链表源码参考

顺序存储结构与链式存储结构使用建议

静态链表

静态链表的定义

静态链表的数据结构

代码实现

静态链表的实现

VirMach 便宜 VPS

QNews

【数据结构&算法】04-线性表

前言

线性表的定义

线性表的数据类型&操作

线性表操作

数据类型定义

复杂操作

线性表的顺序存储结构

顺序存储结构的定义

顺序存储方式

数据长度和线性表长度的区别

地址的计算方法

顺序存储结构的插入与删除

线性表顺序存储结构的优缺点

线性表的链式存储结构

链式存储结构的定义

头指针与头结点的异同

链式存储结构的数据结构

时间复杂度分析

链表源码参考

顺序存储结构与链式存储结构使用建议

静态链表

静态链表的定义

静态链表的数据结构

代码实现

静态链表的实现

分享此文：

Related Posts

生产环境部署springcloud微服务启动慢的问题排查

如何设计实时数据平台（设计篇）

如何成为中国首富？

jQuery效果

VirMach 便宜 VPS

QNews

熱門搜尋