• SCAUoj实验11 链表操作

    SCAU链表oj题目

    文章目录

    前言

      刚开始学习链表可能会看得比较头晕，关键在于先理解链表的逻辑结构和物理结构，尤其是逻辑结构自己一定要会画并且能理解，在刚开始做题时建议自己画出逻辑结构并照着代码一步一步对链表进行操作。

    一、堂前习题

    1099 [填空题]链表的合并

    下面程序创建两个链表，然后将第二个链表合并到第一个链表未尾，但合并部分的代码未完成，请你完成这部分代码。

    #include "stdio.h"
#include "malloc.h"
#define LEN sizeof(struct student)

struct student
{
     long num;
     int score;
     struct student *next;
};

struct student *create(int n)
{ 
     struct student *head=NULL,*p1=NULL,*p2=NULL;
     int i;
     for(i=1;i<=n;i++)
     {  p1=(struct student *)malloc(LEN);
        scanf("%ld",&p1->num);    
        scanf("%d",&p1->score);    
        p1->next=NULL;
        if(i==1) head=p1;
        else p2->next=p1;
        p2=p1;
      }
      return(head);
}

struct student *merge(struct student *head, struct student *head2)
{ 
_______________________
}


void print(struct student *head)
{
    struct student *p;
    p=head;
    while(p!=NULL)
    {
        printf("%8ld%8d",p->num,p->score);
        p=p->next;
        printf("\n");
    }
}

