資料結構與演算法–（鏈表，堆疊，佇列）

文章目錄

資料結構與演算法--（鏈表，堆疊，佇列）
鏈表
- 定義
- 單向鏈表
- - 功能:
  - - 1.頭部添加元素
    - 2.尾部添加元素
    - 3.指定位置添加元素
    - 4.洗掉節點
    - 5.查找節點是否存在
    - 6.判斷鏈表是否為空
    - 7.當前鏈表的長度
    - 8.遍歷鏈表
    - 全部代碼粘貼
- 雙向鏈表
- - 功能:
  - - 1.頭部添加元素
    - 2.尾部添加元素
    - 3.指定位置添加元素
    - 4.洗掉節點
    - 5.查找節點是否存在
    - 6.判斷鏈表是否為空
    - 7.當前鏈表的長度
    - 8.遍歷鏈表
    - 全部代碼粘貼
堆疊（stack）
- 堆疊的實作
佇列（queue）
- 佇列的實作

鏈表

定義

鏈表：是一種常見的資料結構，是一種線性表，不像順序表那樣連續存盤資料，而是在每個節點（資料存盤單元）里存放下一個節點的位置資訊（地址），

單向鏈表

單向鏈表也叫單鏈表，是鏈表中最簡單的一種形式，它的每個節點包含兩個域，一個資訊域(元素域)和一個鏈接域，這個鏈接指向鏈表中的下一個節點，而最后一個節點的鏈接域則指向一個空值，

功能:

1.頭部添加元素

    def add(self,item):
        node = Node(item)
        # 將新節點的鏈接域next指向頭結點
        node.next=self.__head
        #將鏈表頭__head指向新節點
        self.__head = node

2.尾部添加元素

    #尾部追加
    def append(self,item):
        node = Node(item)
        curNode = self.__head
        #鏈表為空和不為空的情況
        if self.is_empty():
            self.__head = node
        else:
            while curNode.next !=None:
                curNode = curNode.next
            curNode.next = node

3.指定位置添加元素

    #指定位置添加
    def insert(self,post,item):
        #如果post插入位置小于等于0，屬于頭部插入
        if (post-1)<=0:
            self.add(item)
        # 如果post插入位置大于等于鏈表長度，屬于尾部插入
        elif post>=self.length():
            self.append(item)
        #正常插入
        else:
            count = 0
            preNode = self.__head
            node = Node(item)
            while count<(post-1):
                count += 1
                preNode = preNode.next

            node.next=preNode.next
            preNode.next = node

4.洗掉節點

	#洗掉節點
    def remove(self,item):

        curNode = self.__head
        preNode = None
        while curNode!=None:
            #判斷是否為頭結點
            if curNode.elem == item:
                if preNode == None:
                    self.__head = curNode.next
                else:
                    preNode.next = curNode.next
                break
            else:
                preNode = curNode
                curNode = curNode.next

5.查找節點是否存在

    #查找節點是否存在
    def search(self,item):
        curNode = self.__head
        while curNode != None:
            if curNode.elem==item:
                return True
            curNode = curNode.next
        return False

6.判斷鏈表是否為空

    #判斷當前鏈表是否為空
    def is_empty(self):
        return self.__head == None

7.當前鏈表的長度

    #當前鏈表的長度
    def length(self):
        count = 0
        curNode = self.__head
        while curNode != None:
            count += 1
            curNode = curNode.next
        return count

8.遍歷鏈表

    #遍歷
    def travel(self):
        curNode = self.__head
        while curNode != None:
            print(curNode.elem,end='\t')
            curNode = curNode.next

全部代碼粘貼


class Node(object):
    def __init__(self,elem):
        #elem：資料元素
        self.elem=elem
        #next：下一個節點的鏈接域
        self.next=None

#構建單向鏈表類
class SingleLinkList:
    #初始化方法
    def __init__(self,node=None):
        if node!=None:
            headNode = Node(node)
            self.__head=headNode
        else:
            self.__head=node
        # print(self.__head)


    #在頭部添加元素
    def add(self,item):
        node = Node(item)
        # 將新節點的鏈接域next指向頭結點
        node.next=self.__head
        #將鏈表頭__head指向新節點
        self.__head = node

    #尾部追加
    def append(self,item):
        node = Node(item)
        curNode = self.__head
        #鏈表為空和不為空的情況
        if self.is_empty():
            self.__head = node
        else:
            while curNode.next !=None:
                curNode = curNode.next
            curNode.next = node

    #指定位置添加
    def insert(self,post,item):
        #如果post插入位置小于等于0，屬于頭部插入
        if (post-1)<=0:
            self.add(item)
        # 如果post插入位置大于等于鏈表長度，屬于尾部插入
        elif post>=self.length():
            self.append(item)
        #正常插入
        else:
            count = 0
            preNode = self.__head
            node = Node(item)
            while count<(post-1):
                count += 1
                preNode = preNode.next

            node.next=preNode.next
            preNode.next = node
    #洗掉節點
    def remove(self,item):

        curNode = self.__head
        preNode = None
        while curNode!=None:
            #判斷是否為頭結點
            if curNode.elem == item:
                if preNode == None:
                    self.__head = curNode.next
                else:
                    preNode.next = curNode.next
                break
            else:
                preNode = curNode
                curNode = curNode.next

    #查找節點是否存在
    def search(self,item):
        curNode = self.__head
        while curNode != None:
            if curNode.elem==item:
                return True
            curNode = curNode.next
        return False

    #判斷當前鏈表是否為空
    def is_empty(self):
        return self.__head == None

    #當前鏈表的長度
    def length(self):
        count = 0
        curNode = self.__head
        while curNode != None:
            count += 1
            curNode = curNode.next
        return count

    #遍歷
    def travel(self):
        curNode = self.__head
        while curNode != None:
            print(curNode.elem,end='\t')
            curNode = curNode.next

