04案例-约瑟夫环.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "元素1元素2元素3元素4元素5元素6元素7元素8元素9元素10元素11元素12元素13元素14元素15\n",
      "元素4  元素8  元素12  元素1  元素6  元素11  元素2  元素9  元素15  元素10  元素5  元素3  元素7  元素14  元素13  "
     ]
    }
   ],
   "source": [
    "'''\n",
    "    案例:\n",
    "    使用循环链表求解约瑟夫(losephu )问题\n",
    "    n个人(以编号0，1，2，3...n-1分别表示)围坐在一张圆桌周围。从编号为1的人开始报数1，数到m的那个人出列;\n",
    "    他的下一个人又从1开始报数，数到m的那个人又出列;依此规律重复下去，直到圆桌周围的人全部出列。按照顺序出列的人的编号列表 \n",
    "'''   \n",
    "\n",
    "class SingleNode(object):\n",
    "      # 单链表的结点”\n",
    "  def __init__(self,item):\n",
    "    # item存放数据元素\n",
    "    self.item = item\n",
    "    # next是下一个节点的标识\n",
    "    self.next = None\n",
    "\n",
    "class CycleSingleLinkList:\n",
    "  def __init__(self):\n",
    "    self.__head: SingleNode  = None\n",
    "\n",
    "  # - is_empty() 链表是否为空\n",
    "  def is_empty(self):\n",
    "      return self.__head is None\n",
    "\n",
    "\n",
    "  # - Length() 链表长度\n",
    "  def length(self):\n",
    "      if  self.is_empty():\n",
    "            return 0\n",
    "      \n",
    "      cur = self.__head\n",
    "      count = 1\n",
    "      while cur.next != self.__head :\n",
    "            \n",
    "            count += 1\n",
    "            cur = cur.next\n",
    "      return count\n",
    "      \n",
    "\n",
    "  # - traveL() 遍历整个链表\n",
    "  def travel(self):\n",
    "    if self.is_empty():\n",
    "       print(\"\")\n",
    "       return\n",
    "\n",
    "    cur = self.__head\n",
    "\n",
    "    while  cur.next != self.__head:\n",
    "       print(cur.item, end = \"\")\n",
    "       cur = cur.next\n",
    "    # 从循环退出，cur指向尾节点\n",
    "    print(cur.item)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "  # - add(item) 链表头部添加元素\n",
    "  def add(self,item):\n",
    "    '''\n",
    "    :param item: 要保存的具体数据\n",
    "    '''\n",
    "    node = SingleNode(item)\n",
    "\n",
    "    if self.is_empty():\n",
    "       self.__head = node\n",
    "       node.next = node\n",
    "    # 寻找尾节点\n",
    "    cur = self.__head\n",
    "    while cur.next != self.__head:\n",
    "       cur = cur.next\n",
    "    # 从循环退出 cur指向尾系节点  换self.__head\n",
    "    node.next = self.__head\n",
    "    self.__head = node\n",
    "    cur.next = self.__head\n",
    "\n",
    "  # - append(item) 链表尾部添加元素\n",
    "  def append(self,item):\n",
    "    node = SingleNode(item)\n",
    "    if self.is_empty():\n",
    "       self.__head = node\n",
    "       node.next = node\n",
    "    else:\n",
    "    \n",
    "      # 遍历\n",
    "      cur = self.__head\n",
    "      while cur.next != self.__head:\n",
    "        cur = cur.next # 获取最后一个节点\n",
    "      cur.next = node\n",
    "      node.next = self.__head\n",
    "\n",
    "  # - insert(pos，item) 指定位置添加元素\n",
    "  def insert(self,pos,item):\n",
    "        if pos <= 0 :    \n",
    "          self.add(item)\n",
    "        elif pos >= self.length():\n",
    "          self.append(item)\n",
    "        else:\n",
    "          cur = self.__head\n",
    "          count = 0\n",
    "          while count < (pos-1):\n",
    "                count += 1\n",
    "                cur = cur.next\n",
    "          # 等于要插入的位置 哦一个节点ya\n",
    "          node = SingleNode(item)\n",
    "          # 当前的下一个是插入node的下一个\n",
    "          node.next = cur.next\n",
    "          # 节点是当前的下一个\n",
    "          cur.next= node\n",
    "\n",
    "\n",
    "\n",
    "  # - remove(item) 删除节点\n",
    "  def remove(self,item):\n",
    "        \n",
    "        if self.is_empty():\n",
    "           return\n",
    "        cur: SingleNode = self.__head\n",
    "        pre = None\n",
    "        while cur.next != self.__head :\n",
    "            \n",
    "            if cur.item == item:\n",
    "                # 在头部 直接覆盖掉\n",
    "                if cur == self.__head:\n",
    "                    # 先找到尾节点\n",
    "                    rear = self.__head\n",
    "                    while rear.next != self.__head:\n",
    "                       rear = rear.next\n",
    "                    # 退出循环后 rear指向尾节点\n",
    "                    self.__head = cur.next\n",
    "                    rear.next = self.__head\n",
    "                else:\n",
    "                    pre.next = cur.next\n",
    "                return True\n",
    "            pre = cur # 记录一下上一个节点，开启下一个轮回\n",
    "            cur = cur.next\n",
    "        # 退出循环后 cur指向尾节点\n",
    "        if cur.item == item:\n",
    "           # 链表只有一个节点\n",
    "           if cur == self.__head:\n",
    "                self.__head = None\n",
    "           else:\n",
    "                pre.next = self.__head\n",
    "              \n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "  # - search(item) 查找节点是否存在\n",
    "  def search(self,item):\n",
    "        if self.is_empty():\n",
    "               return False\n",
    "        cur: SingleNode = self.__head\n",
    "        while cur.next != self.__head :\n",
    "        \n",
    "            if cur.item == item:\n",
    "                return True\n",
    "            cur = cur.next\n",
    "        # 退出循环后 cur指向尾节点\n",
    "        if cur.item == item:\n",
    "            return True\n",
    "        return False\n",
    "  \n",
    "  def josehu(self,k=None):\n",
    "        count = 1\n",
    "        cur = self.__head\n",
    "        while not self.is_empty():\n",
    "            if count == k:\n",
    "                print(cur.item,end=\"  \")\n",
    "                self.remove(cur.item)\n",
    "                count = 0\n",
    "            cur = cur.next\n",
    "            count +=1\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    ll = CycleSingleLinkList()\n",
    "    for i  in range(1,16):\n",
    "        ll.append(f\"元素{i}\")\n",
    "    ll.travel()\n",
    "    ll.josehu(4)\n",
    "    \n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "pytorch3.7",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.11"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}