精华内容
下载资源
问答
  • 双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表...
  • 数据结构c++双向链表(首尾指针) 插入操作 #pragma once #include <iostream> using namespace std; template <class T> class DoubleLinkList; template <class T> class Node { public: ...

    数据结构c++双向链表(首尾指针)

    1. 插入操作
      在这里插入图片描述
    #pragma once
    #include <iostream>
    
    using namespace std;
    
    template <class T>
    class DoubleLinkList;
    
    template <class T>
    class Node
    {
    public:
    	Node(T data)
    	{
    		this->data = data;
    		pre = nullptr;
    		next = nullptr;
    	}
    	friend class DoubleLinkList<T>;
    
    	friend ostream& operator<<(ostream& os, Node<T>* node)
    	{
    		return os << node->data;
    	}
    private:
    	T data;
    
    	Node<T>	*pre;		//上一节点
    
    	Node<T> *next;		//下一节点
    };
    
    template <class T>
    class DoubleLinkList
    {
    public:
    	DoubleLinkList()
    	{
    		first = last = new Node<T>(-1);
    		size = 0;
    	}
    
    	bool is_empyt()
    	{
    		if (size == 0)
    			return true;
    		return false;
    	}
    
    	void Clear()
    	{
    		if (is_empyt())
    			return;
    		auto p = first->next;
    		Node<T>* temp = nullptr;
    		while (p!=last)
    		{
    			temp = p;
    			delete temp;
    			p = p->next;
    		}
    		last = first;		//重置末节点
    		size = 0;
    	}
    
    	void show_list()
    	{
    		if (is_empyt())
    			return;
    		auto p = first->next;
    		while (p != nullptr)
    		{
    			cout << p;
    			p = p->next;
    		}
    	}
    
    	Node<T>* get_node(int index)
    	{
    		if (is_empyt())
    			return nullptr;
    		if (index<0 || index>size)
    			return nullptr;
    		auto p = first->next;
    		for (int i=0;i<size;++i)
    		{
    			if(i==index)
    				break;
    			p = p->next;
    		}
    		return p;
    	}
    
    	void insert_index(T data, int index)
    	{
    		if (index<0 || index>size)
    			return;
    		auto node = new Node<T>(data);
    		if (size == 0)
    		{
    			node->pre = first;
    			first->next = node;
    			last = node;
    		}
    		else if (index == 0)
    		{
    			node->pre = first;			//把首节点赋值给新节点的前驱
    			node->next = first->next;	//将第一个节点赋值给新节点的后驱
    			first->next->pre = node;	//将新节点赋值给第一个节点的前驱
    			first->next = node;			//将新节点赋值给首节点的后驱			
    		}
    		else if(index == size)
    		{
    			last->next = node;
    			node->pre = last;
    			last = node;
    		}
    		else
    		{
    			auto pre_node = get_node(index-1);		//当前节点的上一节点
    			node->pre = pre_node;
    			node->next = pre_node->next;
    			pre_node->next->pre = node;
    			pre_node->next = node;
    		}
    		++size;
    	}
    
    	void push_back(T data)
    	{
    		insert_index(data, size);
    	}
    
    	void push_front(T data)
    	{
    		insert_index(data, 0);
    	}
    
    	T pop_index(int index)
    	{
    		if (index<0 || index>size-1)
    			return -1;		
    		Node<T>* node = nullptr;
    		if (index == 0)		//首
    		{
    			node = first->next;
    			first->next = node->next;
    			node->pre = first;
    			if (size == 1)
    				last = first;
    		}
    		else if (index == size-1)		//尾
    		{
    			node = last;
    			last = last->pre;
    			last->next = nullptr;
    		}
    		else	//中
    		{
    			node = get_node(index);		//当前位置节点
    			node->pre->next = node->next;
    			node->next->pre = node->pre;
    		}
    		T data = node->data;
    		delete node;
    		--size;
    		return data;
    	}
    
    	T pop_back()
    	{
    		return pop_index(size-1);
    	}
    
    	T pop_front()
    	{
    		return pop_index(0);
    	}
    private:
    	Node<T>* first;
    
    	Node<T>* last;
    
    	int size;
    };
    
    
    
    展开全文
  • 实现双向链表反转

    2018-05-10 10:33:51
    基于linkedList实现自己的双向链表反转。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。...
  • JAVA双向链表反转实现

    2018-06-10 06:25:14
    通过java实现的双向链表,及反转功能,可能对面试有用哦
  • 创建空的双向链表; 逐字符读取键盘输入的合法...(【提示】:可以利用双向链表的头指针和尾指针,其中头指针往链表尾部移动,尾指针向链表头部方向移动。当头尾指针最后能相遇时,则可认为输入字符串是首尾对称的。)
  • 双向链表

    千次阅读 2019-07-29 15:35:37
    双向链表:在单链表的结点中增加一个指向其前驱的pre指针;该链表中第一个结点的前趋结点为NULL,最后一个结点的后继结点为NULL 。 双向链表具有单链表的所有操作:创建、销毁、获取链表长度、清空、获取某个元素、...

    为什么需要双向链表?

    单链表的结点都只有一个指向下一个结点,单链表的数据元素无法直接访问其前驱元素,所以逆序访问单链表中元素极其耗时;

    思想有点类似使用空间复杂度换时间复杂度。
    双向链表:在单链表的结点中增加一个指向其前驱的pre指针;该链表中第一个结点的前趋结点为NULL,最后一个结点的后继结点为NULL 。

    双向链表示意图
    双向链表具有单链表的所有操作:创建、销毁、获取链表长度、清空、获取某个元素、插入元素、删除元素;

    定义双向链表类型结构

    typedef struct line{
    	struct line *prior;//指向直接前趋
    	int data;
    	struct line *next;//指向直接后继 
    }line;
    

    初始化双向链表

    line *initLine(line *head){
    	//给头结点分配内存 
    	head =(line *)malloc(sizeof(line));//创建链表第一个结点(首元结点)
    	//初始化头结点 
    	head->data =1;
    	head->prior = NULL;
    	head->next = NULL;
    	line *list =head;
    	int i;
    	for(i=2;i<=5;i++){
    		//初始化结点 
    		line *body = (line *)malloc(sizeof(line));  //创建并初始化一个结点 
    		body->data =i;
    		body->prior =NULL;
    		body->next = NULL;
    		//新增结点 
    		list->next = body; //直接将前趋结点的next指针指向新结点;@新增结点body为list的后继结点 
    		body->prior = list; //新结点指向直接前趋结点;@新增结点body的前趋为list 
    		list =list->next; //更新head后继指针的值,不更新的话,更改只是头结点的值 
    	}
    	return head;
    } 
    
    

    插入元素操作

    需要考虑插入元素位置,链表头部、中间、尾部
    插入中间位置示意图

    代码实现

    删除操作

    展开全文
  • 相信大家都明白 LinkedList 是基于双向链表而实现的,本篇文章主要讲解一下双向链表的实现,并且我们参考 LinkedList 自己实现一个单链表尝试一下。 什么是链表? 简单的来讲一下什么是链表:首先链表是一种线性的...
  • 双向链表(结构体+指针)

    千次阅读 2019-08-02 17:43:04
    双向链表的结点时结构体,有数据本体,指向前一元素的指针prev以及指向后一元素的指针next组成。这些结构体通过指针构成一个链表,就形成了双向链表。 struct node{ int key; node *prev,*next;//注意不是node...

    首先当然得了解单向链表了

    传送门

    首先,表中的各个元素称作“结点”。双向链表的结点时结构体,有数据本体,指向前一元素的指针prev以及指向后一元素的指针next组成。这些结构体通过指针构成一个链表,就形成了双向链表。

    struct node{
        int key;
        node *prev,*next;//注意不是node *prev,next
    };

    另外,在表头设置一个特殊节点可以简化链表的实现,将这个结点称为“头节点”,头节点中不包括实际数据,但它可以让我们更轻松地对链表做更改。

    init函数用于初始化链表。它会生成一个NIL节点作为链表的头节点,然后让prev和next都指向这个头节点,从而创建一个空表。

    node *nil;
    void init()
    {
        nil=(node*)malloc(sizeof(node));
        nil->next=nil;
        nil->prev=nil;
    }

    然后就是很重要的插入元素。

    void insert(int key)
    {
        node *x=(node*)malloc(sizeof(node));
        x->key=key;
        x->next=nil->next;
        nil->next->prev=x;
        nil->next=x;
        x->prev=nil;
    }

     

    listsearch函数用于搜索元素,它可以在链表中寻找包含指定键值的结点,并返回其指针,假设cur为指向当前位置结点的指针,那么只要从头节点的next所指的结点,即链表开头的元素逐个进行cur=cur->next,即可逐一访问每个结点。

     

    node* listsearch(int key)
    {
        node *cur=nil->next;
        while(cur!=nil&&cur->key!=key){
            cur=cur->next;
        }
        return cur;
    }

    deletenode函数删除指定结点t。

    void deletenode(node *t)
    {
        if(t==nil){
            return ;
        }
        t->prev->next=t->next;//修改前面的指向
        t->next->prev=t->prev;//修改后面的指向
        free(t);
    }
    
    void deletefirst()
    {
        
        deletefirst(nil->next);
    }
    
    void deletelast()
    {
        deletenode(nil->prev);
    }
    
    void deletekey(int key)
    {
        deletekey(listsearch(key));
    }

    deletelastfirst函数,deletelast函数分别用于删除头节点next,prev所指向的结点,deletekey函数可以删除包含指定key的结点,它可以先通过listsearch函数搜索出与key一致的结点t,然后再使用deletenode(t)删除该节点。

    整体运用一下:

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    
    using namespace std;
    
    struct node{
        int key;
        node *prev,*next;
    };
    
    node *nil;
    void init()
    {
        nil=(node*)malloc(sizeof(node));
        nil->next=nil;
        nil->prev=nil;
    }
    
    void insert(int key)
    {
        node *x=(node*)malloc(sizeof(node));
        x->key=key;
        x->next=nil->next;
        nil->next->prev=x;
        nil->next=x;
        x->prev=nil;
    }
    
    void deleteNode(node*t)
    {
        if(t==nil){
            return ;
        }
        t->prev->next=t->next;
        t->next->prev=t->prev;
        free(t);
    }
    
    void deleteFirst()
    {
        deleteNode(nil->next);
    }
    
    void deleteLast()
    {
        deleteNode(nil->prev);
    }
    
    node* listSearch(int key)
    {
        node *cur=nil->next;
        while(cur!=nil&&cur->key!=key){
            cur=cur->next;
        }
        return cur;
    }
    
    void deleteKey(int key)
    {
        deleteNode(listSearch(key));
    }
    
    void printList()
    {
        node*cur=nil->next;
        int isf=0;
        while(1){
            if(cur==nil){
                break;
            }
            if(isf++>0){
                printf(" ");
            }
            printf("%d",cur->key);
            cur=cur->next;
        }
        printf("\n");
    }
    
    int main()
    {
        int n,key;
        char com[20];
        scanf("%d",&n);
        init();
        for(int i=0;i<n;i++){
            scanf("%s%d",com,&key);
            if(com[0]=='i'){
                insert(key);
            }else if(com[0]=='d'){
                if(strlen(com)>=6){
                    if(com[6]=='F'){
                        deleteFirst();
                    }else if(com[6]=='L'){
                        deleteLast();
                    }else{
                        deleteKey(key);
                    }
                }
            }
        }
        printList();
        return 0;
    }
    /*
    7
    insert 5
    insert 2
    insert 3
    insert 1
    delete 3
    insert 6
    delete 5
    */
    

     

    展开全文
  • 双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表...
  • 双向链表实现结点类

    2018-04-11 08:47:19
    定义、实现并测试一个双向链表结点类DNode。 链表结点类中包含私有数据成员为两个整数x,y以及结点指针left及右结点指针right。 包含的函数成员包括: (a)对结点的数据成员赋值setDNodeValues(int,int,DNode* ...
  • 异或指针双向链表

    2016-12-16 19:09:29
    复习链表时挺好的
  • C语言数据结构 双向链表的建立与基本操作 双向链表比单链表有更好的灵活性,其大部分操作与...由于定义双向链表指针域中多了一个prior指针,插入操作相应变得复杂,但基本操作也并不难理解。只需记住在处理前驱和后
  • 单链表、双向链表、循环链表

    千次阅读 多人点赞 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);
    }
    
    展开全文
  • 指针双向链表逻辑结构单指针双向链表则需要采用异或链表的方式,下图是一个具有五个节点的双向链表的逻辑结构示意图,没有头结点。其中每个节点的后半部分表示指针域,存储了它的前驱节点的指针与后继借点的指针的...
  • 多级双向链表中,除了指向下一个节点和前一个节点指针之外,它还有一个子链表指针,可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项,依此类推,生成多级数据结构,如下面的示例所示。 给你位于...
  • 改进:不需要对每个结点的链域进行置空初始化,因为最后还是会重新赋值。只需要对头结点 L 初始化: L->prior = L; 原方法:每次选出最小元素,采用尾插法排序,较为繁琐,而且指针变量太多。新方法:每次选出...
  • 对循环双链表实现下述功能: void meau(); //菜单函数 void Initlist(List *list); //初始化 void show(List *list); //打印链表内容 bool Push_back(List *list,ElemType x); //尾插法 b
  • 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。 为了让您更好地理解问题,以下面的二叉搜索树为例: 我们希望将这个二叉搜索树转化为...
  • 双向链表头文件.zip

    2020-07-18 23:48:58
    双向链表基本操作函数头文件。包括创建链表,销毁链表,向前插入节点,向后插入节点,打印链表,清空链表,等
  • 链表中的双指针

    2020-06-23 11:59:19
    链表中的双指针,一般是指初始时设置两个移动指针,它们可能以不同的初始状态或不同的移动方式进行移动。 1.删除链表的倒数第N个节点 题目描述:给定一个链表,删除链表的倒数第n个节点,并且返回链表的头结点。 ...
  • 10.逆置(通过改变指针的方式将元素逆序);11.按元素查找(查找指定元素是否存在);12.按位置删(删除指定位置元素);13.按元素删(删除指定元素);14.清空(清除所有元素,但链表未销毁,还可以继续进行操作)...
  • 双向链表:单向链表只能向着一个方向遍历链表节点,而在节点指针域中增加了前向指针双向链表,则可以向着两个方向遍历节点。这使得双向链表也可以在任何一个节点遍历整个链表。 function DoublyLinkedList() { ...
  • 双向链表(详解)

    千次阅读 多人点赞 2020-10-19 02:09:10
    双向链表操作 在学习了单链表之后,就顺带学习了双链表的操作。... 而在双向链表中,我们需要有两个指针域,一个负责向后连接,一个负责向前连接。 /* 单链表的结构 */ struct List{ int data; // 数据域 st
  • 详解双向链表的基本操作(C语言)

    万次阅读 多人点赞 2020-04-06 22:06:19
    1.双向链表的定义 上一节学习了单向链表单链表详解。今天学习双链表。学习之前先对单向链表和双向链表做个回顾。 单向链表特点:   1.我们可以轻松的到达下一个节点, 但是回到前一个节点是很难的.   2.只能从头...
  • 双向链表的插入

    2021-09-20 15:15:06
    已知p指针,那么a结点的地址就在p指针所指结点的prior里存着, a结点要变成s的前驱, 所以要给s的Prior域赋值,赋的是a结点的地址,即p的prior。 接下来 将s结点变成a结点的后继,就要给a结点的...
  • 添加(默认添加到双向链表的最后) (1).先找到双向链表的最后这个节点(temp) (2).temp.next = newHeroNode (3).newHeroNode.pre = temp; 修改思路和单链表一样 删除 (1).以为是双向链表,因此,我们可以...
  • 指针异或运算实战二、异或指针双向链表的实现 一、异或运算的基本知识 1. 什么是异或运算 假设二进制数10跟二进制数01进行异或运算的时候,即10 ^ 01,从右往依次进行运算,相同情况的异或结果为0,否则为1。...
  • 有个节点为e,指向他的指针为s①插入:想要把e插入到ai的后面,只需要把s的next指向p的next,再把p的next指向e就可以了②删除:想要删除ai+1节点,只需要把p的next指针指向p的next的next就可以了二、静态链表就是用...
  • 双向链表的删除操作

    万次阅读 2021-03-19 19:32:50
    //从双向链表中删除一个节点 //说明 //1.对于双向链表,我们可以直接找到删除的这个节点 //2.找到后,自我删除即可 public void del(int no) { //判断当前链表是否为空 if (head.next==null){//空链表 System...
  • 本文实例讲述了Python二叉搜索树与双向链表实现方法。分享给大家供大家参考,具体如下: # encoding=utf8 ''' 题目:输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。 要求不能创建任何新的结点,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 86,178
精华内容 34,471
关键字:

双向链表左指针