线性表可执行代码

1. 顺序表-数组

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

#define MAX_SIZE 10 // 定义最大长度
typedef struct {
  int data[MAX_SIZE]; // 用静态的
  int length; // 顺序表的当前长度
} SqList; // 顺序表的类型定义

// 初始化顺序表
void InitList (SqList &L) {
  L.length = 0; // 顺序表初始长度为 0
}

// 在 L 的位序 i 处插入元素 e
// 注意区分【位序】和【下标】，位序从1开始，下标从0开始
bool ListInsert(SqList &L, int i, int e) {
  // 判断i的范围是否有效
  if (i < 1 || i > L.length + 1)
    return false;
  // 当前存储的元素已达到最大值，不能插入
  if (L.length >= MAX_SIZE)
    return false;
  // 将第i个元素及之后的元素后移
  for (int j = L.length; j >= i; j--) {
    L.data[j] = L.data[j - 1];
  }
  // 在位置 i 处放入 e
  L.data[i - 1] = e;
  // 长度加1
  L.length++;
  return true;
}

// 删除顺序表 L 的位序 i，并使用 e 返回删除的值
bool ListDelete (SqList &L, int i, int &e) {
  // 判断 i 的范围是否有效
  if (i < 1 || i > L.length)
    return false;

  // 将被删除的元素赋值给 e
  e = L.data[i - 1];
  // 将第 i 个位置后的元素前移
  for (int j = i; j < L.length; j++) {
    L.data[j - 1] = L.data[j];
  }
  L.length--;
  return true;
}

// 按位序查找，返回的为 值
int ListGetElem (SqList L, int i) {
  // 判断 i 的范围是否有效，-999 为约定的失败代表值可以为任意能代表失败的数
  if (i < 1 || i > L.length)
    return -999;

  return L.data[i - 1];
}

// 按值查找，返回的为位序
int ListLocateElem (SqList L, int e) {
  for (int i = 0; i < L.length; i++) {
    if (L.data[i] == e) {
      // 返回的为 位序，所以是 下标 + 1
      return i + 1;
    }
  }
  return -1;
}

void ListPrint (SqList L) {
  printf("顺序表：");
  for (int i = 0; i < L.length; i++) {
    printf("%d ", L.data[i]);
  }
  printf("\n");
}


// 在尾部插入
bool ListInsertTail (SqList &L, int e) {
  // 当前存储的元素已达到最大值，不能插入
  if (L.length >= MAX_SIZE)
    return false;

  L.data[L.length] = e;
  L.length = L.length + 1;
}

int main () {
  // 声明一个顺序表
  SqList L;
  // 初始化顺序表
  InitList(L);

  ListInsert(L, 1, 1);
  ListInsert(L, 1, 2);
  ListInsert(L, 1, 3);
  ListInsert(L, 1, 4);
  // 超出 length，并没有插入成功
  ListInsert(L, 8, 7);
  ListPrint(L);

  int delValue;
  ListDelete(L, 1, delValue);
  ListPrint(L);
  return 0;
}

1. 单链表-不带头结点

#include <stdio.h>
#include<stdlib.h>
typedef struct LNode {
    int data;
    struct LNode * next;
} LNode, *LinkList;

// 初始化链表
bool List_Init (LinkList &pHead) {
    pHead = NULL;
    return true;
}

// 判断单链表是否为空
bool List_Empty (LinkList pHead) {
    return pHead == NULL;
}

// 获取单链表有效数据节点个数
int List_Length (LinkList pHead)
{
  int count = 0;
  for (LNode *p = pHead; p != NULL; p = p->next)
    count++;
  return count;
}


// 创建链表，头插结果为倒叙
LinkList List_Create(LinkList &pHead) {
    LNode *pTemp; int x;
    scanf("%d", &x);
    while (x != 999) {
        pTemp = (LNode *)malloc(sizeof(LNode));
        pTemp->data = x;
        pTemp->next = pHead;
        pHead = pTemp;
        scanf("%d", &x);
    }
    return pHead;
}


// 按位序插入，i=1插在表头，i=length+1插在表尾
bool List_Insert(LinkList &pHead, int i, int e) {
    if (i < 1 || i > List_Length(pHead) + 1) return false;
    LNode *pTemp = (LNode *)malloc(sizeof(LNode));
    if (i == 1) { // 插入第1个结点的操作
        pTemp->data = e;
        pTemp->next = pHead;
        pHead = pTemp;
        return true;
    }
    LNode *p; // 指针p指向的为当前扫描到的结点
    int j = 1; // 当前p指向的是第几个结点
    p = pHead; // p 指向第1个结点（注意：不是头节点）
    while (p != NULL && j < i - 1) { // 循环找到要插入位置的前驱结点
        p = p->next;
        j++;
    }
    pTemp->data = e;
    pTemp->next = p->next;
    p->next = pTemp;
    return true;
}


// 通过值获取结点和位序
LNode* List_Get_Elem (LinkList pHead, int e, int &i) {
  i = 1;
  LNode *p = pHead;
  while(p != NULL && p->data != e) {
      p = p->next;
      i = i + 1;
  }
  return p;
}


