鍊式存儲結構

結點在存儲器中的位置是任意的，即邏輯上相鄰的資料元素在實體上不一定相鄰

有關術語

結點：資料元素的存儲映像。由資料域和指針域兩部分組成
- 資料域：存儲元素數值資料
- 指針域：存儲直接後繼結點的存儲位置
連結清單：n 個結點由指針鍊組成一個連結清單。它是線性表的鍊式存儲映像，稱為線性表的鍊式存儲結構
- 單連結清單
  - 結點隻有一個指針域的連結清單，稱為單連結清單或線性連結清單
- 雙連結清單
  - 有兩個指針域的連結清單，稱為雙連結清單
- 循環連結清單
  - 首尾相接的連結清單稱為循環連結清單
頭指針
- 指向連結清單中第一個結點的指針
首元結點
- 指連結清單中存儲第一個資料元素a1的結點
頭結點
- 在連結清單的首元結點之前附設的一個結點；資料域内隻放空表标志和表長等資訊
- 設定頭結點的好處
  - 便于首元結點的處理
    - 首元結點的位址儲存在頭結點的指針域中,是以在連結清單的第一個位置上的操作和其它位置一緻，無須進行特殊處理;
  - 便于空表和非空表的統一處理
    - 無論連結清單是否為空，頭指針都是指向頭結點的非空指針，是以空表和非空表的處理也就統一了。

連結清單的特點

通路時隻能通過頭指針進傳入連結表，并通過每個結點的指針域向後掃描其餘結點，是以尋找第一個結點和最後一個結點所花費的時間不等

連結清單的優缺點

優點
- 資料元素的個數可以自由擴充
- 插入、删除等操作不必移動資料，隻需修改連結指針，修改效率較高
缺點
- 存儲密度小
- 存取效率不高，必須采用順序存取，即存取資料元素時，隻能按連結清單的順序進行通路（順藤摸瓜）

順序表和連結清單的比較

存儲結構比較項目	順序表	連結清單
存儲空間	預先配置設定，會導緻空間閑置或溢出現象	動态配置設定，不會出現存儲空間閑置或溢出現象
存儲密度	不用為表示結點間的邏輯關系而增加額外的存儲開銷，存儲密度等于1	需要借助指針來展現元素間的邏輯關系，存儲密度小于1
存取元素	随機存取，按位置通路元素的時間複雜度為O(1)	順序存取，按位置通路元素時間複雜度為O(n)
插入、删除	平均移動約表中一半元素，時間複雜度為O(n)	不需移動元素，确定插入、删除位置後，時間複雜度為O(1)
适用情況	① 表長變化不大，且能事先确定變化的範圍 ② 很少進行插入或删除操作，經常按元素位置序号通路資料元素	① 長度變化較大 ② 頻繁進行插入或删除操作

C++代碼實作

#include<iostream>
#include<stdlib.h>
using namespace std;

#define OVERFLOW -2
#define OK 1
#define ERROR -1

typedef int Status;
typedef int Elemtype;

/* typedef struct LNode{
    Elemtype data;
    struct LNode *next;
}LNode;

typedef struct{
    lnode *l;
}LinkList; */

typedef struct LNode {
    Elemtype data;
    struct LNode* next;
}LNode, * LinkList;


// 構造一個空的單連結清單
Status InitList(LinkList& L)
{
    L = new LNode; // 頭指針L指向頭結點
    if (!L) exit(OVERFLOW);
    L->next = NULL;  // 指針域置空
    return OK;
}

// 前插法建立單連結清單
void CreateList_H(LinkList& L, int n)
{
    LinkList p;
    int i;
    L = new LNode;  
    L->next = NULL;  // 先建立一個帶頭結點的空連結清單
    // for(i = 0; i < n; ++i)
    for (i = 1; i < n + 1; ++i)
    {
        cout << "請輸入第" << i << "個結點的資料" << endl;
        p = new LNode;  // 生成新結點*p
        cin >> p->data;  // 輸入元素指派給新結點*p的資料域
        p->next = L->next;
        L->next = p; // 将新結點*p插入到頭結點之後
    }
}


