线性表的链接存储

线性表的链接存储是指它的存储结构是链式的。线性表常见的链式存储结构有单链表、循环链表和双向循环链表，其中最简单的是单链表。

单链表的类型定义

// 假定数据元素类型为 DataType 
typedef struct
{
    int num;        // 学号 
    char name[8];   // 姓名
    char sex[2];    // 性别
    int age;        // 年龄
    int score;      // 入学成绩  
} DataType;

// 单链表的类型定义 
typedef struct node
{
    DataType data;      // 数据域 
    struct node *next;  // 指针域或链域 
} Node, *LinkList;      // 通过 typedef 语句把 struct node 类型定义为 Node，把 struct node 指针类型定义为 LinkList

LinkList head; // head 为链表的名称

单链表的初始化

LinkList InitiateLinkList()
{
    // 建立一个空的单链表
    LinkList head;                         // 头指针
    head = (LinkList)malloc(sizeof(Node)); // 动态构建一结点，它是头结点
    head->next = NULL;                     // 如果为非空单链表，头结点的指针域指向首结点 
    return head; 
} 

读表元素

Node *GetLinkList(LinkList head, int i)
{
    // 在单链表 head 中查找第 i 个元素结点。若找到，则返回指向该结点的指针；否则返回 NULL
    Node *p;        
    p = head->next; // 初始时，p 指向首结点
    int c = 1;
    while ((c < i) && (p != NULL)) { // 当未到第 i 个结点且未到尾结点时继续后移 
        p = p->next;
        c++;
    }
    if (i == c) {   // 找到第 i 个结点 
        return p;
    } else {        // i<1 或 i>n，i 值不合法，查找失败
        return NULL;
    }
} 

单链表的插入

void InsertLinkList(LinkList head, DataType x, int i)
{
    // 在表 head 的第 i 个数据元素结点之前插入一个以 x 为值的新结点
    Node *p, *q;
    if (i == 1) { 
        q = head;
    } else { 
        q = GetLinkList(head, i - 1); // 找到第 i-1 个数据元素结点
    }
    if (q == NULL) { 
        exit('找不到插入的位置'); 
    } else {
        p = (Node *)malloc(sizeof(Node));  
        p->data = x;        // 生成新结点 
        p->next = q->next;  // 新结点指针域指向 *q 的后继结点 
        q->next = p;        // 修改 *q 的指针域 
    }
} 

单链表的删除

void DeleteLinkList(LinkList head, int i)
{
    // 删除表 head 的第 i 个结点
    Node *p, *q;
    if (i == 1) {
        q = head;
    } else {
        q = GetLinkList(head, i - 1); // 先找到待删结点的直接前驱 
    }
    if (q != NULL && q->next != NULL){ // 若直接前驱存在且待删结点存在
        p = q->next;       // p 指向待删结点
        q->next = p->next; // 移除待删结点
        free(p);           // 释放已移除结点 p 的空间 
    } else {
        exit('找不到要删除的结点');
    }    
}