溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
今天看了一下數據結構的書，發現其實數據結構沒有幾種，線性表，數組，字符串，隊列和棧，等等，其實是一回事，然后就是樹結構，圖結構。數據結構的理論并不難，主要是要自己寫一下這些數據結構以及對應的基本的操作方法，這樣就能夠更快的提高。
這一篇blog寫一下線性表。
線性表：分為順序表和鏈表
一、順序表
順序表就是相對于表中的數據，地址也是順序的，所以可以隨機存取。但是在操作插入和刪除元素的時候，由于要滿足地址的連續性，所以要移動很多的元素位置，因此，插入或者刪除一個順序表的元素的時間復雜度是o(n)。很多時候，在對順序表做合并的時候，需要先對表中的元素進行排序，然后再進行處理，這樣可以避免每次都從頭進行查詢。
二、鏈表
鏈表就失去了順序表的隨機存取特點，即每次從中取一個元素都要從頭開始找，這樣耗費了一些時間，時間復雜度為o(n)；但是在做插入和刪除，以及兩個鏈表合并的時候，就方便了很多，只需要做一點指針修改就可以了。
鏈表中的每一個元素節點都包含了數據部分和下一個節點的指針。一般在鏈表的頭部附設一個頭結點，而且頭結點一般不存儲數據，而是存放一些長度等附加信息，或者不存儲。
在很多語言中沒有指針這一概念，而有數組的概念，比如java和python，java中的數組還要求定義數組的類型，也就是說必須都是同一類型的數據，而python則沒有要求，所以python的list更貼近鏈表的真正含義。這種用數組描述的鏈表叫做靜態鏈表。使用靜態鏈表來描述鏈表對此類語言要方便很多了，本身這些語言都提供了內置類來處理鏈表。
除此之外，還有循環鏈表，雙向鏈表（解決了無法向前搜索的問題，但是在修改指針的時候需要有更多的操作）。
# -*- coding=utf-8 -*-
# 這個例子是Python版本的單鏈表
class Node(object):
def __init__(self, value, next=0):
self.value = value
self.next = next # 指針
class LinkedList(object):
# 鏈表的數據結構
def __init__(self):
self.head = 0 # 頭部
def __getitem__(self, key):
if self.is_empty():
print 'Linked list is empty.'
return
elif key < 0 or key > self.get_length():
print 'The given key is wrong.'
return
else:
return self.get_elem(key)
def __setitem__(self, key, value):
if self.is_empty():
print 'Linked list is empty.'
return
elif key < 0 or key > self.get_length():
print 'The given key is wrong.'
return
else:
return self.set_elem(key, value)
def init_list(self, data): # 按列表給出 data
self.head = Node(data[0])
p = self.head # 指針指向頭結點
print p, self.head
for i in data[1:]:
p.next = Node(i) # 確定指針指向下一個結點
p = p.next # 指針滑動向下一個位置
print self.head.next.next
def get_length(self):
length = 0
p = self.head
while p != 0: # 0 值就是Node結點中默認的 0 值，表示下一個結點沒有了，即沒有為其賦值
length += 1
p = p.next
return length
def is_empty(self):
if self.head == 0:
return True
else:
return False
def insert_node(self, index, value):
if index < 0 or index > self.get_length():
print 'Can not insert node into the linked list.'
elif index == 0:
temp = self.head
self.head = Node(value, temp)
else:
p, post = self.head, self.head
for i in xrange(index):
post = p
p = p.next
temp = p
post.next = Node(value, temp)
def delete_node(self, index):
if index < 0 or index > self.get_length()-1:
print "Wrong index number to delete any node."
elif self.is_empty():
print "No node can be deleted."
elif index == 0:
temp = self.head
self.head = temp.next
elif index == self.get_length():
p = self.head
for i in xrange(self.get_length()-2):
p = p.next
p.next = 0
else:
p = self.head
for i in xrange(index-1):
p = p.next
p.next = p.next.next
def show_linked_list(self): # 打印鏈表中的所有元素
if self.is_empty():
print 'This is an empty linked list.'
else:
p, container = self.head, []
for _ in xrange(self.get_length()-1):
container.append(p.value)
p = p.next
container.append(p.value)
print container
def clear_linked_list(self): # 將鏈表置空
self.head = 0
def get_elem(self, index):
if self.is_empty():
print "The linked list is empty. Can not get element."
elif index < 0 or index > self.get_length()-1:
print "Wrong index number to get any element."
else:
p = self.head
for _ in xrange(index):
p = p.next
return p.value
def set_elem(self, index, value):
if self.is_empty():
print "The linked list is empty. Can not set element."
elif index < 0 or index > self.get_length()-1:
print "Wrong index number to set element."
else:
p = self.head
for _ in xrange(index):
p = p.next
p.value = value
def get_index(self, value):
p = self.head
for i in xrange(self.get_length()):
if p.value == value:
return i
else:
p = p.next
return -1
l = LinkedList()
print "The length of linked list now is: ", l.get_length()
print l.is_empty()
l.init_list([1, 5, 12, "fjd", 45, 999])
print "The length of linked list now is: ", l.get_length()
print l.is_empty()
l.insert_node(4, 100)
l.insert_node(6, "cecil")
l.show_linked_list()
print "The value of index 0 is: ", l.get_elem(0)
l.set_elem(0,1000)
l.show_linked_list()
print "the index of *** is: ", l.get_index(1009)
print "The length of linked list now is: ", l.get_length()
l.delete_node(3)
#l.clear_linked_list()
l.show_linked_list()
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持億速云。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
