數據結構第3問：什么是線性表？

線性表

線性表由具有相同數據類型的n個元素構成，這些元素之間存在一一對應的線性關系。其中n為表長，當n=0的時候線性表是一個空表。簡單來說，線性表中的元素排列成一條線，每個元素最多有一個直接的前驅和后繼（除第一個和最后一個元素外）。線性表的第一個數據元素稱為表頭元素，最后一個數據元素稱為表尾元素。

線性表的特點

  1. 表中元素的個數有限。
  2. 表中元素具有邏輯上的順序，有先后次序。
  3. 表中元素都是數據元素，每個元素都是單獨的基本單位。
  4. 表中元素的數據類型相同，占用相同大小的存儲空間。
  5. 表中元素具有抽象性，表示邏輯上的數據對象。
  6. 表中每個元素除首末元素外，有且僅有一個直接前驅和一個直接后繼，保證線性關系。
  7. 線性表可用順序存儲（如數組）或鏈式存儲（如鏈表）兩種方式實現。
  8. 支持按位置訪問元素，比如通過索引或指針遍歷。
  9. 線性表的邏輯結構獨立于物理存儲，實現方式多樣。

線性表的基本操作

InitList(&L);			// 初始化線性表
Length(L);				// 求表長。返回表L的長度，即L中數據元素的個數
LocateElem(L, e);		// 按值查找操作，即查找表中具有給定e的元素
GetElem(L, i);			// 按位查找操作，獲取表L中第i個位置的元素的值
ListInsert(&L, i, e);	// 將元素e插入表L的第i個位置
ListDelete(&L, i, &e);	// 刪除表L第i個位置的元素，并用e返回刪除元素的值
PrintList(L);			// 按先后順序打印出表L的所有元素值
Empty(L);				// 判斷表L是否為空，為空返回true，否則返回false
DestyoyList(&L);		// 銷毀線性表

線性表的順序表示：順序表

線性表的順序存儲也稱順序表。

順序表是一種線性表的存儲結構，也叫做“順序存儲結構”或“順序結構”。它將線性表中的元素按順序存放在一塊連續的存儲空間中（通常是數組），每個元素占用相同大小的存儲單元。通過元素的下標，可以快速訪問和定位元素。簡單來說，順序表就是利用數組實現的線性表。

由于每個數據元素的存儲位置都和順序表的起始位置相差一個和該數據元素的位序乘正比的常數，因此順序表的任意數據元素都支持隨機存取，所以線性表的順序存儲結構是一種隨機存取的存儲結構。

隨機存取：只要一種數據結構能夠在常數時間 O(1) 內直接找到任意元素的地址，就可以稱之為支持隨機存取。支持隨機存取的數據結構具有以下特征：

  1. 直接訪問：能夠直接訪問任何元素而不需要依賴于順序遍歷。例如，通過索引或其他唯一標識符（如鍵）可以直接獲取到數據。

  2. 時間復雜度：支持隨機存取的關鍵是，在訪問任何元素時，不論元素在數據結構中的位置，都能保持常數時間的訪問復雜度 O(1)。這意味著，無論數據的大小如何，訪問時間始終是固定的。

靜態分配內存空間的順序表實例