// 尾插法建立單連結清單
Status CreateList_L(LinkList& L, int n)
{
    LinkList r, p;
    int i;
    L = new LNode;
    L->next = NULL;
    // 尾結點指向頭結點
    r = L;
    for (i = 1; i < n + 1; ++i)
    {
        cout << "請輸入第" << i << "個結點的資料" << endl;
        p = new LNode;  // 生成新結點
        cin >> p->data;
        p->next = NULL;
        r->next = p;
        r = p;
    }
    return OK;
}

// 取值
Status GetElem(LinkList L, int i, Elemtype& e)
{
    // 根據序号i擷取元素的值，用e傳回值
    int j;
    LinkList p;
    for (p = L->next, j = 1; j < i && p; j++)
        p = p->next;
    if (!p || j > i) return ERROR;
    e = p->data;
    return OK;
}

// 在連結清單中查找值為e的元素的位置，傳回其位址
LinkList LocateElem_L(LinkList L, Elemtype e)
{
    LinkList p;
    p = L->next;
    while (p && p->data != e)
    {
        p = p->next;
    }
    return p;
}

// 插入
Status ListInsert(LinkList& L, int i, Elemtype& e)
{
    LinkList p, s;
    int j;
    for (p = L, j = 0;j < i - 1 && p; j++)
        p = p->next;
    if (!p || j > i) return ERROR;
    s = new LNode;
    s->data = e;
    s->next = p->next;
    p->next = s;
    return OK;
}

// 删除
Status ListDelete(LinkList& L, int i, Elemtype& e)
{
    LinkList p, q;
    int j;
    for (p = L, j = 0;j < i - 1 && p; j++)
        p = p->next; 
    if (!p || j > i) return ERROR;
    q = p->next;
    p->next = q->next;
    e = q->data;
    delete q;
    return OK;
}

// 銷毀
Status DestroyList(LinkList& L)
{
    LinkList p;
    while (L)
    {
        p = L;
        L = L->next;
        delete p;
    }
    return OK;
}

// 清空
Status ClearList(LinkList& L)
{
    LinkList p, q;
    p = L->next; // p指向第一個結點
    while (p)  // 沒到表尾
    {
        q = p->next;
        delete p;
        p = q;
    }
    L->next = NULL;  // 頭結點指針域為空
    return OK;
}

// 求表長
int ListLength_L(LinkList L){
    // 傳回L中資料元素的個數
    int i;
    LinkList p;
    p = L->next;  // p指向第一個結點
    i = 0;
    while (p)  // 周遊單連結清單，統計結點數
    {
        i++;
        p = p->next;
    }
    return i;
}

// 判斷表是否為空
int ListEmpty(LinkList L) {
    // 若L為空，傳回1；否則，傳回0
    if (L->next)
        return 0;
    else
        return 1;
}

int main()
{
    LinkList L;
    Elemtype e;
    int i, n;

    // 建立連結清單測試
    cout << "請輸入表長：";
    cin >> n;
    // 尾插法建立
    CreateList_L(L, n);

    cout << "表長為：";
    cout << ListLength_L(L) << endl;

    // 查找測試
    cout << "請輸入您需要查找元素的位置：";
    cin >> i;
    GetElem(L, i, e);
    cout << e;

    // 删除測試
    cout << "請輸入您要删除的元素的位置：";
    cin >> i;
    ListDelete(L, i, e);
    cout << e;

    return 0;
}

Python代碼實作

SingleNode

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Date    : 2019-10-02 09:32:38
# @Author  : Your Name ([email protected])
# @Link    : http://example.org
# @Version : $Id$

class SingleNode(object):
    def __init__(self, item):
        self.item = item
        self.next = None

