線性表之鏈式表

主要內容

  1. 單鏈表
  2. 雙鏈表和循環鏈表

鏈式表是一種常見的數據結構,它由一系列節點組成,每個節點包含數據和指向下一個節點的指針。鏈式表具有靈活的插入和刪除操作,但訪問元素的效率較低。

一.單鏈表

單鏈表是最簡單的鏈表結構之一。它由一系列節點組成,每個節點包含數據和指向下一個節點的指針。單鏈表的特點是只能從頭節點開始依次訪問每個節點,無法直接訪問任意位置的節點。這使得單鏈表在插入和刪除操作時效率較高,但在查找和訪問特定節點時效率較低。

1.頭插法建立單鏈表

代碼如下(示例):

C語言代碼:

#include <stdio.h>
#include <stdlib.h>typedef struct Node {int data;struct Node* next;
} Node;Node* createListByHeadInsert(int arr[], int n) {Node* head = (Node*)malloc(sizeof(Node));head->next = NULL;for (int i = 0; i < n; i++) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = arr[i];newNode->next = head->next;head->next = newNode;}return head;
}

Python代碼:

class Node:def __init__(self, data):self.data = dataself.next = Nonedef create_list_by_head_insert(arr):head = Node(None)for data in arr:new_node = Node(data)new_node.next = head.nexthead.next = new_nodereturn head

2.尾插法建立單鏈表

代碼如下(示例):

C語言代碼:

Node* createListByTailInsert(int arr[], int n) {Node* head = (Node*)malloc(sizeof(Node));head->next = NULL;Node* tail = head;for (int i = 0; i < n; i++) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = arr[i];newNode->next = NULL;tail->next = newNode;tail = newNode;}return head;
}

Python代碼:

def create_list_by_tail_insert(arr):head = Node(None)tail = headfor data in arr:new_node = Node(data)tail.next = new_nodetail = new_nodereturn head

3.按序號查找結點值

代碼如下(示例):

C語言代碼:

int getElemByIndex(Node* head, int index) {Node* p = head->next;int i = 1;while (p && i < index) {p = p->next;i++;}if (!p || i > index) {return -1;}return p->data;
}

Python代碼:

def get_elem_by_index(head, index):p = head.nexti = 1while p and i < index:p = p.nexti += 1if not p or i > index:return -1return p.data

4.按值查找表結點

代碼如下(示例):

C語言代碼:

Node* locateElem(Node* head, int value) {Node* p = head->next;while (p && p->data != value) {p = p->next;}return p;
}

Python代碼:

def locate_elem(head, value):p = head.nextwhile p and p.data != value:p = p.nextreturn p

5.插入節點操作

代碼如下(示例):

C語言代碼:

void insertElem(Node* head, int index, int value) {Node* p = head;int i = 0;while (p && i < index - 1) {p = p->next;i++;}if (!p || i > index - 1) {return;}Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = value;newNode->next = p->next;p->next = newNode;
}

Python代碼:

def insert_elem(head, index, value):p = headi = 0while p and i < index - 1:p = p.nexti += 1if not p or i > index - 1:returnnew_node = Node(value)new_node.next = p.nextp.next = new_node

6.刪除結點操作

代碼如下(示例):

C語言代碼:

void deleteElem(Node* head, int value) {Node* p = head;while (p->next && p->next->data != value) {p = p->next;}if (p->next) {Node* temp = p->next;p->next = temp->next;free(temp);}
}

Python代碼:

def delete_elem(head, value):p = headwhile p.next and p.next.data != value:p = p.nextif p.next:temp = p.nextp.next = temp.nextdel temp

7.求表長操作

代碼如下(示例):

C語言代碼:

int getLength(Node* head) {Node* p = head->next;int length = 0;while (p) {length++;p = p->next;}return length;
}

Python代碼:

def get_length(head):p = head.nextlength = 0while p:length += 1p = p.nextreturn length

二.雙鏈表和循環鏈表

雙鏈表在單鏈表的基礎上增加了一個指向前一個節點的指針。這樣一來,雙鏈表可以雙向遍歷,即可以從頭節點向后遍歷,也可以從尾節點向前遍歷。這種特性使得雙鏈表在某些場景下具有更高的靈活性和效率。

1.雙鏈表的插入操作

代碼如下(示例):

C語言實現:

