C程序设计基础Lab08

1032.进制转换

定义一个函数h2i，将一个字符串表示的16进制数转换成一个10进制数。

//********** Specification of hex2int **********
unsigned h2i(char s[]);
/* PreCondition:
s is a string consisting of 0~9,A-F or a-f with at most 8 characters
PostCondition:
return a decimal number equivalent to s
Examples: "100" ==> 256 ; "a" ==> 10 ; "0"==> 0
*/
/***************************************************************/
/*                                                             */
/*  DON'T MODIFY main function ANYWAY!                         */
/*                                                             */
/***************************************************************/
#include <stdio.h>
#define N 8

//********** Specification of hex2int **********
unsigned h2i(char s[])
/*
PreCondition:
s is a string consisting of 0~9,A-F or a-f with at most 8 characters
PostCondition:
return a decimal number equivalent to s
Examples: "100"==>256 ; "a"==> 10 ; "0"==> 0
*/
{
    //TODO: your function definition
}
/***************************************************************/
int main()
{
    char s[N+1];
    scanf("%s",s);
    //********** hex2int is called here ****************
    printf("%u\n",h2i(s));
    //**************************************************
    return 0;
}

样例

Input
100

Output
256

题解：

正序遍历，核心代码为sum = sum*16 + temp;

代码：

#include<stdio.h>
#define N 8
unsigned h2i(char s[]){
   int length = 0;
   unsigned int sum = 0;
   int temp;
   while(s[length]!='\0'){
       if(s[length]<='9' && s[length]>='0')
           temp = s[length]-'0';
       else{
           if(s[length]>='a' && s[length]<='f')
               temp = s[length]-'a'+10;
           else
               temp = s[length]-'A'+10;
       }
       sum = sum*16 + temp;
       length++;
   }
   return sum; 
}

int main(){
    char s[N+1];
    scanf("%s",s);
    printf("%u\n",h2i(s));
}

1033.查找字符串

定义一个函数strReverseIndex(s,t)，返回t在s中最右边出现的位置（s中的第1个字符的位置为0），找不到时返回-1。

//********** Specification of strrindex**********
int strReverseIndex(char s[],char t[ ]);
/* precondition: NULL
postcondition: return index of t in s from right  to left, -1 if none
*/
/***************************************************************/
/*                                                             */
/*  DON'T MODIFY main function ANYWAY!                         */
/*                                                             */
/***************************************************************/
#include <stdio.h>
int strReverseIndex(char s[],char t[])
/* precondition: NULL
postcondition: return index of t in s from right to left, -1 if none
*/
{
    //TODO: your function definition
}
/***************************************************************/
#define N 80
int main()
{
    char s[N+1],t[N+1];
    scanf("%s%s",s,t);
    //********** strReverseIndex is called here ********************
    printf("%d\n",strReverseIndex(s,t));
    //**************************************************
    return 0;
}

题解：

两种思路，模式匹配算法和KMP算法，但是KMP我不会写，就用模式匹配了，哈哈。 模式匹配算法： 长串s和短串t，遍历长串s，可以任意顺序，如本题中就是倒序遍历。将s中的字符与t中的第一个字符比较，如果相同，那么比较s中的下一个字符和t的第二个字符，如此往复，直到比较次数大于t的长度，那么就找到了。如果没找到，跳出，继续将s的下一个字符与t第一个字符比较，如此往复。

代码：

#include <stdio.h>
#define N 80

int strReverseIndex(char s[], char t[]){
    int found = 0;
    int length_s = 0, length_t = 0;
    while (t[length_t] != '\0')length_t++;
    while (s[length_s] != '\0')length_s++;
    for (int i = length_s-1; i >= 0; i--){
        int j = 0;int temp = i;
        while (s[temp] == t[j] && temp < length_s){
            temp++; j++;
            if (j == length_t)
                found = 1;
        }
        if (found)
            return i;
    }
    return -1;
}

int main(){
    char s[N + 1], t[N + 1];
    scanf("%s%s", s, t);
    printf("%d\n", strReverseIndex(s, t));
    return 0;
}

1034.字符串的旋转

国外某知名 IT 企业有一个招聘题 :

Enter two strings, s1 and s2, with length no more than 80, write code to check if s1 is a rotation of s2.

输入2个字符串，以1个空格分隔。

在一行中输出相关判断结果。

例如： 输入：waterbottle erbottlewat 输出："waterbottle" is a rotation of "erbottlewat"

又如： 输入：water erbottlewat 输出："water" is NOT a rotation of "erbottlewat"

