数据结构与算法（三）——单项循环链表

#include <stdio.h>
#include "string.h"
#include "ctype.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"

// 操作的结果状态
typedef enum : int {
  Success,
  Error,
} Status;

// 给链表分配的初始存储量
#define MAX_SIZE 20

// 定义元素的类型
typedef int ElementType;

// 定义节点
typedef struct Node {
  ElementType data; // 数据域
  struct Node * next; // 指针域
} Node;

// 定义链表类型
typedef struct Node * LinkedList;

// 1.1，初始化链表
/* 要分两种情况：
 * (1)，传入的链表为空，那么就新建一个节点，并且让该节点的指针域指向自身
 * (2)，传入的链表非空，那么就找到尾结点，然后将尾结点的指针域指向新节点，新节点的指针域指向链表首元结点
 */
Status initLinkedList1(LinkedList *list) {
  int scanedItem;
  printf("请依次输入节点的值，输入0结束");
  while (1) { // 该while循环的退出条件是，输入0
    scanf("%d", &scanedItem); // 控制台输入数字
    if (scanedItem == 0) { // 停止输入，退出循环
      break;
    }
    
    if (*list == NULL) {// 如果传入的链表是空的
      // 新建一个节点
      LinkedList node = malloc(sizeof(Node));
      if (!node) {
        exit(0);
      }
      node->data = scanedItem;
      // 将该节点的指针域指向其自身
      node->next = node;
      // 将该节点配置为链表的首元结点
      *list = node;
    } else { // 如果链表非空
      // 找到尾结点
      LinkedList tailNode;
      for (tailNode = *list; tailNode->next != *list; tailNode = tailNode->next);
      // 新建一个节点
      LinkedList node = malloc(sizeof(Node));
      if (!node) {
        exit(0);
      }
      node->data = scanedItem;
      // 将新节点的指针域指向首元结点
      node->next = *list;
      // 将尾结点的指针域指向新节点
      tailNode->next = node;
    }
  }
  
  return Success;
}

// 1.2，初始化链表
/*
 1.1那种初始化链表的方式，每一次都需要通过循环遍历找到尾结点，接下来我通过一个临时变量来记录尾结点
 思路跟1.1还是一样的，也是分两种情况：
 （1）如果链表之前就是空的，那么新增节点，并且将该节点的指针域指向自身，然后将链表指针指向该节点
 （2）如果链表已经存在，那么就找到链表的尾结点，然后将尾结点的指针域赋值给新节点的指针域，并且将尾结点的指针域指向新节点
 */
Status initLinkedList2(LinkedList *list) {
  printf("请依次输入链表元素值，输入0结束：\n");
  int scanedItem;
  LinkedList tailNode = NULL; // 通过tailNode记录尾结点，这样就不需要每次都通过循环遍历来查找尾结点了
  while (1) { //当输入0的时候，跳出循环
    scanf("%d", &scanedItem);
    if (scanedItem == 0) {
      break;
    }
    
    if ((*list) == NULL) { // 如果链表为空
      // 新建一个节点，并将该节点的指针域指向其自身
      LinkedList node = malloc(sizeof(Node));
      if (!node) {
        return  Error;
      }
      node->data = scanedItem;
      node->next = node;
      // 将该节点设置为链表的首元结点
      *list = node;
      // 给尾结点赋值
      tailNode = node;
    } else { // 如果链表非空
      // 创建一个新的节点，并且将新节点的指针域指向首元结点
      LinkedList node = malloc(sizeof(Node));
      if (!node) {
        return Error;
      }
      node->data = scanedItem;
      node->next = *list;
      // 将尾结点的指针域指向新节点
      tailNode->next = node;
      // 更新尾结点
      tailNode = node;
    }
  }
  
  return  Success;
}

