链表 - Link List

C 语言课设——成绩管理系统，写了一个链表的模板，拿来这里记录一下
氵 了 800+ lines，好像也没什么意思。。。

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// T 是宏定义或者类型别名，实现伪泛型

/**
 * 链表节点
 */

typedef struct __LNode {
  struct __LNode* next;  // 后继节点
  struct __LNode* prev;  // 前驱节点
  T data;                // 数据区, T是数据类型
} LinkListNode_t;

/**
 * 链表
 */
typedef struct {
  LinkListNode_t* headPtr;  // 头指针
  LinkListNode_t* tailPtr;  // 尾指针
  int len;
} LinkList_t;

typedef LinkList_t* LinkList;  // 链表指针

/**
 * 找链表中满足“升序”定义的最小上界
 * data 是数据指针，因为需要比较，所以无需值传递
 *
 * compareFunction是判断是否升序的函数，返回int，非0即为满足，接受两个参数，
 * 类型为const T*，const *为底层const，表示这个指针指向T类型的常量
 * 因为比较时不应该修改值
 *
 * 如果未找到LUB,则返回NULL
 */

LinkListNode_t* findLeastUpperBond(const LinkList linkListPtr, const T* data,
                                   int (*compareFunction)(const T*, const T*)) {
  assert(
      linkListPtr != NULL &&
      linkListPtr->headPtr !=
          NULL);  // assert是断言，判断条件是否满足，不满足则报错, 异常退出程序
  LinkListNode_t* cur = linkListPtr->headPtr;
  while (cur != NULL && !compareFunction(data, &cur->data)) cur = cur->next;
  return cur;
}

// 链表类型的初始化，这里不是真正的建链，仅初始化LinkList结构体

LinkList createLinkList() {
  LinkList linkListPtr = malloc(sizeof(LinkList_t));
  assert(linkListPtr);
  linkListPtr->headPtr = NULL;
  linkListPtr->tailPtr = NULL;
  linkListPtr->len = 0;
  assert(linkListPtr != NULL);
  return linkListPtr;
}

/**
 * 在一个链表中的节点“后”插入新节点
 */
void appendNode(LinkListNode_t* const linkListNodePtr, const T data) {
  assert(linkListNodePtr != NULL);
  // 动态内存申请，mannual allocate =
  // malloc,申请成功返回正确地址，失败则返回NULL
  LinkListNode_t* newLinkListNode = malloc(sizeof(LinkListNode_t));
  assert(newLinkListNode != NULL);
  newLinkListNode->next = linkListNodePtr->next;
  newLinkListNode->data = data;
  newLinkListNode->prev = linkListNodePtr;
  // 如果后继不为NULL，那么也需要修改它的前驱节点为新节点
  if (linkListNodePtr->next != NULL)
    linkListNodePtr->next->prev = newLinkListNode;
  linkListNodePtr->next = newLinkListNode;
}

/**
 * 有序插入”一个“节点，升序由compareFunction定义，同上
 */
void insertNodeByOrder(LinkList linkListPtr, const T data,
                       int (*compareFunction)(const T*, const T*)) {
  LinkListNode_t* p = findLeastUpperBond(linkListPtr, &data, compareFunction);
  if (p != NULL) {
    appendNode(p->prev, data);
    if (p == linkListPtr->headPtr)
      linkListPtr->headPtr = linkListPtr->headPtr->prev;
  } else {
    appendNode(linkListPtr->tailPtr, data);
    linkListPtr->tailPtr = linkListPtr->tailPtr->next;
  }
  ++linkListPtr->len;
}

/**
 * 删除某一链表节点
 */
void deleteLinkListNode(LinkList linkListPtr, LinkListNode_t* linkListNodePtr) {
  assert(linkListNodePtr != NULL);
  // q -> p -> r  => q -> r
  linkListNodePtr->prev->next = linkListNodePtr->next;
  // 判断是否有后继，有后继则需要更新其前驱
  if (linkListNodePtr->next != NULL)
    linkListNodePtr->next->prev = linkListNodePtr->prev;
  // 头删
  if (linkListPtr->headPtr == linkListNodePtr) {
    linkListPtr->headPtr = linkListPtr->headPtr->next;
  }
  // 尾删
  else if (linkListPtr->tailPtr == linkListNodePtr) {
    linkListPtr->tailPtr = linkListNodePtr->prev;
  }
  --linkListPtr->len;
  free(linkListNodePtr);
}

/**
 * 有序插入“多个”节点
 *
 * datas 是数据数组的地址指针
 *
 * n 是数组长度
 */
void insertNodesByOrder(LinkList linkListPtr, const T* datas, int n,
                        int (*compareFunction)(const T*, const T*)) {
  for (int i = 0; i < n; i++) {
    insertNodeByOrder(linkListPtr, datas[i], compareFunction);
  }
}

/**
 * 初始化链表，这里是真正的建链
 */
void initializeLinkList(const LinkList linkListPtr, T* datas, const int n,
                        int (*compareFunction)(const T*, const T*)) {
  assert(n > 0);  // 至少有一个元素，否则无法建链
  assert(linkListPtr != NULL);
  LinkListNode_t* dummy = malloc(sizeof(
      LinkListNode_t));  // dummy节点是为了方便实现插入，这样头节点也有前驱
  assert(dummy != NULL);
  linkListPtr->headPtr = malloc(sizeof(LinkListNode_t));
  assert(linkListPtr->headPtr != NULL);
  dummy->prev = NULL;
  dummy->next = linkListPtr->headPtr;
  linkListPtr->headPtr->next = NULL;
  linkListPtr->headPtr->prev = dummy;
  linkListPtr->tailPtr = linkListPtr->headPtr;
  linkListPtr->headPtr->data = datas[0];
  linkListPtr->len = 1;
  for (int i = 1; i < n; i++) {
    insertNodeByOrder(linkListPtr, datas[i], compareFunction);
  }
}

/**
 * 递归回收链表节点空间
 */
void destoryLinkListNode(LinkListNode_t* linkListNodePtr) {
  if (linkListNodePtr != NULL) destoryLinkListNode(linkListNodePtr->next);
  free(linkListNodePtr);
}

/**
 * 回收链表空间
 */
void destoryLinkList(LinkList linkListPtr) {
  assert(linkListPtr != NULL && linkListPtr->headPtr != NULL);
  destoryLinkListNode(linkListPtr->headPtr);
  linkListPtr->headPtr = NULL;
  linkListPtr->tailPtr = NULL;
  linkListPtr->len = 0;
}

/**
 * 前向遍历，callback是回调函数，或者说当遇到下一个节点时，需要执行一次的函数，这样做可以解耦遍历，以复用代码
 *
 * callback 接收一个const T*指针
 */
void forwardTraversal(LinkList linkListPtr, int (*callback)(const T*)) {
  assert(linkListPtr != NULL);
  if (linkListPtr->headPtr != NULL) {
    LinkListNode_t* cur = linkListPtr->headPtr;
    while (cur != linkListPtr->tailPtr->next) {
      if (!callback(&cur->data)) break;
      cur = cur->next;
    }
  }
}

/**
 * 反向遍历，callback是回调函数
 *
 * callback 接收一个const T*指针
 */
void reverseTraversal(LinkList linkListPtr, int (*callback)(const T*)) {
  assert(linkListPtr != NULL);
  if (linkListPtr->tailPtr != NULL) {
    LinkListNode_t* cur = linkListPtr->tailPtr;
    while (cur != linkListPtr->headPtr->prev) {
      if (!callback(&cur->data)) break;
      cur = cur->prev;
    }
  }
}