void insertNode(struct Node* prevNode, int newData) {if (prevNode == NULL) {printf("The given previous node cannot be NULL");return;}struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));newNode->data = newData;newNode->next = prevNode->next;prevNode->next = newNode;newNode->prev = prevNode;if (newNode->next != NULL) {newNode->next->prev = newNode;}
}

Python實現:

def insertNode(prev_node, new_data):if prev_node is None:print("The given previous node cannot be NULL")returnnew_node = Node(new_data)new_node.next = prev_node.nextprev_node.next = new_nodenew_node.prev = prev_nodeif new_node.next is not None:new_node.next.prev = new_node

2.雙鏈表的刪除操作

代碼如下(示例):

C語言實現:

void deleteNode(struct Node** head_ref, struct Node* del) {if (*head_ref == NULL || del == NULL) {return;}if (*head_ref == del) {*head_ref = del->next;}if (del->next != NULL) {del->next->prev = del->prev;}if (del->prev != NULL) {del->prev->next = del->next;}free(del);
}

Python實現:

def deleteNode(head_ref, del_node):if head_ref is None or del_node is None:returnif head_ref == del_node:head_ref = del_node.nextif del_node.next is not None:del_node.next.prev = del_node.previf del_node.prev is not None:del_node.prev.next = del_node.nextdel_node = None

循環鏈表是一種特殊的鏈表結構,其尾節點指向頭節點,形成一個閉環。循環鏈表可以用于模擬循環隊列或循環緩沖區等場景,其特點是可以無限循環訪問節點。

3.循環單鏈表

代碼如下(示例):

C語言實現:

struct Node {int data;struct Node* next;
};void insertNode(struct Node** head_ref, int newData) {struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));struct Node* last = *head_ref;newNode->data = newData;newNode->next = *head_ref;if (*head_ref == NULL) {newNode->next = newNode;} else {while (last->next != *head_ref) {last = last->next;}last->next = newNode;}*head_ref = newNode;
}

Python實現:

class Node:def __init__(self, data):self.data = dataself.next = Nonedef insertNode(head_ref, new_data):new_node = Node(new_data)last = head_refnew_node.next = head_refif head_ref is None:new_node.next = new_nodeelse:while last.next != head_ref:last = last.nextlast.next = new_nodehead_ref = new_node

循環雙鏈表是一種特殊的鏈式表,它的最后一個節點指向第一個節點,而第一個節點指向最后一個節點,形成一個循環。循環雙鏈表可以在任意位置插入和刪除節點。

4.循環雙鏈表的插入操作

代碼如下(示例):

C語言實現:

typedef struct Node {int data;struct Node* prev;struct Node* next;
} Node;void insert(Node* head, int data) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = data;newNode->prev = head;newNode->next = head->next;head->next->prev = newNode;head->next = newNode;
}

Python實現:

class Node:def __init__(self, data):self.data = dataself.prev = Noneself.next = Nonedef insert(head, data):new_node = Node(data)new_node.prev = headnew_node.next = head.nexthead.next.prev = new_nodehead.next = new_node

5.循環雙鏈表的刪除操作

代碼如下(示例):

C語言實現:

void delete(Node* node) {node->prev->next = node->next;node->next->prev = node->prev;free(node);
}

Python實現:

def delete(node):node.prev.next = node.nextnode.next.prev = node.prev

靜態鏈表是一種使用數組來模擬鏈表結構的數據結構。它的特點是在靜態分配的數組中維護節點的關系,而不是使用指針。靜態鏈表在某些特定場景下可以減少指針操作的開銷,但也限制了鏈表的動態性和靈活性。

6.靜態鏈表的基本操作

代碼如下(示例):

C語言實現:

#define MAX_SIZE 100
typedef struct {int data;int next;
} Node;int allocate(Node* arr) {int i = arr[0].next;if (i != -1) {arr[0].next = arr[i].next;}return i;
}void deallocate(Node* arr, int i) {arr[i].next = arr[0].next;arr[0].next = i;
}

Python實現:

MAX_SIZE = 100
class Node:def __init__(self, data, next):self.data = dataself.next = nextdef allocate(arr):i = arr[0].nextif i != -1:arr[0].next = arr[i].nextreturn idef deallocate(arr, i):arr[i].next = arr[0].nextarr[0].next = i

總結

