SDUTOJ 《程序设计基础(B)Ⅱ》 实验 1 2 难度较大题目记录

第四周周六又双叒叕要机测,像我这样的小白怎么跟集训Dalao比?于是”重操旧业“,开始复习做笔记QAQ

小 I 选宾馆

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

小 I 去天津玩啦,一路上,他跟他的同学发生了许多有趣的事。

到了晚上了,小 I 跟他的同学们要选一个宾馆住下了。但是形形色色的宾馆让小 I 不知所措。

对于一个宾馆来说,有许多特征,比如「价格」、「舒适度」。小I会对每个特征都有一个满意度。

小I会选择出满意度更高一些的宾馆。

其中,「价格」对于小 I 来说是最重要的,其次是「舒适度」。

如果有两个宾馆,如果对「价格」的满意度相同,那么根据「舒适度」进行选择;如果有多个宾馆条件相同,输出编号最小的宾馆。

小 I 现在处于水深火热之中,因为他们面对一堆宾馆不知所措,他想到了会编程的你,如果你不帮他选出来,他可能就会露宿街头了QAQ~

你能帮他按照他的意愿找到小I最满意的宾馆吗?

Input

多组输入,对于每组输入:

  • 给出 n (n <= 5000) 代表 n 个宾馆(编号从 1 - n),随后有 n 行数据。
  • 每行数据有两个整数,分别代表小I对「价格」、「舒适度」的满意程度,数值越大满意程度越高,满意度的范围从0 - 5000。

Output

输出按照描述的条件中小I最满意的宾馆编号,如果有多个宾馆条件相同,输出编号最小的宾馆。

Sample Input

4
0 1
1 0
1 1
1 0

Sample Output

3

Reference Code

#include<stdio.h>
struct
{
    int no;
    int cost;
    int com;
}hotal[5001],temp;
int main()
{
    int n,i,j;
    while (scanf("%d",&n)!=EOF)
    {
        for (i=0;i<n;i++)
        {
            hotal[i].no=(i+1);
            scanf("%d %d",&hotal[i].cost,&hotal[i].com);
        }
        for (i=0;i<n-1;i++)
        {
            for (j=0;j<n-1-i;j++)
            {//重点就是下面的循环判断,先比较价格,价格相同的条件下再比较舒适度
                if (hotal[j+1].cost>hotal[j].cost)
                {
                    temp=hotal[j];
                    hotal[j]=hotal[j+1];
                    hotal[j+1]=temp;
                }
                else if ((hotal[j+1].cost==hotal[j].cost)&&(hotal[j+1].com>hotal[j].com))
                {
                    temp=hotal[j];
                    hotal[j]=hotal[j+1];
                    hotal[j+1]=temp;
                }
            }
        }
        printf("%d\n",hotal[0].no);
    }
    return 0;
}

最终排名

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

​ 第四届山东理工大学ACM网络编程擂台赛比赛完后需要产生一个最终排名,排名按照题数多少来决定。但是有太多的队伍参与,手动计算排名已经不能满足比赛的需求。现在有一份名单记录各个队伍的ID和做出的题目数,需要你写一个程序,产生最终的排名。

​ 为了简化题目,这里的排名规则为:做出题目数量多的队伍排在前面,如果题数相等,保持输入时的相对顺序不要改变。

Input

​ 第一行包含一个正整数T( 1 ≤ T ≤ 15),表示有T组测试数据。每组数据第一行有一个正整数N(1 < N ≤ 10000),表示队伍数量。接下来N 行包含两个整数,1 ≤ ID ≤ 10^7, 0 ≤ M ≤ 100。ID为队伍的编号,M为做出的题数。

Output

​ 每组数据输出包含N行,第i行有两个整数,ID和M表示排在第i位的队伍的ID和做出的题数。

Sample Input

1
8
1 2
16 3
11 2
20 3
3 5
26 4
7 1
22 4

Sample Output

3 5
26 4
22 4
16 3
20 3
1 2
11 2
7 1

Reference Code

#include<stdio.h>
struct
{
    int id;
    int num;
}rank[10001],t;

