数据结构PTA 进阶实验5-3.1 航空公司VIP客户查询题目解法

53 阅读 0 评论 35 点赞

我是靠谱客的博主温婉向日葵，最近开发中收集的这篇文章主要介绍数据结构PTA 进阶实验5-3.1 航空公司VIP客户查询题目解法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

进阶实验5-3.1 航空公司VIP客户查询

题目
解法

题目

不少航空公司都会提供优惠的会员服务，当某顾客飞行里程累积达到一定数量后，可以使用里程积分直接兑换奖励机票或奖励升舱等服务。现给定某航空公司全体会员的飞行记录，要求实现根据身份证号码快速查询会员里程积分的功能。

输入格式:
输入首先给出两个正整数N（≤10⁵）和K（≤500）。其中K是最低里程，即为照顾乘坐短程航班的会员,航空公司还会将航程低于K公里的航班也按K公里累积。随后N行，每行给出一条飞行记录。飞行记录的输入格式为：18位身份证号码（空格）飞行里程。其中身份证号码由17位数字加最后一位校验码组成，校验码的取值范围为0~9和x共11个符号；飞行里程单位为公里，是(0, 15 000]区间内的整数。然后给出一个正整数M（≤10⁵），随后给出M行查询人的身份证号码。

输出格式:
对每个查询人，给出其当前的里程累积值。如果该人不是会员，则输出No Info。每个查询结果占一行。

输入样例:

4 500
330106199010080419 499
110108198403100012 15000
120104195510156021 800
330106199010080419 1
4
120104195510156021
110108198403100012
330106199010080419
33010619901008041x

输出样例:

800
15000
1000
No Info

解法

思路

本题还是常规的哈希表操作+额外小功能。常规操作包括：建立表，插入，查找。
额外小功能分别是：身份证的哈希函数的构造、Cell类型中添加计算里程的数据类型（用int即可）
身份证的哈希函数，可以提取指定的随机位，最好不要把所有的身份证号码都存储起来，而且存身份证号不要用整型，应该用字符串类型。

实现

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define MAXCHAR 18
typedef enum{empty, exist} EntryType;
typedef char EleType[MAXCHAR+1];
typedef struct HashEntry Cell;
struct HashEntry
{
EleType Data;
int Distance;
EntryType Info;
};
typedef struct TblNode *HashTable;
struct TblNode
{
int K;
int TableSize;
Cell *Cells;
};
HashTable CreateTable(int N)
{
HashTable H = (HashTable)malloc(sizeof(struct TblNode));
H->TableSize = 2*N;
H->Cells = (Cell*)malloc(H->TableSize*sizeof(struct HashEntry));
for(int i=0; i<H->TableSize; i++)
{
strcpy(H->Cells[i].Data,"");
H->Cells[i].Info = empty;
H->Cells[i].Distance = 0;
}
return H;
}
int Hash(HashTable H, EleType key)
{
//6,10,14,16,17,18
int hkey;
int hkey1 = (key[5]-'0')*pow(10,4) + (key[9]-'0')*pow(10,3) + (key[13]-'0')*pow(10,2) + (key[15]-'0')*pow(10,1) + (key[16]-'0');
if(key[17] == 'x')
hkey = hkey1*10+10;
else
hkey = hkey1*10 + key[17]-'0';
return hkey%H->TableSize;
}
int LinearFind(HashTable H, EleType key)
{
int CurPos, NewPos;
CurPos = NewPos = Hash(H, key);
int count = 0;
while(H->Cells[NewPos].Info != empty && strcmp(H->Cells[NewPos].Data, key))
{
count++;
NewPos = CurPos + count;
if(NewPos>=H->TableSize)
NewPos = NewPos%H->TableSize;
}
return NewPos;
}
void Insert(HashTable H, EleType key, int D)
{
int Pos = LinearFind(H, key);
if(H->Cells[Pos].Info == empty)
{
strcpy(H->Cells[Pos].Data, key);
H->Cells[Pos].Info = exist;
if(D<H->K)
H->Cells[Pos].Distance = H->K;
else
H->Cells[Pos].Distance = D;
}
else
{
if(D<H->K)
H->Cells[Pos].Distance += H->K;
else
H->Cells[Pos].Distance += D;
}
}
void PrintResults(HashTable H, EleType key)
{
int Pos = LinearFind(H, key);
if(H->Cells[Pos].Info == empty)
printf("No Infon");
else
{
printf("%dn", H->Cells[Pos].Distance);
}
}
int main()
{
int N,K,Dist,i;
EleType key;
scanf("%d %d", &N, &K);
HashTable H = CreateTable(N);
H->K = K;
EleType UserID;
for(i=0; i<N; i++)
{
scanf("%s", UserID);
scanf("%d", &Dist);
Insert(H, UserID, Dist);
}
int M;
scanf("%d", &M);
for(i=0; i<M; i++)
{
scanf("%s", UserID);
PrintResults(H, UserID);
}
return 0;
}