LinkedList | LSABLOG

首页 » Program » C/C++ » 正文

LinkedList

链表的结点中有指针域,这里先写最初级的链表(后续会有链表的进化型和究极进化型)
几个关键点:
1.头指针
2.插入和删除操作的指针修改
3.插入和删除操作的各种情况分析(具体的看注释)
4.记录指针
下面以一个学生成绩管理程序为例:

    #include <stdio.h>
    #include <malloc.h>

    #define NULL 0

    struct student
    {
        int num;     //学号
        double score;     //分数
        struct student *next;    //指向下一个学生
    };
    int main()
    {
        struct student *del(struct student *head,int num);    //删除声明
        struct student *ins(struct student *head,struct student *stu);    //插入声明

        int n = 0;
        int dnum;
        struct student *head,*p,*p1,*p2,*p3,stu;
        head = NULL;    //先让头结点指针为空
        p1 = (struct student*)malloc(sizeof(struct student));     //开辟空间
        scanf("%d%lf",&p1->num,&p1->score);
        do
            {
                n = n+1;
                if (n==1)head = p1;        //若是第一个结点,就给head
                else p2->next = p1;           //非第一个结点,就给p2的下一个结点
                p2 = p1;                    //把p1先给p2
                p1 = (struct student*)malloc(sizeof(struct student));   //p1再新开一个内存区
                scanf("%d%lf",&p1->num,&p1->score);
            }
        while (p1->num!=0);     //号数输入为0就结束了
        p2->next = NULL;          //最后一个结点的next指向null没了
        p = head;              //创建链表完毕--------------------------------------
        while (p!=NULL)
            {
                printf("%d\t%lf\n",p->num,p->score);
                p = p->next;              //指针后移输出结点信息
            }
        printf("请输入需要删除的学号:");
        scanf("%d",&dnum);
        p = del(head,dnum);  //返回删除后的头结点,删除完毕------------------------------
        p3 = p;            //记录删除后的链表!
        while (p!=NULL)
            {
                printf("%d\t%lf\n",p->num,p->score);
                p = p->next;
            }

        printf("请输入需要增添的学号及其数据");
        scanf("%d%lf",&stu.num,&stu.score);
        p = ins(p3,&stu);    //返回插入后的头结点,插入完毕-------------------------------
        while (p!=NULL)
            {
                printf("%d\t%lf\n",p->num,p->score);
                p = p->next;
            }
        return 0;
    }

    struct student *del(struct student *head,int num)  //传头结点与要删除的号数进来
    {
        struct student *p1,*p2;
        if (head==NULL)
            {
                printf("NO\n");
            }
        p1 = head;
        while (num!=p1->num&&p1->next!=NULL)   //要删除的号数不是第一个并且没到或等于最后一个
            {
                p2 = p1;          //p1先给p2(存前一个结点)
                p1 = p1->next;     //指针后移继续寻找要删除的号数
            }
        if (num==p1->num)       //如果找到了
            {
                if (p1==head) head=p1->next;      //要删除的号数是第一个结点,使头指针后移一位,这样第一个结点就删除了
                else p2->next = p1->next;         //要删除的号数不是第一个结点,那要删除的号数的前一个结点的next就可以直接指向要删除的号数的next指的结点

                printf("delete:%ld\n",num);
            }
        else printf("%d not been found!\n",num);
        return head;
    }

    struct student *ins(struct student *head,struct student *stu)    //传头结点与要插入的学生信息
    {
        struct student *p0,*p1,*p2;
        p1 = head;    //先给头结点于p1
        p0 = stu;     //新增学生信息给p0
        if (head==NULL)
            {
                head=p0;    //1.无结点的情况
                p0->next=NULL;
            }
        else
            {
                while ((p0->num>p1->num)&&(p1->next!=NULL))     //要插入的号数大于p1的号数并且没到或等于最后一个
                    {
                        p2 = p1;      //p1先给p2存着(存前一个结点)
                        p1 = p1->next;   //指正后移继续寻找
                    }
                if (p0->num<=p1->num)     //如果要插入的号数小于或等于p1的号数(找到插入位置了)
                    {
                        if (head==p1)head = p0;  //2.如果是头结点,就插在第一个结点前
                        else p2->next = p0;       //3.插在结点之间(p2这时候有用啦)
                        p0->next = p1;  //next指向那个号数比插入结点大或等的结点
                    }
                else
                    {
                        p1->next = p0;    //4.插在表尾(找到最后结点了也没找到)
                        p0->next = NULL;
                    }
            }
        return head;
    }


Comment