文章目錄

（1）. 線性表的本質
（2）. 線性表的順序存儲結構
（3）. 線性表的鍊式存儲結構
（4）. 小結

（1）. 線性表的本質

線性表可用于描述“隊列類型”關系的問題

線性表的定義
1. 線性表（List）是零個或多個資料元素的集合
2. 線性表中的資料元素之間是有順序的
3. 線性表中的資料元素個數是有限的
4. 線性表中的資料元素的類型必須相同
線性表的性質
1. a0為線性表的第一個元素，隻有一個後繼
2. an為線性表的最後一個元素，隻有一個前驅
3. 除a0和an外的其他元素ai，既有前驅，又有後繼
4. 線性表能夠逐項通路和順序存取

（2）. 線性表的順序存儲結構

順序存儲定義

線性表的順序存儲結構，指的是用一段位址連續的存儲單元依次存儲線性表的資料元素。

部分功能實作

存儲實作

typedef struct _tag_SeqList
{
    int capacity;       // 線性表存儲容量
    int length;         // 線性表目前長度
    TSeqListNode* node; // 存儲空間起始位址
} TSeqList;

建立線性表操作

資料結構筆記——2. 線性表（1）. 線性表的本質（2）. 線性表的順序存儲結構（3）. 線性表的鍊式存儲結構（4）. 小結

SeqList* SeqList_Create(int capacity) 
{
    TSeqList* ret = NULL;
    
    // 1. 建立存儲空間
    if (capacity >= 0)
    {
        ret = (TSeqList*)malloc(sizeof(TSeqList) + sizeof(TSeqListNode) * capacity);
    }
    
    // 2. 初始化線性表
    if (ret != NULL)
    {
        ret->capacity = capacity;
        ret->length = 0;
        // 3. 指針操作
        ret->node = (TSeqListNode*)(ret + 1);
    }
    
    return ret;
}

插入元素操作

資料結構筆記——2. 線性表（1）. 線性表的本質（2）. 線性表的順序存儲結構（3）. 線性表的鍊式存儲結構（4）. 小結

int SeqList_Insert(SeqList* list, SeqListNode* node, int pos)
{
    // 1. 判斷線性表是否合法
    TSeqList* sList = (TSeqList*)list;
    int ret = (sList != NULL);
    int i = 0;
    
    // 2. 判斷插入位置是否合法
    ret = ret && (sList->length + 1 <= sList->capacity);
    ret = ret && (0 <= pos);
    
    if (ret)
    {
        // 3. 若插入位置大于目前長度，則将元素放在最後
        if (pos >= sList->length)
        {
            pos = sList->length;
        }
        
        // 4. 從最後一個元素開始到第pos個元素，分别将他們都向後移動一個位置
        for (i = sList->length; i > pos; i--)
        {
            sList->node[i] = sList->node[i-1];
        }
        
        // 5. 将新元素插入
        sList->node[i] = (TSeqListNode)node;
        
        // 6. 長度加1
        sList->length++;
    }
    
    return ret;
}

删除元素操作

資料結構筆記——2. 線性表（1）. 線性表的本質（2）. 線性表的順序存儲結構（3）. 線性表的鍊式存儲結構（4）. 小結

SeqListNode* SeqList_Delete(SeqList* list, int pos)
{
    // 1. 進行位置合法性檢測與删除元素擷取
    TSeqList* sList = (TSeqList*)list;
    SeqListNode* ret = SeqList_Get(list, pos);
    int i = 0;
    
    // 2. 判斷線性表是否合法
    if (ret != NULL)
    {
         // 3. 把删除位置pos後的元素分别向前移動一個位置
        for (i = pos + 1; i < sList->length; i++)
        {
            sList->node[i - 1] = sList->node[i];
        }
        
        // 4. 長度減1
        sList->length--;
    }
    
    return ret;
}

優缺點：
1. 優點：
  - 無需為線性表中的邏輯關系增加額外的空間
  - 可以快速的擷取表中合法位置的元素
2. 缺點：
  - 插入和删除操作需要移動大量元素
  - 當線性表長度變化較大時難以确定存儲空間的容量

工程執行個體

頭檔案

#ifndef _SEQLIST_H_
#define _SEQLIST_H_

typedef void SeqList;
typedef void SeqListNode;

/*
    該方法用于建立并且傳回一個空的線性表
*/
SeqList* SeqList_Create(int capacity);

/*
    該方法用于銷毀一個線性表list
*/
void SeqList_Destroy(SeqList* list);

/*
    該方法用于将一個線性表list中的所有元素清空
    使得線性表回到建立時的初始狀态
*/
void SeqList_Clear(SeqList* list);

