A.数据结构（线性表）

A.顺序存储

1.求两个线性表的并集

list1 = ['a', 's', 'd']
list2 = ['a', 's', 'f']
for i in list1:
    if i not in list2:
        list2.extend(i)
print(list2)

2.查找第i个位置元素的值

def fetch(lis, i):
    if len(lis) == 0 or i < 1 or i >len(lis) :
        return 0
    else:
        return lis[i-1]


a = ['a', 'x', 'd']
print(fetch(a, 2))

3.在第i个位置插入新的元素，线性表长度加1

def addd(lis, i, new_data):
    if (i < 1) or (i > len(lis) + 1):  # len(lis)+1 是因为要考虑到在列表末尾添加元素
        return 0
    elif i == len(lis)+1:
        lis.extend(new_data)
        return lis
    else:
        if i <= len(lis):
            k = len(lis)-1
            lis.extend('1')
            while k >= i-1:
                lis[k+1] = lis[k]
                k = k-1

        lis[i-1] = new_data
        return lis


a = ['a', 'x', 'd']

print(addd(a, 4, 'f'))

4.删除第i个位置上的元素

def delete(lis, i):
    if (len(lis) == 0) or (i < 1) or (i > len(lis) + 1):
        return 0
    elif i < len(lis):  # 删除的不是最后一个位置
        k = i
        while k < len(lis):
            lis[k-1] = lis[k]
            k = k+1
        lis.pop()
        return lis
    else:
        lis.pop()
        return lis


a = ['a', 'x', 'd']

print(delete(a, 1))

 B.链表

一·、单链表

class Node(object):
    #  定义一个节点的类
    def __init__(self, elem):
        self.elem = elem
        self.next = None  # 初始设置下一节点为空


