数据结构（三）线性表 の 单链表

链表的定义

链表（线性表的链式存储结构）是由 n 个结点链结成，第一个结点的储存位置叫做头指针，最后一个结点的指针为空。结点包括数据域和指针域。

基本概念

• 头指针：链表中第一个结点的存储位置。
• 头结点：在单链表的第一格结点前附设的结点。

单链表的定义

链表的每一个结点中只包含一个指针域。

单链表和顺序表的比较

头指针与头结点的异同

头指针

• 头指针是智链表指向第一个结点的指针，若指针有头结点吗，则是指向头结点的指针。
• 头指针具有标识符作用，所以常用头指针冠以链表的名字。
• 无论链表是否为空，头指针均不为空。头指针是链表的必要元素。

头结点

• 头结点是为了操作的统一和方便而设置的，放在第一元素的结点之前，其元素域一般无意义（也可以放链表的长度）。
• 有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作与其它结点的操作就统一了。
• 头结点不一定是链表必须要素。

头插法和尾插法

头插法

把后建立的结点插在头部。用这种方法建立起来的链表的实际顺序与输入顺序刚好向反，输出时为倒序。

struct node *headcreat()
{
    struct node *p,*q,*head;
    head = (struct node*)malloc(sizeof(struct node));
    p = (struct node*)malloc(sizeof(struct node));
    p->next = NULL;  //先让最后一个节点p指向空
    printf("请输入数字，以0结尾：\n");
    do{
        q = (struct node*)malloc(sizeof(struct node));
        scanf("%d",&q->data);
        if(q->data == 0)break;  //输入数字为0时跳出循环，停止操作（0不在链表内）
        L++; //L为全局变量，用于计算链表长度，对于实现功能没有影响
        q->next = p->next;
        p->next = q;
    } while(true);
    head = p;  //头节点head为空
    return (head); 
}

尾插法

将后建立的结点插在链表尾部，这种方法建立起来的链表的实际顺序与输入顺序相同，在对链表顺序有严格要求时，建议使用尾插法.

struct node *tailcreat()
{
 struct node *p,*q,*head;
 int n = 0;
 head = (struct node*)malloc(sizeof(struct node));
 p = (struct node*)malloc(sizeof(struct node));
 printf("请输入数字，以0结尾:\n");
 do{
  q = (struct node*)malloc(sizeof(struct node));
  scanf("%d",&q->data);L++;
  if(q->data == 0)break;
  if(n == 0) //当输入第一个数字时，将这个节点赋值给头节点的指针域
  {
   head->next = q;
   p->next = q;
   p = q;
   n++;
  }
  p->next = q;
  p = q;
 }while(true); 
 p->next = NULL; //容易忽略，后果就是在display时疯狂输出！！
 return (head);
}

单链表的代码实现

// DataElement.h
#ifndef INC_01_DATAELEMENT_H
#define INC_01_DATAELEMENT_H

#define MAX_SIZE 255

// 定义数据元素
typedef struct {
    int id;
    char * name;
} ElementType;

// 定义顺序表结构
typedef struct {
    ElementType datas[MAX_SIZE];  // 顺序表中的数据集合
    int length;  // 当前顺序表中的元素个数
} SeqList;

#endif

// LinkList.h
#ifndef INC_01_LINKLIST_H
#define INC_01_LINKLIST_H

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

// 定义链表的结点，包含数据域和指针域

typedef struct Node {
    ElementType data;  // 数据域
    struct Node * next;  // 指针域，指向下一个结点
} Node;

typedef struct LinkList {
    Node * next;  // 头指针
    int length;  // 链表的长度，初始化为 0
} LinkList;

// 初始化链表
void InitLinkList(LinkList * linkList, ElementType * dataArray, int length);

/**
 * 在指定的位置 pos 插入元素 element
 * @param linkList  要插入的链表指针
 * @param pos  插入位置
 * @param element  插入的元素
 */
void InsertLinkList(LinkList * linkList, int pos, ElementType element);
// 清空链表
void ClearLinkList(LinkList * linkList);
// 打印链表元素
void PrintLinkList(LinkList * linkList);
// 判断链表是否为空
int IsLinkListEmpty(LinkList * linkList);
// 返回 pos 位置的元素
ElementType GetLinkListElement(LinkList * linkList, int pos);
// 删除指定位置的结点
ElementType DeleteLinkElement(LinkList * linkList, int pos);