// 按位序删除，i=1删表头，i=length删头尾
bool List_Del (LinkList &pHead, int i) {
    if (i < 1 || i > List_Length(pHead)) return false;
    LNode *p = pHead; // p 指向表头
    if (i == 1) { // 删除第一个结点
        pHead = p->next;
        free(p);
        return true;
    }
    // 找到待删除位序的前一位结点，i==1已处理，故从j=2开始
    for (int j = 2; j < i; j++)
        p = p->next;
    LNode *q = p->next; // 待删除结点
    p->next = q->next; // p->next q q->next 跳过q
    free(q);
    return true;
}


// 打印链表所有值
void List_Show (LinkList pHead) {
    LNode *node = pHead;
    printf("链表值：");
    do {
      printf("%d、", node->data);
      node = node->next;
    } while(node != NULL);
    printf("\n");
}

int main () {
    LinkList pHead;
    List_Init(pHead);
    printf("链表判空：%s\n", List_Empty(pHead) ? "空" : "非空");
    List_Create(pHead);
    List_Show(pHead);
    printf("链表长度：%d\n\n", List_Length(pHead));

    printf("位序为1(头插)，插入：0\n");
    List_Insert(pHead, 1, 0);
    List_Show(pHead);
    printf("链表长度：%d\n\n", List_Length(pHead));

    printf("位序为%d(尾插)，插入：99\n", List_Length(pHead) + 1);
    List_Insert(pHead, List_Length(pHead) + 1, 99);
    List_Show(pHead);
    printf("链表长度：%d\n\n", List_Length(pHead));

    printf("删除位序为1(头删)\n");
    List_Del(pHead, 1);
    List_Show(pHead);
    printf("链表长度：%d\n\n", List_Length(pHead));

    printf("删除位序为%d(尾插)\n", List_Length(pHead));
    List_Del(pHead, List_Length(pHead));
    List_Show(pHead);
    printf("链表长度：%d\n\n", List_Length(pHead));

    printf("获取值为：5的结点位序\n");
    int i = -1; // -1 为未找到
    LNode * p5 = List_Get_Elem(pHead, 5, i);
    printf("值为5的结点位序为：%d\n\n", i);

    printf("链表判空：%s\n", List_Empty(pHead) ? "空" : "非空");
    return 0;
}

1. 单链表-带头结点

#include <stdio.h>
#include<stdlib.h>
typedef struct LNode {
  int data;
  struct LNode * next;
} LNode, *LinkList;

// 初始化链表
bool List_Init (LinkList &pHead) {
  pHead = (LNode *) malloc(sizeof(LNode)); // 为头结点分配内存并将地址存储在pHead中。
  if (pHead == NULL) return false; // 检查内存分配是否成功（pHead不为NULL）。
  pHead->next = NULL; // 初始化头结点的'next'指针为NULL，因为它是链表中唯一的节点。
  return true;
}

// 判断单链表是否为空
bool List_Empty (LinkList pHead) {
  return pHead->next == NULL; // 检查头结点的'next'指针是否为NULL，如果是，则链表为空。
}

// 获取单链表有效数据节点个数
int List_Length (LinkList pHead) {
  int count = 0; // 用于计数有效节点的变量
  for (LNode *p = pHead->next; p != NULL; p = p->next) // 从头结点的下一个节点开始，遍历链表直到链表结束（节点为NULL）。
    count++; // 每经过一个节点，有效节点数量加1。
  return count;
}

// 创建链表，头插法结果为倒叙
LinkList List_Create(LinkList &pHead) {
  LNode *pTemp; int x; // 临时节点指针
  scanf("%d", &x);
  while (x != 999) {
    pTemp = (LNode *)malloc(sizeof(LNode)); // 分配内存并创建新节点
    pTemp->data = x;
    pTemp->next = pHead->next; // 新节点的指针指向当前头节点的下一个节点
    pHead->next = pTemp; // 头指针指向新节点，使其成为新的头节点
    scanf("%d", &x);
  }
  return pHead; // 返回带头结点的链表头指针
}

// 创建链表-通过尾插法
LinkList List_Create_Tail_Insert(LinkList &pHead) {
  LNode *pTemp; // 临时节点指针
  LNode *pTail = pHead; // 尾节点指针，初始指向头结点
  int x; // 用于存储输入的数据
  scanf("%d", &x);
  while (x != 999) {
    pTemp = (LNode *)malloc(sizeof(LNode)); // 分配内存并创建新节点
    pTemp->data = x; // 尾节点的下一个指针指向新节点
    pTail->next = pTemp; // 更新尾节点指针，使其指向新节点
    pTail = pTemp; // 读取下一个数据
    scanf("%d", &x);
  }
  pTail->next = NULL; // 尾节点的下一个指针置为 NULL，表示链表结束
  return pHead; // 返回带头结点的链表头指针
}

