数据结构与算法基础（青岛大学-王卓）(6)

**数据结构与算法基础**

**第一章：线性表**

###1.1 线性表的定义线性表是指零个或多个元素按一定顺序排列起来的集合体。每个元素都有一个唯一的前驱和后继元素，或者说，每个元素都有一个唯一的位置。

###1.2 线性表的基本操作线性表的基本操作包括：

* **插入**:将一个新元素插入到线性表中。
* **删除**:从线性表中删除一个元素。
* **查找**:在线性表中找到一个指定的元素。
* **长度**:求出线性表中的元素个数。

###1.3 线性表的存储结构线性表可以使用数组或链式存储结构来实现。数组存储结构是指将所有元素都存放在一块连续的内存空间中，而链式存储结构则是通过指针连接各个元素。

###1.4 线性表的应用线性表广泛应用于计算机科学中的许多领域，如数据库管理系统、操作系统等。

**示例代码**

class Node:
 def __init__(self, data):
 self.data = data self.next = Noneclass LinkedList:
 def __init__(self):
 self.head = None def insert(self, data):
 new_node = Node(data)
 if not self.head:
 self.head = new_node else:
 current = self.head while current.next:
 current = current.next current.next = new_node def delete(self, key):
 if self.head is None:
 return # If the node to be deleted is head node if self.head.data == key:
 self.head = self.head.next return # Search for the node to be deleted and update head current = self.head while current.next:
 if current.next.data == key:
 break current = current.next if current.next is None:
 print("Node not found")
 return current.next = current.next.next def search(self, key):
 current = self.head while current:
 if current.data == key:
 return True current = current.next return False def length(self):
 count =0 current = self.head while current:
 count +=1 current = current.next return count# Test the LinkedList classlinked_list = LinkedList()
linked_list.insert(5)
linked_list.insert(10)
linked_list.insert(15)

print("Length:", linked_list.length())
print("Search for10:", linked_list.search(10))
linked_list.delete(10)
print("Length after deletion:", linked_list.length())

**第二章：栈**

###2.1 栈的定义栈是指一个元素按一定顺序排列起来的集合体。每个元素都有一个唯一的前驱和后继元素，或者说，每个元素都有一个唯一的位置。

###2.2 栈的基本操作栈的基本操作包括：

* **入栈**:将一个新元素压入栈中。
* **出栈**:从栈中弹出一个元素。
* **顶部元素**:获取栈中的顶部元素。

###2.3 栈的存储结构栈可以使用数组或链式存储结构来实现。数组存储结构是指将所有元素都存放在一块连续的内存空间中，而链式存储结构则是通过指针连接各个元素。

###2.4 栈的应用栈广泛应用于计算机科学中的许多领域，如表达式求值、回溯算法等。

**示例代码**

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

 def push(self, item):
 self.items.append(item)

 def pop(self):
 if not self.is_empty():
 return self.items.pop()
 else:
 raise IndexError("Stack is empty")

 def peek(self):
 if not self.is_empty():
 return self.items[-1]
 else:
 raise IndexError("Stack is empty")

 def is_empty(self):
 return len(self.items) ==0# Test the Stack classstack = Stack()
stack.push(5)
stack.push(10)
print("Top element:", stack.peek())
print("Popped element:", stack.pop())
print("Is empty?", stack.is_empty())

**第三章：队列**

###3.1 队列的定义队列是指一个元素按一定顺序排列起来的集合体。每个元素都有一个唯一的前驱和后继元素，或者说，每个元素都有一个唯一的位置。

###3.2 队列的基本操作队列的基本操作包括：

* **入队**:将一个新元素加入到队列中。
* **出队**:从队列中取出一个元素。
* **首部元素**:获取队列中的首部元素。

###3.3 队列的存储结构队列可以使用数组或链式存储结构来实现。数组存储结构是指将所有元素都存放在一块连续的内存空间中，而链式存储结构则是通过指针连接各个元素。

###3.4 队列的应用队列广泛应用于计算机科学中的许多领域，如进程调度、线程管理等。

**示例代码**

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

 def enqueue(self, item):
 self.items.append(item)

 def dequeue(self):
 if not self.is_empty():
 return self.items.pop(0)
 else:
 raise IndexError("Queue is empty")

 def peek(self):
 if not self.is_empty():
 return self.items[0]
 else:
 raise IndexError("Queue is empty")

 def is_empty(self):
 return len(self.items) ==0# Test the Queue classqueue = Queue()
queue.enqueue(5)
queue.enqueue(10)
print("Front element:", queue.peek())
print("Dequeued element:", queue.dequeue())
print("Is empty?", queue.is_empty())

**第四章：树**

###4.1 树的定义树是指一个元素按一定顺序排列起来的集合体。每个元素都有一个唯一的前驱和后继元素，或者说，每个元素都有一个唯一的位置。

###4.2 树的基本操作树的基本操作包括：

* **插入**:将一个新元素插入到树中。
* **删除**:从树中删除一个元素。
* **查找**:在树中找到一个指定的元素。
* **高度**:求出树中的最大深度。

###4.3 树的存储结构树可以使用数组或链式存储结构来实现。数组存储结构是指将所有元素都存放在一块连续的内存空间中，而链式存储结构则是通过指针连接各个元素。

###4.4 树的应用树广泛应用于计算机科学中的许多领域，如文件系统管理、数据库索引等。

**示例代码**

class Node:
 def __init__(self, data):
 self.data = data self.left = None self.right = Noneclass BinaryTree:
 def __init__(self):
 self.root = None def insert(self, data):
 if not self.root:
 self.root = Node(data)
 else:
 self._insert(data, self.root)

 def _insert(self, data, node):
 if data < node.data:
 if node.left is None:
 node.left = Node(data)
 else:
 self._insert(data, node.left)
 else:
 if node.right is None:
 node.right = Node(data)
 else:
 self._insert(data, node.right)

 def delete(self, key):
 self.root = self._delete(key, self.root)

 def _delete(self, key, node):
 if not node:
 return node if key < node.data:
 node.left = self._delete(key, node.left)
 elif key > node.data:
 node.right = self._delete(key, node.right)
 else:
 if not node.left and not node.right:
 return None elif not node.left:
 return node.right elif not node.right:
 return node.left else:
 min_node = self._find_min(node.right)
 node.data = min_node.data node.right = self._delete(min_node.data, node.right)
 return node def _find_min(self, node):
 while node.left:
 node = node.left return node def search(self, key):
 return self._search(key, self.root)

 def _search(self, key, node):
 if not node or node.data == key:
 return node elif key < node