专栏首页随笔记录C++链表的创建与操作

C++链表的创建与操作

我们知道,数组式计算机根据事先定义好的数组类型与长度自动为其分配一连续的存储单元,相同数组的位置和距离都是固定的,也就是说,任何一个数组元素的地址都可一个简单的公式计算出来,因此这种结构可以有效的对数组元素进行随机访问。但若对数组元素进行插入和删除操作,则会引起大量数据的移动,从而使简单的数据处理变得非常复杂,低效。

为了能有效地解决这些问题,一种称为“链表”的数据结构得到了广泛应用。 1. 链表概述 链表是一种动态数据结构,他的特点是用一组任意的存储单元(可以是连续的,也可以是不连续的)存放数据元素。 链表中每一个元素成为“结点”,每一个结点都是由数据域和指针域组成的,每个结点中的指针域指向下一个结点。Head是“头指针”,表示链表的开始,用来指向第一个结点,而最后一个指针的指针域为NULL(空地址),表示链表的结束。 可以看出链表结构必须利用指针才能实现,即一个结点中必须包含一个指针变量,用来存放下一个结点的地址。 实际上,链表中的每个结点可以用若干个数据和若干个指针。结点中只有一个指针的链表称为单链表,这是最简单的链表结构。 在c++中实现一个单链表结构比较简单。例如,可定义单链表结构的最简单形式如下

struct Node
 {
 int Data;
 Node*next;
 };

这里用到了结构体类型。其中,*next是指针域,用来指向该结点的下一个结点;Data是一个整形变量,用来存放结点中的数据。当然,Data可以是任何数据类型,包括结构体类型或类类型。 在此基础上,我们在定义一个链表类list,其中包含链表结点的插入,删除,输出等功能的成员函数。

class list
 {
 Node*head;
 public:
 list(){head=NULL;}
 void insertlist(int aDate,int bDate);//链表结点的插入
 void Deletelist(int aDate);//链表结点的删除
  void Outputlist();//链表结点的输出

  Node*Gethead(){return head;}
};

2. 链表结点的访问 由于链表中的各个结点是由指针链接在一起的,其存储单元文笔是连续的,因此,对其中任意结点的地址无法向数组一样,用一个简单的公式计算出来,进行随机访问。只能从链表的头指针(即head)开始,用一个指针p先指向第一个结点,然后根据结点p找到下一个结点。以此类推,直至找到所要访问的结点或到最后一个结点(指针为空)为止。 下面我们给出上述链表的输出函数

 void list::outputlist()
 {
 Nodecurrent=head;
 while(current!=NULL)
 {
 cout<Data<<" ";
 current=current->next;
 }
 cout<<endl;
 }

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中的数据
 {
 Nodep,*q,s;       //p指向结点a,q指向结点a_k,s指向结点b
 s=(Node)new(Node);   //动态分配一个新结点
 s->Data=bDate;      //设b为此结点
 p=head;
 if(head==NULL)      //若是空表,使b作为第一个结点
 {
 head=s;
 s->next=NULL;
}
else if(p->Data==aDate) //若a是第一个结点
{
   s->next=p;
   head=s; 
}
 else
 {
 while(p->Data!=aDate&&p->next!=NULL)//查找结点a
 {
 q=p;
 p=p->next;
 }
 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不存在,则不做任何改变。 以下是链表类的结点删除函数。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Matlab中libsvm工具箱用PSO优化SVM做回归,训练集结果很好,但测试集结果是一条直线?

    部分代码如下: load data.mat %% % 1. 随机产生训练集和测试集 n = randperm(size(c,2));

    w4979的博客
  • 抛出IllegalStateException异常。Queue-PriorityQueue源码解析

    add(E e) -> 往队列添加一个元素,如果队列已满抛出IllegalStateException异常。 offer(E e) -> 往队列添加一个元素,...

    w4979的博客
  • Kali Linux中安装Xfce的步骤2-2 通过update-alternatives

    在软件系统中,有时候面临着一个复杂对象的创建工作,其通常由各个部分的子对象用一定的算法构成。由于需求的变化,这个复杂对象的各个部分经常面临着剧烈的变化,但是它们...

    w4979的博客
  • 关于索引以及B-Tree的实现

    对于多数的应用系统来说,查询数据的频率是远远高于写入或者更新数据的频率,在大数据量的场景中,常规的查询方式可能在效率上达不到预期, 此时我们需要对SQL查询语句...

    每天学Java
  • 数据结构—线性表

    本篇开始,又会开始一个新的系列,数据结构,数据结构在算法或者是编程中的重要性不言而喻,所以学好数据结构还是很有必要的。本篇主要介绍数据结构的第一个结构——线性表...

    张俊红
  • 数据结构 | 每日一练(21)

    ——老子

    C语言入门到精通
  • 【数据结构系列】单链表

    最近也一直在思考该写点什么文章,想了很久,还是决定重新编写一下数据结构的相关内容,关于数据结构的重要性就不用我多说了,之前的文章中我也写过,但实现语言是Java...

    wangweijun
  • 红黑树

    每个结点不是红色就是黑色 不可能有连在一起的红色结点 根结点都是黑色 每个红色结点的两个子结点都是黑色 任一结点到其子树中每个叶子节点的路径都有相同数量...

    瑞新
  • 漫画:什么是AVL树?(修订版)

    对于AVL树的每一个结点,平衡因子是它的左子树高度和右子树高度的差值。只有当二叉树所有结点的平衡因子都是-1, 0, 1这三个值的时候,这颗二叉树才是一颗合格的...

    小灰
  • 漫画:什么是平衡二叉树?

    对于AVL树的每一个结点,平衡因子是它的左子树高度和右子树高度的差值。只有当二叉树所有结点的平衡因子都是-1, 0, 1这三个值的时候,这颗二叉树才是一颗合格的...

    小灰

扫码关注云+社区

领取腾讯云代金券