双向链表的查找、删除、插入节点

双向链表前插入无需定位到节点的前一位，因为其本身有prior指针。从根本上来讲，它和单链表是类似的：

#include<stdio.h>
#include<stdlib.h>
typedef struct student
{
    int num;
    struct student *next;
    struct student *prior;
}LDstudent,*LDPstudent;
//-------------添加链表
void InitLink(LDPstudent *phead)
{
    *phead=NULL;
    LDPstudent ptr;
    LDPstudent r=ptr;//后插入需要加一个指针
    int n;
    printf("please input num of student:\n");
    scanf("%d",&n);
    while(n>0)
    {
        ptr=malloc(sizeof(LDstudent));
        ptr->num=n;

/*      ptr->next=*phead;//前插入的方式
        ptr->prior=NULL;
        if(*phead!=NULL)
            (*phead)->prior=ptr;
        *phead=ptr;
*/
                            //后插入
                            ptr->next=NULL;
                            if(*phead==NULL)
                            {   ptr->prior=NULL;
                                *phead=ptr;}
                            else

                            {   ptr->prior=r;
                                r->next=ptr;}

                            r=ptr;
        printf("please input num of student:\n");
        scanf("%d",&n);
    }


}
 //-------------打印链表
void printf_link(LDstudent *ptr)
{
    LDPstudent p1=ptr;
    printf("正序打印:\n");
    while(p1!=NULL)
    {
        printf("%d\t",p1->num);
        p1=p1->next;
    }
    printf("\n");
    printf("反序打印:\n");
    p1=ptr;
    while(p1->next!=NULL)
        p1=p1->next;
    while(p1!=NULL)
    {
        printf("%d\t",p1->num);
        p1=p1->prior;
    }printf("\n");
}
                     //-----------计算长度
unsigned int ListLength(LDPstudent ptr)
{
    unsigned int l=0;
    while(ptr!=NULL)
    {   ptr=ptr->next;
        l++;}
    return l;
}
            //-------------------按序号查找
LDPstudent ListLocate(LDPstudent ptr,int i)
{
    int j=1;
    while(ptr!=NULL&&j<i)
    {
        ptr=ptr->next;
        j++;
    }
    if(j==i)return ptr;
    else return NULL;
}
//-----------------------按值查找
LDPstudent ListLocate2(LDPstudent ptr,int i)
{
    while(ptr!=NULL)
    {
        if(ptr->num==i)return ptr;
        else ptr=ptr->next;}
        return ptr;
}
//-------------------------按序号后插入

void ListInsert(LDPstudent ptr,int i,int j)
{
    LDPstudent p1=ListLocate(ptr,i);
    if(p1==NULL)
    {   printf("无第%d学生,error!\n",i);return;}
    else{
        LDPstudent p2=malloc(sizeof(LDstudent));
        p2->num=j;
        p2->prior=p1;
        if(p1->next!=NULL)
        {   p2->next=p1->next;
            p1->next->prior=p2;}
        else p2->next=NULL;
        p1->next=p2;}
        printf("----------序号后插入----------:\n");
        printf_link(ptr);
}

//-------------------------按序号前插入

void ListInsert2(LDPstudent ptr,int i,int j)
{
    LDPstudent p1=ListLocate(ptr,i);
    if(p1==NULL)
    {   printf("无第%d学生,error!\n",i);return;}
    else{
        LDPstudent p2=malloc(sizeof(LDstudent));
        p2->num=j;
        p2->next=p1;////////////////
        p2->prior=p1->prior;
        if(p1->prior!=NULL)
        {   p1->prior->next=p2;}
        else ptr=p2;//注意头指针发生了变化;
        p1->prior=p2;}
        printf("----------序号前插入----------:\n");
        printf_link(ptr);
}

//-------------------------- 按值后插入

void ListInsert3(LDPstudent ptr,int i,int j)
{
    LDPstudent p1=ListLocate2(ptr,i);
    if(p1==NULL)
    {   printf("无这个学生,error!\n");return;}
    else{
        LDPstudent p2=malloc(sizeof(LDstudent));
        p2->num=j;
        p2->prior=p1;
        if(p1->next!=NULL)
        {   p2->next=p1->next;
            p1->next->prior=p2;}
        else p2->next=NULL;
        p1->next=p2;}
        printf("----------按值后插入----------:\n");
        printf_link(ptr);
}
//---------------------------按值前插入
void ListInsert4(LDPstudent ptr,int i,int j)
{
    LDPstudent p1=ListLocate2(ptr,i);
    if(p1==NULL)
    {   printf("无这个学生,error!\n");return;}
    else{
        LDPstudent p2=malloc(sizeof(LDstudent));
        p2->num=j;
        p2->next=p1;////////////////
        p2->prior=p1->prior;
        if(p1->prior!=NULL)
        {   p1->prior->next=p2;}
        else ptr=p2;//注意头指针发生了变化;
        p1->prior=p2;}
        printf("----------值前插入----------:\n");
        printf_link(ptr);
}
//-----------------------------按序号删除
void ListDelete(LDPstudent ptr,int i)
{
    LDPstudent p1=ListLocate2(ptr,i);

    if(p1==NULL)
    {   printf("无这个（值）学生,error!\n");return;}
    else
    {
        if(p1->prior==NULL&&p1->next!=NULL)
        {
            p1->next->prior=NULL;ptr=p1->next;//头指针变化
        }
        else if(p1->next==NULL&&p1->prior!=NULL)
        {
            p1->prior->next=NULL;
        }
        else if(p1->prior==NULL&&p1->next==NULL)
        {   ptr=NULL;   }
        else
        {
            p1->prior->next=p1->next;
            p1->next->prior=p1->prior;
        }
        printf("\n------按 序号删除后：----------\n");

        if(ptr==NULL)printf("NULL\n");
        else printf_link(ptr);
    }
}

//-----------------------------按 值删除
void ListDelete2(LDPstudent ptr,int i)
{
    LDPstudent p1=ListLocate2(ptr,i);

    if(p1==NULL)
    {   printf("无这个（值）学生,error!\n");return;}
    else
    {
        if(p1->prior==NULL&&p1->next!=NULL)
        {
            p1->next->prior=NULL;ptr=p1->next;//头指针变化
        }
        else if(p1->next==NULL&&p1->prior!=NULL)
        {
            p1->prior->next=NULL;
        }
        else if(p1->prior==NULL&&p1->next==NULL)
        {   ptr=NULL;   }
        else
        {
            p1->prior->next=p1->next;
            p1->next->prior=p1->prior;
        }
        printf("\n------按值删除后：----------\n");

        if(ptr==NULL)printf("NULL\n");
        else printf_link(ptr);
    }
}
// -======================主函数
int main()
{
    LDPstudent head;
    InitLink(&head);

    printf_link(head);// 打印链表

    unsigned int l;//计算长度
    l=ListLength(head);
    printf("\n长度l:%d\n",l);

/*  LDPstudent p=ListLocate(head,3);// 按序号查找
    if(p==NULL)
        printf("no third student\n");
    else
        printf("this third is %d\n",p->num);

    LDPstudent p2=ListLocate2(head,4);//按值查找
    if(p2==NULL)
        printf("no this student\n");
    else
        printf("this is %d\n",p2->num);
*/
//  ListInsert(head,3,3333);//按序号后插入


//  ListInsert2(head,3,2222);//按序号前插入


//  ListInsert3(head,6,6666);//按值后插入


//  ListInsert4(head,6,5555);//按值前插入

    ListDelete(head,3);//按序号删除
    ListDelete2(head,6);//按值删除

}