// 按位序插入，i=1插在表头，i=length+1插在表尾
bool List_Insert(LinkList &pHead, int i, int e) {
  if (i < 1 || i > List_Length(pHead) + 1) return false;  // 检查插入位置是否有效
  int j = 0; // 当前p指向的是第几个结点
  LNode *p = pHead; // p 指向头结点
  while (p != NULL && j < i - 1) { // 循环找到要插入位置的前驱结点，直到找到前驱结点或者链表结束
    p = p->next;
    j++;
  }
  LNode *pTemp = (LNode *)malloc(sizeof(LNode));
  pTemp->data = e;
  pTemp->next = p->next; // 将新节点的'next'指向p的下一个节点
  p->next = pTemp; // 更新p的'next'指向新节点，完成插入操作。
  return true;
}

// 通过值获取结点和其位序
LNode* List_Get_Elem (LinkList pHead, int e, int &i) {
  i = 1;
  LNode *p = pHead->next; // p指向第一个数据节点
  while(p != NULL && p->data != e) {
    p = p->next;
    i = i + 1;
  }
  return p;
}

// 按位序删除，i=1删表头，i=length删头尾
bool List_Del (LinkList &pHead, int i) {
  if (i < 1 || i > List_Length(pHead)) return false;
  LNode *p = pHead;
  // 找到待删除位序的前一位结点，i==1已处理，故从j=2开始
  for (int j = 0; j < i - 1; j++)
    p = p->next;
  LNode *q = p->next; // 待删除结点
  p->next = q->next; // q->next p p->next 跳过p
  free(q);
  return true;
}

// 打印链表所有值
void List_Show (LinkList pHead) {
  LNode *node = pHead->next;
  printf("链表值：");
  while (node != NULL) {
    printf("%d、", node->data);
    node = node->next;
  }
  printf("\n");
}

int main () {
  LinkList pHead;
  List_Init(pHead);
  printf("链表判空：%s\n", List_Empty(pHead) ? "空" : "非空");

  // 头插法创建
  List_Create(pHead);
  List_Show(pHead);
  printf("链表长度：%d\n\n", List_Length(pHead));

  printf("位序为1(头插)，插入：0\n");
  List_Insert(pHead, 1, 0);
  List_Show(pHead);
  printf("链表长度：%d\n\n", List_Length(pHead));

  printf("位序为%d(尾插)，插入：99\n", List_Length(pHead) + 1);
  List_Insert(pHead, List_Length(pHead) + 1, 99);
  List_Show(pHead);
  printf("链表长度：%d\n\n", List_Length(pHead));

  printf("删除位序为1(头删)\n");
  List_Del(pHead, 1);
  List_Show(pHead);
  printf("链表长度：%d\n\n", List_Length(pHead));

  printf("删除位序为%d(尾删)\n", List_Length(pHead));
  List_Del(pHead, List_Length(pHead));
  List_Show(pHead);
  printf("链表长度：%d\n\n", List_Length(pHead));

  printf("获取值为：5的结点位序\n");
  int i = -1; // -1 为未找到
  LNode * p5 = List_Get_Elem(pHead, 5, i);
  printf("值为5的结点位序为：%d\n\n", p5 != NULL ? i : -1);

  printf("链表判空：%s\n", List_Empty(pHead) ? "空" : "非空");

  // 尾插法创建
  LinkList pHead1;
  List_Init(pHead1);

  List_Create_Tail_Insert(pHead1);
  printf("尾插法创建链表：\n");
  List_Show(pHead1);
  return 0;
}

1. 双链表--不带头结点

#include <stdio.h>
#include<stdlib.h>
using namespace std;

// 定义双链表结构
typedef struct DNode {
  int data; // 数据
  struct DNode *prior, *next; // 前驱和后继指针
} DNode, *DLinkList;

// 初始化链表
bool DList_Init(DLinkList &pHead) {
  pHead = NULL; // 不再创建头结点
  return true;
}

// 判断双链表是否为空（不带头节点）
bool DList_Empty(DLinkList pHead) {
  return pHead == NULL;
}

// 获取链表有效数据节点个数
int DList_Length(DLinkList pHead) {
  int count = 0;
  DNode *p = pHead;
  while (p != NULL) { // 当指针p不为空时，即链表不为空时
    count++;
    p = p->next; // 将指针p移动到下一个节点
  }
  return count;
}


// 创建双链表，头插结果为倒序（不带头节点）
DLinkList DList_Create(DLinkList &pHead) {
  pHead = NULL; // 初始化链表头指针为空，表示链表为空
  int x;
  scanf("%d", &x);
  DNode *pTemp; // 创建一个临时节点指针pTemp
  while (x != 999) {
    pTemp = (DNode *)malloc(sizeof(DNode));
    pTemp->data = x; // 将新节点的数据域设置为x
    pTemp->prior = NULL; // 新节点的prior为空，因为是头插法，头始终为空
    pTemp->next = pHead; // 新节点的next指向链表当前头节点
    if (pHead != NULL) {
      pHead->prior = pTemp; // 设置原头节点的prior指向新节点
    }
    pHead = pTemp; // 更新链表头指针为新节点
    scanf("%d", &x);
  }
  return pHead; // 返回创建好的双链表的头指针
}