#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>#define MaxSize 100
// 描述一個順序表的存儲結構
typedef struct
{unsigned char data[MaxSize];unsigned int length;
} SqList;// 順序表初始化
void InitList(SqList *L)
{L->length = 0;
}// 求表長
int Length(SqList L)
{return L.length;
}// 按值查找操作，即查找表中具有給定值e的元素
int LocateElem(SqList L, unsigned char e)
{for (int i = 0; i < L.length; i++){if (L.data[i] == e)return i + 1;}return 0;
}// 按位查找操作，獲取表L中第i個位置的元素的值
int GetElem(SqList L, unsigned int i)
{if (i < 1 || i > L.length)return 0;elsereturn (L.data[i - 1]);
}// 將元素e插入表L的第i個位置
bool ListInsert(SqList *L, unsigned int i, unsigned char e)
{if (i < 1 || i > L->length + 1)return false;if (L->length >= MaxSize)return false;// 搬運元素的時候注意要從后往前開始搬運，從前往后會導致前面的數據元素把后面的元素覆蓋掉for (int j = L->length; j >= i; j--)L->data[j] = L->data[j - 1];L->data[i - 1] = e;L->length++;return true;
}// 刪除表L第i個位置的元素，并用e返回刪除元素的值
bool ListDeleteSqList(SqList *L, unsigned int i, unsigned char *e)
{if (i < 1 || i > L->length + 1)return false;if (L->length >= MaxSize)return false;*e = L->data[i-1];for (int j = i; j < L->length; j++)L->data[j-1] = L->data[j];L->length--;return true;
}// 按先后順序打印出表L的所有元素值
void PrintList(SqList *L)
{for (int i = 0; i < L->length; i++){printf("Array index:%d, data:%d\r\n", i, L->data[i]);}
}// 判斷表L是否為空，為空返回true，否則返回false
bool Empty(SqList L)
{if (L.length == 0)return true;elsereturn false;
}// 銷毀順序表
void DestyoyList(SqList *L)
{L->length = 0;L = NULL;
}

線性表的鏈式表示：鏈表

順序表雖然具有隨機存取的優點，但是進行刪除和插入的操作時需要移動大量的元素，并且需要一段連續的內存空間進行存儲。而鏈式存儲的線性表，不需要使用連續的一段內存空間來存儲整個線性表，它是利用 “鏈” 建立元素之間的邏輯關系，因此插入和刪除操作不需要移動元素，只需要修改指針，但這樣也就失去了順序表隨機存取的優點。

鏈表是一種線性表的鏈式存儲結構。每個節點包含數據部分和指針部分，指針指向下一個節點的位置，這樣節點按邏輯順序連接起來，形成一個線性結構。通過指針的連接，可以方便地進行插入和刪除操作，不需要像順序表那樣移動大量元素。

  1. 單鏈表：
    • 除尾節點外，每個節點只有一個指針，指向下一個節點。
    • 尾節點的指針指向 NULL，表示鏈表結束。
  2. 雙鏈表：
    • 除頭尾節點外，每個節點有兩個指針，分別指向上一個節點和下一個節點。
    • 頭節點的前驅指針指向 NULL，后繼指針指向下一個節點。
    • 尾節點的后繼指針指向 NULL，前驅指針指向上一個節點。
  3. 循環單鏈表：
    • 每個節點都有一個指針指向下一個節點。
    • 尾節點指針不指向 NULL，而是指向頭節點，形成環狀結構。
  4. 循環雙鏈表：
    • 每個節點有兩個指針，分別指向上一個節點和下一個節點。
    • 頭節點的前驅指針指向尾節點，尾節點的后繼指針指向頭節點，形成雙向環狀結構。

動態分配內存空間的單鏈表實例

