精华内容
下载资源
问答
  • 双向链表C++

    2012-09-17 16:19:24
    #include "stdafx.h" #include #include using namespace std; #define ERROR 0 #define OVERFLOW -1 #define OK 0x1 typedef int Status; typedef int ElemType; typedef struct DNode{ ...struct
    #include "stdafx.h"
    #include <iostream>
    #include <stdio.h>
    using namespace std;

    #define ERROR  0
    #define OVERFLOW  -1
    #define OK 0x1

    typedef int Status;
    typedef int ElemType;

    typedef struct DNode{
    struct DNode *front;
    ElemType data;
    struct DNode *next;
    }DNode,*LinkList;

    LinkList GetDNode(LinkList &L,int i);
    Status InitList(LinkList &L);
    Status ListInsert(LinkList &L,int i, ElemType e);
    LinkList GetDNode(LinkList &L,int i);
    int ListLength(LinkList &L);

    // Init Double list
    Status InitList(LinkList &L)
    {
    L =(LinkList)malloc(sizeof(DNode));
    if(!L)  return OVERFLOW;
    L->next = NULL;
    return OK;
    }

    // Insert double list
    Status ListInsert(LinkList &L,int i, ElemType e)
    {
    LinkList P,S;
    if(i<1 || i>ListLength(L)+1)  return ERROR;
    P = GetDNode(L,i-1);
    S = (LinkList)malloc(sizeof(DNode));
    if(!S)  return OVERFLOW;

    S->next  = P->next;
    P->next = S;
    S->data = e;
    S->front = P;
    if(S->next)
    S->next->front = S;
    return OK;
    }


    // Get the pre-Node of the current node
    LinkList GetDNode(LinkList &L,int i)
    {
    LinkList P;
    P = L;
    for(int j=1;j<=i;++j)
    {
    P = P->next;
    }
    return P;
    }

    // Delete one of the double node
    Status ListDelete(LinkList &L,int i)
    {
    LinkList P,P1;
    if(i<1 || i>ListLength(L))
    return ERROR;
    P = GetDNode(L,i-1);
    P1 = P->next;
    if(P->next->next)  // delete the non-last node
    {
    P->next = P1->next; //netx
    P1->next->front = P;
    free(P1);
    }
    else
    {
    P->next = NULL;
    P1->front = NULL;
    free(P1);
    }

    return OK;
    }

    // calculate the length of double list
    int ListLength(LinkList &L)
    {
    int i = 0;
    LinkList P;
    P = L->next;
    while(P)
    {
    P = P->next;
    ++i;
    }
    return i;
    }


    void Travese(LinkList &L, void (*visit)(ElemType e))
    {
    LinkList P;
    P = L->next;
    while(P)
    {
    visit(P->data);
    P = P->next;
    }
    }


    void print(ElemType e)
    {
    printf("%d\n",e);
    }


    int _tmain(int argc, _TCHAR* argv[])
    {
    LinkList head;
    InitList(head);
    for(int i=1;i<=5;++i)
    ListInsert(head,i,2*i);
    Travese(head,print);
    ListInsert(head, 4,20);
    Travese(head,print);

    ListDelete(head, 5);
    Travese(head,print);
    return 0;
    }
    展开全文
  • 双向链表c++.zip

    2020-08-03 13:47:25
    大二时期的课设,利用c++实现了双向链表的增删改查,适合于大学生或者刚接触此门语言的小白使用,代码都是最基础的,没有调用库直接自己编辑的
  • 双向链表C++实现代码

    2019-09-06 16:26:32
    1、双向链表和单链表 单链表是在每个节点只有一个指向下一节点的指针,所以遍历时候需要从头开始,而双向链表的每个节点有两个指针,一个指向下一节点,一个指向上一结点(头结点的上一节点给个NULL) 双向链表的...

    1、双向链表和单链表

    单链表C++实现代码
    单链表是在每个节点只有一个指向下一节点的指针,所以遍历时候需要从头开始,而双向链表的每个节点有两个指针,一个指向下一节点,一个指向上一结点(头结点的上一节点给个NULL)
    双向链表的实现其实也是对指针再一次进行联系,帮助加深指针咯,反正感觉单链表去存东西够用了。

    #include <string>
    #include <iostream>
    using namespace std;
    
    typedef int DataType;
    
    class Node
    {
    public:
    	DataType data;
    	Node *next;
    	Node *prev;
    };
    
    class TwoWayLinkList
    {
    public:
    	TwoWayLinkList();
    	~TwoWayLinkList();
    	int CreateTwoWayLinkList(int size);
    	int BYETwoWayLinkList();/*销毁*/
    	int TravalTwoWayLinkList();/*遍历链表*/
    	int InsertTwoWayLinklList(Node *data, int n);/*头插传0/1,尾插传this->size+1*/
    	int DeleteTwoWayLinklist(int n);/*删除节点*/
    
    	int GetLen();
    	bool IsEmply();
    
    	Node *head;
    	int size;
    };
    
    TwoWayLinkList::TwoWayLinkList()
    {
    	head = new Node;
    	head->data = 8888;/*我在头结点不存数据的,只是一个链表的开始标记而已*/
    	head->next = NULL;
    	head->prev = NULL;/*头节点没prev指针*/
    	size = 0;
    }
    
    TwoWayLinkList::~TwoWayLinkList()
    {
    	delete head;
    }
    
    int TwoWayLinkList::CreateTwoWayLinkList(int size)
    {
    	if (size < 0) {
    		printf("error\n");
    		return -1;
    	}
    	Node *ptemp = NULL;
    	Node *pnew = NULL;
    
    	this->size = size;
    	ptemp = this->head;
    	for (int i = 0; i<size; i++)
    	{
    		pnew = new Node;
    		pnew->next = NULL;
    		pnew->prev = NULL;
    		cout << "输入第" << i + 1 << "个节点值" << endl;
    		cin >> pnew->data;
    		ptemp->next = pnew;
    		pnew->prev = ptemp;
    		ptemp = pnew;
    	}
    	cout << "Create Completion" << endl;
    	return 0;
    }
    
    int TwoWayLinkList::BYETwoWayLinkList()
    {
    	Node *ptemp;
    	if (this->head == NULL) {
    		cout << "The list is empty" << endl;
    		return -1;
    	}
    	while (this->head)
    	{
    		ptemp = head->next;
    		free(head);
    		head = ptemp;
    	}
    	cout << "Destruction List Completion" << endl;
    	return 0;
    }
    
    int TwoWayLinkList::TravalTwoWayLinkList()
    {
    	Node *ptemp = this->head->next;
    	if (this->head == NULL) {
    		cout << "The list is empty" << endl;
    		return -1;
    	}
    	while (ptemp)
    	{
    		cout << ptemp->data << "->";
    		ptemp = ptemp->next;
    	}
    	cout << "NULL" << endl;
    	return 0;
    }
    
    int TwoWayLinkList::InsertTwoWayLinklList(Node *data, int n)
    {
    	Node *ptemp;
    	if (this->head == NULL) {
    		cout << "The list is empty" << endl;
    		return -1;
    	}
    	if (data == NULL) {
    		cout << "The insertion node is NULL" << endl;
    		return -1;
    	}
    /*不同插入方法*/
    	//头插
    	if (n<2) {
    		Node *pnew = new Node;
    		pnew->data = data->data;
    		pnew->next = this->head->next;
    		pnew->prev = this->head;
    		this->head->next->prev = pnew;
    		this->head->next = pnew;
    		this->size++;
    		return 0;
    	}
    	//尾插
    	if (n > this->size) {
    		ptemp = this->head;
    		while (ptemp->next != NULL) {
    			ptemp = ptemp->next;
    		}
    		Node *pnew = new Node;
    		pnew->data = data->data;
    		pnew->next = NULL;
    		pnew->prev = ptemp;
    		ptemp->next = pnew;
    		this->size++;
    		return 0;
    	}
    	//中间插
    	else {
    		ptemp = this->head;
    		for (int i = 1; i < n; i++) {
    			ptemp = ptemp->next;
    		}
    		Node *pnew = new Node;
    		pnew->data = data->data;
    		pnew->next = ptemp->next;
    		pnew->prev = ptemp;
    		ptemp->next->prev = pnew;
    		ptemp->next = pnew;
    		this->size++;
    		return 0;
    	}
    }
    
    int TwoWayLinkList::DeleteTwoWayLinklist(int n)
    {
    	Node *ptemp;
    	Node *ptemp2;
    	if (n > this->size) {
    		cout << "The Input size is Go beyond" << endl;
    		return -1;
    	}
    	//删头节点
    	if (n < 2) {
    		ptemp = this->head->next;
    		this->head->next = ptemp->next;
    		ptemp->next->prev = this->head;
    		free(ptemp);
    		this->size--;
    		return 0;
    	}
    	//尾部删除
    	if (n == this->size) {
    		ptemp = this->head;
    		for (int i = 1; i < this->size; i++) {
    			ptemp = ptemp->next;
    		}
    		ptemp2 = ptemp->next;
    		ptemp->next = NULL;
    		free(ptemp2);
    		this->size--;
    		return 0;
    	}
    	//中间删除
    	else
    	{
    		ptemp = this->head;
    		for (int i = 1; i < n; i++) {
    			ptemp = ptemp->next;
    		}
    		ptemp2 = ptemp->next;
    		ptemp->next = ptemp2->next;
    		ptemp2->next->prev = ptemp;
    		free(ptemp2);
    		this->size--;
    		return 0;
    	}
    }
    
    int TwoWayLinkList::GetLen()
    {
    	return this->size;
    }
    
    bool TwoWayLinkList::IsEmply()
    {
    	if (this->head->next == NULL) {
    		return true;
    	}
    	else {
    		return false;
    	}
    }
    
    void main(void)
    {
    	Node temp;
    	temp.data = 9;
    	temp.next = NULL;
    	temp.prev = NULL;
    
    	TwoWayLinkList list;
    	TwoWayLinkList *plist = &list;
    	plist->CreateTwoWayLinkList(5);
    	plist->TravalTwoWayLinkList();
    	plist->InsertTwoWayLinklList(&temp, 0);
    	plist->TravalTwoWayLinkList();
    	plist->InsertTwoWayLinklList(&temp, 3);
    	plist->TravalTwoWayLinkList();
    	plist->InsertTwoWayLinklList(&temp, plist->size);
    	plist->TravalTwoWayLinkList();
    	plist->DeleteTwoWayLinklist(0);
    	plist->TravalTwoWayLinkList();
    	plist->DeleteTwoWayLinklist(3);
    	plist->TravalTwoWayLinkList();
    	system("pause");
    }
    
    

    有时间需要把树的结构实现实现

    展开全文
  • 双向链表C++实现

    2020-01-07 14:26:22
    DoubleLinkList.h #pragma once #ifndef DOUBLELINKLIST_H ...//双向链表,下面英文名字写错了 #include<iostream> using std::cout; using std::endl; using std::cin; typedef int ElemType; cla...

    DoubleLinkList.h

    #pragma once
    #ifndef DOUBLELINKLIST_H
    #define DOUBLELINKLIST_H
    //双向链表,下面英文名字写错了
    #include<iostream>
    using std::cout;
    using std::endl;
    using std::cin;
    typedef int ElemType;
    
    class Node
    {
    public:
    	Node(Node* left=nullptr,Node* right=nullptr):prior(left),next(right){}
    	Node* prior;
    	Node* next;
    	ElemType data;
    };
    
    
    class doubleLinkList
    {
    public:
    	doubleLinkList();
    	~doubleLinkList();
    	bool empty();//查看是否为空表
    	void getElem(int nPos, ElemType& elem);//获得第nPos位置的元素值,并返回给elem
    	bool findElem(ElemType elem);//查找列表中是否有elem值d的元素
    	void insert(ElemType elem);//默认在列表尾部插入elem元素
    	void insert(int nPos, ElemType elem);//在第nPos位置后插入值为elem的元素
    	void remove(int nPos, ElemType& elem);//删除第nPos位置的元素,并将其值返回给elem元素
    	void remove();//默认删除尾部的元素
    	int length();//返回列表长度
    	void print();//打印列表
    private:
    	Node* head;
    };
    #endif // !DOUBLELINKLIST_H
    

    DoubleLinkList.cpp

    #include"DoubleLinkList.h"
    
    //构造函数,建立一个空表,双向链表的空表定义是前驱和后驱都指向头指针
    doubleLinkList::doubleLinkList(){
    	head = new Node;//为head分配内存
    	if (head == nullptr) {
    		cout << "分配内存失败" << endl;
    		return;
    	}
    	head->next = head;
    	head->prior = head;
    }
    
    //析构函数
    doubleLinkList::~doubleLinkList(){
    	if (!empty())
    	{
    		Node* p = head->next;
    		Node* q = nullptr;
    		while (p!=head)
    		{
    			q = p;
    			p = p->next;
    			delete q;
    		}
    	}
    	delete head;
    }
    
    //查看是否为空表
    bool doubleLinkList::empty(){
    	if (head->next==head && head->prior==head)
    		return true;
    	return false;
    }
    
    //返回列表长度
    int doubleLinkList::length() {
    	int Index = 0;
    	if (!empty())
    	{		
    		Node* p = head->next;
    		while (p!=head)
    		{
    			++Index;
    			p = p->next;
    		}
    		return Index;
    	}
    	return Index;
    }
    
    //获得第nPos位置的元素值,并返回给elem
    void doubleLinkList::getElem(int nPos, ElemType& elem){
    	if (nPos < 0) {
    		cout << "输入位置不得小于0,请重新输入位置" << endl;
    		return;
    	}
    	else if(empty()){
    		cout << "列表为空" << endl;
    		return;
    	}
    	Node* p = head->next;
    	int Index = 0;
    	while (p!=head && Index<nPos)
    	{
    		p = p->next;
    		++Index;
    	}
    	if (p == head)
    	{
    		if (Index == nPos) {//如果恰好两个条件都满足,即在末尾的元素恰好是npos
    			elem = p->prior->data;
    			return;
    		}
    		cout << "输入位置过大,请重新输入" << endl;
    		return;
    	}
    	elem = p->prior->data;//nPos位置的元素在当前p的上一个节点
    }
    
    //查找列表中是否有elem值的元素
    bool doubleLinkList::findElem(ElemType elem) {
    	if (!empty())
    	{
    		Node* p = head->next;
    		while (p!=head)
    		{
    			if (p->data == elem)
    				return true;
    			p = p->next;
    		}
    	}
    	return false;
    }
    
    //默认在列表尾部插入elem元素
    void doubleLinkList::insert(ElemType elem) {
    	Node* q = (Node*)new Node[1];
    	q->data = elem;
    	if (empty()){
    		Node* p = head;
    		p->next = q;//先排后继,按箭头顺序赋值
    		q->next = head;
    		head->prior = q;//再排后继,按箭头顺序赋值
    		q->prior = head;
    	}
    	else {
    		Node* p = head->prior;				
    		head->prior = q;//先排前继,按箭头顺序赋值
    		q->prior = p;
    		p->next = q;//先排后继,按箭头顺序赋值
    		q->next = head;
    	}
    }
    
    //在第nPos位置后插入值为elem的元素
    void doubleLinkList::insert(int nPos, ElemType elem) {
    	if (nPos < 0) {
    		cout << "输入位置不得小于0,请重新输入位置" << endl;
    		return;
    	}
    	int L = length();
    	int Index = 1;
    	Node* q = (Node*)new Node[1];
    	if (nPos <= L)
    	{
    		Node* p = head->next;
    		q->data = elem;
    		while (p != head && Index < nPos) {//大于等于两个元素时会有移动
    			++Index;
    			p = p->next;
    		}
    		if (L = 0) {//空表插入
    			head->next = q;//先排后继,按箭头顺序赋值
    			q->next = head;
    			head->prior = q;//再排后继,按箭头顺序赋值
    			q->prior = head;
    		}
    		else if (Index == nPos && p->next == head) {//说明要在尾部结点插入元素,在不为空表时
    			Node* s = head->prior;
    			head->prior = q;//先排前继,按箭头顺序赋值
    			q->prior = s;
    			s->next = q;//先排后继,按箭头顺序赋值
    			q->next = head;
    		}
    		else if (nPos == 0) {//在0位置后插入元素,头部插入
    			head->next = q;//先排后继
    			q->next = p;
    			p->prior = q;
    			q->prior = head;
    		}
    		else //非尾部,非头部插入
    		{
    			q->next = p->next;//逆序
    			p->next = q;
    			q->prior = p;
    			q->next->prior = q;
    		}
    	}
    	else
    		cout << "输入位置过大,请重新输入位置" << endl;
    }
    
    //删除第nPos位置的元素,并将其值返回给elem元素
    void doubleLinkList::remove(int nPos, ElemType& elem) {
    	if (!empty() && nPos > 0) {
    		int Index = 1;
    		int L = length();
    		if (nPos <= L)
    		{
    			Node* p = head->next;
    			while (p != head && Index < nPos) {//两个元素时
    				++Index;
    				p = p->next;
    			}
    			elem = p->data;//赋值
    			if (L>1)//一般情况,即大于一个元素时
    			{
    				p->prior->next = p->next;
    				p->next->prior = p->prior;
    			}
    			else //仅有一个元素时
    			{
    				head->next = head;
    				head->prior = head;
    			}
    			delete p;
    			return;
    		}
    	}
    	cout << "列表为空!" << endl;
    	return;
    }
    
    //默认删除尾部的元素
    void doubleLinkList::remove() {
    	if (!empty()) {
    		if (head->next->next!=head)//大于一个元素时
    		{
    			Node* p = head->prior;
    			Node* q = head->prior->prior;
    			head->prior = q;
    			q->next = head;
    			delete p;			
    		}
    		else {//一个元素时
    			Node* p = head->prior;
    			head->next = head;
    			head->prior = head;
    			delete p;
    		}
    		return;
    	}
    	cout << "列表为空! 或者 输入位置不得小于等于0" << endl;
    	return;
    }
    
    //打印列表
    void doubleLinkList::print() {
    	cout << "列表元素是: ";
    	if (!empty())
    	{
    		Node* p = head;
    		while (p->next != head)
    		{
    			p = p->next;
    			cout << p->data << " ";	
    		}
    		cout << endl;
    	}
    	else
    	{
    		cout << "The list is empty!" << endl;
    		return;
    	}
    }

    main.cpp

    #include"DoubleLinkList.h"
    
    
    int main() 
    {
    	doubleLinkList list;
    	ElemType elem = 0;
    	cout << "列表是否为空:" << list.empty() << endl;
    	for (int i = 0; i < 10; i++)
    		list.insert(i);
    	list.print();
    	for (int i = 0; i < 10; i++) {
    		list.remove();
    		if(i==9)//查看仅剩一个元素时的删除结果
    			list.print();
    	}
    	cout << "分割线" << endl << endl;
    	list.insert(0,1);//空表插入
    	list.insert(1,2);//一个元素时插入
    	list.print();
    	list.insert(2, 3);//两个个元素时插入末尾
    	list.print();
    	list.insert(1, 4);//大于两个元素时插入中间
    	list.print();
    	cout << "分割线" << endl << endl;
    	list.remove(3, elem);
    	cout << "取得的元素是:" << elem << endl;
    	list.print();
    
    	return 1;
    }

     

    展开全文
  • 反转双向链表 c++

    2021-03-23 15:00:15
    和反转单向链表思路一样就是多反转一个方向 代码 #include<iostream> #include<vector> using namespace std; struct ListNode { int val; ListNode*next; ListNode*last; ListNode(intx):val(x),...

    和反转单向链表思路一样就是多反转一个方向

    代码

    #include<iostream>
    #include<vector>
    
    using namespace std;
    
    struct ListNode
    {
    	int val;
    	ListNode*next;
    	ListNode*last;
    	ListNode(intx):val(x), next(NULL),last(NULL){}
    }
    
    void doublePerverse(LisNode*head)
    {
    	ListNode*left=NULL;
    	ListNode*right=NULL;
    	LisNode*prehead=NULL;
    	ListNode*cur=head;
    	while(cur!=NULL)
    	{
    		right=cur->next;
    		if(right==NULL)
    		{
    			prehead=cur;
    		}
    		cur->next=left;
    		cur->last=right;
    		left=cur;
    		cur=right;
    	}
    }
    
    展开全文
  • 双向链表练习 构建有头结点和尾结点的双向链表,为了使交换的操作更加方便,所以增加了冗余的头结点和尾结点。 MyList实现的功能 方法 功能 add 添加元素,int类型 insert 指定下标,插入元素 swap ...
  • 双向链表c++实现

    千次阅读 2018-06-08 18:07:36
    cout 链表为空,oop!!" ; return 0; } else { if (ptr->doublelink_getlength(ptr) == 1) { ptr->root->next = NULL; ptr->length--; } else { node* deletenode = root->next; for ...
  • 按照中序遍历每个节点并加入链表更新Plast----将整个树分解成了无数的小树,然后将他们分别转化成了一小段一小段的双向链表,再利用pLast记录总的链表的末尾,然后将这些小段链表一个接一个地加到末尾。 class ...
  • 多级双向链表中,除了指向下一个节点和前一个节点指针之外,它还有一个子链表指针,可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项,依此类推,生成多级数据结构,如下面的示例所示。 给你位于...
  • 双向链表C++版本

    2017-03-01 21:04:21
    typedef int DataType; struct Node { Node(const DataType& data) : _data(data) , _pNext(NULL) , _pPre(NULL) {} DataType _data; Node* _pNext; Node* _pPre; }; class List ...
  • 430. 扁平化多级双向链表 多级双向链表中,除了指向下一个节点和前一个节点指针之外,它还有一个子链表指针,可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项,依此类推,生成多级数据结构,如...
  • DS_双向链表C++实现

    2021-01-25 21:52:58
    //如题所示 // DS_DoublyLinkedList.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" #include<iostream> using namespace std; template<class T> ...class DBLinkList
  • //判断链表是否为空 int length() const; //返回链表的长度 ElemType& operator[] (int index) throw(out_of_range);//返回index位置的值 private: class dbnode //结点类型 { public: dbnode() {} dbnode...
  • 题目:将二叉搜索树换成双向链表 思路:利用树的中序遍历(左根右),
  • 题目描述:将二叉排序树转换成一个有序的双向链表,要求:不能创建任何新的节点,只能通过调整指针的指向来实现; 解题思路:二叉排序树的中序遍历是一个递增的序列,根据这个特性,在二叉排序树的中序遍历过程...
  • 具体原理参考大话数据结构: #include<iostream> #include<...typedef struct Node//链表是由一个个节点组成所以这里单独定义这一类型方便在链表类中使用 { Datatype _data; struct N...
  • 树的递归操作说来说去就这么几个,这里很明显要用中序,因为要形成的是从小到大的双向链表。BST的中序就是从小到大的。 这里的中序就难在根那个地方的操作。递归函数需要一个指针的引用来作为前一个结点(pre),pre...
  • 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。 思路 本题和leetcode14有相似之处。 采用树的中序历遍的思想。 解答 /* struct TreeNode { ...
  • 题目描述 解法 dfs 很容易发现这题就是考察二叉搜素树的中序遍历是...可以发现只要对中间的主体做出改动,使遍历过程中的结点指针指向对应位置就能形成双向链表。 但题目还要求是循环链表,所以我们需要记录头结点和
  • 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。 思路1:递归——按照中序遍历 左根右,先找到左子树的最左头节点;将根节点连接到左子树最...

空空如也

空空如也

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

双向链表c++

c++ 订阅