if __name__ == '__main__':
    singleLinkList=SingleLinkList()
    # print('鏈表長度：',singleLinkList.length())
    # print('鏈表是否為空:',singleLinkList.is_empty())
    # print('遍歷鏈表:', end=' ')
    # singleLinkList.travel()
    # print('查找節點是否存在:', singleLinkList.search(20))
    # singleLinkList.add(1)
    # singleLinkList.add(2)
    # singleLinkList.add(3)
    singleLinkList.append(1)
    singleLinkList.append(2)
    singleLinkList.append(3)
    singleLinkList.insert(10,4)
    singleLinkList.remove(4)
    singleLinkList.remove(1)
    print('遍歷鏈表:', end=' ')
    singleLinkList.travel()

雙向鏈表

每個節點有兩個鏈接：一個指向前一個節點（當此節點為第一個節點時，指向空值）；另一個節點指向下一個節點（當此節點為最后一個節點時，指向空值）

功能:

1.頭部添加元素

    #在頭部添加元素
    def add(self,item):
        node = Node(item)
        #判斷是否是空串列
        if self.is_empty():
            self.__head = node
        else:
            # 將新節點的鏈接域next指向頭結點
            node.next=self.__head

            #將__head 的頭節點的prev指向node
            self.__head.prev = node

            #將鏈表頭__head指向新節點
            self.__head = node

2.尾部添加元素

    #尾部追加
    def append(self,item):
        node = Node(item)
        curNode = self.__head
        #鏈表為空和不為空的情況
        if self.is_empty():
            self.__head = node

        else:
            while curNode.next !=None:
                curNode = curNode.next
            curNode.next = node
            #將node節點的前驅指向當前節點
            node.prev = curNode

3.指定位置添加元素

    #指定位置添加
    def insert(self,post,item):
        #如果post插入位置小于等于0，屬于頭部插入
        if (post-1)<=0:
            self.add(item)
        # 如果post插入位置大于等于鏈表長度，屬于尾部插入
        elif post>=self.length():
            self.append(item)
        #正常插入
        else:
            count = 0
            preNode = self.__head
            node = Node(item)
            while count<(post-1):
                count += 1
                preNode = preNode.next

            node.next=preNode.next
            node.prev = preNode
            preNode.next.prev = node
            preNode.next = node

4.洗掉節點

	 #洗掉節點
    def remove(self,item):

        curNode = self.__head
        while curNode!=None:
            #判斷是否為頭結點
            if curNode.elem == item:
                if curNode == self.__head:
                    self.__head = curNode.next
                    #判斷當前節點是否只有一個節點
                    if curNode.next:
                        curNode.next.prev = None

                else:
                    curNode.prev.next = curNode.next
                    if curNode.next:
                        curNode.next.prev = curNode.prev
                break
            else:
                curNode = curNode.next

5.查找節點是否存在

    #查找節點是否存在
    def search(self,item):
        curNode = self.__head
        while curNode != None:
            if curNode.elem==item:
                return True
            curNode = curNode.next
        return False

6.判斷鏈表是否為空

    #判斷當前鏈表是否為空
    def is_empty(self):
        return self.__head == None

7.當前鏈表的長度

    #當前鏈表的長度
    def length(self):
        count = 0
        curNode = self.__head
        while curNode != None:
            count += 1
            curNode = curNode.next
        return count

8.遍歷鏈表

    #遍歷
    def travel(self):
        curNode = self.__head
        while curNode != None:
            print(curNode.elem,end='\t')
            curNode = curNode.next

全部代碼粘貼

class Node(object):
    def __init__(self,elem):
        self.elem = elem
        self.prev = None
        self.next = None


