双链表的操作

双链表的操作

2021 年 09 月 28 日

558 次浏览

2136字数

双链表的代码定义

#include <iostream>
using namespace std;

typedef struct _DLNode
{
    int data;   //结点数据域
    struct _DLNode *next;   //指向后继的指针
    struct _DLNode *prev;   //指向前驱的指针
  
}DbLinkNode,DbLinkList;

初始化双链表

//初始化双链表
bool initDbLinkList(DbLinkList* &L)
{
    L = new DbLinkNode;
  
    //合法性检查，检查内存是否分配成功
    if(!L) return false;
  
    L->next = NULL;
    L->prev = NULL;
    L->data = -1;
  
    return true;
}

插入

前插法

//前插法
bool DbListInsertFront(DbLinkList* &L, DbLinkNode *node)
{
    //合法性检查
    if(!L || !node) return false;
  
//    if(L->next == NULL)
//    {
//        //若只有头结点，则在头结点后面插入一个结点
//        node->next = NULL;
//        node->prev = L;
//        L->next = node;
//    }
//    else
//    {
//        //若有多个结点，则在头结点与其后结点之间插入
//        L->next->prev = node;   //令第二结点指向前驱的指针指向node
//        node->next = L->next;
//        node->prev = L;
//        L->next = node;
//    }
  
    //优化
    if(L->next) L->next->prev = node;
    node->next = L->next;
    node->prev = L;
    L->next = node;
  
    return true;
}

尾插法

//尾插法
bool DbListInsertBack(DbLinkList* &L, DbLinkNode *node)
{
    //合法性检查
    if(!L || !node) return false;
  
    DbLinkNode *p = L;
  
    //找到尾结点
    while(p->next)
    {
        p = p->next;
    }
  
    node->next = NULL;
    node->prev = p;
    p->next = node;
  
    return true;
}

任意位置插入

//任意位置插入
/*  参数: 插入的双向链表， 插入位置， 插入结点数据域的值*/
bool DbListInsert(DbLinkList* &L, int i, int &e)
{
    //若链表为空未初始化，返回false
    if(!L) return false;
  
    //若只有头结点，但插入位置不等于1，则返回false
    if((!L->next && i != 1) || i < 1) return false;
  
    int j = 0;
    DbLinkList *p = L, *s;
  
    while(p && j < i)
    {
        //找查位置为i的结点
        p = p->next;
        j++;
    }
  
    if(!p || j != i)
    {
        cout << "不存在结点" << i << endl;
        return false;
    }
  
    cout << "p: " << p << endl;
  
    s = new DbLinkNode; //生成新的结点
    s->data = e;
  
    s->next = p;
    s->prev = p->prev;
    p->prev->next = s;
    p->prev = s;
  
    return true;
}

双链表的遍历输出

//双向链表的遍历输出
void printDbList(DbLinkList *L)
{
    //检查链表是否为空
    if(!L)
    {
        cout << "链表为空" << endl;
        return;
    }
  
    DbLinkList *p = L;
    p = p->next;
  
    while(p)
    {
        cout << p->data << endl;
        p = p->next;
    }
  
}