C++双向循环列表用法实例

本文实例讲述了C++双向循环列表用法。分享给大家供大家参考。具体如下:

/*
 双向循环链表
*/
#include <iostream>
using namespace std;
//结构体构造链表的指针域和数据域
struct ChainNode
{
 int data; //节点数据
 ChainNode *left; //节点的前驱指针
 ChainNode *right; //节点的后继指针
};
////////////创建n个双向循环链表 并返回链表头指针/////////
ChainNode* CreateNode(int n)
{
 ChainNode *head = NULL; //链表头节点
 ChainNode *pCur=NULL,*pNew=NULL; //当前节点,新建节点
 //初始化头结点的前驱和后继节点都为NULL
 if (n<1) //没有节点 返回头节点
 {
  return head;
 }
 //创建头节点并将器左右指针指向空
 head = new ChainNode;
 head->left = NULL;
 head->right = NULL;
 head->data = 0;
 pCur = head;
 //为防止指针互指带来的混乱,用pCur节点保存了头节点 也表示当前指针移动到了头指针
 //创建n个节点 并连接成链表
 for (int i=0; i<n; i++)
 {
  pNew = new ChainNode; //创建一个新节点
  cout<<"请输入数据:";
  cin>>pNew->data;
  pCur->right = pNew; //头指针的右指针指向新建节点
  pNew->left = pCur; //新建节点的左指针执行头节点
  pNew->right = NULL; //用于最后和头指针进行交换
  pCur = pNew; //指针往下移动
 }
 //最后将头指针的左指针指向最后一个节点,
 //最后一个节点的有指针指向头指针,构成循环
 head->left = pCur;
 pCur->right = head;
 return head;
}
//////////////输出链表头节点///////////////////////
void OutList(ChainNode *head) //参数为头指针 从头指针开始
{
  cout<<"链表元素输出如下:"<<endl;
  ChainNode *pCur = head->right;
  //重第一个节点开始输出
  //没有指向空节点,则链表没结束 输出链表元素
  while (pCur->right != head)
  {
   cout<<pCur->data<<" ";
   pCur = pCur->right;
   //当前节点指向下一个节点 可以遍历链表
  }
  cout<<pCur->data<<endl;
  //输入最后一个元素,它的右指针执行head
}
///////在双向循环链表后添加n个节点//////
ChainNode* AddNode(ChainNode* head, int n)
{
 ChainNode *pNew,*pCur;
 //新添加节点和当前节点
 pCur = head;
 //移动到最节点
 while (pCur->right != head)
 {
   pCur = pCur->right;
   //当前节点往下移动 一直移到最后一个节点
 }
 //新添加n个节点并插入链表
 for (int i=0; i<n; i++)
 {
  pNew = new ChainNode;
  cout<<"输入要添加的节点元素:";
  cin>>pNew->data;
  pCur->right = pNew; //头指针的右指针指向新建节点
  pNew->left = pCur; //新建节点的左指针执行头节点
  pNew->right = NULL; //用于最后和头指针进行交换
  pCur = pNew; //指针往下移动
 }
 //最后将头指针的左指针指向最后一个节点,
 //最后一个节点的有指针指向头指针,构成循环
 head->left = pCur;
 pCur->right = head;
 return head;
}
/////在双向循环链表中删除一个节点///////
ChainNode* DeleteNode(ChainNode* head, unsigned num)
//删除第num个节点
{
 ChainNode *pNew,*pCur,*temp;
 //新添加节点和当前节点 ,临时交换节点
 pCur = head;
 int ncount = 0;
 //移动到第num-1个节点
 while (1)
 {
   ncount++;
   pCur = pCur->right; //当前节点往下移动
   if (num == ncount)
   {
    break; //此时pCur还是指向了第num个节点
   }
 }
 //当前节点的前一个节点的右指针 指向 当前节点的下一个节点
 //当前节点的下一个节点的左指针 指向 当前节点的上一个节点 构成连接
 //最后 删除当前节点
 (pCur->left)->right = pCur->right;
 (pCur->right)->left = pCur->left;
 delete pCur;
 return head;
}
int main()
{
 int num;
 //创建num个节点并显示
 cout<<"输入要创建的链表节点个数:";
 cin>>num;
 ChainNode *head = CreateNode(num);
 OutList(head);
 //往链表后添加n个节点
 int addnum;
 cout<<"输入要添加的节点个数:";
 cin>>addnum;
 AddNode(head, addnum);
 OutList(head);
 //删除链表的第del个元素
 int del;
 cout<<"输入要删除的第几个位置的节点:";
 cin>>del;
 DeleteNode (head, del);
 OutList(head);
 system("pause");
 return 0;
}

希望本文所述对大家的C++程序设计有所帮助。

时间: 2015-07-11

C++循环链表之约瑟夫环的实现方法

