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 = p->prior;
p->prior->next = s;
p->prior = s;

删除操作

删除结点p。p->next->prior 指向 p->prior，p->prior->next 指向 p->next 。最后将p结点delete。

p->prior->next = p->next;
p->next->prior = p->prior;
delete p;

实例操作

（附截图）

注意：因为函数没有返回Node*类型，所以这里对指针进行引用，否则在退出函数的时候，并没有保存改变。如果需要删除全部链表，需要保存InitList之后的head地址，否则会遗漏一个Node结点没有删除。

代码实现：

#include<iostream>
#include<cstddef>
#include<cstdio>
using namespace std;

const int OK = 1;
const int ERROR = 0;
const int LETTERNUM = 26;
typedef char ElemType;

struct Node{
  ElemType data;
  Node * prior;//前驱结点
  Node * next;//后驱结点
};

int InitList(Node *&L){
  Node *p,*q;
  int i;

  L = new Node; //头结点
  L->next = L->prior = NULL;
  p = L; //p是当前指针

  for(int i=0;i<LETTERNUM;i++){
    q = new Node; //q是临时指针
    q->data = 'A' + i;
    q->prior = p;
    q->next = p->next;
    p->next = q;
    p = q;//指针移动
  }
  p->next = L->next; //尾结点指向head->next(第一个有字母的地址)
  L->next->prior = p;

  return OK;
}

void Change(Node *&L,int i){ //移动头指针
  if (i>0){
    while(i--){
      L = L->next;
    }
  }
  else if (i<0){
    L = L->next ;
    while(i++){
      L = L->prior;
    }
  }
  else{
    L = L->next;
  }
}

int main(){
  Node *head = NULL;
  int i,n;
  InitList(head);
  //Node *s_head = head; // 保存头结点之后删除
  cout<<"输入位置："<<endl;
  cin>>n;
  Change(head,n);

  for(i = 0;i<LETTERNUM;++i){
    head = head->next;
    cout<<head->data<<" ";
  }

  cout<<endl;
  return 0;
}

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

赞 (0)

