带头结点的线性链表的基本操作

2024-09-08 05:08
文章标签 链表 基本操作 线性 结点 带头

本文主要是介绍带头结点的线性链表的基本操作，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

持续了好久，终于有了这篇博客，链表的操作需要借助图像模型进行反复学习，这里尽可能的整理并记录下自己的思考，以备后面复习，和大家分享。需要说明的是，我们从实际应用角度出发重新定义了线性表。

一. 定义

从上一篇文章可以看到，由于链表在空间的合理利用上和插入、删除时不需要移动等优点，因此在很多场合下，它是线性表的首选存储结构。然而，它也存在某些实现的缺点，如求线性表的长度时不如顺序存储结构的缺点。因此，从实际应用角度出发重新定义了线性表。
一个带头结点的线性链表类型定义如下：

//结点类型
typedef struct Node
{ElemType   data;struct Node *next;
}Node,*PNode;//链表类型
typedef struct List
{PNode head; //指向线性链表的头结点PNode tail; //指向线性链表的尾结点size_t size; //线性表中数据元素的个数
}List;

二、函数实现的难点

我们基于一个改良的链表类型，进行常见的基本操作，这里将就每个函数实现的重难点找出来，使其核心精髓展现在我们眼前：

InitList(List *list)

该函数实现了将我们定义的链表进行初始化，使其头指针、尾指针都指向头结点（空表），链表的大小size为0.
这里写图片描述

void push_back(List *list,ElemType x)

尾插入，首先构建一个节点，然后将其插入链表尾部。此时体现出来该种数据结构的优势，我们无需从链表首部直接操作，直接找到了链表尾部对其操作。

void push_front(List *list,ElemType x)

头插，核心是用于在头结点和第一个结点之间插入新的子节点。当然，如果插入前为空表，需修改链表的尾结点指向第一个结点。(因为是对头部操作，我们需要留意尾结点)

void pop_back(List *list)

尾部删除，首先判断链表是否非空，然后不停的删除尾结点。当然，需要找到尾结点的前驱，我们需要顺序遍历。

void pop_front(List *list)

头部删除，首先判断链表是否非空，然后不停的删除头结点第一个结点。需要注意，如果删除到只剩头结点时，需要将尾指针指向头结点。(因为是对头部操作，我们需要留意尾结点)

void insert_val(List *list, ElemType x)

插入值，也即插入一个结点。前提是有序，按值插入(需考虑插入到尾结点之后情况：此时更新尾结点指针)。

Node* find (List *list, ElemType key)
void delete_val(List *list,ElemType key)

删除值，调用了find方法，我们首先找到指向当前要删除值的结点，然后将下一结点的值赋值给当前结点，使当前结点指向下一结点的next，删除下一结点，从而变相的删除了当前结点。
当然，我们也可以通过顺序遍历，找到当前要删除值结点的前驱，然后删除该节点。

void sort(List *list)

本篇文章的重点：排序。之前的实现中，我们都是通过某种排序方法，交换结点中的data，从而实现。本篇文章我们通过交换结点的方法来实现。
这里写图片描述
首先，我们把整个单链表断开，已排序部分仅仅包括头结点和第一个结点（尾指针指向第一个结点），待排序部分从第二个结点开始余下的部分。
我们每次从待排序部分取出一个结点s，将其值和已排序部分顺序比较，从而找到要插入位置的前驱p,插入前要更新q为待排序链表的第一个结点。然后尾插即可。

void reverse(List *list)

本篇文章的重点：反转。同上，我们还是把整个单链表断开分为两部分：已排序部分仅仅包括头结点和第一个结点（尾指针指向第一个结点），待排序部分从第二个结点开始余下的部分。
我们每次从待排序部分取出一个结点给p,然后在头结点和第一个结点之间头插实现。

三、代码

sList.h

