數據結構之線性表（鏈表）

来源:https://www.cnblogs.com/XNQC1314/archive/2018/01/22/8331385.html
-Advertisement-
Play Games

鏈表 1.鏈表的定義：線性表的鏈式存儲結構的特點是用一組任意的存儲單元存儲線性表的數據元素（這組存儲單元可以是 連續的，也可以是不連續的）。因此，為了表示每個數據元素ai與其直接後繼數據元素ai+1之間的邏輯關係，對數據元素 ai來說，除了存儲其本身的信息之外，還需存儲一個指示其直接後繼的信息（即直 ...


鏈表

    1.鏈表的定義：線性表的鏈式存儲結構的特點是用一組任意的存儲單元存儲線性表的數據元素（這組存儲單元可以是

連續的，也可以是不連續的）。因此，為了表示每個數據元素ai與其直接後繼數據元素ai+1之間的邏輯關係，對數據元素

ai來說，除了存儲其本身的信息之外，還需存儲一個指示其直接後繼的信息（即直接後繼的存儲位置）。這兩部分信息組

成數據元素ai的存儲映像，稱為結點。它包括兩個域，其中存儲數據元素信息的域稱為數據域；存儲直接後繼存儲位置的

域稱為指針域。指針域中存儲的信息稱做指針或鏈。n個結點（ai(1<=i<=n）的存儲映像）鏈結成一個鏈表，即為線性表的

鏈式存儲結構。又由於此鏈表的每個結點中只包含一個指針域，故又稱線性鏈表或單鏈表。

   2.鏈表的數據結構

#define ElemType int 
typedef struct ListNode
{
    ElemType data;
    ListNode *next;
}ListNode;
typedef struct List
{
    ListNode *first;
    ListNode *last;
    size_t size;
}List;

    3.在鏈表中有以下操作：

void InitList(List *list);
bool push_back(List *list, ElemType x);
bool push_front(List *list, ElemType x);
void show(List *list);
void pop_back(List *list);
bool insert_val(List *list, ElemType x);
bool delete_val(List *list, ElemType key);
ListNode *find_key(List *list, ElemType key);
void clear_list(List *list);
void reverse_list(List *list);
void sort_list(List *list);
void destroy_list(List *list);

    以上聲明的方法有：（1）初始化一個鏈表.（2）尾插法向鏈表中添加元素.（3）頭插法向鏈表中添加元素.（4）展示鏈表

內容.（5）尾部刪除鏈表中的數據元素.（6）按值向鏈表中插入數據元素.（7）按值刪除鏈表中的數據元素.（8）按值查找

鏈表中的數據數據元素.（9）清空鏈表操作.（10）逆序排列鏈表中的數據元素.（11）對鏈表中的數據元素進行排序.（12）

銷毀鏈表.

   4.將上面所聲明的方法在LinkList.h的頭文件中進行實現：

#ifndef _LINKLIST_H
#define _LINKLIST_H

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

#define ElemType int 
typedef struct ListNode
{
    ElemType data;
    ListNode *next;
}ListNode;
typedef struct List
{
    ListNode *first;
    ListNode *last;
    size_t size;
}List;

void InitList(List *list);
bool push_back(List *list, ElemType x);
bool push_front(List *list, ElemType x);
void show(List *list);
void pop_back(List *list);
bool insert_val(List *list, ElemType x);
bool delete_val(List *list, ElemType key);
ListNode *find_key(List *list, ElemType key);
void clear_list(List *list);
void reverse_list(List *list);
void sort_list(List *list);
void destroy_list(List *list);

void InitList(List *list)
{
    list->first = list->last = (ListNode*)malloc(sizeof(ListNode));
    list->last->next = NULL;
    assert(list->first != NULL);
    list->size = 0;
}

bool push_back(List *list, ElemType x)
{
    ListNode *s = (ListNode*)malloc(sizeof(ListNode));
    if (s == NULL)
        return false;
    s->data = x;
    s->next = NULL;
    list->last->next = s;
    list->last = s;
    list->size++;
    return true;
}

bool push_front(List *list, ElemType x)
{
    ListNode *s = (ListNode*)malloc(sizeof(ListNode));
    if (s == NULL)
        return false;
    s->data = x;
    s->next = list->first->next;
    list->first->next = s;
    if (list->size == 0)
        list->last = s;
    list->size++;
    return true;
}

void show(List *list)
{
    ListNode *p = list->first->next;
    while (p != NULL)
    {
        cout << p->data << "->";
        p = p->next;
    }
    cout << "Over." << endl;
}

void pop_back(List *list)
{
    if (list->size == 0)
        return;
    ListNode *p = list->first;
    while (p->next != list->last)
        p = p->next;
    p->next = NULL;
    free(list->last);
    list->last = p;
    list->size--;
}

bool insert_val(List *list, ElemType x)
{
    ListNode *p = list->first;
    while (p->next != NULL && p->next->data < x)
        p = p->next;
    ListNode *s = (ListNode*)malloc(sizeof(ListNode));
    if (s == NULL)
        return false;
    s->data = x;
    s->next = NULL;
    s->next = p->next;
    p->next = s;
    if (p == list->last)
        list->last = s;
    list->size++;
    return true;
}

bool delete_val(List *list, ElemType key)
{
    if (list->size == 0)
        return false;
    ListNode *p = list->first;
    while (p->next != NULL && p->next->data != key)
        p = p->next;
    if (p->next == NULL)
        return false;
    ListNode *q = p->next;
    p->next = q->next;
    if (q == list->last)
        list->last = p;
    free(q);
    list->size--;
    return true;
}

ListNode *find_key(List *list, ElemType key)
{
    if (list->size == 0)
        return false;
    ListNode *p = list->first->next;
    while (p != NULL &&p->data != key)
        p = p->next;
    return p;
}

void clear_list(List *list)
{
    if (list->size == 0)
        return;
    ListNode *p = list->first->next;
    while (p != NULL)
    {
        list->first->next = p->next;
        free(p);
        p = list->first->next;
    }
    list->last = list->first;
    list->size = 0;
}

void reverse_list(List *list)
{
    if (list->size <= 1)
        return;
    ListNode *p = list->first->next;
    ListNode *q = p->next;
    list->last = p;
    list->last->next = NULL;
    while (q != NULL)
    {
        p = q;
        q = p->next;
        p->next = list->first->next;
        list->first->next = p;
    }
}

void sort_list(List *list)
{
    if (list->size <= 1)
        return;
    ListNode *p = list->first->next;
    ListNode *q = p->next;
    list->last = p;
    list->last->next = NULL;
    ListNode *t;
    while (q != NULL)
    {
        p = q;
        q = q->next;
        t = list->first;
        while (t->next != NULL && p->data > t->next->data)
            t = t->next;
        if (t->next = NULL)
            list->last = p;
        p->next = t->next;
        t->next = p;
    }
}

void destroy_list(List *list)
{
    clear_list(list);
    free(list->first);
    list->first = list->last = NULL;
}

#endif

  5.將上面所實現的方法在主函數中調用實現：

#include <iostream>
#include "LinkList.h"
using namespace std;

int main()
{
    List mylist;
    InitList(&mylist);

    ListNode *p = NULL;
    ElemType item;
    int pos;
    int select = 1;
    while (select)
    {
        cout << "******************************************" << endl;
        cout << "*[1] push_back       [2] push_front      *" << endl;
        cout << "*[3] Show            [4] pop_back        *" << endl;
        cout << "*[5] insert_val      [6] delete_val      *" << endl;
        cout << "*[7] find_key        [8] reverse_list    *" << endl;
        cout << "*[9] sort_list       [10] clear_list     *" << endl;
        cout << "*[0] quit_system                         *" << endl;
        cout << "******************************************" << endl;
        cout << "請選擇:>";
        cin >> select;
        switch (select)
        {
        case 1:
            cout << "請輸入要插入的數據(-1結束):>";
            while (cin >> item, item != -1)     //逗號表達式
            {
                push_back(&mylist, item);
            }
            break;
        case 2:
            cout << "請輸入要插入的數據(-1結束):>";
            while (cin >> item, item != -1) 
            {
                push_front(&mylist, item);
            }
            break;
        case 3:
            show(&mylist);
            break;
        case 4:
            pop_back(&mylist);
            break;
        case 5:
            cout << "請輸入要插入的值:>";
            cin >> item;
            insert_val(&mylist, item);
            break;
        case 6:
            cout << "請輸入要刪除的值:>";
            cin >> item;
            delete_val(&mylist, item);
            break;
        case 7:
            cout << "請輸入要查找的值:>";
            cin >> item;
            p = find_key(&mylist, item);
            if (p == NULL)
            {
                cout << "要查找的值:" << item << "不存在!" << endl;
            }
            break;
        case 8:
            reverse_list(&mylist);
            break;
        case 9:
            sort_list(&mylist);
            break;
        case 10:
            clear_list(&mylist);
            break;
        }
        system("pause");
        system("cls");
    }
    destroy_list(&mylist);

    return 0;
}

您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • Java學習筆記51（綜合項目：家庭記賬系統）
    這個案例幾乎用到了前50篇的所有內容，實現一個簡易的家庭記賬軟體 功能：賬務增刪改查，按條件查詢 需要的jar包： commons-dbcp-1.4.jar commons-pool-1.5.6.jar mysql-connector-java-5.1.37-bin.jar commons-dbut ...
  • 確認
    Consumer Acknowledgements and Publisher Confirms 消費者到RabbitMQ的投遞處理確認在AMQP 0-9-1中被稱之為“acknowledgements”；而RabbitMQ給生產者的確認是協議的擴展，這種協議擴展被叫做“publisher conf ...
  • ThinkPHP基礎知識（一）
    1.入口文件中定義的內容 2.U方法的參數規則 ('地址表達式',['參數'],['偽靜態尾碼'],['顯示功能變數名稱']) 3.如何判斷請求類型，常用的請求方式有哪兩種，I方法的參數規則？ 註意：變數類型不區分大小寫。 變數名則嚴格區分大小寫。 預設值和過濾方法均屬於可選參數。 4.成功和失敗，重定向跳 ...
  • 泛型編程-2
    上一篇 介紹了泛型最基本的用法，泛型類和泛型方法。 這篇將繼續慢慢的解開泛型的面紗。 類型限定 有的時候方法或者類為了一些需求需要對泛型的的類型做出 一些限定。 假如：有一個類對象ArrayList中的的每一個元素實現了AutoCloseable，想要把他們全部關閉，可以如下寫 類型的變異和通配符 ...
  • python3 第十八章 - 迭代器與生成器
    1、迭代器 迭代是訪問集合元素的一種方式 迭代器是一個可以記住遍歷的位置的對象。 迭代器對象從集合的第一個元素開始訪問，直到所有的元素被訪問完結束。迭代器只能往前不會後退。 迭代器有兩個基本的方法：iter() 和 next()。 字元串，列表或元組對象都可用於創建迭代器： 實例1： 以上代碼，輸出 ...
  • python 3.x 寫 shell sed 替換功能
    shell sed 替換功能 要替換的文件： ...
  • 構造函數
    構造函數特點： 函數名與類名相同、不用定義返回值類型、沒有return語句、構造函數可以有多個並以重載的方式存在 構造函數的作用： 給new出來的對象進行初始化 如果定義的一個類中沒有自定義的構造函數，系統會有預設的產生一個無參的構造函數， 如果有自定義的構造函數， 系統預設構造函數就不存在了，構造 ...
  • Python3 的分支與迴圈
    1：條件分支 if 條件 : 語句 else： 語句 2.縮寫 else: if : 可以簡寫為 elif ,因此Python 可以有效的避免“懸掛else” 舉例: 3:條件表達式（三元操作符） small = x if x<y else y 例子將下列代碼修改為三元操作符 修改後 4:斷言（as ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類