欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-06-20 20:29:18
...

双向链表前插入无需定位到节点的前一位,因为其本身有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);//按值删除

}