线性链表各个数据节点存储空间必须连续吗_百度知道
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。
线性链表各个数据节点存储空间必须连续吗
我有更好的答案
线性链表中的线性指的是链表中各个结点是线性存在的,而非存储空间
采纳率：31%
链表的节点都不需要是连续的存储空间，节点是通过指针连接的。
存储空间不需要连续，所以才通过指针相连
不需要。每个节点有指针域，可以链接到下一个节点。
其他3条回答
为您推荐：
其他类似问题
您可能关注的内容
存储空间的相关知识
换一换
回答问题，赢新手礼包C++链表动态内存分配操作大全【访问、插入、删除】 09:13:51
( 2人已投票,[高质量] )
分享: ╬收藏31.3K
在C++中关于数组，其实数组只是计算机根据事先定义好的数组类型与长度自动为其分配一连续的存储单元，相同数组的位置和距离都是固定的，意味着任意数组元素的地址都由简单的公式计算出来，因此这种结构可以有效的对数组元素进行随机访问。但若对数组元素进行插入和删除操作，则会引起大量数据的移动，从而使简单的数据处理变得非常复杂，低效。为了能有效地解决这些问题，一种称为“链表”的数据结构应运而生。1、 链表概述：链表是一种（动态）数据结构，特点是用一组任意的存储单元（连续或不连续的）存放数据元素。链表中每一个元素成为“节点”，每一个节点都是由数据域和指针域组成的，每个节点中的指针域指向下一个节点。Head是“头指针”，表示链表的开始，用来指向第一个节点，而最后一个指针的指针域为NULL(空地址)，表示链表的结束。可以看出链表结构必须利用指针才能实现，即一个节点中必须包含一个指针变量，用来存放下一个节点的地址。实际上，链表中的每个节点可以用若干个数据和若干个指针。节点中只有一个指针的链表称为单链表，这是最简单的链表结构。再c++中实现一个单链表结构比较简单。例如，可定义单链表结构的最简单形式如下：struct Node{
};这里用到了结构体类型。其中，*next是指针域，用来指向该节点的下一个节点；Data是一个整形变量，用来存放节点中的数据。当然，Data可以是任何数据类型，包括结构体类型或类类型。在此基础上，我们在定义一个链表类list，其中包含链表节点的插入，删除，输出等功能的成员函数。class list{
public: list(){
head=NULL;
void insertlist(int aDate,int bDate);//链表节点的插入
void Deletelist(int aDate);//链表节点的删除
void Outputlist();//链表节点的输出
Node*Gethead(){}
};2、 链表节点的访问：由于链表中的各个节点是由指针链接在一起的，其存储单元文笔是连续的，因此，对其中任意节点的地址无法向数组一样，用一个简单的公式计算出来，进行随机访问。只能从链表的头指针（即head）开始，用一个指针p先指向第一个节点，然后根据节点p找到下一个节点。以此类推，直至找到所要访问的节点或到最后一个节点（指针为空）为止。下面我们给出上述链表的输出函数；void list::outputlist(){
Node*current=
while(current!=NULL) {
cout&&current-&Data&&" ";
current=current-&
cout&&}3、 链表节点的插入：如果要在链表中的节点a之前插入节点b，则需要考虑下面几点情况。（1） 插入前链表是一个空表，这时插入新节点b后。（2） 若a是链表的第一个节点，则插入后，节点b为第一个节点。（3） 若链表中存在a,且不是第一个节点，则首先要找出a的上一个节点a_k，然后使a_k的指针域指向b，在令b的指针域指向a，即可完成插入。（4） 如链表中不存在a，则插在最后。先找到链表的最后一个节点a_n，然后使a_n的指针域指向节点b，而b指针的指针为空。以下是链表类的节点插入函数，显然其也具有建立链表的功能。void list::insertlist(int aDate,int bDate){//设aDate是节点a中的数据，bDate是节点b中的数据
Node *p,*q,*s;
//p指向节点a，q指向节点a_k，s指向节点b
s=(Node*)new(Node); //动态分配一个新节点
s-&Data=bD
//设b为此节点
if(head==NULL){//若是空表，使b作为第一个节点
s-&next=NULL;
}else if(p-&Data==aDate){//若a是第一个节点
s-&next=p;
while(p-&Data!=aDate&&p-&next!=NULL){//查找节点a
if(p-&Data==aDate){//若有节点a
q-&next=s;
s-&next=p;
}else{//若没有节点a；
p-&next=s;
s-&next=NULL;
}}4、 链表节点的删除：如果要在链表中删除节点a并释放被删除的节点所占的存储空间，则需要考虑下列几种情况。（1） 若要删除的节点a是第一个节点，则把head指向a的下一个节点。（2） 若要删除的节点a存在于链表中，但不是第一个节点，则应使a得上一个节点a_k-1的指针域指向a的下一个节点a_k+1。（3） 空表或要删除的节点a不存在，则不做任何改变。以下是链表类的节点删除函数。void list::deletelist(int aDate){//设aDate是要删除的节点a中的数据成员
Node*p,*q;//p用于指向节点a,q用于指向结a的前一个节点
if(p==NULL)//若是空表
if(p-&Data==aDate){//若a是第一个节点
while(p-&Data!=aDate&&p-&next!=NULL){//查找节点a
if(p-&Data==aDate){//若有节点a
q-&next=p-&
}}以上三个链表操作成员函数insertlist,deletelist.outputlist,可形成以下的简单链表操作程序。#include"iostream.h"
struct Node{
class list{ Node*public: list(){
head=NULL;
void insertlist(int aData,int bData);
void deletelist(int aData);
void outputlist();
Node*gethead(){}};
void list::insertlist(int aData,int bData){//设aData是节点a中的数据，bData是节点b中的数据
Node*p,*q,*s;
//p指向节点a，q指向节点a_k，s指向节点b
s=(Node*)new(Node); //动态分配一个新节点
s-&Data=bD
//设b为此节点
if(head==NULL){//若是空表，使b作为第一个节点
s-&next=NULL;
}else if(p-&Data==aData){//若a是第一个节点
s-&next=p;
while(p-&Data!=aData && p-&next!=NULL){//查找节点a
if(p-&Data==aData){//若有节点a
q-&next=s;
s-&next=p;
}else{//若没有节点a；
p-&next=s;
s-&next=NULL;
void list::deletelist(int aData){//设aData是要删除的节点a中的数据成员
Node*p,*q;//p用于指向节点a,q用于指向结a的前一个节点
if(p==NULL)//若是空表
if(p-&Data==aData){//若a是第一个节点
while(p-&Data!=aData&&p-&next!=NULL){//查找节点a
if(p-&Data==aData){//若有节点a
q-&next=p-&
void list::outputlist(){
Node*current=
while(current!=NULL) {
cout&&current-&Data&&" ";
current=current-&
void main(){
int Data[10]={25,41,16,98,5,67,9,55,1,121};
A.insertlist(0,Data[0]);//建立链表A首节点
for(int i=1;i&10;i++)
A.insertlist(0,Data[i]);//顺序向后插入
cout&&"\n链表A:";
A.outputlist();
A.deletelist(Data[7]);
cout&&"删除元素Data[7]后";
A.outputlist();
B.insertlist(0,Data[0]); //建立链表B首节点
for(i=0;i&10;i++)
B.insertlist(B.gethead()-&Data,Data[i]); //在首节点处顺序向后插入
cout&&"\n链表B:";
B.outputlist();
B.deletelist(67);
cout&&"删除元素67后";
B.outputlist();
}程序运行结果为链表A；25，41，16，98，5，67，9，55，1，121删除元素Data[7]后；25，41，16，98，5，67，9，1，121链表B；121，1，55，9，67，5，98，16，41，25删除元素67后；121，1，55，9，5，98，16，41，25接着下面来一段杨辉三角的参考代码：#include &iostream&
#include &iomanip&
int main(){
const int n=11;
int i,j,a[n][n];
for(i=1;i&n;i++){
a[i][i]=1;
a[i][1]=1;
for(i=3;i&n;i++){
for(j=2;j&=i-1;j++)
a[i][j]=a[i-1][j-1]+a[i-1][j];
for(i=1;i&n;i++){
for(j=1;j&=i;j++)
cout&&setw(5)&&a[i][j]&&" ";
相关推荐：
随机推荐：
你还没有登录，要回复请
收藏到我的私密空间
标题：C++链表动态内存分配操作大全【访问、插入、删除】作者：柳岸花明
你暂未登录，请登录后才可收藏至您的私密空间
键盘操作 更便捷 -雪炭网雪中送炭－乐趣无限
(C) 2016 SnowCoal - All Right Reserved.2005年4月 C/C++大版内专家分月排行榜第二
2004年3月 C/C++大版内专家分月排行榜第三
2004年3月 C/C++大版内专家分月排行榜第三
2004年3月 C/C++大版内专家分月排行榜第三
本帖子已过去太久远了，不再提供回复功能。链表 - 简书
什么是链表
是一种物理存储单元上非连续/非顺序的存储结构.
所谓链表即是由多个节点组成,像一条铁链,铁链的每一个环就相当于链表的节点.
一个节点用于储存数据的内存控件
一个节点用于储存和它连接的下一个节点地址的内存空间
不需要指定内存空间的大小,非常具有灵活性
删除一个节点不需要像数组那样将其余的数据整体向前移动,只需要修改节点的指针域即可完成删除节点的操作
可以通过循环或者递归访问到链表的任何数据,但是访问效率低于数组(线性数据结构)
由于不是线性结构,并且相对于线性的储存结构来说,需要保存每个节点的指针域,这又是一笔内存开销,占用了内存空间,对内存空间的利用效率低
链表的种类
是连接方向单一的链表,从头结点开始可以一直指向尾节点,方向不会改变(即从头结点走到尾节点只有一条路径).其中每一个节点的指针域只有一个指向,也就是一个节点有一个指针,可以保存下一个节点
每一个节点的指针域中保存有两个指针(引用),可以同时指向该节点的前驱节点和后继节点
单链表:是一种逻辑上的线性结构,只有一条链,首尾不相接
环形链表:首尾相接的链表(类比丢手帕)(约瑟夫问题)
如何创建链表
图形化结构
signal-linked-list
signal-circular-linked-list
double-signal-linked-list
double-signal-circular-linked-list
Node-class
数据域 : 节点中储存数据内存控件
指针域 : 节点中储存其他节点(可能是下一个,也可能是上一个)的地址信息的内存空间
[Java]单项链表类图//TODO 修改类图(无bug的类图)
LinkedList_Class_Map
//TODO 书写思路
//TODO 书写思路
单向环形链表
//TODO 书写思路
双向环形链表
//TODO 书写思路
[]单向链表
[Java]双向链表//TODO 添加超链接
[Java]单向环形链表//TODO 添加超链接
[Java]双向环形链表//TODO 添加超链接
如何使用链表
数据域 : Object data
Node successorNode//前驱节点(双向链表节点特有属性)
Node precursorNode//后继节点
构造方法 : (根据传入的Object对象创建一个后继节点指向null的Node对象)
查询节点数据 : private Object getData()
修改节点数据 : private void setData(Object newData)//当Node类的成员属性不是私有的时候不需要这些方法,并且就算有这些方法,它们的修饰符也不能是private
长度 : int length = 0
头结点引用 : Node headNode = null
尾节点引用 : Node tailNode = null ? ?(双向链表特有属性)
方法[单向链表]//TODO完成四种链表的分类
初始化链表(利用构造器) : public LinkedList()
增加尾节点 : public void add()
插入指定节点: public void insert(int index)
删除尾节点 : public void del()
删除指定节点 : public void del(int index)
修改尾节点 : public void update(Object newData)
修改指定节点 : public void update(int index, Object newData)
获取尾节点 : public Node getNode()
获取指定节点 : public Node getNode(int index)
链表长度 : public int length()
判断空链表 : public boolean isEmpty()
排序 : public void sort()
截取链表 : public LinkedList subLinkedList(int start, int end)
如何进行测试
当我们构建好了我们自己的链表的时候,就必须得对其正确性和健壮性进行测试,这个测试的过程一般来说是随着编码一起进行的,我们来看一下应该如何进行测试.
正确性//TODO
健壮性//TODO
如何优化链表
链表的应用场景
首先我们知道链表的特点就是可以动态地增加和删除元素,就类似与一个可以自动扩大和缩小容量的数组,因此,我们可以想到它的应用场景应该有:
1.求解约瑟夫问题(利用环形链表)
[Java]单向链表代码 :
package linkedL
* 节点类(单向链表)
* @author 王一航
class Node {
Node nextNode =//单向链表因此只有一个指向自身类型的引用
//构造函数
public Node(Object data){
this.data =
package linkedL
/** * 单向链表类 * @author 王一航 */
public class LinkedList {
* 成员变量
*/ int length = 0;
Node headNode =
* 成员方法
//初始化链表(利用构造器)
public LinkedList(){
int length = 0;//记录链表长度
Node headNode =//头结点
//增加尾节点
public void add(Object data){
insert(length, data);
//插入指定节点
public void insert(int index, Object data){
Node temp = getNode(index);//使用一个临时的引用记录需要插入的位置的前驱结点的地址
Node node = new Node(data);//创建新节点准备插入
if(index & 0){
getNode(index - 1).nextNode =
headNode =
node.nextNode =
//删除尾节点
public void del(){
del(length - 1);
//删除指定节点
public void del(int index){
//TODO 检查入口参数
if(index & 0){
getNode(index - 1).nextNode = getNode(index + 1);
if(index == 0){
headNode = getNode(1);
} //TODO 释放内存
//修改尾节点
public void update(Object newData){
update(length - 1, newData);
//修改指定节点
public void update(int index, Object newData){
getNode(index).data = newD
//获取尾节点
public Node getNode(){
return getNode(length - 1);
//获取指定节点
public Node getNode(int index){
point = headN
int count = 0;
while(count & index){
point = point.nextN
}catch(NullPointerException e){
System.out.println("请检查链表是否越界! 链表长度 : " + length);
//链表长度
public int length(){
//判断空链表
public boolean isEmpty(){
return length == 0 ? true :
public void sort(){
//TODO 完成排序功能
System.out.println("请完成排序功能!");
//截取链表
public LinkedList subLinkedList(int start, int end){
if(end &= start){
headNode = getNode(start);
getNode(end - start).nextNode =
length = end -
//TODO 释放不需要的内存
//打印链表所有元素
public void show(){
for(int i = 0; i & i++){
System.out.println("索引 : " + i + " 第" + (i+1) + "个" + getNode(i).data);
[Java]双向链表代码 :
package doubleLinkedL
/** * 双向链表节点类 * @author 王一航 */
class Node {
Node lastNode =//前驱节点引用
Node nextNode =//后继节点引用
//构造函数
public Node(Object data){
this.data =
//TODO 添加双向链表的代码
[Java]单向环形链表代码 :
//TODO 添加代码
package circularLinkedL
/** * 单向环形链表节点类 * @author 王一航 */
public class Node {
* 成员属性
Node successorN//后继节点
* 成员方法
public Node(Object data){
this.data =
[Java]双向环形链表代码 :
//TODO 添加代码
package circularLinkedL
/** * 双向环形链表节点类 * @author 王一航 */
public class Node {
* 成员属性
Node successorN//后继节点
Node precursorN//前驱节点
* 成员方法
public Node(Object data){
this.data =
总结(个人理解):
关于健壮性 :
当某一个方法需要入口参数的时候,必须对入口参数的合法性进行检查(以后要将这种意识变成一种意识)
关于代码结构 :
关于方法的组织 :
良好的代码中方法的组织结构应该具有"高内聚低耦合"的特点
关于属性和方法的命名 :
关于类图的使用 :
1 . 杜绝魔术数字的出现,程序中一旦需要使用到某些常量,则必须首先声明常量为一个有意义的名字,然后根据这个名字去访问该常量
我还年轻,我渴望上路,带着最初的激情和梦想,我们上路吧!
Github : /WangYihang
GitBook : https://wangyihang.gitbooks.io/
SniperOJ :
CVE : ['CVE-', 'CVE-', 'CVE-', 'CVE-', 'CVE-', ' CVE-']
作为一个资深的新手程序员?,链表这些既基础又深奥的东西是日常工作中并不常见,但是却非常重要,所以就总结一下链表的简单认识! 数组作为存放同类数据的集合，给我们在程序设计时带来很多的方便，增加了灵活性。但数组也同样存在一些弊病。如数组的大小在定义时要事先规定，不能在程序中进行...
本文内容：1、 什么是链表？2、 链表共分几类？3、 链表的 C 实现！ 总表：《数据结构？》 工程代码 Github: Data_Structures_C_Implemention -- Link List 1、什么是链表？ 链表 [Linked List]：链表是由一组...
链表 概念 说到链表，coder们都不会陌生，在日常开发中或多或少都会用到它。它是链式存储的线性表，简称链表。链表由多个链表元素组成，这些元素称为节点。结点之间通过逻辑连接，形成链式存储结构。存储结点的内存单元，可以是连续的也可以是不连续的。逻辑连接与物理存储次序没有关系。...
【声明】欢迎转载，但请保留文章原始出处→_→文章来源：/p/08d085b34b2c联系方式： 【正文】链表是非常基础和灵活的数据结构，在面试中出现的频率非常高。以下是我在学习《剑指offer》过...
//leetcode中还有花样链表题，这里几个例子，冰山一角 求单链表中结点的个数----时间复杂度O（n）这是最最基本的了，应该能够迅速写出正确的代码，注意检查链表是否为空。参考代码如下： 将单链表反转----时间复杂度O（n）(也可以先inplace的翻转，再遍历，空间...
-1 我以为努力过你会懂，结果被秋风吹下的落叶也在嘲笑着我，你看，夏日也已经离开，伴随立秋的冷风，迎来的又将是一个寂寥的冬季。 我分手了。 手机弹出消息的时候，我正打着游戏，英雄已经攻到水晶，不用想也一定能猜到是方小姐的消息。划开屏幕，这是第几次她说这句话了，我已经不记得了...
前段时间，和业内朋友聊天，又聊到了应该“重实体、轻程序”还是“重程序、轻实体”的老话题。因为这个话题不仅是法律圈的一个纠结，更是对社会公众容易产生影响的重要话题。因此，觉得有必要多说两句按照自己的感受澄清下。 I.“重实体、轻程序”到底是个什么意思 说白了，“重实体、轻程序...
这本书的目录，戳它。 第六章第七章
猜想 可是他们刚才的眼神，我很怕，我竟然不想，也不敢在拥有现在的温暖，我想要，躲开他们，毁掉他们，我要杀了他们。 突然而来的这么温暖的怀抱，这么温暖的目光，我竟然可以接受刚才那样的眼神了，准确的说，现在的这种眼神，足以让我忘记所有的悲痛...
不管是在学校里还是在校外，总会发现现在的年轻人做事的少，抱怨的多。常说自己的父母是农民，不富有。但是，20年后，你的孩子还会抱怨你不富有吗？上天让我们都生活在同一个时空里，为什么有些人贫穷？为什么有些人富有呢？富人身上有什么特质，穷人又有什么特性呢？如何才能去掉我们身上的劣...
骞卉 （第44天） 目标：获得财务自由，成为榜样，帮助妈妈群体 今天种下与目标相关的种子： 1.给洳霞每日支持，愿她越来越精进，大人小孩都健康快乐 2.猛烈随喜妹妹妹夫从安徽过来帮忙，随喜她们对时间和金钱的慷慨 3.感恩顾客的光临，猛烈猛烈猛烈随喜顾客的慷慨...