/***************************************************************/
/*                                                             */
/*  DON'T MODIFY main function ANYWAY!                         */
/*                                                             */
/***************************************************************/

#include <stdio.h>
#include <string.h>

int isRotation(char s1[],char s2[])
   /* PreCondition:  s1和s2是长度不超80的两个字符串
     PostCondition: s2可以是s1经过循环移动后得到时返回1，否则0
   */
{
    //TODO: your function definition

}

/***************************************************************/
#define N 80
int main()
{
    char s[N+1],t[N+1];
    scanf("%s%s",s,t);

    //********** isRotation is called here *************
    if(isRotation(s,t)) printf("\"%s\" is a rotation of \"%s\"\n",s,t);
    else printf("\"%s\" is NOT a rotation of \"%s\"\n",s,t);
    //**************************************************

    return 0;
}

题解：

两种思路：

1.循环链表 我这里用的就是循环链表的方法，具体什么是循环链表，可以自己百度。 2.字符数组模拟循环链表 创建index代表数组下标，模拟指针，根据数组长度，令index=index%length。特殊情况需要单独判断。

代码：

#include <stdio.h>
#include <string.h>

#define N 80

typedef struct LinkedList{
    char ch;
    struct LinkedList *next;
} link;

void add(link *head, char x){
    link *p = head;
    while (p->next)
        p = p->next;
    p->next = (link *)malloc(sizeof(link));
    p = p->next;
    p->ch = x;
    p->next = NULL;
}

int isRotation(char s1[], char s2[]){
    if (strlen(s1) != strlen(s2))
        return 0;
    int flag = 1;
    for(int i = 0; i < strlen(s1);i++){
        if(s1[i]!=s2[i]){
            flag = 0;
            break;
        } 
    }
    if(flag) return 1;
    link *head = (link *)malloc(sizeof(link));
    head->ch = '\0';
    head->next = NULL;
    for (int i = 0; i < strlen(s1); i++)
        add(head, s1[i]);
    link *p = head;
    while (p->next)
        p = p->next;
    p->next = head->next;
    p = head->next;
    link *pp = p->next;
    while (pp != p){
        int flag = 1;
        link *temp = pp;
        for (int i = 0; i < strlen(s2); i++){
            if (temp->ch != s2[i]){
                flag = 0;
                break;
            }
            else
                temp = temp->next;
        }
        if (flag == 0)
            pp = pp->next;
        else
            return flag;
    }
    return 0;
}

int main(){
    char s[N+1],t[N+1];
    scanf("%s%s",s,t);

    //********** isRotation is called here *************
    if(isRotation(s,t)) printf("\"%s\" is a rotation of \"%s\"\n",s,t);
    else printf("\"%s\" is NOT a rotation of \"%s\"\n",s,t);
    //**************************************************

    return 0;
}

1035.二分查找

Write a function binarySearch(a, n, x) that searches x integer array a of length n, and returns the index of a (-1 if x can not be found in a).

Assume elements of a are entered in descending order, and the value of evey element is unique.

Write a program to call binarySearch(a, n, x).

/***************************************************************/
/*                                                             */
/*  DON'T MODIFY main function ANYWAY!                         */
/*                                                             */
/***************************************************************/

#include <stdio.h>

int binarySearch(int a[], int n, int x) {
    // TODO: your function definition
}

/***************************************************************/
#define N 100000
int a[N];
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    //********** binarySearch is called here *************
    int q, x;
    scanf("%d", &q);
    for (int i = 0; i < q; i++) {
        scanf("%d", &x);
        printf("%d\n", binarySearch(a, n, x));
    }
    //**************************************************
    return 0;
}

题解：

这题我踩雷了，数组是按照降序排列的，一定要看清楚。二分查找算法不必细说，注意分开处理奇偶情况的二分（c特性）。

代码：

#include <stdio.h>

int binarySearch(int *a, int n, int x){
    int mid;
    int left = 0;
    int right = n-1;
    while(left<=right){
        if ((right + left) % 2 != 0)
            mid = (right + left) / 2 + 1;
        else
            mid = (right + left) / 2;
        if (a[mid] == x) return mid;
        else if(a[mid] < x) right = mid-1;
        else left = mid+1;
    }
    return -1;
}

#define N 100000
int a[N];
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    //********** binarySearch is called here *************
    int q, x;
    scanf("%d", &q);
    for (int i = 0; i < q; i++) {
        scanf("%d", &x);
        printf("%d\n", binarySearch(a, n, x));
    }
    //**************************************************
    return 0;
}