数据结构04 ------线性表（双向链表）

为了弥补单向链表的缺陷：发明出了双向链表

双向链表：它有两个指针域，一个指向其前面的节点，另外一个指向其后面的节点

双向链表：

    struct link{
        datatype data;            //数据域
        struct link *prev;        //指针域 前面那个节点的地址
        struct link *next;        //指针域 后面那个节点的地址
    };

双向链表的实现： 实现增 删 改 查：

#include

#include

typedef int datatype;

typedef struct link{
    datatype data;
    struct link *prev;
    struct link *next;
} link_t,*plink_t;

/*
 * @bref    创建新的节点
 * @param    d  :  数据
 * @retval    新的节点
 */
static plink_t create_node(datatype d)
{
    // 在堆中开空间
    plink_t node = (plink_t)malloc(sizeof(link_t));
    if(node == NULL){
        perror("malloc error");
        return NULL; 
    }
    
    // 成员赋值
    node->data = d;
    node->prev = NULL;
    node->next = NULL;
    
    //将新的节点返回
    return node;
}

/*
 * @bref    一个节点插在另外一个节点的后面
 * @param    p  :  节点
 * @param    node  :  节点
 * @retval    None
 */
static void insert_behind(plink_t p,plink_t node)
{
    node->next = p->next;
    node->prev = p;
    if(p->next!=NULL)
        p->next->prev = node;
    p->next = node;
}

/*
 * @bref    剪切
 * @param    node  :  被剪切的节点
 * @retval    None
 */
static void cut_node(plink_t node)
{
    node->prev->next = node->next;
    if(node->next!=NULL)
        node->next->prev = node->prev;
    
    node->next = NULL;
    node->prev = NULL;
}

/*
 * @bref    替换
 * @param    old  :  被替换的节点
 * @param    new  :  新的节点
 * @retval    None
 */
void replace(plink_t old,plink_t new)
{
    new->prev = old->prev;
    new->next = old->next;
    new->prev->next = new;
    if(new->next!=NULL)
        new->next->prev = new;

}

/*
 * @bref    初始化
 * @param    p ：二级指针，头节点的地址的地址
 * @retval    None
 */
void link_init(plink_t *p)
{
//    *p = create_node(-2); //可以这样子

    // 在堆中开空间
    *p = (plink_t)malloc(sizeof(link_t));
    if(*p == NULL){
        perror("malloc error");
        return; 
    }
    
    // 成员赋值
    (*p)->prev = NULL;
    (*p)->next = NULL;

}

/*
 * @bref    头插
 * @param    p ：头节点地址
 * @param    d ：插入的数据
 * @retval    None
 */
void link_insert_head(plink_t p,datatype d)
{
    //通过数据d创建新的节点
    plink_t node = create_node(d);
    if(node == NULL)
        return;
    
    //把新节点插入到头节点的后面
    insert_behind(p,node);
}

/*
 * @bref    尾插
 * @param    p ：头节点地址
 * @param    d ：插入的数据
 * @retval    None
 */
void link_insert_tail(plink_t p,datatype d)
{
    //通过数据d创建新的节点
    plink_t node = create_node(d);
    if(node == NULL)
        return;
    
    //跳到尾巴上
    while(p->next!=NULL)
        p = p->next;
    
    //把新节点插入到尾巴的后面
    insert_behind(p,node);
}

/*
 * @bref    删除
 * @param    p ：头节点地址
 * @param    d ：需要删除的数据
 * @retval    None
 */
void link_del(plink_t p,datatype d)
{
    plink_t node = NULL;
    
    //通过数据d 查询 其 节点 
    while(p->next!=NULL){
        node = p->next;
        if(node->data == d){  
            // 找到该节点，做删除 *** 作
            cut_node(node);
            free(node);
            continue;
        }
        p = p->next;
    }
}

/*
 * @bref    更新
 * @param    p ：头节点地址
 * @param    old_data ：旧数据
 * @param    new_data ：新数据
 * @retval    None
 */
void link_update(plink_t p,datatype old_data,datatype new_data)
{
    // 通过 old_data 找到节点 
    plink_t node = NULL;
    
    plink_t new_node = NULL;
    
    //通过数据d 查询 其 节点 
    while(p->next!=NULL){
        node = p->next;
        if(node->data == old_data){  
            // 通过new_data 创建新的节点 
            new_node = create_node(new_data);
            if(new_node==NULL)
                return;
            
            // 新的节点 替换 旧 的节点
            replace(node,new_node);
            node->next = NULL;
            node->prev = NULL;
            free(node);
        }
        p = p->next;
    }
}

/*
 * @bref    正序遍历
 * @param    p ：头节点地址
 * @retval    None
 */
void display(plink_t p)
{
    printf("正序遍历结果：");
    while(p->next!=NULL){
        p = p->next;
        printf("%d ",p->data);
    }
    printf("\n");
}