首页 > 其他分享 >数据结构————————单链表

数据结构————————单链表

时间：2024-10-13 08:50:10浏览次数：3  
标签：pre 结点 单链 Slist next phead pos 数据结构

1 单链表

1.1 概念与结构

        概念： 链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构，数据元素的逻辑顺序是通过链表中的 指针链接次序实现的 。单链表就如同火车一样去掉或加上车厢不会影响到其他的车厢那么在链表中，每节车厢是什么样子的呢？如图下： 1.1.1 结点         与顺序表不同的是，链表⾥的每节"⻋厢"都是独⽴申请下来的空间，我们称之为“结点/结点” 结点的组成主要有两个部分：当前结点要保存的数据和保存下⼀个结点的地址（指针变量） 。 图中指针变量 plist保存的是第⼀个结点的地址，我们称plist此时“指向”第⼀个结点，如果我们希望 plist“指向”第⼆个结点时，只需要修改plist保存的内容为0x0012FFA0。 链表中每个结点都是独⽴申请的（即需要插⼊数据时才去申请⼀块结点的空间），我们需要通过指针 变量来保存下⼀个结点位置才能从当前结点找到下⼀个结点。 1.1.2 链表的性质 1、 链式机构在逻辑上是连续的，在物理结构上不⼀定连续 2、 结点⼀般是从堆上申请的 3、 从堆上申请来的空间，是按照⼀定策略分配出来的，每次申请的空间可能连续，可能不连续 结合前⾯学到的结构体知识，我们可以给出每个结点对应的结构体代码： // 定义一个结构体链表 ypedef struct SlsitNode {
    SLDatetype data; //结点数据
    struct SlsitNode* next; //指针变量⽤保存下⼀个结点的地址
}Slist;  / /申请新的结点
Slist* SLTbuycode(SLDatetype x)
{
    Slist* node = (Slist*)malloc(sizeof(Slist));
    if (node == NULL)
    {
        perror("malloc fail");
        exit(1);
    }
    node->data = x;
    node->next = NULL;
    return node;
} 首先来实现单链表的尾插 void Insertback(Slist **phead,SLDatetype x)
{
    assert(phead);
    Slist* newcode = SLTbuycode(x);
    if (*phead == NULL)
    {
        *phead = newcode;
    }
    else
    {
        Slist* Sltail = *phead;
        while (Sltail->next)
        {
            Sltail = Sltail->next;
        }
        Sltail->next = newcode;
        newcode->next = NULL;
    }
}    进入函数首先先判断是否为空，然后去申请一个新的结点空间，如果头节点为空的话就让我们申请的结点变成头节点，如果不为空就去遍历结点找到最后一个结点让最后结点的next指向我们申请的新的结点，然后让我们申请新的结点的next赋值为空 实现单链表的头插 void Inserthead(Slist** phead, SLDatetype x)
{
    assert(phead);
    Slist* newcode = SLTbuycode(x);
    newcode->next = *phead;
    *phead = newcode;
} 首先判断传来的是否为空，然后申请一个新的结点赋值给newcode,让newcode->next指向*phead，然后在把phead变成头节点 //链表打印 void Sltprintf(Slist* phead) {
    Slist* p = phead;
    while (p != NULL)
    {
        printf("%d->", p->data);
        p = p->next;
    }
    printf("NULL");
    printf("\n");
} 因为不需要改变结点的值只需要遍历数组，所以只需要用形参就行，先创建一个新的结点指向头节点以防改变头节点的位置，然后判断是否为空不为空就一直遍历让p一直指向后面的结点然后输出 //尾删 void popback(Slist** phead)
{
    assert(phead&&*phead);
    Slist* sltail = *phead;
    if ((*phead)->next == NULL)
    {
        free(*phead);
        *phead = NULL;
    }
    Slist* pre = NULL;
    while (sltail->next)
    {
        pre = sltail;
        sltail = sltail->next;
    }
    pre->next = NULL;
    free(sltail);
    sltail = NULL;
} 要想删除结点就要结点不能为空，定义一个新的指针指向头节点如果要删除只有一个结点那就直接释放然后把头节点指向空，如果不是就在定义一个指针指向空然后去遍历一直找到最后结点的前一个结点让前一个结点的next直接指向空然后去释放最后一个结点。 //头删
void pophead(Slist** phead)
{
    assert(phead && *phead);
    Slist* p = (*phead)->next;
    free(*phead);
    *phead =p;
} 要把头节点的next赋给新定义的结点然后去释放头节点，最后在重新让phead指向新的结点。 //查找数据
Slist* sltfind(Slist* phead, SLDatetype x)
{
    Slist* prer = phead;
    while (prer!=NULL)
    {
        if (prer->data == x)
        {
            return prer;
        }
        prer = prer->next;
    }
    return NULL;
} 因为查找只需要遍历数组只需要穿形式参数不需要改变值，首先定义一个让他指向头结点然后去遍历数组如果找到了就返回这个结点如果没有找到就返回NULL； //指定位置前插入
void SLtInsert(Slist** phead, Slist* pos, SLDatetype x)
{
    assert(phead && pos);
    
    if (*phead== pos)
    {
        Inserthead(phead, x); 
    }
    else {
        Slist* newcode = SLTbuycode(x);
        Slist* pre = *phead;
        while (pre->next != pos)
        {
            pre = pre->next;
        }
        newcode->next = pos;
        pre->next = newcode;
    }
} 如果要在头结点前插入数据就相当于头插可以调用一下头插函数，然后不是就去申请一个空间然后一直遍历让他找到pos的前一个结点然后让新结点的next指向pos，然后在让pre的next指向newcode； //在指定位置后插入数据
void SLtInsertback(Slist* pos, SLDatetype x)
{
    assert(pos); 
    Slist* newcode = SLTbuycode(x);
    newcode->next=pos->next;
    pos->next = newcode; 
} 首先要让申请的新结点的next指向pos的next然后在把pos的next指向新结点这； //在指点位置前删除数据
void sltdelet(Slist** phead, Slist* posr)
{
    assert(phead && posr); 
    if (posr == *phead)
    {
        pophead(phead);
    }
    Slist* pre = *phead;
    while (pre->next != posr)
    {
        pre = pre->next;
    }
    pre->next = posr->next;
    free(posr);
    posr = NULL;
} 如果指定的位置时头结点就相当于头删除直接调用头删函数就行，如果不是头结点就定义一个结构体的指针指向头结点然后一直遍历到指定位置的前一个结点把指定位置的next赋值给pre的next最后释放posr。 //在指定结点之后删除
void sltdeletback(Slist* pos)
{
    assert(pos&&pos->next);
    Slist* del = pos->next;
    pos->next = del->next;
    free(del);
   } 这里也比较简单只需要得知pos指向的下一个结点的下一个地址就简单了； //单链表的释放 void sltdestory(Slist** phead)
{
    Slist* pre = *phead;
    while (pre)
    {
        Slist* node = pre->next;
        free(pre);
        pre = node;
    }
    *phead = NULL;
} 轮流释放每一个结点然后让释放前把结点的next存到一个新的结构体指针里面然后去释放单链表 下面时三个部分的代码 Sqlist.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int SLDatetype;