// 2，打印链表
Status printLinkedList(LinkedList list){
  if (list == NULL) {
    printf("当前链表为空\n");
    return Error;
  }
  
  printf("当前链表元素为:\n");
  LinkedList tempNode = list;
  do {
    printf("%d\n", tempNode->data);
    tempNode = tempNode->next;
  } while (tempNode != list);
  
  return Success;
}

// 3，往循环链表中插入数据
/*
 1，如果插入的位置在第一位，那么就将新节点的指针域指向当前的首元结点，然后将新节点设置为首元结点，还要找到尾结点，然后将尾结点的指针域指向新节点
 2，如果插入的位置不在第一位，那么就找到插入位置的前驱结点，然后将新节点的指针域指向当前前驱结点的后继节点，然后将前驱节点的指针域指向新节点
 3，如果插入的位置超过了链表长度，则自动插入到表尾。
 */
Status insert(LinkedList *list, int index, ElementType element) {
  if (index < 1) {
    return Error;
  }
  
  if (index == 1) {
    // 新建节点，并且将新节点的后继节点设置为当前的首元结点
    LinkedList node = malloc(sizeof(Node));
    if (!node) {
      return  Error;
    }
    node->data = element;
    node->next = *list;
    // 找到尾结点，并且将尾结点的指针域指向新节点
    LinkedList tailNode;
    for (tailNode = *list; tailNode->next != *list; tailNode = tailNode->next);
    tailNode->next = node;
    // 将新节点设置为首元结点
    *list = node;
  } else {
    //找到插入位置的上一个节点（如果插入位置超过链表长度，则将新节点放到表尾）
    LinkedList previousNode;
    int i;
    for (previousNode = *list, i = 2; (previousNode->next != *list) && i < index; previousNode = previousNode->next, i++);
    //新建节点，并且将新节点的后继节点设置为当前的前驱结点的后继
    LinkedList node = malloc(sizeof(Node));
    if (!node) {
      return Error;
    }
    node->data = element;
    node->next = previousNode->next;
    // 将当前的前驱结点的后继节点设置为新节点
    previousNode->next = node;
    
  }
  
  return  Success;
}

// 4，删除单项循环链表中的元素
Status deleteElement(LinkedList *list, int index) {
  //链表中没有节点
  if (*list == NULL) {
    return Error;
  }
  
  if (index == 1) { // 如果删除的是首元结点
    // 如果链表中只有一个首元结点了，则直接将链表置空
    if ((*list)->next == *list) {
      *list = NULL;
      return Success;
    }
    
    //如果链表中有两个以及两个以上的节点
    // 找到待删除的首元结点
    LinkedList toDeleteNode = *list;
    // 找到链表的尾结点，并且将尾结点的指针域指向原首元结点的下一个节点
    LinkedList tailNode;
    for (tailNode = *list; tailNode->next != *list; tailNode = tailNode->next);
    tailNode->next = toDeleteNode->next;
    //将当前首元结点的下一个节点设置为链表的首元结点
    *list = toDeleteNode->next;
    //释放节点内存
    free(toDeleteNode);
  } else { // 如果删除的是其他位置
    //找到待删除的节点的上一个节点
    LinkedList previousNode;
    int i;
    for (previousNode = *list, i = 2; previousNode->next->next != *list && i < index; previousNode = previousNode->next, i++);
    //将前驱结点的next指向待删除节点的next
    LinkedList toDeleteNode = previousNode->next;
    previousNode->next = toDeleteNode->next;
    //释放待删除节点的内存
    free(toDeleteNode);
  }
  
  return Success;
}

// 5，查询循环链表中的值
int findValue(LinkedList list, int value) {
  int index = 1;
  LinkedList tempNode = list;
  // 找寻值为value的节点
  while (tempNode->data != value && tempNode->next != list) {
    tempNode = tempNode->next;
    index++;
  }
  
  //对尾结点做特殊处理
  if (tempNode->next == list && tempNode->data != value) {
    return  -1;
  }
  
  return index;
}