main()
{
    struct student *head, *head2;
    int n;
    long del_num;
    scanf("%d",&n); 
    head=create(n);
    print(head);
    scanf("%d",&n); 
    head2=create(n);
    print(head2);
    head = merge(head, head2);    
    print(head);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59

    输入样例
    2 （the 1st linked list, 2 students）
    1 （code of no.1 studentof the 1st linked list）
    98 （score of no.1 student of the 1st linked list）
    7 （code of no.2 student of the 1st linked list）
    99 （score of no.2 student of the 1st linked list）
    1 （the 2nd linked list, 1 student）
    5 （code of no.1 student of the 2nd linked list）
    87 （score of no.1 student of the 2nd linked list）

    输出样例
    1 98
    7 99
    5 87
    1 98
    7 99
    5 87

    代码如下：

    struct student *merge(struct student *head, struct student *head2)
{
    if(head == NULL)
    {
        return head2;
    }
    struct student* p = head;
    while(p->next != NULL)
    {
        p = p -> next;
    }
    p -> next = head2;
    return head;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    二、堂上练习

    1098 [填空]链表结点的插入

    完成插入链表结点的函数(按学号顺序)，并调试通过、提交。

    #include "stdio.h"
#include "malloc.h"
#define LEN sizeof(struct student)

struct student
{
     long num;
     int score;
     struct student *next;
};

struct student *create(int n)
{ 
     struct student *head=NULL,*p1=NULL,*p2=NULL;
     int i;
     for(i=1;i<=n;i++)
     {  p1=(struct student *)malloc(LEN);
        scanf("%ld",&p1->num);    
        scanf("%d",&p1->score);    
        p1->next=NULL;
        if(i==1) head=p1;
        else p2->next=p1;
        p2=p1;
      }
      return(head);
}

void print(struct student *head)
{
    struct student *p;
    p=head;
    while(p!=NULL)
    {
        printf("%8ld%8d",p->num,p->score);
        p=p->next;
        printf("\n");
    }
}

struct student *insert(struct student *head, struct student *stud)
{  
_______________________
}

main()
{
    struct student *head,*stu;
    int n;
    scanf("%d",&n);   
    head=create(n);
    print(head);
    stu=(struct student *)malloc(LEN);
    scanf("%ld",&stu->num);        
    scanf("%d",&stu->score);    
    stu->next = NULL;
    head=insert(head,stu);
    print(head);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58

    输入样例
    3 （3 students）
    1 （code of no.1 student）
    98 （score of no.1 student）
    3 （code of no.2 student）
    99 （score of no.2 student）
    5 （code of no.3 student）
    87 （score of no.3 student）
    4 （code of no.3 student needs be inserted）
    77 （score of no.3 student needs be inserted）

    输出样例
    1 98
    3 99
    5 87
    1 98
    3 99
    4 77
    5 87

    代码如下：

    struct student *insert(struct student *head, struct student *stud)
{
    struct student* p = head,*p1 = head;
    if(head == NULL)//空链表
    {
        head = stud;
    }
    else
    {
        if(p -> next == NULL)//注意是==，不是=,这句话是假如链表只有1个成员
        {
            if(p -> num < stud -> num)
            {
                p -> next = stud;
            }
            else
            {
                stud -> next = p;
                head = stud;
            }
        }
        else//大于1个成员，分为插在中间和插在末尾
        {
            while((p1 -> num < stud -> num)&&(p1 !=NULL))
            {
                p = p1;
                p1 = p1 -> next;
            }
            if(p1 != NULL)
            {
                stud -> next = p1;
                p -> next = stud;
            }
            else
            {
                p->next = stud;
            }
        }
    }
    return head;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41

    1104 [填空题]链表的倒序

    下面程序，先创建一个链表，然后调用reverse函数，将链表中各结点变为倒序排列。请完成reverse函数，

    #include "stdio.h"
#include "malloc.h"
#define LEN sizeof(struct student)

struct student
{
     long num;
     int score;
     struct student *next;
};

struct student *create(int n)
{ 
     struct student *head=NULL,*p1=NULL,*p2=NULL;
     int i;
     for(i=1;i<=n;i++)
     {  p1=(struct student *)malloc(LEN);
        scanf("%ld",&p1->num);
        scanf("%d",&p1->score);
        p1->next=NULL;
        if(i==1) head=p1;
        else p2->next=p1;
        p2=p1;
      }
      return(head);
}

void print(struct student *head)
{
    struct student *p;
    p=head;
    while(p!=NULL)
    {
        printf("%8ld%8d",p->num,p->score);
        p=p->next;
        printf("\n");
    }
}

struct student *reverse(struct student *head)
{
_______________________
}

main()
{
    struct student *head,*stu;
    int n;
    scanf("%d",&n);  
    head=create(n);
    print(head);
    head=reverse(head);
    print(head);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54

    输入样例
    3 （3 students）
    1 （code of no.1 student）
    98 （score of no.1 student）
    4 （code of no.2 student）
    99 （score of no.2 student）
    5 （code of no.3 student）
    87 （score of no.3 student）

    输出样例
    1 98
    4 99
    5 87
    5 87
    4 99
    1 98
    代码如下：

    struct student *reverse(struct student *head)
{
    struct student* p1,*p2;
    if(head == NULL)
    {
        return NULL;
    }
    p1 = head -> next;
    head -> next = NULL;
    while(p1 != NULL)
    {
        p2 = p1;
        p1 = p1 -> next;
        p2 -> next = head;//这里并不是要指向头结点，p2->next想指向的是最新脱离原链表的结点，而head刚好指向最新脱离的结点
        head = p2;//注意这里不能是head -> next = p2
    }
    return head;//最后head就刚好成为反转之后的链表的头结点
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    1101 [填空题]链表的排序

    下面程序，先创建一个链表（链表中各结点未按学号由小到大排序），然后调用sort函数，将链表中各结点按学号由小到大排序。

    #include "stdio.h"
#include "malloc.h"
#define LEN sizeof(struct student)

struct student
{
     long num;
     int score;
     struct student *next;
};

struct student *create(int n)
{ 
     struct student *head=NULL,*p1=NULL,*p2=NULL;
     int i;
     for(i=1;i<=n;i++)
     {  p1=(struct student *)malloc(LEN);
        scanf("%ld",&p1->num);    
        scanf("%d",&p1->score);    
        p1->next=NULL;
        if(i==1) head=p1;
        else p2->next=p1;
        p2=p1;
      }
      return(head);
}

void print(struct student *head)
{
    struct student *p;
    p=head;
    while(p!=NULL)
    {
        printf("%8ld%8d",p->num,p->score);
        p=p->next;
        printf("\n");
    }
}

struct student *insert(struct student *head, struct student *stud)
{  struct student *p0,*p1,*p2;
    p1=head;  p0=stud;
    if(head==NULL)
      {head=p0;}
    else
   { while( (p0->num > p1->num) && (p1->next!=NULL) )
       { p2=p1;     p1=p1->next;}
     if( p0->num <= p1->num )
      {  if( head==p1 ) head=p0;
           else p2->next=p0;
         p0->next=p1; }
     else {  p1->next=p0;}
     }
    return(head);
}

struct student *del(struct student *head,long num)
{
    struct student *p1,*p2;
    p1=head;
    while(p1!=NULL)
    {
        if(p1->num == num)
        {
          if(p1 == head) head=p1->next;
          else p2->next=p1->next;
          free(p1);
          break;
        }
        p2=p1;
        p1=p1->next;
    }
    return(head);
}

struct student *sort(struct student *head)
{
_______________________
}

main()
{
    struct student *head,*stu;
    int n;
    scanf("%d",&n);
    head=create(n);
    print(head);
    head=sort(head);
    print(head);
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91

    输入样例
    3 （the 1st linked list, 2 students）
    1 （code of no.1 student）
    98 （score of no.1 student）
    7 （code of no.2 student）
    99 （score of no.2 student）
    5 （code of no.3 student）
    87 （score of no.3 student）

    输出样例
    1 98
    7 99
    5 87
    1 98
    5 87
    7 99

    struct student *sort(struct student *head)
{
    struct student* p1,*p2;
    if(head == NULL)
    {
        return NULL;
    }
    p1 = head -> next;
    head -> next = NULL;//断开第一个结点
    while(p1 != NULL)
    {
        p2 = p1;
        p1 = p1 -> next;
        p2 -> next = NULL;
        head = insert(head,p2);
    }
    return head;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
  • 相关阅读:
    Spring Data JPA与Mybatis的对比
    一次搞定：借助Hutool封装代码快速解决webservice调用烦恼
    ceph 005 赋权补充 rbd块映射
    App爬虫之强大的Airtest的操作总结
    WEB安全基础 - - -Linux反弹shell
    数据结构----哈希
    分享股票下单API接口的方式和API攻略
    分布式存储--负载均衡
    贪心算法解汽车加油问题
    vue组件之间的五种传值方法(父子\兄弟\跨组件)
  • 原文地址：https://blog.csdn.net/callmeggyh/article/details/134544764