本文实例形式展示了C++实现循环链表中约瑟夫环的方法,分享给大家供大家参考之用.具体方法如下: 主要功能代码如下: #include <iostream> using namespace std; typedef struct student { int data; struct student* next; }node,*LinkList; //约瑟夫环 void printfList(LinkList head){ LinkList p=head; if (head!=NULL) { do

简单掌握C++编程中的while与do-while循环语句使用

While 语句 重复执行语句,直到表达式计算为零. 语法 while ( expression ) statement 备注 expression 的测试在每次执行循环前发生:因此 while 循环执行零次或更多次. 表达式必须是整型.指针类型或包含明确的整型或指针类型转换的类类型. 当中断.导航或回归在语句体中执行时,也可以中止while 循环.请使用continue语句来结束当前迭代但不退出while循环. 继续 将控件传递给下一轮循环 while. 以下代码使用 while 循环从字符串

用C++实现单向循环链表的解决方法

用C++实现一个单向循环链表,从控制台输入整型数字,存储在单项循环链表中,实现了求链表大小.不足之处,还望指正! 复制代码 代码如下: // TestSound.cpp : 定义控制台应用程序的入口点.//实现单向循环链表#include "stdafx.h"#include <iostream>#include <string>using namespace std;//定义链表一个节点的结构体template <class T>struct NO

C++条件及循环语句的综合运用实例

用下面公式求π的近似值.π/4≈1-1/3+1/5-1/7+-直到最后一项的绝对值小于10-7为止.根据给定的算法很容易编写程序如下: #include <iostream> #include <iomanip> #include <cmath> using namespace std; int main( ) { int s=1; double n=1,t=1,pi=0; while((fabs(t))>1e-7) { pi=pi+t; n=n+2; s=-s;

C++编程中break语句和continue语句的学习教程

break 语句 break 语句可终止执行最近的封闭循环或其所在条件语句. 控制权将传递给该语句结束之后的语句(如果有的话). break; 备注 break 语句与 switch 条件语句以及 do.for 和 while 循环语句配合使用. 在 switch 语句中,break 语句将导致程序执行 switch 语句之外的下一语句. 如果没有 break 语句,则将执行从匹配的 case 标签到 switch 语句末尾之间的每个语句,包括 default 子句. 在循环中,break 语句

解析C++中的for循环以及基于范围的for语句使用

for循环语句 重复执行语句,直到条件变为 false. 语法 for ( init-expression ; cond-expression ; loop-expression ) statement; 备注 使用 for 语句可构建必须执行指定次数的循环. for 语句包括三个可选部分,如下表所示. for 循环元素 下面的示例将显示使用 for 语句的不同方法. #include <iostream> using namespace std; int main() { // The co

C++循环队列实现模型

本文实例讲述了C++循环队列实现模型.分享给大家供大家参考.具体分析如下: 前段时间在知乎上看到这样一个小题目: 用基本类型实现一队列,队列要求size是预先定义好的的.而且要求不可以使用语言自带的api,如C++的STL.普通的实现很简单,但是现在要求要尽可能的时间和空间复杂度的优化,要和语言自带的api比较时间和空间.这个队列还要支持如下的操作: constructor: 初始化队列 enqueue:入队 dequeue:出队 队列是一种基本的数据结构,在平常的应用中十分广泛,多数情况队列都

C++中的while循环和for循环语句学习教程

C++ while循环 while语句的一般形式如下: while (表达式) 语句 其作用是: 当指定的条件为真(表达式为非0)时,执行while语句中的内嵌语句.其流程图见下图. 其特点是:先判断表达式,后执行语句.while循环称为当型循环. 例:求1+2+3+-+100. #include <iostream> using namespace std; int main( ) { int i=1,sum=0; while (i<=100) { sum=sum+i; i++; }

c++中for双循环的那些事