/*
    該方法用于傳回一個線性表list中的所有元素個數
*/
int SeqList_Length(SeqList* list);

/*
    該方法用于傳回一個線性表list中最大容量
*/
int SeqList_Capacity(SeqList* list);

/*
    該方法用于向一個線性表list的pos位置處插入新元素node
    傳回值為1表示插入成功，0表示插入失敗
*/
int SeqList_Insert(SeqList* list, SeqListNode* node, int pos);

/*
    該方法用于擷取一個線性表list的pos位置處的元素
    傳回值為pos位置處的元素，NULL表示擷取失敗
*/
SeqListNode* SeqList_Get(SeqList* list, int pos);

/*
    該方法用于删除一個線性表list的pos位置處的元素
    傳回值為被删除的元素，NULL表示删除失敗
*/
SeqListNode* SeqList_Delete(SeqList* list, int pos);

#endif

實作檔案

#include <stdio.h>
#include <malloc.h>
#include "SeqList.h"

typedef unsigned int TSeqListNode;

typedef struct _tag_SeqList
{
    int capacity;
    int length;
    TSeqListNode* node;
} TSeqList;

SeqList* SeqList_Create(int capacity) 
{
    TSeqList* ret = NULL;
    
    // 1. 建立存儲空間
    if (capacity >= 0)
    {
        ret = (TSeqList*)malloc(sizeof(TSeqList) + sizeof(TSeqListNode) * capacity);
    }
    
    // 2. 初始化線性表
    if (ret != NULL)
    {
        ret->capacity = capacity;
        ret->length = 0;
        // 3. 指針操作
        ret->node = (TSeqListNode*)(ret + 1);
    }
    
    return ret;
}

void SeqList_Destroy(SeqList* list) 
{
    free(list);
	list = NULL;
}

void SeqList_Clear(SeqList* list)
{
    TSeqList* sList = (TSeqList*)list;
    
    if( sList != NULL )
    {
        sList->length = 0;
    }
}

int SeqList_Length(SeqList* list)
{
    TSeqList* sList = (TSeqList*)list;
    int ret = -1;
    
    if( sList != NULL )
    {
        ret = sList->length;
    }
    
    return ret;
}

int SeqList_Capacity(SeqList* list)
{
    TSeqList* sList = (TSeqList*)list;
    int ret = -1;
    
    if( sList != NULL )
    {
        ret = sList->capacity;
    }
    
    return ret;
}

int SeqList_Insert(SeqList* list, SeqListNode* node, int pos)
{
    // 1. 判斷線性表是否合法
    TSeqList* sList = (TSeqList*)list;
    int ret = (sList != NULL);
    int i = 0;
    
    // 2. 判斷插入位置是否合法
    ret = ret && (sList->length + 1 <= sList->capacity);
    ret = ret && (0 <= pos);
    
    if (ret)
    {
        // 3. 若插入位置大于目前長度，則将元素放在最後
        if (pos >= sList->length)
        {
            pos = sList->length;
        }
        
        // 4. 從最後一個元素開始到第pos個元素，分别将他們都向後移動一個位置
        for (i = sList->length; i > pos; i--)
        {
            sList->node[i] = sList->node[i-1];
        }
        
        // 5. 将新元素插入
        sList->node[i] = (TSeqListNode)node;
        
        // 6. 長度加1
        sList->length++;
    }
    
    return ret;
}

SeqListNode* SeqList_Get(SeqList* list, int pos)
{
    TSeqList* sList = (TSeqList*)list;
    SeqListNode* ret = NULL;
    
    if ((sList != NULL) && (0 <= pos) && (pos < sList->length))
    {
		ret = (SeqListNode*)(sList->node[pos]);
    }
    
    return ret;
}

SeqListNode* SeqList_Delete(SeqList* list, int pos)
{
    // 1. 進行位置合法性檢測與删除元素擷取
    TSeqList* sList = (TSeqList*)list;
    SeqListNode* ret = SeqList_Get(list, pos);
    int i = 0;
    
    // 2. 判斷線性表是否合法
    if (ret != NULL)
    {
         // 3. 把删除位置pos後的元素分别向前移動一個位置
        for (i = pos + 1; i < sList->length; i++)
        {
            sList->node[i - 1] = sList->node[i];
        }
        
        // 4. 長度減1
        sList->length--;
    }
    
    return ret;
}

測試檔案

#include <stdio.h>
#include <stdlib.h>
#include "SeqList.h"

