1、封装一套数据结构和算法，包含：顺序表、单链表、顺序栈、循 环队列、二叉树的二叉链表、图的邻接矩阵或邻接表、基本排序算法（直接插入排序、希尔排序、简单选择排序、快速排序、堆排序、归并排序至少任选3个）

以下是一套数据结构和算法的实现，包含顺序表、单链表、顺序栈、循环队列、二叉树的二叉链表、图的邻接矩阵和邻接表、基本排序算法（直接插入排序、希尔排序、简单选择排序、快速排序、堆排序、归并排序）：

# 顺序表
class SeqList:
    def __init__(self, maxsize=None):
        self.maxsize = maxsize
        self._items = [None] * self.maxsize
        self.length = 0

    def __getitem__(self, index):
        if index < self.length:
            return self._items[index]
        else:
            raise IndexError('Index out of range')

    def __setitem__(self, index, value):
        if index < self.length:
            self._items[index] = value
        else:
            raise IndexError('Index out of range')

    def __len__(self):
        return self.length

    def __repr__(self):
        return str(self._items[:self.length])

    def insert(self, index, value):
        if self.length >= self.maxsize:
            raise Exception('Full')
        if index < 0:
            index += self.length
        if index < 0:
            index = 0
        if index > self.length:
            index = self.length
        for i in range(self.length-1, index-1, -1):
            self._items[i+1] = self._items[i]
        self._items[index] = value
        self.length += 1

    def delete(self, index):
        if self.length == 0:
            raise Exception('Empty')
        if index < 0:
            index += self.length
        if index < 0 or index >= self.length:
            raise IndexError('Index out of range')
        for i in range(index, self.length-1):
            self._items[i] = self._items[i+1]
        self.length -= 1

# 单链表
class Node:
    def __init__(self, value=None, next=None):
        self.value = value
        self.next = next

class LinkedList:
    def __init__(self):
        self.head = Node()
        self.length = 0

    def __len__(self):
        return self.length

    def __repr__(self):
        values = []
        current_node = self.head.next
        while current_node:
            values.append(current_node.value)
            current_node = current_node.next
        return '->'.join(str(value) for value in values)

    def insert(self, index, value):
        if index < 0:
            index += self.length
        if index < 0:
            index = 0
        if index > self.length:
            index = self.length
        prev_node = self.head
        for i in range(index):
            prev_node = prev_node.next
        new_node = Node(value)
        new_node.next = prev_node.next
        prev_node.next = new_node
        self.length += 1

    def delete(self, index):
        if index < 0:
            index += self.length
        if index < 0 or index >= self.length:
            raise IndexError('Index out of range')
        prev_node = self.head
        for i in range(index):
            prev_node = prev_node.next
        current_node = prev_node.next
        prev_node.next = current_node.next
        self.length -= 1

# 顺序栈
class SeqStack:
    def __init__(self, maxsize=None):
        self.maxsize = maxsize
        self._items = [None] * self.maxsize
        self.top = -1

    def __len__(self):
        return self.top + 1

    def __repr__(self):
        return str(self._items[:self.top+1])

    def push(self, value):
        if self.top == self.maxsize - 1:
            raise Exception('Full')
        self.top += 1
        self._items[self.top] = value

    def pop(self):
        if self.top == -1:
            raise Exception('Empty')
        value = self._items[self.top]
        self.top -= 1
        return value

# 循环队列
class CircularQueue:
    def __init__(self, maxsize):
        self.maxsize = maxsize
        self._items = [None] * self.maxsize
        self.head = 0
        self.tail = 0

    def __len__(self):
        return (self.tail - self.head + self.maxsize) % self.maxsize

    def __repr__(self):
        if self.tail >= self.head:
            return str(self._items[self.head:self.tail])
        else:
            return str(self._items[self.head:] + self._items[:self.tail])

    def push(self, value):
        if (self.tail + 1) % self.maxsize == self.head:
            raise Exception('Full')
        self._items[self.tail] = value
        self.tail = (self.tail + 1) % self.maxsize

    def pop(self):
        if self.tail == self.head:
            raise Exception('Empty')
        value = self._items[self.head]
        self.head = (self.head + 1) % self.maxsize
        return value

# 二叉树的二叉链表
class BinTNode:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

class BinTree:
    def __init__(self):
        self._root = None

    def is_empty(self):
        return self._root is None

    def root(self):
        return self._root

    def leftchild(self, node):
        return node.left

    def rightchild(self, node):
        return node.right

    def set_root(self, rootnode):
        self._root = rootnode

    def set_left(self, node, leftchild):
        node.left = leftchild

    def set_right(self, node, rightchild):
        node.right = rightchild

    def preorder_elements(self, node):
        if node is not None:
            yield node.data
            yield from self.preorder_elements(node.left)
            yield from self.preorder_elements(node.right)

    def inorder_elements(self, node):
        if node is not None:
            yield from self.inorder_elements(node.left)
            yield node.data
            yield from self.inorder_elements(node.right)

    def postorder_elements(self, node):
        if node is not None:
            yield from self.postorder_elements(node.left)
            yield from self.postorder_elements(node.right)
            yield node.data