int main()
{
    int n;
    int m,i,j;
    scanf("%d",&n);
    while (n--)
    {
        scanf("%d",&m);
        for (i=0;i<m;i++)
        {
            scanf("%d %d",&rank[i].id,&rank[i].num);
        }
        for (i=0;i<m-1;i++)
        {
            for (j=0;j<m-1-i;j++)
            {
                if (rank[j+1].num>rank[j].num)
                {
                    t=rank[j];
                    rank[j]=rank[j+1];
                    rank[j+1]=t;
                }
            }
        }
        for (i=0;i<m;i++)
        {
            printf("%d %d\n",rank[i].id,rank[i].num);
        }
    }
    return 0;
}

选夫婿1

Time Limit: 1000 ms Memory Limit: 32768 KiB

Problem Description

​ 倾国倾城的大家闺秀潘小姐要选夫婿啦!武林中各门各派,武林外各大户人家,闻讯纷纷前来,强势围观。前来参与竞选的男生藏龙卧虎,高手云集,才子遍布,帅哥纷纭,更不乏富二代,官二代,可谓声势空前。

img

​ 每个人参与竞选的帅哥除了进行一段激情洋溢的求婚演讲以外,还要报上自己姓名、身高和体重,以及个人简历。最后再进行文武选拔,最后夺魁者方能得到潘小姐的芳心。

​ 潘小姐不爱名利,只看人,第一关就是身高和体重要合格,即必须在其要求的范围内,否则直接排除在外,不允许参加下一轮的选拔。

​ 作为一个程序员,你没有钱也没有权,擅长的也就是编程了。潘小姐也发现了这一点,所以把首轮根据身高体重进行选拔的任务交给了你,如果完成的好,你可以直接进入下一轮选拔,你笑了。

Input

​ 潘小姐给你了所有报名男生的信息。输入数据的第一行是一个正整数N(0 < N < 1000)。然后N行数据,每行包含三部分,用空格隔开。第一部分是报名者的姓名name(长度小于20的字符串),然后是整数身高h(0 < h < 300),第三部分是整数体重w (0 < w < 200)。

最后一行是四个整数a,b,c,d.表示身高的合格范围是[a,b],体重的合格范围是[c,d](0 < a < b < 200, 0 < c < d < 300)。

Output

​ 你需要把合格的男生信息按照身高从低到高输出,格式跟输入一样,也是每行三个信息,共N行,如果身高相同则按体重从轻到重输出,若没有合格人选则输出No,具体格式见样例。

Sample Input

8
武大郎 70 40
西门庆 180 70
李逵 160 150
燕青 175 69
鲁智深 180 100
武松 180 75
小泉纯一狼 30 20
孙二娘 169 60
165 190 60 90

Sample Output

孙二娘 169 60
燕青 175 69
西门庆 180 70
武松 180 75

Reference Code

#include<stdio.h>
struct
{
    char name[21];
    int w;
    int h;
}rank[1001],ok[1001],t;
int main()
{
    int n,i,j,k,sh1,sh2,sw1,sw2;
    scanf("%d",&n);
    for (i=0;i<n;i++)
    {
        scanf("%s %d %d",rank[i].name,&rank[i].h,&rank[i].w);
    }
    scanf("%d %d %d %d",&sh1,&sh2,&sw1,&sw2);
    for (i=0,k=0;i<n;i++)
    {
        if (rank[i].h>=sh1&&rank[i].h<=sh2&&rank[i].w>=sw1&&rank[i].w<=sw2)
        {
            ok[k]=rank[i];
            k++;
        }
    }
    if (k!=0)
    {
        for (i=0;i<k-1;i++)
        {
            for (j=0;j<k-i-1;j++)
            {
                if (ok[j+1].h<ok[j].h)
                {
                    t=ok[j+1];
                    ok[j+1]=ok[j];
                    ok[j]=t;
                }
                else if ((ok[j+1].h==ok[j].h)&&(ok[j+1].w<ok[j].w))
                {
                    t=ok[j+1];
                    ok[j+1]=ok[j];
                    ok[j]=t;
                }
            }
        }
        for (i=0;i<k;i++)
        {
            printf("%s %d %d\n",ok[i].name,ok[i].h,ok[i].w);
        }
    }
    else printf("No\n");
    return 0;
}

共用体练习

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

给定n和m,接下来有n个描述,每个描述包含一个类型标志和一组相应的数据。类型标志共3种:INT DOUBLE STRING,然后对应一组相应的数据。紧接着有m个询问,每个询问仅包含一个整数x,要求输出第x个描述对应的数据(STRING类型保证不含空格,每组对应STRING数据不会超过19个字符)。