typedef struct SlsitNode {
    SLDatetype data;
    struct SlsitNode* next;
}Slist;        
//尾插
void Insertback(Slist *phead, SLDatetype x);
//打印
void Sltprintf(Slist* phead);
//头插
void Inserthead(Slist** phead, SLDatetype x);
//尾删
void popback(Slist** phead);
//头删
void pophead(Slist** phead);
//查找
Slist* sltfind(Slist* phead, SLDatetype x);
//在指定之前插入数据
void SLtInsert(Slist** phead,Slist *pos ,SLDatetype x);
//在指定之后插入数据
void SLtInsertback( Slist* pos, SLDatetype x);
//在指定之前删除数据
void sltdelet(Slist** phead, Slist* pos);
//在指定之后删除数据
void sltdeletback(Slist* pos);
//单链表的销毁
void sltdestory(Slist **phead);

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Sqlist.h"
void test()
{
    /*Slist* node1 = (SLDatetype*)malloc(sizeof(Slist));
    Slist* node2 = (SLDatetype*)malloc(sizeof(Slist));
    Slist* node3 = (SLDatetype*)malloc(sizeof(Slist));
    Slist* node4 = (SLDatetype*)malloc(sizeof(Slist));

    node1->data = 1;
    node2->data = 2;
    node3->data = 3;
    node4->data = 4;

    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = NULL;*/
    Slist* plist = NULL;
    Insertback(&plist ,1);
    Insertback(&plist, 2 );
    Insertback(&plist, 3);
    Sltprintf(plist); 
/*    Inserthead(&plist, 1);
    Sltprintf(plist);
    Inserthead(&plist, 2);
    Sltprintf(plist);*/ 
    /*Inserthead(&plist, 3);*/
    /*popback(&plist);*/
    /*Sltprintf(plist);*/
    Slist* find = sltfind(plist,1);
    /*if (find==NULL)
    {
        printf("没找到");
    }
    else
    {
        printf("找到了");
    }*/
    /*SLtInsert(&plist, find, 99);
    Sltprintf(plist);*/
     SLtInsertback(find,99);
     Sltprintf(plist);
    /* sltdelet(&plist,find);
     Sltprintf(plist);*/
    /* sltdeletback(find);*/
     /*Sltprintf(plist);*/
     /*sltdestory(&plist);*/
}

