一起来看看C语言线性表的线性链表

目录
  • 定义
  • 1.插入
  • 2.建立线性链表
    • 1)头插法
    • 2)尾插法
  • 3.删除
  • 4.查找
  • 5.求线性链表的表长
  • 总结

定义

链表是通过一组任意的存储单元来存储线性表中的数据元素,每一个结点包含两个域:存放数据元素信息的域称为数据域,存放其后继元素地址的域称为指针域。因此n个元素的线性表通过每个结点的指针域连接成了一个“链条”,称为链表。若此链表的每个结点中只包含一个指针域,则被称为线性链表单链表

线性表的链式存储结构,它不需要用地址连续的存储单元来实现,因为它不要求逻辑上相邻的两个数据元素物理位置上也相邻,它是通过“指针”建立起数据元素之间的逻辑关系。

链表是由一个个结点构成的,结点定义如下:

typedef struct node
{
    DataType data;
    struct node *next;
} Linklist;

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

为了使用方便可以在第一个元素的前面增加一个结点(被称为头节点),该节点的数据域为空,指针域中存储线性链表的第一个元素所在的结点(表头结点)的存储地址。如果为空表,则指针域为空。

因此空链表也分为带有头结点的空链表和不带头结点的空链表。若有头结点,头结点的数据域为空,指针域为空,则说明该链表为空链表;若没有头结点,表头指针为空指针,则说明该链表为空链表。

1.插入

假设要在线性表的两个数据元素a和b之间插入一个数据元素x,p为指向结点a的指针。为了插入数据元素x,首先要生成一个数据域为x的新结点s为指向新增节点的指针,然后使新增节点的指针域指向b(p->next),结点a的指针域指向新增节点(s)。

int InsertLinkList(LinkList *H, int i, DataType x)
/*在有头结点的线性链表H中第i个位置前插入元素x*/
{
    LinkList *p;
    LinkList *s;
    int j = 0;
    p = H;
    while (p && j<i-1)
    {
        p = p->next;
        j++;
    }/*循环直到p指向第i-1个元素*/
    if (!p)
        return -1;/*i大于表长加1*/
    s = (LinkList *)malloc(sizeof(LinkList));
    s->data = x;
    s->next = p->next;/*插入数据元素x*/
    p->next = s;
    return 1;
}

2.建立线性链表

1)头插法

建立线性链表应从空表开始,每读入一个数据元素则申请一个结点,然后插在链表的头结点与第一个结点之间。记头结点为H,申请的结点为s,按照上述插入算法,操作步骤为:

s->next = H->next; H->next = s;

再加上新建头结点、读入数据元素、申请结点等步骤,可编程如下:

LinkList *CreateLinkList_front()
{
    LinkList *H;/*H表示头结点*/
    LinkList *s;
    char x;/*设数据元素的类型为char*/
    H = (LinkList *)malloc(sizeof(LinkList));/*为头结点申请内存空间*/
    H->next = NULL;
    scanf(" %c", &x);
    while (x!=flag)/*flag为结束创建过程的标志,如'#'等*/
    {
        s = (LinkList *)malloc(sizeof(LinkList));
        s->data = x;
        s->next = H->next;
        H->next = s;
        scanf(" %c", &x);
    }
    return H;
}

因为是在链表的头部插入,读入数据的顺序和线性表中的逻辑顺序是相反的。

2)尾插法

在表头插入建立线性链表方法简单,但读入数据元素的顺序与生成的链表中元素的顺序是相反的,若希望次序一致,则用尾插法。因为每次是将新结点插入到链表的尾部,所以需加入一个指针用来始终指向链表中的尾结点,以便能够将新结点插入到链表的尾部。

在前面,我们介绍了插入算法,在这里可以通过调用插入算法,即定义一个变量int i = 1;,调用前面的函数InsertLinkList(H, i, x);,每插入一个数据元素,便使i++;,这样就可一直保持在链表的尾部插入。

LinkList *CreateLinkList_rear()
{
    LinkList *H;
    DataType x;/*设DataType为数据元素的类型*/
    int i = 1;
    H = (LinkList *)malloc(sizeof(LinkList));
    H->next = NULL;
    scanf(&x);/*读入数据元素的值*/
    while (x!=flag)
    {
        InsertLinkList(H, i, x);/*调用插入算法*/
        i++;
        scanf(&x);
    }
    return H;
}

