数据结构

大话数据结构: 线性表的单链表存储结构

Posted by Viletyy on 2020-06-09 10:01

线性表的单链表存储结构

1
2
3
4
5
6
7

/*线性表的单链表存储结构*/
typedef struct Node 
{
    ElemType data;
    struct Node *next; 

typedef struct Node *LinkList;

结点由存放数据元素的数据域存放后继结点地址的指针域组成。

单链表的读取

获得链表第i个数据的算法思路

  1. 声明一个结点p指向链表第一个结点，初始化j从1开始
  2. 当j<i时，就便利链表，让p的指针向后移动，不断指向下一结点，j累加1；
  3. 若到链表末尾p为空，则说明第i个元素不存在；
  4. 否则查找成功，返回结点p的数据
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

/*初始条件：顺序线性表L已存在，1<=i<=ListLength(L)*/
/*操作结果：用e返回L中第i个数据元素的值*/
Status GetElem(LinkList L,int i, ElemType *e)
{
    int j;
    LinkList p; /*声明一结点p*/
    p = L->next; /*让p指向链表L的第一个结点*/
    j = 1; /*j为计数器*/
    while (p && j<i) /*p不为空和计数器j还没有等于i时，循环继续*/
    {
        p = p->next; /*让p指向下一个结点*/
        ++j;
    }
    if (!p || j > i) 
        return ERROR; /*第i个元素不存在*/
    *e  = p->data; /*取第i个元素的数据*/
    return OK;
}

单链表的插入和删除

单链表第i个数据插入结点的算法思路：

  1. 声明一结点p指向链表第一个结点，初始化j从1开始；
  2. 当j<i时，就便利链表，让p的指针向后移动，不断指向下一结点，j累加1；
  3. 若到链表末尾p为空，则说明第i个元素不存在；
  4. 否则查找成功，在系统中生存一个空结点s
  5. 将数据元素e赋值给s->data;
  6. 单链表的插入标准语句s->next=p->next; p->next=s;
  7. 返回成功
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

/*初始条件：顺序线性表L已存在，1<=i<=ListLength(L)*/
/*操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1*/
Status ListInsert(LinkList *L,int i,ElemType e)
{
    int j;
    LinkList p, s;
    p = *L;
    j = 1;
    while (p && j<i) /*寻找第i个结点*/
    {
        p=p->next;
        ++j;
    }
    if (!p || j > i)
        return ERROR; /*第i个元素不存在*/
    s = (LinkList) malloc(sizeof(Node)); /*生成新结点（c标准函数）*/
    s->data = e;
    s->next = p->next; /*将p的后继结点赋值给s的后继结点*/
    p->next = s; /*将s赋给p的后继结点*/
    return OK;
}

单链表第i个数据删除结点的算法思路：

  1. 声明一结点p指向链表第一个结点，初始化j从1开始；
  2. 当j<i时，就便利链表，让p的指针向后移动，不断指向下一个结点，j累加1；
  3. 若到链表末尾p为空，则说明第i个元素不存在；
  4. 否则查找成功，将与删除的结点p->next赋值给q；
  5. 单链表的删除标准语句p->next=q->next;
  6. 将q结点中的数据复制给e，作为返回；
  7. 释放q结点；
  8. 返回成功。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

/*初始条件：顺序线性表L已存在，1<=i<=ListLength(L)*/
/*操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1*/
Status ListDelete(LinkList *L, int i, ElemType *e)
{
    int j;
    LinkList p, q;
    p = *L;
    j = 1;
    while (p->next && j<i) /*遍历寻找第i个元素*/
    {
        p = p->next;
        ++j;
    }
    if (!(p->next) || j>i) 
        return ERROR; /*第i个元素不存在*/
    q = p->next;
    p->next = q->next; /*将q的后继复制给p的后继*/
    *e = q->data;   /*将q结点中的数据给e*/
    free(q);    /*让系统回收此结点，释放内存*/
    return OK;
}

对于插入或删除数据越频繁的操作，单链表的效率优势就越是明显。

单链表的整表创建

顺序存储结构的创建，其实就是一个数组的初始化，即声明一个类型和大小的数组并复制的过程。而单链表和顺序存储结构就不一样，它不像顺序存储结构这么集中，它可以很散，是一种动态结构。对于每个链表来说，它所占用空间的大小和位置是不需要预先分配划定的，可以根据系统的情况和实际的需求即时生成。

所以创建单链表的过程就是一个动态生成链表的过程。即从“空表”的初始状态起，一次建立个元素结点，并逐个插入链表。

单链表整表创建的算法思路：

  1. 声明一结点p和计数器变量i；
  2. 初始化一空链表L；
  3. 让L的头结点的指针指向NULL，即建立一个带头结点的单链表；
  4. 循环
    1. 生成一新结点赋值给p
    2. 随机生成一数字复制给p的数据域p->data;
    3. 将p插入到头结点与前一新结点之间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

/*随机产生n个元素的值，建立带表头结点的单链线性表L（头插法）*/
void CreateListHead(LinkList *L, int n) 
{
    LinkList p;
    int 1;
    srand(time(0)); /*初始化随机数种子*/
    *L = (LinkList)malloc(sizeof(Node));
    (*L)->next = NULL; /*先建立一个带头结点的单链表*/
    for (i=0; i<n; i++) 
    {
        p = (LinkList)malloc(sizeof(Node)); /*生成新结点*/
        p->data = rand()%100+1; /*随机生成100以内的数字*/
        p->next = (*L)->next;
        (*L)->next = p; /*插入到表头*/
    }
}

这段算法代码里，我们其实用的是插队的办法，就是始终让新结点在第一的位置。这种算法也称为头插法。

可事实上，我们还是可以不这样干，为什么不把新结点都放到最后呢，这才是排队时到正常思维，所谓的先来后到。我们把每次新结点都插在终端结点的后面，这种算法称之为尾插法。

实现代码算法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

/*随机产生n个元素的值，建立带表头结点的单链线性表L（尾插法）*/
void CreateListTail(LinkList *L, int n)
{
    LinkList p,r;
    int i;
    srand(time(0)); /*初始化随机数种子*/
    *L = (LinkList)malloc(sizeof(Node)); /*为整个线性表*/
    r = *L;
    for (i=0; i<n; i++)
    {
        p = (Node *)malloc(sizeof(Node)); /*生成新结点*/
        p->data = rand()%100+1; /*随机生成100以内的数字*/
        r->next=p; /*将表尾终端结点指针指向新结点*/
        r=p; /*将当前的新结点定义为表尾终端结点*/
    }
    r->next = NULL; /*表示当前链表结束*/
}

注意L与r的关系，L是指整个单链表，而r时指向尾结点的变量，r会随着循环不断地变化结点，而L则是随着循环增长为一个多结点的链表。

单链表的整表删除

算法思路如下：

  1. 声明一结点p和q；
  2. 将第一个结点赋值给p；
  3. 循环：
    1. 将下一个结点赋值给q；
    2. 释放p；
    3. 将q赋值给p
1
2
3
4
5
6
7
8
9
10
11
12
13
14

/*初始条件：顺序线性表L已存在，操作结果：将L重置为空表*/
Status ClearList(LinkList *L)
{
    LinkList p, q;
    p = (*L) ->next; /*p指向第一个结点*/
    while (p) /*没到表尾*/
    {
        q=p->next;
        free(p);
        p = q;
    }
    (*L)->next=Null; /*头结点指针域为空*/
    return OK;
}

单链表结构与顺序存储结构优缺点

  • 存储分配方式
    • 顺序存储结构用一段连续的存储单元一次存储线性表的数据元素
    • 单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素
  • 时间性能
    • 查找
      • 顺序存储结构O(1)
      • 单链表O(n)
    • 插入和删除
      • 顺序存储结构需要平均移动表长一般的元素，时间为O(n)
      • 单链表在找出某位置的指针后，插入和删除时间仅为O(1)
  • 空间性能
    • 顺序存储结构需要预分配存储空间，分大了，浪费，分小了易发生上溢
    • 单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制。

结论：

  • 若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构。若需要频繁插入和删除时，宜采用单链表结构。
  • 当线性表中的元素个数变化较大或者根本不知道有多大时，最好用单链表结构，这样可以不需要考虑存储空间的大小问题。而如果事先知道线性表的大致长度，使用顺序存储结构效率会高很多。

参考资料：

CATALOG
    FEATURED TAGS
    Rails Linux Golang 数据结构 包 Shell 代码安全 Git