Input

输入的第一行为两个整数,n和m (n<=100000, m<=100000),分别代表描述的个数和询问的个数。接下来为 n 行描述,最后为m行询问,具体格式见样例输入输出。

Output

对于每个询问,输出对应的结果,注意:浮点数保留两位小数。

Sample Input

5 4
INT 456
DOUBLE 123.56
DOUBLE 0.476
STRING welcomeToC
STRING LemonTree
0
1
2
4

Sample Output

456
123.56
0.48
LemonTree

Hint

必须使用共用体完成。

Reference Code

#include<stdio.h>
#include<string.h>
union
{
    int a;
    double b;
    char c[20];
}u[100001];

int main()
{
    int n,m,i,t;
    char str[100001][30];
    /*
    共用体的特点就是各个元素共用一块内存,写入数据后再写入数据,前面的数据将被破坏,因此需要定义一个数组来存放类型。
    */
    scanf("%d %d",&n,&m);

    for (i=0;i<n;i++)
    {
        scanf("%s",str[i]);
        if (strcmp(str[i],"INT")==0)
        {
            scanf("%d",&u[i].a);
        }
        else if (strcmp(str[i],"DOUBLE")==0)
        {
            scanf("%lf",&u[i].b);
        }
        else if (strcmp(str[i],"STRING")==0)
        {
            scanf("%s",&u[i].c);
        }
    }
    for (i=0;i<m;i++)
    {
        scanf("%d",&t);
        if (strcmp(str[t],"INT")==0) printf("%d\n",u[t].a);
        else if (strcmp(str[t],"DOUBLE")==0) printf("%.2f\n",u[t].b);
        else if (strcmp(str[t],"STRING")==0) printf("%s\n",u[t].c);
    }
    return 0;
}

简单枚举类型——植物与颜色

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

​ 请定义具有red, orange, yellow, green, blue, violet六种颜色的枚举类型color,根据输入的颜色名称,输出以下六种植物花朵的颜色:

Rose(red), Poppies(orange), Sunflower(yellow), Grass(green), Bluebells(blue), Violets(violet)。如果输入的颜色名称不在枚举类型color中,例如输入purple,请输出I don't know about the color purple.

Input

​ 输入数据有多行,每行有一个字符串代表颜色名称,颜色名称最多30个字符,直到文件结束为止。

Output

​ 输出对应颜色的植物名称,例如:Bluebells are blue. 如果输入的颜色名称不在枚举类型color中,例如purple, 请输出I don't know about the color purple.

Sample Input

blue
yellow
purple

Sample Output

Bluebells are blue.
Sunflower are yellow.
I don't know about the color purple.

Hint

请用枚举类型实现。

Reference Code

#include<stdio.h>
#include<string.h>
enum {red, orange, yellow, green, blue, violet, unkonwn}color;
int main()
{
    char ch[31];
    while (scanf("%s",ch)!=EOF)
    {
        if (strcmp("red",ch)==0) color=red;
        else if (strcmp("orange",ch)==0) color=orange;
        else if (strcmp("yellow",ch)==0) color=yellow;
        else if (strcmp("green",ch)==0) color=green;
        else if (strcmp("blue",ch)==0) color=blue;
        else if (strcmp("violet",ch)==0) color=violet;
        else color=unkonwn;
        switch (color)
        {
            case red : printf("Rose are red.\n");break;
            case orange : printf("Poppies are orange.\n");break;
            case yellow : printf("Sunflower are yellow.\n");break;
            case green : printf("Grass are green.\n");break;
            case blue : printf("Bluebells are blue.\n");break;
            case violet : printf("Violets are violet.\n");break;
            default : printf("I don't know about the color %s.\n",ch);break;
        }
    }
    return 0;
}

链表:主要掌握单链表的增删改查,双向链表的建立和查询,以及循环链表的删改查。这部分的程序相较之前的程序长度有所增长,复杂度大大增加,一个主函数main()太过于冗长,以下的程序均用到了函数,模块化处理问题。

数据结构实验之链表一:顺序建立链表

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

​ 输入N个整数,按照输入的顺序建立单链表存储,并遍历所建立的单链表,输出这些数据。

Input