int main()
{
    test();
}

sllist.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Sqlist.h"
//打印
void Sltprintf(Slist* phead) {
    Slist* p = phead;
    while (p != NULL)
    {
        printf("%d->", p->data);
        p = p->next;
    }
    printf("NULL");
    printf("\n");
}
//申请新的结点
Slist* SLTbuycode(SLDatetype x)
{
    Slist* node = (Slist*)malloc(sizeof(Slist));
    if (node == NULL)
    {
        perror("malloc fail");
        exit(1);
    }
    node->data = x;
    node->next = NULL;
    return node;
}
//尾插
void Insertback(Slist **phead,SLDatetype x)
{
    assert(phead);
    Slist* newcode = SLTbuycode(x);
    if (*phead == NULL)
    {
        *phead = newcode;
    }
    else
    {
        Slist* Sltail = *phead;
        while (Sltail->next)
        {
            Sltail = Sltail->next;
        }
        Sltail->next = newcode;
        newcode->next = NULL;
    }
}
//头插
void Inserthead(Slist** phead, SLDatetype x)
{
    assert(phead);
    Slist* newcode = SLTbuycode(x);
    newcode->next = *phead;
    *phead = newcode;
}
//尾删
void popback(Slist** phead)
{
    assert(phead&&*phead);
    Slist* sltail = *phead;
    if ((*phead)->next == NULL)
    {
        free(*phead);
        *phead = NULL;
    }
    Slist* pre = NULL;
    while (sltail->next)
    {
        pre = sltail;
        sltail = sltail->next;
    }
    pre->next = NULL;
    free(sltail);
    sltail = NULL;
}
//头删
void pophead(Slist** phead)
{
    assert(phead && *phead);
    Slist* p = (*phead)->next;
    free(*phead);
    *phead =p;
}
//查找数据
Slist* sltfind(Slist* phead, SLDatetype x)
{
    Slist* prer = phead;
    while (prer!=NULL)
    {
        if (prer->data == x)
        {
            return prer;
        }
        prer = prer->next;
    }
    return NULL;
}
//指定位置前插入
void SLtInsert(Slist** phead, Slist* pos, SLDatetype x)
{
    assert(phead && pos);
    
    if (*phead== pos)
    {
        Inserthead(phead, x); 
    }
    else {
        Slist* newcode = SLTbuycode(x);
        Slist* pre = *phead;
        while (pre->next != pos)
        {
            pre = pre->next;
        }
        newcode->next = pos;
        pre->next = newcode;
    }
}
//在指定位置后插入数据
void SLtInsertback(Slist* pos, SLDatetype x)
{
    assert(pos); 
    Slist* newcode = SLTbuycode(x);
    newcode->next=pos->next;
    pos->next = newcode; 
}
//在指点位置前删除数据
void sltdelet(Slist** phead, Slist* posr)
{
    assert(phead && posr); 
    if (posr == *phead)
    {
        pophead(phead);
    }
    Slist* pre = *phead;
    while (pre->next != posr)
    {
        pre = pre->next;
    }
    pre->next = posr->next;
    free(posr);
    posr = NULL;
}
//在指定结点之后删除
void sltdeletback(Slist* pos)
{
    assert(pos&&pos->next);
    Slist* del = pos->next;
    pos->next = del->next;
    free(del);
    del = NULL;
}
void sltdestory(Slist** phead)
{
    Slist* pre = *phead;
    while (pre)
    {
        Slist* node = pre->next;
        free(pre);
        pre = node;
    }
    *phead = NULL;
}