#endif

// LinkList.c
#include "LinkList.h"

// 初始化链表
void InitLinkList(LinkList * linkList, ElementType * dataArray, int length) {
    for (int i = 0; i < length ; ++i) {
        InsertLinkList(linkList, i+1, dataArray[i]);
    }
};

/**
 * 在指定的位置 pos 插入元素 element
 * @param linkList  要插入的链表指针
 * @param pos  插入位置
 * @param element  插入的元素
 */
void InsertLinkList(LinkList * linkList, int pos, ElementType element) {
    // 创建一个结点并为数据域赋值
    Node * node = (Node *)malloc(sizeof(Node));
    node -> data = element;
    node -> next = NULL;
    // 找到要插入的结点
    if (pos == 1) {  // 当要插入的结点是第一个元素
        linkList -> next = node;
        linkList -> length++;
        return;
    }
    // 通过循环找到要插入的结点位置
    Node * currNode = linkList -> next;
    for (int i = 1; currNode && i < pos - 1; ++i) {
        currNode = currNode -> next;
    }
    // 将结点插入并对接前面的结点
    if (currNode) {
        node -> next = currNode -> next;
        currNode -> next = node;
        linkList -> length++;
    }
};
// 打印链表元素
void PrintLinkList(LinkList * linkList) {
    Node * node = linkList -> next;
    if (!node) {
        printf("链表为空！");
        linkList -> length = 0;
        return;
    }
    for (int i = 0; i < linkList -> length ; ++i) {
        printf("%d\t%s\n", node -> data.id, node->data.name);
        node = node -> next;
    }
};
// 判断链表是否为空
int IsLinkListEmpty(LinkList * linkList) {
    return linkList -> length == 0 ? 0 : 1;
};
// 返回 pos 位置的元素
ElementType GetLinkListElement(LinkList * linkList, int pos) {
    Node * node = linkList -> next;
    for (int i = 1; node && i < pos; ++i) {
        node = node -> next;
    }
    return  node -> data;
};

// 删除指定位置的结点
ElementType DeleteLinkElement(LinkList * linkList, int pos) {
    ElementType element;  // 被删除的元素
    element.id = -999;
    Node * node = NULL;
    if (pos == 1) {
        node = linkList -> next;
        if (node != NULL) {
            element = node -> data;
            linkList -> next = node -> next;
            free(node);  // 释放被删除的结点内存
        }
        return element;
    }
    // 1.找到要删除的结点和它的前缀结点
    // 2.将要删除结点的 next 赋值给前缀结点的 next
    // 3.释放要删除的结点内存
    Node * preNode = NULL; // 前缀结点
    node = linkList -> next;
    for (int i = 1; node && i < pos; ++i) {
        preNode = node;
        node = node -> next;
    }
    if (node) {
        element = node -> data;
        preNode -> next = node -> next;
        free(node);
        linkList -> length--;
    }
    return element;
};

// 清空链表
void ClearLinkList(LinkList * linkList) {
    Node * node = linkList -> next;
    Node * nextNode;
    while (node) {
        nextNode = node -> next;  // 记录当前结点的下一个结点，以便释放当前结点的内存
        free(node);
        node = nextNode;
    }
    linkList -> next = NULL;
    linkList -> length = 0;
};

// main.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "DataElement.h"
#include "LinkList.h"

ElementType dataArray[] = {
        {1, "奇异博士"},
        {2, "美国队长"},
        {3, "太上老君"},
        {4, "齐天大圣"},
};

void TestLinkList();

int main() {
    TestLinkList();
    return 0;
}
void TestLinkList() {
    LinkList linkList;
    linkList.length = 0;
    InitLinkList(&linkList, dataArray, sizeof(dataArray) / sizeof(dataArray[0]));
    printf("插入前：\n");
    PrintLinkList(&linkList);
    ElementType element;
    element.id = 123;
    element.name = (char *) malloc(10);
    strcpy(element.name, "测试内容");
    InsertLinkList(&linkList, 2, element);
    printf("插入后：\n");
    PrintLinkList(&linkList);
    printf("删除第三个元素后：\n");
    DeleteLinkElement(&linkList, 3);
    PrintLinkList(&linkList);
    ClearLinkList(&linkList);
    printf("清空链表后：\n");
    PrintLinkList(&linkList);
};