首页 > 其他分享 >数据结构-单向不带头不循环链表

数据结构-单向不带头不循环链表

时间：2025-01-21 21:29:16浏览次数：3  
标签：LKNode val temp 单向 链表 数据结构 LinkNode 节点

链表知识总结

逻辑结构：线性结构（元素之间存在一对一关系）
存储结构（物理结构）：链式存储（存储顺序和逻辑顺序不在乎是否一致）

1.链表的特点：擅长进行动态删除和增加操作，不擅长随机访问（需要遍历，因为链表不按顺序存放）

2.链表分类：单双向链表

单链表：元素节点有两部分组成（数据域-存储当前的元素、指针域-指向下一个节点地址）
双链表：元素节点有三部分组成（数据域-存储当前元素节点，2个指针域，1个用来指向上一个元素节点地址，1个用来指向下一个元素节点地址）

带头不带头：是否带有头指针
循环不循环：尾结点的next指针指向空-不循环，指向首元素节点或头指针-循环

3.链表的操作：创建、销毁、增（头插、尾插、中间插）删（头删、尾删、中间删）改查
由此得出：链表的分类的一共有8种       讲解单向、不带头、不循环链表

1、链表的介绍          链表是一种链式存储的线性表

1.1、链表的特点     节点定义成结构体类型

链表是一种基本的数据结构，它由一系列节点组成，每个节点包含一个值和指向下一个节点的指针

特点：1.不要求大片连续空间，改变容量方便。2.可以动态的添加和删除节点

缺点：不方便随机存取，要耗费一定空间存放指针。

2、链表的分类

链表可以分为三种类型：

  • 单向链表：每个节点只有一个指针指向下一个节点，最后一个节点的指针指向NULL。

  • 双向链表：每个节点有两个指针，分别指向上一个节点和下一个节点，可以在O(1)时间内实现向前和向后遍历。

  • 循环链表：在单向或双向链表的基础上，将最后一个节点的指针指向头节点，形成一个环。

链表的种类其实有很多种，按照单双向、带头不带头、循环不循环，一共可以分为8种类型，但最常见就是单向链表（单向不带头不循环）和双向链表（双向带头）

带头：有一个指针，专门指向首元素节点

3、链表的操作

链表的操作包括插入、删除、查找、遍历等。

  • 插入操作：可以在链表头或尾插入节点，也可以在指定位置插入节点。    头插、尾插、中间插
  • 删除操作：可以删除指定节点或按照值删除节点。                                    头删、尾删、中间删
  • 查找操作：可以查找指定节点或按照值查找节点。
  • 遍历操作：可以遍历整个链表，输出每个节点的值或执行其他操作

4、单向链表

单向链表是由若干个节点组成的数据结构，每个节点包含两个部分：数据域和指针域。

数据域存储节点的数据，指针域存储下一个节点的地址。

单链表的一个存储节点包含两部分：

data部分称为数据域，用于存储线性表的一个数据元素；   放的是元素值也可以叫值域

link部分称为指针域，用于存放一个指针，该指针指示链表下一个结点的开始存储地址   

指向下一个节点的指针

5、单链表的操作

5.1、main.c

#include <stdio.h>
#include "01.h"

int main() {
    fn3();
    return 0;
}

5.2、01.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>  //包含有调试文件

//定义单向、不带头、不循环链表的元素节点结构体类型
typedef int eleT;
typedef struct Link_Node {
    eleT val;//数据域  存储节点元素值
    struct Link_Node* next;//指针域   指向下一个节点
}LKNode;


void fn3(void);
void printf_menu(void);
LKNode* init_Link(eleT val);
void print_Link(LKNode* LinkNode);
void head_insert(LKNode** LinkNode, eleT val);
void tail_insert(LKNode* LinkNode, eleT val);
void head_delete(LKNode** LinkNode);
void tail_delete(LKNode** LinkNode);
LKNode* find_item(LKNode* LinkNode, eleT val);
void middle_delete(LKNode* LinkNode, eleT val);//中间删除1.0
void mid_del(LKNode* temp);//中间删除2.0
void mid_insert(LKNode* temp, eleT newval);
void destory(LKNode** LinkNode);

5.3、01.c

#include "01.h"

