双向链表

骑猪看日落 2022-06-16 13:08 209阅读 0赞

/*双向链表*/
    #include<stdio.h>
    typedef struct dbnode
    {
        int num;
        char name[9];
        char sex[3];
        int age;
        int score;
        struct dbnode *prior;   /*前指针*/
        struct dbnode *next;    /*后指针*/
    }Node,*LinkList;            /*结点类型、头指针类型*/
    LinkList CreateLinkList()   /*创建结点*/
    {
        LinkList head;          /*链表头指针*/
        Node *New,*End;         /*新指针、尾指针*/
        int i,x;
        head=(LinkList)malloc(sizeof(Node));/*生成头结点*/
        head->prior=head;       /*头指针prior指向自己*/
        head->next=head;        /*头指针next指向自己*/
        End=head;               /*尾指针指向头指针*/
        printf("请输入链表的长度:\n");
        scanf("%d",&x);
        for(i=1;i<=x;i++)
        {
            printf("请输入学号、姓名、性别、年龄、成绩:\n");
            New=(Node*)malloc(sizeof(Node));/*创建新结点*/
            scanf("%d%s%s%d%d",&New->num,New->name,New->sex,&New->age,&New->score);/*输入结点信息*/
            End->next=New;      /*尾指针next指向新结点*/
            New->prior=End;     /*新结点prior指向尾结点*/
            New->next=head;     /*新结点next指向头结点*/
            head->prior=New;    /*头指针prior指向新结点*/
            End=New;            /*尾结点指向新结点*/
        }
        return(head);
    }
    void OutLinkList(LinkList head) /*输出结点*/
    {
        Node *p;
        int i=1;
        p=head;
        p=p->next;
        printf("--------学生信息档案表--------\n");
        while(p!=head)
        {
            printf("Num %d:%d,%s,%s,%d,%d.\n",i++,p->num,p->name,p->sex,p->age,p->score);
            p=p->next;
        }
    }
    LinkList GetLinkList(LinkList head,int i)   /*读表元素*/
    {
        Node *p;
        p=head->next;
        int c=1;
        while((c<i)&&(p!=head)) /*当未到第i结点且未到头结点继续后移*/
        {
            p=p->next;
            c++;
        }
        if(c==i)                /*找到第i个结点*/
            return p;
        else
            return NULL;        /*查找失败*/
    }
    void InsertLinkList(LinkList head,int i) /*插入结点*/
    {
        Node *End,*New,*x;
        if(i==1)
            End=head;
        else
            End=GetLinkList(head,i-1);
        if(End==NULL)
            printf("找不到插入位置");
        else
        {
            New=(Node *)malloc(sizeof(Node));
            printf("请输入学号、姓名、性别、年龄、成绩:\n");
            scanf("%d%s%s%d%d",&New->num,New->name,New->sex,&New->age,&New->score);
            New->prior=End;
            New->next=End->next;
            End->next->prior=New;
            End->next=New;
        }
    }
    void DeleteLinkList(LinkList head,int i)    /*删除结点*/
    {
        Node *p;
        if(i==1)
            p=head;
        else
            p=GetLinkList(head,i);  /*查找第i个结点位置*/
        if(p!=NULL)
        {
            p->prior->next=p->next;     /*p前驱结点的后链指向p的后继结点*/
            p->next->prior=p->prior;    /*p后继结点的前链指向p的前驱结点*/
            free(p);                    /*释放*p的空间*/
        }
        else
            printf("找不到删除位置\n");
    }
    
    main()
    {
        LinkList head;
        int n;
        head=CreateLinkList();
        OutLinkList(head);
        printf("请输入插入的位置:\n");
        scanf("%d",&n);
        InsertLinkList(head,n);
        OutLinkList(head);
        printf("请输入删除位置:\n");
        scanf("%d",&n);
        DeleteLinkList(head,n);
        OutLinkList(head);
    }