// 按位序插入，i=1插在表头，i=length+1插在表尾
bool DList_Insert(DLinkList &pHead, int i, int e) {
  // 检查插入位置的有效性
  if (i < 1 || i > DList_Length(pHead) + 1) return false;
  // 创建一个新节点pTemp并分配内存
  DNode *pTemp = (DNode *)malloc(sizeof(DNode));
  pTemp->data = e;

  // 如果插入位置是链表头
  if (i == 1) {
    pTemp->next = pHead; // 新节点的next指向当前头节点
    pTemp->prior = NULL; // 新节点的prior为空，因为是头插法
    if (pHead != NULL) { // 如果链表不为空
      pHead->prior = pTemp; // 设置原头节点的prior指向新节点
    }
    pHead = pTemp; // 更新链表头指针为新节点
  } else { // 插入位置不在表头
    int j = 1;
    DNode *p = pHead; // 创建一个指针p，指向链表头节点
    while (j < i - 1) { // 循环找到要插入位置的前驱结点
      p = p->next;
      j++;
    }
    pTemp->next = p->next; // 新节点的next指向前驱结点的下一个节点
    pTemp->prior = p;  // 新节点的prior指向前驱结点
    if (p->next != NULL) { // 如果前驱结点的下一个节点存在
      p->next->prior = pTemp; // 设置前驱结点的下一个节点的prior指向新节点
    }
    p->next = pTemp; // 设置前驱结点的next指向新节点
  }
  return true;
}


// 通过值获取结点和其位序
DNode* DList_Get_Elem(DLinkList pHead, int e, int &i) {
  i = 1;
  DNode *p = pHead; // 创建一个指针p，指向链表头节点
  while (p != NULL && p->data != e) { // 循环查找值为e的节点或到达链表尾部
    p = p->next; // 移动到下一个节点
    i++;
  }
  return p;// 返回找到的节点，如果没有找到则返回NULL
}


// 按位序删除，i=1删表头，i=length删头尾
bool DList_Del(DLinkList &pHead, int i) {
   // 检查删除位置的有效性
  if (i < 1 || i > DList_Length(pHead)) return false;

  if (i == 1) { // 如果删除位置是链表头
    DNode *q = pHead; // 创建一个指针q，指向链表头节点
    pHead = pHead->next; // 更新链表头指针为下一个节点
    if (pHead != NULL) { // 如果链表不为空
      pHead->prior = NULL; // 设置新头节点的prior为空
    }
    free(q); // 释放原头节点的内存
  } else { // 删除位置不在表头
    int j = 1;
    DNode *p = pHead; // 创建一个指针p，指向链表头节点
    while (j < i - 1) { // 循环找到要删除位置的前驱结点
      p = p->next; // 移动到下一个节点
      j++; // 增加位置计数器
    }
    DNode *q = p->next; // 创建一个指针q，指向待删除的节点
    p->next = q->next; // 前驱结点的next指向待删除节点的下一个节点
    if (q->next != NULL) { // 如果待删除节点的下一个节点存在
      q->next->prior = p; // 设置待删除节点的下一个节点的prior指向前驱结点
    }
    free(q); // 释放待删除节点的内存
  }
  return true;
}


// 打印链表所有值
void DList_Show(DLinkList pHead) {
  DNode *node = pHead;
  printf("链表值(从头遍历)：");
  while (node != NULL) {
    printf("%d、", node->data);
    node = node->next;
  }
  printf("\n");
}

// 打印链表所有值，从尾到头
// 双链表是可以走回头路的，所以可以从最后一个结点往前遍历
void DList_Show_Back(DLinkList pHead) {
  DNode *node = pHead;
  while (node->next != NULL) {
    node = node->next;
  }
  printf("链表值(从尾遍历)：");
  while (node != NULL) { // 从最后一个节点开始循环，一直到链表头
    printf("%d、", node->data);
    node = node->prior;
  }
  printf("\n");
}

int main() {
  DLinkList pHead;
  DList_Init(pHead);
  printf("链表判空：%s\n", DList_Empty(pHead) ? "空" : "非空");

  DList_Create(pHead);
  DList_Show(pHead);
  DList_Show_Back(pHead);
  printf("链表长度：%d\n\n", DList_Length(pHead));

  printf("位序为1(头插)，插入：0\n");
  DList_Insert(pHead, 1, 0);
  DList_Show(pHead);
  printf("链表长度：%d\n\n", DList_Length(pHead));

  printf("位序为%d(尾插)，插入：99\n", DList_Length(pHead) + 1);
  DList_Insert(pHead, DList_Length(pHead) + 1, 99);
  DList_Show(pHead);
  printf("链表长度：%d\n\n", DList_Length(pHead));

  printf("删除位序为1(头删)\n");
  DList_Del(pHead, 1);
  DList_Show(pHead);
  DList_Show_Back(pHead);
  printf("链表长度：%d\n\n", DList_Length(pHead));

  printf("删除位序为%d(尾删)\n", DList_Length(pHead));
  DList_Del(pHead, DList_Length(pHead));
  DList_Show(pHead);
  DList_Show_Back(pHead);
  printf("链表长度：%d\n\n", DList_Length(pHead));

  printf("获取值为：5的结点位序\n");
  int i = -1;
  DNode *p5 = DList_Get_Elem(pHead, 5, i);
  printf("值为5的结点位序为：%d\n\n", p5 != NULL ? i : -1);

  printf("链表判空：%s\n", DList_Empty(pHead) ? "空" : "非空");
  return 0;
}

