精华内容
下载资源
问答
  • 2.用双向链表数据结构,编写一个通信录管理系统。本系统应完成以下几方面的功能。 输入信息——enter(); 显示信息——display(); 查找以姓名作为关键字——search(); 删除信息——delete(); 存盘——...
  • 简单明了的C语言代码 可以在vc2005上编译的
  • 双向链表学生管理系统?怎么实现??跪求,各位大神指点迷津,谢谢
  • 单链表、双向链表、循环链表

    千次阅读 多人点赞 2019-07-26 14:26:09
    学习三种常见的链表结构,他们分别是:单链表、双向链表和循环链表。 单链表 单链表有两个较特殊节点,头结点和尾节点。头结点用来记录链表的基地址,可以用来遍历整条链表。尾结点的指针不是指向下一个节点而是指向...

    常见链表

    学习三种常见的链表结构,他们分别是:单链表、双向链表和循环链表。

    单链表

    单链表有两个较特殊节点,头结点尾节点。头结点用来记录链表的基地址,可以用来遍历整条链表。尾结点的指针不是指向下一个节点而是指向一个空地址NULL,表示链表上的最后一个节点。

    和数组一样,链表也支持数据的查找、插入和删除操作。但相对于数据的插入删除需要做大量的搬移操作,链表的插入,删除的时间复杂度为O(1)。但是链表想要随机访问第k个元素,就没有数组高效,随机访问数据的时间复杂度为O(n)。单向链表的简单实现代码如下:

    link_list.h

    /*
     *****************************************************************************
     *
     * File:       linke_list.h
     *
     * Description: Single link list header file
     *
     *
     * History:
     *    Created:  Apri, 2019
     *
     * Copyright (c) 2019 
     * All rights reserved.
     *
     ****************************************************************************/
     #ifndef LINK_LIST_
     #define LINK_LIST_
     
     
     typedef struct _node{
    	 struct _node *next;
    	 int date;
     }node, *list;
    
    list init_single_link_list();
    int insert_to_link_list_head(list list, int date);
    int insert_to_link_list_tail(list list, int date);
    void show_single_link_list (list head);
    void delete_from_link_tail(list list_);
    #endif
    

    link_list.c

    /*
     *****************************************************************************
     *
     * File:        link_list.c
     *
     * Description: Single link list file
     *
     *
     * History:
     *    Created:  Apri, 2019
     *
     * Copyright (c) 2019 
     * All rights reserved.
     *
     ****************************************************************************/
    #include <stdio.h>
    #include <stdlib.h>
    #include "link_list.h"
    
     
    list init_single_link_list()
    {
    	list link_list = NULL;
    	
    	link_list = (list)malloc(sizeof(list));
    	if(NULL == link_list){
    		printf("malloc failed !!\n");
    		exit(1);
    	}
    	link_list->next = NULL;
    	return link_list;
    }
    
    /*
      insert a node to single link list
      头插法
    */
    int insert_to_link_list_head(list list_, int date)
    {
    	list p = NULL;
            
            if (NULL == list_) {
               printf("list is NULL ...\n");
               exit(1);
            }	
    	p = (list)malloc(sizeof(list));
    	if(p == NULL) {
    		printf("malloc failed \n");
    		exit(1);
    	}
    	p->date = date;
    	
    	p->next = list_->next;
    	list_->next = p;
    	
    	return 1;
    }
    /*
     * 尾插法实现
    */
    int insert_to_link_list_tail(list list_, int date)
    {
    	list p = NULL;
            
            if (NULL == list_) {
                printf("list is NULL ...\n");
                exit(1);
            }
    	p = (list)malloc(sizeof(list));
    	if(NULL == p) {
    		printf("malloc fialed !\n");
    		exit(1);
    	}
    	while(list_->next) {
                       
                list_ = list_->next;    
            } 
            p->date = date;
            list_->next = p;
            p->next = NULL; 
    	
    	return 1;
    	
    }
    
    void show_single_link_list (list head)
    {
    	if (NULL == head) {
    		printf(" list is null ...\n");
    		return;
    	}
    	head = head->next;
    	while(head) {
    		printf("date ---- > %d \n", head->date);
    		head = head->next;
    	}
    	
    	return;
    }
    /*
     * delete element from tail of link list
     * */
    void delete_from_link_tail(list list_)
    {
        if(NULL == list_) {
            printf("list is NULL ...\n");
            exit(1);
        }
        if(list_->next == NULL) {
            free(list_);
            list_ = NULL;
        }
        while(list_->next->next) {
            list_ = list_->next;
        }
        free(list_->next);
        list_->next= NULL;
        
        return ;
    }
    /*
     * delete from link head
     * */
    void delete_from_link_head(list list_)
    {   
        list p = NULL;
        if(NULL == list_) {
            printf("link is NULL ...\n");
            exit(1);
        }
        
        if(list_->next) {
            p = list_->next;
            list_->next = p->next;
            free(p);
        }
        return;
    }
    /*
     * get link list size
     * 
     * */
    int get_link_size(list list_)
    {
        int size = 0;
        if(NULL == list_) {
            printf("link is NULL ...\n");
            exit(1);
        }
        while(list_->next) {
            ++size;
            list_ = list_->next;
        }
        return size;
    }
    void delete_specific_date(list list_, int date)
    {
        list p = NULL;
        int size = 0;
        if(NULL == list_) {
            printf("list is NULL ...\n");
            exit(1);
        }
        size = get_link_size(list_);
        if (size <= 0) {
            printf("link hasn't element ...\n");
            exit(1);
        }
        p = list_->next;
        while(p->date != date) {
            p = list_->next;
        }
      
       list_->next = p;
       free(list_);
        
        return;
    }
    int main()
    {
    	list head = NULL;
    	int i;
    	
    	head = init_single_link_list();
    #if 0
    	for (i = 0; i < 2; i++) {
    		
               //insert_to_link_list_head(head, i);
               insert_to_link_list_tail(head, i);
    	}
    #endif
    	show_single_link_list(head);
            printf("list size is %d\n", get_link_size(head));
            //delete_from_link_tail(head);
            //delete_from_link_head(head);
            delete_specific_date(head, 0);
            show_single_link_list(head);	
    }
    
    
    

    双向链表

    双向链表支持两个方向,每个节点有一个后继指针next指向后面的节点,还有一个前驱指针指向前面的节点。
    在这里插入图片描述
    双向链表简单实现:
    double_linklist.h

    #ifndef DOUBLE_LINKLIST_
    #define DOUBLE_LINKLIST_
    
    #include "stdbool.h"
    typedef int ElementType;
    typedef struct _double_link {
        ElementType date;
        struct _double_link *next;
        struct _double_link *pre;     
    }double_linklist;
    
    double_linklist *init_double_linklist();
    bool insert_linklist_head(double_linklist* d_linklist, ElementType date);
    ElementType delete(double_linklist* d_linklist);
    void display(double_linklist* d_linklist);
    bool isEmpty(double_linklist* d_linklist);
    
    #endif
    

    double_linklist.c

    #include <stdio.h>
    #include <stdlib.h>
    #include "double_linklist.h"
    
    /*
    @func :创建头结点和尾结点,新增的节点插入头结点和尾结点之间
    */
    double_linklist *init_double_linklist()
    {
        double_linklist *head = (double_linklist *)malloc(sizeof(double_linklist));
        if (!head) {
            perror("malloc failed.");
            exit(1);
        }
        head->next = NULL;
        head->pre = NULL;
        double_linklist *pNew = (double_linklist *)malloc(sizeof(double_linklist));
        if (!pNew) {
            perror("malloc failed.");
            exit(1);
        }
        pNew->next = NULL;
        pNew->pre = head;
        head->next = pNew;
        
        return head;
    }
    /*
    @func: 头插法,新增的节点插入头结点后面
    */
    bool insert_linklist_head(double_linklist* head, ElementType date)
    {
        if (!head) {
            perror("d_linklist is NULL");
            exit(1);
        }
        double_linklist* pNew = (double_linklist *)malloc(sizeof(double_linklist));
        if (!pNew) {
            perror("malloc failed.");
            exit(1);
        }
        pNew->date = date;
        /*先确定新增节点的前后指针指向*/
        pNew->pre = head;
        pNew->next = head->next;
        head->next->pre = pNew;
        head->next = pNew;
        
        printf("insert %d\n", head->next->date);
        return true;
    }
    bool isEmpty(double_linklist* head)
    {
        if (!head) {
            perror("d_linklist is NULL.");
            exit(1);
        }
        if (head->next->next == NULL && head->next->pre == head)
            return true;
        else
            return false;
    }
    /*
    @func: 删除一个节点
    */
    ElementType delete(double_linklist* head)
    {
        if (!head) {
            perror("d_linklist is NULL.");
            exit(1);
        }
        if (isEmpty(head)) {
            printf("double linklist is empty.\n");
            exit(1);
        }
        double_linklist* pDel = head->next;
        ElementType val = pDel->date;
        
        pDel->next->pre = head;
        head->next = pDel->next;
        if (pDel) {
            free(pDel);
            pDel = NULL;
        }
        return val;
    }
    
    void display(double_linklist* head)
    {
        if (!head) {
            perror("d_linklist is NULL.\n");
            exit(1);
        }
        if (isEmpty(head)) {
            printf("double linklist is empty.\n");
            exit(1);
        }
        double_linklist* tmp = head->next;
        while (tmp->next != NULL) {
            printf("val ---> %d\n", tmp->date);
            tmp = tmp->next;
        }
    }
    int main()
    {
        double_linklist* d_link = init_double_linklist();
        insert_linklist_head(d_link, 20);
        insert_linklist_head(d_link, 10);
        printf("delete val is %d .\n", delete(d_link));
        printf("delete val is %d .\n", delete(d_link));
        display(d_link);
        
    }
    

    循环链表

    单向循环链表

    和单链表相比,循环链表的优点是从链尾到链头特别容易,适合处理具有环形结构特点的数据,如著名的约瑟夫问题。循环链表的简单实现如下:
    robin_linklist.h

    #ifndef ROBIN_LINKLIST_
    #define ROBIN_LINKLIST_
    
    #include "stdbool.h"
    typedef int ElementType;
    typedef struct _node {
        ElementType date;
        struct _node* next;
    }robin_linklist;
    
    robin_linklist* init_robin_linklist();
    bool insert_to_robin_linklist(robin_linklist* link, ElementType date);
    bool delete_from_robin_linklist(robin_linklist* link);
    void display_robin_linklist(robin_linklist* link);
    #endif
    

    robin_linklist.c

    #include <stdio.h>
    #include <stdlib.h>
    #include "robin_linklist.h"
    
    robin_linklist* init_robin_linklist()
    {
        robin_linklist *head = (robin_linklist *)malloc(sizeof(robin_linklist));
        if (!head) {
            perror("malloc failed.");
            exit(1);
        }
        /*next指针指向自己*/
        head->next = head;
        robin_linklist *node = (robin_linklist *)malloc(sizeof(robin_linklist));
        if (!node) {
            perror("malloc failed.");
            exit(1);
        }
        node->next = head;
        head->next = node;
        return head;
    }
    /*
    @func : insert a element to linklist
    */
    bool insert_to_robin_linklist(robin_linklist* link, ElementType date)
    {
        if (!link) {
            perror("link is NULL.");
            exit(1);
        }
        robin_linklist* node = (robin_linklist *)malloc(sizeof(robin_linklist));
        if (!node) {
            perror("malloc failed.");
            exit(1);
        }
        node->date = date;
        node->next = link->next;
        link->next = node;
        
        return true;  
    }
    /*
    @func : delete a element from linklist
    */
    bool delete_from_robin_linklist(robin_linklist* link)
    {
        if (!link) {
            perror("link is NULL.");
            exit(1);
        }
        if (link->next->next != link) {
            robin_linklist *tmp = link->next;
            link->next = tmp->next;
            return true;
        }else {
            printf("link is empty.\n");
            return false;
        }
    }
    void display_robin_linklist(robin_linklist* link)
    {
        if (!link) {
            perror("link is NULL.");
            exit(1);
        }
        robin_linklist *tmp = link->next;
        while(link != tmp->next) {
          printf("val ---> %d\n", tmp->date);
          tmp = tmp->next;
        }
    }
    int main()
    {
        /*test code*/
        robin_linklist *ro_linklist = init_robin_linklist();
        insert_to_robin_linklist(ro_linklist, 10);
        display_robin_linklist(ro_linklist);
        delete_from_robin_linklist(ro_linklist);
        display_robin_linklist(ro_linklist);
        delete_from_robin_linklist(ro_linklist);
          
    }
    
    

    双向循环链表

    在这里插入图片描述
    双向链表的简单实现:
    double_robin_linklist.h

    #ifndef DOUBLE_ROBIN_LINKLIST_
    #define DOUBLE_ROBIN_LINKLIST_
    
    #include "stdbool.h"
    
    typedef int ElementType;
    typedef struct _double_robin_link {
        ElementType date;
        struct _double_robin_link *next;
        struct _double_robin_link *pre;
    }dou_robin_link;
    
    dou_robin_link* init_double_robin_linklist();
    bool insert_head(dou_robin_link * link, ElementType date);
    ElementType delete(dou_robin_link* link);
    bool isEmpty(dou_robin_link* link);
    void display(dou_robin_link* link);
    
    #endif
    

    double_robin_linklist.c

    #include <stdio.h>
    #include <stdlib.h>
    #include "double_robin_linklist.h"
    
    
    dou_robin_link * init_double_robin_linklist()
    {
        dou_robin_link* head = (dou_robin_link *)malloc(sizeof(dou_robin_link));
        if (!head) {
            perror("malloc failed.");
            exit(1);
        }
        head->next = head;
        head->pre = head;
        
        /*创建尾节点*/
        dou_robin_link *tail = (dou_robin_link *)malloc(sizeof(dou_robin_link));
        if (!tail) {
            perror("malloc failed.");
            exit(1);
        }
        tail->pre = head;
        tail->next = head;
        head->next = tail;
        
        return head;
    }
    bool isEmpty(dou_robin_link* link)
    {
        if (!link) {
            perror("link is NULL.");
            exit(1);
        }
        if (link->next->next == link && link->next->pre == link) {
            
            printf("double robin linklist is empty.\n");
            return true;
        }
        else {
            return false;
        }
    }
    /*
    @func: 头插法
    */
    bool insert_head(dou_robin_link * link, ElementType date)
    {
        if (!link) {
            perror("link is NULL.");
            exit(1);
        }
        dou_robin_link *pNew = (dou_robin_link *)malloc(sizeof(dou_robin_link));
        if (!pNew) {
            perror("malloc is NULL.");
            exit(1);
        }
        pNew->date = date;
        pNew->next = link->next;
        pNew->pre = link;
        
        link->next = pNew;
        link->next->next->pre = pNew;
        printf("insert -->%d\n", link->next->date);
        
        return true;
    }
    /*
    @func: 头删法
    */
    ElementType delete(dou_robin_link* link)
    {
        if (!link) {
            perror("link is NULL.");
            exit(1);
        }
        if (isEmpty(link)) {
            exit(1);
        }
        dou_robin_link *pDel = link->next;
        ElementType val = pDel->date;
        link->next = pDel->next;
        pDel->next->pre = link;
        
        printf("delete ---> %d\n", val);
        if(pDel) {
            free(pDel);
            pDel = NULL;
        }
        return val;
    }
    
    void display(dou_robin_link* link)
    {
        if(!link) {
            perror("link is NULL.");
            exit(1);
        }
        if(isEmpty(link)) {
            exit(1);
        }
        dou_robin_link* tmp = link->next;
        while (tmp->next != link && tmp->next->pre != link) {
            printf("val ---> %d\n", tmp->date);
            tmp = tmp->next;
        }
    }
    int main()
    {
        dou_robin_link *head = init_double_robin_linklist();
        insert_head(head, 10);
        insert_head(head, 20);
        delete(head);
        display(head);
    }
    
    展开全文
  • 详解双向链表的基本操作(C语言)

    万次阅读 多人点赞 2020-04-06 22:06:19
    学习之前先对单向链表和双向链表个回顾。 单向链表特点:   1.我们可以轻松的到达下一个节点, 但是回到前一个节点是很难的.   2.只能从头遍历到尾或者从尾遍历到头(一般从头到尾) 双向链表特点   1.每次在...

    工科生一枚,热衷于底层技术开发,有强烈的好奇心,感兴趣内容包括单片机,嵌入式Linux,Uboot等,欢迎学习交流!
    爱好跑步,打篮球,睡觉。
    欢迎加我QQ1500836631(备注CSDN),一起学习交流问题,分享各种学习资料,电子书籍,学习视频等。

    1.双向链表的定义

    上一节学习了单向链表单链表详解。今天学习双链表。学习之前先对单向链表和双向链表做个回顾。
    单向链表特点
      1.我们可以轻松的到达下一个节点, 但是回到前一个节点是很难的.
      2.只能从头遍历到尾或者从尾遍历到头(一般从头到尾)
    双向链表特点
      1.每次在插入或删除某个节点时, 需要处理四个节点的引用, 而不是两个. 实现起来要困难一些
      2.相对于单向链表, 必然占用内存空间更大一些.
      3.既可以从头遍历到尾, 又可以从尾遍历到头
    双向链表的定义:
      双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。下图为双向链表的结构图。
    在这里插入图片描述
      从上中可以看到,双向链表中各节点包含以下 3 部分信息:
      指针域:用于指向当前节点的直接前驱节点;
      数据域:用于存储数据元素。
      指针域:用于指向当前节点的直接后继节点;
    在这里插入图片描述
    双向循环链表的定义:
      双向链表也可以进行首尾连接,构成双向循环链表,如下图所示
    在创建链表时,只需要在最后将收尾相连即可(创建链表代码中已经标出)。其他代码稍加改动即可。
    在这里插入图片描述
    双链表的节点结构用 C 语言实现为:

    /*随机数的范围*/
    #define MAX 100
    /*节点结构*/
    typedef struct Node{
        struct Node *pre;
        int data;
        struct Node *next;
    }Node;
    

    2.双向链表的创建

      同单链表相比,双链表仅是各节点多了一个用于指向直接前驱的指针域。因此,我们可以在单链表的基础轻松实现对双链表的创建。
      需要注意的是,与单链表不同,双链表创建过程中,每创建一个新节点,都要与其前驱节点建立两次联系,分别是:
      将新节点的 prior 指针指向直接前驱节点;
      将直接前驱节点的 next 指针指向新节点;
      这里给出创建双向链表的 C 语言实现代码:

    #define MAX 100
    Node *CreatNode(Node *head)
    {
            head=(Node*)malloc(sizeof(Node));//鍒涘缓閾捐〃绗竴涓粨鐐癸紙棣栧厓缁撶偣锛?
            if(head == NULL)
            {
                printf("malloc error!\r\n");
                return NULL;
            }
            head->pre=NULL;
            head->next=NULL;
            head->data=rand()%MAX;
            return head;
    }
    Node* CreatList(Node * head,int length)
    {
        if (length == 1)
        {
            
            return( head = CreatNode(head));
        }
        else
        {
            head = CreatNode(head);
            Node * list=head;
            for (int i=1; i<length; i++) 
            /*创建并初始化一个新结点*/
            {
                Node * body=(Node*)malloc(sizeof(Node));
                body->pre=NULL;
                body->next=NULL;
                body->data=rand()%MAX;
    			/*直接前趋结点的next指针指向新结点*/
                list->next=body;
                /*新结点指向直接前趋结点*/
                body->pre=list;
                /*把body指针给list返回*/
                list=list->next;
            }
             
        }
        /*加上以下两句就是双向循环链表*/
        // list->next=head;
        // head->prior=list;
        return head;
    }
    

    3.双向链表的插入

      根据数据添加到双向链表中的位置不同,可细分为以下 3 种情况:
    1.添加至表头
      将新数据元素添加到表头,只需要将该元素与表头元素建立双层逻辑关系即可。
      换句话说,假设新元素节点为 temp,表头节点为 head,则需要做以下 2 步操作即可:
      temp->next=head; head->prior=temp;
      将 head 移至 temp,重新指向新的表头;
      将新元素 7 添加至双链表的表头,则实现过程如下图所示:
    在这里插入图片描述

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
    本文链接:https://blog.csdn.net/qq_16933601/article/details/105351119

    2.添加至表的中间位置
      同单链表添加数据类似,双向链表中间位置添加数据需要经过以下 2 个步骤,如下图所示:
      新节点先与其直接后继节点建立双层逻辑关系;
      新节点的直接前驱节点与之建立双层逻辑关系;
    在这里插入图片描述
    3.添加至表尾
      与添加到表头是一个道理,实现过程如下:
      找到双链表中最后一个节点;
      让新节点与最后一个节点进行双层逻辑关系;
    在这里插入图片描述

    /*在第add位置的前面插入data节点*/
    Node * InsertListHead(Node * head,int add,int data)
    {
        /*新建数据域为data的结点*/
        Node * temp=(Node*)malloc(sizeof(Node));
        if(temp== NULL)
        {
            printf("malloc error!\r\n");
            return NULL;
        }    
        else
        {
            temp->data=data;
            temp->pre=NULL;
            temp->next=NULL; 
        }
        /*插入到链表头,要特殊考虑*/
        if (add==1)
        {
            temp->next=head;
            head->pre=temp;
            head=temp;
        }
        else
        {
            Node * body=head;
            /*找到要插入位置的前一个结点*/
            for (int i=1; i<add-1; i++)
            {
                body=body->next;
            }
            /*判断条件为真,说明插入位置为链表尾*/
            if (body->next==NULL)
            {
                body->next=temp;
                temp->pre=body;
            }
            else
            {
                body->next->pre=temp;
                temp->next=body->next;
                body->next=temp;
                temp->pre=body;
            }
        }
        return head;
    }
    
    
    /*在第add位置的后面插入data节点*/
    Node * InsertListEnd(Node * head,int add,int data)
    {
        int i = 1;
        /*新建数据域为data的结点*/
        Node * temp=(Node*)malloc(sizeof(Node));
        temp->data=data;
        temp->pre=NULL;
        temp->next=NULL;
    
        Node * body=head;
        while ((body->next)&&(i<add+1))
        {
            body=body->next;
            i++;
        }
        
        /*判断条件为真,说明插入位置为链表尾*/
        if (body->next==NULL)
        {
            body->next=temp;
            temp->pre=body;
            temp->next=NULL;
        }
        else
        {
            temp->next=body->pre->next;
            temp->pre=body->pre;
            body->next->pre=temp;
            body->pre->next=temp;
    
        }
    
        return head;
    }
    

    4.双向链表的删除

      双链表删除结点时,只需遍历链表找到要删除的结点,然后将该节点从表中摘除即可。
      例如,删除元素 2 的操作过程如图 所示:
    在这里插入图片描述

    Node * DeleteList(Node * head,int data)
    {
        Node * temp=head;
        /*遍历链表*/
        while (temp)
        {
            /*判断当前结点中数据域和data是否相等,若相等,摘除该结点*/
            if (temp->data==data) 
            {
                /*判断是否是头结点*/
                if(temp->pre == NULL)
                {
                    head=temp->next;
                    temp->next = NULL;
                    free(temp);
                    return head;
                }
                /*判断是否是尾节点*/
                else if(temp->next == NULL)
                {
                    temp->pre->next=NULL;
                    free(temp);
                    return head;
                }
                else
                {
                    temp->pre->next=temp->next;
                    temp->next->pre=temp->pre;
                    free(temp);
                    return head;   
                }
                
    
            }
            temp=temp->next;
        }
        printf("Can not find %d!\r\n",data);
        return head;
    }
    

    5.双向链表更改节点数据

      更改双链表中指定结点数据域的操作是在查找的基础上完成的。实现过程是:通过遍历找到存储有该数据元素的结点,直接更改其数据域即可。

    /*更新函数,其中,add 表示更改结点在双链表中的位置,newElem 为新数据的值*/
    Node *ModifyList(Node * p,int add,int newElem)
    {
        Node * temp=p;
        /*遍历到被删除结点*/
        for (int i=1; i<add; i++) 
        {
            temp=temp->next;
        }
        temp->data=newElem;
        return p;
    }
    

    6.双向链表的查找

      通常,双向链表同单链表一样,都仅有一个头指针。因此,双链表查找指定元素的实现同单链表类似,都是从表头依次遍历表中元素。

    /*head为原双链表,elem表示被查找元素*/
    int FindList(Node * head,int elem)
    {
    /*新建一个指针t,初始化为头指针 head*/
        Node * temp=head;
        int i=1;
        while (temp) 
        {
            if (temp->data==elem)
            {
                return i;
            }
            i++;
            temp=temp->next;
        }
        /*程序执行至此处,表示查找失败*/
        return -1;
    }
    

    7.双向链表的打印

    /*输出链表的功能函数*/
    void PrintList(Node * head)
    {
        Node * temp=head;
        while (temp) 
        {
            /*如果该节点无后继节点,说明此节点是链表的最后一个节点*/
            if (temp->next==NULL) 
            {
                printf("%d\n",temp->data);
            }
            else
            {
                printf("%d->",temp->data);
            }
            temp=temp->next;
        }
    }
    

    8.测试函数及结果

    int main() 
    {
        Node * head=NULL;
        //创建双链表
        head=CreatList(head,5);
        printf("新创建双链表为\t");
        PrintList(head);
        //在表中第 5 的位置插入元素 1
        head=InsertListHead(head, 5,1);
        printf("在表中第 5 的位置插入元素 1\t");
        PrintList(head);
        //在表中第 3 的位置插入元素 7
        head=InsertListEnd(head, 3, 7);
        printf("在表中第 3 的位置插入元素 7\t");
        PrintList(head);
        // //表中删除元素 7
        head=DeleteList(head, 7);
        printf("表中删除元素 7\t\t\t");
        PrintList(head);
        printf("元素 1 的位置是\t:%d\n",FindList(head,1));
        //表中第 3 个节点中的数据改为存储 6
        head = ModifyList(head,3,6);
        printf("表中第 3 个节点中的数据改为存储6\t");
        PrintList(head);
        return 0;
    }
    

    在这里插入图片描述
      大家的鼓励是我继续创作的动力,如果觉得写的不错,欢迎关注,点赞,收藏,转发,谢谢!
    以上代码均为测试后的代码。如有错误和不妥的地方,欢迎指出。
    部分内容参考网络,如有侵权,请联系删除。

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
    本文链接:https://blog.csdn.net/qq_16933601/article/details/105351119

    展开全文
  • 本篇文章主要介绍了JAVA实现双向链表的增删功能的方法,小编觉得挺不错的,现在分享给大家,也给大家个参考。一起跟随小编过来看看吧
  • 链表 操作3 双向链表的 插入排序法

    千次阅读 2015-04-18 14:06:50
    昨天了某公司的数据结构笔试题: 其中一个小功能 是要求对 双向链表进行 快速排序。 思想: 借用了 nginx 链表排序思想  head prev next  假设: 从小到大排序 从链表的 第二个 元素 head->next , 开始,  ...

    昨天做了某公司的数据结构笔试题:

    其中一个小功能 是要求对 双向链表进行 快速排序。  


    思想:

    借用了  nginx 链表排序思想 

    head   prev next 

    假设: 从小到大排序

    从链表的 第二个 元素  head->next , 开始,

             1)首先删除该节点 在链表中的位置(但是不删除该节点)

             2)逐次向前遍历链表 如果 比自己大 则不停向前遍历

    3)找到合适位置,将该节点 插入即可。


    贴上代码:

     

    #include <iostream>
    #include <algorithm>
    #include <time.h>
    #include <stdio.h>
    #include <errno.h>
    #include <string.h>
    #include <stddef.h>
    #include<time.h>
    #include <fcntl.h>
    
    
    #define MAX_PATH   256
    typedef char WCHAR;
    typedef unsigned long DWORD;
    
    
    #if 1
    	typedef struct _FILE_NODE {
    
    	struct _FILE_NODE  *Prev;
    	struct _FILE_NODE  *Next;
    
    	int          size;
    	WCHAR        wzFileName[MAX_PATH];
    	DWORD        dwLowDateTimeLastWrite;
    
    } FILE_NODE, *LPFILENODE;
    
    typedef struct Node
    {
    	FILE_NODE *head;
    	FILE_NODE *tail;
    	int list_size;
    }Node;
    #endif
    
    	int compare(const FILE_NODE *a, const FILE_NODE *b)
    	{
    		if(NULL == a)
    			return 1;
    		if(NULL == b)
    			return 0;
    		return a->size > b->size;
    	}
    
    	
    	void LIST_INIT(Node** node)
    	{
    		if(NULL != *node)
    			return ;
    		
    		Node *tmp_node = (Node*)malloc(sizeof(Node)); 
    		tmp_node->head = (FILE_NODE*)malloc(sizeof(FILE_NODE));
    		memcpy(tmp_node->head->wzFileName, "NULL ", strlen("NULL "));
    		tmp_node->head->wzFileName[strlen("NULL ")]='\0';
    		tmp_node->head->dwLowDateTimeLastWrite = 0;
    		tmp_node->head->size = -1;
    		tmp_node->head->Next = NULL;
    		tmp_node->head->Prev = NULL;
    		tmp_node->tail = tmp_node->head;
    		tmp_node->list_size= 1 ;
    		*node = tmp_node;
    		return ;
    	}
    	
    	void ADD_LIST(Node* plist, FILE_NODE* pnode)
    	{
    		if(NULL == plist || NULL == pnode)
    			return ;
    		
    		if(NULL != pnode)
    		{
    			if(plist->head == plist->tail)
    			{	
    				plist->tail = pnode;
    				pnode->Prev = plist->head;
    				plist->head->Next= pnode;
    				pnode->Next = NULL;
    			}	
    			else
    			{
    				FILE_NODE* tmp = plist->tail;
    				pnode->Next = tmp->Next;
    				pnode->Prev = tmp;
    				tmp->Next = pnode;
    				plist->tail = pnode;
    			}
    			plist->list_size ++;
    		}
    		
    	}
    	
    	
    	
    	// 搜索指定 位置的名字
    	FILE_NODE*  SEARCH_NAME(Node* node, char* name)
    	{
    		if(NULL == node)
    			return NULL;
    		FILE_NODE* tmp = node->head;
    		while(tmp)
    		{
    			if(!memcpy(tmp->wzFileName, name, strlen(name)))
    			{
    				return tmp;
    			}
    			tmp = tmp->Next;
    		}
    		return NULL;
    	}
    	
    	
    	//删除指定名字 的 节点
    	void  DELETE_NAME(Node* node, char* name)
    	{
    		if(NULL == node)
    			return ;
    		FILE_NODE* tmp = node->head;
    		while(tmp)
    		{
    			if(!memcpy(tmp->wzFileName, name, strlen(name)));
    			{
    				//这边仅仅 做一个中间位置的处理两边的话比较简单
    				tmp->Prev->Next = tmp->Next;
    				tmp->Next->Prev = tmp->Prev;
    				node->list_size--;
    			}
    			tmp = tmp->Next;
    		}
    			
    	}
    	
    	
    	void FREE_LIST(Node* node)
    	{
    		if( node->list_size == 0 )
    		{
    			return ;
    		}
    		
    		FILE_NODE* tmp_node = NULL;
    		FILE_NODE* swap = NULL;
    		tmp_node = node->head;
    	
    		while(tmp_node != NULL)
    		{
    			swap = tmp_node->Next;
    			{
    				free(tmp_node);
    				tmp_node = NULL ;
    				node->list_size--;
    			}
    			tmp_node = swap;
    		}
    		return ;
    	}
    	
    	
    	void travel(Node* node)
    	{
    		if(NULL == node)
    			return;
    		FILE_NODE* tmp = node->head->next;
    		while(tmp)
    		{
    			printf("size:%d, name:%s, time=%u\n", tmp->size, tmp->wzFileName, tmp->dwLowDateTimeLastWrite); 
    			tmp = tmp->Next;
    		}
    		return ;
    	}
    	
    	
    #if 1	
    #define list_insert_head(h, x)                                           \
    		(x)->Next = (h)->Next;													  \
    		(x)->Next->Prev = x;													  \
    		(x)->Prev = h;															  \
    		(h)->Next = x
    	
    #define list_remove(x)                                           \
    		(x)->Next->Prev = (x)->Prev;													  \
    		(x)->Prev->Next = (x)->Next;													  \
    		(x)->Prev = NULL;															  \
    		(x)->Next = NULL;
    
    
    	void
    	list_sort(Node *node,
    			int (*cmp)(const FILE_NODE *, const FILE_NODE *))
    		{
    				
    			FILE_NODE  *q, *prev, *next;
    		
    			q = node->head;
    		
    			if (q == node->tail) {
    				return;
    			}
    		
    			for (q = node->head->Next; q != NULL; q = next) {
    		
    				prev = q->Prev;
    				next = q->Next;
    		
    				if(NULL == q->Next)
    				{
    					q->Prev->Next = NULL;	
    				}
    				else
    				{
    					list_remove(q);
    				}	
    				do {
    					//如果 prev 小于q
    					if (cmp(prev, q) <= 0) {
    						break;
    					}
    	
    					prev = prev->Prev;
    		
    				} while (prev != node->head);
    		//将q 插入到prev的后面,
    				list_insert_head(prev, q);
    				//travel(node);
    			}
    		}
    	
    #endif
    
    
    
    int  main()
    {
    	Node *node = NULL;
    	LIST_INIT(&node);
    
    	int i = 0;
    	for(i; i< 10; i++)
    	{
    		FILE_NODE* sp = (FILE_NODE*)malloc(sizeof(FILE_NODE));
    		memset(sp, 0, sizeof(FILE_NODE));
    
    		sp->size  = rand()%10;
    		sp->dwLowDateTimeLastWrite = 100000000;
    		memcpy(sp->wzFileName, "luchenfei", 32);
    
    		ADD_LIST(node,sp);
    
    	}
    
    	travel(node);
    	list_sort(node, compare);
    	travel(node);
    	getchar();
    }
      
    



    展开全文
  • JS实现双向链表

    千次阅读 2018-12-22 17:29:36
    链表结构是我们在面试中经常会被问起的较为基础的数据结构问题,起初学习数据结构使用的是C++语言,最近在前端面试题的过程中没碰到了需要用js实现双链表的需求,百度出来的文章发现可很多错误,于是索性自己重新...

    链表结构是我们在面试中经常会被问起的较为基础的数据结构问题,起初学习数据结构使用的是C++语言,最近在做前端面试题的过程中没碰到了需要用js实现双链表的需求,百度出来的文章发现可很多错误,于是索性自己重新写了,并且列出了一些错误点,这里给大家较为详细的一步步看一下实现思想和步骤,相较于C++语言,js的实现可以说是很简单了,不需要创建繁琐的对象,更加直观易懂;
    首先我们来看一下双向链表的结构图:
    在这里插入图片描述
    每个结点包含三部分,指向前一个结点的指针(pre),指向后一个节点的指针(next),以及自己的数据部分(element),于是我们就可以先写出结点对象

    function Node:定义结点对象

    function Node(element) {
      this.element = element
      this.next = null
      this.previous = null
    }
    

    然后我们开始实现插入链表的算法
    在这里插入图片描述

    (声明)下面函数中的this是我们最后初始化链表的实例,这里大家不要疑惑。可以拉到最下面我们初始化链表那里,相信你会明白呦

    **`function insert`:插入节点**
    function insert(newelement, currentelement) {
      var newNode = new Node(newelement)
      var currentNode = this.find(currentelement)
      if (currentNode === 'error') {
        console.log('无法插入,要插入节点不存在')
        return
      }
      if (currentNode.next != null) {
        newNode.next = currentNode.next
        currentNode.next = newNode
        newNode.previous = currentNode
        newNode.next.previous = newNode
      } else {
        currentNode.next = newNode
        newNode.previous = currentNode
      }
    }
    

    function find:找到插入位置

    function find(element) {
      var currentNode = this.head
      while (currentNode.element != element) {
      /*如果找到最后一个节点还没有找到我们的插入点,那么我们就会返回错误*/
        if (currentNode.next == null) {
          console.log('can not find this node; maybe not have this node')
          return 'error'
        }
        currentNode = currentNode.next
      }
      return currentNode
    }
    

    接下来是移除结点的实现,如果看懂了插入节点的实现,那么移除就会很简单了,相信大家都可以很快明白,这里就直接贴出实现代码;

    function remove:移除一个结点

    function remove(element) {
      var currentNode = this.find(element)
      if (currentNode === 'error') {
        console.log('要移除节点不存在')
        return
      }
      /*首先是不是头尾节点的情况*/
    
      if (currentNode.next != null && currentNode.previous != null) {
        currentNode.previous.next = currentNode.next
        currentNode.next.previous = currentNode.previous
        currentNode.next = null
        currentNode.previous = null
      } else if (currentNode.previous == null) {
        /*当是头节点的时候*/
        this.head = currentNode.next
        currentNode.next.previous = null
        currentNode.next = null
      } else if (currentNode.next == null) {
        /*当是尾节点的时候 */
    
        currentNode.previous.next = null
        currentNode.previous = null
      }
    }
    

    截止到这里我们基本功能已经有了,下面使我们根据自己需要可以自定义一些其他函数

    function lastNode:找到最后一个节点

    function lastNode() {
      var head = this.head
      while (head.next != null) {
        head = head.next
      }
      return head     //这里head在尾节点的位置
    }
    

    function append:将要添加的结点放在链表末尾

    function append(element) {
      var lastnode = this.lastNode()
      var newNode = new Node(element)
      lastnode.next = newNode
      newNode.previous = lastnode
    }
    

    function showlist:将链表所有的结点打印出来

    function showlist() {
      var head = this.head
      do {
        console.log(head.element)
        head = head.next
      } while (head != null)
      // 大家可以看一下下面注释内容存在什么问题,留给大家思考一下
      // while (head.next != null) {
      //   console.log(head.element)
      //   head = head.next
      // }
    }
    

    接下来是对链表进行初始化,这也是上述函数中所有this所代表的实例

    function initlist:初始化链表,并将所有方法注册到链表中

    function initlist() {
      this.head = new Node('one')
      this.find = find
      this.insert = insert
      this.remove = remove
      this.showlist = showlist
      this.lastNode = lastNode
      this.append = append
    }
    
    var list = new initlist()
    list.insert('two', 'one')
    list.insert('four', 'two')
    list.insert('three', 'two')
    
    // console.log(list.head.next)
    list.showlist()
    list.append('A')
    list.append('B')
    list.insert('B2', 'B')
    list.showlist()
    console.log(list.lastNode())
    // list.remove('one')
    // list.showlist()
    console.log(list.find('A').previous)
    // console.log(list.find('four').previous)
    // console.log(list.head.element)
    

    下面是运行结果:
    在这里插入图片描述

    源码:

    function Node(element) {
      this.element = element
      this.next = null
      this.previous = null
    }
    function find(element) {
      var currentNode = this.head
      while (currentNode.element != element) {
        if (currentNode.next == null) {
          console.log('can not find this node; maybe not have this node')
          return 'error'
        }
        currentNode = currentNode.next
      }
      return currentNode
    }
    function insert(newelement, currentelement) {
      var newNode = new Node(newelement)
      var currentNode = this.find(currentelement)
      if (currentNode === 'error') {
        console.log('无法插入,要插入节点不存在')
        return
      }
      if (currentNode.next != null) {
        newNode.next = currentNode.next
        currentNode.next = newNode
        newNode.previous = currentNode
        newNode.next.previous = newNode
      } else {
        currentNode.next = newNode
        newNode.previous = currentNode
      }
    }
    function remove(element) {
      var currentNode = this.find(element)
      if (currentNode === 'error') {
        console.log('要移除节点不存在')
        return
      }
      /*首先是不是头尾节点的情况*/
    
      if (currentNode.next != null && currentNode.previous != null) {
        currentNode.previous.next = currentNode.next
        currentNode.next.previous = currentNode.previous
        currentNode.next = null
        currentNode.previous = null
      } else if (currentNode.previous == null) {
        /*当是头节点的时候*/
        this.head = currentNode.next
        currentNode.next.previous = null
        currentNode.next = null
      } else if (currentNode.next == null) {
        /*当是尾节点的时候 */
    
        currentNode.previous.next = null
        currentNode.previous = null
      }
    }
    function showlist() {
      var head = this.head
      do {
        console.log(head.element)
        head = head.next
      } while (head != null)
      // while (head.next != null) {
      //   console.log(head.element)
      //   head = head.next
      // }
    }
    function initlist() {
      this.head = new Node('one')
      this.find = find
      this.insert = insert
      this.remove = remove
      this.showlist = showlist
      this.lastNode = lastNode
      this.append = append
    }
    function append(element) {
      var lastnode = this.lastNode()
      var newNode = new Node(element)
      lastnode.next = newNode
      newNode.previous = lastnode
    }
    function lastNode() {
      var head = this.head
      while (head.next != null) {
        head = head.next
      }
      return head
    }
    var list = new initlist()
    list.insert('two', 'one')
    list.insert('four', 'two')
    list.insert('three', 'two')
    
    // console.log(list.head.next)
    list.showlist()
    list.append('A')
    list.append('B')
    list.insert('B2', 'B')
    list.showlist()
    console.log(list.lastNode())
    // list.remove('one')
    // list.showlist()
    console.log(list.find('A').previous)
    // console.log(list.find('four').previous)
    // console.log(list.head.element)
    
    
    展开全文
  • 双向链表结点的插入和删除算法

    万次阅读 多人点赞 2018-10-03 23:47:46
    双向链表的插入与删除 双向链表的结点定义 #define ElemType int //双向链表的存储结构 typedef struct DuLNode { ElemType data; DuLNode *prior; DuLNode *next; }DuLNode, *DuLinkList; 双向链表...
  • 一、向双向链表中插入新节点new 关于双向链表的插入问题,有些地方需要特别理解一下,有一个原则就是不能将原始链表弄丢,所以在断开原始连接之前, 我们应该先要将即将断开部分的前后连接保存下来,也就是链表...
  • 双向链表(c++实现)

    千次阅读 2018-02-02 18:14:36
      这种方式,遍历操作的时间复杂度是插入操作的平方,要代码优化,那就和单向链表的正序访问一样,逆序访问就需要一个可以逆序移动的迭代器,即构成一个 双向链表 :在单向链表的每一个节点增加一个指针域,用于...
  • 实现通用的双向链表(c语言实现)

    千次阅读 2017-10-16 15:46:08
    从实现一个通用的双向链表开始。 1. 构建链表节点   链表节点存值还是存值的地址(指针)?对于通用链表首先要做到能够存放任何数据类型的数据,首先可能会想到的是union,但是数据类型无穷无尽,不可能在union...
  • 这是数据结构的约瑟夫双向链表算法,用c++的,使我们学习数据结构的时候老师让我们的实验,很经典,提供给大家参考一下!
  • 链表的插入和删除是非常快速的,因为不需要数据搬移,但是链表想要随机访问第k个元素就没有数组那么高效了,因为链表的数据不是连续的,没办法将首地址和下标带入寻址公式直接计算出对应的内存地址,而是需要根据...
  • LinkedList底层实现(双向链表)(10)

    千次阅读 多人点赞 2020-04-21 17:52:46
    List特性:List底层是双向链表实现的,它的特点是:查询效率低,增删效率高,线程不安全。 1、当对数据存储后需要进行频繁的查询,使用ArrayList 2、但是数据是只用用来存储,增删元素比较频繁那LinkList是你非常好...
  • 双向链表插入、删除节点(详细图解+代码)

    千次阅读 多人点赞 2020-02-01 20:36:36
    双向链表 在单链表的基础上增加了前缀结点,一定程度上提升了查找元素的速度 在查找元素时,可以反向查找前缀结点 插入结点过程(分为4步) 这四个步骤的顺序可调整,但是必须要保证需要的链不断!!...
  • 双向链表的插入与删除(c++实现)

    千次阅读 2020-04-30 16:28:13
    目录前言双向链表插入节点实现代码双向链表删除节点实现代码整个项目的完整代码运行截图总结 前言 本篇文章主要接着上文的双向链表的创建与遍历(c++实现) ...
  • 用 JAVA 实现双向链表

    千次阅读 2019-01-28 23:23:05
    Java 不让人对内存任何操作。为了让人放弃直接操作内存的想法,甚至佯装没有指针。 Java 虚拟机有一个垃圾回收机制,负责释放 / 回收无用对象所占用的内存空间,从而防止内存泄漏(内存泄漏是指,程序中分配的堆...
  • 数据结构--带头结点的双向链表

    千次阅读 2018-04-22 19:38:22
    带头结点的双向链表    之前用c语言写了单链表,单链表是每个结点结构体中包含一个指针,指向下一个结点,还有一个数据类型,用于存储当前结点的值。单链表的结构简单,所以会导致在有时候,它有一些弊端,比如...
  • java 完美 之 单,双向链表自己的 对你学习面向对象,数据结构 有绝对的作用
  • 双向链表(结构体+指针)

    千次阅读 2019-08-02 17:43:04
    首先,中的各个元素称作“结点”。双向链表的结点时结构体,有数据本体,指向前一元素的指针prev以及指向后一元素的指针next组成。这些结构体通过指针构成一个链表,就形成了双向链表。 struct node{ int key...
  • 那么本文将介绍一下另一种特殊的链表结构,叫做 双向链表。 顾名思义,普通的链表都是从 head 开始往后遍历结构内的元素,那么双向链表就是既可以从头开始遍历,又可以从结构的末尾开始遍历。 上一篇文章的跳转链接...
  • 输入一棵二叉搜索树,将该二叉搜索树转换为一个排序的双向链表。要求:不能创建任何新的结点,只能调整树中结点指针的指向。如下图:解法1(非递归): 思想:二叉搜索树的中序遍历是一个有序的数组,在中序遍历的...
  • 如何判断双向链表是否有环

    千次阅读 2019-11-06 13:37:37
    参考 ...之前参加某面试,考了唯一一道算法题,感觉自己答的不好,在此记下这惨痛的教训!...当时可能也是紧张,并且之前过判断单链表是否有环的题目,所以就too young too simple的回答按照单链表的方法进行判断,即...
  • 双向链表(3) - 反转双向链表

    千次阅读 2015-06-14 00:57:31
    双向链表(3) - 反转双向链表
  • C++: 实现双向链表(例题讲解)

    千次阅读 2016-03-24 19:34:14
    这道题和我们之前的单向链表是同一种类型的,只是这一次是双向链表,需要实现的操作较多,可能产生的bug也比之前多。我个人觉得,打出这道题的代码不难,难是难在调试。(入门链表的可以参照我以前的一篇文档入门:...
  • 在代码里面,我了详细的剖析,我成了一个.h文件,当然写了一个使用的main函数: 最重要的,我对container_of和offsetof两个宏进行了分析: #ifndef __list_H #define __list_H //在linux内核中提供了一个用来创建...
  • } 如果看到这里你都已经基本看明白了,那么你用双向循环链表写一个学生管理系统什么的已经没问题了,以前我也是学到这里也过,如果需要欢迎私信。 写到这里突然想起来Linux里还有一个叫做内核链表的东西,下一篇...
  • 双向GRU分类

    千次阅读 2020-04-03 15:23:01
    因为最后的输出是一个前向和一个后向,所以应该连接起来共同作为分类的向量
  • 哈希+双向链表的组合使用

    千次阅读 2016-03-24 13:47:38
    工作五年,四年在一个老牌通信公司,的核心网项目开发,整天关注的是call flow,所参与的项目基本和MM和Call Control相关, 大多重点在项目开发逻辑,以及信令的解析和分析上。 关于网络通信,进程间通信,以及多...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 259,802
精华内容 103,920
关键字:

双向表怎么做