int main(int argc, char *argv[]) 
{
    SeqList* list = SeqList_Create(3);
    
    int i = 0;
    int j = 1;
    int k = 2;
    int x = 3;
    int index = 0;
    
    SeqList_Insert(list, &i, 0);
    SeqList_Insert(list, &j, 0);
    SeqList_Insert(list, &k, 0);
    SeqList_Insert(list, &x, 0);
    for(index=0; index<SeqList_Length(list); index++)
    {
        int* p = (int*)SeqList_Get(list, index);
        
        printf("%d\n", *p);
    }
    
    printf("\n");
    
    while( SeqList_Length(list) > 0 )
    {
        int* p = (int*)SeqList_Delete(list, 0);
        
        printf("%d\n", *p);
    }
    
    SeqList_Destroy(list);
    
    return 0;
}

（3）. 線性表的鍊式存儲結構

鍊式存儲定義

為了表示每一個資料元素與其直接後繼元素之間的邏輯關系，每個元素除了存儲本身的資訊外，還需要存儲訓示其直接後繼的資訊。

資料結構筆記——2. 線性表（1）. 線性表的本質（2）. 線性表的順序存儲結構（3）. 線性表的鍊式存儲結構（4）. 小結

部分功能實作

插入元素操作

資料結構筆記——2. 線性表（1）. 線性表的本質（2）. 線性表的順序存儲結構（3）. 線性表的鍊式存儲結構（4）. 小結

int LinkList_Insert(LinkList* list, LinkListNode* node, int pos)
    { 
        // 1. 線性表與插入位置合法性檢測
        TLinkList* sList = (TLinkList*)list;
        int ret = (sList != NULL) && (pos >= 0) && (node != NULL);
        int i = 0;
        
        if( ret )
        {
            LinkListNode* current = (LinkListNode*)sList;
            
            // 2. 由表頭開始通過next指針移動pos次後，目前元素的next指針即指向要插入的位置
            for(i=0; (i<pos) && (current->next != NULL); i++)
            {
                current = current->next;
            }
            
            // 3. 将新元素插入
            node->next = current->next;
            current->next = node;
            
            // 4. 線性表長度加1
            sList->length++;
        }
        
        return ret;
    }

删除元素操作

資料結構筆記——2. 線性表（1）. 線性表的本質（2）. 線性表的順序存儲結構（3）. 線性表的鍊式存儲結構（4）. 小結

LinkListNode* LinkList_Delete(LinkList* list, int pos)
    {
        TLinkList* sList = (TLinkList*)list;
        LinkListNode* ret = NULL;
        int i = 0;
        
    	// 1. 線性表與删除位置合法性檢測
        if( (sList != NULL) && (0 <= pos) && (pos < sList->length) )
        {
            LinkListNode* current = (LinkListNode*)sList;
    		
            // 2. 由表頭開始通過next指針移動pos次後，目前元素的next指針即指向要删除元素的位置
            for(i=0; i<pos; i++)
            {
                current = current->next;
            }
            
    		// 3. 擷取将删除的元素
            ret = current->next;
    		
    		// 4. 将元素舍棄
            current->next = ret->next;
            
    		// 5. 線性表長度減1
            sList->length--;
        }
        
        return ret;
    }

優缺點：
1. 優點：
  - 無需一次性定制連結清單的容量
  - 插入和删除操作無需移動資料元素
2. 缺點：
  - 資料元素必須儲存後繼元素的位置資訊
  - 擷取指定資料的元素操作需要順序通路之前的元素

工程執行個體

頭檔案

#ifndef _LINKLIST_H_
#define _LINKLIST_H_

typedef void LinkList;
typedef struct _tag_LinkListNode LinkListNode;
struct _tag_LinkListNode
{
    LinkListNode* next;
};

/*
	該方法用于建立并且傳回一個空的線性表
*/
LinkList* LinkList_Create();

/*
	該方法用于銷毀一個線性表list
*/
void LinkList_Destroy(LinkList* list);

/*
	該方法用于将一個線性表list中的所有元素清空
	使得線性表回到建立時的初始狀态
*/
void LinkList_Clear(LinkList* list);

/*
	該方法用于傳回一個線性表list中的所有元素個數
*/
int LinkList_Length(LinkList* list);

/*
	該方法用于向一個線性表list的pos位置處插入新元素node
	傳回值為1表示插入成功，0表示插入失敗
*/
int LinkList_Insert(LinkList* list, LinkListNode* node, int pos);

/*
	該方法用于擷取一個線性表list的pos位置處的元素
	傳回值為pos位置處的元素，NULL表示擷取失敗
*/
LinkListNode* LinkList_Get(LinkList* list, int pos);

