精华内容
下载资源
问答
  • 文章目录双链表的定义双链表上的操作初始化插入操作建立双链表头插法建立双链表尾插法建立双链表遍历操作求双链表的长度查找操作按值查找按位查找删除操作判空操作完整代码及实例总结 双链表的定义  为什么引入...

    双链表的定义

     为什么引入双链表?

     单链表的结点中只有一个指向其后继的指针,使得单链表要访问某个结点的前驱结点时,只能从头开始遍历,访问后驱结点的复杂度为O(1),访问前驱结点的复杂度为O(n)。为了克服上述缺点,引入了双链表。

     双链表的结点中有两个指针prior和next,分别指向前驱结点和后继结点。

     双链表中结点类型的描述:

    typedef struct DNode{
        int data;  //数据域
        struct DNode *prior,*next;  //前驱和后继指针
    }DNode, *DLinkList;
    

    双链表上的操作

    初始化

     双链表与单链表一样,为了操作方便也可以加入头结点,那么初始化双链表其实就是定义一个头结点,然后将指针域置空。

    在这里插入图片描述

    //初始化
    void InitList(DLinkList &L){
        L = (DNode *)malloc(sizeof(DLinkList));
        L->prior = NULL;
        L->next = NULL;
    }
    

    插入操作

      在双链表中p所指的结点之后插入结点*s,其指针的变化过程如下图所示:
    插入操作
     实现代码:

    //将x插入到双链表L中*p结点的下一个结点
    void Insert(DLinkList &L, DNode *p, int x){
        DNode *s = (DNode *)malloc(sizeof(DNode));
        s->data = x;
        s->next = p->next;  //1
        p->next->prior = s; //2
        s->prior = p;  //3
        p->next = s; //4
    }
    

     当然,插入操作的语句并不只有这一种顺序,但必须保证1和2两步必须在4步之前,否则*p的后继结点的指针就会丢掉,导致插入失败。


    建立双链表

    头插法建立双链表

     每次在头结点的后面插入新结点。

     实现代码:

    //头插法建立双链表
    DLinkList HeadInsert(DLinkList &L){
        InitList(L); //初始化
        int x;
        cin>>x;
        while(x!=9999){
            DNode *s = (DNode *)malloc(sizeof(DNode));
            s->data = x;
            if(L->next == NULL){
                s->next = NULL;
                s->prior = L;
                L->next = s;
            }else{
                s->next = L->next;
                L->next->prior = s;
                s->prior = L;
                L->next = s;
            }
            cin>>x;
        }
        return L;
    }
    

    尾插法建立双链表

     每次在双链表的尾部插入新结点,为此,应该声明一个尾指针r并始终指向尾结点。

     实现代码:

    //尾插法建立双链表
    DLinkList TailInsert(DLinkList &L){
        InitList(L);
        DNode *s,*r=L;
        int x;
        cin>>x;
        while(x!=9999){
            s = (DNode *)malloc(sizeof(DNode));
            s->data = x;
            s->next = NULL;
            s->prior = r;
            r->next = s;
            r = s;
            cin>>x;
        }
        return L;
    }
    

    遍历操作

     从单链表的第一个结点开始,依次遍历输出结点的数据直到最后一个结点。

     实现代码:

    //遍历操作
    void PrintList(DLinkList L){
        DNode *p = L->next;
        while(p){
            cout<<p->data<<" ";
            p = p->next;
        }
        cout<<endl;
    }
    

    求双链表的长度

     从双链表的第一个结点开始,依次遍历每个结点,并计数,直到最后一个结点为止。

     实现代码:

    //求双链表的长度
    int Length(DLinkList L){
        DNode *p = L->next;
        int len = 0;
        while(p){
            len++;
            p = p->next;
        }
        return len;
    }
    

    查找操作

    按值查找

     查找值x在L中的位置。与单链表的按值查找是一样的,不会用到前驱结点指针prior。

     实现代码:

    //按值查找:查找x在L中的位置
    DNode *LocateElem(DLinkList L, int x){
        DNode *p = L->next;
        while(p && p->data != x){
            p = p->next;
        }
        return p;
    }
    

    按位查找

     查找在双链表L中第 i 个位置的结点。与单链表的按位查找是一样的,不会用到前驱结点指针prior。

     实现代码:

    //按位查找:查找在双链表L中第i个位置的结点
    DNode *GetElem(DLinkList L, int i){
        int j=1;
        DNode *p = L->next;
        if(i==0)return L;
        if(i<1)return NULL;
        while(p && j<i){
            p = p->next;
            j++;
        }
        return p; //如果i大于表长,p=NULL,直接返回p即可
    }
    

    删除操作

    删除操作
     将双链表中的第 i 个结点删除。

     实现代码:

    //删除操作:将双链表中的第i个结点删除
    void Delete(DLinkList &L, int i){
        if(i<1 || i>Length(L)){
            cout<<"delete failed: index is wrong."<<endl;
            return;
        }
        DNode *p = GetElem(L,i-1);
        DNode *q = p->next;
        p->next = q->next; //1
        q->next->prior = p; //2
        free(q);
    }
    
    

    判空操作

     判断双链表是否为空。

     实现代码:

    //判空操作
    bool Empty(DLinkList L){
        if(L->next == NULL){
            cout<<"L is null"<<endl;
            return true;
        }else{
            cout<<"L is not null"<<endl;
            return false;
        }
    }
    

    完整代码及实例

     完整代码:

    #include<bits/stdc++.h>
    using namespace std;
    
    typedef struct DNode{
        int data;
        struct DNode *prior,*next;
    }DNode, *DLinkList;
    
    //初始化
    void InitList(DLinkList &L){
        L = (DNode *)malloc(sizeof(DLinkList));
        L->prior = NULL;
        L->next = NULL;
    }
    
    //遍历操作
    void PrintList(DLinkList L){
        DNode *p = L->next;
        while(p){
            cout<<p->data<<" ";
            p = p->next;
        }
        cout<<endl;
    }
    
    //求双链表的长度
    int Length(DLinkList L){
        DNode *p = L->next;
        int len = 0;
        while(p){
            len++;
            p = p->next;
        }
        return len;
    }
    
    //头插法建立双链表
    DLinkList HeadInsert(DLinkList &L){
        InitList(L); //初始化
        int x;
        cin>>x;
        while(x!=9999){
            DNode *s = (DNode *)malloc(sizeof(DNode));
            s->data = x;
            if(L->next == NULL){
                s->next = NULL;
                s->prior = L;
                L->next = s;
            }else{
                s->next = L->next;
                L->next->prior = s;
                s->prior = L;
                L->next = s;
            }
            cin>>x;
        }
        return L;
    }
    
    //尾插法建立双链表
    DLinkList TailInsert(DLinkList &L){
        InitList(L);
        DNode *s,*r=L;
        int x;
        cin>>x;
        while(x!=9999){
            s = (DNode *)malloc(sizeof(DNode));
            s->data = x;
            s->next = NULL;
            s->prior = r;
            r->next = s;
            r = s;
            cin>>x;
        }
        return L;
    }
    
    //按值查找:查找x在L中的位置
    DNode *LocateElem(DLinkList L, int x){
        DNode *p = L->next;
        while(p && p->data != x){
            p = p->next;
        }
        return p;
    }
    
    //按位查找:查找在双链表L中第i个位置的结点
    DNode *GetElem(DLinkList L, int i){
        int j=1;
        DNode *p = L->next;
        if(i==0)return L;
        if(i<1)return NULL;
        while(p && j<i){
            p = p->next;
            j++;
        }
        return p; //如果i大于表长,p=NULL,直接返回p即可
    }
    
    //将x插入到双链表L中*p结点的下一个结点
    void Insert(DLinkList &L, DNode *p, int x){
        DNode *s = (DNode *)malloc(sizeof(DNode));
        s->data = x;
        s->next = p->next;
        p->next->prior = s;
        s->prior = p;
        p->next = s;
    }
    
    //删除操作:将双链表中的第i个结点删除
    void Delete(DLinkList &L, int i){
        if(i<1 || i>Length(L)){
            cout<<"delete failed: index is wrong."<<endl;
            return;
        }
        DNode *p = GetElem(L,i-1);
        DNode *q = p->next;
        p->next = q->next;
        q->next->prior = p;
        free(q);
    }
    
    //判空操作
    bool Empty(DLinkList L){
        if(L->next == NULL){
            cout<<"L is null"<<endl;
            return true;
        }else{
            cout<<"L is not null"<<endl;
            return false;
        }
    }
    
    
    int main(){
        //尾插法建立双链表,并遍历单链表
        DLinkList L = TailInsert(L);
        cout<<"L: ";
        PrintList(L);
        
        DNode *p;
        //按值查找
        p = LocateElem(L,2);
        cout<<"值为2的结点的下一个结点值是:"<<p->next->data<<endl;
        cout<<"值为2的结点的上一个结点值是:"<<p->prior->data<<endl;
        //按位查找
        p = GetElem(L,3);
        cout<<"第三个结点值是:"<<p->data<<endl;
        
        //插入操作
        Insert(L,p,7);
        cout<<"在第三个结点后面插入值为7的结点后L: ";
        PrintList(L);
        
        //删除操作
        Delete(L, 5);
        cout<<"删除第五个结点后L: ";
        PrintList(L);
        
        //求表长
        cout<<"表长为:"<<Length(L)<<endl;;
        
        //判空
        Empty(L);
        return 0;
    }
    

     运行结果:

    在这里插入图片描述

    总结

     双链表与单链表在某些操作上几乎是相同的,比如按位查找,按值查找,求表长,打印链表等等,但由于双链表有指向前驱结点的指针,故双链表在初始化,建立双链表,插入操作,删除操作等函数内需要对前驱结点的指针进行修改。本文中插入和删除操作都是对结点*q的后面进行插入和删除,由于双链表有指向前驱结点的指针,故这些操作也可以转换为在某个结点前的插入删除操作等等。

    展开全文
  • 单向链表 package LinkedList; public class LinkedList { public static void main(String[] args) { HeroNode hero1 = new HeroNode(1, "艾希", "寒冰"); HeroNode hero2 = new HeroNode(2, "阿卡丽", "akl");...

    单向链表

    package LinkedList;
    
    public class LinkedList {
        public static void main(String[] args) {
            HeroNode hero1 = new HeroNode(1, "艾希", "寒冰");
            HeroNode hero2 = new HeroNode(2, "阿卡丽", "akl");
            HeroNode hero3 = new HeroNode(3, "嘉文", "皇子");
            HeroNode hero4 = new HeroNode(4, "卡兹克", "螳螂");
            HeroNode hero5 = new HeroNode(5, "陈泽", "秀的一批");
            HeroNode hero6 = new HeroNode(5, "泽哥", "铁头泽");
    
            SingleLinkedlist singleLinkedlist = new SingleLinkedlist();
    
            singleLinkedlist.add(hero4);
            singleLinkedlist.add(hero2);
            singleLinkedlist.add(hero5);
            singleLinkedlist.addByOder(hero1);
            singleLinkedlist.addByOder(hero3);
            singleLinkedlist.changeHero(hero6);
        }
    }
    
    //创建链表管理我们的英雄
    class SingleLinkedlist {
        //创建一个空的表头
        private HeroNode head = new HeroNode(0, "", "");
    
        //在链表的最后添加一个元素
        public void add(HeroNode newHero) {
            //我们需要创建一个临时变量帮助我们遍历整个链表,初始位置在链表头上
            HeroNode temp = head;
            //开始遍历
            while (true) {
                if (temp.next == null) {
                    break;
                }
                temp = temp.next;
            }
            temp.next = newHero;
            System.out.println("新英雄" + newHero.toString());
        }
    
        //在链表中添加一个元素
        public void addByOder(HeroNode newHero) {
            boolean flag = false;
            HeroNode temp = head;
            while (true) {
                if (temp.next == null) {
                    break;
                }
                if (temp.no == newHero.no) {
                    System.out.println("已经存在想要添加的英雄");
                    break;
                } else if (temp.next.no > newHero.no) {
                    flag = true;
                    break;
                }
                temp = temp.next;
            }
            if (flag) {
                newHero.next = temp.next;
                temp.next = newHero;
                System.out.println("已添加英雄:");
                System.out.println(newHero.toString());
            }
    
        }
    
        //在链表中删除一个元素
        public void delectLink(HeroNode newHero) {
            HeroNode temp = head;
            while (true) {
                if (temp.next == null) {
                    break;
                }
                if (temp.next.no == newHero.no) {
                    temp.next = temp.next.next;
                    System.out.println("已删除指定英雄");
                    break;
                } else {
                    System.out.println("没有找到指定英雄");
                }
                temp = temp.next;
            }
        }
    
        //改变一个英雄的属性     这里一定要注意    对于no的查找一定要放在前面  不然在链表最后添加英雄会失败
        public void changeHero(HeroNode newHero) {
            HeroNode temp = head;
            boolean flag = false;
            while (true) {
                if (temp.no == newHero.no) {
                    flag = true;
                    break;
                }
                if (temp.next == null) {
                    break;
                }
                temp = temp.next;
            }
            if (flag){
                temp.name = newHero.name;
                temp.nickedname = newHero.nickedname;
                System.out.println("已修改对应属性");
            }else{
                System.out.println("没有指定英雄");
            }
    
        }
    }
    
    class HeroNode {
        public int no;
        public String name;
        public String nickedname;
        public HeroNode next;
    
    
        public HeroNode(int no, String name, String nickedname) {
            this.name = name;
            this.nickedname = nickedname;
            this.no = no;
        }
    
        @Override
        public String toString() {
            return "HeroNode{" +
                    "no=" + no +
                    ", name='" + name + '\'' +
                    ", nickedname='" + nickedname + '\'' +
                    '}';
        }
    }
    

    双向链表

    package LinkedList;
    
    public class DoubleList {
        public static void main(String[] args) {
    
        }
    }
    
    class DoubleListDemo {
        private HeroNode2 head;
    
        //在最后添加英雄
        public void add(HeroNode2 newHero) {
            HeroNode2 temp = head;
            while (true) {
                //找到链表的最后
                if (temp.next == null) {
                    break;
                }
                temp = temp.next;
            }
            temp.next = newHero;
            newHero.pre = temp;
        }
    
        public void addMid(HeroNode2 newHero) {
            HeroNode2 temp = head;
            boolean flag = false;
            while (true) {
                if (temp.next == null) {
                    System.out.println("没有指定英雄");
                    break;
                }
                //temp遍历的英雄序号第一次大于newHero的序号时,就是所在点
                if (temp.next.no > newHero.no) {
                    flag = true;
                    break;
                }
                if (temp.no == newHero.no) {
                    System.out.println("已经存在这个英雄了!");
                    break;
                }
                temp = temp.next;
            }
            if (flag) {
                newHero.next = temp.next;
                temp.next = newHero;
                newHero.pre = temp;
                System.out.println("已加入对应英雄:");
                System.out.println(newHero.toString());
            }
        }
    
        public void delectHero(HeroNode2 newHero) {
            HeroNode2 temp = head;
            boolean flag = false;
            while (true) {
                if (temp.next == null) {
                    System.out.println("没有指定可以删除的英雄");
                    break;
                }
                if (temp.no == newHero.no) {
                    flag = true;
                    break;
                }
                temp = temp.next;
            }
            if (flag) {
                newHero.pre = temp.pre;
                newHero.next = temp.next;
                System.out.println("已添加删除对应的英雄" + newHero.toString());
            }
        }
    
        public void changeHeroMessage(HeroNode2 newHero){
            HeroNode2 temp = head;
            boolean flag = false;
            while (true) {
                if (temp.next == null) {
                    System.out.println("没有指定可以修改信息的英雄");
                    break;
                }
                if (temp.no == newHero.no) {
                    flag = true;
                    break;
                }
                temp = temp.next;
            }
            if (flag) {
                newHero.name = temp.name;
                newHero.nickname = temp.nickname;
                System.out.println("已修改对应的英雄" + newHero.toString());
            }
        }
    }
    
    class HeroNode2 {
        public int no;
        public String name;
        public String nickname;
        public HeroNode2 pre;
        public HeroNode2 next;
    
        public HeroNode2(int no, String name, String nickname) {
            this.no = no;
            this.name = name;
            this.nickname = nickname;
        }
    
        @Override
        public String toString() {
            return "HeroNode2{" +
                    "no=" + no +
                    ", name='" + name + '\'' +
                    ", nickname='" + nickname + '\'' +
                    '}';
        }
    }
    
    展开全文
  • 单链表和双链表上的基本操作

    千次阅读 2010-05-03 19:13:00
    1.程序清单 单链表建表(create)删除(delete)插入(insert)双链表建表(create)删除(delete)插入(insert)查找(search)2.程序 //by gigglesun 2010-5-3 #include #include #define FALSE 0 #defi

    1.程序清单

     

    单链表

    1. 建表(create)
    2. 删除(delete)
    3. 插入(insert)

    双链表

    1. 建表(create)
    2. 删除(delete)
    3. 插入(insert)
    4. 查找(search)

    2.程序

     

    3.结果

    operation on link list

     

     

     


    附注

    1.单链表的查找和双链表的创建参考了ReeK著的《C和指针》中文版第12章的部分内容

    展开全文
  • 双链表操作

    2018-09-24 09:35:17
    双链表操作: 建表,查找,插入,删除 建立双链表(尾插) 分配结点空间 确定链表是空表:前驱后继为空 创立新结点,并且赋值新结点值域 确立新结点在链表里的关系: 终端结点 -&gt;next = 新结点; 新结点-&...

    双链表操作: 建表,查找,插入,删除

    建立双链表(尾插)

    1. 分配结点空间
    2. 确定链表是空表:前驱后继为空
    3. 创立新结点,并且赋值新结点值域
    4. 确立新结点在链表里的关系:

      终端结点 ->next = 新结点;
      新结点->prior = 终端结点 ;

    查找结点

    插入结点

     已知点 -> next = 新结点 -> next;
     已知点 -> prior = 新结点;
     新结点 ->next = 已知点;
    

    删除

    展开全文
  • 双向链表

    2019-07-13 20:55:00
    建表 typedef struct Dnode { int data; Dnode *prior; Dnode *next; }*Dlink; Dlink p,q,s,H; void D_init(Dlink &L) { L = new Dnode; L->next = L; L->p...
  • 文章目录数据结构与算法——双链表学习思路双链表的基本结构双链表的基本操作定义双链表——C++版插入结点在某个结点后...双链表的进阶操作输出销毁头插法建表尾插法建表删除第i个元素在第i个元素后插入值为value的元素...
  • 本程序实现了单链表和双向链表的一些基本操作,包括建表,插入,删除等,对学习数据结构的人会有帮助!!!
  • 双链表的实现

    2014-11-12 00:29:01
    双链表数据结构为: typedef struct DNode{ ElemType data; //节点数据 struct DNode* prior; //指向前一节点指针 struct DNode* next; //指向后一节点指针 }DLinkList; 实现下列函数: void Create
  • //正位序输入n个元素的值,建立带表头结点的双向链表L L=new DuLNode; L->next=NULL; L->prior=NULL; DuLNode *p; DuLNode *r=L;//尾指针r指向头结点 for(int i=0;i;++i){ p=new DuLNode;//生成新...
  • C++双向链表实现

    2017-01-17 18:29:16
    纯属无聊,自己实现了一下双向链表,主要操作有头插法尾插法建表,从前往后和从后往前遍历,其他的功能暂时没有实现,因为只是无聊,但是唯一的收获就是:真的理解了头结点(尾节点)的重要性和便捷性,最初是从大话...
  • 双链表的基本操作

    2019-02-18 22:37:57
    首先,双链表的结构声明如下:一个前驱节点的指针,一个后继节点的指针和数据域。 typedef struct node{ int data; struct node *prior; //前驱节点 struct node *next; //后继节点 }Dlinklist; 1.头插法...
  • 实验题3:实现双链表的各种基本运算 编写一个程序DBLinklist.h和DBlinklist.cpp,实现单链表的各种基本运算和整体建表算法(元素类型ElemType为char)。在此基础上面设计一个exp2-3.cpp完成下面的功能。 初始化双链表...
  • (新手向)双向链表的c语言实现

    万次阅读 2019-09-22 23:12:30
    双向链表的c语言实现 概述 链表是很多数据结构的基础,它本身也是一种基本数据结构(线性表)...建表 首先,建立节点与链表的结构体 struct ListNode {//节点 int data;//数据 ListNode* Next;//指向前一个...
  • 文章目录一、线性表的顺序存储顺序存储结构的定义1、线性表的查找2、线性表的插入3、线性表的删除4、顺序表的合并二、线性表的链式存储单链表存储结构声明1、链表的初始化2、头插法建表3、尾插法建表4、按序号查找...
  • 最近最少使用淘汰机制, 访问一个key在map中,也就是 在内存中, 就将此页放到建表头部, , 不在内存中, (假如规定链表只能有三个节点, 当访问第四个时, 如果值不在内存中, 那就释放链表最尾部的节点, 然后将此值包装成...
  • 双向链表初级版本

    2010-10-26 17:04:02
    #include <stdio.h> #include <conio.h> typedef struct DuLNode { int element; struct DuLNode *prior; struct DuLNode *next; }DuLNode; DuLNode *Init_List(void); //建表 in...
  • 要求: 建立一个空表。 在第i个位置插入新的元素x。 删除第i个位置上的元素。 取第i个位置上的元素。 ...1.建表 2.插入 3.删除 4.就地逆置 节点类: package keshe; public class DuLNode...
  • Mysql-innodb-B+索引(本篇)Mysql-innodb-锁(预计20200523)Mysql-innodb-事务预计20200530)概述下面是常见的建表语句: 其中的Key和PRIMARY就是 B+树索引,即常用的索引,大概率是B+树索引注:mysql还有全文索引和...
  • 链表

    2015-05-16 23:28:45
    2、单链表的建立:顺序建表(尾插法)、逆序建表(头插法)。单链表插入、删除操作需要寻找前驱结点。 3、双向链表和单向链表相比,多了一个前驱指针,单向链表在删除结点时候要遍历链表,双向链表在删除不需要遍历...
  • 链表笔试题

    2017-11-13 22:47:00
    2、单链表的建立:顺序建表(尾插法)、逆序建表(头插法)。单链表插入、删除操作需要寻找前驱结点。 3、双向链表和单向链表相比,多了一个前驱指针,单向链表在删除结点时候要遍历链表,双向链表在删除不需要遍历...
  • 链表面试题——C

    2017-09-02 12:07:47
    2、单链表的建立:顺序建表(尾插法)、逆序建表(头插法)。单链表插入、删除操作需要寻找前驱结点。 3、双向链表和单向链表相比,多了一个前驱指针,单向链表在删除结点时候要遍历链表,双向链表在删除不需要...
  • 数据结构之链表

    2017-09-09 12:34:14
    链表作者:Tinuv 时间:2017.9.02 单链表 单链表的创建 头插法创建单链表 ...单链表单链表的创建头插法建表#include #include <malloc.h>typedef struct node { int data; struct node *next; } linklist; int
  • 单向链表的构造

    2017-07-28 08:26:12
    链表的个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。 链表包括单向链表(也就是今天要写的),双向...今天写的代码是按从小到大顺序建表的; 比如输入:5,2,6,4,3;

空空如也

空空如也

1 2
收藏数 39
精华内容 15
关键字:

双链表建表