以上是今天要講的內容,學到了鏈式表中單鏈表、雙鏈表、循環鏈表和靜態鏈表的相關操作。
線性表–鏈式表-1

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

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

相關文章

ELK+kafka+filebeat企業內部日志分析系統

1、組件介紹 1、Elasticsearch&#xff1a; 是一個基于Lucene的搜索服務器。提供搜集、分析、存儲數據三大功能。它提供了一個分布式多用戶能力的全文搜索引擎&#xff0c;基于RESTful web接口。Elasticsearch是用Java開發的&#xff0c;并作為Apache許可條款下的開放源碼發布…

module ‘d2l.torch‘ has no attribute ‘train_ch3‘

解決方法&#xff1a; 方法1&#xff1a; 如果沒有安裝d2l&#xff0c;請安裝 詳細步驟見安裝d2l 方法2&#xff1a; 先卸載舊的版本 pip uninstall d2l再下載新的版本&#xff0c;需要以管理員身份運行下載指令 pip install d2l0.17.5 --user完美解決&#xff01; ????…

創新研報|企業如何在不確定時期突破至新高度?

報告下載地址&#xff1a; 創新研報&#xff5c;BCG 2023最創新企業研究-在不確定時期躍升新高度 創新從未如此重要&#xff0c;領先的企業創新者正在證明這一切。BCG&#xff08;于2005年首次發布年度創新報告&#xff0c;其中列出了全球創新高管最欽佩的50家企業&#xf…

2824. 統計和小于目標的下標對數目 --力扣 --JAVA

題目 給你一個下標從 0 開始長度為 n 的整數數組 nums 和一個整數 target &#xff0c;請你返回滿足 0 < i < j < n 且 nums[i] nums[j] < target 的下標對 (i, j) 的數目。 解題思路 對數組進行排序&#xff0c;可以利用List自帶的sort函數傳遞比較規則(代碼中的…

【MATLAB源碼-第88期】基于matlab的灰狼優化算法(GWO)的柵格路徑規劃,輸出做短路徑圖和適應度曲線

操作環境&#xff1a; MATLAB 2022a 1、算法描述 灰狼優化算法&#xff08;Grey Wolf Optimizer, GWO&#xff09;是一種模仿灰狼捕食行為的優化算法。灰狼是群居動物&#xff0c;有著嚴格的社會等級結構。在灰狼群體中&#xff0c;通常有三個等級&#xff1a;首領&#xff…

數據結構-歸并排序+計數排序

1.歸并排序 基本思想&#xff1a; 歸并排序是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法的一個非常典型的應用。將已有序的子序列合并&#xff0c;得到完全有序的序列&#xff1b;即先使每個子序列有序&#xff0c;再使子序列段間有序。若將兩個有序表合并成一個…

2023年P氣瓶充裝證模擬考試題庫及P氣瓶充裝理論考試試題

題庫來源&#xff1a;安全生產模擬考試一點通公眾號小程序 2023年P氣瓶充裝證模擬考試題庫及P氣瓶充裝理論考試試題是由安全生產模擬考試一點通提供&#xff0c;P氣瓶充裝證模擬考試題庫是根據P氣瓶充裝最新版教材&#xff0c;P氣瓶充裝大綱整理而成&#xff08;含2023年P氣瓶…

pulseaudio是如何測試出音頻延遲的

