请教一个C++链表(linked list)的创建和遍历的基础问题

我从前对C++链表不太熟悉,现在看书上有一个例子讲链表的创建和遍历:

struct ListNode
    {
    int content;
    ListNode *next;
    }; // 请问:这里写或者不写“ListNode *head=NULL;”有什么区别?

void List_Create(ListNode *&LN, int array[], int n)
    {
    ListNode* p;
    int i;
    LN = (ListNode*)malloc(sizeof(ListNode)); // 请问:这里的LN为什么要用malloc分配内存呢?直接ListNode* LN为什么不行呢?
    LN->next = NULL; // 把LN作为结尾指向NULL.
    for(i=n-1; i>=0; i--)
        {
        p = (ListNode*)malloc(sizeof(ListNode)); // 请问:这里的p为什么要用malloc分配内存呢?直接ListNode* p为什么不行呢?
        p->content = array[i];
        p->next = LN->next; // 直接写p->next = LN为什么不对呢?
        LN->next = p; // 请问:为什么前面是把LN-next赋给p-next、这里却把p整个赋给了LN呢?
        }
    }

void List_Display(ListNode *&LN)
    {
    cout << "\nThe displayed list is: " << endl;
    while(LN -> next != NULL)
        {
        cout << LN->next->content << " ";
        LN = LN->next;
        }
    cout << endl;
    }

请教一下大家4个问题:

1 最开始的struct那一段,结尾处写或者不写 ListNode *head=NULL有什么区别?

2 Create函数中,LN=(ListNode*)malloc(sizeof(ListNode)) 以及 p=(ListNode*)malloc(sizeof(ListNode)); 请问:这里的LN为什么要用malloc分配内存呢?直接ListNode* LN和ListNode* p为什么不行呢?最开始struct那里 ListNode*head定义的时候也没malloc分配内存啊?

3 Create函数中,p->next = LN->next; LN->next = p;这应该是实现p的插入。但是为什么前面是把LN-next赋给p-next、后面却把p整个赋给了LN-next呢? 如果写 p->next = LN; LN->next = p; 这样看起来更一致,为什么不对呢?

4 Display函数虽然遍历了整个链表,但是也事实上移动到了链表的末端。有没有什么办法能既遍历、又不移动到末端呢?

谢谢了先!

2个回答

链表无非就是用指针把一个个节点连接起来,可以自己画一个简易图,针对你的问题:
(1)ListNode head=NULL,这里是定义头节点指针,你后面所有的操作都要以头节点为依据,初始化头节点为空,方便做安全校验。
(2)Create函数中,LN=(ListNode
)malloc(sizeof(ListNode)) 以及 p=(ListNode*)malloc(sizeof(ListNode)); 这里用malloc分配内存,是在堆上的,
只要你不去free就不会释放,一直存在,然后这里的LN和P保存了内存的地址,后面的操作就可以根据地址来访问内存;
直接ListNode* LN和ListNode* p这只是两个指针变量,并不是一个完整的节点,只是ListNode* 而不是ListNode;
最开始struct那里 ListNode*head定义的时候没malloc分配内存是因为这里只是定义的一个头节点指针,这个链表的一个标志,并不是一个节点,所以不用。
(3)插入,p->next = LN->next;是将P节点的下一个指针指向插入位置的下一个节点,LN->next = p;是将插入位置节点的下一个指向P节点,这样实现一个节点的插入;
如果写 p->next = LN; LN->next = p; 就是让p节点的下一个指针指向LN节点,LN节点的下一个指针指向P节点,这就相互指向,形成了一个小环,这就不是插入了。
(4)不让头节点移动到末端就定义一个临时变量指针来遍历就可以了。
链表没什么的,可以自己多写写,单向链表,双向链表,增删改查

Whatsmyname
Whatsmyname 谢谢!
大约 3 年之前 回复

学习链表最好的方式是画图,能画图就一目了然了。
1)ListNode head=NULL;写不写都可以;程序开始可定会给头指针赋值
2)c++里面也可以使用new关键字。上面的写法是c语言的。ListNode
LN和ListNode* p一定要手动创建。
3)要看你实现尾插入还是头插入
4)可以定义一个ListNode *p=LN;然后使用p来做循环即可