​ 第一行输入整数的个数N;
第二行依次输入每个整数。

Output

​ 输出这组整数。

Sample Input

8
12 56 4 6 55 15 33 62

Sample Output

12 56 4 6 55 15 33 62

Reference Code

//这道题把正序建立和逆序建立链表放在了一起,因为程序其他部分完全相同。
#include<stdio.h>
#include<stdlib.h>
struct node
{
    int data;
    struct node *next;
};

void create(int x,struct node *head)//顺序建立链表
{
    struct node *p,*tail;
    p = (struct node *)malloc(sizeof(struct node));
    p->data = x;
    p->next = NULL;
    tail = head;
    while (tail->next)
    {
        tail = tail->next;
    }
    tail->next = p;
}

void create1(int x,struct node *head)//逆序建立链表
{
    struct node *p;
    p = (struct node *)malloc(sizeof(struct node));
    p->data = x;
    p->next = head->next;
    head->next = p;
}

void print(struct node *head)
{
    head = head->next;
    while (head)
    {
        if (head->next) printf("%d ",head->data);
        else printf("%d\n",head->data);
        head = head->next;
    }
}

int main()
{
    int n,x;
    scanf("%d",&n);
    struct node *head;
    head = (struct node *)malloc(sizeof(struct node));
    head->next = NULL;
    while (n--)
    {
        scanf("%d",&x);
        create(x,head);
    }
    print(head);
    return 0;
}

师--链表的结点插入

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

​ 给出一个只有头指针的链表和 n 次操作,每次操作为在链表的第 m 个元素后面插入一个新元素x。若m 大于链表的元素总数则将x放在链表的最后。

Input

​ 多组输入。每组数据首先输入一个整数n(n∈[1,100]),代表有n次操作。

​ 接下来的n行,每行有两个整数Mi(Mi∈[0,10000]),Xi。

Output

​ 对于每组数据。从前到后输出链表的所有元素,两个元素之间用空格隔开。

Sample Input

4
1 1
1 2
0 3
100 4

Sample Output

3 1 2 4

Reference Code

#include<stdio.h>
#include<stdlib.h>

struct node
{
    int data;
    struct node *next;
};

void insert(int m,int x,struct node *head)
{
    struct node *p,*q,*tail;
    p = (struct node *)malloc(sizeof(struct node));
    p->next = NULL;
    p->data = x;
    q = head->next;
    tail = head;

    while (m--&&q)
    {
        q = q->next;
        tail = tail->next;
    }
    if (q)
    {
        tail->next = p;
        p->next = q;
    }
    else
    {
        p->next = tail->next;
        tail->next = p;
    }
}

void display (struct node *head)
{
    struct node *p;
    p = (struct node *)malloc(sizeof(struct node));
    p = head->next;
    while (p != NULL)
    {
        if (p->next == NULL)
        {
            printf("%d\n",p->data);
        }
        else
        {
            printf("%d ",p->data);
        }
        p = p->next;
    }
    free(p);
}

int main()
{
    int n,m,x;
    struct node *head;
    while (scanf("%d",&n)!=EOF)
    {
        head = (struct node *)malloc(sizeof(struct node));
        head->next = NULL;
        while (n--)
        {
            scanf("%d %d",&m,&x);
            insert(m,x,head);
        }
        display(head);
    }
    return 0;
}


数据结构实验之链表七:单链表中重复元素的删除

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

​ 按照数据输入的相反顺序(逆位序)建立一个单链表,并将单链表中重复的元素删除(值相同的元素只保留最后输入的一个)。

Input

第一行输入元素个数 n (1 <= n <= 15);
第二行输入 n 个整数,保证在 int 范围内。

Output

第一行输出初始链表元素个数;
第二行输出按照逆位序所建立的初始链表;
第三行输出删除重复元素后的单链表元素个数;
第四行输出删除重复元素后的单链表。

Sample Input

10
21 30 14 55 32 63 11 30 55 30

Sample Output

10
30 55 30 11 63 32 55 14 30 21
7
30 55 11 63 32 14 21

Reference Code

#include<stdio.h>
#include<stdlib.h>

struct node
{
    int data;
    struct node *next;
};

void ins(int x,struct node *head)
{
    struct node *p;
    p = (struct node *)malloc(sizeof(struct node));
    p->data = x;
    p->next = head->next;
    head->next = p;
}

