STRUKTUR DATA - HASHING
NAMA: MOH.SABHAN
NIM: 160411100078
MAPEL: STRUKTUR DATA
- A. HASHING
menunjukkan
tabel hash dengan ukuran \ (m = 11 \) . Dengan kata lain,
ada m slot dalam tabel, diberi nama 0 sampai 10.
Pemetaan antara item
dan slot tempat item tersebut berada dalam tabel hash disebut fungsi
hash. Fungsi hash akan
mengambil barang apapun dalam koleksi dan mengembalikan bilangan bulat di
kisaran nama slot, antara 0 dan m -1. Asumsikan bahwa
kita memiliki kumpulan item integer 54, 26, 93, 17, 77, dan 31. Fungsi hash
pertama kita, kadang-kadang disebut sebagai "metode sisa," hanya
mengambil item dan membaginya dengan ukuran tabel, kembali Sisanya sebagai
nilai hashnya ( \ (h (item) = item \% 11 \) ). Tabel 4 memberikan
semua nilai hash untuk item contoh kami. Perhatikan bahwa metode sisa ini
(modulo aritmatika) biasanya akan hadir dalam beberapa bentuk dalam semua
fungsi hash, karena hasilnya harus berada dalam kisaran nama slot.
Barang
|
Nilai Hash
|
54
|
10
|
26
|
4
|
93
|
5
|
17
|
6
|
77
|
0
|
31
|
9
|
Setelah nilai hash
dihitung, kita dapat memasukkan setiap item ke dalam tabel hash pada posisi
yang ditunjuk seperti yang ditunjukkan pada Gambar 5 . Perhatikan
bahwa 6 dari 11 slot sekarang ditempati. Ini disebut sebagai faktor
beban , dan biasanya dilambangkan dengan \ (\ lambda = \ frac
{numberofitems} {tablesize} \) . Untuk contoh ini, \ (\ lambda =
\ frac {6} {11} \) .
Sekarang ketika kita
ingin mencari item, kita cukup menggunakan fungsi hash untuk menghitung nama
slot untuk item tersebut dan kemudian memeriksa tabel hash untuk melihat apakah
ada. Operasi pencarian ini adalah \ (O (1) \) , karena jumlah
waktu yang konstan diperlukan untuk menghitung nilai hash dan kemudian
mengindeks tabel hash di lokasi tersebut. Jika semuanya ada dimana
seharusnya, kita telah menemukan algoritma pencarian waktu yang konstan.
Anda mungkin sudah
bisa melihat bahwa teknik ini akan bekerja hanya jika setiap item memetakan ke
lokasi unik di tabel hash. Misalnya, jika item 44 adalah item berikutnya
dalam koleksi kami, itu akan memiliki nilai hash 0 ( \ (44 \% 11 == 0 \) ). Karena 77 juga memiliki nilai hash 0, kita akan
memiliki masalah. Menurut fungsi hash, dua atau lebih item perlu
berada di slot yang sama. Ini disebut sebagai tabrakan (ini
mungkin juga disebut "bentrokan"). Jelas, tabrakan menciptakan
masalah bagi teknik hashing. Kita akan membahasnya secara rinci nanti.
Resolusi
Tabrakan
Kita sekarang kembali
ke masalah tabrakan. Ketika dua item hash ke slot yang sama, kita harus
memiliki metode sistematis untuk menempatkan item kedua pada tabel hash. Proses
ini disebut collision resolution . Seperti yang telah
kita nyatakan sebelumnya, jika fungsi hash itu sempurna, tabrakan tidak akan
pernah terjadi. Namun, karena ini seringkali tidak memungkinkan, resolusi
tabrakan menjadi bagian yang sangat penting dari hashing.
Salah satu metode
untuk menyelesaikan tabrakan melihat ke dalam tabel hash dan mencoba menemukan
slot terbuka lain untuk menahan barang yang menyebabkan tabrakan. Cara
sederhana untuk melakukan ini adalah dengan memulai pada posisi nilai hash asli
dan kemudian bergerak secara berurutan melalui slot sampai kita menemukan slot
pertama yang kosong. Perhatikan bahwa kita mungkin perlu kembali ke slot
pertama (sirkular) untuk menutupi seluruh tabel hash. Proses resolusi
tabrakan ini disebut sebagai open addressing karena ia mencoba
menemukan slot atau alamat terbuka berikutnya di tabel hash. Dengan secara
sistematis mengunjungi setiap slot satu per satu, kami melakukan teknik
pengalamatan terbuka yang disebut linear probing .
Gambar 8 menunjukkan
serangkaian item integer yang diperluas berdasarkan fungsi hash metode sisa
sederhana (54,26,93,17,77,31,44,55,20). Tabel 4 di atas
menunjukkan nilai hash untuk item asli. Gambar 5 menunjukkan
isi aslinya. Saat kita mencoba menempatkan 44 pada slot 0, tabrakan
terjadi. Di bawah linear probing, kita melihat secara berurutan, slot
dengan slot, sampai kita menemukan posisi terbuka. Dalam hal ini, kita
menemukan slot 1.
Sekali lagi, 55 harus
masuk slot 0 tapi harus ditempatkan di slot 2 karena ini adalah posisi terbuka
berikutnya. Nilai akhir dari 20 hash ke slot 9. Karena slot 9 sudah penuh,
kita mulai melakukan probing linier. Kami mengunjungi slot 10, 0, 1, dan
2, dan akhirnya menemukan slot kosong pada posisi 3.
Setelah kita membuat
tabel hash dengan menggunakan pengalamatan terbuka dan penyelidikan linier,
penting bagi kita untuk menggunakan metode yang sama untuk mencari barang. Asumsikan
kita ingin melihat item 93. Ketika kita menghitung nilai hash, kita akan
mendapatkan 5. Melihat di slot 5 menunjukkan 93, dan kita dapat mengembalikan True . Bagaimana jika kita mencari 20? Sekarang nilai
hash adalah 9, dan slot 9 saat ini memegang 31. Kita tidak bisa begitu saja
mengembalikan False karena kita tahu bahwa mungkin ada
tabrakan. Kita sekarang terpaksa melakukan pencarian sekuensial, mulai
dari posisi 10, melihat sampai kita menemukan item 20 atau kita menemukan slot
kosong.
Kerugian untuk
menyelidik linier adalah kecenderungan pengelompokan ; Item
menjadi berkerumun di meja. Ini berarti bahwa jika banyak tabrakan terjadi
pada nilai hash yang sama, sejumlah slot di sekitarnya akan diisi oleh resolusi
probing linier. Ini akan berdampak pada item lain yang sedang dimasukkan,
seperti yang kita lihat saat kita mencoba menambahkan item 20 di atas. Sekelompok
nilai hashing ke 0 harus dilewati sampai akhirnya menemukan posisi terbuka. Cluster
ini ditunjukkan pada Gambar 9 .
Salah satu cara untuk
mengatasi clustering adalah dengan memperluas teknik probing linier sehingga
alih-alih mencari secara berurutan untuk slot terbuka berikutnya, kita
melewatkan slot, sehingga lebih merata mendistribusikan barang-barang yang
menyebabkan tabrakan. Hal ini berpotensi mengurangi pengelompokan yang
terjadi. Gambar 10 menunjukkan
item saat resolusi tabrakan dilakukan dengan probe "plus 3". Ini
berarti sekali tabrakan terjadi, kita akan melihat setiap slot ketiga sampai
kita menemukan yang kosong.
Nama umum untuk proses
mencari slot lain setelah tabrakan mengulangi . Dengan
solusi linear sederhana, fungsi pengulangan adalah \ (newhashvalue =
rehash (oldhashvalue) \) di mana \ (rehash (pos) = (pos + 1) \%
sizeoftable \) . Pengulangan "plus 3" dapat
didefinisikan sebagai \ (rehash (pos) = (pos + 3) \% sizeoftable \) . Secara
umum, \ (rehash (pos) = (pos + skip) \% sizeoftable \) . Penting
untuk dicatat bahwa ukuran "skip" harus sedemikian rupa sehingga
semua slot dalam tabel pada akhirnya akan dikunjungi. Jika tidak, bagian
dari tabel tidak akan terpakai. Untuk memastikan hal ini, sering
disarankan agar ukuran meja menjadi bilangan prima. Inilah alasan mengapa
kita menggunakan 11 dalam contoh kita.
Variasi dari ide
probing linier disebut kuadratic probing . Alih-alih
menggunakan nilai "lewati" konstan, kita menggunakan fungsi
pengulangan yang meningkatkan nilai hash sebesar 1, 3, 5, 7, 9, dan seterusnya. Ini
berarti bahwa jika nilai hash pertama adalah h , nilai
berturut-turut adalah \ (h + 1 \) , \ (h + 4 \) , \ (h
+ 9 \) , \ (h + 16 \) , dan seterusnya . Dengan kata lain,
kuadrat menyelidik menggunakan lompatan yang terdiri dari kotak sempurna yang
berurutan. Gambar 11 menunjukkan
nilai contoh kita setelah ditempatkan menggunakan teknik ini.
Metode alternatif
untuk menangani masalah tabrakan adalah membiarkan setiap slot menahan
referensi ke koleksi (atau rantai) item. Chaining memungkinkan
banyak item ada di lokasi yang sama di tabel hash. Saat tabrakan terjadi,
item masih ditempatkan di slot tabel hash yang tepat. Karena semakin
banyak item hash ke lokasi yang sama, sulitnya mencari item dalam koleksi
meningkat. Gambar 12 menunjukkan
item karena ditambahkan ke tabel hash yang menggunakan chaining untuk
menyelesaikan tabrakan
Ketika kita ingin
mencari item, kita menggunakan fungsi hash untuk menghasilkan slot di tempat
yang seharusnya berada. Karena setiap slot memegang koleksi, kami
menggunakan teknik pencarian untuk memutuskan apakah item itu ada. Keuntungannya
adalah rata-rata ada banyak item di setiap slot, jadi pencariannya mungkin
lebih efisien. Kita akan melihat analisis untuk hashing pada akhir bagian
ini.
Algoritma
table =
[None] * 10
def
hash(x):
return x % 10
def
insert(table,key,value):
index = hash(key)
if table[index] == None:
table[index] = value
else :
collusion=index
found = False
ind=(collusion+1)% 10
if ind > len(table)-1:
Ind = 0
while (ind<=len(table)-1) and
not(found):
if table[ind]== None:
found=True
table[ind]=value
ind=(ind+1)% 10
def
cari(Data, data):
list1=[]
found = False
for i in range(len(Data)):
if Data[i] == data:
found = True
list1.append(i)
if found:
return ("Data berada : " +
str(list1))
else:
return("Tidak ada")
x = int(input("Data
yang diinginkan : "))
while
0<x:
y = int(input("Masukan data : "))
insert(table,y,y)
print(table)
x=x-1
z =
int(input("Data yang ingin dicari : "))
print(cari(table,z))
Quadratic Probing
table =
[None] * 10
def
hash(x):
return x % 10
def
insert(table,key,value):
index = hash(key)
if table[index] == None:
table[index] = value
else:
collusion=index
found = False
i=1
ind = collusion+1
if ind > len(table)-1:
ind = 0
while (ind<=len(table)-1) and
not(found):
if table[ind]== None:
found=True
table[ind]=value
ind = (collusion+(i*i)) % 10
i=i+1
def
cari(Data, data):
list1=[]
found = False
for i in range(len(Data)):
if Data[i] == data:
found = True
list1.append(i)
if found:
return ("Data berada : " +
str(list1))
else:
return("Tidak ada")
x =
int(input("Data yang diinginkan : "))
while
0<x:
y = int(input("Masukan data : "))
insert(table,y,y)
print(table)
x=x-1
z =
int(input("Data yang ingin dicari : "))
print(cari(table,z))
Chaining
table = [
[] for _ in range(10)]
def
hash(x):
return x % 10
def
insert(table,key,value):
table[hash(key)].append(value)
def
cari(Data, data):
list1=[]
found = False
for i in range(len(Data)):
if Data[i] == data:
found = True
list1.append(i)
if found:
return ("Data berada : " +
str(list1))
else:
return("Tidak ada")
x =
int(input("Data yang diinginkan : "))
while
0<x:
y = int(input("Masukan data : "))
insert(table,y,y)
print(table)
x=x-1
z =
int(input("Data yang ingin dicari : "))
print(cari(table,z))
- B. LINKKED LIST
Nodes
Self-referential
objects (object yang mereferensikan dirinya sendiri) yang disebut nodes,
yang dihubungkan dengan links, membentuk kata “linked” list.
Linked
List ( LL )
Adalah
koleksi data item yang tersusun dalam sebuah barisan secara linear,
dengan penyisipan dan pemindahan dapat dilakukan dalam semua tempat di LL
tersebut.
Single
Linked List
Adalah
sebuah LL yang menggunakan sebuah variabel pointer saja untuk menyimpan banyak
data dengan metode LL, suatu daftar isi yang saling berhubungan.
Ilustrasi
single LL:
Pada
gambar di atas, data terletak pada sebuah lokasi dalam sebuah memory, tempat
yang disediakan memory untuk menyimpan data disebut node ? simpul, setiap node
memiliki pointer ( penunjuk ) yang menunjuk ke node berikutnya sehingga
terbentuk suatu untaian yang disebut single LL.
Bila
dalam single LL pointer hanya dapat bergerak ke satu arah saja, maju / mundur,
kanan / kiri, sehingga pencarian datanya juga hanya satu arah saja.
Double
Linked List
Dalam
double LL ( Linked List berpointer ganda ) dapat mengatasi kelemahan-kelemahan
single LL tersebut.
Ilustrasi
double LL:
·
UNORDERST: menghapus sebuah list
yang tidak ada data.
class
Node:
def __init__(self,initdata):
self.data = initdata
self.next = None
def getData(self):
return self.data
def getNext(self):
return self.next
def setData(self,newdata):
self.data = newdata
def setNext(self,newnext):
self.next = newnext
class
UnorderedList:
def __init__(self):
self.head = None
def isEmpty(self):
return self.head == None
def add(self,item):
temp = Node(item)
temp.setNext(self.head)
self.head = temp
def show(self):
current = self.head
print('head ->',end='')
while current != None:
print(current.getData(),
"->",end='')
current= current.getNext()
print(None)
def size(self):
current = self.head
count = 0
while current != None:
count = count + 1
current = current.getNext()
return count
def search(self,item):
current = self.head
found = False
stop = False
while current != None and not found and
not stop:
if current.getData() == item:
found = True
else:
if current.getData() > item:
stop = True
else:
current = current.getNext()
return(found)
def remove(self,item):
current = self.head
previous = None
found = False
stop = False
while not found and current != None:
if current.getData() == item:
found = True
print("data yang dihapus
",item)
else:
previous = current
if current != None:
current = current.getNext()
elif not found:
Stop=True
if previous == None:
if self.head == None:
stop= True
else:
self.head = current.getNext()
else:
if current != None:
previous.setNext(current.getNext())
if current is None:
print("Data not in list")
if current == self.head and previous ==
None:
print("list null")
print("========================================")
print("Unorderlist")
print("========================================")
mylist
= UnorderedList()
mylist.add(31)
mylist.add(77)
mylist.add(17)
mylist.show()
mylist.remove(31)
mylist.show()
mylist.remove(17)
mylist.show()
mylist.remove(77)
mylist.show()
mylist.remove(12)
mylist.show()
- C. TREE DAN GRAPH
BINARY
TREE
Pohon biner adalah pohon dengan syarat bahwa tiap node hanya
memiliki boleh maksimal dua subtree dan kedua subtree tersebut harus terpisah.
Sesuai dengan definisi tersebut, maka tiap node dalam binary tree hanya boleh
memiliki paling banyak dua anak/child.
Ilustrasi
Algoritma
class Node(object):
|
def __init__(self, data):
|
self.left = None
|
self.right = None
|
self.data = data
|
def __repr__(self):
|
return "Node With Data:
%d" % self.data
|
def insert(self, data):
|
if data < self.data:
|
if self.left is None:
|
self.left = Node(data)
|
else:
|
self.left.insert(data)
|
else:
|
if self.right is None:
|
self.right = Node(data)
|
else:
|
self.right.insert(data)
|
def lookup(self, data,
parent=None):
|
if data < self.data:
|
if self.left is None:
|
return None, None
|
return self.left.lookup(data,
self)
|
elif data > self.data:
|
if self.right is None:
|
return None, None
|
return self.right.lookup(data,
self)
|
else:
|
return self, parent
|
def children_count(self):
|
count = 0
|
if self.left:
|
count += 1
|
if self.right:
|
count += 1
|
return count
|
def descendant_count(self):
|
count = 0
|
if self.left:
|
count += 1 +
self.left.descendant_count()
|
if self.right:
|
count += 1 +
self.right.descendant_count()
|
return count
|
def delete(self, data):
|
node, parent = self.lookup(data)
|
if node:
|
children_count =
node.children_count()
|
if children_count == 0:
|
# If node has no children then
remove it
|
if parent.left is node:
|
parent.left = None
|
else:
|
parent.right = None
|
del node
|
elif children_count == 1:
|
if node.left:
|
child = node.left
|
else:
|
child = node.right
|
if parent:
|
if parent.left is node:
|
parent.left = child
|
else:
|
parent.right = child
|
del node
|
else:
|
parent = node
|
successor = node.right
|
while successor.left:
|
parent = successor
|
successor = successor.left
|
node.data = successor.data
|
if parent.left == successor:
|
parent.left = successor.right
|
else:
|
parent.right = successor.right
|
def inorder_print(self):
|
if self.left:
|
self.left.print_tree()
|
print self.data
|
if self.right:
|
self.right.print_tree()
|
def print_each_level(self):
|
# Start off with root node
|
thislevel = [self]
|
while thislevel:
|
nextlevel = list()
|
for node in thislevel:
|
print node.data
|
if node.left:
nextlevel.append(node.left)
|
if node.right:
nextlevel.append(node.right)
|
Print
|
thislevel = nextlevel
|
def compare_trees(self, node):
|
if node is None:
|
return False
|
if self.data != node.data:
|
return False
|
res = True
|
if self.left is None:
|
if node.left:
|
return False
|
else:
|
res =
self.left.compare_trees(node.left)
|
if self.right is None:
|
if node.right:
|
return False
|
else:
|
res =
self.right.compare_trees(node.right)
|
return res
|
def tree_data(self):
|
|
stack = []
|
node = self
|
while stack or node:
|
if node:
|
stack.append(node)
|
node = node.left
|
else:
|
node = stack.pop()
|
yield node.data
|
node = node.right
|
root = Node(8)
|
root.insert(3)
|
root.insert(10)
|
root.insert(1)
|
root.insert(6)
|
root.insert(4)
|
root.insert(7)
|
root.insert(14)
|
root.insert(13)
|
import
pdb; pdb.set_trace()
ALGORITMA BELAJAR
class Node:
def __init__(self,initdata):
self.data = initdata
self.next = None
def getData(self):
return self.data
def getNext(self):
return self.next
def setData(self,newdata):
self.data = newdata
def setNext(self,newnext):
self.next = newnext
class UnorderedList:
def __init__(self):
self.head = None
def isEmpty(self):
return self.head == None
def add(self,item):
temp = Node(item)
temp.setNext(self.head)
self.head = temp
def show(self):
current = self.head
print ('Head ->',end=' ')
while current != None:
print (current.getData(), "->",end=' ')
current = current.getNext()
print (None)
def size(self):
current = self.head
count = 0
while current != None:
count = count + 1
current = current.getNext()
return count
def search(self,item):
current = self.head
found = False
while current != None and not found:
if current.getData() == item:
found = True
else:
current = current.getNext()
return found
def remove(self,item):
current = self.head
previous = None
found = False
while not found:
if current.getData() == item:
found = True
print('data yang di pindah adalah :',item)
else:
previous = current
current = current.getNext()
if previous == None:
self.head = current.getNext()
else:
if current != None :
previous.setNext(current.getNext())
if current is None :
print('Data tidak ada')
mylist = UnorderedList()
a = []
q = []
print('Menginputkan ke table Hashing')
print('======================================')
for i in range(0,3):
c = input('Memasukkan angka ke Unorderlist : ')
d = int(c)
mylist.add(d)
a.append(d)
mylist.show()
f = 'Head -> '+str(a[0])+' -> '+str(a[1])+' -> '+str(a[2])+' -> None'
d = 'Head -> '+str(a[2])+' -> '+str(a[0])+' -> None'
print('===========================================================')
table = [ [] for _ in range(10)]
def hash(x):
return x % 10
def insert(table,key,value):
table[hash(key)].append(value)
insert(table,8,f)
insert(table,4,4)
insert(table,3,3)
insert(table,4,14)
insert(table,3,21)
insert(table,3,23)
insert(table,9,9)
insert(table,12,d)
print (table)
ALGORITMA BELAJAR
class Node:
def __init__(self,initdata):
self.data = initdata
self.next = None
def getData(self):
return self.data
def getNext(self):
return self.next
def setData(self,newdata):
self.data = newdata
def setNext(self,newnext):
self.next = newnext
class UnorderedList:
def __init__(self):
self.head = None
def isEmpty(self):
return self.head == None
def add(self,item):
temp = Node(item)
temp.setNext(self.head)
self.head = temp
def show(self):
current = self.head
print ('Head ->',end=' ')
while current != None:
print (current.getData(), "->",end=' ')
current = current.getNext()
print (None)
def size(self):
current = self.head
count = 0
while current != None:
count = count + 1
current = current.getNext()
return count
def search(self,item):
current = self.head
found = False
while current != None and not found:
if current.getData() == item:
found = True
else:
current = current.getNext()
return found
def remove(self,item):
current = self.head
previous = None
found = False
while not found:
if current.getData() == item:
found = True
print('data yang di pindah adalah :',item)
else:
previous = current
current = current.getNext()
if previous == None:
self.head = current.getNext()
else:
if current != None :
previous.setNext(current.getNext())
if current is None :
print('Data tidak ada')
mylist = UnorderedList()
a = []
q = []
print('Menginputkan ke table Hashing')
print('======================================')
for i in range(0,3):
c = input('Memasukkan angka ke Unorderlist : ')
d = int(c)
mylist.add(d)
a.append(d)
mylist.show()
f = 'Head -> '+str(a[0])+' -> '+str(a[1])+' -> '+str(a[2])+' -> None'
d = 'Head -> '+str(a[2])+' -> '+str(a[0])+' -> None'
print('===========================================================')
table = [ [] for _ in range(10)]
def hash(x):
return x % 10
def insert(table,key,value):
table[hash(key)].append(value)
insert(table,8,f)
insert(table,4,4)
insert(table,3,3)
insert(table,4,14)
insert(table,3,21)
insert(table,3,23)
insert(table,9,9)
insert(table,12,d)
print (table)
ALGORITMA ORDER LIST
# Bisa menggunakan trinket untuk melihat hasilnya
class Node:
def __init__(self,initdata):
self.data = initdata
self.next = None
def getData(self):
return self.data
def getNext(self):
return self.next
def setData(self,newdata):
self.data = newdata
def setNext(self,newnext):
self.next = newnext
class OrderedList:
def __init__(self):
self.head = None
def search(self,item):
current = self.head
found = False
stop = False
while current != None and not found and not stop:
if current.getData() == item:
found = True
else:
if current.getData() > item:
stop = True
else:
current = current.getNext()
return found
def add(self,item):
current = self.head
previous = None
stop = False
while current != None and not stop:
if current.getData() > item:
stop = True
else:
previous = current
current = current.getNext()
temp = Node(item)
if previous == None:
temp.setNext(self.head)
self.head = temp
else:
temp.setNext(current)
previous.setNext(temp)
def isEmpty(self):
return self.head == None
def size(self):
current = self.head
count = 0
while current != None:
count = count + 1
current = current.getNext()
return count
def remove(self,item):
current = self.head
previous = None
found = False
while not found and current != None:
if current.getData() == item:
found = True
else:
previous = current
current = current.getNext()
if previous == None:
self.head = current.getNext()
else:
if current != None:
previous.setNext(current.getNext())
if current is None:
print("Data Tidak Ada DIdalam List")
def show(self):
current = self.head
print'Head->',
while current != None:
print current.getData(), "->",
current= current.getNext()
print None
mylist = OrderedList()
mylist.add(21)
mylist.add(77)
mylist.add(27)
mylist.add(83)
mylist.show()
mylist.remove(21)
mylist.show()
mylist.remove(20)
mylist.show()
mylist.remove(27)
mylist.show()
mylist.remove(83)
mylist.show()
ALGORITMA UNORDERLIST
# Bisa menggunakan trinket untuk melihat hasilnya
class Node:
def __init__(self,initdata):
self.data = initdata
self.next = None
def getData(self):
return self.data
def getNext(self):
return self.next
def setData(self,newdata):
self.data = newdata
def setNext(self,newnext):
self.next = newnext
class UnorderedList:
def __init__(self):
self.head = None
def show(self):
current = self.head
print 'Head ->',
while current != None:
print current.getData(), " -> ",
current = current.getNext()
print None
def isEmpty(self):
return self.head == None
def add(self,item):
temp = Node(item)
temp.setNext(self.head)
self.head = temp
def size(self):
current = self.head
count = 0
while current != None:
count = count + 1
current = current.getNext()
return count
def search(self,item):
current = self.head
found = False
while current != None and not found:
if current.getData() == item:
found = True
print('Data di dalam list broooo')
else:
current = current.getNext()
return found
def remove(self,item):
current = self.head
previous = None
found = False
while current != None and not found:
if current.getData() == item:
found = True
else:
previous = current
current = current.getNext()
if previous == None:
self.head = current.getNext()
else:
if current != None:
previous.setNext(current.getNext())
if current is None:
print("Tidak ada data")
mylist = UnorderedList()
mylist.add(33)
mylist.add(28)
mylist.add(17)
mylist.add(69)
mylist.remove(69)
mylist.show()
mylist.remove(10)
mylist.show()
mylist.remove(17)
mylist.show()
mylist.remove(28)
mylist.show()
mylist.remove(99)
mylist.show()
GRAPH
Grafik adalah
jaringan yang terdiri dari node yang dihubungkan oleh tepi atau busur. Dalam
grafik terarah, hubungan antara node memiliki arah, dan disebut busur; Dalam
grafik yang tidak berarah, koneksi tidak memiliki arah dan disebut tepi. Kami
terutama membahas grafik terarah. Algoritma dalam grafik termasuk menemukan
jalur antara dua simpul, menemukan jalur terpendek antara dua simpul,
menentukan siklus dalam grafik (sebuah siklus adalah jalur yang tidak kosong
dari simpul ke simpul itu sendiri), menemukan jalur yang mencapai semua simpul
(yang terkenal "Masalah salesman traveling"), dan seterusnya.
Terkadang simpul atau lengkungan grafik memiliki bobot atau biaya yang terkait
dengannya, dan kami tertarik untuk menemukan jalur yang paling murah.
Litelatur
Kode
graph = {'A': ['B', 'C','D'],
'B': ['A','E', 'D'],
'C': ['A','D','E'],
'D': ['A','B','C','E'],
'E': ['B','C','D']}
def find_all_shortest(data):
path = []
minSize=3
for i in
range(len(data)):
if
len(data[i])<minSize:
minSize = len(data[i])
listterpendek=[]
for i in
range(len(data)):
if
len(data[i])==minSize:
listterpendek.append(data[i])
print(str(data[i])+str(minSize-1)+" titik yang dikunjungi")
def find_all_longest(data):
path = []
minSize=3
for i in
range(len(data)):
if
len(data[i])<minSize:
minSize = len(data[i])-1
listterpendek=[]
for i in
range(len(data)):
if
len(data[i])-1==minSize:
listterpendek.append(data[i])
print(data[i],minSize," titik yang dikunjungi")
def find_all_paths(graph, start, end, path=[]):
path =
path + [start]
if
start == end:
return [path]
paths
= []
for
node in graph[start]:
if
node not in path:
newpaths = find_all_paths(graph, node, end, path)
for newpath in newpaths:
paths.append(newpath)
return
paths
data =find_all_paths(graph,'A','E')
print("==============terpendek=============")
print(find_all_shortest(data))
print("=========terpanjang=============")
print(find_all_longest(data))
ALGORITMA 2
graph = {'A': ['B', 'C','D'],
'B': ['C', 'D'],
'C': ['D','E'],
'D': ['C'],
'E': ['F'],
'F': ['D']}
print('from', '\tto')
for i in graph:
print (i, graph[i], sep='\t')
def find_path(graph, start, end, path=[]):
path = path + [start]
if start == end:
return path
if not start in graph:
return None
for node in graph[start]:
if node not in path:
print(start, end, node, path, sep='\t')
newpath = find_path(graph, node, end, path)
if newpath:
return newpath
return None
print(''); print ('start', 'end', 'node', 'path', sep='\t')
print('path : ', find_path(graph, 'A', 'D')); print('')
def find_all_paths(graph, start, end, path=[]):
path = path + [start]
if start == end:
return [path]
if not start in graph:
return []
paths = []
for node in graph[start]:
if node not in path:
print(start, end, node, path, sep='\t')
newpaths = find_all_paths(graph, node, end, path)
if node == end:
print(newpaths[0])
for newpath in newpaths:
paths.append(newpath)
return paths
print(''); print ('start', 'end', 'node', 'path', sep='\t')
print('all path : ', find_all_paths(graph, 'A', 'D')); print('')
def find_shortest_path(graph, start, end, path=[]):
path = path + [start]
if start == end:
return path
if not start in graph:
return None
shortest = None
for node in graph[start]:
if node not in path:
print(start, end, node, path, shortest, sep='\t')
newpath = find_shortest_path(graph, node, end, path)
if node == end:
print(newpath)
if newpath:
if not shortest or len(newpath) < len(shortest):
shortest = newpath
return shortest
print(''); print ('start', 'end', 'node', 'path', '\tshortest', sep='\t')
print('shortest : ', find_shortest_path(graph, 'A', 'D'))
graph = {'A': ['B', 'C','D'],
'B': ['C', 'D'],
'C': ['D','E'],
'D': ['C'],
'E': ['F'],
'F': ['D']}
print('from', '\tto')
for i in graph:
print (i, graph[i], sep='\t')
def find_path(graph, start, end, path=[]):
path = path + [start]
if start == end:
return path
if not start in graph:
return None
for node in graph[start]:
if node not in path:
print(start, end, node, path, sep='\t')
newpath = find_path(graph, node, end, path)
if newpath:
return newpath
return None
print(''); print ('start', 'end', 'node', 'path', sep='\t')
print('path : ', find_path(graph, 'A', 'D')); print('')
def find_all_paths(graph, start, end, path=[]):
path = path + [start]
if start == end:
return [path]
if not start in graph:
return []
paths = []
for node in graph[start]:
if node not in path:
print(start, end, node, path, sep='\t')
newpaths = find_all_paths(graph, node, end, path)
if node == end:
print(newpaths[0])
for newpath in newpaths:
paths.append(newpath)
return paths
print(''); print ('start', 'end', 'node', 'path', sep='\t')
print('all path : ', find_all_paths(graph, 'A', 'D')); print('')
def find_shortest_path(graph, start, end, path=[]):
path = path + [start]
if start == end:
return path
if not start in graph:
return None
shortest = None
for node in graph[start]:
if node not in path:
print(start, end, node, path, shortest, sep='\t')
newpath = find_shortest_path(graph, node, end, path)
if node == end:
print(newpath)
if newpath:
if not shortest or len(newpath) < len(shortest):
shortest = newpath
return shortest
print(''); print ('start', 'end', 'node', 'path', '\tshortest', sep='\t')
print('shortest : ', find_shortest_path(graph, 'A', 'D'))
Komentar
Posting Komentar