但是这样使得算法的时间复杂度比头插法要高出了一个数量级,因为每次在尾部插入数据元素时,都要重新调用InsertLinkList()函数,使指针重新从表头指针开始指向尾结点。

因此我们可以使指针(记为p)一直指向链表中的尾结点,然后让新结点(记为s)按照插入算法插入链表的尾部。只需修改上述代码的while循环即可实现:

LinkList *CreateLinkList_rear()
{
    LinkList *H, *p, *s;
    DataType x;/*设DataType为数据元素的类型*/
    H = (LinkList *)malloc(sizeof(LinkList));
    H->next = NULL;
    scanf(&x);/*读入数据元素的值*/
    p = H;
    while (x!=flag)
    {
        s = (LinkList *)malloc(sizeof(LinkList));
        s->data = x;
        s->next = NULL;
        p->next = s;
        p = p->next;
        scanf(&x);
    }
    return H;
}

3.删除

假设链表中有a, b, c3个数据元素,要删除数据元素a和数据元素c中间的数据元素b时,仅需修改数据元素a所在的结点的指针域。假设指针p指向数据元素a,用语句表示就是:

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

添加一个指针变量q,让q指向数据元素b,当改变数据元素a所在的结点的指针域后,即可释放q的内存,即释放数据元素b所占的内存。进一步地,调用函数时传入标志变量i,可实现删除第i个数据元素。

int DeleteLinkList(LinkList *H, int i)
/*在有头结点的线性链表H中删除第i个元素*/
{
    LinkList *p;
    LinkList *q;
    int j = 0;
    p = H;
    while (p->next && j<i-1)
    {
        p = p->next;
        j++;
    }/*循环直到p指向第i-1个元素*/
    if (!(p->next))
        return -1;/*删除节点不合法*/
    q = p->next;
    p->next = q->next;/*删除第i个数据元素*/
    free(q);/*释放第i个数据元素所占内存*/
    return 1;
}

对比插入算法和删除算法,while循环的功能同样是使p指向第i-1个元素,为什么插入算法的循环条件为p && j<i-1,而删除算法的循环条件是p->next && j<i-1?能否将删除算法的循环条件也改为p && j<i-1?

这是因为,在链表根本没有i-1个元素的情况下,循环条件为p && j<i-1的循环运行结果为p指向尾结点的下一个结点即p=NULL,而循环条件为p->next && j<i-1的循环运行结果为p指向尾结点即p≠NULL。若将删除算法的循环条件也改为p && j<i-1,在链表根本没有i-1个元素的情况下,while循环后面的语句if (!(p->next))将会造成非法内存访问,因为此时p=NULL,我们无法访问空指针指向的内容。

4.查找

查找结点使用的算法是线性查找法(顺序查找法),即从链表的第一个结点开始,顺着指针链一个一个比较,相等则查找成功,返回结点位置;如果比较到最后也没有相等的,则查找不成功,返回空。

LinkList *SearchLinkList(LinkList *H, DataType x)
/*在线性链表H中查找值为x的结点,找到后返回其指针,否则返回空*/
{
    LinkList *p = H->next;/*p指向线性链表的第一个数据元素*/
    while (p!=NULL && p->data!=x)
        p = p->next;
    return p;
}

若要返回值为x的结点在链表中的位序,则可使用一个标记变量i,记录结点的位序;若找不到则返回-1。修改程序如下:

int SearchLinkList(LinkList *H, DataType x)
/*在线性链表H中查找值为x的结点,找到后返回其在链表中的位序,否则返回-1*/
{
    LinkList *p = H->next;/*p指向线性链表的第一个数据元素*/
    int i = 1;
    while (p!=NULL && p->data!=x)
    {
        p = p->next;
        i++;
    }
    if (p != NULL)
        return i;
    else
        return -1;
}

5.求线性链表的表长

设H是带头结点的线性链表(线性表的长度不包括头结点),求线性链表的表长的操作与上述查找某结点在链表中的位序相似。

int LinkListLength(LinkList *H)
{
    LinkList *p = H;/*p指向头结点*/
    int n = 0;
    while (p->next)
    {
        p = p->next;
        n++;
    }/*p所指的是第n个结点*/
    return n;
}

总结

