今天看了一下数据结构的书，发现其实数据结构没有几种，线性表，数组，字符串，队列和栈，等等，其实是一回事，然后就是树结构，图结构。数据结构的理论并不难，主要是要自己写一下这些数据结构以及对应的基本的操作方法，这样就能够更快的提高。
这一篇blog写一下线性表。
线性表：分为顺序表和链表
一、顺序表
顺序表就是相对于表中的数据，地址也是顺序的，所以可以随机存取。但是在操作插入和删除元素的时候，由于要满足地址的连续性，所以要移动很多的元素位置，因此，插入或者删除一个顺序表的元素的时间复杂度是o(n)。很多时候，在对顺序表做合并的时候，需要先对表中的元素进行排序，然后再进行处理，这样可以避免每次都从头进行查询。
二、链表
链表就失去了顺序表的随机存取特点，即每次从中取一个元素都要从头开始找，这样耗费了一些时间，时间复杂度为o(n)；但是在做插入和删除，以及两个链表合并的时候，就方便了很多，只需要做一点指针修改就可以了。
链表中的每一个元素节点都包含了数据部分和下一个节点的指针。一般在链表的头部附设一个头结点，而且头结点一般不存储数据，而是存放一些长度等附加信息，或者不存储。
在很多语言中没有指针这一概念，而有数组的概念，比如java和python，java中的数组还要求定义数组的类型，也就是说必须都是同一类型的数据，而python则没有要求，所以python的list更贴近链表的真正含义。这种用数组描述的链表叫做静态链表。使用静态链表来描述链表对此类语言要方便很多了，本身这些语言都提供了内置类来处理链表。
除此之外，还有循环链表，双向链表（解决了无法向前搜索的问题，但是在修改指针的时候需要有更多的操作）。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
|
# -*- 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()
|
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持脚本之家。
原文链接：https://blog.csdn.net/dongrixinyu/article/details/78618971