Whatsmyname
Whatsmyname 谢谢!
大约 3 年之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
C++实现单链表(Singly-Linked List)追加、遍历、删除
#include using namespace std; struct Node { int data; struct Node* next; }; class List { Node* head; public: List() { head = NULL;} void Print(); int GetSize(); void Append(int addData); voi
C语言实现单向(循环)链表的创建和遍历
本代码在QT控制台环境下测试通过,如果在其他IDE下,注意修改包含的打印头文件即可。 include include include /* *2018-08-24 13:23:03 * 单向链表测试 * 包括循环链表的实现 */ using namespace std; typedef struct Node{ struct Node *next; ...
C语言链表的创建和遍历
链表是一种常见的重要的数据结构。它是动态地进行存储分配的一种结构。它可以根据需要开辟内存单元。链表有一个“头指针”变量,以head表示,它存放一个地址。该地址指向一个元素。链表中每一个元素称为“结点”,每个结点都应包括两个部分:一为用户需要用的实际数据,二为下一个结点的地址。因此,head指向第一个元素:第一个元素又指向第二个元素;……,直到最后一个元素,该元素不再指向其它元素,它称为“表尾”,它
链表《1》链表的创建和遍历
链表是一种动态数据结构,它的特点是用一组任意的存储单元(可以是连续的,也可以是不连续的)存放数据元素,一个简单的链表如下图所示 尾结点 链表中每一个元素称为结点,每一个结点都是由数据域和指针域组成的,每个结点的指针域指向下一个结点 非循环单链表的实现: 要实现非循环单链表首先应定义一个结点结构 typedef struct Node//结点结构 { int data;/
链表(LinkedList) C 语言实现
链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。如图: 下面是代码实现: #include #include struct student { int score; struct student *next; }; typedef struct student NODE; //typedef为C语言的关
Linked List 链表详解
本文是stanford cs library中两篇关于linked list的文章合体版 linked list basics linked list problems 我觉得这两篇讲linked list的文章写的非常非常好,所以在博客里自己写一下,也算是温习巩固数据结构的知识了 本文代码下载:http://download.csdn.net/detail/stevemarbo/
c语言的创建和遍历
链表的创建和遍历。这是一个最基本的操作,元素类型定义为int 本源程序包含了链表的创建和遍历操作
单链表的各种操作——创建及遍历
链表动态地进行存储分配,可以适应数据动态地增减的情况,且可以方便地插入、删除数据项。
C语言实现单链表创建和遍历
创建单链表有多种方式,我这里介绍从尾部添加新节点的创建方式。 创建的过程: 1.定义节点的数据结构 c语言中链表节点是用结构体来实现,创建之前要明白数据域需要什么类型的数据。例如: //定义链表中的节点 typedef struct node{ int data; //链表中的数据 struct node * p_next;//指向下一节点的指针
java实现单向链表--创建、遍历
自己练习,简陋的Java实现的单向链表
链表创建和链表遍历操作
实现的方法PNODE create(void); void travers(PNODE); bool empty(PNODE); int length(PNODE); void sort(PNODE);全部代码#include <stdio.h> #include <malloc.h> #include <stdlib.h> /* * 单链表 */ typedef struct Node{
单链表的建立和遍历(Java)
读入n值及n个整数,建立单链表并遍历输出。输入格式:读入n及n个整数输出格式:输出n个整数,以空格分隔(最后一个数的后面没有空格)。输入样例:在这里给出一组输入。例如:2 10 5 输出样例:在这里给出相应的输出。例如:10 5程序代码:import java.util.Scanner;class Node{    Node next;    int data;    public Node(){...
循环链表的创建、遍历
循环链表 在单链表中遍历链表时,判断链表终端结点的next指针为空(node-&amp;gt;next=NULL),则表示当前链表遍历完成。 循环链表中,将单链表中的终端结点的指针端由空指针改为指向头结点,就使整个单链表形成一个环,使得链表的头尾相接,这种链表称之为单循环链表,简称为循环链表++。 循环链表和单链表的主要差异就在于循环的判断条件上,单链表判断循环结束为:node-&amp;gt;next==...
python数据结构之链表(linked list)
目录 基础 知识 1.1 链表的基本结构 1.2 节点类和链表节点的定义 1.3 顺序打印和逆序打印 链表的基本操作 2.1 计算链表长度 2.2 从前,后插入数据 2.3 查找与删除 参考 1.基础 知识 1.1 链表的基本结构 链表是通过一个个节点组成的,每个节点都包含了称为cargo的基本单元,它也是一种递归的数据结构。它能保持数据之间的逻辑顺序,但存储空间
创建和遍历链表
简单实用的创建和遍历链表代码
Python 数据结构与算法——列表(链表,linked list)
Python 中的 list 并不是我们传统(计算机科学)意义上的列表,这也是其 append 操作会比 insert 操作效率高的原因。传统列表——通常也叫作链表(linked list)——通常是由一系列节点(node)来实现的,其每一个节点(尾节点除外)都持有一个指向下一个节点的引用。 其简单实现: class Node: def __init__(self, value, ...
黑马程序员————LinkedList和c语言中的链表
最近学习java常常和大一学习的c语言互相印证,待看到
邻接表无向图的创建和遍历(dfs)
网上找的一个图,对这个图进行dfs /************************************************************************* > File Name: adjlist.cpp > Author:gens_ukiy > Mail: > Created Time: 2016年11月29日 星期二 07时22
创建单链表并赋值,要求遍历能输出1~9
用表头创建单链表,用头插法创建链表,遍历的结果是9 8 7 6 5 4 3 2 1       具体的源程序如下:#include #include #define OK 0 #define ERROR -1 #define MALLOC_ERROR -2 typedef int ElementType; typedef struct node {
C实现 LeetCode->Reverse Linked List (双指针大法)(单链表反转)
Reverse a singly linked list. /**  *  Reverse a singly linked list    反转单链表,请牢记 Reverse()函数  */ // // ReverseLinkedList.c // Algorithms // // Created by TTc on 15/6/22. // Copyr
[笔记]python数据结构之线性表:linkedlist链表,stack栈,queue队列
python数据结构之线性表 python内置了很多高级数据结构,list,dict,tuple,string,set等,在使用的时候十分舒心。但是,如果从一个初学者的角度利用python学习数据结构时,这些高级的数据结构可能给我们以迷惑。 比如,使用list实现queue的时候,入队操作append()时间复杂度可以认为是O(1),但是,出队操作pop(0)的时间复杂度就是O(n)。
创建一个有序的链表
创建有序链表的基本思路就是在插入一个新节点之前,
leetcode 328 Odd Even Linked List(调整链表使得奇数位置的元素位于偶数位置元素之前)
Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes. You should try to do it
链表的QuickSort快速排序法
使用QuickSort快速排序算法,排序一个链表。 下面是quickSort,因为quickSort算法的最坏情况是O(n*n), 所以如果做LeetCode上的Sort List这道题目,会遇上最坏情况超时的,不过这是个很好的算法,故此贴出来。 也看了有些博客或什么网站也写有quickSort排序链表的文章,注意看清楚了,很多并不是真正的链表排序,而是排序了链表的值,那样并不是链表操作,不能算链表的quicksort。 有几个地方需要注意的: 1 分成两个链表的时候,注意把结尾=NULL,重新合并中间
C++数据结构 之 链表_Linked List
C++数据结构 之 链表_Linked List源代码只包含头文件注:需要C++11的支持.
链表的创建和输出链表的创建和输出
链表的创建和输出链表的创建和输出链表的创建和输出链表的创建和输出链表的创建和输出链表的创建和输出链表的创建和输出链表的创建和输出
java集合系列——List集合之LinkedList介绍(三)
LinkedList是基于链表实现的,从源码可以看出是一个双向链表。除了当做链表使用外,它也可以被当作堆栈、队列或双端队列进行操作。不是线程安全的,继承AbstractSequentialList实现List、Deque、Cloneable、Serializable。
[python3教程]第三章.3.1.3链表(list)
#其实把list叫做链表我也不知道合不合适,我在学习C语言的时候自己做过链表,一般的来说没有索引功能。但是显然python的链表格外强大~         python有许多种数据类型,list可以说是其中的佼佼者。定义list只需要使用[]就可以,一般情况一个链表种我们只存放一种数据类型,但他支持存放多种数据类型。 链表的索引和字符串几乎是一样的: 连接两个链表的方法和字符串也
C语言实现单链表的初始化、创建、遍历等操作
编译环境:VC++6.0 #include#includetypedef struct LNode{int data;struct LNode *next;}LNode,*LinkList;LinkList Init_LNode() //链表初始化{LNode *L;L = (LinkList)malloc(sizeof(LNode));if(L == NULL){printf("初始化失败!\
数据结构:链表(linked-list)
链表分为单向链表(Singly linked lis)、双向链表(Doubly linked list)、循环链表(Circular Linked list)。
Delete Node in a Linked List(删除链表中的节点)
Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.(实现删除一个除尾节点外的链表节点的函数,假定只能访问被删节点)Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are give
创建一个链表实例
#include #include /* 提供malloc()原型 */ #include //提供strcpy原型 #define TSIZE 45 struct film { char title[TSIZE]; int rating; struct film * next; //指向链表
C语言中树的建立和遍历
树的遍历分为三种:前序遍历(根左右),中序遍历(左根右),后序遍历(左右根)。 PS:根左右,就是先遍历根节点,然后是左子树,最后是右子树。如下图: 前序遍历:ABDECF。 中序遍历:DBEACF。 后序遍历:DEBFCA。 PPS:有一种更便捷的方法来写出三种遍历的结果:从根节点开始,从左面画线,将树沿着边界圈起来。按照线在节点的不同位置依次写出数据。其中:前序遍历为线在节点
C#中链表的用使用LinkedList
using System;using System.Collections.Generic;using System.Linq;using System.Text;namespace 集合{    class 链表    {        public static void Main()        {             //Linke
反转单向链表(reverse a singly linked list)(单个反转) [# 7]
问题: 给一个单向链表,把它从头到尾反转过来。比如: a -> b -> c ->d 反过来就是 d -> c -> b -> a 。 这里讲解两种方法: 第一种方法就是把每个Node按照顺序存入到一个stack里面,这样,最后面一个就在最上面了。然后,把每一个再取出来,这样顺序就换过来了。 public static Node reverse(Node head) { Stack
单链表的复制——C++实现
#include #include using namespace std; typedef int DataType; /*定义链表数据结构*/ typedef struct node{ DataType data; struct node * next; }LNode,* LinkList; int main(){ /*函数声明*/ LinkList Tail_Create_Li
数据结构实验之二叉树的建立与遍历
题目描述        已知一个按先序序列输入的字符序列,如abc,,de,g,,f,,,(其中逗号表示空节点)。请建立二叉树并按中序和后序方式遍历二叉树,最后求出叶子节点个数和二叉树深度。 输入  输入一个长度小于50个字符的字符串。 输出 输出共有4行: 第1行输出中序遍历序列; 第2行输出后序遍历序列; 第3行输出叶子节点个数; 第4行输出二叉树深度。 示例输入
js遍历el list对象
var companyOptions = ""; c:forEach items="${companyList}" var="t"> companyOptions += "${t.id}'>${t.name}"; c:forEach> $("#companyId").append(companyOptions);
什么是linkedlist?
linkedlist的意义我们知道 ArrayList 是以数组实现的,遍历时很快,但是插入、删除时都需要移动后面的元素,效率略差些。而LinkedList 是以链表实现的,插入、删除时只需要改变前后两个节点指针指向即可,省事不少。LinkedList的定义LinkedList 是链表实现的线性表(双链表)。双链表中的结点结构图LinkedList 特点双向链表实现元素时有序的,输出顺序与输入顺序...
单向链表的节点创建和头插、尾插、任意位置插入节点的实现
单向链表的节点创建和头插、尾插、任意位置插入节点的实现 今天复习了以下链表的知识,决定通过自己的理解直接手撕代码,不去参考已经写过的链表代码,在不断的调试中,总算写出来了同时发现对指针和单向链表有了更深的理解。 实现代码: //单向链表 struct Node //用结构体作为链表的节点 { Node *next; //用于存储下一个节点的地址 string data...
C语言:循环单链表的创建,遍历,插入
/* 1.循环单链表的创建,由尾节点指向该链表, 2.循环链表遍历 3.求链表的长度 4.向链表中插入元素 */ # include # include typedef struct node { int data; struct node * pNext; }NODE, * PNODE; PNODE creat_list(); //创建链表 void traves
【LeetCode-面试算法经典-Java实现】【203-Remove Linked List Elements(删除单链表中的元素)】
【203-Remove Linked List Elements(删除单链表中的元素)】【LeetCode-面试算法经典-Java实现】【所有题目目录索引】代码下载【https://github.com/Wang-Jun-Chao】原题  Remove all elements from a linked list of integers that have value val.   Exampl
C#高级编程五十一天----链表
链表 LinkedList集合类没有非泛型类的版本,它是一个双向链表,他的元素指向元素的前一个与后一个元素. 链表的有点事:如果要插入一个元素到链表的中间位置,效率很高,因为如果插入一个元素,只需要修改上一个元素的Next与下一个元素的Previous的引用即可. 链表的缺点是,链表只能是一个接着一个访问,这样就要用更长的时间来查找定位位于链表中间的元素. LinkedListNode被L
图的创建和遍历
#include #include #include #define MaxInt 32767 #define MAXQSIZE 100 #define MVNum 100 #define OK 1 #define ERROR 0 #define OVERFLOW -2 bool visited[MVNum]; typedef struct {/*存储表示*/ char vexs[MVNum];
C++:实现LinkedList 学习抽象数据类型
C++:实现LinkedList 学习抽象数据类型标签(空格分隔): c++ 数据结构 作者:陈小默C实现LinkedList 学习抽象数据类型 定义需求 作为类 作为List 作为栈stack 作为队列 定义模版 定义数据结构 声明类 方法实现 演示 用作一般数据存储 用作栈 用作队列 如果之前学习过java的话,一定接触过其中的ArrayList和LinkedList。当我们说起其中的区别时,
C++ 无向图 邻接表创建 广度遍历 深度遍历
花了点时间,写了下 无向图lingjieb
数据结构c语言实现-链表(带和不带头节点)
                                                                                                   数据结构与算法分析——c语言描述第3章   第二节   表1.带头结点(原书)   稍微改造一下#include &amp;lt;stdio.h&amp;gt; #include &amp;lt;stdlib.h&amp;gt; st...
图的遍历与输出 (邻接矩阵和邻接表)
#include #include #include "graph.h" using namespace std; int main() { freopen("data.in" , "r" , stdin); // cout << "\n ** 生成邻接矩阵图,并进行DFS遍历输出: "<< endl; // MGraph mg ; // createMGra
Reorder List 链表首尾交叉排列@LeetCode
思路就是: 1 用快慢指针找到中间节点 2 翻转中间节点后一个元素到最后一个元素区间的所有元素 3 断开前半段和翻转后的后半段元素 4 把前半段和翻转后的后半段元素以交叉的方式合并起来 5 特殊处理输入为空,只有一个元素和只有两个元素的corner case,就是多加几个if...return 感想:可以看出翻转链表实在是非常重要,是做很多题目的基础。还有merge的思想也很重
头插法实现逆转链表
插法实现逆转链表List Reverse(List L)
相关热词 c#怎么获得线程名 c# usb 采集器 c# csv 读取 c# sort() c# 关闭io流 c# 响应函数 插入 c#面对对象的三大特性 c# 打印 等比缩放 c#弹出右键菜单 c#1如何搞成01
立即提问