class SingleLinkList(object):
    def __init__(self):
        self._head = None

    def isEmpty(self):
        return self._head == None

    def length(self):
        cur = self._head

        count = 0

        while cur:
            count += 1
            cur = cur.next

        return count

    def travel(self):
        cur = self._head

        while cur:
            print(cur.item, end=" ")
            cur = cur.next
        print()
        return None

    def addFirst(self, item):
        node = SingleNode(item)
        node.next = self._head
        self._head = node

    def append(self, item):
        node = SingleNode(item)
        
        if self.isEmpty():
            self._head = node

        else:
            cur = self._head
            while cur.next:
                cur = cur.next
            cur.next = node

    def insert(self, pos, item):
        if pos <= 0:
            self.addFirst(item)
        elif pos > (self.length() - 1):
            self.append(item)
        else:
            node = SingleNode(item)
            count = 0
            pre = self._head
            # 資料從0開始
            # 從1開始 應該為 pos - 2
            while count < (pos - 1):
                count += 1
                pre = pre.next

            node.next = pre.next
            pre.next = node

    def remove(self, item):
        cur = self._head
        pre = None

        while cur:
            if cur.item == item:
                if not pre:
                    self._head = cur.next
                else:
                    pre.next = cur.next

                break

            else:
                pre = cur
                cur = cur.next

    def search(self, item):
        cur = self._head
        while cur:
            if cur.item == item:
                return True
            cur = cur.next
        return False


if __name__ == '__main__':
    sll = SingleLinkList()
    sll.addFirst(10)
    sll.addFirst(20)
    sll.append(30)
    sll.travel()
    sll.remove(10)
    sll.travel()
    print(sll.search(30))
    print(sll.search(10))
    sll.insert(2, 40)
    sll.travel()
    print(sll.length())
    print(sll.isEmpty())
    sll.insert(2, 50)
    sll.travel()

20 10 30 
20 30 
True
False
20 30 40 
3
False
20 30 50 40 
[Finished in 0.6s]

SingleCycLinkedList

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Date    : 2019-10-02 11:13:14
# @Author  : Your Name ([email protected])
# @Link    : http://example.org
# @Version : $Id$

class SingleNode(object):
    def __init__(self, item):
        self.item = item
        self._head = None

class SingleCysLinkedList(object):
    def __init__(self):
        self._head = None

    def is_empty(self):
        return self._head == None

    def length(self):
        if self.is_empty():
            return 0
        count = 1
        cur = self._head
        while cur.next != self._head:
            count += 1
            cur = cur.next
        return count

    def travel(self):
        if self.is_empty():
            return
        cur = self._head
        print(cur.item, end=" ")

        while cur.next != self._head:
            cur = cur.next
            print(cur.item, end=" ")
        print()

    def addFirst(self, item):
        node = SingleNode(item)
        if self.is_empty():
            self._head = node
            node.next = self._head
        else:
            node.next = self._head
            cur = self._head
            while cur.next != self._head:
                cur = cur.next
            cur.next = node
            self._head = node

    def append(self, item):
        node = SingleNode(item)
        if self.is_empty():
            self._head = node
            node.next = self._head
        else:
            node.next = self._head
            cur = self._head
            while cur.next != self._head:
                cur = cur.next
            cur.next = node
            node.next = self._head

    def insert(self, pos, item):
        if pos<= 0:
            self.addFirst(item)
        elif pos > (self.length() - 1):
            self.append(item)
        else:
            node = SingleNode(item)
            cur = self._head
            count = 0
            while count < (pos - 1):
                count += 1
                cur = cur.next
            node.next = cur.next
            cur.next = node

    def remove(self, item):
        if self.is_empty():
            return
        cur = self._head
        pre = None
        if cur.item == item:
            # 删除第一個元素
            if cur.next != self._head:
                while cur.next != self._head:
                    cur = cur.next
                cur.next = self._head.next
                self._head = self._head.next
            else:
                # 隻有一個元素
                self._head = None

        else:
            pre = self._head
            while cur.next != self._head:
                if cur.item == item:
                    pre.next = cur.next
                    return
                else:
                    pre = cur
                    cur = cur.next
            if cur.item == item:
                pre.next = cur.next

    def search(self, item):
        if self.is_empty():
            return False
        cur = self._head
        if cur.item == item:
            return True
        while cur.next != self._head:
            cur = cur.next
            if cur.item == item:
                return True
        return False    