通常專業的音頻設備生產廠商都有專業的設備來測試精確的音頻鏈路延時。 那么沒有專業設備怎么測試出音頻延遲呢?如下圖,我們可以看到pulseaudio可以測試出硬件音頻延遲。 那么,他是怎么測試出硬件延遲的呢?他的理論依據是什么呢?接下來我帶大伙一起探索一下。 /*占位…

紅隊攻防實戰之從邊界突破到漫游內網(無cs和msf)

也許有一天我們再相逢&#xff0c;睜大眼睛看清楚&#xff0c;我才是英雄。 本文首發于先知社區&#xff0c;原創作者即是本人 本篇文章目錄 網絡拓撲圖&#xff1a; 本次紅隊攻防實戰所需繪制的拓撲圖如下&#xff1a; 邊界突破 訪問網站&#xff1a; http://xxx.xxx.xxx…

leetcode刷題記錄——1991. 找到數組的中間位置

找到數組的中間位置 給你一個下標從 0 開始的整數數組 nums &#xff0c;請你找到 最左邊 的中間位置 middleIndex &#xff08;也就是所有可能中間位置下標最小的一個&#xff09;。 中間位置 middleIndex 是滿足 nums[0] nums[1] … nums[middleIndex-1] nums[middleInd…

數據傳輸的思考

Wi-Fi&#xff1a;Wi-Fi是一種無線網絡技術&#xff0c;可以用于無線互聯網接入、局域網通信和數據傳輸等。Wi-Fi基于IEEE 802.11標準&#xff0c;通過無線信號傳輸數據&#xff0c;提供高速的無線網絡連接。Wi-Fi可用于連接設備與路由器或者設備之間的直接通信&#xff0c;可以…

Linux 排查必看文件

目錄 1. 登錄日志 1.1 /var/log/wtmp 1.2 /var/log/btmp.* 1.3 /var/log/lastlog 1.4 /var/log/faillog 1.5 /var/log/secure 1.6 /var/log/auth.log 2. 系統日志 2.1 /var/log/cron.* 2.2 /var/log/syslog 2.3 /var/log/audit/audit.*log 3. 歷史命令 3.1 ~/…

Docker 中OpenResty下載與使用

1Panel安裝OpenResty 查看到就說明安裝成功 部署項目 在http中添加&#xff1a; server { listen 8001; //端口號 server_name localhost; location / { root /admin; //項目路徑 index index.html index.htm; …

Java二級醫院區域HIS信息管理系統源碼(SaaS服務)

一個好的HIS系統&#xff0c;要具有開放性&#xff0c;便于擴展升級&#xff0c;增加新的功能模塊&#xff0c;支撐好醫院的業務的拓展&#xff0c;而且可以反過來給醫院賦能&#xff0c;最終向更多的患者提供更好的服務。 系統采用前后端分離架構&#xff0c;前端由Angular、J…

P1028 [NOIP2001 普及組] 數的計算

時刻記住一句話&#xff1a;寫遞歸&#xff0c;1畫圖&#xff0c;2大腦放空&#xff01;&#xff01;&#xff01; 意思是&#xff0c;自己寫遞歸題目&#xff0c;先用樣例給的數據畫圖&#xff0c;然后想一個超級簡單的思路&#xff0c;直接套上去就可以了。 上題干&#xff…

牛客 HJ106 字符逆序 golang實現

牛客題目算法連接 題目 golang 實現 package mainimport ("fmt""bufio""os" )func main() {str, _ : bufio.NewReader(os.Stdin).ReadString(\n)if len(str) 0 {return } else {newstr:""strLen:len(str)-1for i:strLen;i>0;i-…

生產環境出現問題,測試人如何做工作復盤?

很多時候我們能把大部分的Bug或一些部署等問題在業務上線之前就解決了&#xff0c;但由于某些因素&#xff0c;線上問題還是時而出現&#xff0c;影響業務生產甚至是公司效益。 避免線上問題的發生以及線上問題及時處理是測試人員的一項重要職責&#xff0c;如何快速地處理&am…

XG916Ⅱ輪式裝載機后驅動橋設計機械設計CAD

wx供重浩&#xff1a;創享日記 對話框發送&#xff1a;裝載機 獲取完整論文報告工程源文件 本次設計內容為XG916Ⅱ裝載機后驅動橋設計&#xff0c;大致上分為主傳動的設計&#xff0c;差速器的設計&#xff0c;半軸的設計&#xff0c;最終傳動的設計四大部分。其中主傳動錐齒輪…

【多線程】Thread類的使用

目錄 1.概述 2.Thread的常見構造方法 3.Thread的幾個常見屬性 4.啟動一個線程-start() 5.中斷一個線程 5.1通過共享的標記來進行溝通 5.2 調用 interrupt() 方法來通知 6.等待一個進程 7.獲取當前線程引用 8.線程的狀態 8.1所有狀態 8.2線程狀態和轉移的意義 1.概述 …

Relabel與Metic Relabel

Prometheus支持多種方式的自動發現目標&#xff08;targets&#xff09;&#xff0c;以下是一些常見的自動發現方式&#xff1a; 靜態配置&#xff1a;您可以在Prometheus配置文件中直接列出要監測的目標。這種方式適用于目標相對穩定的情況下&#xff0c;例如固定的服務器或設…