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;  
}