【數據結構&演算法】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;
}

Tags: /label/dataStructure /label/lzm 書籍筆記博文教程集合數據結構數據結構與演算法演算法線性表

【數據結構&演算法】04-線性表

前言

線性表的定義

線性表的數據類型&操作

線性表操作

數據類型定義

複雜操作

線性表的順序存儲結構

順序存儲結構的定義

順序存儲方式

數據長度和線性表長度的區別

地址的計算方法

順序存儲結構的插入與刪除

線性表順序存儲結構的優缺點

線性表的鏈式存儲結構

鏈式存儲結構的定義

頭指針與頭結點的異同

鏈式存儲結構的數據結構

時間複雜度分析

鏈表源碼參考

順序存儲結構與鏈式存儲結構使用建議

靜態鏈表

靜態鏈表的定義

靜態鏈表的數據結構

程式碼實現

靜態鏈表的實現

VirMach 便宜 VPS

QNews

【數據結構&演算法】04-線性表

前言

線性表的定義

線性表的數據類型&操作

線性表操作

數據類型定義

複雜操作

線性表的順序存儲結構

順序存儲結構的定義

順序存儲方式

數據長度和線性表長度的區別

地址的計算方法

順序存儲結構的插入與刪除

線性表順序存儲結構的優缺點

線性表的鏈式存儲結構

鏈式存儲結構的定義

頭指針與頭結點的異同

鏈式存儲結構的數據結構

時間複雜度分析

鏈表源碼參考

順序存儲結構與鏈式存儲結構使用建議

靜態鏈表

靜態鏈表的定義

靜態鏈表的數據結構

程式碼實現

靜態鏈表的實現

分享此文：

Related Posts

面試官：談談類載入器吧，你有沒有看過類載入器的源碼

SonarQube系列一、Linux安裝與部署

如何成為中國首富？

jQuery效果

VirMach 便宜 VPS

QNews

熱門文章

熱門搜尋