单链表

线性表的链式表示和实现

      线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以使不连续的)。因此,为了表示每个数据元素ai与其直接后继数据元素ai+1之间的逻辑关系对数据元素ai来说,除了存储其本身的信息之外,还需存储一个指示其直接后继的信息(即直接后继的存储位置)。这两部分信息组成数据元素ai的存储映像,称为结点。

     结点包括两个域:其中存储数据元素信息的域称为数据域;存储直接后继存储位置的域称为指针域。指针域中存储的信息称做指针或链。n个结点(ai(1<= i <= n )的存储映像)链结成一个链表,即为线性表(a1,a2,...,an)的链式存储结构。又由于此链表的每个结点中只包含一个指针域,故又称线性链表或单链表。

     整个链表的存取必须从头指针开始进行,头指针指示链表中第一个结点(即第一个数据元素的存储映像)的存储位置。同时,由于最后一个数据元素没有直接后继,则线性链表中最后一个结点的指针为“空”(NULL)。

     用线性链表表示线性表时,数据元素之间的逻辑关系是由结点中的指针指示的。换句话说,指针为数据元素之间的逻辑关系的映像,则逻辑上相邻的两个数据元素其存储的物理位置不要求紧邻,由此,这种存储结构为非顺序映像或链式映像。在使用链表时,关心的只是它所表示的线性表中数据元素之间的逻辑顺序,而不是每个数据元素在存储器中的实际位置。

