数据结构（单链表

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

using namespace std;

#define ElemType int

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

// 初始化
bool InitList(LinkList& L) {
  L = (LNode*)malloc(sizeof(LNode));
  if (L == NULL) return false;
  L->next = NULL;
  return true;
}

// 判断是否为空
bool Empty(LinkList L) {
  if (L->next == NULL) return true;
  else return false;
}

// 按位序插入
bool ListInsert(LinkList& L, int i, ElemType e) {
  if (i < 1) return false;

  int j = 0;
  LNode* p = L;
  while (p != NULL && j < i - 1) {  // 找到第 i - 1 个节点
    p = p->next;
    j++;
  }
  if (p == NULL) return false;    // i值不合法
  
  LNode* node = (LNode*)malloc(sizeof(LNode));
  if (node == NULL) return false;

  node->data = e;
  node->next = p->next;
  p->next = node;
  return true;
}

// 指定节点的后插
bool InsertNextNode(LNode* p, ElemType e) {
  LNode* node = (LNode*)malloc(sizeof(LNode));
  if (node == NULL) return false;

  node->data = e;
  node->next = p->next;
  p->next = node;
  return true;
}

// 指定节点的前插
bool InsertPriorNode(LNode* p, ElemType e) {
  LNode* node = (LNode*)malloc(sizeof(LNode));
  if (node == NULL) return false;

  node->data = p->data;
  p->data = e;
  node->next = p->next;
  p->next = node;
  return true;
}

// 按位序删除
bool ListDelete(LinkList& L, int i, ElemType& e) {
  if (i < 1) return false;

  int j = 0;
  LNode* p = L;
  while (p != NULL && j < i - 1) {  // 找到第 i - 1 个节点
    p = p->next;
    j++;
  }
  if (p == NULL) return false;    // i值不合法

  LNode* node = p->next;
  e = node->data;
  p->next = node->next;
  free(node);
  return true;
}

// 指定节点的删除
void DeleteNextNode(LNode* p) {
  LNode* node = p->next;
  p->data = node->data;
  p->next = node->next;
  free(node);
}

// 按位查找
bool GetElem(LinkList L, int i, ElemType& e) {
  if (i < 1) return false;

  int j = 0;
  LNode* p = L;
  while (p != NULL && j < i) {  // 找到第 i 个节点
    p = p->next;
    j++;
  }
  if (p == NULL) return false;    // i值不合法

  e = p->data;

  return true;
}

// 按值查找
int LocateElem(LinkList L, ElemType e) {
  int j = 1;
  LNode* p = L->next;
  while (p != NULL && p->data != e) { // 找到与e相等的节点
    p = p->next;
    j++;
  }
  if (p == NULL) return 0;

  return j;
}

// 求表长度
int Length(LinkList L) {
  int len = 0;
  LNode* p = L->next;
  while (p != NULL) {
    p = p->next;
    len++;
  }

  return len;
}

// 尾插法建立单链表
bool List_TailInsert(LinkList& L) {
  int node;
  scanf_s("%d", &node);
  LNode* p;
  LNode* last = L;
  while (node != 9999) {
    p = (LNode*)malloc(sizeof(LNode));
    if (p == NULL) return false;
    p->data = node;
    last->next = p;
    last = p;

    scanf_s("%d", &node);
  }
  last->next = NULL;
  return true;
}

// 头插法建立单链表
bool List_HeadInsert(LinkList& L) {
  int node;
  scanf_s("%d", &node);
  LNode* p;
  while (node != 9999) {
    p = (LNode*)malloc(sizeof(LNode));
    if (p == NULL) return false;
    p->data = node;
    p->next = L->next;
    L->next = p;

    scanf_s("%d", &node);
  }
  return true;
}

int main() {
  LinkList L;
  // 初始化链表
  if (!InitList(L)) {
    cout << "初始化失败！" << endl;
    return -1;
  }

  // 头插法建立单链表
  cout << "请输入节点数据，以9999结束：" << endl;
  if (!List_HeadInsert(L)) {
    cout << "头插法建立链表失败！" << endl;
    return -1;
  }
  cout << "头插法建立链表成功！" << endl;

  // 输出链表长度
  cout << "链表长度为：" << Length(L) << endl;

  // 输出链表元素
  cout << "链表元素为：";
  LNode* p = L->next; // 第一个节点
  while (p != NULL) {
    cout << p->data << " ";
    p = p->next;
  }
  cout << endl;

  // 在第3个位置插入元素10
  ElemType e;
  if (ListInsert(L, 3, 10)) {
    cout << "在第3个位置插入元素10成功！" << endl;
  }
  else {
    cout << "在第3个位置插入元素10失败！" << endl;
  }

  // 输出链表长度
  cout << "链表长度为：" << Length(L) << endl;

  // 输出链表元素
  cout << "链表元素为：";
  p = L->next; // 第一个节点
  while (p != NULL) {
    cout << p->data << " ";
    p = p->next;
  }
  cout << endl;

  // 删除第2个位置的元素
  if (ListDelete(L, 2, e)) {
    cout << "删除第2个位置的元素成功！删除的元素为：" << e << endl;
  }
  else {
    cout << "删除第2个位置的元素失败！" << endl;
  }

  // 输出链表长度
  cout << "链表长度为：" << Length(L) << endl;

  // 输出链表元素
  cout << "链表元素为：";
  p = L->next; // 第一个节点
  while (p != NULL) {
    cout << p->data << " ";
    p = p->next;
  }
  cout << endl;

  // 释放链表所占内存
  LNode* q;
  while (L != NULL) {
    q = L;
    L = L->next;
    free(q);
  }

  return 0;
}