void del(struct node *head)
{
    int count = 0,i;
    struct node *p,*q,*r;
    p = head->next;
    while (p)
    {
        p = p->next;
        count ++;
    }
    p = head->next;
    while(p)
    {
        r = p->next;
        q = p;
        while (r)
        {
            if (r->data == p->data)
            {
                q->next = r->next;
                r = q->next;
            }
            else
            {
                q = q->next;
                r = r->next;
            }
        }
        p = p->next;
    }
}

void dis(struct node *head)
{
    int count = 0;
    struct node *p;
    p = head->next;
    while (p)
    {
        p = p->next;
        count ++;
    }
    printf("%d\n",count);
    head = head->next;
    while (head)
    {
        if (head->next)
        {
            printf("%d ",head->data);
        }
        else
        {
            printf("%d\n",head->data);
        }
        head = head->next;
    }
}

int main()
{
    int n,x;
    while (scanf("%d",&n)!=EOF)
    {
        struct node *head;
        head = (struct node *)malloc(sizeof(struct node));
        head->next = NULL;
        while (n--)
        {
            scanf("%d",&x);
            ins(x,head);
        }
        dis(head);
        del(head);
        dis(head);
    }
    return 0;
}

数据结构实验之链表三:链表的逆置

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

​ 输入多个整数,以-1作为结束标志,顺序建立一个带头结点的单链表,之后对该单链表的数据进行逆置,并输出逆置后的单链表数据。

Input

​ 输入多个整数,以-1作为结束标志。

Output

​ 输出逆置后的单链表数据。

Sample Input

12 56 4 6 55 15 33 62 -1

Sample Output

62 33 15 55 6 4 56 12

Hint

不得使用数组。

Reference Code

#include<stdio.h>
#include<stdlib.h>

struct node
{
    int data;
    struct node *next;
};

void create(int n,struct node *head)
{
    struct node *p,*q;
    p = (struct node *)malloc(sizeof(struct node));
    p->data = n;
    p->next = NULL;
    q = head;
    while (q->next)
    {
        q = q->next;
    }
    q->next = p;
}

void reverse(struct node *head)
{
    struct node *p,*q;
    p = head->next;
    head->next = NULL;
    q = p->next;
    while (p)
    {
        p->next = head->next;
        head->next = p;
        p = q;
        if (q)
        {
            q = q->next;
        }
    }
}

void print(struct node *head)
{
    head = head->next;
    while (head)
    {
        if (head->next)
        {
            printf("%d ",head->data);
        }
        else
        {
            printf("%d\n",head->data);
        }
        head = head->next;
    }
}

int main()
{
    int n;
    struct node *head;
    head = (struct node *)malloc(sizeof(struct node));
    head->next = NULL;
    while (scanf("%d",&n))
    {
        if (n == -1) break;
        create(n,head);
    }
    reverse(head);
    print(head);
    return 0;
}

数据结构实验之链表四:有序链表的归并

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

​ 分别输入两个有序的整数序列(分别包含M和N个数据),建立两个有序的单链表,将这两个有序单链表合并成为一个大的有序单链表,并依次输出合并后的单链表数据。

Input

第一行输入M与N的值;
第二行依次输入M个有序的整数;
第三行依次输入N个有序的整数。

Output

输出合并后的单链表所包含的M+N个有序的整数。

Sample Input

6 5
1 23 26 45 66 99
14 21 28 50 100

Sample Output

1 14 21 23 26 28 45 50 66 99 100

Hint

不得使用数组!

Reference Code

#include<stdio.h>
#include<stdlib.h>

struct node
{
    int data;
    struct node *next;
};

void create(int x,struct node *head)
{
    struct node *p,*q;
    p = (struct node *)malloc(sizeof(struct node));
    p->data = x;
    p->next = NULL;
    q = head;
    while (q->next)
    {
        q = q->next;
    }
    q->next = p;
}

struct node * merge(struct node *head1,struct node *head2)
{
    struct node *p1,*p2,*tail;
    p1 = head1->next;
    p2 = head2->next;
    tail = head1;
    free(head2);
    while (p1&&p2)
    {
        if (p1->data < p2->data)
        {
            tail->next = p1;
            tail = p1;
            p1 = p1->next;
        }
        else
        {
            tail->next = p2;
            tail = p2;
            p2 = p2->next;
        }
        if (p1)
        {
            tail->next = p1;
        }
        else
        {
            tail->next = p2;
        }
    }
    return (head1);
}