标签：pre,结点,单链,Slist,next,phead,pos,数据结构
From： https://blog.csdn.net/qwer55588/article/details/142891295

相关文章

  • python数据结构学习第一章——栈
    在这片文章中，我们使用python3.8自制一个具有基本功能的栈结构，它的功能只有push，pop，peek这三个功能`#!/usr/bin/envpython#*coding:utf-8*#@Time:2024/9/1519:26#@Author:Huzhaojun#@Version：V1.0#@File:test.py#@desc:#数据结构复习第一章，栈结构的......
  • 数据结构与算法Python版p26-p28 无序表链表实现、有序表
    B站视频-数据结构与算法Python版无序表链表实现、有序表一、节点二、无序表三、有序表一、节点#节点classNode:def__init__(self,initdata):self.data=initdataself.next=NonedefgetData(self):returnself.data......
  • 高清图解28个高并发之数据结构/数据结构场景匹配技巧分析(高并发精通篇一)
    ​Java集合以ArrayList、LinkedList、HashSet、TreeSet和HashMap等组件为核心，构筑了强大而灵活的数据结构体系。这些组件精心设计以满足不同的性能和功能需求，如ArrayList的动态数组支持快速随机访问，而LinkedList的双向链表结构则擅长于频繁的插入和删除操作。HashSe......
  • 链表-数据结构
    链表的连接简单题目描述：创建两个链表：S1,S2；让s1和s2实现合并连接；连接要求：输入s1节点的数值下标和输入s2的数值下标，如果数值相同实现连接；比如:cin>>s1(2),cin>>s2(0);就让s1的下标2：数值1和s2的下标0：数值1比较相同--------321123s1数值1在跟s......
  • 2024.10.7（数据结构的栈）
    顺序栈是利用顺序存储结构实现的栈，指针top指示栈顶在顺序栈的位置。base为存储空间基地址，S.top-S.base是栈中元素的个数，类似Length。栈为空时：S.topS.base;栈满时：S.top-S.baseMAXSIZE;顺序栈，top在最高元素的上一个，base位置是最低元素，故取栈顶元素要取top-1的：队列先进先出。......
  • 数据结构与算法 - 单链表 & 双链表 -- 概念+实现
    文章目录前言一、顺序表的缺陷二、链表是如何设计的？三、链表的分类四、链表的概念及其结构1、链表的概念：2、链表的结构五、不带头单向不循环链表的实现(一)、SList.h的实现(二)、SList.c的实现1、初始化2、创建结点3、头插4、尾插4、头删5、尾删6、指定p......
  • 【趣学C语言和数据结构100例】
    【趣学C语言和数据结构100例】问题描述一个球从100m高度自由落下，每次落地后反弹回原高度的一半，再落下，求它在第10次时共经过多少米，第10次反弹多高。猴子吃桃问题。猴子第1天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了一个。第2天早上又将剩下的桃子吃掉一......
  • Redis原理篇 之数据结构
    Redis原理篇之数据结构文章目录Redis原理篇之数据结构1动态字符串SDS1.1SDS介绍1.2SDS扩容1.3SDS优点2IntSet2.1IntSet介绍2.2IntSet升级2.3总结3Dict3.1Dict的原理3.2Dict的扩容3.3Dict的收缩3.4Dict的rehash3.5总结4ZipList4.1ZipList原理4.2Zi......
  • HALCON数据结构之数组
    1.1Tuple数组的基本操作*1、Tuple数组元素的创建*1.1、创建一个空数组assign([],empty_tuple)//采用赋值操作empty_tuple:=[]//采用赋值操作*1.2、创建一个整型数组assign([1,2,3,4,5,6,7,8,9,10],tupleInt1)//采用赋值操作tupleInt1:=[1,0,3,4,5,6,7,8,9]/......
  • 数据结构：快排
    注：所有的快排针对无重复大量数据是很快的，但是针对有重复大量数据的排序是很慢的；1.霍尔(hoare)版本时间复杂度:O（N*logN）稳定性：不稳定；在fun()函数while判断时一不小心就会存在越界和和死循环问题；霍尔版本的快排，代码如下：主要实现再func()和quick()函数中intfunc(intarr[],in......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99