C语言程序设计 PAT题目

1. 习题7-8 字符串转换成十进制整数（15 分）
   输入一个以#结束的字符串，本题要求滤去全部的非十六进制字符（不分大小写），组成一个新的表示十六进制数字的字符串，而后将其转换为十进制数后输出。若是在第一个十六进制字符以前存在字符“-”，则表明该数是负数。

输入格式：node

输入在一行中给出一个以#结束的非空字符串。web

输出格式：算法

在一行中输出转换后的十进制数。题目保证输出在长整型范围内。数组

输入样例：svg

+-P-xf4+-1!#
输出样例：函数

-3905ui

每种条件都要考虑彻底

#include <stdio.h>

int main()
{
    int i, j, flag;
    char hexad[100], str[100];
    long number;
    i = 0;
    while ((str[i] = getchar()) != '#')
        i++;
    str[i] = '\0';
    flag = 0;
    for (i = 0; str[i] != '\0'; i++)
    {
        if (str[i] == '-')
        {
            flag = 1;
            break;
        }
        else if ((str[i] >= '0' && str[i] <= '9'))
            break;
    }
    if (flag)
    {
        hexad[0] = '-';
        j = 1;
    }
    else
        j = 0;
    for (i = 0; str[i] != '\0'; i++)
    {
        if ((str[i] >= '0' && str[i] <= '9') || (str[i] >= 'a' && str[i] <= 'f') || (str[i] >= 'A' && str[i] <= 'F'))
        {
            hexad[j] = str[i];
            j++;
        }
    }
    hexad[j] = '\0';
    number = 0;
    for (i = 0; hexad[i] != '\0'; i++)
    {
        if (hexad[i] >= '0' && hexad[i] <= '9')
            number = number*16 + hexad[i]-'0';
        else if (hexad[i] >= 'A' && hexad[i] <= 'F')
            number = number*16+hexad[i]-'A'+10;
        else if (hexad[i] >= 'a' && hexad[i] <= 'f')
            number = number*16 + hexad[i]-'a'+10;
    }
    if (hexad[0] == '-' && number < 0xabcdef)
        number = -1*number;
    printf("%ld\n", number);
    return 0;
}

1. 习题4-7 最大公约数和最小公倍数（15 分）
   本题要求两个给定正整数的最大公约数和最小公倍数。

输入格式:spa

输入在一行中给出两个正整数M和N（≤1000）。指针

输出格式:code

在一行中顺序输出M和N的最大公约数和最小公倍数，两数字间以1空格分隔。

输入样例:

511 292
输出样例:

73 2044

#include <stdio.h>
int GCD(int m, int n);
int LCM(int m, int n);

int main()
{
    int m, n, max, min;
    scanf("%d %d", &m, &n);
    max = GCD(m, n);
    min = LCM(m, n);
    printf("%d %d\n", max, min);
    return 0;
}

int GCD(int m, int n)
{
    if (n) {
        while((m = m%n) && (n = n%m)); //这个比展转相除的方法简洁
    return m+n;
    }
}

int LCM(int m, int n)
{
    return m*n / GCD(m, n);
}

3
习题8-4 报数（20 分）
报数游戏是这样的：有n我的围成一圈，按顺序从1到n编好号。从第一我的开始报数，报到m（

#include <stdio.h>
#define MAXN 20

void CountOff( int n, int m, int out[] );

int main()
{
    int out[MAXN], n, m;
    int i;

    scanf("%d %d", &n, &m);
    CountOff( n, m, out );   
    for ( i = 0; i < n; i++ )
        printf("%d ", out[i]);
    printf("\n");

    return 0;
}

输入样例：

11 3
输出样例：

4 10 1 7 5 2 11 9 3 6 8

这道题居然扯到算法了.. 想了半天，主要是被i-1那里坑了，没发现。下次要先画个四个的简单分析下，就很快就作出来了。


void CountOff(int n, int m, int out[])
{
    int i, j, count, length, circle[MAXN], temp[MAXN];
    for (i = 0, length = 0; i < n; i++)
    {
        circle[i] = i+1;
        length++;
    }

    count = 0;
    j = 0;
    while (length > 0)
    {
        for (i = 0; i < n; i++)
        {
            if (circle[i] != 0)
                count++;
            else
                continue;
            if (count%m == 0)
            {
                temp[j] = circle[i];
                j++;
                circle[i] = 0;
                length--;
            }
        }
    }

    for (i = 0; i < n; i++)
    {
        j = temp[i];
        out[j-1] = i + 1;
    }
}

创建链表

struct stud_node *createlist()
{
    struct stud_node *head, *tail, *q;
    head = tail = NULL;
    int num;
    scanf ("%d", &num);
    while (num != 0)
    {
        q = (struct stud_node *)malloc (sizeof (struct stud_node));
        scanf ("%s %d", q->name, &q->score);
        q->num = num;
        q->next = NULL;
        if (head == NULL)
            head = q;
        else
            tail->next = q;
        tail = q;
        scanf ("%d", &num);
    }
    return head;
}

**实验11-2-2 学生成绩链表处理（20 分）
本题要求实现两个函数，一个将输入的学生成绩组织成单向链表；另外一个将成绩低于某分数线的学生结点从链表中删除。**

链表创建和删除，必定要熟练！

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

struct stud_node {
     int    num;
     char   name[20];
     int    score;
     struct stud_node *next;
};