void fn3(void) {
    int order = 0;//接收用户输入的命令
    printf_menu();
    LKNode* LinkNode = NULL;    //存放头结点指针（地址）
    eleT val = 0;
    LKNode* temp = NULL;

    while (1) {
        printf("请输入您的操作指令：");
        scanf("%d", &order);
        switch (order) {
        case 1:
            //初始化    初始化一个头结点，不包含头（头结点包含元素）
            printf("请输入头结点元素值：");
            scanf("%d", &val);
            LinkNode=init_Link(val);
            break;
        case 2:
            //遍历
            print_Link(LinkNode);
            break;
        case 3:
            //链表头插
            printf("请输入要头插的元素");
            scanf("%d", &val);
            head_insert(&LinkNode,val);//头插，头结点要变，只能传地址
            break;
        case 4:
            //链表尾插
            printf("请输入要尾插的元素");
            scanf("%d", &val);
            tail_insert(LinkNode, val);//尾部插入，头结点不变，也可以传值
            break;
        case 5:
            //链表头删
            head_delete(&LinkNode);
            break;
        case 6:
            //链表尾删
            tail_delete(&LinkNode);
            break;
        case 7:
            //链表的查找
            //思路：找到了返回当前元素节点的指针   找不到返回NULL
            printf("请输入要查找的元素");
            scanf("%d", &val);
            temp = find_item(LinkNode, val);
            if (temp == NULL) {
                printf("没有此元素");
            }
            else {
                printf("找到的元素值为：%d\n", temp->val);
            }
            break;
        case 8:
            //链表的中间删（随机删），至少需要两个元素（要删除的目标元素以及它的前一个元素）

            /*
            printf("请输入要删除的元素");
            scanf("%d", &val);
            middle_delete(LinkNode, val);
            */
            printf("请输入要删除的前一个元素");
            scanf("%d", &val);
            temp = find_item(LinkNode, val);
            if (temp == NULL) {
                printf("没有此元素==》要删除的前一个\n");
            }
            else {
                //删除查找的元素temp的后一个元素
                mid_del(temp);
            }
            break;
        case 9:
            //链表的中间插
            printf("请输入您要在哪个元素后面插入：");
            scanf("%d", &val);
            printf("请输入要中间插的新元素");
            eleT newval = 0;
            scanf("%d", &newval);
            temp = find_item(LinkNode, val);
            if (temp == NULL) {
                printf("无法插入\n");
            }
            else {
                //正常中间插
                mid_insert(temp, newval);
            }
            break;
        case 10:
            //链表销毁
            destory(&LinkNode);
            break;
        case 11:
            return;
        default:
            printf("指令输入有误");
        }
    }
}

//打印菜单
void printf_menu(void) {
    system("cls");//系统函数 用于屏幕清空
    printf("操作指令说明:\n");
    printf("1:链表初始化\n2:打印链表\n");
    printf("3:链表头插\n4:链表尾插\n");
    printf("5:链表头删\n6:链表尾删\n");
    printf("7:链表的查找\n8:链表的中间删\n");
    printf("9:链表的中间插\n10:链表销毁\n");
    printf("11:退出\n");
}

//初始化头结点
LKNode* init_Link(eleT val) {
    //申请节点内存
    LKNode* newnode = (LKNode*)malloc(sizeof(LKNode));
    //判断内存是否申请成功
    /*
    if (!newnode) {
        printf("内存申请失败\n");
        return NULL;
    }
    */
    assert(newnode);//如果为空，报错
    newnode->val = val;
    newnode->next = NULL;
    printf("初始化成功\n");
    return newnode;
}

//遍历
void print_Link(LKNode* LinkNode) {
    assert(LinkNode);//是否初始化
    //正常遍历
    //方法1
/*
    LKNode* temp = LinkNode;
    while (temp->next != NULL) {
        printf("%d ", temp->val);//输出不是尾结点的元素
        temp = temp->next;
    }
    printf("%d ", temp->val);//输出尾结点的元素值
}
*/
//方法2
    LKNode* temp = LinkNode;
    while (1) {
        printf("%d ", temp->val);
        if (temp->next == NULL) {//尾结点
            break;
        }
        temp = temp->next;
    }
    printf("\n");
}