相关推荐

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

    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

  • C#如何自定义线性节点链表集合

    C#如何自定义线性节点链表集合

    本例子实现了如何自定义线性节点集合,具体代码如下: using System; using System.Collections; using System.Collections.Generic; namespace LineNodeDemo { class Program { static void Main(string[] args) { LineNodeCollection lineNodes = new LineNodeCollection(); lineNodes.Add(new

  • 面试题快慢链表和快慢指针

    腾讯的一道面试题:如何快速找到位置长度单链表的中间节点?普通方法,就是先遍历,在从头找到2/length的中间节点.算法复杂度是:O(3*n/2).而更快的方法就是利用快慢指针的原理. 快慢链表:利用标尺的思想,设置两个指针(一快一慢)*serach和*mid,刚开始都指向单链表的头结点.但是*search指针的移动速度是*mid的两倍.当*search到尾结点的时候,mid刚好到了中间.算法复杂度是:O(n/2) int GetMidNode(LinkList *L,int elem){ Li

  • C++ 实现双向链表的实例

    双向链表C++ 的实现 本文是通过C++ 的知识实现数据结构中的双向链表,这里不多说 了,代码注释很清楚, 实现代码: //double LinkList implement with C++ template #include<iostream> using namespace std; /*template<typename Type> class DBListADT { public: virtual void Append(const Type &)=0; virt

  • C语言 数据结构链表的实例（十九种操作）

    C语言 数据结构链表的实例(十九种操作) #include <stdio.h> #include <string.h> #include <stdlib.h> /*************************************************************************************/ /* 第一版博主 原文地址 http://www.cnblogs.com/renyuan/archive/2013/05/21/30915

  • C语言数据结构实现链表去重的实例

    C语言数据结构实现链表去重的实例 题目及分析 链表去重 时间限制 300 ms 内存限制 65536 kB 代码长度限制 8000 B 判题程序 Standard 给定一个带整数键值的单链表L,本题要求你编写程序,删除那些键值的绝对值有重复的结点.即对任意键值K,只有键值或其绝对值等于K的第一个结点可以被保留.同时,所有被删除的结点必须被保存在另外一个链表中.例如:另L为21→-15→-15→-7→15,则你必须输出去重后的链表21→-15→-7.以及被删除的链表-15→15. 输入格式: 输入

  • C++ 中循环链表和约瑟夫环

    循环链表和约瑟夫环 循环链表的实现 单链表只有向后结点,当单链表的尾链表不指向NULL,而是指向头结点时候,形成了一个环,成为单循环链表,简称循环链表.当它是空表,向后结点就只想了自己,这也是它与单链表的主要差异,判断node->next是否等于head. 代码实现分为四部分: 初始化 插入 删除 定位寻找 代码实现: void ListInit(Node *pNode){ int item; Node *temp,*target; cout<<"输入0完成初始化"&

  • C语言之复杂链表的复制详解

    C语言之复杂链表的复制详解

    什么是复杂链表? 复杂链表指的是一个链表有若干个结点,每个结点有一个数据域用于存放数据,还有两个指针域,其中一个指向下一个节点,还有一个随机指向当前复杂链表中的任意一个节点或者是一个空结点.今天我们要实现的就是对这样一个复杂链表复制产生一个新的复杂链表. 复杂链表的数据结构如下: typedef int DataType; //数据域的类型 //复杂链表的数据结构 typedef struct ComplexNode { DataType _data ; // 数据 struct Complex

  • C++ 实现静态链表的简单实例

    C++ 实现静态链表的简单实例

    C++ 实现静态链表的简单实例 用数组描述的链表,即称为静态链表. 在C语言中,静态链表的表现形式即为结构体数组,结构体变量包括数据域data和游标cur. 这种存储结构,仍需要预先分配一个较大的空间,但在作为线性表的插入和删除操作时不需移动元素,仅需修改指针,故仍具有链式存储结构的主要优点. 下图表示了静态链表的一中存储结构: 图中用彩色途上的是两个头结点,不存放数据,分别用来记录第一个备用节点和第一个数据节点的下标. 下面给出静态链表的C++实现代码: 首先给出头文件:StaticList.

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

    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 =

  • Kotlin 语言中调用 JavaScript 方法实例详解

    Kotlin 语言中调用 JavaScript 方法实例详解 Kotlin 已被设计为能够与 Java 平台轻松互操作.它将 Java 类视为 Kotlin 类,并且 Java 也将 Kotlin 类视为 Java 类.但是,JavaScript 是一种动态类型语言,这意味着它不会在编译期检查类型.你可以通过动态类型在 Kotlin 中自由地与 JavaScript 交流,但是如果你想要 Kotlin 类型系统的全部威力 ,你可以为 JavaScript 库创建 Kotlin 头文件. 内联 J

  • C语言中联合体union的实例详解

     C语言中联合体union的实例详解 1.定义: union(int i, short s, char c) un; un.i = 3; printf("i=%d",un.i); printf("length = %d\n",sizeof(un);//==4,有最大的变量来决定 2.相当与java里的List T类型 3.数据交换 void swap(int *p , int *q){ int temp = *p; *p = *q; *q = temp; } 4.打

  • C语言中二级指针的实例详解

    C语言中二级指针的实例详解

    C语言中二级指针的实例详解 用图说明 示例代码: #include <stdio.h> int main(int argc, const char * argv[]) { // int a = 5; int *p1 = &a; //-打印地址-----地址相同--------------- printf("&a = %p\n", &a);// printf("p1 = %p\n", p1);// int **p2 = &p

  • C语言中调用Swift函数实例详解

    C语言中调用Swift函数实例详解 在Apple官方的<Using Swift with Cocoa and Objectgive-C>一书中详细地介绍了如何在Objective-C中使用Swift的类以及如何在Swift中使用Objective-C中的类.在后半部分也介绍了如何在Swift中使用C函数,不过对于如何在C语言中使用Swift函数却只字未提.这里我就为大家分享一下如何在C语言中调用Swift函数. 我们首先要知道的是,所有Swift函数都属于闭包.其次,Swift函数的调用约定与

  • C语言中强制地址跳转详解

    C语言中强制地址跳转详解 #define jump(TargetAddr ) (*((void(*)())(TargetAddr))() 第一个(( void( * )(  )) ,意思为强制类型转换为一个无形参,无返回值的函数指针,(*(TargetAddr))为跳转地址,但是函数指针变量不能为常数所以要加((void( * )(  )) 进行强制类型转换.最后一个()为执行的意思. 整一条指定的目的是为了跳转到一个绝对地址执行函数. 1.在单片机中可以实现软件复位,比如跳转到0地址. 2.如

  • Java语言中的内存泄露代码详解

    Java语言中的内存泄露代码详解

    Java的一个重要特性就是通过垃圾收集器(GC)自动管理内存的回收,而不需要程序员自己来释放内存.理论上Java中所有不会再被利用的对象所占用的内存,都可以被GC回收,但是Java也存在内存泄露,但它的表现与C++不同. JAVA中的内存管理 要了解Java中的内存泄露,首先就得知道Java中的内存是如何管理的. 在Java程序中,我们通常使用new为对象分配内存,而这些内存空间都在堆(Heap)上. 下面看一个示例: public class Simple { public static vo

  • C语言中的正则表达式使用示例详解

    正则表达式,又称正规表示法.常规表示法(英语:Regular Expression,在代码中常简写为regex.regexp或RE).正则表达式是使用单个字符串来描述.匹配一系列符合某个句法规则的字符串. 在c语言中,用regcomp.regexec.regfree 和regerror处理正则表达式.处理正则表达式分三步: 编译正则表达式,regcomp: 匹配正则表达式,regexec: 释放正则表达式,regfree. 函数原型 /* 函数说明:Regcomp将正则表达式字符串regex编译

  • C语言中指针和数组试题详解分析

    C语言中指针和数组试题详解分析

    目录 数组题: 程序一(一维数组): 字符数组 程序二(字符数组): 程序三(字符数组): 程序四(字符数组): 程序五(字符数组): 二维数组 程序六( 二维数组): 指针题 程序七( 指针): 程序八( 指针): 程序九( 指针): 程序十( 指针): 程序十( 图): 程序十一( 指针): 程序十二( 指针): 程序十三( 指针): 指针 和 数组 试题解析 小编,在这里想说一下,c语言的最后一节 C预处理,可能还需要一些时间,因为小编,昨天才下载了虚拟机 和 linux 系统,还没开始安

  • C语言中递归和排列组合详解

    目录 排列组合三大问题: 1.打印n个数的全排列 2.打印n个数中任意m个数的全排列 3.打印n个数中任意m个数的组合 完整代码如下: 总结 排列组合三大问题: 1.打印n个数的全排列2.打印n个数中任意m个数的全排列3.打印n个数中任意m个数的组合 1.打印n个数的全排列 这个题实际上是可以直接用STL中的next_permutation()函数,代码如下: #include<bits/stdc++.h> using namespace std; int main(){ int data[4

随机推荐