情况1:如下,这样我们会发现,n输出为100,虽然两层循环的标识符都是i,然是两个做管辖的范围不同,具体情况不明~~~求大神解释 复制代码 代码如下: int main(int argc,char* argv[]){    int n=0;    int mx;    for (int i=0;i<10;i++)    {        for (int i=0;i<10;i++)        {            n++;        }    }    cout<<n&

讲解C++的do while循环和循环语句的嵌套使用方法

用do-while语句构成循环 do-while语句的特点是先执行循环体,然后判断循环条件是否成立.其一般形式为: do 语句 while (表达式); 它是这样执行的:先执行一次指定的语句(即循环体),然后判别表达式,当表达式的值为非零("真") 时,返回重新执行循环体语句,如此反复,直到表达式的值等于0为止,此时循环结束.可以用下图表示其流程. [例]用do-while语句求1+2+3+-+100. #include <iostream> using namespace

如何用C++实现双向循环链表

双向循环链表,即每个节点都拥有一前一后两个指针且头尾互链的链表.各种链表的简单区别如下:单向链表:基本链表:单向循环链表:不同于单向链表以 NULL 判断链表的尾部,单向循环链表的尾部链接到表头,因此当迭代操作到表头前即是尾部:双向链表:比单向链表多出指向前一个节点的指针,但实际上使用双向链表时很少使用不循环的:双向循环链表:相对于单向循环链表,双向循环链表可从头部反向迭代,这在链表长度很大且需要获取.插入或删除靠近链表尾部元素的时候十分高效.单向循环列表只能从表头正向迭代,执行的时间大于从反向

java双向循环链表的实现代码

例1: 复制代码 代码如下: package com.xlst.util; import java.util.HashMap;import java.util.Map;import java.util.UUID; /*** 双向循环链表* 完成时间:2012.9.28* 版本1.0* @author xlst**/public class BothwayLoopLinked {/*** 存放链表长度的 map* * 如果简单使用 static int 型的 size 基本类型变量,则只能维护一个

C语言中双向链表和双向循环链表详解

双向链表和双向循环链表 和单向链表相比,多了一个前驱结点.如果他为空,那么next和prior都指向自己.而对于双循环链表,只需要最后一个元素的next指向head->next,head->next的prior指向最后一个节点即可. 插入操作 新节点s插入链表,s->next给p结点,s->prior给p->prior,然后,p->prior->next指向s,p->prior再指向s.顺序需要注意 s->next = p; s->prior =

C语言数据结构之双向循环链表的实例

数据结构之双向循环链表 实例代码: #include <stdlib.h> #include <stdio.h> #include <malloc.h> typedef struct Node{ struct Node *pNext; int data; struct Node *prior; } NODE,*PNODE; PNODE CreatList(); void TreNode(PNODE pHead); bool isEmpty(PNODE pHead); i

JavaScript数据结构之双向链表和双向循环链表的实现

双向链表和普通链表的区别在于,在链表中,一个节点只有链向下一个节点的链接,而在双向链表中,链接是双向的:一个链向下一个元素,另一个链向前一个元素. 双向链表提供了两种迭代列表的方法:从头到尾,或者反过来.我们也可以访问一个特定节点的下一个或前一个元素.在单向链表中,如果迭代列表时错过了要找的元素,就需要回到列表起点,重新开始迭代.这是双向链表的一个优点. 双向链表:单向链表只能向着一个方向遍历链表节点,而在节点指针域中增加了前向指针的双向链表,则可以向着两个方向遍历节点.这使得双向链表也可以在任

Python双向循环链表实现方法分析

本文实例讲述了Python双向循环链表实现方法.分享给大家供大家参考,具体如下: 最近身边的朋友在研究用python来实现数据结构.遇到一个问题就是双向循环链表的实现,改指向的时候总是发蒙. 我自己尝实现了一个python的双向循环链表.附上代码,希望对大家有帮助. 如果不懂什么是双向循环链表的伙伴,需要补习一下数据结构的基础之后哦~~~ 在python当中 用一个类Node 来实现链表的节点,节点数据有三个变量: prev:前驱指针: 用于指向当前节点前一个节点 next: 后继指针  用于指

c++双向链表操作示例(创建双向链、双向链表中查找数据、插入数据等)

双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱.所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点.一般我们都构造双向循环链表. (1)定义双向链表的基本结构 复制代码 代码如下: typedef struct _DOUBLE_LINK_NODE  {      int data;      struct _DOUBLE_LINK_NODE* prev;      struct _DOUBLE_LINK_NODE* nex

约瑟夫经典问题扩展成双向约瑟夫问题

约瑟夫问题是一个经典的问题,我们不妨将这个经典问题进行扩展,变成一个双向的约瑟夫问题. 已知 n 个人(不妨分别以编号 1,2,3,...,n 代表 )围坐在一张圆桌周围,首先从编号为 k 的人从 1 开始顺时针报数,1, 2, 3, ...,记下顺时针数到 m 的那个人,同时从编号为 k 的人开始逆时针报数,1, 2, 3, ...,数到 m 后,两个人同时出列.然后从出列的下一个人又从 1 开始继续进行双向报数,数到 m 的那两个人同时出列,...:.依此重复下去,直到圆桌周围的人全部出列.

C#数据结构与算法揭秘三 链表

上文我们讨论了一种最简单的线性结构--顺序表,这节我们要讨论另一种线性结构--链表. 什么是链表了,不要求逻辑上相邻的数据元素在物理存储位置上也相邻存储的线性结构称之为链表.举个现实中的例子吧,假如一个公司召开了视频会议的吧,能在北京总公司人看到上海分公司的人,他们就好比是逻辑上相邻的数据元素,而物理上不相连.这样就好比是个链表. 链表分为①单链表,②单向循环链表,③双向链表,④双向循环链表. 介绍各种各样链表之前,我们要明白这样一个概念.什么是结点.在存储数据元素时,除了存储数据元素本身的信息