#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>
#include <stdlib.h>typedef struct Node
{int data;struct Node *next;
} Node, *Linklist;/*** 方法1：初始化鏈表頭指針（通過入口參數傳入指針的地址）* @param L 指向鏈表頭指針的指針（二級指針）* @return true 分配成功，false 分配失敗** 說明：* - 函數接收一個指向頭指針變量的指針（Linklist *L），*   可以在函數內部修改調用者的頭指針變量，使其指向新節點。* - malloc 分配一塊內存空間存儲一個 Node 結構體。* - 如果分配失敗，返回 false。* - 分配成功后，設置頭節點的數據成員和指針域。* - 這種寫法充分利用了 C 語言的值傳遞特性，通過傳入指針的地址，*   修改指針本身，實現頭指針的初始化。*/
bool init_Linklist(Linklist *L)
{*L = malloc(sizeof(Node));if (*L == NULL){return false;}(*L)->data = 1;(*L)->next = NULL;return true;
}/*** 方法2：初始化鏈表頭指針（通過函數返回新分配的節點指針）* @return 返回指向鏈表頭節點的指針，分配失敗返回 NULL** 說明：* - 函數內部通過 malloc 分配一個 Node 節點。* - 給新節點賦予初始數據和指針值。* - 函數直接返回新分配節點的指針。* - 調用者通過接收返回值獲得鏈表頭指針。* - 這種寫法簡潔，調用方便，適用于不需要返回其它狀態碼，*   只需要通過 NULL 判斷失敗的情況。*/
Linklist INIT2_Linklist(void)
{Linklist L = malloc(sizeof(Node));L->data = 1;L->next = NULL;return L;
}// 在頭節點后面插入新的節點
bool insert_below_head(Linklist *head, int new_data)
{Node *new_node = malloc(sizeof(Node));if (new_node == NULL)return false;new_node->data = new_data;new_node->next = (*head)->next;(*head)->next = new_node;return true;
}// 在頭節點前面插入新的節點
bool insert_front_head(Linklist *head, int new_data)
{// 創建新節點Node *new_node = malloc(sizeof(Node));if (new_node == NULL)return false;new_node->data = new_data;// 插入新節點new_node->next = (*head);// 更新頭指針為新的節點*head = new_node;return true;
}// 在尾節點后面插入新的節點
bool insert_tail(Linklist *head, int new_data)
{Node *new_node = malloc(sizeof(Node));if(new_node == NULL)return false;new_node->data = new_data;new_node->next = NULL;  // 尾節點的next為NULLNode *node = *head;// 遍歷找到最后一個節點，循環退出時node為尾節點while(node->next != NULL){node = node->next;}node->next = new_node;return true;
}// 在尾節點前面插入新的節點
bool insert_front_tail(Linklist *head, int new_data, int length)
{Node *new_node = malloc(sizeof(Node));if(new_node == NULL)return false;new_node->data = new_data;new_node->next = NULL;  // 尾節點的next為NULLNode *node = *head;while (node->next->next != NULL){node = node->next;}new_node->next = node->next;node->next = new_node;return true;
}// 打印鏈表所有節點
void print_node(Linklist *head)
{Node *new_node = *head;if (*head == NULL){printf("鏈表為空\n");return;}// 遍歷打印出所有節點，循環退出時new_node為NULLwhile (new_node != NULL){printf("node:%p,DATA:%d\r\n", new_node, new_node->data);new_node = new_node->next;}
}// 刪除鏈表
void delete_list(Linklist *head)
{while((*head) != NULL){Node *node = *head;*head = (*head)->next;free(node);}
}// 求鏈表長度
int getlistlength(Linklist *head)
{if (*head == NULL){printf("鏈表長度為:0\n");return 0;}Node *node = *head;int i = 0;while(node->next != NULL){i++;node = node->next;}printf("鏈表長度為:%d (不包含頭節點)\n",i);return i;
}// 按值查找某個節點，返回該節點的位號
int seek_node_by_value(Linklist *head, int value)
{Node *current = *head;int i = 0;while (current != NULL && current->data != value){current = current->next;i++;}printf("[check by value] index:%d,DATA:%d\r\n",i,current->data);return i;
}// 按位置查找某個節點，返回該節點的值,eg：查找第3個節點的值
int seek_node_by_index(Linklist *head, int index)
{Node *current = *head;int i = 0;while (current != NULL && i < index - 1){current = current->next;i++;}printf("[check by index] index:%d,DATA:%d\r\n",i,current->data);return current->data;
}// 將某個節點插入第i個位置（不考慮頭尾需要的額外處理）
bool insert_node_by_index(Linklist *head, int index, int data)
{Node *new_node = malloc(sizeof(Node));if(new_node == NULL)return false; new_node->data = data;Node *current_node = *head;    int i = 0;// while (i < index - 1) 這個條件正是為了讓循環結束時 current_node 指向插入位置的前驅節點，方便在這個位置插入新節點。while(current_node != NULL && i < index - 1){current_node = current_node->next;i++;}new_node->next = current_node->next;current_node->next = new_node;return true;
}// 刪除表中第i個節點
bool delete_node_by_index(Linklist *head, int index)
{Node *current = *head;int i = 0;while(current != NULL && i < index - 1){current = current->next;i++;}// 先保存待刪除的節點指針Node *node_to_delete = current->next;// 修改指針來斷開鏈表中的該節點current->next = current->next->next;// 最后釋放內存free(node_to_delete);return true;
}