/* 线性表的单链表存储结构 */
typedef struct LNode {
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

假设L是LinkList型的变量,则L为单链表的头指针,它指向表中第一个结点。若L为“空”(即L=NULL),则所表示的线性表为“空”表,其长度n为“零”。有时,我们在单链表的第一个结点之前附设一个结点,称之为头结点。头结点的数据域可以不存储任何信息,也可存储如线性表的长度等类的附加信息,头结点的指针域存储指向第一个结点的指针(即第一个元素结点的存储位置)。如图a所示,此时,单链表的头指针指向头结点。若线性表为空表,则头结点的指针域为“空”,如图b所示。

在单链表中,任何两个元素的存储位置之间没有固定的联系,然而,每个元素的存储位置都包含在其直接前驱结点的信息之中。假设p是指向线性表中第i个数据元素(结点ai)的指针,则p->next是指向第i+1个数据元素(结点ai+1)的指针。换句话说,若p->data=ai,则p->next->data=ai+1。

      由此,在单链表中,取得第i个数据元素必须从头指针出发寻找。单链表是非随机存取的存储结构。

 1 //获取线性表中的元素
 2 Status GetElem_L(LinkList L, int i, ElemType &e) {
 3     //L为带头结点的单链表的头指针, 当第i个元素存在时, 其值赋给e并返回OK, 否则返回ERROR
 4     int j = 0;
 5     struct LNode *p = NULL;
 6     p = L->next; j = 1;  //初始化, p指向第一个结点, j为计数器
 7     while(p && j < i) {  //顺指针向后查找, 直到p指向第i个元素或p为空
 8         p = p->next; ++j;
 9     }
10     if (!p || j > i) return ERROR; //第i个元素不存在
11     e = p->data;  //取第i个元素
12     return OK;
13 }

    在单链表中,如何实现“插入”和“删除”操作?

假设我们要在线性表的两个数据元素a和b之间插入一个数据元素x,已知p为其单链表存储结构中指向结点a的指针,如图a所示。

为插入数据元素x,首先要生成一个数据域为x的结点,然后插入在单链表中。根据插入操作的逻辑定义,还需要修改结点a中的指针域,令其指向结点x,而结点x中的指针域应指向结点b,从而实现3个元素a,b,x之间逻辑关系的变化。插入后的单链表如图b所示。假设s为指向结点x的指针,则上述指针修改用语句描述即为:

s->next = p->next;
p->next = s;

为了更清晰直观的看结点的插入情况,我们可以参看结点插入的动态演示:http://sjjg.js.zwu.edu.cn/SFXX/sf1/lbcr.html

     反之,如图所示在线性表中删除元素b时,为在单链表中实现元素a,b和c之间的逻辑关系的变化,仅需修改结点a中的指针域即可。假设p为指向结点a的指针,则修改指针的语句为:

p->next = p->next->next;

可见,在已知链表中元素插入或删除的确切位置的情况下,在单链表中插入或删除一个结点时,仅需修改指针而不需要移动元素。

 1 //在线性表中插入元素
 2 Status ListInsert_L(LinkList &L, int i, ElemType e) {
 3     //在带头结点的单链线性表L中第i个位置之前插入元素e
 4     struct LNode *p = L; int j = 0;
 5     struct LNode *s = NULL;
 6     while (p && j < i - 1) { p = p->next; ++j; } //寻找第i-1个结点
 7     if (!p || j > i - 1) return ERROR;           //i小于1或者大于表长
 8     s = (LinkList)malloc(sizeof(LNode));         //生成新结点
 9     s->data = e; s->next = p->next;
10     p->next = s;
11     return OK;
12 }

     在线性表中删除元素:

 1 // 删除线性表中的元素
 2 Status ListDelete_L(LinkList &L, int i, ElemType &e) {
 3     //在带头结点的单链线性表L中, 删除第i个元素, 并由e返回其值
 4     struct LNode *p = L; int j = 0; struct LNode *q = NULL;
 5     while (p->next && j < i - 1) { //寻找第i个结点, 并令p指向其前趋
 6         p = p->next; ++j; 
 7     }
 8     if (!(p->next) || j > i - 1) return ERROR;   //删除位置不合法
 9     q = p->next; p->next = q->next;    //删除并释放结点
10     e = q->data; free(q);
11     return OK;
12 }

假设p和q是LinkList型的变量,则执行p=(LinkList)malloc(sizeof(LNode))的作用是由系统生成的一个LNode型的结点,同时将该结点的起始位置赋给指针变量p;反之,执行free(p)的作用是由系统回收一个LNode型的结点,回收后的空间可以备作再次生成结点时用。因此,单链表和顺序存储结构不同,它是一种动态结构。整个可用存储空间可为多个链表共同享用,每个链表占用的空间不需预先分配划定,而是可以由系统应需求即时生成。因此,建立线性表的链式存储结构的过程就是一个动态生成链表的过程。即从“空表”的初始状态起,依次建立各元素结点,并逐个插入链表。

 1 //构造线性链表
 2 void CreateList_L(LinkList &L, int n) {
 3     //逆位序输入n个元素的值, 建立带表头结点的单链线性表L
 4     printf("input %d integers: \n", n);
 5     struct LNode *p = NULL;
 6     L = (LinkList)malloc(sizeof(LNode));
 7     L->next = NULL;    //先建立一个带头结点的单链表
 8     for (int i = n; i > 0; --i) {
 9         p = (LinkList)malloc(sizeof(LNode));  //生成新结点
10         scanf("%d", &p->data);
11         p->next = L->next; L->next = p;       //插入到表头
12     }
13 }

将两个有序链表并为一个有序链表:

     指针的初始状态为:当LA和LB为非空表时,pa和pb分表指向La和Lb表中第一个结点,否则为空;pc指向空表Lc中的头结点。      由于链表的长度为隐含的,则第一个循环执行的条件是pa和pb皆非空,当其中一个为空时,说明有一个表的元素已归并完,则只要将另一个表的剩余段链接在pc所指结点之后即可。

 1 //归并线性表
 2 void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc) {
 3     //已知单链线性表La和Lb的元素按值非递减排列
 4     //归并La和Lb得到新的单链线性表Lc, Lc的元素也按值非递减排列
 5     struct LNode *pa = NULL;  struct LNode *pb = NULL;  struct LNode *pc = NULL;
 6     pa = La->next; pb = Lb->next;
 7     Lc = pc = La;        //用La的头结点作为Lc的头结点
 8     while (pa && pb) {
 9         if (pa->data <= pb->data) {
10             pc->next = pa; pc = pa; pa = pa->next;
11         }
12         else { pc->next = pb; pc = pb; pb = pb->next; }
13     }
14     pc->next = pa ? pa : pb;     //插入剩余段
15     free(Lb);                    //释放Lb的头结点
16 }

   单链线性表的实现代码如下:

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 
  4 /******************************************************************************
  5 /* 数据类型和常量定义
  6 /******************************************************************************/
  7 #define TURE         1
  8 #define FALSE        0
  9 #define OK           1
 10 #define ERROR        0
 11 #define OVERFLOW    -2
 12 
 13 typedef int Status;
 14 typedef int ElemType;
 15 
 16 /******************************************************************************
 17 /* 数据结构声明
 18 /******************************************************************************/
 19 /* 线性表的单链表存储结构 */
 20 typedef struct LNode {
 21     ElemType data;
 22     struct LNode *next;
 23 }LNode, *LinkList;
 24 
 25 
 26 //获取线性表中的元素
 27 Status GetElem_L(LinkList L, int i, ElemType &e) {
 28     //L为带头结点的单链表的头指针, 当第i个元素存在时, 其值赋给e并返回OK, 否则返回ERROR
 29     int j = 0;
 30     struct LNode *p = NULL;
 31     p = L->next; j = 1;  //初始化, p指向第一个结点, j为计数器
 32     while(p && j < i) {  //顺指针向后查找, 直到p指向第i个元素或p为空
 33         p = p->next; ++j;
 34     }
 35     if (!p || j > i) return ERROR; //第i个元素不存在
 36     e = p->data;
 37     return OK;
 38 }
 39 
 40 //构造线性链表
 41 void CreateList_L(LinkList &L, int n) {
 42     //逆位序输入n个元素的值, 建立带表头结点的单链线性表L
 43     printf("input %d integers: \n", n);
 44     struct LNode *p = NULL;
 45     L = (LinkList)malloc(sizeof(LNode));
 46     L->next = NULL;    //先建立一个带头结点的单链表
 47     for (int i = n; i > 0; --i) {
 48         p = (LinkList)malloc(sizeof(LNode));  //生成新结点
 49         scanf("%d", &p->data);
 50         p->next = L->next; L->next = p;       //插入到表头
 51     }
 52 }
 53 
 54 //在线性表中插入元素
 55 Status ListInsert_L(LinkList &L, int i, ElemType e) {
 56     //在带头结点的单链线性表L中第i个位置之前插入元素e
 57     struct LNode *p = L; int j = 0;
 58     struct LNode *s = NULL;
 59     while (p && j < i - 1) { p = p->next; ++j; } //寻找第i-1个结点
 60     if (!p || j > i - 1) return ERROR;           //i小于1或者大于表长
 61     s = (LinkList)malloc(sizeof(LNode));         //生成新结点
 62     s->data = e; s->next = p->next;
 63     p->next = s;
 64     return OK;
 65 }
 66 
 67 //删除线性表中的元素
 68 Status ListDelete_L(LinkList &L, int i, ElemType &e) {
 69     //在带头结点的单链线性表L中, 删除第i个元素, 并由e返回其值
 70     struct LNode *p = L; int j = 0; struct LNode *q = NULL;
 71     while (p->next && j < i - 1) { //寻找第i个结点, 并令p指向其前趋
 72         p = p->next; ++j; 
 73     }
 74     if (!(p->next) || j > i - 1) return ERROR;   //删除位置不合法
 75     q = p->next; p->next = q->next;    //删除并释放结点
 76     e = q->data; free(q);
 77     return OK;
 78 }
 79 
 80 //归并线性表
 81 void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc) {
 82     //已知单链线性表La和Lb的元素按值非递减排列
 83     //归并La和Lb得到新的单链线性表Lc, Lc的元素也按值非递减排列
 84     struct LNode *pa = NULL;  struct LNode *pb = NULL;  struct LNode *pc = NULL;
 85     pa = La->next; pb = Lb->next;
 86     Lc = pc = La;        //用La的头结点作为Lc的头结点
 87     while (pa && pb) {
 88         if (pa->data <= pb->data) {
 89             pc->next = pa; pc = pa; pa = pa->next;
 90         }
 91         else { pc->next = pb; pc = pb; pb = pb->next; }
 92     }
 93     pc->next = pa ? pa : pb;     //插入剩余段
 94     free(Lb);                    //释放Lb的头结点
 95 }
 96 
 97 //遍历线性表
 98 Status ListTraverse_L(LinkList &L, Status (*Visit)(ElemType)) {
 99     struct LNode *p = L->next; //略过头结点
100     while (p) {
101         Visit(p->data);
102         p = p->next;
103     }
104     return OK;
105 }
106 
107 //访问线性表中的元素
108 Status Visit(ElemType e)
109 {
110     printf("%d ", e);
111     return OK;
112 }
113 
114 
115 //测试函数
116 void main()
117 {
118     LinkList L;  ElemType e;
119     CreateList_L(L, 2);
120     
121     //插入元素
122     if (OK == ListInsert_L(L, 1, 55)) printf("insert succeed!\n");
123     if (OK == ListInsert_L(L, 0, 56)) printf("insert succeed!\n");
124     if (OK == ListInsert_L(L, 7, 57)) printf("insert succeed!\n");
125     if (OK == ListInsert_L(L, 4, 58)) printf("insert succeed!\n");
126     ListTraverse_L(L, Visit); printf("\n");
127 
128     //删除元素
129     if (OK == ListDelete_L(L, 1, e)) printf("delete %d succeed!\n", e);
130     if (OK == ListDelete_L(L, 3, e)) printf("delete %d succeed!\n", e);
131     ListTraverse_L(L, Visit); printf("\n");
132 
133     //获取元素
134     if (OK == GetElem_L(L, 2, e)) printf("get elem %d succeed!\n", e);
135 
136     //链表合并
137     LinkList La, Lb, Lc;
138     CreateList_L(La, 3);
139     CreateList_L(Lb, 4);
140     MergeList_L(La, Lb, Lc);
141     ListTraverse_L(Lc, Visit);
142 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏mathor

LeetCode222. 完全二叉树的节点个数

 常规思路,遍历整棵树,时间复杂度O(N),但是有一种时间复杂度小于O(N)的做法  首先遍历头结点右子树的最左边界,如果最左边界不为空,说明头结点的左子...

16830
来自专栏令仔很忙

集合详解(二)----ArrayList源代码剖析(JDK1.7)

ArrayList是List类的一个典型的实现,是基于数组实现的List类,因此,ArrayList封装了一个动态的、可变长度的Object[]数组。Arra...

7810
来自专栏趣学算法

数据结构 第4讲 单链表

链表是线性表的链式存储方式,逻辑上相邻的数据在计算机内的存储位置不一定相邻,那么怎么表示逻辑上的相邻关系呢?可以给每个元素附加一个指针域,指向下一个元素的存储位...

11830
来自专栏王硕

原 B树C语言代码实现

779100
来自专栏架构之路

Combination Sum 组合数求和-Leetcode

原题: Given a set of candidate numbers (C) and a target number (T), find all uniqu...

34440
来自专栏决胜机器学习

PHP数据结构(六) ——树与二叉树之概念及存储结构

PHP数据结构(六)——树与二叉树之概念及存储结构 (原创内容,转载请注明来源,谢谢) 一、树的含义 1、树为非线性结构,是n(n>=0)个节点的有限集,非空树...

552100
来自专栏Java学习网

用Java实现处理日期的工具类——常用日期处理方法

日期处理是开发过程中经常遇到的问题,以下是总结了开发中常用的方法,代码如下: import java.text.ParseException; import j...

37250
来自专栏猿人谷

线性表简介

学习数据结构 -> 线性表 -> 线性表的介绍     线性表是一种典型的数据结构, 线性结构的基本特点是线性表中的数据元素是有序且有限的, 在线性结构中...

22280
来自专栏老马说编程

(42) 排序二叉树 / 计算机程序的思维逻辑

40节介绍了HashMap,41节介绍了HashSet,它们的共同实现机制是哈希表,一个共同的限制是没有顺序,我们提到,它们都有一个能保持顺序的对应类TreeM...

21260
来自专栏算法与数据结构

PTA 带头结点的单链表就地逆置(10 分)

本题要求编写函数实现带头结点的单链线性表的就地逆置操作函数。L是一个带头结点的单链表,函数ListReverse_L(LinkList &L)要求在不新开辟节点...

35770

扫码关注云+社区

领取腾讯云代金券