//头插
void head_insert(LKNode **LinkNode, eleT val) {
    assert(*LinkNode);//是否初始化
    //1.创建新节点
    LKNode* newnode = (LKNode*)malloc(sizeof(LKNode));
    assert(newnode);
    //2.给新节点赋值
    newnode->val = val;
    newnode->next = *LinkNode;
    //3.更新头结点
    *LinkNode = newnode;//更新头结点
    printf("头插成功\n");
}

    //补充调试代码常用的函数：
    //exit()     用于终止程序执行，输出一些参数，一般用0表示正常退出，!0异常退出
    //assert()  导入<assert.h>头文件   用于调试代码，条件为真，程序正常执行，条件为假，程序报错    


//尾插
void tail_insert(LKNode* LinkNode, eleT val) {
    assert(LinkNode);//判断是否初始化
    //1.创建新节点
    LKNode* newnode = (LKNode*)malloc(sizeof(LKNode));
    assert(newnode);//内存申请成功
    //2.给新节点成员赋值
    newnode->val = val;
    newnode->next = NULL;

    //3.将新节点放到链表的尾部，首先找到链表的尾结点
    LKNode* temp = LinkNode;
    while (1) {
        if (temp->next == NULL) {
            //4.说明找到尾结点,将新节点插到尾结点后面
            temp->next = newnode;
            break;
        }
        temp = temp->next;
    }
    printf("尾插成功！\n");
}


//头删
void head_delete(LKNode** LinkNode) {
    assert(LinkNode);//判断是否初始化
    LKNode* temp = (*LinkNode)->next;//保存当前头结点的后一个节点
    free(*LinkNode);//释放原来的头结点
    *LinkNode = temp;//更新头结点
    printf("头删成功！\n");
}

//尾删
void tail_delete(LKNode** LinkNode) {
    assert(*LinkNode);//判断是否初始化

    //考虑只有一个结点时
    if ((*LinkNode)->next == NULL) {
        free(*LinkNode);//释放当前节点
        *LinkNode = NULL;
    }
    else {
        //找到链表的倒数第二个元素节点
        LKNode* temp = *LinkNode;
        while (1) {
            if (temp->next->next == NULL) {
                //4.说明找到倒数第二个节点
                break;
            }
            temp = temp->next;
        }
        free(temp->next);//释放尾结点
        temp->next = NULL;//更新尾结点
        printf("尾删成功！\n");
    }
}

//查找
LKNode* find_item(LKNode* LinkNode, eleT val) {
    assert(LinkNode);//判断是否初始化
    LKNode* temp = LinkNode;
    while (temp) {
        if (temp->val == val) {
            //找到了查找的元素
            return temp;
        }
        temp = temp->next;
    }
    return NULL;
}

//中间删1.0
void middle_delete(LKNode* LinkNode, eleT val) {
    assert(LinkNode);//判断是否初始化
    int flag = 0;//表示查找元素的状态
    //查找到删除元素的前一个元素的地址
    LKNode* temp = LinkNode;
    while (temp) {
        if (temp->next->val == val) {
            flag = 1;
            //找到了,删除temp->next
            LKNode* ptr = temp->next;//保存要删除的节点
            temp->next = temp->next->next;
            free(ptr);//释放要删除的节点
            printf("中间删成功！\n");
            break;
        }
        temp=temp->next;
    }
    if(flag==0){
        printf("没有找到要删除的元素\n");
    }
}


//中间删2.0，至少需要两个元素（要删除的目标元素以及它的前一个元素）,才能实现中间的随机删除
void mid_del(LKNode* temp) {
    //temp是要删除元素的前一个元素
    LKNode* ptr = temp->next->next;//保存要删除元素的后一个元素
    free(temp->next);//释放要删除的元素
    temp->next = ptr;
    printf("中间删成功！\n");
}

//中间插
void mid_insert(LKNode* temp, eleT newval) {
    LKNode* newnode =(LKNode*) malloc(sizeof(LKNode));
    assert(newnode);
    //给新节点赋值
    newnode->val = newval;
    //将新节点插入
    newnode->next = temp->next;
    temp->next = newnode;
    printf("中间插入成功！\n");
}