void print(struct node *head)
{
    head = head->next;
    while (head)
    {
        if (head->next)
        {
            printf("%d ",head->data);
        }
        else
        {
            printf("%d\n",head->data);
        }
        head = head->next;
    }
}

int main()
{
    int m,n,x;
    struct node *head1,*head2,*head;
    scanf("%d %d",&m,&n);
    head1 = (struct node *)malloc(sizeof(struct node));
    head2 = (struct node *)malloc(sizeof(struct node));
    head1->next = NULL;
    head2->next = NULL;
    while (m--)
    {
        scanf("%d",&x);
        create(x,head1);
    }
    while (n--)
    {
        scanf("%d",&x);
        create(x,head2);
    }
    head = merge(head1,head2);
    print(head);
    return 0;
}

数据结构实验之链表五:单链表的拆分

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

​ 输入N个整数顺序建立一个单链表,将该单链表拆分成两个子链表,第一个子链表存放了所有的偶数,第二个子链表存放了所有的奇数。两个子链表中数据的相对次序与原链表一致。

Input

​ 第一行输入整数N;;
第二行依次输入N个整数。

Output

​ 第一行分别输出偶数链表与奇数链表的元素个数;
第二行依次输出偶数子链表的所有数据;
第三行依次输出奇数子链表的所有数据。

Sample Input

10
1 3 22 8 15 999 9 44 6 1001

Sample Output

4 6
22 8 44 6 
1 3 15 999 9 1001

Hint

不得使用数组!

Reference Code

#include<stdio.h>
#include<stdlib.h>

struct node
{
    int data;
    struct node *next;
};

void create(int x,struct node *head)
{
    int count1=0,count2=0;
    struct node *p,*tail;
    p = (struct node *)malloc(sizeof(struct node));
    p->data = x;
    p->next = NULL;
    tail = head;
    while (tail->next)
    {
        tail = tail->next;
    }
    tail->next = p;
}

void print(struct node *head)
{
    head = head->next;
    while (head)
    {
        if (head->next)
        {
            printf("%d ",head->data);
        }
        else
        {
            printf("%d\n",head->data);
        }
        head = head->next;
    }
}

void split(struct node *head)
{
    struct node *head2,*p,*q,*tail,*tail2;
    int count1=0,count2=0;
    head2 = (struct node *)malloc(sizeof(struct node));
    head2->next = NULL;
    p = head->next;
    tail = head;
    tail2 = head2;
    q = p->next;
    while (p)
    {
        if (p->data % 2 == 0)
        {
            p->next = NULL;
            tail->next = p;
            tail = p;
            count1++;
        }
        else
        {
            p->next = NULL;
            tail2->next = p;
            tail2 = p;
            count2++;
        }
        p = q;
        if (q)
        {
            q = q->next;
        }
    }
    printf("%d %d\n",count1,count2);
    print(head);
    print(head2);
}

int main()
{
    int n,x;
    struct node *head;
    head = (struct node *)malloc(sizeof(struct node));
    head->next = NULL;
    scanf("%d",&n);
    while (n--)
    {
        scanf("%d",&x);
        create(x,head);
    }
    split(head);
    return 0;
}

不敢死队问题

Time Limit: 1000 ms Memory Limit: 65536KiB

Problem Description

说到“敢死队”,大家不要以为我来介绍电影了,因为数据结构里真有这么道程序设计题目,原题如下:

有M个敢死队员要炸掉敌人的一个碉堡,谁都不想去,排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务,则要再派一个战士上去。现给每个战士编一个号,大家围坐成一圈,随便从某一个战士开始计数,当数到5时,对应的战士就去执行任务,且此战士不再参加下一轮计数。如果此战士没完成任务,再从下一个战士开始数数,被数到第5时,此战士接着去执行任务。以此类推,直到任务完成为止。

这题本来就叫“敢死队”。“谁都不想去”,就这一句我觉得这个问题也只能叫“不敢死队问题”。今天大家就要完成这道不敢死队问题。我们假设排长是1号,按照上面介绍,从一号开始数,数到5的那名战士去执行任务,那么排长是第几个去执行任务的?

Input

