C++双向链表习题讲解

c++双向链表习题讲解

#ifndef dbnode_h  
#define dbnode_h  
#include<iostream>  
using namespace std;  
  
//双向链表的定义、结构  
struct node  
{  
    int data;   //节点数据  
    node *left;  //前驱结点指针  
    node *right;  //后继节点指针  
};  
  
typedef node* dbnode;  
  
dbnode createdblist();  
//创建一个双向链表  
  
int getlength(dbnode head);  
//计算链表的长度  
  
void putout(const dbnode head);  
//输出链表  
  
dbnode findnode(const dbnode head,int data1);  
//找出数据data1的结点  
  
dbnode insertnode(dbnode head,int data2,int k);  
//在第k个结点后插入一个结点。结点的数据是data2  
  
  
  
#endif   

#include"dbnode.h"  
#include<iostream>  
using namespace std;  
  
dbnode createdblist()  
{  
    int x,i=0;  
    dbnode p;  
    p = new node;  
    dbnode q;  
    q = new node;   
    dbnode head;  
    head = new node;  
    cout<<"输入结点数据，输入为0结束输入"<<endl;  
    cin>>x;  
    if(x==0)  
    {  
        return null;  
    }  
    p->data=x;  
    head->right=p;  
    head->left=null;  
    p->left=head;  
    q=p;  
    p = new node;  
    cout<<"输入结点数据，输入为0结束输入"<<endl;  
    cin>>x;  
    while(x!=0)  
    {  
  
        p->data=x;  
        q->right=p;  
        p->left=q;  
        p->right=null;  
        q=p;  
        p = new node;  
        cout<<"输入结点数据，输入为0结束输入"<<endl;  
        cin>>x;  
    }  
    return head;      
}  

#include<iostream>  
#include"dbnode.h"  
using namespace std;  
  
void putout(const dbnode head)  
{  
    dbnode node;  
    node=new node;  
    dbnode p;  
    if(head == null)  
    {  
        return;   
    }  
    node = head->right;  
    while(node != null)  
    {  
        cout<<node->data<<endl;  
        node=node->right;  
        //node=p;  
  
    }  
}  

#include<iostream>  
#include"dbnode.h"  
using namespace std;  
int getlength(const dbnode head)  
{  
    dbnode p=null;  
    int n=0;  
    if(head==null)  
    {  
        return null;  
    }  
    p=head;  
    while(p->right != null)  
    {  
        ++n;  
        p=p->right;  
    }  
    return n;  
}  

#include<iostream>  
#include"dbnode.h"  
using namespace std;  
int main()  
{  
    dbnode head;  
    //双向链表  
  
    head=createdblist();  
    //创建一个双向链表  
  
    putout(head);  
    //输出一个双向链表  
  
    int n=getlength(head);  
    cout<<"双向链表的长度："<<n<<endl;  
}