C 语言实验 9

C语言 锐格实验

九.链表2-基本访问操作

1、

查找指定结点的前驱。利用前面学到的尾插法创建链表的方法，建立一个具有n个结点的单链表，之后输入一个整数x，查找x在链表中的前驱结点是哪个？若x是第一个结点，则输出“没有前驱”，如果x不存在，则输出“x不存在”。

#include <stdio.h>
#include <stdlib.h>
struct table{
    int num;
    struct table* next;
};
int main()
{
    int n,i;
    int findnum,flag;
    struct table *head,*p,*q;
    while(scanf("%d",&n)!=-1)
    {
        flag=0;
        for(i=0;i<n;i++)
        {
            p=(struct table *)malloc(sizeof(struct table));
            scanf("%d",&p->num);
            if(i==0)
                head=q=p;
            else
                q->next=p;
            q=p;
            p->next=NULL;
        }
        scanf("%d",&findnum);
        q=p=head;
        while(p!=NULL)
        {
            if(p->num==findnum)
            {
                flag=1;
                if(p==head){
                    printf("没有前驱\n");
                    break;
                }else{
                    printf("%d\n",q->num);
                    break;
                }
            }
            q=p;
            p=p->next;
        }
        if(flag==0) printf("x不存在\n");
    }
}

2、

查找链表中有多少个值为偶数的结点。利用前面学到的头插法创建链表的方法，建立一个具有n个结点的单链表，之后统计一下该链表中有多少个值为偶数的结点。有则输出个数，没有则输出0。

#include <stdio.h>
#include <stdlib.h>
struct table{
    int num;
    struct table *next;
};
int main()
{
    int i,n;
    struct table *head,*q,*p;
    while(scanf("%d",&n)!=-1)
    {
        for(i=0;i<n;i++)
        {
            p=(struct table *)malloc(sizeof(struct table));
            scanf("%d",&p->num);
            if(i==0)
                head=q=p;
            else
                q->next=p;
            q=p;
            p->next=NULL;
        }
        p=head;
        int num=0;
        while(p!=NULL)
        {
            if((p->num)%2==0) num++;
            p=p->next;
        }
        printf("%d\n",num);
    }
}

3、

删除所有结点值为x的结点。利用前面学到的尾插法创建链表的方法，建立一个具有n个结点的单链表，之后删除其中所有值为x的结点（设x有多个）。

#include <stdio.h>
#include <stdlib.h>
struct table{
    int num;
    struct table *next;
};
int main()
{
    int i,n;
    struct table *head,*q,*p;
    while(scanf("%d",&n)!=-1)
    {
        for(i=0;i<n;i++)
        {
            p=(struct table *)malloc(sizeof(struct table));
            scanf("%d",&p->num);
            if(i==0)
                head=q=p;
            else
                q->next=p;
            q=p;
            p->next=NULL;
        }
        int deletenum;
        scanf("%d",&deletenum);
        q=p=head;
        while(p!=NULL)
        {
            if(p->num==deletenum)
            {
                if(p==head){
                    head=head->next;
                }else{
                    q->next=p->next;
                    p=p->next;
                    continue;
                }
            }
            q=p;
            p=p->next;
        }
        printf("%d",head->num);
        p=head->next;
        while(p!=NULL)
        {
            printf("  %d",p->num);
            p=p->next;
        }
        printf("\n");
    }
}

4、

利用尾插法建立一个递增有序的链表，（输入值有序即可），之后在这个链表中插1个x值，使链表仍然有序。利用前面学到的尾插法创建链表的方法，建立一个具有n个结点的递增有序的单链表，（此处使输入的数值递增有序即可），之后再输入一个整数x，将x插入到上述链表的合适的位置上，使得链表仍然有序。

#include <stdio.h>
#include <stdlib.h>
struct table{
    int num;
    struct table *next;
};
int main()
{
    int i,n;
    struct table *head,*q,*p,*t;
    while(scanf("%d",&n)!=-1)
    {
        for(i=0;i<n;i++)
        {
            p=(struct table *)malloc(sizeof(struct table));
            scanf("%d",&p->num);
            if(i==0)
                head=q=p;
            else
                q->next=p;
            q=p;
            p->next=NULL;
        }
        int insertnum;
        scanf("%d",&insertnum);
        q=p=head;
        while(p!=NULL)
        {
            if(p->num>insertnum)
            {
                t=(struct table *)malloc(sizeof(struct table));
                t->num=insertnum;
                if(p==head){
                    t->num=head->num;
                    head->num=insertnum;
                    t->next=head->next;
                    head->next=t;
                    break;
                }else{
                    t->next=q->next;
                    q->next=t;
                    break;
                }
            }
            if(p->next==NULL && insertnum>p->num)
            {
                t=(struct table *)malloc(sizeof(struct table));
                t->num=insertnum;
                t->next=NULL;
                p->next=t;
                break;
            }
            q=p;
            p=p->next;
        }
        p=head->next;
        printf("%d",head->num);
        while(p!=NULL)
        {
            printf("  %d",p->num);
            p=p->next;
        }
        printf("\n");

    }
}

5、

利用第4题中有序表插入数值的思想，编写程序，从空链表开始，逐个插入结点，最终建立一个递增有序的链表。完成输入和输出函数。

#include <stdio.h>
#include <stdlib.h>
struct stu{
    int num;
    struct stu *next;
};
int main()
{
    int n,i,j,t;
    while(scanf("%d",&n)!=-1)
    {
        struct stu *head,*p,*q;
        for(i=0;i<n;i++)
        {
            p=(struct stu *)malloc(sizeof(struct stu));
            scanf("%d",&p->num);
            if(i==0)
                head=q=p;
            else
                q->next=p;
            q=p;
            p->next=NULL;
        }
        p=q=head;
        while(p)
        {
            q=p->next;
            while(q)
            {
                if(q->num<p->num)
                {
                    t=q->num;
                    q->num=p->num;
                    p->num=t;
                }
                q=q->next;
            }
            p=p->next;
        }
        p=head->next;
        printf("%d",head->num);
        while(p)
        {
            printf("  %d",p->num);
            p=p->next;
        }
        printf("\n");
    }
}