抱歉，您的浏览器无法访问本站

本页面需要浏览器支持（启用）JavaScript


了解详情 >

线性表的链式存储原理及 C 语言实现

C/C++

本文发布于：2022年7月9日

字数：1.9k字

时长：9分钟

顺序表在插入和删除操作需要移动大量元素。数组的大小不好确定，且存储分配需要一整段连续的存储空间，造成很多碎片。因此在需要经常插入和删除的线性表中，需要通过链式存储方式实现。线性表的链式表示称为链表。以下为我在学习和实战练习过程中所做的笔记，可供参考。

一、单链表

逻辑上相邻的两个元素在物理位置上不相邻。

单链表结点的定义：

1
2
3
4
5
typedef int ElemType;
typedef struct LNode {  // 单链表结点类型
  	ElemType data;    // 数据域
  	struct LNode *next;  // 指向下一个结点 
} LNode, *LinkList;  // LinkList 等价于 struct LNode *

头指针：链表中第一个结点的存储位置，用来标识单链表。

头结点：在单链表第一个结点之前附加的个结点，为了操作上的方便。

若链表有头结点，则头指针永远指向头结点，不论链表是否为空，头指针均不为空，头指针是链表的必须元素，他标识一个链表。

头结点是为了操作的方便而设立的，其数据域一般为空，或者存放链表的长度。有头结点后，对在第一结点前插入和删除第一结点的操作就统一了，不需要频繁重置头指针。但头结点不是必须的。

优点：

  • 插入和删除操作不需要移动元素，只需要修改指针。
  • 不需要大量的连续存储空间。

缺点：

  • 单链表附加指针域，也存在浪费存储空间的缺点。
  • 查找操作时需要从表头开始遍历，依次查找，不能随机存取。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int main()
{
    LinkList L;		 // 链表头，是结构体指针类型
    LinkList search; // 用来存储拿到的某一个节点
    // CreatList1(L); // 输入数据可以为3 4 5 6 7 9999，头插法新建链表
    CreatList2(L); // 输入数据可以为3 4 5 6 7 9999，尾插法新建链表
    PrintList(L);  // 链表打印
    search=GetElem(L,2);
    if(search!=NULL)
    {
        printf("按序号查找成功\n");
        printf("%d\n",search->data);
    }
    search=LocateElem(L,6); // 按值查询
    if(search!=NULL)
    {
        printf("按值查找成功\n");
        printf("%d\n",search->data);
    }
    ListFrontInsert(L,2,99);   // 新结点插入第i个位置
    PrintList(L);
    ListDelete(L,4);   // 删除第4个结点
    PrintList(L);
}

头插法新建链表：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
LinkList CreatList1(LinkList &L) // list_head_insert
{
    LNode *s;
    int x;
    L = (LinkList)malloc(sizeof(LNode)); // 带头结点的链表
    L->next = NULL;						 // L->data里边没放东西
    scanf("%d", &x);					 // 从标准输入读取数据
    // 3 4 5 6 7 9999
    while (x != 9999)
    {
        s = (LNode *)malloc(sizeof(LNode)); // 申请一个新空间给s，强制类型转换
        s->data = x;						// 把读取到的值，给新空间中的data成员
        s->next = L->next;			// 让新结点的next指针指向链表的第一个元素（第一个放我们数据的元素）
        L->next = s;						// 让s作为第一个元素
        scanf("%d", &x);					// 读取标准输入
    }
    return L;
}

尾插法新建链表：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
LinkList CreatList2(LinkList &L) // list_tail_insert
{
    int x;
    L = (LinkList)malloc(sizeof(LNode)); // 带头节点的链表
    LNode *s, *r = L;					 // LinkList s,r=L;也可以，r代表链表表尾结点，指向链表尾部
    // 3 4 5 6 7 9999
    scanf("%d", &x);
    while (x != 9999)
    {
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        r->next = s; // 让尾部结点指向新结点
        r = s;		 // r指向新的表尾结点
        scanf("%d", &x);
    }
    r->next = NULL; // 尾结点的next指针赋值为NULL
    return L;
}

按序号查找结点值：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
LNode *GetElem(LinkList L, int i)
{
    int j = 1;
    LNode *p = L->next;
    if (i == 0)
      	return L;
    if (i < 1)
      	return NULL;
    while (p && j < i)
    {
      	p = p->next;
      	j++;
    }
    return p;
}

按值查找：

1
2
3
4
5
6
7
LNode *LocateElem(LinkList L, ElemType e)
{
    LNode *p = L->next;
    while (p != NULL && p->data != e)
      	p = p->next;
    return p;
}

新结点插入第 i 个位置：