class SingleLinkList(object):
    def __init__(self, node=None):
        #  使用一个默认参数，传入第一个结点时接收，没有传入时，默认是空链表
        self.__head = node

    def is_empty(self):
        # 判断链表是否为空 空返回Ture
        return   self.__head == None

    def length(self):
         '''链表长度'''
        # cur为游标，用来遍历节点，是移动的
         cur = self.__head
        # count记录节点数量
         count = 0
         while cur != None:
             count += 1
             cur = cur.next
         return count

    def travel(self):
        '''遍历整个列表'''
        cur = self.__head
        while cur != None:
            print(cur.elem,end = ' ')  # ''中必须有空格。'空格'，这样两个元素打印出来中间不会连着
            cur = cur.next
        print("
") # 打印完整个链表以后换行

    def add(self,item):
        '''链表头部添加元素'''
        node = Node(item)
        node.next = self.__head
        self.__head = node

    def append(self,item):
        '''链表尾部添加元素'''
        node = Node(item)
        if self.is_empty():
            # 特殊情况，链表为空
            self.__head = node
        else:
            cur = self.__head
            while cur.next != None: # 游标最后是在最后一个节点
                cur = cur.next
            cur.next = node

    def insert(self,pos,item):
        '''指定位置添加元素'''
        if pos <= 0: # 想要插入节点的位置小于等于0，都当做在链表头部添加节点
            self.add(item)
        elif pos > self.length():
            self.append(item)
        else:
            per = self.__head
            count = 1
            while count < pos-1:
                count += 1
                per = per.next
            # 循环退出时，per这个游标在pos-1位置，指定位置的前面一个节点
            node = Node(item)
            node.next = per.next # 顺序不能变，先加入原链表，再破坏原链表
            per.next = node

    def remove(self,item):
        '''删除节点'''
        cur = self.__head
        pre = None
        while cur != None:
            if cur.elem == item:
                # 找到要删除的节点
                if cur == self.__head:
                    # 要删除的节点是第一个节点,并直接删掉第一个节点
                    self.__head = cur.next
                else:
                    # 要删除的节点不是第一个节点
                    pre.next = cur.next
                break # 删除完退出循环
            else: # 没要找到要删除的节点，两个游标继续往后
                 pre = cur # 顺序不能变
                 cur = cur.next

    def search(self,item):
          '''查找节点是否存在'''
          cur = self.__head
          while cur ！= None:
              if cur.elem == item:
                  return True
              else:
                  cur = cur.next
          return False

if __name__ == "__main__":
    l1 = SingleLinkList()
    print(l1.is_empty()) # true l1是一个空链表
    l1.append(3)
    l1.add(999)
    l1.insert(2,2)
    l1.travel()  # 999  2 3

    print(l1.length())
    print(l1.is_empty())
    l1.remove(999)
    l1.travel()  # 2 3
    print(l1.search(999))  # False

二、双向链表

class Node(object):
    #  定义一个节点的类
    def __init__(self, item):
        self.elem = item
        self.prev = None  #指向前驱结点
        self.next = None  #指向后继结点


class LinkedListTwoway(object):
    def __init__(self, node=None):
        #  使用一个默认参数，传入第一个结点时接收，没有传入时，默认是空链表
        self.__head = node

    def is_empty(self):
        '''判断链表是否为空 空返回Ture'''
        return   self.__head == None

    def length(self):
         '''链表长度'''
        # cur为游标，用来遍历节点，是移动的
         cur = self.__head
        # count记录节点数量
         count = 0
         while cur != None:
             count += 1
             cur = cur.next
         return count

    def travel(self):
        '''遍历整个列表'''
        cur = self.__head
        while cur != None:
            print(cur.elem,end = ' ')  # ''中必须有空格。'空格'，这样两个元素打印出来中间不会连着
            cur = cur.next
        print("
") # 打印完整个链表以后换行

    def add(self,item):
        '''链表头部添加元素'''
        node = Node(item)
        if self.is_empty():
            # 特殊情况，链表为空
            self.__head = node
        else:
            node.next = self.__head
            node.next.prev = node  # self.__head.prev = node
            self.__head = node

    def append(self,item):
        '''链表尾部添加元素'''
        node = Node(item)
        if self.is_empty():
            # 特殊情况，链表为空
            self.__head = node
        else:
            cur = self.__head
            while cur.next != None: # 退出循环时游标最后是在最后一个节点
                cur = cur.next
            cur.next = node
            node.prev = cur

    def insert(self, pos, item):
        '''指定位置添加元素'''
        if pos <= 0: # 想要插入节点的位置小于等于0，都当做在链表头部添加节点
            self.add(item)
        elif pos > self.length():
            self.append(item)
        else:
            count = 1
            # 符合用户习惯，从1开始计数
            cur = self.__head
            while count < pos-1:
                count += 1
                cur = cur.next
            # 循环退出时，per这个游标在pos-1位置，指定位置的前面一个节点
            node = Node(item)
            node.next = cur.next # 顺序不能变，先加入原链表，再破坏原链表
            cur.next.prev = node
            node.prev = cur
            cur.next = node

    def remove(self,item):
        '''删除节点'''
        if self.is_empty():
            return
        cur = self.__head
        # 单向链表为了在指定位置插入，需要在链表中找出指定位置的前一个位置，所以使用两个游标比较容易理解和方便
        # 双向链表不需要两个游标
        while cur != None:
            if cur.elem == item:
                # 找到要删除的节点
                if cur == self.__head:
                    # 要删除的节点是第一个节点,并直接删掉第一个节点
                    self.__head = cur.next
                    if cur.next:
                        # 特殊情况：链表只有一个节点
                        cur.next.prev = None
                else:
                    # 要删除的节点不是第一个节点
                    cur.prev.next = cur.next
                    if cur.next != None:
                        #特殊情况：如果删除最后一个节点，则不能进入执行这一句
                        cur.next.prev = cur.prev
                break # 删除完退出循环
            else: # 没要找到要删除的节点，两个游标继续往后
                 cur = cur.next

    def search(self,item):
          '''查找节点是否存在'''
          cur = self.__head
          while cur != None:
              if cur.elem == item:
                  return True
              else:
                  cur = cur.next
          return False

if __name__ == "__main__":
    l1 = LinkedListTwoway()
    print(l1.is_empty()) # true l1是一个空链表
    l1.append(3)
    l1.add(999)
    l1.insert(2,2)
    l1.travel()  # 999  2  3

    print(l1.length())  # 3
    print(l1.is_empty())  # False
    l1.remove(999)
    l1.travel()  # 2 3
    print(l1.search(999))  # False

三、单向循环链表

class Node(object):
    #  定义一个节点的类
    def __init__(self, elem):
        self.elem = elem
        self.next = None  # 初始设置下一节点为空


class CircularLinkedList(object):
    def __init__(self, node=None):
        # 只是一个空链表也可以哈
        if node:
            #  构造非空链表，初始链表默认只有一个节点，其地址域指向自己
            node.next = node
        self.__head = node

    def is_empty(self):
        # 判断链表是否为空 空返回Ture
        return self.__head == None

    def length(self):
         #   链表长度
         cur = self.__head
         count = 1
         # count记录节点数量
         # 需要从1开始计数，因为游标走到最后一个节点时不再进入循环体
         # 前面单向链表和双向链表的游标走到最后一步还会进入循环体
         if self.is_empty():
             return 0
         while cur.next != self.__head:
             count += 1
             cur = cur.next
         return count

    def travel(self):
        '''遍历整个列表'''
        if self.is_empty():
            return 0
        cur = self.__head
        while cur.next != self.__head:
            print(cur.elem, end=' ')  # ''中必须有空格。'空格'，这样两个元素打印出来中间不会连着
            cur = cur.next
        print(cur.elem)
        print("
") # 打印完整个链表以后换行

    def add(self,item):
        '''链表头部添加元素'''
        node = Node(item)
        if self.is_empty():
            # 特殊情况：空链表
            self.__head = node
            node.next = node
        else:
            cur = self.__head
            while cur.next != self.__head:
                cur = cur.next
            # 退出循环后，cur指向最后一个节点，找到了尾结点
            node.next = self.__head  # 新节点指向原来的第一个节点
            self.__head = node  # 头结点指向新的第一个节点
            cur.next = node  # 尾结点还要指向第一个结点

    def append(self,item):
        '''链表尾部添加元素'''
        node = Node(item)
        if self.is_empty():
            # 特殊情况，链表为空
            self.__head = node
            self.__head.next = self.__head
        else:
            cur = self.__head
            while cur.next != self.__head: # 游标最后是在最后一个节点
                cur = cur.next
            node.next = cur.next  # 新节点指向 最后一个游标指向的东西（第一个节点）
            cur.next = node  # 原最后一个节点指向新的最后一个节点

    def insert(self,pos,item):
        '''指定位置添加元素'''
        if pos <= 0: # 想要插入节点的位置小于等于0，都当做在链表头部添加节点
            self.add(item)
        elif pos > self.length():
            self.append(item)
        else:
            cur = self.__head
            count = 1
            while count < pos-1:
                count += 1
                per = cur.next
            # 循环退出时，per这个游标在pos-1位置，指定位置的前面一个节点
            node = Node(item)
            node.next = cur.next # 顺序不能变，先加入原链表，再破坏原链表
            cur.next = node

    def remove(self,item):
        '''删除节点'''
        cur = self.__head
        pre = None
        if self.is_empty():
            return 0
        while cur.next != self.__head:
            if self.is_empty():
                return 0
            if cur.elem == item:
                # 找到要删除的节点
                if cur == self.__head:
                    # 特殊情况：要删除的节点是第一个节点
                    # 找到尾结点
                    rear = self.__head
                    while rear.next != self.__head:
                        rear = rear.next
                    self.__head = cur.next
                    rear.next = self.__head
                else:
                    # 要删除的节点不是第一个节点，在中间
                    pre.next = cur.next
                return  # 删除完不是退出循环，而是退出这个函数，返回
            else:  # 没要找到要删除的节点，两个游标继续往后
                 pre = cur
                 cur = cur.next

        # 退出循环时，cur指向的结点并没有进行操作，也就是没有执行循环体
        if cur.item == item:
            # 要删除的节点是最后一个节点
            if cur == self.__head:
                # 特殊情况：链表只有一个节点
                self.__head = None
                return
            pre.next = cur.next  # pre.next = self.__head

    def search(self,item):
          '''查找节点是否存在'''
          if self.is_empty():
              return False
          cur = self.__head
          while cur.next != self.__head:
              if cur.elem == item:
                  return True
              else:
                  cur = cur.next
          if cur.elem == item:
              # 判断循环外的尾结点是不是要找的节点
              return True
          return False

if __name__ == "__main__":
    l1 = CircularLinkedList()
    print(l1.is_empty()) # true l1是一个空链表
    l1.append(3)
    l1.add(999)
    l1.insert(2,2)
    l1.travel()  # 999  2 3

    print(l1.length())
    print(l1.is_empty())
    l1.remove(999)
    l1.travel()  # 2 3
    print(l1.search(999))  # False