c++编程实现一个双向链表

系统管理员 2022-12-01 03:57 156阅读 0赞

自己发现在学习链表、双向链表、二叉树的时候，其实是有一定的规律的。

例如**链表中节点的定义：**

typedef struct node
    { 
    	int data;
    	node* next;
    }Node;

**双向链表中节点的定义：**

typedef struct node
    { 
    	int data;
    	node* left;
    	node* right;
    }DDNode;

**二叉树节点的定义：**

typedef struct node
    { 
    	int data;
    	node* parent;
    	node* left;
    	node* right;
    }Node;

可以看到节点定义内部的指针呈现1-2-3数目增加，关于链表的操作都是一些基本的操作，在这里不做赘述，直接上c++编程实现一个双向链表代码：

每天一点代码，冲冲冲！

/******************************************************** *[abstract] Double direction list *[date] 2020/8/25 21：16 *[author] LowHand ********************************************************/
    
    #include <iostream>
    #include <cstdlib>
    
    using namespace std;
    
    /* This is used to create a node. */
    typedef struct node
    { 
    	int data;
    	node* left;
    	node* right;
    }DDNode;
    
    /******************************************************** * Three functions are needed to create a DDList: * [1] CreateNode(): create and return an node. * [2] CreateDDList(): create DDList. * [3] InsertNode(); insert value. ********************************************************/
    
    DDNode *CreateNode(int data)
    { 
    	using namespace std;
    	DDNode *Newnode = (DDNode*)malloc(sizeof(DDNode));
    	Newnode->data = data;
    	Newnode->left = Newnode->right = Newnode;
    
    	return Newnode;
    }
    
    DDNode *CreareDDList(int head)
    { 
    	DDNode* Newnode = (DDNode*)malloc(sizeof(DDNode));
    	Newnode->data = head;
    	Newnode->left = Newnode->right = Newnode;
    
    	return Newnode;
    }
    
    // insert new nodes at the end of list and return the front node.
    
    DDNode *InsertNode(DDNode* head, int data)
    { 
    	DDNode *node = CreateNode(data);
    	DDNode *p = head;
    	DDNode *q;
    
    	while (p != NULL)
    	{ 
    		q = p;
    		p = p->right;  // here we need to notice the direction.
    	}
    	q->right = p;
    	p->left = q;
    
    	return head;
    }
    // Fight for life。