C++ 单链表的基本操作(详解)
链表一直是面试的高频题,今天先总结一下单链表的使用,下节再总结双向链表的。本文主要有单链表的创建、插入、删除节点等。
1、概念
单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。
链表中的数据是以结点来表示的,每个结点的构成:元素 + 指针,元素就是存储数据的存储单元,指针就是连接每个结点的地址数据。如下图:
2、链表的基本操作
SingleList.cpp:
#include "stdafx.h" #include "SingleList.h" #include <cstdlib> #include <iostream> #include <string.h> #include <conio.h> #include <stdio.h> /*c++实现简单的单链表操作*/ using namespace std; SingleList::SingleList() { int num; char name[128]; // 创建链表 node *stuList = CreatNode(); PrintList(stuList); // 插入节点 printf("\n请输入要插入的学生学号和姓名,输入0 0表示结束."); scanf_s("%d%s", &num, name, 100); stuList = InsertNode(stuList, num, name); PrintList(stuList); // 删除节点 printf("\n请输入要删除的学生学号:"); scanf_s("%d", &num, 100); stuList = DeleteNode(stuList, num); PrintList(stuList); // 逆序 printf("\n逆序后的链表为:\n"); stuList = ReverseList(stuList); PrintList(stuList); system("PAUSE"); } SingleList::~SingleList() { } //建立单链表 node *SingleList::CreatNode() { node *head, *p, *s; int num = 0; char name[128]; int cycle = 1; head = (node *)malloc(sizeof(node)); // 为头结点分配内存空间 head->next = nullptr; p = head; // p指向头节点 while (cycle) { printf("\n请输入学生的学号和姓名:"); scanf_s("%d%s", &num, name, 100); if (num != 0) { s = (node *)malloc(sizeof(node)); s->num = num; memcpy(s->name, name, 128); printf("%d%s", s->num, s->name); p->next = s; // 指向新插入的节点 p = s; // p指向当前节点 } else { cycle = 0; } } head = head->next; p->next = NULL; printf("头节点学生信息为: %d%s\n", head->num, head->name); return head; } //单链表插入 node *SingleList::InsertNode(node *head, int num, char* name) { node *s, *p1, *p2 = NULL; p1 = head; s = (node *)malloc(sizeof(node)); s->num = num; strcpy_s(s->name, name); while ((s->num > p1->num) && p1->next != NULL) { p2 = p1; p1 = p1->next; } if (s->num <= p1->num) { if (head == p1) { // 插入首节点 s->next = p1; head = s; } else { // 插入中间节点 p2->next = s; s->next = p1; } } else { // 插入尾节点 p1->next = s; s->next = NULL; } return head; } // 计算单链表长度 int SingleList::GetLength(node *head) { int length = 0; node *p; p = head; while (p != NULL) { p = p->next; length++; } return length; } //单链表删除某个元素 node *SingleList::DeleteNode(node *head, int num) { node *p1, *p2 = nullptr; p1 = head; while (num != p1->num && p1->next != NULL) { p2 = p1; p1 = p1->next; } if (num == p1->num) { if (p1 == head) { head = p1->next; } else { p2->next = p1->next; } free(p1); } else { printf("找不到学号为%d 的学生!\n", num); } return head; } //单链表逆序 node *SingleList::ReverseList(node *head) { // A->B->C->D node *old_head; // 原来链表的头 node *new_head; // 新链表的头 node *cur_head; // 获得原来链表的头 if (head == NULL || head->next == NULL) return head; new_head = head; // A cur_head = head->next; // B while (cur_head) { old_head = cur_head->next; // 将原来链表的头取出,并将第二个节点作为头节点 cur_head->next = new_head; // 将取出的头设为新链表的头 new_head = cur_head; // 新链表的头就是目前新链表的头 cur_head = old_head; // 接着处理 } head->next = NULL; head = new_head; return head; } //打印单链表 void SingleList::PrintList(node *head) { node *p; int n; n = GetLength(head); printf("\n打印出 %d 个学生的信息:\n", n); p = head; while (p != NULL) { printf("学号: %d ,姓名: %s\n", p->num, p->name); p = p->next; } }
SingleList.h:
#pragma once typedef struct student { int num; // 学号 char name[128]; // 姓名 struct student *next; }node; class SingleList { public: SingleList(); ~SingleList(); //建立单链表 node *CreatNode(); //单链表插入 node *InsertNode(node *head, int num, char* name); // 计算单链表长度 int GetLength(node *head); //单链表删除某个元素 node *DeleteNode(node *head, int num); //单链表逆序 node *ReverseList(node *head); //打印单链表 void PrintList(node *head); };
关于逆序逻辑,研究了一下:
1、主要思路:
假设有单链表A->B->C->D,首先取出首节点A作为新逆序出来的链表
这样,原链表就为:B->C->D,逆序后的新链表为:A
2. 按照上述方法,依次取出B、C、D放入新链表
2、图形表示:
原始的单链表:
<!--[endif]-->
初始状态时,单链表如上图所示,head指向头节点A。
1. 取出原始链表的第一个节点A,然后将该节点作为新链表的头节点
原始链表:
<!--[endif]-->
新链表:
<!--[if !vml]--> <!--[endif]-->
<!--[if !supportLists]--> 2.然后同上处理:
原始链表:
<!--[if !vml]--> <!--[endif]-->
新链表:
<!--[if !vml]--> <!--[endif]-->
以上这篇C++ 单链表的基本操作(详解)就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持猪先飞。
相关文章
- 以前我们开发大型项目时都会用到svn来同步,因为开发产品的人过多,所以我们会利用软件来管理,今天发有一居然可以利用php来管理svn哦,好了看看吧。 代码如下 ...2016-11-25
- vector是表示可以改变大小的数组的序列容器,本文主要介绍了C++STL标准库std::vector的使用详解,文中通过示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2022-03-06
- 这篇文章主要介绍了C++中取余运算的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 这篇文章主要介绍了C++ string常用截取字符串方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本文通过例子,讲述了C++调用C#的DLL程序的方法,作出了以下总结,下面就让我们一起来学习吧。...2020-06-25
- 本篇文章主要介绍了C++中四种加密算法之AES源代码,小编觉得挺不错的,现在分享给大家,也给大家做个参考。...2020-04-25
- 整数拆分,指把一个整数分解成若干个整数的和。本文重点给大家介绍C++ 整数拆分方法详解,非常不错,感兴趣的朋友一起学习吧...2020-04-25
- 这篇文章介绍了在C#中对config文件的操作,有需要的朋友可以参考一下...2020-06-25
- 这篇文章主要介绍了C++中Sort函数详细解析,sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变...2022-08-18
- 这篇文章主要介绍了python自动化办公操作PPT的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-05
- 这篇文章主要介绍了C++万能库头文件在vs中的安装步骤(图文),文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 这篇文章主要介绍了C++ bitset用法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本篇文章小编并不是为大家讲解string类型的用法,而是讲解我个人比较好奇的问题,就是string 类型占几个字节...2020-04-25
nodejs文件操作模块FS(File System)常用函数简明总结
件系统操作相关的函数挺多的。首先可以分为两大类。一类是异步+回调的。 一类是同步的。在这里只对异步的进行整理,同步的只需要在函数名称后面加上Sync即可1. 首先是一类最常规的读写函数,函数名称和形式,应该是起源于C...2014-06-07- 这篇文章主要为大家详细介绍了C++ Eigen库计算矩阵特征值及特征向量,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-04-25
- 这篇文章主要介绍了C#模拟window操作鼠标的方法,可实现模拟鼠标移动到固定位置后点击右键的功能,涉及鼠标常用事件的操作技巧,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了微信小程序手势操作之单触摸点与多触摸点的相关资料,需要的朋友可以参考下...2017-03-13
- 这篇文章主要介绍了C++ pair的用法实例详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了VSCode C++多文件编译的简单使用方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-03-29
- 虽然C++11引入了智能指针的,但是开发人员在与内存的斗争问题上并没有解放,如果我门实用不当仍然有内存泄漏问题,其中智能指针的循环引用缺陷是最大的问题。下面通过实例代码给大家介绍c++中的循环引用,一起看看吧...2020-04-25