精华内容
下载资源
问答
  • 1.利用前驱后继 对于一个二叉树,可以将其分为左子树、根节点和右子树三部分。...那么可以先找到并标记根节点的前驱和后继,然后连接。同时递归执行这一过程便能达到要求。 具体代码如下: /** ...

    1.利用前驱后继

    对于一个二叉树,可以将其分为左子树、根节点和右子树三部分。根据题目要求可知将BST化为一个排好序的双向链表实际上就是将其中序遍历序列对应的各个节点连接起来。同时还可以知道若根的左右子树非空,则根节点在链表中的前驱结点一定在其左子树中,后继结点一定在其右子树中。那么可以先找到并标记根节点的前驱和后继,然后连接。同时递归执行这一过程便能达到要求。

    具体代码如下:

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        TreeNode *findPreNode(TreeNode *root){
            TreeNode *p = root;
            if(p -> left){
                p = p -> left;
                while(p -> right) p = p -> right;
                return p;
            }
            else return NULL;
        }
        
        TreeNode *findSuccNode(TreeNode *root){
            TreeNode *p = root;
            if(p -> right){
                p = p -> right;
                while(p -> left) p = p -> left;
                return p;
            }
            else return NULL;
        }
        
        TreeNode *change(TreeNode * root){
            TreeNode *p = findPreNode(root); //记录前驱节点指针
            TreeNode *q = findSuccNode(root); //记录后继节点指针
            if(root -> left) change(root -> left);
            if(root -> right) change(root -> right);
            //将当前节点分别与其前驱节点和后继节点相连
            root -> left = p;
            if(p) p -> right = root;
            root -> right = q;
            if(q) q -> left = root;
            return root;
        }
        
        TreeNode* convert(TreeNode* root) {
            if(!root) return NULL;
            change(root);
            while(root -> left) root = root -> left;
            return root;
        }
    };

    2.中序遍历

    可以发现对于一棵BST而言,中序遍历的当前节点与将要回溯的节点之间就是双向链表中相邻的关系。因此可以考虑通过中序遍历来直接完成BST到链表的转化。

    具体代码如下:

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        TreeNode *change(TreeNode *root, TreeNode *&head, TreeNode *&tail){
            if(!root) return NULL;
            change(root -> left, head, tail);
            if(!head){
                head = tail = root;
            }
            else{
                root -> left = tail;
                tail -> right = root;
                tail = root;
            }
            change(root -> right, head, tail);
            return head;
        }
    
        TreeNode* convert(TreeNode* root) {
            TreeNode *head = NULL, *tail = NULL; //注意这里要么在传参时使用指针引用要么将head和tail声明为全局变量
            return change(root, head, tail);
        }
    };

     

    展开全文
  • 所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。 二.结构实现 1.双向链表结构 public class DoubleLinkedList { private int data; private ...

    一.概述

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

    二.结构实现

    1.双向链表结构
    public class DoubleLinkedList {
    
        private int data;
        private DoubleLinkedList before;
        private DoubleLinkedList after;
    
    
        public int getData() {
            return data;
        }
    
        public void setData(int data) {
            this.data = data;
        }
    
        public DoubleLinkedList getBefore() {
            return before;
        }
    
        public void setBefore(DoubleLinkedList before) {
            this.before = before;
        }
    
        public DoubleLinkedList getAfter() {
            return after;
        }
    
        public void setAfter(DoubleLinkedList after) {
            this.after = after;
        }
    }
    2.生成链表
    public static DoubleLinkedList create(int n){
        DoubleLinkedList curPoint = null;
        DoubleLinkedList head = null;
    
        while (n != 0){
            DoubleLinkedList node = new DoubleLinkedList();
            node.setData((int)(Math.random()*11));
            node.setBefore(curPoint);
    
            if(curPoint != null){
                curPoint.setAfter(node);
            }else{
                head = node;
            }
    
            curPoint = node;
            n--;
        }
    
    
        return head;
    }
    3.链表排序
    //当前算法时间复杂度是O(N^2)
    public static DoubleLinkedList sort(DoubleLinkedList doubleLinkedList){
        DoubleLinkedList curPointOut = doubleLinkedList;
        DoubleLinkedList curPointIn;
    
        while (curPointOut.getAfter() != null){
            curPointIn = doubleLinkedList;
            while (curPointIn.getAfter() != null){
                int afterData = curPointIn.getAfter().getData();
                if(afterData < curPointIn.getData()){
                    curPointIn.getAfter().setData(curPointIn.getData());
                    curPointIn.setData(afterData);
                }
                curPointIn = curPointIn.getAfter();
            }
            curPointOut = curPointOut.getAfter();
        }
    4.测试
    public static void main(String[] args) {
        DoubleLinkedList doubleLinkedList = create(5);
        sort(doubleLinkedList);
    }
    展开全文
  • 已知不带头结点的双向链表第一个节点的指针为list,链节点除了数据域和分别指向该结点的前驱结点和后继结点的指针域外,还设置记录该节点访问次数频度域freq(初始值为0),请设计一算法LOCATE(list,x),该算法的功能是...

    双向链表的访问,双向链表的排序

    题目

    已知不带头结点的双向链表第一个节点的指针为list,链节点除了数据域和分别指向该结点的前驱结点和后继结点的指针域外,还设置记录该节点访问次数频度域freq(初始值为0),请设计一算法LOCATE(list,x),该算法的功能是每当访问LOCATE(list,x)操作,数据域信息为X的结点freq域的值增加1并且保持链表中结点的freq值得递减链接,使得频繁访问的结点靠近前面。

    分析

    思路分析:
    第一步:双向链表中查找符合条件的X,并且freq+1;
    第二步:根据freq的大小递减排序

    假设 算法的数据域为int型。

    代码

    typedef struct DNode{    
    	int data;    // 数据域
    	int freq; // 存储访问的次数    
    	struct DNode *llink,*rlink;
    }DNode,*DLinklist;
    
    

    函数的具体实现

    // 双向链表的访问,双向链表的排序
    int LOCATE(DLinklist list,int x){    
    	DLinklist q,p;    
    	p=list->rlink;    
    	while (p!=NULL&&p->data!=x)    {      
    	 	p = p->rlink;  // 判断指针下移    
    	 }    
    	 if (p==NULL)    {        
    	 	return 0;  // 如果为空,说明没有和X相等的这个结点   
    	 }else    {        
    	 	p->freq++;  // 访问的次数加一        
    	 	q=p->llink;  // q 指向p 所指的前驱结点        
    	 	while (q!=list&&q->freq<p->freq)  {  
    	 	       // q与p的访问次数比较 条件成立需要移动指针  
    	 	        p->llink=q->llink;            
    	 	       p->llink->rlink=p;  // p所指结点移到q的前面          
    	 	       q->rlink=p->rlink;            
    	 	       if (p->rlink!=NULL)    {    
                		 q->rlink->llink=q;            
    	 	       }            
    	 	       q->llink=p;            
    	 	       p->rlink=q;      // 这里防止锻炼哦。      
    	 	       q=p->llink; //  q指向p的前驱结点                    
    	 	}   // while         
    	 } // if   
    	 return 1;
    }
    
    展开全文
  • 文章目录一:双向链表(一):双向链表的结构(二):数据的构建(三):创建...分别指向节点的前驱和后继。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。 其结构如下示意图...

    一:双向链表

    (一):双向链表的结构

    双向链表是链表的一种,它的每个节点中都有两个指针:前指针和后指针。分别指向节点的前驱和后继。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。
    其结构如下示意图所示:
    链表中任意两相邻的节点通过前后指针相互相连。
    在这里插入图片描述
    节点:
    在这里插入图片描述

    (二):数据的构建

    节点:节点是描述结构体的基本单元,抽象单一个体
    节点:

    struct Node
    {
    	int data;
    	struct Node* front;//前指针		或称左指针(left)
    	struct Node* tail;//后指针		或称右指针(right)
    };
    

    链表的封装:描述结构的特征
    链表:

    struct List
    {
    	//万金油参数
    	int size;
    	struct Node* firstNode;//首节点
    	struct Node* lastNode;//尾节点
    };
    

    (三):创建节点

    //1.创建节点
    struct Node* createNode(int data)
    {
    	struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));//为节点申请内存
    	//节点的初始化
    	newNode->data = data;
    	newNode->front = NULL;
    	newNode->tail = NULL;
    	return newNode;
    }
    

    (四):创建链表

    //2.创建链表
    struct List* createList()
    {
    	struct List* list = (struct List*)malloc(sizeof(struct List));//为链表申请内存
    	//初始化变量
    	list->size = 0;
    	list->firstNode = NULL;
    	list->lastNode = NULL;
    	return list;
    }
    

    (五):插入

    1:表头法插入

    注意:
    1.当链表为空时,进行插入链表的首节点和尾节点都指向新插入的节点
    2.不为空时,进行插入要做好"连线",即连接插入节点和首节点,然后注意让list->firstNode始终指向首节点即:list->firstNode=newNode

    //3.表头法插入
    void insertNodeByHead(struct List* list, int data)//函数参数的确定:插入到哪个链表,插入的数据是什么
    {
    	struct Node* newNode = createNode(data);//创建插入的节点
    	if (list->size==0)
    	{
    		list->firstNode = newNode;//当链表为空时进行插入,list链表的first和last全都指向新节点newNode
    		list->lastNode = newNode;
    	}
    	else
    	{
    		//这里进行节点之间的连接需要连接两条线并且移动list->firstNode,使其始终指向首节点
    		list->firstNode->front = newNode;//做连接
    		newNode->tail = list->firstNode;//做连接
    		list->firstNode = newNode; //将list->firstNode一直指向首节点
    	}
    	list->size++;
    }
    
    

    2:表尾法插入

    表尾法插入的过程
    1.当链表为空时,首节点和尾节点指向newNode
    2.链表不为空时,做连接,连接尾节点和新插入的节点
    3.不要忘记将list->last始终指向尾节点

    //4.表尾插入
    void insertNodeByTail(struct List* list, int data)//函数参数的确定:插入到哪个链表,插入的数据是什么
    {
    	struct Node* newNode = createNode(data);//创建插入的节点
    	if (list->size == 0)
    	{
    		list->firstNode = newNode;
    		list->lastNode = newNode;
    	}
    	else
    	{
    		//与表头法插入类似,连接两条线,然后移动list->lastNode使其一直指向尾节点
    		list->lastNode->tail = newNode;
    		newNode->front = list->lastNode;
    		list->lastNode = newNode;
    	}
    	list->size++;
    }
    

    3:指定位置插入

    指定位置插入(指定位置删除)等首要任务都是找到指定的位置,然后将插入的数据节点与指定位置前节点,指定位置后节点做连接即可我们需要找到指定位置节点以及指定位置前的节点,因此的我们需要两个相邻的移动节点posNode和posFrontNode
    过程:
    1:首先判断是否首节点为指定位置节点,若是则头插法
    2:当首节点不是指定位置节点时,通过两个并排的移动指针往后找
    3:跳出循环后,posNode指向NULL则链表中无指定位置节点,无法进行插入
    4:posNode不指向NULL时,则指向指定位置节点,此时在posNode和posFrontNode之间做连线即可
    注意:需要连接四条线

    //5.指定位置插入
    void insertNodeByAppoin(struct List* list, int posData, int data)//参数的确定:要插入到哪个链表(list),插到哪个数据的前面(posData),要插入的数据(data)
    {
    
    	struct Node* posFrontNode = list->firstNode;
    	struct Node* posNode = list->firstNode->tail;
    	if (posFrontNode->data==posData)//当首节点为指定位置节点时,进行头插法
    	{
    		insertNodeByHead(list, data);
    	}
    	else
    	{
    		while (posNode->data != posData)//一直等到找到指定位置或者找到结尾然后跳出
    		{
    			posFrontNode = posNode;//节点并排往后移动
    			posNode = posNode->tail;
    			if (posNode == NULL)//走到最后面退出来
    			{
    				break;
    			}
    		}
    		if (posNode == NULL)//判断posNode的转态是指向指定位置节点还是指向NULL(未找到数据)
    		{
    			printf("未找到指定数据,无法插入。\n");
    		}
    		else
    		{
    			struct Node* newNode = createNode(data);///创建节点
    			newNode->tail = posNode;//然后进行做连接,newNode与posNode,posFrontNode分别做连接,将newNode放到posNode和posFrontNode的中间。需要连接4条线
    			posNode->front = newNode;
    			newNode->front = posFrontNode;
    			posFrontNode->tail = newNode;
    		}
    		list->size++;
    	}
    }
    

    (六):删除

    1:头删除

    //6.头删
    void deleteNodeByHead(struct List* list)//要删除哪个节点
    {
    	if (list->size == 0)//当链表为空时,无法删除
    	{
    		printf("链表为空,无法进行删除\n");
    	}
    	else
    	{
    		struct Node* nextNode = list->firstNode->tail;//保存一下链表list的第二个节点
    		free(list->firstNode);
    		list->firstNode = nextNode;//list->firstNode始终指向链表的首节点
    		list->size--;
    	}
    }
    

    2:尾删

    注意:list->lastNode指向previousNode后,previousNode的后指针不为NULL,这时需要将list->lastNode的后指针指向NULL

    //7.尾删
    void deleteNodeByTail(struct List* list)
    {
    	if (list->size == 0)//当链表为空时,无法删除
    	{
    		printf("链表为空,无法进行删除\n");
    	}
    	else
    	{
    		struct Node* previousNode = list->lastNode->front;//保存一下链表list的倒数第二个指针
    		free(list->lastNode);
    		list->lastNode = previousNode;//list->lastNode始终指向链表的尾节点
    		list->lastNode->tail = NULL;  //注意这一点不能遗漏,
    		//再次犯错!!!,previousNode=list->lastNode->front的tail不止向NULL
    		//因此,这里list->lastNode=previousNode后,需要将list->lastNode的后指针指向NULL
    		list->size--;
    	}
    }
    

    3:指定位置删除

    //8.指定位置删除
    void deleteNodeByAppoin(struct List* list, int posData)
    {
    	struct Node* posFrontNode = list->firstNode;
    	struct Node* posNode = list->firstNode->tail;
    	if (posFrontNode->data==posData)
    	{
    		deleteNodeByHead(list);
    	}
    	else
    	{
    		while (posNode->data != posData)
    		{
    			posFrontNode = posNode;
    			posNode = posNode->tail;
    			if (posNode == NULL)
    			{
    				break;
    			}
    		}
    		if (posNode == NULL)
    		{
    			printf("未找到指定位置,无法删除\n");
    		}
    		else
    		{
    			posFrontNode->tail = posNode->tail;//做连线,将posFrontNode和posNode->tail连接到一起
    			posNode->tail->front = posFrontNode;
    			free(posNode);//清理posNode
    			posNode = NULL;//置空
    			list->size--;
    		}
    	}
    }
    

    (七):链表的打印

    这里的每一个节点都有前指针和后指针。很容易通过后指针进行顺序打印,通过前指针进行逆序打印。

    //9.顺序打印(通过后指针)
    void printListByTail(struct List* list)//通过节点的后指针进行顺序打印
    {
    	if (list->size == 0)
    	{
    		printf("链表为空,无法打印\n");
    	}
    	else
    	{
    		struct Node* pMove = list->firstNode;
    		printf("顺序打印:");
    		while (pMove)
    		{
    			printf("%d ", pMove->data);
    			pMove = pMove->tail;
    		}
    		printf("\n");
    	}
    }
    //10.逆序打印(通过前指针)
    void printListByFront(struct List* list)//通过节点的前指针进行顺序打印
    {
    	if (list->size == 0)
    	{
    		printf("链表为空,无法打印\n");
    	}
    	else
    	{
    		struct Node* pMove = list->lastNode;
    		printf("逆序打印:");
    		while (pMove)
    		{
    			printf("%d ", pMove->data);
    			pMove = pMove->front;
    		}
    		printf("\n");
    	}
    }
    

    (八):完整测试代码

    //双向循环链表 约瑟环问题  杀人游戏
    #include<stdio.h>
    #include<stdlib.h>
    struct Node
    {
    	int data;
    	struct Node* front;
    	struct Node* tail;
    };
    //创建节点
    struct Node* createNode(int data)
    {
    	struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    	newNode->data = data;
    	newNode->front = NULL;
    	newNode->tail = NULL;
    	return newNode;
    }
    //创建链表
    struct Node* createList()//headNode里不存放数据
    {
    	struct Node* headNode = (struct Node*)malloc(sizeof(struct Node));
    	headNode->front = headNode;
    	headNode->tail = headNode;
    	return headNode;
    }
    //头插
    void insertNodeByFront(struct Node* headNode, int data)
    {
    	struct Node* newNode = createNode(data);
    	struct Node* nextNode = headNode->tail;//记录一下首节点的下一位
    	//做连线  四条线
    	headNode->tail = newNode;//首节点的后指针指向新节点
    	newNode->front = headNode;//新节点的前指针指向首节点
    	newNode->tail = nextNode;//新节点的后指针指向首节点的下一位
    	nextNode->front = newNode;//首节点的下一位前指针指向新节点
    }
    //尾插
    void insertNodeByTail(struct Node* headNode, int data)
    {
    	struct Node* newNode = createNode(data);
    	struct Node* tailNode = headNode->front;//首节点的前指针的指向尾节点
    	//连接四根线
    	tailNode->tail = newNode;//尾节点的后指针指向新节点
    	newNode->front = tailNode;//新节点的前指针指向尾节点
    	headNode->front = newNode;//首节点的前指针指向新节点
    	newNode->tail = headNode;//新节点的后指针指向头节点
    }
    //指定位置插入
    void insertNodeByAppoin(struct Node* headNode, int posData, int data)
    {
    	if (headNode->front == headNode && headNode->tail == headNode)//当头指针和尾指针指向headNode时,说明为初始状态,链表为空。
    	{
    		printf("链表为NULL,无法插入\n");
    	}
    	else
    	{
    		struct Node* posFrontNode = headNode;
    		struct Node* posNode = headNode->tail;
    		while (posNode->data != posData)
    		{
    			posFrontNode = posNode;
    			posNode = posNode->tail;
    			while (posNode == headNode)
    			{
    				break;
    			}
    		}
    		if (posNode == headNode)
    		{
    			printf("未找到指定位置,无法做指定位置插入\n");
    		}
    		else
    		{
    			struct Node* newNode = createNode(data);//创建节点
    			//做连线,四条连线
    			posFrontNode->tail = newNode;//指定位置前节点的后指针指向新节点
    			newNode->front = posFrontNode;//新节点的前指针指向指定位置节点
    			posNode->front = newNode;//指定位置节点的前指针指向新节点
    			newNode->tail = posNode;//新节点的后指针指向指定位置节点
    		}
    	}
    }
    //删除
    //头删除
    void deleteNodeByHead(struct Node* headNode)
    {
    	if (headNode->front == headNode&&headNode->tail==headNode)//当头指针和尾指针指向headNode时,说明为初始状态,链表为空。
    	{
    		printf("链表为NULL,无法进行删除\n");
    	}
    	else
    	{
    		struct Node* nextNode = headNode->tail;//记录一下第一个数据节点
    		//做连接:头节点的尾指针指向nextNode的tail
    		headNode->tail = nextNode->tail;
    		//nextNode->tail的头指针指向headNode
    		nextNode->tail->front = headNode;
    		//清理第一个数据节点
    		free(nextNode);
    		nextNode = NULL;
    	}
    }
    //尾删除
    void deleteNodeByTail(struct Node* headNode)
    {
    	if (headNode->front == headNode && headNode->tail == headNode)//当头指针和尾指针指向headNode时,说明为初始状态,链表为空。
    	{
    		printf("链表为NULL,无法进行删除。\n");
    	}
    	else
    	{
    		struct Node* tailNode = headNode->front;//找到尾节点,headNode的前指针就是尾节点
    		tailNode->front->tail = headNode;
    		headNode->front = tailNode->front;
    		free(tailNode);
    		tailNode = NULL;
    	}
    }
    //指定位置删除
    void deleteNodeByAppoin(struct Node* headNode, int posData)
    {
    	struct Node* posFrontNode = headNode;
    	struct Node* posNode = headNode->tail;
    	if (posNode->data == posData)//首个数据节点的数据等于指定数据时,头删除
    	{
    		deleteNodeByHead(headNode);
    	}
    	else
    	{
    		while (posNode->data != posData)
    		{
    			posFrontNode = posNode;
    			posNode = posNode->tail;
    			if (posNode == headNode)//循环一圈回到headNode,说明没有指定数据。退出
    			{
    				break;
    			}
    		}
    		if (posNode == headNode)//判断posNode的状态
    		{
    			printf("没有找到指定数据,无法进行删除。\n");
    		}
    		else
    		{
    			posFrontNode->tail = posNode->tail;
    			posNode->tail->front = posFrontNode;
    			free(posNode);
    			posNode = NULL;
    		}
    	}
    }
    
    //打印测试
    //通过后指针打印遍历
    void printListByTail(struct Node* headNode)
    {
    	if (headNode->front == headNode&&headNode->tail==headNode)//当头指针和尾指针指向headNode时,说明为初始状态,链表为空。
    	{
    		printf("表为NULL,无法打印\n");
    		return;
    	}
    	struct Node* pMove = headNode->tail;
    	printf("通过后指针打印\n");
    	while (pMove != headNode)
    	{
    		printf("%d ", pMove->data);
    		pMove = pMove->tail;
    	}
    	printf("\n"); 
    }
    //通过前指针打印遍历
    void printListByFront(struct Node* headNode)
    {
    	if (headNode->front == headNode&&headNode->tail==headNode)//当头指针和尾指针指向headNode时,说明为初始状态,链表为空。
    	{
    		printf("表为NULL,无法打印\n");
    		return;
    	}
    	struct Node* pMove = headNode->front;
    	printf("通过后指针打印\n");
    	while (pMove != headNode)
    	{
    		printf("%d ", pMove->data);
    		pMove = pMove->front;
    	}
    	printf("\n");
    }
    int main()
    {
    	//创建链表
    	struct Node* list = createList();
    	
    	//尾插法
    	insertNodeByTail(list, 3);
    	insertNodeByTail(list, 2);
    	insertNodeByTail(list, 1);
    	printListByTail(list);
    	printListByFront(list);
    	printListByTail(list);
    
    	//头插法
    	insertNodeByFront(list, 4);
    	insertNodeByFront(list, 5);
    	insertNodeByFront(list, 6);
    	printListByTail(list);
    
    	//指定位置插入
    	insertNodeByAppoin(list, 6, 7);
    	printListByTail(list);
    
    	//头删
    	deleteNodeByHead(list);
    	deleteNodeByHead(list);
    	printListByTail(list);
    
    	//尾删
    	deleteNodeByTail(list);
    	deleteNodeByTail(list);
    	printListByTail(list);
    
    	//指定位置删除
    	deleteNodeByAppoin(list, 4);
    	deleteNodeByAppoin(list, 3);
    	deleteNodeByAppoin(list, 5);
    	printListByTail(list);
    	return 0;
    }
    

    二:双向循环链表

    (一):双向循环链表的结构

    双向循环链表的结构如下:
    它是在双向链表的基础上,将双向链表的首节点指向尾节点,尾节点指向首节点。使得各个节点之间通过指针连接成环。

    在这里插入图片描述
    连接成环后,这里就没有严格上的首节点和尾节点了,也没有严格上的“前”和“后”节点了。为了实现以及描述的方便:我们在双向循环链表中取一个节点作为标记headNode(我们这里headNode中不存放数据相当于表头),其headNode的前指针指向tailNode。这样我们就可以,用双向链表的操作来操作这个结构了。

    当然,这里我们也可以使用再封装的方式,或者headNode中也存放数据。写法会略微有点不同,可以尝试着自己去实现。

    变形如下:
    在这里插入图片描述
    节点(结构体)的结构:-
    与循环链表的中节点的结构相同

    在这里插入图片描述

    (二):数据的构建

    1:节点:

    struct Node
    {
    	int data;              //数据域
    	struct Node* front;    //前指针
    	struct Node* tail;     //后指针
    };
    

    2:创建节点:

    //创建节点
    struct Node* createNode(int data)
    {
    	struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));//为节点申请内存
    	//初始化数据
    	newNode->data = data;
    	newNode->front = NULL;
    	newNode->tail = NULL;
    	return newNode;
    }
    

    3:创建链表:
    初始状态:headNode的前后指针都指向本身。

    //创建链表
    struct Node* createList()//headNode里不存放数据
    {
    	struct Node* headNode = (struct Node*)malloc(sizeof(struct Node));//为节点申请内存
    	//初始状态headNode的前指针指向headNode(本身),headNode的后指针指向headNode(本身)
    	headNode->front = headNode;
    	headNode->tail = headNode;
    	return headNode;
    }
    

    图示:
    在这里插入图片描述

    (三):插入

    1:头插

    做好连线即可……

    //1.头插
    void insertNodeByFront(struct Node* headNode, int data)
    {
    	struct Node* newNode = createNode(data);
    	struct Node* nextNode = headNode->tail;//记录一下首节点的下一位
    	//做连线  四条线
    	headNode->tail = newNode;//首节点的后指针指向新节点
    	newNode->front = headNode;//新节点的前指针指向首节点
    	
    	newNode->tail = nextNode;//新节点的后指针指向首节点的下一位
    	nextNode->front = newNode;//首节点的下一位前指针指向新节点
    }
    

    2:尾插

    做好连线即可……
    但是注意一点:这里的循环链表中headNode->front即为尾节点

    //2.尾插
    void insertNodeByTail(struct Node* headNode, int data)
    {
    	struct Node* newNode = createNode(data);
    	struct Node* tailNode = headNode->front;//首节点的前指针的指向尾节点
    	//连接四根线
    	tailNode->tail = newNode;//尾节点的后指针指向新节点
    	newNode->front = tailNode;//新节点的前指针指向尾节点
    	
    	headNode->front = newNode;//首节点的前指针指向新节点
    	newNode->tail = headNode;//新节点的后指针指向头节点
    }
    

    3:指定位置插入

    当headNode的前后指针都指向headNode(本身)时。链表为空

    错点:刚开始写时,我以为headNode的前后指针的指向一样时即可判断为空,但是后来打印时有错误,即链表中有一个数据节点时会有错误。因为链表中有一个数据节点时,headNode的前后指针都指向该数据节点。故headNode->front==headNode->tail并不是判断其为空的条件

    //指定位置插入
    void insertNodeByAppoin(struct Node* headNode, int posData, int data)
    {
    	if (headNode->front == headNode && headNode->tail == headNode)//当头指针和尾指针指向headNode时,说明为初始状态,链表为空。
    	{
    		printf("链表为NULL,无法插入\n");
    	}
    	else
    	{
    		struct Node* posFrontNode = headNode;
    		struct Node* posNode = headNode->tail;
    		while (posNode->data != posData)
    		{
    			posFrontNode = posNode;
    			posNode = posNode->tail;
    			while (posNode == headNode)
    			{
    				break;
    			}
    		}
    		if (posNode == headNode)
    		{
    			printf("未找到指定位置,无法做指定位置插入\n");
    		}
    		else
    		{
    			struct Node* newNode = createNode(data);//创建节点
    			//做连线,四条连线
    			posFrontNode->tail = newNode;//指定位置前节点的后指针指向新节点
    			newNode->front = posFrontNode;//新节点的前指针指向指定位置节点
    			posNode->front = newNode;//指定位置节点的前指针指向新节点
    			newNode->tail = posNode;//新节点的后指针指向指定位置节点
    		}
    	}
    }
    

    (四):删除

    1:头删

    //4.头删除
    void deleteNodeByHead(struct Node* headNode)
    {
    	if (headNode->front == headNode&&headNode->tail==headNode)//当头指针和尾指针指向headNode时,说明为初始状态,链表为空。
    	{
    		printf("链表为NULL,无法进行删除\n");
    	}
    	else
    	{
    		struct Node* nextNode = headNode->tail;//记录一下第一个数据节点
    		//做连接:头节点的尾指针指向nextNode的tail
    		headNode->tail = nextNode->tail;
    		//nextNode->tail的头指针指向headNode
    		nextNode->tail->front = headNode;
    		//清理第一个数据节点
    		free(nextNode);
    		nextNode = NULL;
    	}
    }
    

    2:尾删

    //5.尾删除
    void deleteNodeByTail(struct Node* headNode)
    {
    	if (headNode->front == headNode && headNode->tail == headNode)//当头指针和尾指针指向headNode时,说明为初始状态,链表为空。
    	{
    		printf("链表为NULL,无法进行删除。\n");
    	}
    	else
    	{
    		struct Node* tailNode = headNode->front;//找到尾节点,headNode的前指针就是尾节点
    		tailNode->front->tail = headNode;
    		headNode->front = tailNode->front;
    		free(tailNode);
    		tailNode = NULL;
    	}
    }
    

    3:指定位置删除

    注意:posNode比对一圈后回到headNode则说明没有找到指定数据。

    //6.指定位置删除
    void deleteNodeByAppoin(struct Node* headNode, int posData)
    {
    	struct Node* posFrontNode = headNode;
    	struct Node* posNode = headNode->tail;
    	if (posNode->data == posData)//首个数据节点的数据等于指定数据时,头删除
    	{
    		deleteNodeByHead(headNode);
    	}
    	else
    	{
    		while (posNode->data != posData)
    		{
    			posFrontNode = posNode;
    			posNode = posNode->tail;
    			if (posNode == headNode)//循环一圈回到headNode,说明没有指定数据。退出
    			{
    				break;
    			}
    		}
    		if (posNode == headNode)//判断posNode的状态
    		{
    			printf("没有找到指定数据,无法进行删除。\n");
    		}
    		else
    		{
    			posFrontNode->tail = posNode->tail;
    			posNode->tail->front = posFrontNode;
    			free(posNode);
    			posNode = NULL;
    		}
    	}
    }
    
    

    (五):打印

    有前后指针,使得顺序逆序遍历很方便

    //打印测试
    //通过后指针打印遍历
    void printListByTail(struct Node* headNode)
    {
    	if (headNode->front == headNode&&headNode->tail==headNode)//当头指针和尾指针指向headNode时,说明为初始状态,链表为空。
    	{
    		printf("表为NULL,无法打印\n");
    		return;
    	}
    	struct Node* pMove = headNode->tail;
    	printf("通过后指针打印\n");
    	while (pMove != headNode)
    	{
    		printf("%d ", pMove->data);
    		pMove = pMove->tail;
    	}
    	printf("\n"); 
    }
    //通过前指针打印遍历
    void printListByFront(struct Node* headNode)
    {
    	if (headNode->front == headNode&&headNode->tail==headNode)//当头指针和尾指针指向headNode时,说明为初始状态,链表为空。
    	{
    		printf("表为NULL,无法打印\n");
    		return;
    	}
    	struct Node* pMove = headNode->front;
    	printf("通过后指针打印\n");
    	while (pMove != headNode)
    	{
    		printf("%d ", pMove->data);
    		pMove = pMove->front;
    	}
    	printf("\n");
    }
    

    (六):完整测试代码

    //双向循环链表
    #include<stdio.h>
    #include<stdlib.h>
    struct Node
    {
    	int data;
    	struct Node* front;
    	struct Node* tail;
    };
    //创建节点
    struct Node* createNode(int data)
    {
    	struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    	newNode->data = data;
    	newNode->front = NULL;
    	newNode->tail = NULL;
    	return newNode;
    }
    //创建链表
    struct Node* createList()//headNode里不存放数据
    {
    	struct Node* headNode = (struct Node*)malloc(sizeof(struct Node));
    	headNode->front = headNode;
    	headNode->tail = headNode;
    	return headNode;
    }
    //1.头插
    void insertNodeByFront(struct Node* headNode, int data)
    {
    	struct Node* newNode = createNode(data);
    	struct Node* nextNode = headNode->tail;//记录一下首节点的下一位
    	//做连线  四条线
    	headNode->tail = newNode;//首节点的后指针指向新节点
    	newNode->front = headNode;//新节点的前指针指向首节点
    	newNode->tail = nextNode;//新节点的后指针指向首节点的下一位
    	nextNode->front = newNode;//首节点的下一位前指针指向新节点
    }
    //2.尾插
    void insertNodeByTail(struct Node* headNode, int data)
    {
    	struct Node* newNode = createNode(data);
    	struct Node* tailNode = headNode->front;//首节点的前指针的指向尾节点
    	//连接四根线
    	tailNode->tail = newNode;//尾节点的后指针指向新节点
    	newNode->front = tailNode;//新节点的前指针指向尾节点
    	headNode->front = newNode;//首节点的前指针指向新节点
    	newNode->tail = headNode;//新节点的后指针指向头节点
    }
    //3.指定位置插入
    void insertNodeByAppoin(struct Node* headNode, int posData, int data)
    {
    	if (headNode->front == headNode && headNode->tail == headNode)//当头指针和尾指针指向headNode时,说明为初始状态,链表为空。
    	{
    		printf("链表为NULL,无法插入\n");
    	}
    	else
    	{
    		struct Node* posFrontNode = headNode;
    		struct Node* posNode = headNode->tail;
    		while (posNode->data != posData)
    		{
    			posFrontNode = posNode;
    			posNode = posNode->tail;
    			while (posNode == headNode)
    			{
    				break;
    			}
    		}
    		if (posNode == headNode)
    		{
    			printf("未找到指定位置,无法做指定位置插入\n");
    		}
    		else
    		{
    			struct Node* newNode = createNode(data);//创建节点
    			//做连线,四条连线
    			posFrontNode->tail = newNode;//指定位置前节点的后指针指向新节点
    			newNode->front = posFrontNode;//新节点的前指针指向指定位置节点
    			posNode->front = newNode;//指定位置节点的前指针指向新节点
    			newNode->tail = posNode;//新节点的后指针指向指定位置节点
    		}
    	}
    }
    //删除
    //4.头删除
    void deleteNodeByHead(struct Node* headNode)
    {
    	if (headNode->front == headNode&&headNode->tail==headNode)//当头指针和尾指针指向headNode时,说明为初始状态,链表为空。
    	{
    		printf("链表为NULL,无法进行删除\n");
    	}
    	else
    	{
    		struct Node* nextNode = headNode->tail;//记录一下第一个数据节点
    		//做连接:头节点的尾指针指向nextNode的tail
    		headNode->tail = nextNode->tail;
    		//nextNode->tail的头指针指向headNode
    		nextNode->tail->front = headNode;
    		//清理第一个数据节点
    		free(nextNode);
    		nextNode = NULL;
    	}
    }
    //5.尾删除
    void deleteNodeByTail(struct Node* headNode)
    {
    	if (headNode->front == headNode && headNode->tail == headNode)//当头指针和尾指针指向headNode时,说明为初始状态,链表为空。
    	{
    		printf("链表为NULL,无法进行删除。\n");
    	}
    	else
    	{
    		struct Node* tailNode = headNode->front;//找到尾节点,headNode的前指针就是尾节点
    		tailNode->front->tail = headNode;
    		headNode->front = tailNode->front;
    		free(tailNode);
    		tailNode = NULL;
    	}
    }
    //指定位置删除
    void deleteNodeByAppoin(struct Node* headNode, int posData)
    {
    	struct Node* posFrontNode = headNode;
    	struct Node* posNode = headNode->tail;
    	if (posNode->data == posData)//首个数据节点的数据等于指定数据时,头删除
    	{
    		deleteNodeByHead(headNode);
    	}
    	else
    	{
    		while (posNode->data != posData)
    		{
    			posFrontNode = posNode;
    			posNode = posNode->tail;
    			if (posNode == headNode)//循环一圈回到headNode,说明没有指定数据。退出
    			{
    				break;
    			}
    		}
    		if (posNode == headNode)//判断posNode的状态
    		{
    			printf("没有找到指定数据,无法进行删除。\n");
    		}
    		else
    		{
    			posFrontNode->tail = posNode->tail;
    			posNode->tail->front = posFrontNode;
    			free(posNode);
    			posNode = NULL;
    		}
    	}
    }
    
    //打印测试
    //通过后指针打印遍历
    void printListByTail(struct Node* headNode)
    {
    	if (headNode->front == headNode&&headNode->tail==headNode)//当头指针和尾指针指向headNode时,说明为初始状态,链表为空。
    	{
    		printf("表为NULL,无法打印\n");
    		return;
    	}
    	struct Node* pMove = headNode->tail;
    	printf("通过后指针打印\n");
    	while (pMove != headNode)
    	{
    		printf("%d ", pMove->data);
    		pMove = pMove->tail;
    	}
    	printf("\n"); 
    }
    //通过前指针打印遍历
    void printListByFront(struct Node* headNode)
    {
    	if (headNode->front == headNode&&headNode->tail==headNode)//当头指针和尾指针指向headNode时,说明为初始状态,链表为空。
    	{
    		printf("表为NULL,无法打印\n");
    		return;
    	}
    	struct Node* pMove = headNode->front;
    	printf("通过后指针打印\n");
    	while (pMove != headNode)
    	{
    		printf("%d ", pMove->data);
    		pMove = pMove->front;
    	}
    	printf("\n");
    }
    int main()
    {
    	//创建链表
    	struct Node* list = createList();
    	
    	//尾插法
    	insertNodeByTail(list, 3);
    	insertNodeByTail(list, 2);
    	insertNodeByTail(list, 1);
    	printListByTail(list);
    	printListByFront(list);
    	printListByTail(list);
    
    	//头插法
    	insertNodeByFront(list, 4);
    	insertNodeByFront(list, 5);
    	insertNodeByFront(list, 6);
    	printListByTail(list);
    
    	//指定位置插入
    	insertNodeByAppoin(list, 6, 7);
    	printListByTail(list);
    
    	//头删
    	deleteNodeByHead(list);
    	deleteNodeByHead(list);
    	printListByTail(list);
    
    	//尾删
    	deleteNodeByTail(list);
    	deleteNodeByTail(list);
    	printListByTail(list);
    
    	//指定位置删除
    	deleteNodeByAppoin(list, 4);
    	deleteNodeByAppoin(list, 3);
    	deleteNodeByAppoin(list, 5);
    	printListByTail(list);
    	return 0;
    }
    

    未完持续更新数据结构……

    展开全文
  • 双向链表的插入删除

    万次阅读 多人点赞 2018-09-21 17:23:50
    双向链表的插入 第一步:首先找到插入位置,节点 s 将插入到节点 p 之前 第二步:将节点 s 的前驱指向节点 p 的前驱,即 s-&gt;prior = p-&gt;prior; 第三步:将节点 p 的前驱后继指向节点 s 即 p-&...
  • 通过翻阅资料知道双向链表是指在前驱和后继方向都能遍历的线性表 自己在软件上写了几遍,代码如下 1、双向链表的定义 typedef int ElemType; typedef struct node{ ElemType data; struct node *lef
  • 感谢您的阅读与点赞!欢迎关注:「大猫玩程序」,查看C语言...所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。特点:1)在数据结构中具有双向指针2)插入、删除数据的时候需要考虑...
  • 1.双向循环链表的存储结构在单向链表中,从某一个结点出发可以访问到它的后继结点,但是不能访问到它的前驱结点,而在单向循环链表中,可从某一个结点出发访问到表中任意一个结点,但在访问它的前驱结点时必须通过头...
  • 双向链表和单向链表

    千次阅读 2020-02-04 12:59:16
    所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点,这种数据结构形式使得双向链表在查找时更加方便,特别是大量数据的遍历。由于双向链表具有对称性,能方便地完成各种插入、删除等...
  • 所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。#pragmaonce//只包含一次头文件#includeusingnamespacestd;//使用库函数swap#include#include#includetypedefintDataType;typede...
  • 相比于单项链表,双向链表有一个前驱指针...双向链表节点当双向链表为空表是,仅有一个头节点,且头节点的前驱和后继指针都指向其自身;空表head.png在非空表中,每个节点都有自己的前驱和后继,最后一个节点的后继...
  • 所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。 由于双向链表可以方便地实现正序和逆序两个方向的插入、查找等功能,在很多算法中经常被使用, ...
  • 所以我们从双向链表的任意一个结点开始都可以很方便的访问其前驱元素和后继元素。 双向链表的结构如下图所示: 双向链表的基本操作: 分析 双向链表的遍历,添加,修改,删除的操作思路 遍历:和单链表一样,只是...
  • 找到还不错的双向链表代码,包含了基本函数实现     这几天做了笔试题发现双向链表这一块自己掌握很差...通过翻阅资料知道双向链表是指在前驱和后继方向都能遍历线性表 自己在软件上写了几遍,代码如...
  • 双向链表

    2020-07-16 21:59:08
    所以从双向链表的任意一个节点开始,都可以很方便的访问它的前驱节点和后继节点。 1.2双向链表示意图 1.3双向链表增删改查思路 双向链表比单向链表多了一个指向前一个节点的指针。 1.3.1尾部插入节点 (1)...
  • 双向链表 ...所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。 2.双向链表增删改查的核心操作分析 注意:在执行添加和删除操作时要判断当前结点是否为最后一个结点
  • 双向链表使用前驱指针以及后继指针 循环链表就是尾指针指向头 约瑟夫环问题:n个人围成一个圈,指定一个数字v,从第一个人开始报数,每轮报到v选手出局,由下一个人接着从头开始报,最后一个人是赢家。其中n>1,v...
  • 数据结构—双向链表的基本操作

    千次阅读 多人点赞 2019-06-20 22:37:32
    双向链表的插入和删除操作和单链表是有区别的:双向链表的插入和删除操作要修改指向前驱和指向后继的指针。 2.双向链表的删除:删除指定位置 i 的元素 1.判断输入的删除的位置是否合法,1<=i<=表长 2.顺着...
  • 所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。(1)定义双向链表的基本结构 代码如下:typedef struct _DOUBLE_LINK_NODE { int data; struct ...
  • 可以将左右孩子指针作为双向循环链表的前驱和后继指针。 我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表,第一个节点的前驱是最后一个节点,最后一个节点...
  • 单向链表和双向链表的优缺点及使用场景

    万次阅读 多人点赞 2018-09-28 16:16:39
    单向链表:只有一个指向下一个节点指针。 优点:单向链表增加删除节点简单...优点:可以找到前驱和后继,可进可退; 缺点:增加删除节点复杂,需要多分配一个指针存储空间。 适用于需要双向查找节点值情况。 ...
  • 双向链表的创建相关操作

    千次阅读 2014-08-30 21:34:58
    双向链表其实是单链表改进。  当我们对单链表进行操作时,有时你要对某个结点直接前驱进行操作时,又必须从表头开始查找。这是由单链表结点结构所限制。因为单链表每个结点只有一个存储直接后继结点地址...
  • 定义:双向链表是链表中一种,双向链表也叫双链表,它由多个节点组成,每个节点由一个数据域两个指针域组成,一个指针指向前驱元素,一个指向后继元素 双向链表一般用来构造循环链表,这个后面我们也会学习到 ...
  • 可以将左右孩子指针作为双向循环链表的前驱和后继指针。 为了让您更好地理解问题,以下面的二叉搜索树为例: 特别地,我们希望可以就地完成转换操作。当转化完成以后,树中节点的左指针需要指向前驱,树中节点...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,009
精华内容 403
关键字:

双向链表的前驱和后继