双链表(增删改查)

同上篇,单链表,头指针存储链表长度.查找和删除分别有根据数据或节点位置来处理

#include <iostream>
using namespace std;
typedef struct DbNode{
    int data;
    DbNode *Left;
    DbNode *Right;
}DbNode;
 
DbNode *DbCreate(){
    DbNode *head = new DbNode, *p, *q;
    head -> data = 0;
    head -> Left = head -> Right = NULL;
    p = head;
    for( int i = 0; i < 10; ++i ){
        q = new DbNode;
        q -> data = i;
        q -> Left = q -> Right = NULL;
        head -> data++;
        p -> Right = q;
        q -> Left = p;
        p = q;
    }
    return head;
}
 
void DbPrint( DbNode *head ){
    DbNode *p = head -> Right;
    if( head == NULL )
        return;
    while( p != NULL ){
        cout << p -> data;
        p = p -> Right;
    }
    cout << endl;
}
 
int DbLen( DbNode *head ){
    DbNode *p = head -> Right;
    int len = 0;
    while( p != NULL ){
        len++;
        p = p -> Right;
    }
    return len;
}
 
DbNode *DbSeach1( DbNode *head, int data ){
    if( head == NULL ){
        return NULL;
    }
    DbNode *p = head -> Right;
    while( p != NULL ){
        if( p -> data == data )
            break;
        p = p -> Right;
    }
    return p;
}
 
DbNode *DbSeach2( DbNode *head, int pos ){
    if( pos == 0 )
        return head;
    DbNode *p = head;
    while( p -> Right!= NULL && pos-- ){
        p = p -> Right;
    }
    if( pos != 0 ){
        return p;
    }
    else{
        cout << "error" << endl;
        return NULL;
    }
}
 
DbNode *DbInsert( DbNode *head, int pos, int data ){
    DbNode *q = new DbNode;
    q -> data = data;
    q -> Left = q -> Right = NULL;
    DbNode *p = DbSeach2( head, pos );
    if( pos != NULL ){
        head -> data++;
        q -> Right = p -> Right;
        p -> Right -> Left = q;
        q -> Left = p;
        p -> Right = q;
    }
    return head;
}
 
DbNode *DbDelete( DbNode *head, DbNode *q ){
    DbNode *p = q -> Left;
    if( p == NULL ){
        head -> Right = q -> Right;
        q -> Right -> Left = head;
    }
    else if( q -> Right == NULL ){
        p -> Right = NULL;
    }
    else{
        head ->data --;
        q -> Right -> Left = p;
        p -> Right = q -> Right;
    }
    return head;
}
 
DbNode *DbDelete2( DbNode *head, int pos ){
    DbNode *q = DbSeach2( head, pos );
    head = DbDelete(head, q );
    delete( q );
    return head;
}
DbNode *DbDelete1( DbNode *head, int data ){
    DbNode *q;
    while( ( q = DbSeach1(head, data ) ) != NULL ){
        head = DbDelete(head, q );
        delete( q );
    }
    return head;
}
 
int main()
{
    //建立双链表(带头)
    DbNode *head = DbCreate();
    //求链表长度,头节点存储数据已经
    int Len = DbLen( head );
    cout << Len << endl;
    DbPrint( head );
 
    int m, n;
    cin >> m;
    //按照查找数据m
    DbNode *temp = DbSeach1( head, m );
    cout << temp -> data << endl;
    cin >> m;
    //按照位置查找
    temp = DbSeach2( head, m );
    cout << temp -> data << endl;
    cin >> m >> n;
    //插入数据
    temp = DbInsert( head, m, n );
    DbPrint( temp );
    cin >> m;
    //根据数据删除
    temp = DbDelete1( head, m );
    DbPrint( temp );
    cin >> m;
    //根据节点删除
    temp = DbDelete2( head, m );
    DbPrint( temp );
    return 0;
}

bo-jwolf

一级美术,二级策划,三级程序

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

相关推荐