1. 双链表--带头结点

#include <iostream>
using namespace std;
// 定义双链表结构
typedef struct DNode {
  int data; // 数据
  struct DNode *prior, *next; // 前驱和后继指针
} DNode, *DLinkList;

// 初始化链表
bool DList_Init (DLinkList &pHead) {
  pHead = (DNode *) malloc(sizeof(DNode)); // 创建头结点
  if (pHead == NULL) return false; // 内存不足，分配失败
  pHead->prior = NULL; // 普通双链表头结点 prior 始终指向 NULL
  pHead->next = NULL;
  return true;
}

// 判断双链表是否为空（带头节点）
bool DList_Empty (DLinkList pHead) {
  return pHead->next == NULL;
}

// 获取链表有效数据节点个数
int DList_Length (DLinkList pHead)
{
  int count = 0;
  for (DNode *p = pHead->next; p != NULL; p = p->next)
  count++;
  return count;
}


// 创建双链表，头插结果为倒叙（带头节点）
DLinkList DList_Create(DLinkList &pHead) {
  DNode *pTemp; int x;
  scanf("%d", &x);
  while (x != 999) {
    pTemp = (DNode *)malloc(sizeof(DNode));
    pTemp->data = x;
    pTemp->next = pHead->next;
    pTemp->prior = pHead;
    // 不是空链表
    if (pHead->next != NULL) {
      pHead->next->prior = pTemp;
    }
    pHead->next = pTemp;
    scanf("%d", &x);
  }
  return pHead;
}


// 按位序插入，i=1插在表头，i=length+1插在表尾
bool DList_Insert(DLinkList &pHead, int i, int e) {
  if (i < 1 || i > DList_Length(pHead) + 1) return false;
  int j = 0; // 当前p指向的是第几个结点
  DNode *p = pHead; // p 指向头结点
  while (p != NULL && j < i - 1) { // 循环找到要插入位置的前驱结点
    p = p->next;
    j++;
  }
  DNode *pTemp = (DNode *)malloc(sizeof(DNode));
  pTemp->data = e;
  pTemp->next = p->next;
  pTemp->prior = p;
  // 又后续结点，不是空链表
  if (p->next != NULL) {
    p->next->prior = pTemp;
  }
  p->next = pTemp;
  return true;
}


// 通过值获取结点和其位序
DNode* DList_Get_Elem (DLinkList pHead, int e, int &i) {
  i = 1;
  DNode *p = pHead->next;
  while(p != NULL && p->data != e) {
    p = p->next;
    i = i + 1;
  }
  return p;
}


// 按位序删除，i=1删表头，i=length删头尾
bool DList_Del (DLinkList &pHead, int i) {
  if (i < 1 || i > DList_Length(pHead)) return false;
  DNode *p = pHead;
  // 找到待删除位序的前一位结点
  for (int j = 0; j < i - 1; j++)
    p = p->next;

  DNode *q = p->next; // 待删除结点
  p->next = q->next;
  if (q->next != NULL)
    q->next->prior = p;
  free(q);
  return true;
}


// 打印链表所有值
void DList_Show (DLinkList pHead) {
  DNode *node = pHead->next;
  printf("链表值(从头遍历)：");
  while (node != NULL) {
    printf("%d、", node->data);
    node = node->next;
  }
  printf("\n");
}

// 打印链表所有值，从尾到头
void DList_Show_Back (DLinkList pHead) {
  DNode *node = pHead;
  // 先找到尾结点
  while (node->next != NULL) {
    node = node->next;
  }
  printf("链表值(从尾遍历)：");
  while (node->prior != NULL) { // 跳过头结点
    printf("%d、", node->data);
    node = node->prior;
  }
  printf("\n");
}

int main() {
  DLinkList pHead;
  DList_Init(pHead);
  printf("链表判空：%s\n", DList_Empty(pHead) ? "空" : "非空");

  DList_Create(pHead);
  DList_Show(pHead);
  DList_Show_Back(pHead);
  printf("链表长度：%d\n\n", DList_Length(pHead));

  printf("位序为1(头插)，插入：0\n");
  DList_Insert(pHead, 1, 0);
  DList_Show(pHead);
  printf("链表长度：%d\n\n", DList_Length(pHead));

  printf("位序为%d(尾插)，插入：99\n", DList_Length(pHead) + 1);
  DList_Insert(pHead, DList_Length(pHead) + 1, 99);
  DList_Show(pHead);
  printf("链表长度：%d\n\n", DList_Length(pHead));

  printf("删除位序为1(头删)\n");
  DList_Del(pHead, 1);
  DList_Show(pHead);
  DList_Show_Back(pHead);
  printf("链表长度：%d\n\n", DList_Length(pHead));

  printf("删除位序为%d(尾删)\n", DList_Length(pHead));
  DList_Del(pHead, DList_Length(pHead));
  DList_Show(pHead);
  DList_Show_Back(pHead);
  printf("链表长度：%d\n\n", DList_Length(pHead));

  printf("获取值为：5的结点位序\n");
  int i = -1; // -1 为未找到
  DNode * p5 = DList_Get_Elem(pHead, 5, i);
  printf("值为5的结点位序为：%d\n\n", p5 != NULL ? i : -1);

  printf("链表判空：%s\n", DList_Empty(pHead) ? "空" : "非空");
  return 0;
}