# 图的邻接矩阵
class Graph:
    def __init__(self, mat, unconn=0):
        vnum = len(mat)
        for x in mat:
            if len(x) != vnum:
                raise ValueError('Argument for Graph')
        self._mat = [mat[i][:] for i in range(vnum)]
        self._unconn = unconn
        self._vnum = vnum

    def vertex_num(self):
        return self._vnum

    def _invalid(self, v):
        return 0 > v or v >= self._vnum

    def add_vertex(self):
        raise ValueError('Adj-Matrix does not support "add_vertex"')

    def add_edge(self, vi, vj, val=1):
        if self._invalid(vi) or self._invalid(vj):
            raise ValueError(str(vi) + ' or ' + str(vj) + ' is not a valid vertex.')
        self._mat[vi][vj] = val

    def get_edge(self, vi, vj):
        if self._invalid(vi) or self._invalid(vj):
            raise ValueError(str(vi) + ' or ' + str(vj) + ' is not a valid vertex.')
        return self._mat[vi][vj]

    def out_edges(self, vi):
        if self._invalid(vi):
            raise ValueError(str(vi) + ' is not a valid vertex.')
        return self._out_edges(self._mat[vi], self._unconn)

    @staticmethod
    def _out_edges(row, unconn):
        edges = []
        for i in range(len(row)):
            if row[i] != unconn:
                edges.append((i, row[i]))
        return edges

# 图的邻接表
class GraphAL(Graph):
    def __init__(self, mat=[], unconn=0):
        vnum = len(mat)
        for x in mat:
            if len(x) != vnum:
                raise ValueError('Argument for Graph')
        self._mat = [Graph._out_edges(mat[i], unconn) for i in range(vnum)]
        self._vnum = vnum
        self._unconn = unconn

    def add_vertex(self):
        self._mat.append([])
        self._vnum += 1
        return self._vnum - 1

    def add_edge(self, vi, vj, val=1):
        if self._vnum == 0:
            raise ValueError('Cannot add edge to empty graph.')
        if self._invalid(vi) or self._invalid(vj):
            raise ValueError(str(vi) + ' or ' + str(vj) + ' is not a valid vertex.')
        row = self._mat[vi]
        i = 0
        while i < len(row):
            if row[i][0] == vj:
                self._mat[vi][i] = (vj, val)
                return
            if row[i][0] > vj:
                break
            i += 1
        self._mat[vi].insert(i, (vj, val))

    def get_edge(self, vi, vj):
        if self._invalid(vi) or self._invalid(vj):
            raise ValueError(str(vi) + ' or ' + str(vj) + ' is not a valid vertex.')
        for i, val in self._mat[vi]:
            if i == vj:
                return val
        return self._unconn

    def out_edges(self, vi):
        if self._invalid(vi):
            raise ValueError(str(vi) + ' is not a valid vertex.')
        return self._mat[vi]

# 直接插入排序
def insert_sort(lst):
    n = len(lst)
    for i in range(1, n):
        value = lst[i]
        j = i - 1
        while j >= 0 and lst[j] > value:
            lst[j+1] = lst[j]
            j -= 1
        lst[j+1] = value

# 希尔排序
def shell_sort(lst):
    n = len(lst)
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            value = lst[i]
            j = i - gap
            while j >= 0 and lst[j] > value:
                lst[j+gap] = lst[j]
                j -= gap
            lst[j+gap] = value
        gap //= 2

# 简单选择排序
def select_sort(lst):
    n = len(lst)
    for i in range(n-1):
        min_index = i
        for j in range(i+1, n):
            if lst[j] < lst[min_index]:
                min_index = j
        if min_index != i:
            lst[i], lst[min_index] = lst[min_index], lst[i]

# 快速排序
def quick_sort(lst):
    if len(lst) <= 1:
        return lst
    pivot = lst[0]
    left = [x for x in lst[1:] if x < pivot]
    right = [x for x in lst[1:] if x >= pivot]
    return quick_sort(left) + [pivot] + quick_sort(right)

# 堆排序
def heap_sort(lst):
    def sift_down(start, end):
        root = start
        while True:
            child = 2 * root + 1
            if child > end:
                break
            if child + 1 <= end and lst[child] < lst[child+1]:
                child += 1
            if lst[root] < lst[child]:
                lst[root], lst[child] = lst[child], lst[root]
                root = child
            else:
                break
    for start in range((len(lst)-2)//2, -1, -1):
        sift_down(start,