前言

《算法笔记》 vector的使用

一、题目分析

题目见：http://codeup.hustoj.com/problem.php?cid=100000596&pid=1
大致题意：给出每个学生的选课表，求出每门课程的学生名单

二、需求分析

1.输入分析

每个输入文件包含一个测试用例。
第一行输入学生总数N(<=40000)和课程总数K(<=2500)。
然后输入N行数据，每行包含学生名字（3个大写字母加一位数字（0~9））、一个正整数C（<=20，是学生注册的课程数）、C个课程编号（从1到K）。

2.输出分析

按课程编号升序输出每门课的学生名单。每门课程首先将课程编号和注册人数在一行中输出，然后字典序输出学生名字，每个名字占一行。

3.功能分析

（1）输入学生的课程信息
（2）分析每门课的选课名单
（3）输出课程的学生名单

4.测试用例

输入：

10 5
ZOE1 2 4 5
ANN0 3 5 2 1
BOB5 5 3 4 2 1 5
JOE4 1 2
JAY9 4 1 2 5 4
FRA8 3 4 2 5
DON2 2 4 5
AMY7 1 5
KAT3 3 5 4 2
LOR6 4 2 4 1 5

输出：

1 4
ANN0
BOB5
JAY9
LOR6
2 7
ANN0
BOB5
FRA8
JAY9
JOE4
KAT3
LOR6
3 1
BOB5
4 7
BOB5
DON2
FRA8
JAY9
KAT3
LOR6
ZOE1
5 9
AMY7
ANN0
BOB5
DON2
FRA8
JAY9
KAT3
LOR6
ZOE1

三、概要设计

1.数据结构

通过字符串hash将学生名字映射为整数，名字可使用整数保存。
课程的学生名单使用二维整型数组保存。
学生的课程信息也可以使用二维整型数组来进行保存。

2.基本操作

基本操作	操作结果
name_to_id()	将名字转换为整数id
id_to_name()	将整数id转换为名字
course_list_fit()	输入学生的课表，构建出课程的学生名单
course_list_out()	输出课程的学生名单

3.程序模块及调用图

（1）主程序模块main()
（2）名字转换id模块name_to_id()
（3）id转换名字模块id_to_name()
（4）课表构建模块course_list_fit()
（5）课程名单输出模块course_list_out()
模块调用图：
在这里插入图片描述

四、详细设计

1.数据结构

课表使用二维整数数组来保存，第一维维度为2500，代表课程，0 ~ 2499对应1 ~ 2500的课程，第二维使用vector，保存每个学生名字的id。

2.各模块详细设计

（1）主程序模块
首先调用课程构建模块通过学生的课表分析出课程的学生名单，然后调用课程名单输出模块。
（2）名字转换id模块
前3位是二十六进制数，后一位是十进制数
名字前三位减去字符‘A’，后一位减去字符’0‘
C₁C₂C₃C₄
hash(C₁C₂C₃C₄)=C₁ * 26² * 10+C₂ * 26 * 10+C₃ * 10 +C₄=((C₁*26+C₂) *26+C₃) *10+C₄
通过这个公式计算出id即可。
（3）id转换名字模块
名字转换id的逆过程。
（4）课表构建模块
通过输入的课程编号确定课表的对应位置（编号-1），将对应的名字通过name_to_id()得到id保存到课表里。
（5）课程名单输出模块
遍历课表，将学生id升序排列（由hash构建过程可知即为名字的字典序），名字的输出通过调用id_to_name()。

五、代码编写

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

const int maxn=2500;
vector <int> course[maxn];
int N,K;

int name_to_id(char name[5]){
    int id=0;
    for(int i=0;i<=2;i++){
        id=id*26+(name[i]-'A');
    }
    id=id*10+name[3]-'0';
    return id;
}

void id_to_name(int id,char name[5]){
    name[4]='\0';
    name[3]=id%10+'0';
    id=id/10;
    for(int i=2;i>=0;i--){
        name[i]=id%26+'A';
        id=id/26;
    }
}

void course_list_fit(){
    char name[5];
    int course_num;
    int index;

    scanf("%d %d",&N,&K);

    for(int i=0;i<N;i++){
        scanf("%s",name);
        scanf("%d",&course_num);
        int id=name_to_id(name);
        while(course_num--){
            scanf("%d",&index);
            course[index-1].push_back(id);
        }
    }
}

void course_list_out(){
    int i,j;
    char name[5];
    for(i=0;i<K;i++){
        int index=i+1;
        printf("%d %d\n",index,course[i].size());
        sort(course[i].begin(),course[i].end());
        vector <int>::iterator it=course[i].begin();
        for(;it!=course[i].end();it++){
            id_to_name(*it,name);
            printf("%s\n",name);
        }
    }
}


int main(){
    course_list_fit();
    course_list_out();
    return 0;
}

六、总结

1.遇到的问题

（1）程序不输出学生的名字，将id转换为名字时函数返回指针是空的
出现问题的原代码如下：

char* id_to_name(int id){
	char name[5];
    name[4]='\0';
    name[3]=id%10+'0';
    id=id/10;
    for(int i=2;i>=0;i--){
        name[i]=id%26+'A';
        id=id/26;
    }
}

分析：
该思路是将函数内的name字符数组的指针作为返回值，进而得到解析出的名字。
但是由于name在该函数中是局部变量，在函数调用完成后name指向的内容被释放，name变为空指针，并不能实现返回的效果。这里的局部变量实际上是在栈空间里面。
解决方法：
只要name数组在函数调用后空间不被释放即可。