期末考试复习-链表（C语言基础）

前言

本篇文章的代码中附有注释，可以看一下。代码看起来比较长，其实链表并不难(首先要自信…嗯…)
（此时一个被期末考试逼得肝了几个小时链表题的萌新，留下了他不学无术的泪水）

一、链表的构建

1.尾插法构建链表。输入n个数把它们按输入顺序依次插入到链表中，再依次输出。

#include <stdio.h>
#include <stdlib.h>
struct node//结构体链表基本形式
{
    int data;
    struct node *next;
};
int n,x;
struct node *head,*tail;//定义头指针、尾指针
void insert_after_end(int x)//在链尾插入x
{
    tail->next=(struct node*)malloc(sizeof(struct node));//申请下一个指针的空间
    tail=tail->next;//尾指针向后移一位
    tail->data=x;
    tail->next=NULL;//初始化下一个指针为NULL
}
int main()
{
    scanf("%d",&n);
    head=(struct node*)malloc(sizeof(struct node));//申请头指针空间
    tail=head;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        insert_after_end(x);
    }
    head=head->next;
    while(head!=NULL)
    {
        printf("%d ",head->data);
        head=head->next;
    }
    return 0;
}

2.头插法构建链表。输入n个数把它们逆序插入到链表中，再依次输出。

#include <stdio.h>
#include <stdlib.h>
struct node
{
    int data;
    struct node *next;
};
int n,x;
struct node *H,*head;//H作为头节点，不存储信息，只是起到一个参照物的作用，为了方便理解可以把它当做序号0
void insert_before_begin(int x)//把x插入到头节点的后面，为了方便理解可以当做每次都把x插入到序号0之后，x成为序号1，原序号1后移
{
    head=(struct node*)malloc(sizeof(struct node));
    head->data=x;
    head->next=H->next;
    H->next=head;//这几行代码的作用是把head指针插入到H(序号0)和H的后一个指针(序号1)之间
}
int main()
{
    scanf("%d",&n);
    H=(struct node*)malloc(sizeof(struct node));
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        insert_before_begin(x);
        if(i==1)H->next->next=NULL;//头插法构建链表时，第一个输入的元素是链尾，所以要把它的下一个指针初始化为NULL
    }
    head=H->next;
    while(head!=NULL)
    {
        printf("%d ",head->data);
        head=head->next;
    }
    return 0;
}

二、链表的删除

#include <stdio.h>
#include <stdlib.h>
struct node
{
    int data;
    struct node *next;
};
int n,x;
struct node *p,*head,*tail;
void insert_after_end(int x)
{
    tail->next=(struct node*)malloc(sizeof(struct node));
    tail=tail->next;
    tail->data=x;
    tail->next=NULL;
}
void del(int x)//删除链表中指定元素x
{
    p=(struct node*)malloc(sizeof(struct node));
    p=head;
    while(p->next!=NULL)
    {
        if(p->next->data==x)p->next=p->next->next;
        else p=p->next;
    }
}
int main()
{
    while(scanf("%d",&n)!=-1)
    {
        head=(struct node*)malloc(sizeof(struct node));
        tail=head;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&x);
            insert_after_end(x);
        }
        scanf("%d",&x);
        del(x);
        head=head->next;
        while(head!=NULL)
        {
            printf("%d ",head->data);
            head=head->next;
        }
        printf("\n");
    }
    return 0;
}

三、链表的修改

#include <stdio.h>
#include <stdlib.h>
struct node
{
    int data;
    struct node *next;
};
int n,k,x;
struct node *p,*H,*head;
void insert_before_begin(int x)
{
    head=(struct node*)malloc(sizeof(struct node));
    head->data=x;
    head->next=H->next;
    H->next=head;
}
void edit(int k,int x)//将第k个节点的值修改为x
{
    p=(struct node*)malloc(sizeof(struct node));
    p=H->next;
    for(int i=1;i<=n;i++)
    {
        if(i==k){p->data=x;break;}
        else p=p->next;
    }
}
int main()
{
    H=(struct node*)malloc(sizeof(struct node));
    while(scanf("%d",&x)&&x>=0)
    {
        n++;//n记录链表长度
        insert_before_begin(x);
        if(n==1)H->next->next=NULL;
    }
    scanf("%d%d",&k,&x);
    edit(k,x);
    head=H->next;
    while(head!=NULL)
    {
        printf("%d ",head->data);
        head=head->next;
    }
    return 0;
}

四、链表的插入

1.升序给出n个元素，插入到链表中，再插入一个元素后链表元素依然升序排列。

#include <stdio.h>
#include <stdlib.h>
struct node
{
    int data;
    struct node *next;
};
int n,x;
struct node *p,*head,*tail,*newnode;
void insert_after_end(int x)//尾插法构建链表
{
    tail->next=(struct node*)malloc(sizeof(struct node));
    tail=tail->next;
    tail->data=x;
    tail->next=NULL;
}
void insert(int x)//在已经升序排列的链表中插入元素x后，链表仍然升序排列
{
    p=(struct node*)malloc(sizeof(struct node));
    p=head;
    p->data=-1;//把头节点(序号0)赋负值是为了特判插入的x在head->next(序号1)之前的情况
    while(p!=NULL)
    {
        if( x > p->data && x < p->next->data )
        {
            newnode=(struct node*)malloc(sizeof(struct node));
            newnode->data=x;
            newnode->next=p->next;
            p->next=newnode;
            break;
        }
        p=p->next;
    }
}
int main()
{
    while(scanf("%d",&n)!=-1)
    {
        head=(struct node*)malloc(sizeof(struct node));
        tail=head;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&x);
            insert_after_end(x);
        }
        scanf("%d",&x);
        insert(x);
        head=head->next;
        while(head!=NULL)
        {
            printf("%d ",head->data);
            head=head->next;
        }
        printf("\n");
    }
    return 0;
}