struct stud_node *createlist();
struct stud_node *deletelist( struct stud_node *head, int min_score );

int main()
{
    int min_score;
    struct stud_node *p, *head = NULL;

    head = createlist();
    scanf("%d", &min_score);
    head = deletelist(head, min_score);
    for ( p = head; p != NULL; p = p->next )
        printf("%d %s %d\n", p->num, p->name, p->score);

    return 0;
}

struct stud_node *createlist()
{
    struct stud_node *head, *tail, *q;
    head = tail = NULL;
    int num;
    scanf ("%d", &num);
    while (num != 0)
    {
        q = (struct stud_node *)malloc (sizeof (struct stud_node));
        scanf ("%s %d", q->name, &q->score);
        q->num = num;
        q->next = NULL;
        if (head == NULL)
            head = q;
        else
            tail->next = q;
        tail = q;
        scanf ("%d", &num);
    }
    return head;
}
struct stud_node *deletelist( struct stud_node *head, int min_score )
{
    struct stud_node *ptr1, *ptr2;
    while (head != NULL && head->score < min_score)
    {
        ptr2 = head;
        head = head->next;
        free(ptr2);
    }
    if (head == NULL)
        return NULL;
    ptr1 = head;
    ptr2 = head->next;
    while (ptr2 != NULL)
    {
        if (ptr2->score < min_score) {
            ptr1->next = ptr2->next;
            free(ptr2);
        }
        else
            ptr1 = ptr2;
        ptr2 = ptr1->next;
    }
    return head;
}

将两个链表排序合并， 不难， 可是感受用数组排一下直观一点？

struct ListNode *mergelists(struct ListNode *list1, struct ListNode *list2)
{
    int num = 0;
    int temp[100];
    struct ListNode  *p = list1;
    while(p)
    {
        temp[num] = p->data;
        num++;
        p = p->next;
    }
    p = list2;
    while(p)
    {
        temp[num] = p->data;
        num++;
        p = p->next;
    }
    int i,j;
    for(i = 1; i < num; i++)
        for(j = 0; j < num-i; j++)
        {
            if(temp[j] > temp[j+1])
            {
                int t;
                t = temp[j];
                temp[j] = temp[j+1];
                temp[j+1] = t;
            }
        }
      struct ListNode  *head, *tail, *q;
      head = tail = NULL;
      for(i = 0; i < num; i++)
      {
          q = (struct ListNode  *)malloc(sizeof(struct ListNode));
          q->data = temp[i];
          q->next = NULL;
          if (head == NULL)
            head = q;
          else
            tail->next = q;
          tail = q;
      }
      return head;
}

实验11-2-6 奇数值结点链表（20 分）
本题要求实现两个函数，分别将读入的数据存储为单链表、将链表中奇数值的结点从新组成一个新的链表。链表结点定义以下：

struct ListNode {
int data;
ListNode *next;
};
函数接口定义：

struct ListNode *readlist();
struct ListNode *getodd( struct ListNode **L );
函数readlist从标准输入读入一系列正整数，按照读入顺序创建单链表。当读到−1时表示输入结束，函数应返回指向单链表头结点的指针。

函数getodd将单链表L中奇数值的结点分离出来，从新组成一个新的链表。返回指向新链表头结点的指针，同时将L中存储的地址改成删除了奇数值结点后的链表的头结点地址（因此要传入L的指针）。

这道题卡了我一天我就操了，主要是一个网上的参考答案各类怀疑人生，本身都按本身的写终于AC了，感受对free这个有点深入的理解了。
#include <stdio.h>
#include <stdlib.h>

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

struct ListNode *readlist();
struct ListNode *getodd( struct ListNode **L );
void printlist( struct ListNode *L )
{
     struct ListNode *p = L;
     while (p) {
           printf("%d ", p->data);
           p = p->next;
     }
     printf("\n");
}

int main()
{
    struct ListNode *L, *Odd;
    L = readlist();
    Odd = getodd(&L);
    printlist(Odd);
    printlist(L);

    return 0;
}
struct ListNode *readlist()
{
    int data;
    struct ListNode *head, *tail, *p;
    head = tail = NULL;
    scanf("%d", &data);
    while (data != -1)
    {
        p = (struct ListNode*) malloc(sizeof(struct ListNode));
        p->data = data;
        p->next = NULL;
        if (head == NULL)
            head = p;
        else
            tail->next = p;
        tail = p;
        scanf("%d", &data);
    }
    return head;
}

struct ListNode *getodd(struct ListNode **L)
{
    int flag = 0;
    struct ListNode *head, *tail, *q, *p, *p1, *p2, *ptr;
    head = tail = q = p = p1 = p2 = ptr = NULL;
    p = *L;
    while (p)
    {
        if (p->data % 2 != 0)
        {
            q = (struct ListNode *) malloc(sizeof(struct ListNode));
            q->data = p->data;
            q->next = NULL;
            if (head == NULL)
                head = q;
            else
                tail->next = q;
            tail = q;
            ptr = p;
            p = p->next;
            free(ptr);
        }
        else
        {
            if (p1 == NULL)
                p1 = p;
            else
                p2->next = p;
            p2 = p;
            p = p->next;
            flag = 1;
        }
    }
    if (flag)
        p2->next = NULL;
    *L = p1;
    return head;
}