# Python Data Structures - C1 Search

Python数据结构篇(1) 搜索

#### 搜索(或查找)总结

(1)顺序查找：O(n) (2)二分查找：O(lgn) (3)Hash查找：O(1)

1.reminder method：取余数（size=11，下图对11取余数，例如17取余数得到6）

2.folding method: 分组求和再取余数

3.mid-square method：平方值的中间两位数取余数

4.对于由字符的元素可以尝试使用ord函数来将字符串转换成一个有序的数值序列。在Python中ord函数可以得到对应字符的ASCII码值。将所有字符的码值累加再取余数。

From wiki

1.open address(开放寻址)：线性探测(linear probing)下一个位置，缺点是容易造成聚集现象(cluster)，解决聚集现象的办法是跳跃式地查找下一个空槽。数值的顺序：(54, 26, 93, 17, 77, 31, 44, 55, 20).

3.chain：利用链表链接起来

From wiki

From wiki

def sequential_search(a_list, item):
pos = 0
found = False
if a_list[pos] == item:
found = True
else:
pos = pos+1
return found

test_list = [1, 2, 32, 8, 17, 19, 42, 13, 0]
print(sequential_search(test_list, 3))
print(sequential_search(test_list, 13))

def binary_search(a_list, item):
first = 0
last = len(a_list) - 1
found = False
midpoint = (first + last) // 2
if a_list[midpoint] == item:
found = True
else:
if item < a_list[midpoint]:
last = midpoint - 1
else:
first = midpoint + 1
return found

test_list = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
print(binary_search(test_list, 3))
print(binary_search(test_list, 13))

class HashTable:
def __init__(self):
self.size = 11
self.slots = [None] * self.size
self.data = [None] * self.size

#put data in slot
def put_data_in_slot(self,key,data,slot):
if self.slots[slot] == None: # '==None' ? or  'is None' ?
self.slots[slot] = key
self.data[slot] = data
return True
else:
if self.slots[slot] == key: # not None
self.data[slot] = data #replace
return True
else:
return False

def put(self, key, data):
slot = self.hash_function(key, self.size);
result = self.put_data_in_slot(key,data,slot);
while not result:
slot = self.rehash(slot, self.size);
result=self.put_data_in_slot(key,data,slot);

#reminder method
def hash_function(self, key, size):
return key % size

#plus 1
def rehash(self, old_hash, size):
return (old_hash + 1) % size

def get(self, key):
start_slot = self.hash_function(key, len(self.slots))
data = None
stop = False
found = False
position = start_slot
if self.slots[position] == key:
found = True
data = self.data[position]
else:
position=self.rehash(position, len(self.slots))
if position == start_slot:
stop = True
return data

def __getitem__(self, key):
return self.get(key)

def __setitem__(self, key, data):
self.put(key, data)

if __name__ == '__main__':
table=HashTable();
table[54]='cat';
table[26]='dog';
table[93]='lion';
table[17]="tiger";
table[77]="bird";
table[44]="goat";
table[55]="pig";
table[20]="chicken";
print table.slots;
print table.data;

# [77, 44, 55, None, 26, 93, 17, None, None, 20, 54]
# ['bird', 'goat', 'pig', None, 'dog', 'lion', 'tiger', None, None, 'chicken', 'cat']

0 条评论

## 相关文章

2563

1164

1903

1451

2608

3394

### Numpy教程第2部分 - 数据分析的重要功能

【导读】Numpy是python数据分析和科学计算的核心软件包。 上次介绍了numpy的一些基础操作。例如如何创建一个array，如何提取array元素，重塑（...

4459

### JS魔法堂：彻底理解0.1 + 0.2 === 0.30000000000000004的背后

Brief　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　   一天有个朋友问我“JS中计算0.7 * 180怎么会等于125.9999999999...

3046

1600

### 2729:Blah数集

2729:Blah数集 查看 提交 统计 提问 总时间限制:3000ms内存限制:65536kB描述大数学家高斯小时候偶然间发现一种有趣的自然数集合Blah，对...

3144