问题与解答

问题描述

对给定的一个字符串，找出有重复的字符，并给出其位置。

输入格式

输入包括一个由字母和数字组成的字符串，其长度不超过100。

输出格式

可能有多组测试数据，对于每组数据，

按照样例输出的格式将字符出现的位置标出。

1、下标从0开始。

2、相同的字母在一行表示出其出现过的位置。

样例输入

abcaaAB12ab12

样例输出

a:0,a:3,a:4,a:9

b:1,b:10

1:7,1:11

2:8,2:12

样例说明

给定字符串中重复的字母有a,b,1,2，依次输出上述每个字母在字符串中的全部位置。

//找位置

//hash表+拉链法

#include<stdio.h>

#include<string.h>

#include<vector>

using namespace std;

struct Node{

    char element;

    int positon;

};

vector<Node> Hash[125];

//hash表，拉链法处理冲突（实现类似图的邻接矩阵）

//hash函数为直接定址：每个字符c对应的ASCII码，大小写字母的ASCII不超过125

//hash表的每个元素是一个变长数组(vector)，vector中存储结点Node（包含字符c以及对应的下标位置position）

bool Vis[125] = {false};

//标记数组：Vis[i] = true 表示在哈希表中映射为i的值已经被打印过，无需再打印

void FindPostion(char* s);  //找位置并按照题目要求输出

void InsertElement(char c, int position);  //将字符串中的字符插入hash表

int main(){

    char s[100];

    while(scanf("%s", s) != EOF){  //多点输入

        FindPostion(s);

    }

}

void FindPostion(char *s){

    int i,j,index,size;

    int length = strlen(s);

    for(i = 0; i < length; i++)  //将字符串s中的每个字符插入hash表

        InsertElement(s[i], i);

    for(i = 0; i < length; i++){

        index = s[i] - '0';  //直接定址：得到当前字符s[i]在hash表中的位置

        size = Hash[index].size();  //存储当前字符s[i]的变长数组的大小

        if(size > 1 && Vis[index] == false){ //size>1说明有s[i]有重复，Vis[]数组防止多次打印结果

            Vis[index] = true;  //标记，防止多次打印结果

            for(j = 0; j < size; j++){ //遍历vector[index]，打印结果

                if(j == size-1)

                    printf("%c:%d", Hash[index][j].element, Hash[index][j].positon);

                else

                    printf("%c:%d,", Hash[index][j].element, Hash[index][j].positon);

            }

            printf("\n");

        }

    }

}

void InsertElement(char c, int position){ //将字符c及其所在的位置存入hash表中

    Node n;

    n.element = c;

    n.positon = position;

    int index = c -'0';  //直接定址：得到当前字符s[i]在hash表中的位置

    Hash[index].push_back(n);  //插入

}

题后反思：调试记录

打印顺序错误

改动前:遍历hash表中的每个vector，如果Hash[i].size()>1，则打印结果。
问题：
- 结果按照字符在hash表中的顺序打印而不是在字符串中的顺序打印；
- hash[i].size>1判断125次
改动后：
- 按照原顺序输出
- hash[i].size>1判断次数等于字符串长度

多次打印

未加入Vis[]数组时，如果字符'a'在字符串中出现n次，那么'a'的相关结果就会打印n次

巴特西

<数据结构>XDOJ333.找位置

问题与解答

题后反思：调试记录

打印顺序错误

多次打印

最新文章

热门文章