2.乱序给出n个元素，链表中依次插入这n个元素，同时进行排序。

#include <stdio.h>
#include <stdlib.h>
struct node
{
    int data;
    struct node *next;
};
int n,x;
struct node *p,*H,*newnode;
void insert(int x)//链表中插入x，并保持升序排列
{
    p=H;
    while(p!=NULL)
    {
        if(p->next==NULL)
        {
            p->next=(struct node*)malloc(sizeof(struct node));
            p=p->next;
            p->data=x;
            p->next=NULL;
            break;
        }
        else
        {
            if( x > p->data && x < p->next->data )
            {
                newnode=(struct node*)malloc(sizeof(struct node));
                newnode->data=x;
                newnode->next=p->next;
                p->next=newnode;
                break;
            }
        }
        p=p->next;
    }
}
int main()
{
    while(scanf("%d",&n)!=-1)
    {
        H=(struct node*)malloc(sizeof(struct node));
        H->data=-1;//初始化头节点，赋负值
        H->next=NULL;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&x);
            insert(x);
        }
        p=H->next;
        while(p!=NULL)
        {
            printf("%d ",p->data);
            p=p->next;
        }
        printf("\n");
    }
    return 0;
}

五、链表的基本应用-用链表处理结构体排序问题

nefu 1049 cc-test08-1链表的输入与输出

这题相当于上一题的升级版。
上题是结构体中只有data这一个变量，要求把n个元素插入到链表中并要求按data升序排列。
这题是结构体中有num,name,sum等多个变量，要求把每个学生的全部信息插入到每个链表中并要求按sum降序排列(按总成绩从高到低排序输出)，按照上一题的代码改编一下就行了，代码看起来很长，其实很简单的啦~

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct node
{
    int num;
    char sex,name[21];
    double a,b,c,ave,sum;
    struct node *next;
};
int n,x,num;
char sex,name[21];
double a,b,c,sum;
struct node *p,*head,*newnode;
void insert(int num,char name[21],char sex,double a,double b,double c)
{
    p=head;
    sum=a+b+c;
    while(p!=NULL)
    {
        if(p->next==NULL)
        {
            p->next=(struct node*)malloc(sizeof(struct node));
            p=p->next;
            p->num=num;
            strcpy(p->name,name);
            p->sex=sex;
            p->a=a;
            p->b=b;
            p->c=c;
            p->sum=sum;
            p->ave=p->sum/3;
            p->next=NULL;
            break;
        }
        else
        {
            if( sum < p->sum && sum > p->next->sum )
            {
                newnode=(struct node*)malloc(sizeof(struct node));
                newnode->num=num;
                strcpy(newnode->name,name);
                newnode->sex=sex;
                newnode->a=a;
                newnode->b=b;
                newnode->c=c;
                newnode->sum=sum;
                newnode->ave=sum/3;
                newnode->next=p->next;
                p->next=newnode;
                break;
            }
        }
        p=p->next;
    }
}
int main()
{
    scanf("%d",&n);
    head=(struct node*)malloc(sizeof(struct node));
    head->sum=0x3f3f3f3f;//赋值头节点为INF后可以特判插入的成绩比第一个元素大的情况
    head->next=NULL;
    for(int i=1;i<=n;i++)
    {
        scanf("%d %[^\n] %c%lf%lf%lf",&num,name,&sex,&a,&b,&c);
        insert(num,name,sex,a,b,c);
    }
    head=head->next;
    while(head!=NULL)
    {
        printf("%d %s %c %.2lf %.2lf %.2lf %.2lf %.2lf\n",head->num,head->name,head->sex,head->a,head->b,head->c,head->ave,head->sum);
        head=head->next;
    }
    return 0;
}

————————————————————————————————————————————————————

期末考试题

输入一行字符串，以空格分割成多个字符串，以换行结束，要求逆序输出这多个字符串。
Sample Input：
ljw ak ac
Sample Output：
ac
ak
ljw

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct node
{
    char *data;//此处是用的指针表示一维数组
    struct node *next;
};
struct node *p,*H,*head;
struct node* creat()
{
    char in[110],tmp[110];
    gets(in);
    int cnt=0,cnt1=0;
    H=(struct node*)malloc(sizeof(struct node));
    in[strlen(in)]=' ';
    for(int i=0;i<=strlen(in);i++)
    {
        if(in[i]!=' ')tmp[cnt++]=in[i];
        else
        {
            cnt1++;
            p=(struct node*)malloc(sizeof(struct node));
            p->data=(char*)malloc(strlen(tmp)*sizeof(char));//指针一定要先申请空间再使用！！！
            strcpy(p->data,tmp);
            p->next=H->next;
            H->next=p;
            if(cnt1==1)H->next->next=NULL;
            cnt=0;
            memset(tmp,0,sizeof(tmp));
        }
    }
    return H;
}
int main()
{
    head=(struct node*)malloc(sizeof(struct node));
    head=creat();
    head=head->next;
    while(head!=NULL)
    {
        printf("%s\n",head->data);
        head=head->next;
    }
    return 0;
}