雙鏈表的插入 刪除

雙鏈表其實 也沒什麼 只是多了一個前置鏈而已

雙鏈表的定義

[cpp] 
struct DNode 
{ 
    int data; 
    struct DNode *next; 
    struct DNode *pre; 
}; 
 

單鏈表的定義

[cpp] view plaincopy
struct DNode 
{ 
    int data; 
    struct DNode *next; 
}; 

其他的可以看上一篇博客  大致相同

[cpp]
#ifndef HEAD_H 
#define HEAD_H 
#include <iostream> 
using namespace std; 
#include <cassert> 
#include <cstdlib> 
#include <cmath> 
#include <sstream> 
#include <fstream> 
#include <string> 
#include <algorithm> 
#include <list> 
#include <queue> 
#include <vector> 
#include <deque> 
#include <stack> 
#include <bitset> 
#include <set> 
#include <map> 
#endif 
 
struct DNode 
{ 
    int data; 
    struct DNode *next; 
    struct DNode *pre; 
}; 
 
 
DNode *Creat() 
{   www.2cto.com
    DNode *head,*p,*s; 
    head=(DNode *)malloc(sizeof(DNode)); 
    p=head; 
    int temp; 
    while (cin>>temp&&temp) 
    { 
        s=(DNode *)malloc(sizeof(DNode)); 
        s->data=temp; 
        p->next=s; 
        s->pre=p; 
        p=s; 
    } 
    head=head->next; 
    p->next=NULL; 
    head->pre=NULL; 
    return (head); 
} 
 
DNode *Insert(DNode *&head,int num) 
{ 
    DNode *p,*s; 
    s=(DNode *)malloc(sizeof(DNode)); 
    s->data=num; 
    p=head; 
    while (NULL!=p->next&&num>p->data) 
    { 
        p=p->next; 
    } 
    if (num<=p->data) 
    { 
        if (NULL==p->pre) 
        { 
            s->next=head; 
            head->pre=s; 
            head=s; 
            head->pre=NULL; 
        }  
        else 
        { 
            s->pre=p->pre; 
            p->pre->next=s; 
            s->next=p; 
            p->pre=s; 
        } 
    }  
    else 
    { 
        p->next=s; 
        s->pre=p; 
        s->next=NULL; 
    } 
    return(head); 
} 
 
DNode *Del(DNode *&head,int num) 
{ 
    DNode *p; 
    p=head; 
    while (NULL!=p->next&&num!=p->data) 
    { 
        p=p->next; 
    } 
    if (num==p->data) 
    { 
        if (NULL==p->pre) 
        { 
            head=p->next; 
            p->next->pre=head; 
            free(p); 
        }  
        else if (NULL==p->next) 
        { 
            p->pre->next=NULL; 
            free(p); 
        } 
        else 
        { 
            p->pre->next=p->next; 
            p->next->pre=p->pre; 
            free(p); 
        } 
    }  
    else 
    { 
        cout<<num<<" cound not be found"<<endl; 
    } 
    return head; 
} 
 
void Display(DNode *head) 
{ 
    DNode *p; 
    p=head; 
    while (NULL!=p) 
    { 
        cout<<(p->data)<<" "; 
        p=p->next; 
    } 
    cout<<endl; 
} 

[cpp]
#include "head.h" 
 
int main() 
{ 
    DNode *head; 
    head=Creat(); 
    Display(head); 
#ifndef DEBUG 
    cout<<"please input an num to insert:"; 
#endif 
    int insert_num; 
    while (cin>>insert_num&&insert_num) 
    { 
        Insert(head,insert_num); 
        Display(head); 
    } 
#ifndef DEBUG 
cout<<"please input an number to delete:"; 
#endif 
    int delete_num; 
    while (cin>>delete_num&&delete_num) 
    { 
        Del(head,delete_num); 
        Display(head); 
    } 
    return (EXIT_SUCCESS); 
}