/*
	該方法用于删除一個線性表list的pos位置處的元素
	傳回值為被删除的元素，NULL表示删除失敗
*/
LinkListNode* LinkList_Delete(LinkList* list, int pos);

#endif

實作檔案

#include <stdio.h>
#include <malloc.h>
#include "LinkList.h"

typedef struct _tag_LinkList
{
    LinkListNode header;
    int length;
} TLinkList;

LinkList* LinkList_Create() 
{
    TLinkList* ret = (TLinkList*)malloc(sizeof(TLinkList));
    
    if( ret != NULL )
    {
        ret->length = 0;
        ret->header.next = NULL;
    }
    
    return ret;
}

void LinkList_Destroy(LinkList* list) 
{
    free(list);
	
	list = NULL;
}

void LinkList_Clear(LinkList* list) 
{
    TLinkList* sList = (TLinkList*)list;
    
    if( sList != NULL )
    {
        sList->length = 0;
        sList->header.next = NULL;
    }
}

int LinkList_Length(LinkList* list) 
{
    TLinkList* sList = (TLinkList*)list;
    int ret = -1;
    
    if( sList != NULL )
    {
        ret = sList->length;
    }
    
    return ret;
}

int LinkList_Insert(LinkList* list, LinkListNode* node, int pos)
{ 
    TLinkList* sList = (TLinkList*)list;
    int ret = (sList != NULL) && (pos >= 0) && (node != NULL);
    int i = 0;
    
    if( ret )
    {
        LinkListNode* current = (LinkListNode*)sList;
        
        for(i=0; (i<pos) && (current->next != NULL); i++)
        {
            current = current->next;
        }
        
        node->next = current->next;
        current->next = node;
        
        sList->length++;
    }
    
    return ret;
}

LinkListNode* LinkList_Get(LinkList* list, int pos) 
{
    TLinkList* sList = (TLinkList*)list;
    LinkListNode* ret = NULL;
    int i = 0;
    
    if( (sList != NULL) && (0 <= pos) && (pos < sList->length) )
    {
        LinkListNode* current = (LinkListNode*)sList;
        
        for(i=0; i<pos; i++)
        {
            current = current->next;
        }
        
        ret = current->next;
    }
    
    return ret;
}

LinkListNode* LinkList_Delete(LinkList* list, int pos)
{
    TLinkList* sList = (TLinkList*)list;
    LinkListNode* ret = NULL;
    int i = 0;

    if( (sList != NULL) && (0 <= pos) && (pos < sList->length) )
    {
        LinkListNode* current = (LinkListNode*)sList;

        for(i=0; i<pos; i++)
        {
            current = current->next;
        }

        ret = current->next;

        current->next = ret->next;
        
        sList->length--;
    }
    
    return ret;
}

測試檔案

#include <stdio.h>
#include <stdlib.h>
#include "LinkList.h"

struct Value
{
    LinkListNode header;
    int v;
};

int main(int argc, char *argv[]) 
{
    int i = 0;
    LinkList* list = LinkList_Create();
    
    struct Value v1;
    struct Value v2;
    
    v1.v = 1;
    v2.v = 2;

    LinkList_Insert(list, (LinkListNode*)&v1, LinkList_Length(list));
    LinkList_Insert(list, (LinkListNode*)&v2, LinkList_Length(list));

    
    for(i=0; i<LinkList_Length(list); i++)
    {
        struct Value* pv = (struct Value*)LinkList_Get(list, i);
        
        printf("%d\n", pv->v);
    }
    
    while( LinkList_Length(list) > 0 )
    {
        struct Value* pv = (struct Value*)LinkList_Delete(list, 0);
        
        printf("%d\n", pv->v);
    }
    
    LinkList_Destroy(list);
    
    return 0;
}

（4）. 小結

代碼難點主要在于插入與删除的實作，後續代碼實作會在此代碼基礎上進行修改或調用。
本文及以後代碼實作，目的在于實作一種可複用的代碼程式，故隻儲存具體資料元素的位址。

資料結構筆記——2. 線性表（1）. 線性表的本質（2）. 線性表的順序存儲結構（3）. 線性表的鍊式存儲結構（4）. 小結

文章目錄

（1）. 線性表的本質

（2）. 線性表的順序存儲結構

（3）. 線性表的鍊式存儲結構

（4）. 小結

繼續閱讀

樹的基本概念(定義、基本術語、性質)

GSL--GNU Scientific Library

D5|哈希表，善用資料結構

如何成為一名.net 工程師?

BMP檔案結構及圖像每行位元組計算方法

D. Ehab the Xorcist(構造+思維)

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

[轉]ISUP信令的IAM消息詳細内容

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器