#ifndef SLIST_H__
#define SLIST_H__#include <stdio.h>
#include <malloc.h>
#include <assert.h>typedef int ElemType;//结点类型
typedef struct Node
{ElemType   data;struct Node *next;
}Node,*PNode;//链表类型
typedef struct List
{PNode head;PNode tail;size_t size;
}List;void InitList(List *list);void push_back(List *list,ElemType x); //尾插
void push_front(List *list,ElemType x); //头插void pop_back(List *list); //尾删
void pop_front(List *list); //头删void insert_val(List *list, ElemType x); //按值插入
Node* find (List *list, ElemType key);//查找某值
int length(List *list); //长度
void delete_val(List *list,ElemType key); //删除值
void sort(List *list);//升序
void reverse(List *list);//反转
void clear(List *list);//清除
void destroy(List *list);//销毁
void show_list(List *list);
#endif // SLIST_H__

sList.cpp

#include "sList.h"void InitList(List *list)
{list->head = list->tail = (Node *)malloc(sizeof(Node));assert(list->head != NULL);list->head->next = NULL; //头结点下一个为空list->size = 0;
}//1.更新新尾结点(一直对尾结点操作，故不需考虑)
void push_back(List *list,ElemType x)
{Node *s = (Node *)malloc(sizeof(Node));assert (s != NULL);s->data = x;s->next = list->tail->next;list->tail->next = s; //原尾结点指向slist->tail = s;//更新为新尾结点//由于一直对尾指针考虑，因此这里不需要考虑size=0list->size++;
}//1.在头结点之后插入作为第一个结点(需要考虑尾结点)
void push_front(List *list,ElemType x)
{Node *s = (Node *)malloc(sizeof(Node));assert (s != NULL);s->data = x;s->next = list->head->next; //s结点指向第一个结点list->head->next = s; //头结点指向第一个结点//插入时，如果是第一个结点(size=0)则需修改list->tail指针指向sif(list->size == 0){list->tail = s;}list->size++;
}
//1.判断非空 2.使倒数第二个结点为新尾结点(一直对尾结点操作，故不需考虑)
void pop_back(List *list)
{if(list->size == 0){printf("error: seqList is empty\n");return;}Node *p = list->head;while (p->next != list->tail) { p = p->next; }free(list->tail);//删除旧尾结点list->tail = p;//新尾结点list->tail->next = NULL;//新尾结点next为NULLlist->size--;
}//1.判断非空 2.删除头结点之后第一个结点 3.需要考虑尾结点
void pop_front(List *list)
{if(list->size == 0){printf("error: seqList is empty\n");return;}Node *q = list->head->next;list->head->next = q->next;free(q);//删除时，如果只剩第一个结点(size=1)则需修改list->tail指针指向头结点if(list->size == 1){list->tail = list->head;}list->size--;
}
//前提：有序。按值插入(考虑插入到尾结点之后情况)
void insert_val(List *list, ElemType x)
{Node *s = (Node *)malloc(sizeof(Node));assert(s != NULL);s->data = x;s->next = NULL;Node *p = list->head;while(p->next != NULL && p->next->data <x)p=p->next;//若插入到尾结点,则更新尾结点if(p->next == NULL){list->tail = s;}//找到该插入位置的前一位s->next = p->next;p->next = s; //指向新创建的结点list->size++;}Node* find (List *list, ElemType key)
{Node *p = list->head->next;//利用短路条件，注意顺序while( p!=NULL && p->data != key)  { p = p->next; }return p;
}int length(List *list)
{return list->size;
}void delete_val(List *list,ElemType key)
{if(list->size == 0)return;Node *p = find(list,key);if(p == NULL){printf("delete val not exist\n");return ;}if(p == list->tail){pop_back(list);}else{//将要删除数据的next拿过来替换值,取出next的有用信息后free掉qNode *q = p->next;p->data = q->data;p->next = q->next;free(q);list->size--;}}//把整个单链表断开，把剩下链表的结点根据值升序尾插
void sort(List *list)
{if(list->size==0 || list->size == 1)return ;Node *s = list->head->next; //指向第一个结点Node *q = s->next;//指向第二个结点list->tail = s;list->tail->next = NULL; //断开链表//按值插入while(q!=NULL){s = q;q = q->next;//p指针为已排序指针,s为待排序指针Node *p = list->head;while(p->next != NULL && p->next->data < s->data)p=p->next;//若插入到尾结点,则更新尾结点if(p->next == NULL){list->tail = s;}//尾插s->next = p->next;p->next = s; //指向新创建的结点}
}
//把整个单链表断开，把剩下链表的结点按值头插
void reverse(List *list)
{if(list->size==0 || list->size == 1)return ;Node *p = list->head; //指向第一个结点Node *q = p->next;//指向第二个结点list->tail = p;//指向第一个结点list->tail->next = NULL; //断开链表while(q != NULL){p = q;q = q->next;p->next = list->head->next ;list->head->next  = p; //在头结点和第一个结点直接插入}
}void clear(List *list)
{if(list->size ==0)return ;Node *p = list->head->next;while(p!=NULL){list->head->next = p->next;free(p);p = list->head->next;}list->tail = list->head;list->size = 0;
}void destroy(List *list)
{clear(list);free(list->head);list->tail = list->head =NULL;
}
void show_list(List *list)
{Node *p = list->head->next;while(p){printf("%d--->",p->data);p = p->next;}printf("Nul\n");
}

main.cpp

#include "sList.h"/*
break语句通常用在循环语句和开关语句中。
当break用于开关语句switch中时，可使程序跳出switch而执行switch以后的语句；如果没有break语句，则会从满足条件的地方（即与switch（表达式）括号中表达式匹配的case）开始执行，直到switch结构结束。当break语句用于do-while、for、while循环语句中时，可使程序终止循环。而执行循环后面的语句，通常break语句总是与if语句联在一起。即满足条件时便跳出循环。
*/int main()
{List mylist;InitList(&mylist);int select;ElemType num;Node *p;while(select){printf("* [1] push_back                [2] push_front  *\n");printf("* [3] show_list                [4] pop_back     *\n");printf("* [5] pop_front                [6] insert_val   *\n");printf("* [7] find                     [8] length       *\n");printf("* [9] delete_val               [10] sort        *\n");printf("* [11] reverse                 [12] clear       *\n");printf("* [13] destroy                 [0] quit_system  *\n");printf("please choose:>");scanf("%d",&select);if(select == 0)  break;switch(select){case 1:printf("push_back: input numbers(-1 erminate):");while(scanf("%d",&num),num != -1){push_back(&mylist,num);  //尾插}break;case 2:printf("push_front: input numbers(-1 erminate):");while(scanf("%d",&num),num != -1){push_front(&mylist,num);  //头插}break;case 3:show_list(&mylist);break;case 4:pop_back(&mylist); //尾删break;case 5:pop_front(&mylist); //头删break;case 6:printf("input inset value:>");scanf("%d",&num);insert_val(&mylist,num); //升序插值break;case 7:printf("input find value:>");scanf("%d",&num);p = find(&mylist,num); //查找某值if(p == NULL)printf("value %d not exist\n",num);break;case 8:printf("length:%d\n",length(&mylist));  //长度case 9:printf("input delete value:>");scanf("%d",&num);delete_val(&mylist,num); //删除值break;case 10:sort(&mylist); //升序break;case 11:reverse(&mylist); //反转break;case 12:clear(&mylist); //清除break;case 13:destroy(&mylist); //销毁break;default:printf("error,choose again\n");break;}}printf("Hello world!");return 0;
}

这篇关于带头结点的线性链表的基本操作的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1147196。

相关文章

csu1329(双向链表)

csu1329(双向链表)

题意：给n个盒子，编号为1到n，四个操作：1、将x盒子移到y的左边；2、将x盒子移到y的右边；3、交换x和y盒子的位置；4、将所有的盒子反过来放。 思路分析：用双向链表解决。每个操作的时间复杂度为O(1)，用数组来模拟链表，下面的代码是参考刘老师的标程写的。 代码如下： #include<iostream>#include<algorithm>#include<stdio.h>#
阅读更多...
深入手撕链表

深入手撕链表

链表 分类概念单链表增尾插头插插入 删尾删头删删除 查完整实现带头不带头 双向链表初始化增尾插头插插入 删查完整代码 数组 分类 #mermaid-svg-qKD178fTiiaYeKjl {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-
阅读更多...
线性因子模型 - 独立分量分析（ICA）篇

线性因子模型 - 独立分量分析（ICA）篇

序言 线性因子模型是数据分析与机器学习中的一类重要模型，它们通过引入潜变量（ latent variables \text{latent variables} latent variables）来更好地表征数据。其中，独立分量分析（ ICA \text{ICA} ICA）作为线性因子模型的一种，以其独特的视角和广泛的应用领域而备受关注。 ICA \text{ICA} ICA旨在将观察到的复杂信号
阅读更多...
建立升序链表

建立升序链表

题目1181：遍历链表 时间限制：1 秒 内存限制：32 兆 特殊判题：否 提交：2744 解决：1186 题目描述： 建立一个升序链表并遍历输出。 输入： 输入的每个案例中第一行包括1个整数：n(1<=n<=1000)，接下来的一行包括n个整数。 输出： 可能有多组测试数据，对于每组数据， 将n个整数建立升序链表，之后遍历链表并输出。 样例输
阅读更多...
【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟） 题目描述 给定一个链表，链表中的每个节点代表一个整数。链表中的整数由 0 分隔开，表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点，新节点的值为原区间内所有节点值的和。合并后，需要移除所有的 0，并返回修改后的链表头节点。 思路分析 初始化：创建一个虚拟头节点
阅读更多...
学习记录：js算法（二十八）：删除排序链表中的重复元素、删除排序链表中的重复元素II

学习记录：js算法（二十八）：删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一：循环解法二：递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1：（图一）输入：head = [1,1,2]输出：[1,2]示例 2：（图
阅读更多...
✨机器学习笔记（二）—— 线性回归、代价函数、梯度下降

✨机器学习笔记（二）—— 线性回归、代价函数、梯度下降

1️⃣线性回归（linear regression） f w , b ( x ) = w x + b f_{w,b}(x) = wx + b fw,b​(x)=wx+b 🎈A linear regression model predicting house prices： 如图是机器学习通过监督学习运用线性回归模型来预测房价的例子，当房屋大小为1250 f e e t 2 feet^
阅读更多...
【高等代数笔记】线性空间（一到四）

【高等代数笔记】线性空间（一到四）

3. 线性空间 令 K n : = { ( a 1 , a 2 , . . . , a n ) ∣ a i ∈ K , i = 1 , 2 , . . . , n } \textbf{K}^{n}:=\{(a_{1},a_{2},...,a_{n})|a_{i}\in\textbf{K},i=1,2,...,n\} Kn:={(a1​,a2​,...,an​)∣ai​∈K,i=1,2,...,n
阅读更多...
【数据结构与算法 | 灵神题单 | 删除链表篇】力扣3217, 82， 237

【数据结构与算法 | 灵神题单 | 删除链表篇】力扣3217, 82， 237

总结，删除链表节点问题使用到列表，哈希表，递归比较容易超时，我觉得使用计数排序比较稳，处理起来也不是很难。 1. 力扣3217：从链表中移除在数组中的节点 1.1 题目： 给你一个整数数组 nums 和一个链表的头节点 head。从链表中移除所有存在于 nums 中的节点后，返回修改后的链表的头节点。 示例 1： 输入： nums = [1,2,3], head = [1,2,3,
阅读更多...
c++ 链表详细介绍

c++ 链表详细介绍

链表是数据结构的一种，由节点组成，每个节点包含数据和指向下一个节点的指针。链表在C++中的实现可以是单链表、双链表或循环链表。以下是链表的详细介绍： 1. 单链表 结构： 节点（Node）：每个节点包含数据和一个指针（next），指向链表中的下一个节点。 示例结构： struct Node {int data;Node* next;Node(int d) : data(d), next(
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2