羊村懒王

这个屌丝很懒，什么也没留下！

热门标签

C语言数据结构链表(图文）_c语言链表的框架

作者：羊村懒王 | 2024-05-30 07:37:10

踩

c语言链表的框架

关于链表：以下文章仅仅代表我自己的看法，如果哪有不对还请各位大佬批评指出问题所在，互相交流，互相学习！！！

一、链表的简单理解与引入

1.1 链表的引入

首先！！！链表与顺序表的区别是顺序表在物理空间上和逻辑上都是连续的，而对于链表来说，链表在物理上不一定连续，因为其保存的元素是空间通过malloc从堆空间上申请出来的，而malloc在一次中申请多个空间是连续的，如果是多次申请的话就不是连续的。但是！！链表在逻辑上是连续的。

1.2 节点的理解

在链表中，用来保存元素的一段空间（这里边有俩个元素，一个是这个元素的值，一个是下一个元素的空间地址）。

1.3 链表的分类

链表主要有单向和双向、带头和不带头、循环和不循环三类，这三类通过组合就产生了8中链表情况。

1.单向或者双向

2.带头或者不带头

3.循环或者非循环

虽然但是有这么多链表，我们最最最最常用的就是“无头单向非循环链表”和“带头双向循环链表两种”！！！！大家只要把这俩种弄懂，那么其他的也就差不多了

无头单向非循环链表：

带头双向循环链表

注：无头单向非循环链表结构简单，一般不会单独用来存储数据，但是它会跟随其他的结构，作为它的子结构，这种链表种类在面试中考的比较多。而带头双向循环链表在实际中使用的比较多一些，它结构比较复杂，但是优势也是比较大的。

二、常用链表功能的实现

2.1 首先是节点的定义，

链表嘛，就是一个个节点串起来的。如2.1所见，节点就是俩个变量，一个是值域，一个是下一个节点的地址，我们只需要把它定义出来就行！！！如：


typedef int DataType;//这里是吧变量类型重新命名了，方便修改
 
typedef struct SListNode//这个是节点的定义
{
	DataType data;
	struct SListNode* next;
}SListNode;           //这里为它重新命名了，方便后边使用，否则每次都得加上struct

2.2 节点的创建

这里没啥难的，大家可以去看看malloc的用法。


SListNode* BuySListNode(DataType x) {
    SListNode*  newnode = (SListNode*)malloc(sizeof(SListNode));//这里是给这个新的节点在堆上申请了一处空间
    if (newnode == NULL)                   //这个就是申请空间失败了，即节点创建失败
    {
        printf("创建节点失败！！");
        exit(0);                         
    }
    newnode->data = x;                 //将参数x保存到值域
    newnode->next = NULL;              //在没有串起来的时候，将下一个地址保存为NULL
    return newnode;                    //将新创建的节点保存起来
}

2.3 单链表的尾插

尾插说白了就是找到最后一个元素，然后将它指向我们要插入的这个节点就行。但是注意要分情况，链表为空和链表不为空

assert: assert是一个调试宏，即assert是一个宏，这个宏只在debug模式下有效assert是断言，assert(表达式)，表达式的结果是真或者假；如果assert内部的表达式为真，assert就不会触发，程序可以继续往下执行如果assert内部的表达式为假，assert就触发，assert就会中断程序的执行---弹出一个窗口因此：assert是用来断言非法情况的，即当assert触发了之后，程序一定是处于非法的状态if(表达式)：当表达式为假，程序处于合法的情况，就使用if来检测条件链表不存在：根本就没有链表，就不能对链表进行任何操作 ----当往链表中插入或者删除元素时候，将链表不存在视为非法情况空链表：链表中没有插入任何节点---合法情况


//单链表的尾插
void SListPushBack(SListNode** pplist, DataType x)
{
    assert(pplist);              //保证品牌pplist这个链表存在
    if (*pplist == NULL)         //如果链表首地址为空，说明这块插入的节点就充当这个单链表的第一个元素
        *pplist = BuySListNode(x);
    else {                       //如果链表中还有其他的元素，这时候需要找到链表的最后一个元素，将他的next地址指向我们插入的这个节点
        SListNode* cur = *pplist;       //要进行遍历，故构建了一个相同类型的变量
        while (cur->next)           //如果是最后一个元素，这个元素的下一个就会为空，跳出循环
        {
            cur = cur->next;        //相当数组中的i++
        }
        cur->next = BuySListNode(x);   //跳出循环说明他是最后一个元素了。将它指向我们要插入的元素就行啦
    }
 
}

2.4 单链表的尾删

找到最后一个元素，让他的上一个元素指向NULL，注意要释放空间（free）。有两个注意，一个是注意控制最后一个元素和倒数第二个元素的移动，第二个是注意分类，下面代码的第二个else和第三个else可以直接合并为第三个一种情况。


// 单链表的尾删
void SListPopBack(SListNode** pplist)
{
    assert(pplist);
    if (*pplist == NULL)
        return;
    else if((*pplist)->next==NULL) {    //若链表只有一个元素的时候，将他释放掉，再讲链表的首地址指向NULL，否则会造成野指针的产生
        free(*pplist);
        *pplist = NULL;
    }
    else {
        SListNode* cur = *pplist;      //用来遍历数组
        SListNode* prev = NULL;       //保存上一个元素的地址
        while (cur->next)
        {
            prev = cur;
            cur = cur->next;
 
        }                           //当cur为最后一个的同时，prev刚好是倒数第二个，想不来的用
        free(cur);                  //123456自己推一下就懂啦
        prev->next = NULL;
    }
}

2.5 单链表的头插

注意最后更新*pplist的值


// 单链表的头插
void SListPushFront(SListNode** pplist, DataType x)
{
    assert(pplist);
    if ((*pplist) == NULL)
    {
        *pplist = BuySListNode(x);
    }
    SListNode* newnode = BuySListNode(x);
    newnode->next = *pplist;
    *pplist = newnode;
}

2.6 链表的头删

注意：每个删除都需要提前保存这个节点，然后将这个节点释放


// 单链表头删
void SListPopFront(SListNode** pplist)
{
    assert(pplist);
    if ((*pplist) == NULL)
    {
        return;
    }
    SListNode* cor = *pplist;
    *pplist = cor->next;
    free(cor);
}

2.7 单链表的查找

这个和数组的查找没啥区别，主要变通就行


// 单链表查找
SListNode* SListFind(SListNode* plist, DataType x)
{
    assert(plist);
    if (plist == NULL)
    {
        return NULL;
    }
    SListNode* cur = plist;
    while (cur)
    {
        if (cur->data == x)
        {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}

2.8 删除pos后边的值

注意条件与地址保存释放就行


//删除pos之后的值
void SListEraseAfter(SListNode* pos) {
    if (pos == NULL || pos->next == NULL)    //如果pos是空或者他是最后一个元素，都不能进行尾删
    {
        return;
    }
    SListNode* cur = pos->next;           //保存next的地址，以便释放
    pos->next = cur->next;
    free(cur);
}

2.9 在元素pos后插入x

这里注意链接链表的先后就行，这样的好处是2的位置不容易遗失


//在某个元素之后插入X
void SListInsertAfter(SListNode* pos, DataType x) {
    if (pos == NULL)
        return;
    else {
        SListNode* cur = BuySListNode(x);
         cur->next = pos->next;
        pos->next = cur;
    }
}

2.10 链表的销毁

注意点与上一个相同，要先保存下一个元素的地址，要不会造成地址遗失。


//链表的销毁
void SListDestroy(SListNode** plist)
{
    assert(plist);
    SListNode* cur = *plist;
    while (cur)
    {
        *plist = cur->next;
        free(cur);
        cur = *plist;
    }
    plist = NULL;
}

（链表相关oj题解答看下一章）

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/羊村懒王/article/detail/645890