//销毁    遍历后一个一个删除
void destory(LKNode** LinkNode) {
    assert(*LinkNode);//*LinkNode头结点
    while (*LinkNode) {
        LKNode* temp = (*LinkNode)->next;
        free(*LinkNode);
        *LinkNode = temp;
    }
    *LinkNode = NULL;//更新头结点
    printf("销毁成功！\n");
}

标签：LKNode,val,temp,单向,链表,数据结构,LinkNode,节点
From： https://blog.csdn.net/m0_68557555/article/details/145147117

相关文章

  • 数据结构-栈
    1、栈的基本概念1、栈是特殊的线性表：只允许在一端进行插入和删除操作2、栈的逻辑结构就是线性结构，栈的存储结构既可以是顺序存储，也可以是链式存储3、栈顶：允许进行插入和删除的一端（最上面的为栈顶元素)4、栈底：不允许进行插入和删除的一端（最下边的栈底元素)5、空栈：不含任何......
  • 链表实现学生管理系统
    #define_CRT_SECURE_NO_WARNINGS#include<stdio.h>#include<stdlib.h>#include<memory.h>#include<assert.h>//案例需求：使用双向带头循环链表实现学生信息系统的增删改查//定义学生信息结构体类型typedefstructstudent{   intid;//学号   char......
  • 数据结构-二叉树
     树的相关概念：1、节点的度：树中一个节点的孩子个数称为该节点的度，所有节点的度的最大值是树的度2、分支节点：度大于0的节点称为分支节点3、叶子结点：度为0的节点称为叶子结点4、节点的层次（深度）：从上往下数，根节点为1层，依次往下加15、树的高度（深度）：树中节点的最大层次6、树......
  • 《StringBuilder类的数据结构和扩容方式解读》
    StringBuilder类的简单用法、数据结构和扩容方式解读文章目录前言一、pandas是什么？二、使用步骤1.引入库2.读入数据总结前言在之前的文章中和大家讲过String字符串类具有不可变性，今天给大家介绍一个可变字符串类——StringBuilder类。提示：以下是本篇文章正文内......
  • 数据结构2——线性表的链式存储
    前言顺序存储结构的缺点：①插入、删除操作需要移动大量的元素。② 预先分配空间需按最大空间分配，利用不充分。③表容量扩充十分不方便（可能会产生效率问题）。而链式存储结构恰好弥补了顺序存储这些缺陷。1.认识线性表链式存储1.1线性表链式存储的构成①可用一组任意......
  • 【轻松掌握数据结构与算法】动态规划
    引言在本章中，我们将尝试解决那些使用其他技术（例如分治法和贪心法）未能得到最优解的问题。动态规划（DP）是一种简单的技术，但掌握起来可能比较困难。识别和解决DP问题的一个简单方法就是尽可能多地解决各种问题。“编程”一词与编码无关，而是源自文献，意思是填充表格，类似于线性规划。......
  • 单调队列：实用而好写的数据结构
    前言|Preface这几天连续做了好几道单调队列的题，难度从绿到蓝不等，摸索出了一些经验，也总结了一些单调队列的特点和规律。概述|Outline顾名思义，单调队列的重点分为「单调」和「队列」。「单调」指的是元素的「规律」——递增（或递减）。「队列」指的是元素只能从队头和队尾进......
  • 数据结构与算法之递归: LeetCode 39. 组合总和 (Ts版)
    组合总和https://leetcode.cn/problems/combination-sum/description/描述给你一个无重复元素的整数数组candidates和一个目标整数target，找出candidates中可以使数字和为目标数target的所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合candid......
  • 01 序论（数据结构实战）
    计算机的发展与用途：早期的计算机：最初，计算机主要是用来进行数学运算，像是加减乘除这种“数值计算”。它们主要用在科学研究、工程计算等需要大量数字计算的领域。现在的计算机：现代的计算机用途广泛，已经不仅仅局限于处理数字。它们还处理许多其他类型的数据，比如文字、表格、图片......
  • 9.List(带头双向循环链表)
    1.迭代器介绍1.单向迭代器(InputIterator)：++<forward_list>,<unordered_map>,<unordered_set>2.双向迭代器(BidirectionalIterator)：++/--<list>,<map>,<set>3.随机迭代器(RandomAccessIterator)：++/--/+/-<vector>,<deque>,<str......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99