1. 循环单链表

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

typedef struct LNode {
  int data;
  struct LNode* next;
} LNode, *LinkList;

// 初始化循环单链表
bool List_Init(LinkList& pHead) {
  pHead = (LNode*)malloc(sizeof(LNode)); // 为头结点分配内存并将地址存储在pHead中。
  if (pHead == NULL) return false; // 检查内存分配是否成功（pHead不为NULL）。
  pHead->next = pHead; // 头结点的next指向自己，形成循环。
  return true;
}

// 判断循环单链表是否为空
bool List_Empty(LinkList pHead) {
  return pHead->next == pHead; // 检查头结点的next指针是否指向自己，如果是，则链表为空。
}

// 获取循环单链表有效数据节点个数
int List_Length(LinkList pHead) {
  int count = 0; // 用于计数有效节点的变量
  LNode* p = pHead->next; // 从头结点的下一个节点开始
  while (p != pHead) { // 遍历链表直到回到头结点
    count++; // 每经过一个节点，有效节点数量加1。
    p = p->next;
  }
  return count;
}

// 创建循环单链表，头插法结果为倒叙
LinkList List_Create(LinkList& pHead) {
  LNode* pTemp; int x; // 临时节点指针
  scanf("%d", &x);
  while (x != 999) {
    pTemp = (LNode*)malloc(sizeof(LNode)); // 分配内存并创建新节点
    pTemp->data = x;
    pTemp->next = pHead->next; // 新节点的指针指向当前头节点的下一个节点
    pHead->next = pTemp; // 头指针指向新节点，使其成为新的头节点
    scanf("%d", &x);
  }
  return pHead; // 返回带头结点的循环单链表头指针
}


// 创建循环单链表-通过尾插法
LinkList List_Create_Tail_Insert(LinkList& pHead) {
  LNode* pTemp; // 临时节点指针
  LNode* pTail = pHead; // 尾节点指针，初始指向头结点
  int x; // 用于存储输入的数据
  scanf("%d", &x);
  while (x != 999) {
    pTemp = (LNode*)malloc(sizeof(LNode)); // 分配内存并创建新节点
    pTemp->data = x; // 尾节点的下一个指针指向新节点
    pTail->next = pTemp; // 更新尾节点指针，使其指向新节点
    pTail = pTemp; // 尾节点指针后移
    scanf("%d", &x);
  }
  pTail->next = pHead; // 尾节点的下一个指针指向头结点，形成循环
  return pHead; // 返回带头结点的循环单链表头指针
}


// 按位序插入，i=1插在表头，i=length+1插在表尾
bool List_Insert(LinkList& pHead, int i, int e) {
  if (i < 1 || i > List_Length(pHead) + 1) return false;  // 检查插入位置是否有效
  int j = 0; // 当前p指向的是第几个结点
  LNode* p = pHead; // p 指向头结点
  while (p != NULL && j < i - 1) { // 循环找到要插入位置的前驱结点，直到找到前驱结点或者链表结束
    p = p->next;
    j++;
  }
  LNode* pTemp = (LNode*)malloc(sizeof(LNode));
  pTemp->data = e;
  pTemp->next = p->next; // 将新节点的next指向p的下一个节点
  p->next = pTemp; // 更新p的next指向新节点，完成插入操作。
  return true;
}


// 通过值获取结点和其位序
LNode* List_Get_Elem(LinkList pHead, int e, int& i) {
  i = 1;
  LNode* p = pHead->next; // p指向第一个数据节点
  while (p != pHead && p->data != e) { // 遍历链表直到回到头结点或者找到目标值
    p = p->next;
    i++;
  }
  if (p == pHead) return NULL; // 若找到头结点，则表示未找到目标值
  return p;
}


// 按位序删除，i=1删表头，i=length删头尾
bool List_Del(LinkList& pHead, int i) {
  if (i < 1 || i > List_Length(pHead)) return false;
  LNode* p = pHead;
  // 找到待删除位序的前一位结点，i==1已处理，故从j=2开始
  for (int j = 0; j < i - 1; j++)
    p = p->next;
  LNode* q = p->next; // 待删除结点
  p->next = q->next; // 跳过待删除结点
  free(q);
  return true;
}


// 打印循环单链表所有值
void List_Show(LinkList pHead) {
  LNode* node = pHead->next;
  printf("循环单链表值：");
  while (node != pHead) {
    printf("%d、", node->data);
    node = node->next;
  }
  printf("\n");
}

