深刻理解顺序表和链表

这篇具有很好参考价值的文章主要介绍了深刻理解顺序表和链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

顺序表和链表是我们学习数据结构中不可或缺的部分,他们都属于线性表之一。大家在C语言中都学过数组:⼀组相同类型元素的集合而且在内存中存储是连续的。数组也属于顺序表的一种,顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构。顺序表的出现就是为了方便实现增删查改等等操作,大家都用C语言写过简单的通讯录吧,其中用到的就是顺序表。

顺序表

顺序表分为两种:静态顺序表和动态顺序表。

 静态顺序表:使用定长数组存储元素

比如定义了一个结构体:

#define N 10
typedef int SLDatatype;
struct SeqList {
    SLDatatype a[N];
    int size;//存储的有效数据的个数
};

这样结构中数组的长度就是固定的,数据多了不够用,数据少了又浪费内存空间,难以一次确定。

动态顺序表:使用动态开辟的数组存储

typedef int SLDatatype;
typedef struct SeqList {
    SLDatatype *a;
    int size;//存储的有效数据的个数
    int capacity;//容量
}SL;

对比一下我们就会发现数据的类型变成了指针,这样的好处是方便我们动态的分配(malloc)和调整(realloc)空间大小。而且多定义了一个容量,用来记录和比较存储的有效数据的个数,当数据个数达到最大我们就可以调整容量(加一个常量或变为原来的二倍),以此不断实现扩容。

无论哪种顺序表都是在一段连续的空间上实现增删查改操作,改变一个数据元素其他的也需要进行相应位置的调整,时间复杂度太高。这时候就出现了链表来更高效的实现我们的操作。

链表

链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的

链表的物理结构如下:

深刻理解顺序表和链表,链表,数据结构,c语言

链表的结构分为八种:单向的、双向的,带头的、不带头的,循环的、不循环的,单向无头非循环链表一般是最爱考察大家的,因为它的结构简单(条件少),操作起来复杂;双向带头循环链表结构最复杂(条件多),但它的操作却最简单。我们一起来看看这两种链表。

单向无头非循环链表

我们先定义一个结构体:

typedef int SLTDataType;
typedef struct SListNode {
    SLTDataType data;
    struct SListNode* next;
}SLTNode;

插入

我们定义一个SLTPushFront函数来实现链表前插:

void SLTPushFront(SLTNode** pphead, SLTDataType x);

函数的实现:

SLTNode* BuyLTNode(SLTDataType x) {
    SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    if (newnode == NULL) {
        perror("malloc fail");
        return 1;
    }
    newnode->data = x;
    newnode->next = NULL;
    return newnode;
}

void SLTPushFront(SLTNode** pphead, SLTDataType x) {
    assert(pphead);//链表为空,pphead也不为空,因为他是头指针的地址
    //assert(*pphead);//不能断言,链表为空,也需要能插入
    SLTNode* newnode = BuyLTNode(x);
    newnode->next = *pphead;//把newnode指针指向头指针指向的节点
    *pphead = newnode;//头指针指向newnode
}

BuyLTNode函数是为了开辟指针类型的结构体,SLTPushFront函数是实现在*pphead指针前面插入新开辟的newnode,然后让*pphead指向newnode实现指针的向后移动,尾插也是一样的道理。

注意:大家肯定会有疑问,为什么我们传入的实参是二级指针呢?这是因为我们改变的是传入的结构体中指针的指向(主体是结构体的指针),所以要用结构体指针的地址(二级指针)。我们再回顾之前的顺序表传参,其中用的就是一级指针,它要改变的是结构体中某个成员(主体是结构体的成员),这样大家应该就很容易能理解了。

删减

我们定义一个SLTPopFront函数来实现链表头删:

void SLTPopFront(SLTNode** pphead);

函数的实现:

void SLTPopFront(SLTNode** pphead) {
    //没有结点(空链表)
    assert(pphead);//链表为空,pphead也不为空,因为他是头指针的地址
    assert(*pphead);//链表为空,不能头删
    //一个节点
    if ((*pphead)->next == NULL) {
        free(*pphead);
        *pphead = NULL;
    }
    else {
        //多个节点
        SLTNode* tail = *pphead;
        *pphead = (*pphead)->next;
        free(tail);
    }
    SLTNode* tail = *pphead;
    *pphead = (*pphead)->next;
    free(tail);

}

结构越简单的链表之所以操作起来复杂,是因为它要分情况来判断:如果是空链表,就不能进行删除操作;如果链表只有一个节点,那么删除之后链表就为空;如果链表有多个节点,就要让头节点指向下一个,然后释放头节点;尾删也是一样的道理。

查找

我们定义一个STFind函数来实现链表查找:

SLTNode* STFind(SLTNode* phead, SLTDataType x);

函数的实现:

SLTNode* STFind(SLTNode* phead, SLTDataType x) {
    SLTNode* cur = phead;
    while (cur) {
        if (cur->data == x) {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}

我们定义一个cur指针指向头节点,让cur依次往后遍历,如果cur指针指向的节点数据是我们要找的就返回,否则返回空。

修改

数据的修改其实就是在数据查找到之后,在查找的基础上把查找位置的值修改成我们想要的值就行了。

双向带头循环链表

双向跟单向区别点就是双向有指向前一个和后一个两个指针(prev和next),单向只有一个next指针;头节点就是一个哨兵位,不存储数据,只是起监视的作用;循环就是链表最后指向不为空,而是指向头节点。

我们先定义一个结构体:

typedef int LTDataType;
typedef struct ListNode {
    struct ListNode* next;
    struct ListNode* prev;
    LTDataType data;
}LTNode;

初始化

使用双向带头循环链表我们需要先进行链表的初始化让头指针的prev和next指向自己:

LTNode* LTInit() {
    LTNode*  phead = BuyTNode(-1);
    phead->next = phead;
    phead->prev = phead;
    return phead;//用LTNode*类型返回头指针可以避免用二级指针
}

我们想要进行头指针的操作然后返回,如果我们跟之前一样用二级指针会显得很复杂,而且有些同学对二级指针的理解也不是很深,那么有没有什么好的方法可以避免使用二级指针呢?答案是有。我们可以把函数类型从void变为LTNode*,这样就可以返回头指针从而避免使用二级指针。

在指定位置前插入

我们定义一个LTInsert函数来实现在指定位置前插入:

void LTInsert(LTNode* pos, LTDataType x);//在pos之前插入

函数的实现:

void LTInsert(LTNode* pos, LTDataType x) {
    assert(pos);
    LTNode* prev = pos->prev;
    LTNode* newnode = BuyTNode(x);
    // prev   newnode   pos
    prev->next = newnode;
    newnode->prev = prev;
    newnode->next = pos;
    pos->prev = newnode;
}

我们想要进行pos位置之前的插入,也就是想在pos->prev和pos之间插入newnode。就可以用prev和next来固定位置。相信有些眼尖的小伙伴也发现了,我们不仅定义了newnode指针,还定义了一个prev指针。这样的好处就是我们可以随意用prev和next指针,而不用考虑谁先谁后的指向顺序。

比如我们不定义prev指针,而是用pos->prev来代替:
pos->prev->next = newnode;
newnode->prev = pos->prev;
newnode->next = pos;
pos->prev = newnode;

那如果我们替换上面三四行跟一二行的代码会怎么样呢?

newnode->next = pos;
pos->prev = newnode;

pos->prev->next = newnode;
newnode->prev = pos->prev;

答案是错误,因为我们将pos->prev指向newnode后再执行pos->prev->next操作就会让pos指向自己,发生逻辑错误。我们发现插入之前必须先改变前面再改变后面,所以最好的办法就是再定义一个指针prev,这样不仅代码可读性更好,而且不会发生代码的逻辑错误。

如果你就是不想麻烦多定义一个新的指针,那么请记住这个结论:插入之前必须先改变前面再改变后面,插入之后必须先改变后面再改变前面。

头插和尾插

头插:

void LTPushFront(LTNode* phead, LTDataType x) {
    assert(phead);

    LTInsert(phead->next,x);
}

尾插:

void LTPushBack(LTNode* phead, LTDataType x) {
    assert(phead);

    LTInsert(phead, x);
}

这样的操作小伙伴们有没有耳目一新,代码的复用性在这时候就显现出来了。

在指定位置删除

我们定义一个 LTErase函数来实现指定位置的删除:

void LTErase(LTNode* pos);

代码实现:

void LTErase(LTNode* pos) {
    assert(pos);
    LTNode* posPrev = pos->prev;
    LTNode* posNext = pos->prev;
    posPrev->next = posNext;
    posNext->prev = posPrev;
    free(pos);
}

这样就实现了pos位置的删除操作。

头删和尾删

头删:

void LTPopFront(LTNode* phead) {
    assert(phead);
    assert(!LTEmpty(phead));
    LTErase(phead->next);
}

尾删:

void LTPopBack(LTNode* phead) {
    assert(phead);
    assert(!LTEmpty(phead));
    LTErase(phead->prev);
}

查找

我们定义一个LTFind函数来实现值的查找:

LTNode* LTFind(LTNode* phead, LTDataType x);

函数实现:

LTNode* LTFind(LTNode* phead, LTDataType x) {
    assert(phead);
    LTNode* cur = phead->next;
    while (cur != phead) {
        if (cur->data == x) {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}

需要注意的是phead是我们链表的哨兵位,不能删除,别误删了。而修改就是查找到之后进行值的替换。

顺序表和链表的比较

存储空间上:顺序表物理结构上一定连续;链表逻辑结构上连续,但物理结构上不一定连续。

随机访问:顺序表支持O(1),链表不支持O(N);因为链表比顺序表CPU高速缓存命中率更低。

任意位置插入或者删除元素:顺序表可能需要搬移元素,效率低O(N);链表只需修改指针指向。

空间不够:顺序表扩容,有代价,可能会造成空间浪费;链表按需申请释放空间。

学会顺序表和链表有助于我们进行数据更加高效的管理,如果觉得这篇文章对你有帮助或者短时间内还不能全部吸收可以收藏下来慢慢理解,书读百遍其义自见!也欢迎大家进行批评指正,理解顺序表和链表可以帮助我们更好的编写程序,一起加油深刻理解顺序表和链表,链表,数据结构,c语言深刻理解顺序表和链表,链表,数据结构,c语言深刻理解顺序表和链表,链表,数据结构,c语言文章来源地址https://www.toymoban.com/news/detail-816650.html

到了这里,关于深刻理解顺序表和链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【手撕数据结构】(三)顺序表和链表

    🎗️线性表是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串… 🎗️线性表在逻辑上是线性结构,也就说是一条连续的直线。但是在物理结构上并不一定是连续的,线性表在物理上存储

    2024年02月05日
    浏览(54)
  • 【数据结构初阶】顺序表和链表(1)

    线性表(linear list) 是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使 用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上

    2024年02月08日
    浏览(242)
  • 数据结构奇妙旅程之顺序表和链表

    ꒰˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱ ʕ̯•͡˔•̯᷅ʔ大家好,我是xiaoxie.希望你看完之后,有不足之处请多多谅解,让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN 如需转载还请通知˶⍤⃝˶ 个人主页:xiaoxieʕ̯

    2024年02月05日
    浏览(66)
  • 数据结构修炼第二篇:顺序表和链表

    第一章 时间复杂度和空间复杂度 第二章 顺序表,列表 第三章 栈和队列 第四章 二叉树 第五章 排序 作者:🎈乐言🎈 简介:🎈大一学生,目前在致力于c/c++/python,高数的学习,有问题尽管问我,关注后私聊! 持续更新专栏:《c进阶》,《数据结构修炼》 🚀 (优质好文持

    2024年02月02日
    浏览(118)
  • 【数据结构篇C++实现】- 线性表 - 顺序表和链表

    友情链接:C/C++系列系统学习目录 故事导入: 幼儿园放学时,一个班级的小朋友,一个跟着一个排队出校,有一个打头,有一个收尾,当中的小朋友每一个都知道他前面和后面的一个是谁,就如同一根线把他们串联了起来。如此具有像线一样的性质的表就叫线性表 线性表(

    2024年02月07日
    浏览(57)
  • 初阶数据结构之---顺序表和链表(C语言)

    线性表: 线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构。线性表在逻辑上是线性结构,也就是说是连续的一条直线。但在物理上并不一定是连续的。线性表在物理上存储时,通常以 数组 和 链式结构 的形式存储。

    2024年02月22日
    浏览(67)
  • <数据结构>顺序表和链表的比较|缓存命中率

    💭前言:通过之前对顺序表和链表的实现,我们可以发现在增删查改某些操作上两者的效率前言有所差异,本篇文章将总结二者的异同。 顺序表的实现 http://t.csdn.cn/Lxyg2 单链表的实现 http://t.csdn.cn/rHgjG 双链表的实现 http://t.csdn.cn/j3amO 📚顺序表通过数组来实现的,所以在物理

    2024年02月05日
    浏览(52)
  • 数据结构(王道)——线性表之静态链表&顺序表和链表的比较

      如何定义一个静态链表     初始化静态链表:   静态链表的查找、插入、删除           创: 销:   增、删:   查:   顺序表、链表该如何选择?  

    2024年02月16日
    浏览(125)
  • 顺序表和链表【数据结构】【基于C语言实现】【一站式速通】

    目录 顺序表 顺序表的优点 顺序表的实现 1.结构体的定义 2.初始化数组  3.插入数据 4.其余接口函数的实现 5.释放内存 顺序表的缺陷 单向链表 单向链表的优点 单向链表的实现 1.链表的定义  2.链表的初始化 3.其余接口函数的实现 5.释放内存 单向链表的缺陷 双向链表 双向链

    2024年01月24日
    浏览(53)
  • 探索树形数据结构,通识树、森林与二叉树的基础知识(专有名词),进一步利用顺序表和链表表示、遍历和线索树形结构

      结点之间有分支,具有层次关系 树的定义 : 树 (tree)是n(n≥0)个有限集。 若n = 0,则称为空树; 若n 0,则它满足如下两个条件: 有且仅有一个特定的称为根(Root)的结点; 其余结点可分为m(m≥0)个互不相交的有限集T1,T2,T3,.....,Tm,其中每一个集合本身又是一棵树,并称为根的

    2024年02月01日
    浏览(53)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包