1
2
3
4
5
6
7
8
9
10
11
12
13
bool ListFrontInsert(LinkList L, int i, ElemType e)
{
    LinkList p = GetElem(L, i - 1);
    if (NULL == p)
    {
        return false;
    }
    LinkList s = (LNode *)malloc(sizeof(LNode)); // 为新插入的结点申请空间
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

删除第 i 个结点：

1
2
3
4
5
6
7
8
9
10
11
12
13
bool ListDelete(LinkList L, int i)
{
    LinkList p = GetElem(L, i - 1);
    if (NULL == p)
    {
        return false;
    }
    LinkList q;
    q = p->next;
    p->next = q->next; // 断链
    free(q);		   // 释放对应结点的空间
    return true;
}

打印链表中每个结点的值：

1
2
3
4
5
6
7
8
9
10
void PrintList(LinkList L)
{
    L = L->next;
    while (L != NULL) // NULL是为了代表一张空的藏宝图
    {
        printf("%3d", L->data); // 打印当前结点数据
        L = L->next;			// 指向下一个结点
    }
    printf("\n");
}

二、双链表

双链表结点定义：

1
2
3
4
5
typedef int ElemType;
typedef struct DNode{
    ElemType data;
    struct DNode *prior,*next;  //前驱，后继
}DNode,*DLinkList;

双链表增删查：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int main()
{
    DLinkList DL;
    DLinkList search;
    Dlist_head_insert(DL);
    //Dlist_tail_insert(DL);
    //3 4 5 6 7 9999
    PrintDList(DL);
    search=GetElem(DL,2);
    if(search!=NULL)
    {
        printf("按序号查找成功\n");
        printf("%d\n",search->data);
    }
    DListFrontInsert(DL,3,99);
    PrintDList(DL);
    DListDelete(DL,2);
    PrintDList(DL);
    system("pause");
}

双向链表头插法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
DLinkList Dlist_head_insert(DLinkList &DL)
{
    DNode *s;int x;
    DL=(DLinkList)malloc(sizeof(DNode));//带头结点的链表,不带头结点
    DL->next=NULL;
    DL->prior=NULL;
    scanf("%d",&x);//从标准输入读取数据
    //3 4 5 6 7 9999
    while(x!=9999){
        s=(DLinkList)malloc(sizeof(DNode));//申请一个空间空间，强制类型转换
        s->data=x;
        s->next=DL->next;
        if(DL->next!=NULL)//插入第一个结点时，不需要这一步操作
        {
          DL->next->prior=s;
        }
        s->prior=DL;
        DL->next=s;
        scanf("%d",&x);//读取标准输入
    }
    return DL;
}

双向链表尾插法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
DLinkList Dlist_tail_insert(DLinkList &DL)
{
    int x;
    DL=(DLinkList)malloc(sizeof(DNode));//带头节点的链表
    DNode *s,*r=DL;
    DL->prior=NULL;
    //3 4 5 6 7 9999
    scanf("%d",&x);
    while(x!=9999){
        s=(DNode*)malloc(sizeof(DNode));
        s->data=x;
        r->next=s;
        s->prior=r;
        r=s;//r指向新的表尾结点
        scanf("%d",&x);
    }
    r->next=NULL;//尾结点的next指针赋值为NULL
    return DL;
}

按序号查找结点值：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
DNode *GetElem(DLinkList DL,int i)
{
    int j=1;
    DNode *p=DL->next;
    if(i==0)
        return DL;
    if(i<1)
     	  return NULL;
    while(p&&j<i)
    {
        p=p->next;
        j++;
    }
    return p;
}

新结点插入第 i 个位置：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool DListFrontInsert(DLinkList DL,int i,ElemType e)
{
    DLinkList p=GetElem(DL,i-1);
    if(NULL==p)
    {
      	return false;
    }
    DLinkList s=(DLinkList)malloc(sizeof(DNode));//为新插入的结点申请空间
    s->data=e;
    s->next=p->next;
    p->next->prior=s;
    s->prior=p;
    p->next=s;
    return true;
}

删除第 i 个结点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool DListDelete(DLinkList DL,int i)
{
    DLinkList p=GetElem(DL,i-1);
    if(NULL==p)
    {
      	return false;
    }
    DLinkList q;
    q=p->next;
    if(q==NULL)//删除的元素不存在
      	return false;
    p->next=q->next;//断链
    if(q->next!=NULL)
    {
      	q->next->prior=p;
    }
    free(q);//释放对应结点的空间
    return true;
}

链表打印：

1
2
3
4
5
6
7
8
9
10
void PrintDList(DLinkList DL)
{
    DL=DL->next;
    while(DL!=NULL)
    {
        printf("%3d",DL->data);
        DL=DL->next;
    }
    printf("\n");
}

三、循环链表和静态链表

循环单链表与单链表的区别在于，表中最后一个结点的 next 指针不是 NULL，而是指向头结点 L，从而整个链表形成一个环。x

循环双链表与双链表的区别在于，表中最后一个结点的 next 指针不是 NULL，而是指向头结点 L，同时 L->prior 指向尾节点。当循环双链表为空时，其头结点的 prior 域和 next 域都等于 L。

静态链表是借助数组来描述线性表的链式存储结构：

1
2
3
4
5
#define Maxsize 50
typedef struct{
  	ElemType data;
  	int next;
}SLinkList[Maxsize];
参考资料（References）：

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

本文永久地址：http://blog.zhuangzhihao.top/%E7%BA%BF%E6%80%A7%E8%A1%A8%E7%9A%84%E9%93%BE%E5%BC%8F%E5%AD%98%E5%82%A8/

Bezhuang

评论



Copyright © 2020 - 2022 Zhihao Zhuang. All rights reserved

本站访客数： 人，
总访问量： 次