输入包括多试数据,每行一个整数M(0<=M<=10000)(敢死队人数),若M==0,输入结束,不做处理。

Output

输出一个整数n,代表排长是第n个去执行任务。

Sample Input

9
6
223
0

Sample Output

2
6
132

Reference Code

#include<stdio.h>
#include<stdlib.h>
struct node
{
    int data;
    struct node *next;
};

struct node * create(int n)
{
    int i;
    struct node *head,*tail,*p;
    p = (struct node *)malloc(sizeof(struct node));
    p->data = 1;
    p->next = NULL;
    head = p;
    tail = p;
    for (i=1;i<n;i++)
    {
        p = (struct node *)malloc(sizeof(struct node));
        p->data = i+1;
        p->next = NULL;
        tail->next = p;
        tail = p;
    }
    tail->next = head;
    return head;
}
int ying(int n,struct node *head)
{
    int count = 0,num = 0;
    struct node *p,*q;
    q = head;
    while (q->next!=head)
    {
        q = q->next;
    }
    while (count < n - 1)
    {
        p = q->next;
        num ++;
        if (num%5==0)
        {
            count ++;
            if (p->data == 1) break;
            q->next = p->next;
            free(p);
        }
        else q = p;
    }
    if (q->data == 1) count++;
    return count;
}

int main()
{
    int n,ans;
    struct node *head;
    while (~scanf("%d",&n))
    {
        if (n == 0) break;
        head = create(n);
        ans = ying(n,head);
        printf("%d\n",ans);
    }
    return 0;
}

数据结构实验之链表九:双向链表

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

​ 学会了单向链表,我们又多了一种解决问题的能力,单链表利用一个指针就能在内存中找到下一个位置,这是一个不会轻易断裂的链。但单链表有一个弱点——不能回指。比如在链表中有两个节点A,B,他们的关系是B是A的后继,A指向了B,便能轻易经A找到B,但从B却不能找到A。一个简单的想法便能轻易解决这个问题——建立双向链表。在双向链表中,A有一个指针指向了节点B,同时,B又有一个指向A的指针。这样不仅能从链表头节点的位置遍历整个链表所有节点,也能从链表尾节点开始遍历所有节点。对于给定的一列数据,按照给定的顺序建立双向链表,按照关键字找到相应节点,输出此节点的前驱节点关键字及后继节点关键字。

Input

​ 第一行两个正整数n(代表节点个数),m(代表要找的关键字的个数)。第二行是n个数(n个数没有重复),利用这n个数建立双向链表。接下来有m个关键字,每个占一行。

Output

​ 对给定的每个关键字,输出此关键字前驱节点关键字和后继节点关键字。如果给定的关键字没有前驱或者后继,则不输出。
​ 注意:每个给定关键字的输出占一行。
​ 一行输出的数据之间有一个空格,行首、行末无空格。

Sample Input

10 3
1 2 3 4 5 6 7 8 9 0
3
5
0

Sample Output

2 4
4 6
9

Reference Code

#include<stdio.h>
#include<stdlib.h>
struct node
{
    int data;
    struct node *next,*prior;
};

int main()
{
    int n,m,i,x;
    scanf("%d %d",&n,&m);
    struct node *head,*p,*q,*tail;
    head = (struct node *)malloc(sizeof(struct node));
    head->next = NULL;
    head->prior = NULL;
    tail = head;
    for (i=0;i<n;i++)
    {
        p = (struct node *)malloc(sizeof(struct node));
        scanf("%d",&p->data);
        p->next = NULL;
        p->prior = NULL;
        tail->next = p;
        p->prior = tail;
        tail = p;
    }
    for (i=0;i<m;i++)
    {
        struct node *p;
        p = head->next;
        scanf("%d",&x);
        while (p)
        {
            if (p->data==x)
            {
                if (p->prior!=head&&p->next)
                {
                    printf("%d %d\n",p->prior->data,p->next->data);\
                    break;
                }
                else if (p->prior!=head&&p->next==NULL)
                {
                     printf("%d\n",p->prior->data);
                     break;
                }
                else if (p->next!=NULL&&p->prior==head)
                {
                    printf("%d\n",p->next->data);
                    break;
                }
            }
            p = p->next;
        }
    }
    return 0;
}
Tags:none
上一篇
没有啦~

该页面评论已关闭