本篇文章就到这里了,希望能够给你带来帮助,也希望您能够多多关注我们的更多内容!

(0)

相关推荐

  • C语言线性表之双链表详解

    目录 定义 1.删除 2.插入 3.建立 4.查找 总结 定义 链表是通过一组任意的存储单元来存储线性表中的数据元素,每一个结点包含两个域:存放数据元素信息的域称为数据域,存放其后继元素地址的域称为指针域.因此n个元素的线性表通过每个结点的指针域连接成了一个“链条”,称为链表.若此链表的每个结点中包含两个指针域,则被称为双链表. 双链表的结点结构定义如下: typedef struct node { DataType data; struct node *llink; struct node *

  • C语言实现的双链表功能完整示例

    本文实例讲述了C语言实现的双链表功能.分享给大家供大家参考,具体如下: Dlist.h #ifndef __DLIST_H__ #define __DLIST_H__ #include<cstdio> #include<malloc.h> #include<assert.h> typedef int ElemType; typedef struct Node { ElemType data; struct Node *prio; struct Node *next; }

  • C语言的线性表之顺序表你了解吗

    目录 线性表 —— 顺序表 (C语言) 1. 顺序表的储存结构 2. 顺序表的基本操作 2.1 顺序表的插入 2.2 顺序表的查找 2.3 顺序表的删除 总结 线性表 —— 顺序表 (C语言) 概念 线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表中的数据元素,这种表示也称做线性表的顺序储存结构或顺序映像.通常,称这种存储结构的线性表为顺序表 (Sequential List) .其特点是,逻辑上相邻的数据元素,其物理次序也是相邻的. 1. 顺序表的储存结构 #include <st

  • C语言实现循环双链表

    本文实例为大家分享了C语言实现循环双链表的具体代码,供大家参考,具体内容如下 #include<stdio.h> #include<stdlib.h> #include<stdbool.h> typedef int DataType; typedef struct Node { DataType data; // 数据域 struct Node * prior; // 前趋指针 struct Node * next; // 后继指针 }LinkList; LinkLis

  • C语言实现线性表的基本操作详解

    目录 前言 一.实训名称 二.实训目的 三.实训要求 四.实现效果 五.顺序存储代码实现 六.链式存储代码实现 前言 这里使用的工具是DEV C++ 可以借鉴一下 一.实训名称 线性表的基本操作 二.实训目的 1.掌握线性表的基本概念 2.掌握线性表的存储结构(顺序存储与链式存储) 3.掌握线性表的基本操作 三.实训要求 1.线性表可以顺序表也可以用单链表实现,鼓励大家用两种方式实现. 2.创建线性表时,数据从键盘输入整形数据 3.线性表类型定义和或各种操作的实现,可以用教材给出的方法,也可以自

  • 一起来看看C语言线性表的线性链表

    目录 定义 1.插入 2.建立线性链表 1)头插法 2)尾插法 3.删除 4.查找 5.求线性链表的表长 总结 定义 链表是通过一组任意的存储单元来存储线性表中的数据元素,每一个结点包含两个域:存放数据元素信息的域称为数据域,存放其后继元素地址的域称为指针域.因此n个元素的线性表通过每个结点的指针域连接成了一个“链条”,称为链表.若此链表的每个结点中只包含一个指针域,则被称为线性链表或单链表. 线性表的链式存储结构,它不需要用地址连续的存储单元来实现,因为它不要求逻辑上相邻的两个数据元素物理位置

  • C语言数据结构线性表教程示例详解

    目录 线性表 顺序表 线性表 数据结构里我们时常看到什么什么表,线性表是最基本.最简单.也是最常用的一种数据结构,其他各种表的万恶之源就是这个线性表,他是个啥其实顾名思义: 一个线性表是n个具有相同特性的数据元素的有限序列.数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的(注意,这句话只适用大部分线性表,而不是全部.比如,循环链表逻辑层次上也是一种线性表(存储层次上属于链式存储,但是把最后一个数据元素的尾指针指向了首位结点). 说的这么复杂其实就是

  • C语言线性表中顺序表超详细理解

    目录 一.本章重点 二.线性表 三.顺序表 四.静态顺序表接口实现 4.1顺序表初始化 4.2顺序表打印 4.3顺序表尾插 4.4顺序表尾删 4.5顺序表头插 4.6顺序表头删 4.7顺序表任意位置插入 4.8顺序表任意位置删除 五.动态顺序表接口实现 5.1顺序表的初始化 5.2顺序表打印 5.3顺序表尾插 5.4顺序表尾删 5.5顺序表头插 5.6顺序表头删 5.7顺序表任意位置插入 5.8顺序表任意位置删除 六.在线0j练习 一.移除元素(力扣) 二.合并两个有序数组(力扣) 一.本章重点

  • C语言线性表顺序表示及实现

    目录 准备工作 实现线性表 线性表的动态分配顺序存储结构 构造一个空的线性表 对线性表进行赋值 对线性表进行销毁 对线性表进行重置 判断线性表是否为空 获取线性表的长度 获取线性表某一位置对应的元素 在线性表某一位置插入元素 删除线性表某一位置的元素 求线性表某一元素的前驱 求线性表某一元素的后继 打印线性表 运行结果演示: 源码 线性表是最常用且最简单的一种数据结构.简而言之,一个线性表是n个数据元素的有限序列 线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素. 实现工具

  • C语言线性表的链式表示及实现详解

    目录 前言 代码实现 1. 单链表的结点构造 2. 构造一个空的头结点 3. 对线性表进行赋值 4.对线性表进行销毁 5.对线性表进行重置 6.判断线性表是否为空 7.获取线性表的长度 8.获取线性表某一位置对应的元素 9.在线性表某一位置插入元素 10.删除线性表某一位置的元素 11.求线性表某一元素的前驱 12.求线性表某一元素的后继 13.打印线性表 运行结果演示 源码 前言 线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素,而线性表的链式存储特点则是用一组任意的存储

  • Java线性表的顺序表示及实现

    目录 前言 一.什么是顺序表? 二.顺序表的实现 1. 准备工作 2. 获取顺序表的元素个数 3. 获取顺序表当前的容量 4. 顺序表是否为空 5. 在指定索引位置添加元素 6. 在顺序表末尾添加元素 7. 在顺序表头部添加元素 8. 获取指定索引位置的元素 9. 获取顺序表第一个元素 10. 获取顺序表最后一个元素 11. 修改指定索引位置的元素 12. 判断顺序表中是否包含指定元素 13. 获取顺序表中指定元素的索引 14. 删除指定索引位置的元素 15. 删除并返回顺序表第一个元素 16.

  • Python线性表种的单链表详解

    目录 1. 线性表简介 2. 数组 3. 单向链表 设计链表的实现 链表与顺序表的对比 1. 线性表简介 线性表是一种线性结构,它是由零个或多个数据元素构成的有限序列.线性表的特征是在一个序列中,除了头尾元素,每个元素都有且只有一个直接前驱,有且只有一个直接后继,而序列头元素没有直接前驱,序列尾元素没有直接后继. 数据结构中常见的线性结构有数组.单链表.双链表.循环链表等.线性表中的元素为某种相同的抽象数据类型.可以是C语言的内置类型或结构体,也可以是C++自定义类型. 2. 数组 数组在实际的

  • 数据结构简明备忘录 线性表

    线性表 线性表是线性结构的抽象,线性结构的特点是结构中的数据元素之间存在一对一的线性关系. 数据元素之间的位置关系是一个接一个的排列: .除第一个位置的数据元素外,其他数据元素位置的前面都只有一个数据元素. .除最后一个位置的外,其他数据元素位置的后面都只有一个元素. 线性表通常表示为:L=(D,R) D是数据元素的有限集合 R是数据元素之间关系的有限集合 线性表的基本操作: 复制代码 代码如下: public interface IListDS<T> { int GetLength(); /

  • Java数据结构(线性表)详解

    线性表的链式存储与实现 实现线性表的另一种方法是链式存储,即用指针将存储线性表中数据元素的那些单元依次串联在一起.这种方法避免了在数组中用连续的单元存储元素的缺点,因而在执行插入或 删除运算时,不再需要移动元素来腾出空间或填补空缺.然而我们为此付出的代价是,需要在每个单元中设置指针来表示表中元素之间的逻辑关系,因而增加了额外的存储空间的开销. 单链表 链表是一系列的存储数据元素的单元通过指针串接起来形成的,因此每个单元至少有两个域,一个域用于数据元素的存储,另一个域是指向其他单元的指针.这里具有

随机推荐