python算法與數(shù)據(jù)結(jié)構(gòu)之單鏈表的實(shí)現(xiàn)代碼
=一、鏈表
鏈表是一種物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點(diǎn)（鏈表中每一個(gè)元素稱為結(jié)點(diǎn)）組成，結(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成。每個(gè)結(jié)點(diǎn)包括兩個(gè)部分：一個(gè)是存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)域，另一個(gè)是存儲(chǔ)下一個(gè)結(jié)點(diǎn)地址的指針域。 相比于線性表順序結(jié)構(gòu)，操作復(fù)雜。由于不必須按順序存儲(chǔ)，鏈表在插入的時(shí)候可以達(dá)到O(1)的復(fù)雜度，比另一種線性表順序表快得多，但是查找一個(gè)節(jié)點(diǎn)或者訪問(wèn)特定編號(hào)的節(jié)點(diǎn)則需要O(n)的時(shí)間，而線性表和順序表相應(yīng)的時(shí)間復(fù)雜度分別是O(logn)和O(1)。
使用鏈表結(jié)構(gòu)可以克服數(shù)組鏈表需要預(yù)先知道數(shù)據(jù)大小的缺點(diǎn)，鏈表結(jié)構(gòu)可以充分利用計(jì)算機(jī)內(nèi)存空間，實(shí)現(xiàn)靈活的內(nèi)存動(dòng)態(tài)管理。但是鏈表失去了數(shù)組隨機(jī)讀取的優(yōu)點(diǎn)，同時(shí)鏈表由于增加了結(jié)點(diǎn)的指針域，空間開銷比較大。鏈表最明顯的好處就是，常規(guī)數(shù)組排列關(guān)聯(lián)項(xiàng)目的方式可能不同于這些數(shù)據(jù)項(xiàng)目在記憶體或磁盤上順序，數(shù)據(jù)的存取往往要在不同的排列順序中轉(zhuǎn)換。鏈表允許插入和移除表上任意位置上的節(jié)點(diǎn)，但是不允許隨機(jī)存取。鏈表有很多種不同的類型：?jiǎn)蜗蜴湵?，雙向鏈表以及循環(huán)鏈表。
二、單鏈表介紹
單向鏈表（單鏈表）是鏈表的一種，其特點(diǎn)是鏈表的鏈接方向是單向的，對(duì)鏈表的訪問(wèn)要通過(guò)順序讀取從頭部開始。單鏈表是一種鏈?zhǔn)酱嫒〉臄?shù)據(jù)結(jié)構(gòu)，用一組地址任意的存儲(chǔ)單元存放線性表中的數(shù)據(jù)元素。鏈表中的數(shù)據(jù)是以結(jié)點(diǎn)來(lái)表示的，每個(gè)結(jié)點(diǎn)的構(gòu)成： 元素(數(shù)據(jù)元素的映象) + 指針(指示后繼元素存儲(chǔ)位置) ，元素就是存儲(chǔ)數(shù)據(jù)的存儲(chǔ)單元，指針就是連接每個(gè)結(jié)點(diǎn)的地址數(shù)據(jù)。它的每個(gè)節(jié)點(diǎn)包含兩個(gè)域， 一個(gè)信息域（元素域）和一個(gè)鏈接域 。這個(gè)鏈接指向鏈表中的下一個(gè)節(jié)點(diǎn)，而最后一個(gè)節(jié)點(diǎn)的鏈接域則指向一個(gè)空值。
鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表將采用一組任意的存儲(chǔ)單元存放線性表中的數(shù)據(jù)元素。由于不需要按順序存儲(chǔ)，鏈表在插入、刪除數(shù)據(jù)元素時(shí)比順序存儲(chǔ)要快，但是在查找一個(gè)節(jié)點(diǎn)時(shí)則要比順序存儲(chǔ)要慢，使用鏈?zhǔn)酱鎯?chǔ)可以克服順序線性表需要預(yù)先知道數(shù)據(jù)大小的缺點(diǎn)，鏈表結(jié)構(gòu)可以充分利用內(nèi)存空間，實(shí)現(xiàn)靈活的內(nèi)存動(dòng)態(tài)管理。但是鏈?zhǔn)酱鎯?chǔ)失去了數(shù)組隨機(jī)存取的特點(diǎn)，同時(shí)增加了節(jié)點(diǎn)的指針域，空間開銷較大。
三、單鏈表結(jié)構(gòu)
- 表元素域elem用來(lái)存放具體的數(shù)據(jù)。
- 鏈接域next用來(lái)存放下一個(gè)節(jié)點(diǎn)的位置（python中的標(biāo)識(shí)）
- 變量p指向鏈表的頭節(jié)點(diǎn)（首節(jié)點(diǎn)）的位置，從p出發(fā)能找到表中的任意節(jié)點(diǎn)。
四、單鏈表的常用操作圖解
1、頭插
2、尾插
3、指定為之插入
4、刪除
五、單鏈表的python代碼實(shí)現(xiàn)
# 創(chuàng)建節(jié)點(diǎn)
class Node(object):
def __init__(self,item):
self.element = item
self.next = None
# 創(chuàng)建單鏈表類
class SingleLinkList(object):
def __init__(self):
self.header = None
self.length = 0
# 1、判斷是否為空
def is_empty(self):
if self.header == None:
return True
else:
return False
# 2、頭部插入
def add(self,node):
if self.is_empty():
self.header = node
else:
node.next = self.header
self.header = node
# currentNode = self.header
self.length += 1
# 3、尾部插入
def appent(self,node):
currentNode = self.header
if self.is_empty():
self.add(node)
else:
while (currentNode.next != None):
currentNode = currentNode.next
currentNode.next = node
self.length += 1
# 4、指定位置插入
def insert(self,node,index):
currentNode = self.header
if index>self.length+1 or index<=0:
print("你要插入的位置不對(duì)，請(qǐng)重現(xiàn)選擇位置")
if index == 1:
self.add(node)
elif index == 2:
node.next = self.header.next
self.header.next = node
self.length += 1
else:
for i in range(1,index-1):
currentNode = currentNode.next
node.next = currentNode.next
currentNode.next = node
self.length += 1
# 5、遍歷
def travel(self):
currentNode = self.header
if self.length == 0:
print("你要遍歷的鏈表沒有數(shù)據(jù)\n")
else:
print("你要遍歷的鏈表里面的元素有:",end=" ")
for i in range(self.length):
print("%s "%currentNode.element,end=" ")
currentNode = currentNode.next
print("\n")
# 6、排序不用交換節(jié)點(diǎn)的位置，只需要交換節(jié)點(diǎn)上的數(shù)據(jù)值
def list_sort(self):
for i in range(0,self.length-1):
currentNode = self.header
for j in range(0,self.length-i-1):
if currentNode.element > currentNode.next.element:
temp = currentNode.element
currentNode.element = currentNode.next.element
currentNode.next.element = temp
currentNode = currentNode.next
# 7、按索引刪除
def remove(self,index):
if index<=0 or index>self.length:
print("你輸入的下標(biāo)不對(duì)，請(qǐng)重新輸入")
return
else:
if index == 1:
self.header = self.header.next
currentNode = self.header
elif index == 2:
currentNode = self.header
currentNode.next = currentNode.next.next
else:
currentNode = self.header
for i in range(1,index-1):
currentNode = currentNode.next
currentNode.next = currentNode.next.next
self.length -= 1
# 8、查找是否包含,并返回下標(biāo)
def isContain(self,num):
contain = 0
currentNode = self.header
for i in range(self.length):
if currentNode.element == num:
print("%d在鏈表中%d處\n"%(num,i))
contain = 1
currentNode = currentNode.next
if contain == 0:
print("%d不在鏈表中\(zhòng)n"%num)
# 9、根據(jù)下標(biāo)找節(jié)點(diǎn)
def searchNodeByIndex(self,index):
currentNode = self.header
if index<=0 or index>self.length:
print("你輸入的下標(biāo)不對(duì)，請(qǐng)重新輸入\n")
return 0
else:
for i in range(index-1):
currentNode = currentNode.next
return currentNode
# 10、根據(jù)下標(biāo)修改節(jié)點(diǎn)的值
def modifyByIndex(self,index,num):
currentNode = self.header
if index<=0 or index>self.length:
print("你輸入的下標(biāo)不對(duì)，請(qǐng)重新輸入\n")
else:
for i in range(index-1):
currentNode = currentNode.next
currentNode.element = num
def main():
# 創(chuàng)建一個(gè)節(jié)點(diǎn)對(duì)象
node1 = Node(1)
# 創(chuàng)建一個(gè)單鏈表對(duì)象
single_link_list = SingleLinkList()
print("驗(yàn)證空鏈表的遍歷")
single_link_list.travel()
print("驗(yàn)證頭插")
single_link_list.add(node1)
single_link_list.travel()
print("驗(yàn)證尾插")
node2 = Node(2)
single_link_list.appent(node2)
single_link_list.travel()
print("驗(yàn)證按位置插入")
node3 = Node(3)
single_link_list.insert(node3,1)
single_link_list.travel()
print("繼續(xù)驗(yàn)證頭插")
node4 = Node(5)
single_link_list.add(node4)
single_link_list.travel()
print("繼續(xù)驗(yàn)證按位置插入")
node5 = Node(4)
single_link_list.insert(node5,4)
single_link_list.travel()
print("驗(yàn)證刪除")
single_link_list.remove(3)
single_link_list.travel()
print("驗(yàn)證查找一個(gè)節(jié)點(diǎn)是否在鏈表中")
single_link_list.isContain(8)
print("驗(yàn)證按下標(biāo)查找節(jié)點(diǎn)")
node = single_link_list.searchNodeByIndex(2)
print("第二個(gè)節(jié)點(diǎn)的值為：%s"%node.element)
print("\n驗(yàn)證排序")
single_link_list.list_sort()
single_link_list.travel()
print("驗(yàn)證修改")
single_link_list.modifyByIndex(2,10)
single_link_list.travel()
if __name__ == '__main__':
main()
運(yùn)行結(jié)果為：
驗(yàn)證空鏈表的遍歷
你要遍歷的鏈表沒有數(shù)據(jù)驗(yàn)證頭插
你要遍歷的鏈表里面的元素有: 1驗(yàn)證尾插
你要遍歷的鏈表里面的元素有: 1 2驗(yàn)證按位置插入
你要遍歷的鏈表里面的元素有: 3 1 2繼續(xù)驗(yàn)證頭插
你要遍歷的鏈表里面的元素有: 5 3 1 2繼續(xù)驗(yàn)證按位置插入
你要遍歷的鏈表里面的元素有: 5 3 1 4 2驗(yàn)證刪除
你要遍歷的鏈表里面的元素有: 5 3 4 2驗(yàn)證查找一個(gè)節(jié)點(diǎn)是否在鏈表中
8不在鏈表中驗(yàn)證按下標(biāo)查找節(jié)點(diǎn)
第二個(gè)節(jié)點(diǎn)的值為：3驗(yàn)證排序
你要遍歷的鏈表里面的元素有: 2 3 4 5驗(yàn)證修改
你要遍歷的鏈表里面的元素有: 2 10 4 5
六、單鏈表的C語(yǔ)言代碼實(shí)現(xiàn)
#include <stdio.h>
typedef struct N
{
int element;
struct N *next;
}Node;
// 1、創(chuàng)建節(jié)點(diǎn)
Node *createNode(int num)
{
Node *node;
node = (Node *)malloc(sizeof(Node));
node->element = num;
node->next = NULL;
return node;
}
// 2、創(chuàng)建鏈表
Node *createSingleLinkList(Node *node)
{
Node *head = node;
return head;
}
// 3、獲取鏈表長(zhǎng)度
int getlength(Node *head)
{
if (head == NULL)
{
return 0;
}
int count = 1;
Node *current = head;
while (current->next != NULL)
{
count++;
current = current->next;
}
return count;
}
// 4、頭部插入
Node * add(Node *head, Node *node)
{
if(head == NULL)
{
head = node;
return head;
}
else
{
node->next = head;
head = node;
return head;
}
}
// 5、尾部插入
Node * append(Node *head,Node *node)
{
Node *current = head;
if (current->next == NULL)
{
add(head, node);
}
else
{
int len = getlength(head);
for (int i = 0; i<len-1; i++)
{
current = current->next;
}
current->next = node;
}
return head;
}
// 6、按下標(biāo)插入節(jié)點(diǎn)
Node * insert(Node *head,Node *node,int index)
{
int len = getlength(head);
if (index<=0||index>len+1)
{
printf("你要插入的位置不對(duì)，請(qǐng)重現(xiàn)選擇位置");
}
Node *current = head;
if (index == 1)
{
head = add(head, node);
}
else if (index == 2)
{
node->next = head->next;
head->next = node;
}
else
{
for (int i = 1; i<index-1; i++)
{
current = current->next;
}
node->next = current->next;
current->next = node;
}
return head;
}
// 7、遍歷
void travel(Node *head)
{
int len = getlength(head);
printf("len = %d\n",len);
Node *current = head;
if (len == 0)
{
printf("你要遍歷的鏈表沒有數(shù)據(jù)\n");
}
else
{
printf("你要遍歷的鏈表里面的元素有: ");
for (int i = 0; i<len; i++)
{
printf("%d ",current->element);
current = current->next;
}
printf("\n");
}
}
// 8、根據(jù)索引刪除
Node * delect(Node *head,int index)
{
int len = getlength(head);
if (index<=0||index>len)
{
printf("你輸入的下標(biāo)不對(duì)，請(qǐng)重新輸入");
return head;
}
else
{
if (index == 1)
{
head = head->next;
}
else if (index == 2)
{
head->next = head->next->next;
}
else
{
Node *current = head;
for (int i = 1; i<index-1; i++)
{
current = current->next;
}
current->next = current->next->next;
}
}
return head;
}
// 9、查找是否包含，并返回下標(biāo)
void isContain(Node *head,int num)
{
int contain = 0;
Node *current = head;
int len = getlength(head);
for (int i = 0; i<len; i++)
{
if (current->element == num)
{
printf("%d在鏈表中的%d處\n",num,i+1);
contain = 1;
}
current = current->next;
}
if (contain == 0)
{
printf("%d不在鏈表中\(zhòng)n",num);
}
}
// 10、根據(jù)下標(biāo)找節(jié)點(diǎn)
Node *searchByIndex(Node *head , int index)
{
int len = getlength(head);
Node *current = head;
if (index<=0||index>len)
{
printf("你輸入的下標(biāo)不對(duì)，請(qǐng)重新輸入");
return head;
}
else
{
for (int i = 0; i<index-1; i++)
{
current = current->next;
}
return current;
}
}
// 11、根據(jù)下標(biāo)修改節(jié)點(diǎn)的值
void modifyByIndex(Node *head,int index,int num)
{
int len = getlength(head);
Node *current = head;
if (index<=0||index>len)
{
printf("你輸入的下標(biāo)不對(duì)，請(qǐng)重新輸入");
}
else
{
for (int i = 0; i<index-1; i++)
{
current = current->next;
}
current->element = num;
}
}
int main(int argc, const char * argv[])
{
printf("==========1、創(chuàng)建節(jié)點(diǎn)==========\n");
Node * node1 = createNode(1);
printf("==========2、創(chuàng)建單鏈表==========\n");
Node * head = createSingleLinkList(node1);
travel(head);
printf("==========3、驗(yàn)證頭插==========\n");
Node *node2 = createNode(0);
head = add(head, node2);
travel(head);
Node *node3 = createNode(2);
head = add(head, node3);
travel(head);
printf("==========4、驗(yàn)證尾插==========\n");
Node *node4 = createNode(4);
head = append(head,node4);
travel(head);
Node *node5 = createNode(5);
head = append(head,node5);
travel(head);
printf("==========5、驗(yàn)證按下標(biāo)插入==========\n");
Node *node6 = createNode(6);
head = insert(head, node6, 1);
travel(head);
printf("==========6、驗(yàn)證按下標(biāo)刪除==========\n");
head = delect(head, 2);
travel(head);
printf("==========7、驗(yàn)證是否包含==========\n");
isContain(head, 8);
printf("==========8、驗(yàn)證根據(jù)下標(biāo)找節(jié)點(diǎn)==========\n");
Node *n = searchByIndex(head, 1);
printf("第一個(gè)節(jié)點(diǎn)是%d\n",n->element);
printf("==========9、驗(yàn)證根據(jù)下標(biāo)修改==========\n");
modifyByIndex
(head, 3, 9);
travel(head);
return 0;
}
運(yùn)行結(jié)果為：
==========1、創(chuàng)建節(jié)點(diǎn)==========
==========2、創(chuàng)建單鏈表==========
len = 1
你要遍歷的鏈表里面的元素有: 1
==========3、驗(yàn)證頭插==========
len = 2
你要遍歷的鏈表里面的元素有: 0 1
len = 3
你要遍歷的鏈表里面的元素有: 2 0 1
==========4、驗(yàn)證尾插==========
len = 4
你要遍歷的鏈表里面的元素有: 2 0 1 4
len = 5
你要遍歷的鏈表里面的元素有: 2 0 1 4 5
==========5、驗(yàn)證按下標(biāo)插入==========
len = 6
你要遍歷的鏈表里面的元素有: 6 2 0 1 4 5
==========6、驗(yàn)證按下標(biāo)刪除==========
len = 5
你要遍歷的鏈表里面的元素有: 6 0 1 4 5
==========7、驗(yàn)證是否包含==========
8不在鏈表中
==========8、驗(yàn)證根據(jù)下標(biāo)找節(jié)點(diǎn)==========
第一個(gè)節(jié)點(diǎn)是6
==========9、驗(yàn)證根據(jù)下標(biāo)修改==========
len = 5
你要遍歷的鏈表里面的元素有: 6 0 9 4 5
總結(jié)
以上所述是小編給大家介紹的python算法與數(shù)據(jù)結(jié)構(gòu)之單鏈表的實(shí)現(xiàn)代碼 ,希望對(duì)大家有所幫助，如果大家有任何疑問(wèn)請(qǐng)給我留言，小編會(huì)及時(shí)回復(fù)大家的。在此也非常感謝大家對(duì)腳本之家網(wǎng)站的支持！
如果你覺得本文對(duì)你有幫助，歡迎轉(zhuǎn)載，煩請(qǐng)注明出處，謝謝！
- python實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)中雙向循環(huán)鏈表操作的示例
- 基于python實(shí)現(xiàn)模擬數(shù)據(jù)結(jié)構(gòu)模型
- Python 實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)-堆棧和隊(duì)列的操作方法
- Python 實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)-循環(huán)隊(duì)列的操作方法
- Python 實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)中的的棧隊(duì)列
- 用python實(shí)現(xiàn)各種數(shù)據(jù)結(jié)構(gòu)
相關(guān)文章
這篇文章主要介紹了python實(shí)現(xiàn)串口通信的示例代碼，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-02-02
使用 Python 實(shí)現(xiàn)微信公眾號(hào)粉絲遷移流程
近日，因公司業(yè)務(wù)需要，需將原兩個(gè)公眾號(hào)合并為一個(gè)，即要將其中一個(gè)公眾號(hào)（主要是粉絲）遷移到另一個(gè)公眾號(hào)。這篇文章主要介紹了使用 Python 實(shí)現(xiàn)微信公眾號(hào)粉絲遷移,需要的朋友可以參考下2018-01-01
這篇文章主要介紹了flask框架jinja2模板與模板繼承,結(jié)合實(shí)例形式分析了flask框架jinja2模板的基本用法與模板繼承相關(guān)實(shí)現(xiàn)技巧,需要的朋友可以參考下2019-08-08
大家好，本篇文章主要講的是用Python生成會(huì)跳舞的美女，感興趣的同學(xué)趕快來(lái)看一看吧，對(duì)你有幫助的話記得收藏一下2022-01-01
TensorFlow實(shí)現(xiàn)非線性支持向量機(jī)的實(shí)現(xiàn)方法
本篇文章主要介紹了TensorFlow實(shí)現(xiàn)非線性支持向量機(jī)的實(shí)現(xiàn)方法，小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2018-04-04
Pytorch中關(guān)于nn.Conv2d()參數(shù)的使用
這篇文章主要介紹了Pytorch中關(guān)于nn.Conv2d()參數(shù)的使用，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2023-06-06
Python實(shí)現(xiàn)解析yaml配置文件的示例詳解
在開發(fā)過(guò)程中，配置文件是少不了的，而且配置文件是有專門的格式的，比如：ini，yaml，toml等等。本文帶大家來(lái)看看Python如何解析yaml文件，它的表達(dá)能力相比?ini?更加的強(qiáng)大，需要的可以參考一下2022-09-09
Python結(jié)合OpenCV和Pyzbar實(shí)現(xiàn)實(shí)時(shí)攝像頭識(shí)別二維碼
這篇文章主要為大家詳細(xì)介紹了如何使用Python編程語(yǔ)言結(jié)合OpenCV和Pyzbar庫(kù)來(lái)實(shí)時(shí)攝像頭識(shí)別二維碼,文中的示例代碼講解詳細(xì),需要的可以參考下2024-01-01
python+matplotlib繪制餅圖散點(diǎn)圖實(shí)例代碼
這篇文章主要介紹了python+matplotlib繪制餅圖散點(diǎn)圖實(shí)例代碼，本實(shí)例是官網(wǎng)的一個(gè)實(shí)例，不過(guò)也很簡(jiǎn)單，大家可以參考下2018-01-01
Tensorflow實(shí)現(xiàn)在訓(xùn)練好的模型上進(jìn)行測(cè)試
今天小編就為大家分享一篇Tensorflow實(shí)現(xiàn)在訓(xùn)練好的模型上進(jìn)行測(cè)試，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2020-01-01