int main() {
  LinkList pHead;
  List_Init(pHead);
  printf("循环单链表判空：%s\n", List_Empty(pHead) ? "空" : "非空");

  // 头插法创建
  List_Create(pHead);
  List_Show(pHead);
  printf("循环单链表长度：%d\n\n", List_Length(pHead));

  printf("位序为1(头插)，插入：0\n");
  List_Insert(pHead, 1, 0);
  List_Show(pHead);
  printf("循环单链表长度：%d\n\n", List_Length(pHead));

  printf("位序为%d(尾插)，插入：99\n", List_Length(pHead) + 1);
  List_Insert(pHead, List_Length(pHead) + 1, 99);
  List_Show(pHead);
  printf("循环单链表长度：%d\n\n", List_Length(pHead));

  printf("删除位序为1(头删)\n");
  List_Del(pHead, 1);
  List_Show(pHead);
  printf("循环单链表长度：%d\n\n", List_Length(pHead));

  printf("删除位序为%d(尾删)\n", List_Length(pHead));
  List_Del(pHead, List_Length(pHead));
  List_Show(pHead);
  printf("循环单链表长度：%d\n\n", List_Length(pHead));

  printf("获取值为：5的结点位序\n");
  int i = -1; // -1 为未找到
  LNode* p5 = List_Get_Elem(pHead, 5, i);
  printf("值为5的结点位序为：%d\n\n", p5 != NULL ? i : -1);

  printf("循环单链表判空：%s\n", List_Empty(pHead) ? "空" : "非空");

  // 尾插法创建
  LinkList pHead1;
  List_Init(pHead1);

  List_Create_Tail_Insert(pHead1);
  printf("尾插法创建循环单链表：\n");
  List_Show(pHead1);
  return 0;
}

1. 循环双链表

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

typedef struct DNode {
  int data;
  struct DNode* next;
  struct DNode* prior;
} DNode, *DLinkList;

// 初始化循环双链表
bool List_Init(DLinkList& pHead) {
  pHead = (DNode*)malloc(sizeof(DNode));
  if (pHead == NULL) return false;
  pHead->next = pHead;
  pHead->prior = pHead;
  return true;
}

// 判断循环双链表是否为空
bool List_Empty(DLinkList pHead) {
  return pHead->next == pHead;
}

// 获取循环双链表有效数据节点个数
int List_Length(DLinkList pHead) {
  int count = 0;
  DNode* p = pHead->next;
  while (p != pHead) {
    count++;
    p = p->next;
  }
  return count;
}


// 创建循环双链表，头插法结果为倒叙
DLinkList List_Create(DLinkList& pHead) {
  DNode* pTemp; int x;
  scanf("%d", &x);
  while (x != 999) {
    pTemp = (DNode*)malloc(sizeof(DNode));
    pTemp->data = x;
    pTemp->next = pHead->next;
    pTemp->prior = pHead;

    // 仅当链表为空时 pHead的next的prior指向的pHead自身
    pHead->next->prior = pTemp;
    pHead->next = pTemp;
    scanf("%d", &x);
  }
  return pHead;
}


// 创建循环双链表-通过尾插法
DLinkList List_Create_Tail_Insert(DLinkList& pHead) {
  DNode* pTemp;
  DNode* pTail = pHead;
  int x;
  scanf("%d", &x);
  while (x != 999) {
    pTemp = (DNode*)malloc(sizeof(DNode));
    pTemp->data = x;
    pTemp->next = pHead;
    pTemp->prior = pTail;
    pTail->next = pTemp;
    pHead->prior = pTemp;
    pTail = pTemp;
    scanf("%d", &x);
  }
  return pHead;
}


// 按位序插入，i=1插在表头，i=length+1插在表尾
bool List_Insert(DLinkList& pHead, int i, int e) {
  if (i < 1 || i > List_Length(pHead) + 1) return false;
  int j = 0;
  DNode* p = pHead;
  while (p != NULL && j < i - 1) {
    p = p->next;
    j++;
  }
  DNode* pTemp = (DNode*)malloc(sizeof(DNode));
  pTemp->data = e;
  pTemp->next = p->next;
  pTemp->prior = p;
  p->next->prior = pTemp;
  p->next = pTemp;
  return true;
}


// 通过值获取结点和其位序
DNode* List_Get_Elem(DLinkList pHead, int e, int& i) {
  i = 1;
  DNode* p = pHead->next;
  while (p != pHead && p->data != e) {
      p = p->next;
      i++;
  }
  if (p == pHead) return NULL;
  return p;
}


// 按位序删除，i=1删表头，i=length删头尾
bool List_Del(DLinkList& pHead, int i) {
  if (i < 1 || i > List_Length(pHead)) return false;
  DNode* p = pHead;

  for (int j = 0; j < i - 1; j++)
      p = p->next;
  DNode* q = p->next;
  p->next = q->next;
  q->next->prior = p;
  free(q);
  return true;
}