順序表和鏈表的比較

  1. 存取方式

    1. 順序表：采用順序存取，通過數組的下標可以直接訪問任意位置的元素，訪問速度快（時間復雜度為O(1)）。
    2. 鏈表：采用鏈式存取，訪問元素時需從表頭開始沿指針逐個訪問，訪問特定位置元素時間復雜度為O(n)。

  2. 邏輯結構和物理結構

    1. 順序表

      邏輯結構是線性表，元素按順序排列。物理結構是連續的內存空間（數組）。

    2. 鏈表

      邏輯結構也是線性表，元素按順序連接。物理結構是分散的節點，節點通過指針連接，內存地址不必連續。

  3. 查找、插入和刪除操作

操作順序表鏈表
查找支持隨機訪問，時間O(1)需順序遍歷，時間O(n)
插入插入位置后元素需移動，時間O(n)插入位置通過指針調整，時間O(1)（已找到插入點）
刪除刪除后元素需移動，時間O(n)通過指針調整刪除，時間O(1)（已找到刪除點）

  1. 空間分配

    • 順序表：需要預先分配一塊連續的固定大小的內存空間，可能造成浪費或空間不夠。

    • 鏈表：動態分配內存，根據需要申請和釋放節點空間，節省空間但需要額外指針的存儲開銷。

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/916949.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/916949.shtml
英文地址，請注明出處：http://en.pswp.cn/news/916949.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

常見CMS 靶場復現

常見CMS 靶場復現

一、wordpass1.修改模版文件getshell搭建網站登錄網站后臺更改網站模版的相關文件寫入一句話木馬憑借路徑訪問/wp-content/themes/twentyfifteen/404.php/?aphpinfo();2.上傳夾帶木馬的主題getshell外觀-->主題-->添加-->上傳-->瀏覽-->安裝-->訪問木馬文件…
閱讀更多...
Elasticsearch - 倒排索引原理和簡易實現

Elasticsearch - 倒排索引原理和簡易實現

倒排索引的功能設計倒排索引&#xff08;Inverted Index&#xff09;是一種高效的數據結構&#xff0c;常用于全文搜索和信息檢索系統。它的核心思想是將文檔中每個關鍵字&#xff08;term&#xff09;與包含該關鍵字的文檔列表進行映射。以下是實現倒排索引功能的設計步驟和代…
閱讀更多...
C#開發的Panel里控件拖放例子 - 開源研究系列文章

C#開發的Panel里控件拖放例子 - 開源研究系列文章