#構建雙向鏈表類
class DoubleLinkList:
    #初始化方法
    def __init__(self,node=None):
        if node!=None:
            headNode = Node(node)
            self.__head=headNode
        else:
            self.__head=node
        # print(self.__head)


    #在頭部添加元素
    def add(self,item):
        node = Node(item)
        #判斷是否是空串列
        if self.is_empty():
            self.__head = node
        else:
            # 將新節點的鏈接域next指向頭結點
            node.next=self.__head

            #將__head 的頭節點的prev指向node
            self.__head.prev = node

            #將鏈表頭__head指向新節點
            self.__head = node

    #尾部追加
    def append(self,item):
        node = Node(item)
        curNode = self.__head
        #鏈表為空和不為空的情況
        if self.is_empty():
            self.__head = node

        else:
            while curNode.next !=None:
                curNode = curNode.next
            curNode.next = node
            #將node節點的前驅指向當前節點
            node.prev = curNode

    #指定位置添加
    def insert(self,post,item):
        #如果post插入位置小于等于0，屬于頭部插入
        if (post-1)<=0:
            self.add(item)
        # 如果post插入位置大于等于鏈表長度，屬于尾部插入
        elif post>=self.length():
            self.append(item)
        #正常插入
        else:
            count = 0
            preNode = self.__head
            node = Node(item)
            while count<(post-1):
                count += 1
                preNode = preNode.next

            node.next=preNode.next
            node.prev = preNode
            preNode.next.prev = node
            preNode.next = node
    #洗掉節點
    def remove(self,item):

        curNode = self.__head
        while curNode!=None:
            #判斷是否為頭結點
            if curNode.elem == item:
                if curNode == self.__head:
                    self.__head = curNode.next
                    #判斷當前節點是否只有一個節點
                    if curNode.next:
                        curNode.next.prev = None

                else:
                    curNode.prev.next = curNode.next
                    if curNode.next:
                        curNode.next.prev = curNode.prev
                break
            else:
                curNode = curNode.next

    #查找節點是否存在
    def search(self,item):
        curNode = self.__head
        while curNode != None:
            if curNode.elem==item:
                return True
            curNode = curNode.next
        return False

    #判斷當前鏈表是否為空
    def is_empty(self):
        return self.__head == None

    #當前鏈表的長度
    def length(self):
        count = 0
        curNode = self.__head
        while curNode != None:
            count += 1
            curNode = curNode.next
        return count

    #遍歷
    def travel(self):
        curNode = self.__head
        while curNode != None:
            print(curNode.elem,end='\t')
            curNode = curNode.next

if __name__ == '__main__':
    doubleLinkList = DoubleLinkList()
    doubleLinkList.add(1)
    doubleLinkList.add(12)
    doubleLinkList.append(21)
    doubleLinkList.append(22)
    doubleLinkList.insert(2,2)
    doubleLinkList.remove(23)
    doubleLinkList.travel()

堆疊（stack）

是一種容器，可以存入資料，訪問元素，洗掉元素，（LIFO）

特點：只允許在容器的一端加入元素和輸出元素，保證任何時候可以訪問、洗掉的元素都是此前最后存入的那個元素，

堆疊的實作

class Stack(object):
    def __init__(self):
        self.__list = []

    #壓堆疊
    def push(self,item):
        self.__list.append(item)

    #彈出元素
    def pop(self):
        return self.__list.pop()

    #回傳堆疊頂元素
    def peek(self):

        return self.__list[len(self.__list)-1]

    #判斷堆疊是否為空
    def is_empty(self):
        return self.__list == []

    #計算堆疊的大小

    def size(self):
        return len(self.__list)

if __name__ == '__main__':
    stack = Stack()
    #壓堆疊
    stack.push(1)
    stack.push(2)
    stack.push(3)
    stack.push(4)
    #彈出
    print(stack.pop())
    print(stack.pop())
    print(stack.pop())
    print(stack.pop())

佇列（queue）

只允許在一端進行插入操作，另一端進行洗掉操作的線性表，（FIFO），允許插入的一端為隊尾，允許洗掉的一端為對頭，

佇列的實作

class Queue(object):
    def __init__(self):
        self.__list = []

    #進隊
    def enqueue(self,item):
        self.__list.append(item)
        # self.__list.insert(0,item)

    #出隊
    def dequeue(self):
        return self.__list.pop(0)
        # return self.__list.pop()
    #判斷佇列是否為空
    def is_empty(self):
        return self.__list == []

    #計算佇列的大小
    def size(self):
        return len(self.__list)

if __name__ == '__main__':
    queue = Queue()
    queue.enqueue(1)
    queue.enqueue(2)
    queue.enqueue(3)
    print(queue.size())
    print(queue.dequeue())
    print(queue.size())
    print(queue.is_empty())

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/279261.html

標籤：python

上一篇：# PYthon腳本arpspoof自動生成

下一篇：《Python編程從入門到實踐》——學習python的第六天

資料結構與演算法--（鏈表，堆疊，佇列）

資料結構與演算法–（鏈表，堆疊，佇列）

文章目錄

鏈表

定義

單向鏈表

功能:

1.頭部添加元素

2.尾部添加元素

3.指定位置添加元素

4.洗掉節點

5.查找節點是否存在

6.判斷鏈表是否為空

7.當前鏈表的長度

8.遍歷鏈表

全部代碼粘貼

雙向鏈表

功能:

1.頭部添加元素

2.尾部添加元素

3.指定位置添加元素

4.洗掉節點

5.查找節點是否存在

6.判斷鏈表是否為空

7.當前鏈表的長度

8.遍歷鏈表

全部代碼粘貼

堆疊（stack）

堆疊的實作

佇列（queue）

佇列的實作