// 打印循环双链表所有值
void List_Show(DLinkList pHead) {
  DNode* node = pHead->next;
  printf("循环双链表值：");
  while (node != pHead) {
      printf("%d、", node->data);
      node = node->next;
  }
  printf("
");
}

int main() {
  DLinkList pHead;
  List_Init(pHead);
  printf("循环双链表判空：%s
", List_Empty(pHead) ? "空" : "非空");

  // 头插法创建
  List_Create(pHead);
  List_Show(pHead);
  printf("循环双链表长度：%d

", List_Length(pHead));

  printf("位序为1(头插)，插入：0
");
  List_Insert(pHead, 1, 0);
  List_Show(pHead);
  printf("循环双链表长度：%d

", List_Length(pHead));

  printf("位序为%d(尾插)，插入：99
", List_Length(pHead) + 1);
  List_Insert(pHead, List_Length(pHead) + 1, 99);
  List_Show(pHead);
  printf("循环双链表长度：%d

", List_Length(pHead));

  printf("删除位序为1(头删)
");
  List_Del(pHead, 1);
  List_Show(pHead);
  printf("循环双链表长度：%d

", List_Length(pHead));

  printf("删除位序为%d(尾删)
", List_Length(pHead));
  List_Del(pHead, List_Length(pHead));
  List_Show(pHead);
  printf("循环双链表长度：%d

", List_Length(pHead));

  printf("获取值为：5的结点位序
");
  int i = -1; // -1 为未找到
  DNode* p5 = List_Get_Elem(pHead, 5, i);
  printf("值为5的结点位序为：%d

", p5 != NULL ? i : -1);

  printf("循环双链表判空：%s
", List_Empty(pHead) ? "空" : "非空");

  // 尾插法创建
  DLinkList pHead1;
  List_Init(pHead1);

  List_Create_Tail_Insert(pHead1);
  printf("尾插法创建循环双链表：
");
  List_Show(pHead1);
  return 0;
}

1. 静态链表

#include <stdio.h>
#define MAX_SIZE 7

typedef int ElemType;

// 定义静态链表结点
typedef struct {
  ElemType data; // 数据元素
  // 下一个结点的索引
  // -1 表示当前结点是链表的尾结点
  // -2，则表示当前结点是空闲结点
  int next;
} SLinkList[MAX_SIZE];


// 初始化静态链表
void Initialize(SLinkList list) {
  // 0号结点充当“头结点”，不具体存放数据
  list[0].next = -1;

  // 初始化其他结点的next为特殊值-2，表示结点空闲
  for (int i = 1; i < MAX_SIZE; i++) {
    list[i].next = -2;
  }
}


// 插入操作
int Insert(SLinkList list, int position, ElemType data) {
  // 找到一个空闲结点
  int freeNode = -1;
  for (int i = 1; i < MAX_SIZE; i++) {
    if (list[i].next == -2) {
      freeNode = i;
      break;
    }
  }

  // 如果没有空闲结点，插入失败
  if (freeNode == -1) {
    printf("插入失败，静态链表已满\n");
    return 0;
  }

  int current = 0; // 从头结点开始
  int count = 0;

  // 找到要插入位置的前一个结点
  // 直到找到前一个结点或者达到链表的末尾
  while (count < position && list[current].next != -1) {
    current = list[current].next;
    count++;
  }

  // 插入新结点
  list[freeNode].data = data; // 将数据存储在新结点
  list[freeNode].next = list[current].next; // 将新结点指向原位置的下一个结点
  list[current].next = freeNode; // 更新前一个结点的指向，使其指向新结点

  return 1;
}


// 按值查找操作
int FindByValue(SLinkList list, ElemType value) {
  int current = list[0].next; // 从第一个数据结点开始
  int position = 1; // 初始化位置

  while (current != -1) {
    // 比较当前结点的数据与目标值
    if (list[current].data == value) {
      // 找到匹配值，返回位置
      return position;
    }

    // 没有找到，继续遍历下一个结点
    current = list[current].next;
    position++;
  }

  // 没有找到匹配值，返回 -1 表示未找到
  return -1;
}


// 删除操作
int Delete(SLinkList list, int position) {
  int current = 0; // 从头结点开始
  int count = 0;

  // 找到要删除位置的前一个结点
  // 直到找到前一个结点或者达到链表的末尾
  while (count < position && list[current].next != -1) {
    current = list[current].next; // 移动到下一个结点
    count++;
  }

  // 判断是否找到要删除的位置
  if (list[current].next == -1 || count < position) {
    printf("删除失败，位置无效\n");
    return 0;
  }

  // 要删除的结点
  int toBeDeleted = list[current].next;

  // 更新前一个结点的指向，跳过要删除的结点
  list[current].next = list[toBeDeleted].next;

  // 标记要删除的结点为空闲结点
  list[toBeDeleted].data = NULL;
  list[toBeDeleted].next = -2;

  return 1;
}


// 输出静态链表
void PrintList(SLinkList list) {
  int current = list[0].next; // 从第一个数据结点开始
  while (current != -1) {
    printf("%d ", list[current].data);
    current = list[current].next;
  }
  printf("\n");
}


int main() {
  SLinkList list;
  Initialize(list);

  Insert(list, 0, 10);
  Insert(list, 1, 20);
  Insert(list, 1, 30);
  Insert(list, 3, 40);

  printf("静态链表内容：\n");
  PrintList(list);

  Delete(list, 1);
  printf("删除第2个元素后的静态链表内容：\n");
  PrintList(list);

  return 0;
}