数据结构列表与链表,数据结构List

  数据结构列表与链表,数据结构List

  基本数据结构:链表)-C plus-C blog

  基本数据结构:链表

  作者:C肖佳更新时间:2012年7月31日

  在说链表之前,先说线性表。线性表是最基本、最简单、最常用的数据结构。线性表中数据元素之间的关系是一对一的,即除了第一个和最后一个数据元素之外,所有数据元素都是端到端的。线性表的存储方式有两种,一种是顺序存储结构,另一种是链式存储结构。

  顺序存储结构意味着两个相邻的元素在内存中也是相邻的。这种存储方式的优点是查询的时间复杂度为O(1),可以通过首地址和偏移量直接访问一个元素。搜索的自适应算法有很多,最快的可以达到O(logn)。缺点是插入和删除的时间复杂度最坏可以达到O(n)。如果在第一个位置插入一个元素,需要将数组中的每个元素向后移动一位。如果删除第一个位置的元素,需要将数组中的每个元素向前移动一位。另一个缺点是,当你不确定元素的数量时,你打开的数组必须保证能放下最大数量的元素。不幸的是,如果实际数量远小于最大数量,那么你打开的数组未使用的内存只能被浪费。

  我们常用的阵列是典型的顺序存储结构,如图1所示。

  链式存储结构是指两个相邻的元素在内存中可能不相邻,每个元素都有一个指针字段,一般存储指向下一个元素的指针。这种存储方式的优点是插入和删除的时间复杂度为O(1),不会浪费太多内存。你只会在添加元素的时候申请内存,删除元素会释放内存。缺点是访问的时间复杂度最差是O(n),关于搜索的算法很少,只能遍历,所以时间复杂度是线性的(O(n)),频繁的应用和内存释放也会消耗时间。

  顺序表的特点是随机读取,即访问一个元素的时间复杂度为O(1),链表的特点是插入和删除的时间复杂度为O(1)。根据实际情况,选择适合自己的收纳结构。

  链表是存储在链中的线性表。根据指针字段的不同,链表分为单向链表、双向链表、循环链表等。

  1.单向链表

  最简单的一种链表是单向链表。每个元素包含两个字段,一个值字段和一个指针字段。我们称这样的元素为节点。在每个节点的指针字段中,都有一个指向下一个节点的指针,最后一个节点指向一个空值。图2是一个单向链表。

  单向链表的节点分为两部分。第一部分存储或显示一个节点的信息,第二部分存储下一个节点的地址。单向链表只能单向遍历。

  我写了一个简单的C版单向链表模板,所以我将用这段代码来说明如何写一个具体的单向链表(代码仅供学习)。当然,首先你要有C的基础知识和简单的模板元编程。

  完全码

  首先我们要写一个节点类,链表中的每个节点都是一个节点类的对象。如图3所示。

  代码如下:

  模板类别t

  类别列表节点

  {

  公共:

  slist node(){ next=NULL;}//初始化

  Tdata//值

  slistNode * next//指向下一个节点的指针

  };

  第二步是写单链表类的声明,包括属性和方法。

  代码如下:

  模板类别t

  classmyslist

  {

  私人:

  unsignedintlistlength

  slistNode T * node//临时节点

  slistNode T * lastnode//头节点

  slistNode T * headnode//尾节点

  公共:

  myslist();//初始化

  unsignedintlength();//链接列表元素的数量

  void add(Tx);//在页脚添加元素

  void traversal();//遍历整个链表并打印出来

  boolisEmpty();//判断链表是否为空。

  slist node T * find(Tx);//找到第一个值为X的节点,返回该节点的地址。如果找不到,则返回NULL。

  void delete(Tx);//删除第一个值为x的节点。

  voidinsert(Tx,slist node T * p);//在p节点后插入值为x的节点

  void inserthead(Tx);//在链表的开头插入一个节点

  };

  第三步是编写构造函数,初始化链表类的属性。

  代码如下:

  模板类别t

  myslist T :myslist()

  {

  node=NULL

  lastnode=NULL

  headnode=NULL

  list length=0;

  }

  第四步是实现add()方法。

  代码如下:

  模板类别t

  voidmyslist T :add(Tx)

  {

  node=newslitnode T//申请新节点

  node-data=x;//新节点被赋予x。

  If(lastnode==NULL)//如果没有尾节点,则链表为空。节点既是头节点又是尾节点。

  {

  headnode=节点;

  lastnode=node

  }

  否则//如果链表不为空

  {

  lastnode-next=node;//node是尾节点的下一个节点。

  lastnode=node//节点成为尾节点,尾节点被赋值为节点。

  }

  列表长度;//元素数量1

  }

  第五步,实现traversal()函数,遍历并输出节点信息。

  代码如下:

  模板类别t

  voidmyslist T :traversal()

  {

  node=headnode//指向带有临时节点的头节点

  while(节点!=NULL)//遍历链表并输出

  {

  cout节点-数据结束;

  node=node-next;

  }

  cout endl

  }

  第六步:实现isEmpty()函数,判断链表是否为空,为真则不为空。

  代码如下:

  模板类别t

  boolmyslist T :isEmpty()

  {

  returnlist length==0;

  }

  步骤7:实现find()函数。

  代码如下:

  模板类别t

  slistNode T *myslist T :find(Tx)

  {

  node=headnode//指向带有临时节点的头节点

  while(节点!=空节点数据!=x)//遍历链表,跳出相同值的节点。

  {

  node=node-next;

  }

  returnnode//返回找到的节点的地址,如果没有找到,则返回NULL

  }

  第八步:实现delete()函数删除第一个值为x的节点,如图4所示。

  代码如下:

  模板类别t

  voidmyslist T :Delete(Tx)

  {

  slistNode T * temp=headnode//申请一个临时节点指向头节点

  if(temp==NULL)返回;//如果头节点为空,则链表没有元素,直接返回。

  If(temp- data==x)//如果头节点的值是要删除的值,则删除cast节点。

  {

  head node=temp-next;//将头节点指向头节点的下一个节点

  if(temp-next==NULL)lastnode=NULL;//如果链表中只有一个节点,删除后就没有节点了。将尾节点留空。

  删除(临时);//删除头节点

  返回;

  }

  while(temp- next!=NULL temp- next- data!=x)//遍历链表,找到第一个值等于x的节点,temp表示这个节点的上一个节点。

  {

  temp=temp-next;

  }

  if(temp- next==NULL)返回;//如果没有找到,则返回

  If(temp- next==lastnode)//如果找到了尾节点

  {

  lastnode=temp//将尾节点指向它的前一个节点

  删除(temp-next);//删除尾节点

  temp-next=NULL;

  }

  否则//如果它不是尾节点,如图4所示

  {

  node=temp-next;//用临时节点node指向要删除的节点

  temp-next=node-next;//待删除节点的上一个节点指向待删除节点的下一个节点

  删除(节点);//删除节点

  node=NULL

  }

  }

  第九步:实现insert()和insertHead()函数,在p节点后插入值为x的节点。如图5所示。

  代码如下:

  模板类别t

  voidmyslist T :insert(Tx,slistNode T *p)

  {

  if(p==NULL)返回;

  Node=newslistNode T //申请新的空间

  node-data=x;//如图5所示

  node-next=p-next;

  p-next=节点;

  If(node- next==NULL)//如果该节点是尾节点

  lastnode=node

  }

  模板类别t

  voidmyslist T :insertHead(Tx)

  {

  node=新闻列表Node T

  node-data=x;

  node-next=head node;

  headnode=节点;

  }

  最后,我们完成一个简单的单向链表。这个单向链表代码有很多需要改进的地方,以后会修改,不定期更新。

  双向链表

  双向链表的指针字段有两个指针,每个数据节点分别指向直接后继和直接前任。单向链表只能从表头向后遍历,双向链表既可以向前遍历也可以向后向前遍历。除了双向遍历的优点,删除双向链表的时间复杂度会降低到O(1),因为可以直接通过目的指针找到前驱节点,而单向链表要从头开始遍历才能找到前驱节点。缺点是每个节点多一个指针的空间开销。图6是一个双向链表。

  第三,循环链表

  循环链表是指链表的最后一个节点指向第一个节点,从而形成一个可以循环遍历的圆。单向循环链表可以单向遍历,双向循环链表头节点的指针也要指向最后一个节点,可以双向遍历。图7是一个双向循环链表。

  第四,链表的相关问题

  1.如何判断单个链表有环?

  2.如何判断一枚戒指的切入点在哪里?

  3.如何知道戒指的长度?

  4.如何知道两个单链表(非循环的)是否相交?

  5.如果两个单链表(非循环的)相交,怎么知道它们相交的第一个节点是什么?

  6.如何知道两个单链表(带环的)是否相交?

  7.如果两个单链表(有环的)相交,怎么知道它们相交的第一个节点是什么?

  回答

数据结构列表与链表,数据结构List