上次寫了Panel的分頁滾動控件( C#開發的Panel滾動分頁控件&#xff08;滑動版&#xff09; - 開源研究系列文章 - Lzhdims Fashion - 博客園 )&#xff0c;但是主要是想寫一個Panel里控件拖放的效果&#xff0c;然后分頁控件用于Panel里控件的分頁。此文這次寫的是控件拖放效果…
閱讀更多...
Thinkph6中常用的驗證方式實例

Thinkph6中常用的驗證方式實例

我們在使用thinkphp6中的數據驗證時&#xff0c;如果使用不多的話&#xff0c;會經常遇到校驗不對&#xff0c;在這個小問題上折騰很多&#xff0c;索引就不用了。我還不如直接寫if條件來的迅捷&#xff01;&#xff01;下面把常見的校驗方法進行一下整理&#xff1a;protected…
閱讀更多...
分享一個FPGA寄存器接口自動化工具

分享一個FPGA寄存器接口自動化工具

FPGA模塊越寫越多&#xff0c;規范性和可移植性卻堪憂。要是有一個工具可以根據模塊接口描述文件生成verilog和c頭文件就好了。苦苦搜尋找到了幾款免費的工具&#xff0c;SystemRDL、cheby和rggen。筆者學習了下cheby和reksio&#xff0c;reksio是gui版的cheby&#xff0c;這是…
閱讀更多...
小程序中事件對象的屬性與方法

小程序中事件對象的屬性與方法

在小程序中&#xff0c;事件處理函數的參數為事件對象&#xff08;通常命名為 e&#xff09;&#xff0c;包含了事件相關的詳細信息&#xff08;如事件類型、觸發元素、傳遞的數據等&#xff09;。事件對象的屬性和方法因事件類型&#xff08;如點擊、輸入、觸摸等&#xff09;…
閱讀更多...
使用寶塔“PostgreSQL管理器”安裝的PostgreSQL，如何設置遠程連接？

使用寶塔“PostgreSQL管理器”安裝的PostgreSQL，如何設置遠程連接？

安裝 PostgreSQL 使用寶塔“PostgreSQL管理器”安裝PostgreSQL&#xff0c;版本可以根據自己的需求來選擇&#xff0c;我這里使用的是16.1 創建數據庫 根據下圖所示步驟創建數據庫&#xff0c;其中 “訪問權限”一定要選擇“所有人”啟用遠程連接設置允許所有 IP 連接 listen_a…
閱讀更多...
論文：M矩陣

論文：M矩陣

M矩陣是線性代數中的一個概念&#xff0c;它是一種特殊類型的矩陣&#xff0c;具有以下性質&#xff1a;非負的非對角線元素&#xff1a;矩陣的所有非對角線元素都是非負的&#xff0c;即對于矩陣MMM中的任意元素mijm_{ij}mij?&#xff0c;當i≠ji\neq jij時&#xff0c;有m…
閱讀更多...
跳躍表可視化深度解析：動態演示數據結構核心原理

跳躍表可視化深度解析：動態演示數據結構核心原理

跳躍表可視化深度解析&#xff1a;動態演示數據結構核心原理 一、跳躍表基礎概念與核心優勢 跳躍表&#xff08;SkipList&#xff09;是一種基于多層索引鏈表的數據結構&#xff0c;通過概率平衡實現高效的插入、刪除和查找操作。其核心優勢體現在&#xff1a; ?時間復雜度優…
閱讀更多...
《Sentinel服務保護實戰：控制臺部署與SpringCloud集成指南》

《Sentinel服務保護實戰：控制臺部署與SpringCloud集成指南》

sentinel 介紹 Sentinel是阿里巴巴開源的一款服務保護框架&#xff0c;目前已經加入SpringCloudAlibaba中。官方網站&#xff1a; home | Sentinel Sentinel 的使用可以分為兩個部分: 核心庫&#xff08;Jar包&#xff09;&#xff1a;不依賴任何框架/庫&#xff0c;能夠運行…
閱讀更多...
IBM Watsonx BI：AI賦能的下一代商業智能平臺

IBM Watsonx BI：AI賦能的下一代商業智能平臺

產品概覽 IBM Watsonx BI 是基于 watsonx 企業級 AI 與數據平臺 構建的智能分析解決方案&#xff0c;專為現代化企業打造。它深度融合人工智能技術&#xff0c;突破傳統 BI 工具的限制&#xff0c;通過自動化數據洞察、自然語言交互和預測分析&#xff0c;幫助企業在復雜數據環…
閱讀更多...
Python實現GO鵝優化算法優化GBRT漸進梯度回歸樹回歸模型項目實戰

Python實現GO鵝優化算法優化GBRT漸進梯度回歸樹回歸模型項目實戰

說明&#xff1a;這是一個機器學習實戰項目&#xff08;附帶數據代碼文檔&#xff09;&#xff0c;如需數據代碼文檔可以直接到文章最后關注獲取 或者私信獲取。 1.項目背景 隨著大數據和人工智能技術的快速發展&#xff0c;回歸預測在金融、氣象、能源等多個領域中扮演著至關…
閱讀更多...
深度學習計算（深度學習-李沐-學習筆記）

深度學習計算（深度學習-李沐-學習筆記）

層和塊 單一輸出的線性模型&#xff1a;單個神經網絡 &#xff08;1&#xff09;接受一些輸入&#xff1b; &#xff08;2&#xff09;生成相應的標量輸出&#xff1b; &#xff08;3&#xff09;具有一組相關 參數&#xff08;parameters&#xff09;&#xff0c;更新這些參數…
閱讀更多...
leetcode熱題——搜索二維矩陣Ⅱ

leetcode熱題——搜索二維矩陣Ⅱ

目錄 搜索二維矩陣Ⅱ 題目描述 題解 解法一&#xff1a;暴力搜索 C 代碼實現 復雜度分析 解法二&#xff1a;二分查找 C 代碼實現 復雜度分析 解法三&#xff1a;Z字形查找 算法核心思想 算法步驟詳解 C 代碼實現 復雜度分析 搜索二維矩陣Ⅱ 題目描述 編寫一個…
閱讀更多...
牛客 - 數組中的逆序對

牛客 - 數組中的逆序對

描述 在數組中的兩個數字&#xff0c;如果前面一個數字大于后面的數字&#xff0c;則這兩個數字組成一個逆序對。輸入一個數組,求出這個數組中的逆序對的總數P。并將P對1000000007取模的結果輸出。 即輸出P mod 1000000007 數據范圍&#xff1a; 對于 50% 的數據, size≤104 s…
閱讀更多...
Linux 日志管理與時鐘同步詳解

Linux 日志管理與時鐘同步詳解

Linux 日志管理與時鐘同步詳解 一、日志管理 1. 日志服務概述 Linux 系統中主要有兩種日志服務&#xff0c;分別負責臨時和永久日志的管理&#xff1a; systemd-journald&#xff1a;存儲臨時日志&#xff0c;服務器重啟后日志會丟失&#xff0c;無需手動配置rsyslog&#xff1…
閱讀更多...
個人如何做股指期貨？

個人如何做股指期貨？

本文主要介紹個人如何做股指期貨&#xff1f;個人參與股指期貨交易需要遵循一定的流程和規則&#xff0c;同時需充分了解其高風險、高杠桿的特點&#xff0c;并做好風險管理。個人如何做股指期貨&#xff1f;一、了解股指期貨基礎股指期貨是以股票價格指數為標的物的金融期貨合…
閱讀更多...
設計模式-單例模式 Java

設計模式-單例模式 Java

模式概述 單例模式&#xff08;Singleton Pattern&#xff09;是設計模式中最基礎但應用最廣泛的創建型模式之一&#xff0c;確保一個類僅有一個實例&#xff0c;并提供一個全局訪問點。這種模式在需要全局唯一對象的場景中至關重要&#xff0c;如配置管理、線程池、數據庫連接…
閱讀更多...
RFID 系統行業前沿洞察：技術躍遷與生態重構

RFID 系統行業前沿洞察：技術躍遷與生態重構

在物聯網與人工智能深度融合的時代&#xff0c;RFID&#xff08;射頻識別&#xff09;系統正經歷從 “單品識別工具” 到 “智能決策中樞” 的范式轉變。這一技術憑借其非接觸式數據采集、環境適應性強、全生命周期追溯等特性&#xff0c;在醫療、制造、農業、環保等領域引發連…
閱讀更多...
實現implements InitializingBean, DisposableBean 有什么用

實現implements InitializingBean, DisposableBean 有什么用

在 Spring 框架中&#xff0c;實現 InitializingBean 和 DisposableBean 接口用于管理 Bean 的生命周期回調&#xff0c;分別控制 Bean 的初始化后和銷毀前行為。具體作用如下&#xff1a;1. InitializingBean 接口public interface InitializingBean {void afterPropertiesSet…
閱讀更多...
最新文章

Copyright @ 2022~2023