if __name__ == '__main__':
    ll = SingleCysLinkedList()
    ll.addFirst(1)
    ll.addFirst(2)
    ll.append(3)
    ll.insert(2, 4)
    ll.insert(4, 5)
    ll.insert(0, 6)
    print("length: {0}".format(ll.length()))
    ll.travel()
    print(ll.search(3))
    print(ll.search(7))
    ll.remove(1)
    print("length:", ll.length())
    ll.travel()

length: 6
6 2 1 4 3 5 
True
False
length: 5
6 2 4 3 5 
[Finished in 0.4s]

DLinkList

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Date    : 2019-10-02 12:10:18
# @Author  : Your Name ([email protected])
# @Link    : http://example.org
# @Version : $Id$

class Node(object):
    def __init__(self, item):
        self.item = item
        self.next = None
        self.prev = None

class DLinkList(object):
    def __init__(self):
        self._head = None

    def is_empty(self):
        return self._head == None

    def length(self):
        cur = self._head
        count = 0
        while cur:
            count += 1
            cur = cur.next
        return count

    def travel(self):
        cur = self._head
        while cur:
            print(cur.item, end=" ")
            cur = cur.next
        print()

    def add(self, item):
        node = Node(item)
        if self.is_empty():
            self._head = node
        else:
            node.next = self._head
            self._head.prev = node
            self._head = node

    def append(self, item):
        node = Node(item)
        if self.is_empty():
            self._head = node
        else:
            cur = self._head
            while cur.next:
                cur = cur.next
            cur.next = node
            node.prev = cur

    def search(self, item):
        cur = self._head
        while cur:
            if cur.item == item:
                return True
            cur = cur.next
        return False

    def insert(self, pos, item):
        if pos <= 0:
            self.add(item)
        elif pos > (self.length() - 1):
            self.append(item)
        else:
            node = Node(item)
            cur = self._head
            count = 0
            # 移動到指定位置的前一個位置
            while count < (pos - 1):
                count += 1
                cur = cur.next
            # 将node的prev指向cur
            node.prev = cur
            # 将node的next指向cur的下一個結點
            node.next = cur.next
            # 将cur的下一個結點的prev指向node
            cur.next.prev = node
            # 将cur的next指向node
            cur.next = node

    def remove(self, item):
        if self.is_empty():
            return
        else:
            cur = self._head
            if cur.item == item:
                if cur.next == None:
                    self._head = None
            else:
                cur.next.prev = None
                self._head = cur.next
            return

        while cur:
            if cur.item == itme:
                cur.prev.next = cur.next
                cur.next.prev = cur.prev
                break

            cur = cur.next

if __name__ == '__main__':
    ll = DLinkList()
    ll.add(1)
    ll.add(2)
    ll.append(3)
    ll.insert(2, 4)
    ll.insert(4, 5)
    ll.insert(0, 6)
    print("length:", ll.length())
    ll.travel()
    print(ll.search(3))
    print(ll.search(4))
    ll.remove(1)
    print("length: {}".format(ll.length()))
    ll.travel()

length: 6
6 2 1 4 3 5 
True
True
length: 5
2 1 4 3 5 
[Finished in 0.1s]

資料結構——連結清單鍊式存儲結構

鍊式存儲結構

有關術語

連結清單的特點

連結清單的優缺點

順序表和連結清單的比較

C++代碼實作

Python代碼實作

SingleNode

SingleCycLinkedList

DLinkList

繼續閱讀

libsvm for python 安裝

學習軟體測試基礎測試第七天

Zeppelin 配置通路 REST APIApache Zeppelin Configuration REST API

【Torch】最簡潔logging使用指南

C++實作簡單順序表

27. Remove Element(清單)題目代碼

C經典書籍筆記——C陷阱與缺陷②(文法陷阱之優先級)一、錯誤案列二、優先級規律

Cloud Studio初體驗

使用 ctypes 進行 Python 和 C 的混合程式設計

【python】【資料處理】畫多元資料分布圖

線性表之順序表的實作

C++判斷素數、求最大公約數代碼判斷一個數是否為素數求兩個數的最大公約數

SequoiaDB巨杉資料庫C++驅動概述

【python】netconf協定對接管理裝置

「Python 網絡自動化」NETCONF —— Python 使用 NETCONF 管理配置 H3C 網絡裝置

在python中建立excel并寫入