单链表

数据结构 › C
,
·本篇:1k字 大约需要: 4分钟

前言

单链表的实现及基本操作

编程语言: C

单链表

单链表的定义

  • 为了表示每个数据元素ai与其直接后继数据元素 ai+1 之间的逻辑关系，对数据元素 ai 来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息(即直接后继的存储位置)。

  • 把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称做指针或链。这两部分信息组成数据元素 ai 的存储映像，称为结点(Node)。

  • n个结点链结成一个链表，即为线性表(a1, a2, …, an)的链式存储结构，因为此链表的每个结点中只包含一个指针域，所以叫做单链表

基本操作实现

  • 结构代码
1
2
3
4
5
6
7
8
9
10
11
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define sf scanf
#define pf printf

typedef struct Node
{
    int data;
    struct Node *next;
} Node;
  • 初始化头结点
1
2
3
4
5
void Inithead(Node *p)
{
    p->data = 0;
    p->next = NULL;
}

头结点的数据域中可以存储表长

  • 向单链表中添加随机元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void RandLinkList(Node *p)
{
    Node *q = p;
    while(q->next != NULL) q = q->next;
    srand((unsigned) time(0));
    int length = rand() % 10 + 10;
    p->data += length;
    while(length--)
    {
        Node *temp = (Node *) malloc(sizeof(struct Node));
        temp->data = rand() % 100;
        temp->next = NULL;
        q->next = temp;
        q = q->next;
    }
    pf("当前表中一共有%d位元素\n", p->data);
}
  • 向单链表中插入一个元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void InsertList(Node *p, int target, int pos) 
{
    Node *q = p;
    Node *temp = (Node *) malloc(sizeof(Node));
    if(pos >= p->data)
    {
        while(q->next != NULL) q = q->next;
        temp->data = target;
        temp->next = NULL;
        q->next = temp;
        p->data++;
    }
    else if(pos < p->data && pos > 0)
    {
        pos--;
        while(pos--) q = q->next;
        temp->data = target;
        temp->next = q->next;
        q->next = temp;
        p->data++;
    }
    else
        pf("插入位置非法");
}
  • 修改单链表中某一位置的元素值
1
2
3
4
5
6
7
8
9
10
11
void ModifyList(Node *p, int target, int pos) 
{
    if(pos > p->data || pos <= 0)
        pf("位置非法");
    else
    {
        Node *q = p;
        while(pos--) q = q->next;
        q->data = target;
    }
}
  • 删除链表中某一位置的元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void DeleteList(Node *p, int pos)
{
    Node *q = p, *temp;
    if(pos > p->data || p <= 0)
        pf("删除非法");
    else
    {
        pos--;
        while(pos--) q = q->next;
        pf("%d\n", q->data);
        temp = q->next;
        q->next = q->next->next;
        free(temp);
        temp = NULL;
        p->data--;
    }
}
  • 带头结点的单链表逆置
1
2
3
4
5
6
7
8
9
10
11
12
void InverseHeadLinkList(Node *L) 
{
    Node *p = L->next, *q;
    L->next = NULL;
    while(p)
    {
        q = p;
        p = p->next;
        q->next = L->next;
        L->next = q;
    }
}
  • 不带头结点的单链表逆置
1
2
3
4
5
6
7
8
9
10
11
12
Node *InverseLinkList(Node *L) 
{
    Node *p = L, *q = L, *temp = NULL;
    while(p)
    {
        p = p->next;
        q->next = temp;
        temp = q;
        q = p;
    }
    return temp;
}
  • 遍历单链表中的所有元素
1
2
3
4
5
6
7
8
9
10
11
void DisplayLinkList(Node *p)
{
    Node *q = p->next;
    pf("表长 = %d\n", p->data);
    while(q != NULL)
    {
        pf("%d ", q->data);
        q = q->next;
    }
    pf("\n");
}
  • 清空单链表
1
2
3
4
5
6
7
8
9
10
11
12
13
void ClearList(Node *L)
{
    Node *p, *q;
    p = L;
    while(p->next != NULL)
    {
        q = p->next;
        free(p);
        p = q;
    }
    L->data = 0;
    L = NULL;
}

总结

单链表结构与顺序存储结构对比

存储分配方式

  • 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素
  • 单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素

时间性能

  • 查找
  • 顺序存储结构O(1)
  • 单链表O(n)
  • 插入和删除
    • 顺序存储结构需要平均移动表长一半的元素，时间为O(n)
    • 单链表在计算出某位置的指针后，插入和删除时间仅为O(1)

空间性能

  • 顺序存储结构需要预分配存储空间，分大了浪费，分小了易溢出

  • 单链表不需要分配存储空间，元素个数也不受限制