北航数据结构与程序设计查找与排序编程题

单词查找（查找——基本题）

【问题描述】

从标准输入中读入一个英文单词及查找方式，在一个给定的英文常用单词字典文件dictionary3000.txt中查找该单词，返回查找结果（查找到返回1，否则返回0）和查找过程中单词的比较次数。查找前，先将所有字典中单词读入至一个单词表（数组）中，然后按要求进行查找。字典中单词总数不超过3500，单词中的字符都是英文小写字母，并已按字典序排好序（可从课件下载区下载该字典文件）。字典中的单词和待查找单词的字符个数不超过20。

注意：读取文件中的单词时，若要判断行末的换行符，换行符可能是’\n’，也可能是两个字符：‘\r’和’\n’。

查找方式说明：查找方式以1~4数字表示，每个数字含义如下：

1：在单词表中以顺序查找方式查找，因为单词表已排好序，遇到相同的或第一个比待查找的单词大的单词，就要终止查找；

2：在单词表中以折半查找方式查找（折半查找的实现方式要参考上课PPT中的实现方式）；

3：在单词表中通过索引表来获取单词查找范围，并在该查找范围中以折半方式查找。索引表构建方式为：以26个英文字母为头字母的单词在字典中的起始位置和单词个数来构建索引表，如：

该索引表表明以字母a开头的单词在单词表中的开始下标位置为0，单词个数为248。

4：按下面给定的hash函数为字典中单词构造一个hash表，hash冲突时按字典序依次存放单词。hash查找遇到冲突时，采用链地址法处理，在冲突链表中找到或未找到(遇到第一个比待查找的单词大的单词或链表结束)便结束查找。

/* compute hash value for string */

#define NHASH 3001

#define MULT 37

unsigned int hash(char *str)

{

   unsigned int h=0;

   char *p;



   for(p=str; *p!='\0'; p++)

          h = MULT*h + *p;

   return h % NHASH;
1
2
3
4
5
6
7
8
9
10
11

}

提示：hash表可以构建成指针数组，hash冲突的单词形成一有序链表。

【输入形式】

单词字典文件dictionary3000.txt存放在当前目录下，待查找单词和查找方式从标准输入读取。待查找单词只包含英文小写字母，与表示查找方式的整数之间以一个空格分隔。

【输出形式】

将查找结果和单词比较次数输出到标准输出上，两整数之间以一个空格分隔。
【样例输入与输出】
单词字典文件dictionary3000.txt与课件下载中提供的相同，下面两列中，左侧为待查找单词与查找方式，右侧为对应的输出结果：

【样例说明】

wins在单词字典中不存在，4种查找方式都输出结果0，顺序查找、折半查找、索引查找和hash查找的单词比较次数分别为：3314、12、7和2次（wins的hash位置与字典中physics和suggest相同）。

yes在单词字典中存在，4种查找方式都输出结果1，顺序查找、折半查找、索引查找和hash查找的单词比较次数分别为：3357、10、4和1。

【评分标准】

该题要求输出查找结果和查找过程中的单词比较次数，提交程序名为find.c。

---

首先放上dictionary的链接：（有点长大家直接拖到后面）
a
abandon
abandoned
ability
able
about
above
abroad
absence
absent
absolute
absolutely
absorb
abuse
academic
accent
accept
acceptable
access
accident
accidental
accidentally
accommodation
accompany
according
account
accurate
accurately
accuse
achieve
achievement
acid
acknowledge
acquire
across
act
action
active
actively
activity
actor
actual
actually
ad
adapt
add
addition
additional
address
adequate
adequately
adjust
admiration
admire
admit
adopt
adult
advance
advanced
advantage
adventure
advertise
advertisement
advertising
advice
advise
affair
affect
affection
afford
afraid
after
afternoon
afterwards
again
against
age
aged
agency
agent
aggressive
ago
agree
agreement
ahead
aid
aim
air
aircraft
airport
alarm
alarmed
alarming
alcohol
alcoholic
alive
all
allied
allow
ally
almost
alone
along
alongside
aloud
alphabet
alphabetical
alphabetically
already
also
alter
alternative
alternatively
although
altogether
always
am
amaze
amazed
amazing
ambition
ambulance
among
amount
amuse
amused
amusing
an
analyse
analysis
ancient
and
anger
angle
angrily
angry
animal
ankle
anniversary
announce
annoy
annoyed
annoying
annual
annually
another
answer
anti
anticipate
anxiety
anxious
anxiously
any
anyone
anything
anyway
anywhere
apart
apartment
apologize
apparent
apparently
appeal
appear
appearance
apple
application
apply
appoint
appointment
appreciate
approach
appropriate
approval
approve
approving
approximate
approximately
april
area
argue
argument
arise
arm
armed
arms
army
around
arrange
arrangement
arrest
arrival
arrive
arrow
art
article
artificial
artificially
artist
artistic
as
ashamed
aside
ask
asleep
aspect
assist
assistance
assistant
associate
associated
association
assume
assure
at
atmosphere
atom
attach
attached
attack
attempt
attempted
attend
attention
attitude
attorney
attract
attraction
attractive
audience
august
aunt
author
authority
automatic
automatically
autumn
available
average
avoid
awake
award
aware
away
awful
awfully
awkward
awkwardly
baby
back
background
backward
backwards
bacteria
bad
badly
badtempered
bag
baggage
bake
balance
ball
ban
band
bandage
bank
bar
bargain
barrier
base
based
basic
basically
basis
bath
bathroom
battery
battle
bay
be
beach
beak
bear
beard
beat
beautiful
beautifully
beauty
because
become
bed
bedroom
beef
beer
before
begin
beginning
behalf
behave
behaviour
behind
belief
believe
bell
belong
below
belt
bend
beneath
benefit
bent
beside
bet
better
betting
between
beyond
bicycle
bid
big
bill
bin
biology
bird
birth
birthday
biscuit
bit
bite
bitter
bitterly
black
blade
blame
blank
blankly
blind
block
blonde
blood
blow
blue
board
boat
body
boil
bomb
bone
book
boot
border
bore
bored
boring
born
borrow
boss
both
bother
bottle
bottom
bound
bowl
box
boy
boyfriend
brain
branch
brand
brave
bread
break
breakfast
breast
breath
breathe
breathing
breed
brick
bridge
brief
briefly
bright
brightly
brilliant
bring
broad
broadcast
broadly
broken
brother
brown
brush
bubble
budget
build
building
bullet
bunch
burn
burnt
burst
bury
bus
bush
business
businessman
busy
but
butter
button
buy
buyer
by
bye
cabinet
cable
cake
calculate
calculation
call
calm
calmly
camera
camp
campaign
camping
can
cancel
cancer
candidate
candy
cannot
cap
capable
capacity
capital
captain
capture
car
card
cardboard
care
career
careful
carefully
careless
carelessly
carpet
carrot
carry
case
cash
cast
castle
cat
catch
category
cause
cd
cease
ceiling
celebrate
celebration
cell
cellphone
cent
centimetre
central
centre
century
ceremony
certain
certainly
certificate
chain
chair
chairman
challenge
chamber
chance
change
channel
chapter
character
characteristic
charge
charity
chart
chase
chat
cheap
cheaply
cheat
check
cheek
cheerful
cheerfully
cheese
chemical
chemist
chemistry
cheque
chest
chew
chicken
chief
child
chin
chip
chocolate
choice
choose
chop
church
cigarette
cinema
circle
circumstance
citizen
city
civil
claim
clap
class
classic
classroom
clean
clear
clearly
clerk
clever
click
client
climate
climb
climbing
clock
close
closed
closely
closet
cloth
clothes
clothing
cloud
club
cm
coach
coal
coast
coat
code
coffee
coin
cold
coldly
collapse
colleague
collect
collection
college
colour
coloured
column
combination
combine
come
comedy
comfort
comfortable
comfortably
command
comment
commercial
commission
commit
commitment
committee
common
commonly
communicate
communication
community
company
compare
comparison
compete
competition
competitive
complain
complaint
complete
completely
complex
complicate
complicated
computer
concentrate
concentration
concept
concern
concerned
concerning
concert
conclude
conclusion
concrete
condition
conduct
conference
confidence
confident
confidently
confine
confined
confirm
conflict
confront
confuse
confused
confusing
confusion
congratulations
congress
connect
connection
conscious
consequence
conservative
consider
considerable
considerably
consideration
consist
constant
constantly
construct
construction
consult
consumer
contact
contain
container
contemporary
content
contest
context
continent
continue
continuous
continuously
contract
contrast
contrasting
contribute
contribution
control
controlled
convenient
convention
conventional
conversation
convert
convince
cook
cooker
cookie
cooking
cool
cope
copy
core
corner
correct
correctly
cost
cottage
cotton
cough
coughing
could
council
count
counter
country
countryside
county
couple
courage
course
court
cousin
cover
covered
covering
cow
crack
cracked
craft
crash
crazy
cream
create
creature
credit
crime
criminal
crisis
crisp
criterion
critical
criticism
criticize
crop
cross
crowd
crowded
crown
crucial
cruel
crush
cry
ct
cultural
culture
cup
cupboard
curb
cure
curious
curiously
curl
curly
current
currently
curtain
curve
curved
custom
customer
customs
cut
cycle
cycling
dad
daily
damage
damp
dance
dancer
dancing
danger
dangerous
dare
dark
data
date
daughter
day
dead
deaf
deal
dear
death
debate
debt
decade
decay
december
decide
decision
declare
decline
decorate
decoration
decorative
decrease
deep
deeply
defeat
defence
defend
define
definite
definitely
definition
degree
delay
deliberate
deliberately
delicate
delight
delighted
deliver
delivery
demand
demonstrate
dentist
deny
department
departure
depend
deposit
depress
depressed
depressing
depth
derive
describe
description
desert
deserted
deserve
design
desire
desk
desperate
desperately
despite
destroy
destruction
detail
detailed
determination
determine
determined
develop
development
device
devote
devoted
diagram
diamond
diary
dictionary
die
diet
difference
different
differently
difficult
difficulty
dig
dinner
direct
direction
directly
director
dirt
dirty
disabled
disadvantage
disagree
disagreement
disappear
disappoint
disappointed
disappointing
disappointment
disapproval
disapprove
disapproving
disaster
disc
discipline
discount
discover
discovery
discuss
discussion
disease
disgust
disgusted
disgusting
dish
dishonest
dishonestly
disk
dislike
dismiss
display
dissolve
distance
distinguish
distribute
distribution
district
disturb
disturbing
divide
division
divorce
divorced
do
doctor
document
dog
dollar
domestic
dominate
door
dot
double
doubt
down
downstairs
downward
downwards
dozen
dr
draft
drag
drama
dramatic
dramatically
draw
drawer
drawing
dream
dress
dressed
drink
drive
driver
driving
drop
drug
drugstore
drum
drunk
dry
due
dull
dump
during
dust
duty
dvd
dying
each
ear
early
earn
earth
ease
easily
east
eastern
easy
eat
economic
economy
edge
edition
editor
educate
educated
education
effect
effective
effectively
efficient
efficiently
effort
eg
egg
either
elbow
elderly
elect
election
electric
electrical
electricity
electronic
elegant
element
elevator
else
elsewhere
email
embarrass
embarrassed
embarrassing
embarrassment
emerge
emergency
emotion
emotional
emotionally
emphasis
emphasize
empire
employ
employee
employer
employment
empty
enable
encounter
encourage
encouragement
end
ending
enemy
energy
engage
engaged
engine
engineer
engineering
enjoy
enjoyable
enjoyment
enormous
enough
enquiry
ensure
enter
entertain
entertainer
entertaining
entertainment
enthusiasm
enthusiastic
entire
entirely
entitle
entrance
entry
envelope
environment
environmental
equal
equally
equipment
equivalent
error
escape
especially
essay
essential
essentially
establish
estate
estimate
etc
euro
even
evening
event
eventually
ever
every
everyone
everything
everywhere
evidence
evil
exact
exactly
exaggerate
exaggerated
exam
examination
examine
example
excellent
except
exception
exchange
excite
excited
excitement
exciting
exclude
excluding
excuse
executive
exercise
exhibit
exhibition
exist
existence
exit
expand
expect
expectation
expected
expense
expensive
experience
experienced
experiment
expert
explain
explanation
explode
explore
explosion
export
expose
express
expression
extend
extension
extensive
extent
extra
extraordinary
extreme
extremely
eye
face
facility
fact
factor
factory
fail
failure
faint
faintly
fair
fairly
faith
faithful
faithfully
fall
false
fame
familiar
family
famous
fan
fancy
far
farm
farmer
farming
farther
fashion
fashionable
fast
fasten
fat
father
faucet
fault
favour
favourite
fear
feather
feature
february
federal
fee
feed
feel
feeling
fellow
female
fence
festival
fetch
fever
few
field
fight
fighting
figure
file
fill
film
final
finally
finance
financial
find
fine
finely
finger
finish
finished
fire
firm
firmly
first
fish
fishing
fit
fix
fixed
flag
flame
flash
flat
flavour
flesh
flight
float
flood
floor
flour
flow
flower
flu
fly
flying
focus
fold
folding
follow
following
food
foot
football
for
force
forecast
foreign
forest
forever
forget
forgive
fork
form
formal
formally
former
formerly
formula
fortune
forward
found
foundation
frame
free
freedom
freely
freeze
frequent
frequently
fresh
freshly
friday
fridge
friend
friendly
friendship
frighten
frightened
frightening
from
front
frozen
fruit
fry
fuel
full
fully
fun
function
fund
fundamental
funeral
funny
fur
furniture
further
future
gain
gallon
gamble
gambling
game
gap
garage
garbage
garden
gas
gasoline
gate
gather
gear
general
generally
generate
generation
generous
generously
gentle
gentleman
gently
genuine
genuinely
geography
get
giant
gift
girl
girlfriend
give
glad
glass
glasses
global
glove
glue
gm
go
goal
god
gold
good
goodbye
goods
govern
government
governor
grab
grade
gradual
gradually
grain
gram
grammar
grand
grandchild
granddaughter
grandfather
grandmother
grandparent
grandson
grant
grass
grateful
grave
gray
great
greatly
green
grey
groceries
grocery
ground
group
grow
growth
guarantee
guard
guess
guest
guide
guilty
gun
guy
habit
hair
hairdresser
half
hall
hammer
hand
handle
hang
happen
happily
happiness
happy
hard
hardly
harm
harmful
harmless
hat
hate
hatred
have
he
head
headache
heal
health
healthy
hear
hearing
heart
heat
heating
heaven
heavily
heavy
heel
height
hell
hello
help
helpful
hence
her
here
hero
hers
herself
hesitate
hi
hide
high
highlight
highly
highway
hill
him
himself
hip
hire
his
historical
history
hit
hobby
hold
hole
holiday
hollow
holy
home
homework
honest
honestly
honour
hook
hope
horizontal
horn
horror
horse
hospital
host
hot
hotel
hour
house
household
housing
how
however
huge
human
humorous
humour
hungry
hunt
hunting
hurry
hurt
husband
ice
idea
ideal
ideally
identify
identity
ie
if
ignore
ill
illegal
illegally
illness
illustrate
image
imaginary
imagination
imagine
immediate
immediately
immoral
impact
impatient
impatiently
implication
imply
import
importance
important
importantly
impose
impossible
impress
impressed
impression
impressive
improve
improvement
in
inability
inch
incident
include
including
income
increase
increasingly
indeed
independence
independent
independently
index
indicate
indication
indirect
indirectly
individual
indoor
indoors
industrial
industry
inevitable
inevitably
infect
infected
infection
infectious
influence
inform
informal
information
ingredient
initial
initially
initiative
injure
injured
injury
ink
inner
innocent
inquiry
insect
insert
inside
insist
install
instance
instead
institute
institution
instruction
instrument
insult
insulting
insurance
intelligence
intelligent
intend
intended
intention
interest
interested
interesting
interior
internal
international
internet
interpret
interpretation
interrupt
interruption
interval
interview
into
introduce
introduction
invent
invention
invest
investigate
investigation
investment
invitation
invite
involve
involved
involvement
iron
irritate
irritated
irritating
ish
island
issue
it
item
its
itself
jacket
jam
january
jealous
jeans
jelly
jewellery
job
join
joint
jointly
joke
journalist
journey
joy
judge
judgement
juice
july
jump
june
junior
just
justice
justified
justify
keen
keep
key
keyboard
kick
kid
kill
killing
kilogram
kilometre
kind
kindly
kindness
king
kiss
kitchen
km
knee
knife
knit
knitted
knitting
knock
knot
know
knowledge
l
label
laboratory
labour
lack
lacking
lady
lake
lamp
land
landscape
lane
language
large
largely
last
late
later
latest
latter
laugh
launch
law
lawyer
lay
layer
lazy
lead
leader
leading
leaf
league
lean
learn
least
leather
leave
lecture
left
leg
legal
legally
lemon
lend
length
less
lesson
let
letter
level
library
licence
license
lid
lie
life
lift
light
lightly
like
likely
limit
limited
line
link
lip
liquid
list
listen
literature
litre
little
live
lively
living
load
loan
local
locally
locate
located
location
lock
logic
logical
lonely
long
look
loose
loosely
lord
lorry
lose
loss
lost
lot
loud
loudly
love
lovely
lover
low
loyal
luck
lucky
luggage
lump
lunch
lung
machine
machinery
mad
magazine
magic
mail
main
mainly
maintain
major
majority
make
makeup
male
mall
man
manage
management
manager
manner
manufacture
manufacturer
manufacturing
many
map
march
mark
market
marketing
marriage
married
marry
mass
massive
master
match
matching
mate
material
mathematics
matter
maximum
may
maybe
mayor
me
meal
mean
meaning
means
meanwhile
measure
measurement
meat
media
medical
medicine
medium
meet
meeting
melt
member
membership
memory
mental
mentally
mention
menu
mere
merely
mess
message
metal
method
metre
mg
mid
midday
middle
midnight
might
mild
mile
military
milk
milligram
millimetre
mind
mine
mineral
minimum
minister
ministry
minor
minority
minute
mirror
miss
missing
mistake
mistaken
mix
mixed
mixture
mm
mobile
model
modern
mom
moment
monday
money
monitor
month
mood
moon
moral
morally
more
moreover
morning
most
mostly
mother
motion
motor
motorcycle
mount
mountain
mouse
mouth
move
movement
movie
moving
mr
mrs
ms
much
mud
multiply
mum
murder
muscle
museum
music
musical
musician
must
my
myself
mysterious
mystery
nail
naked
name
narrow
nation
national
natural
naturally
nature
navy
near
nearby
nearly
neat
neatly
necessarily
necessary
neck
need
needle
negative
neighbour
neighbourhood
neither
nephew
nerve
nervous
nervously
nest
net
network
never
nevertheless
new
newly
news
newspaper
next
nice
nicely
niece
night
no
nobody
noise
noisily
noisy
non
none
nonsense
nor
normal
normally
north
northern
nose
not
note
nothing
notice
noticeable
novel
november
now
nowhere
nuclear
number
nurse
nut
obey
object
objective
observation
observe
obtain
obvious
obviously
occasion
occasionally
occupied
occupy
occur
ocean
october
odd
oddly
of
off
offence
offend
offensive
offer
office
officer
official
officially
often
oh
oil
ok
old
oldfashioned
on
once
one
onion
only
onto
open
opening
openly
operate
operation
opinion
opponent
opportunity
oppose
opposed
opposing
opposite
opposition
option
or
orange
order
ordinary
organ
organization
organize
organized
origin
original
originally
other
otherwise
ought
our
ours
ourselves
out
outdoor
outdoors
outer
outline
output
outside
outstanding
oven
over
overall
overcome
owe
own
owner
pace
pack
package
packaging
packet
page
pain
painful
paint
painter
painting
pair
palace
pale
pan
panel
pants
paper
parallel
parent
park
parliament
part
particular
particularly
partly
partner
partnership
party
pass
passage
passenger
passing
passport
past
path
patience
patient
pattern
pause
pay
payment
peace
peaceful
peak
pen
pence
pencil
penny
pension
people
pepper
per
perfect
perfectly
perform
performance
performer
perhaps
period
permanent
permanently
permission
permit
person
personal
personality
personally
persuade
pet
petrol
phase
philosophy
phone
photocopy
photograph
photographer
photography
phrase
physical
physically
physics
piano
pick
picture
piece
pig
pile
pill
pilot
pin
pink
pint
pipe
pitch
pity
place
plain
plan
plane
planet
planning
plant
plastic
plate
platform
play
player
pleasant
pleasantly
please
pleased
pleasing
pleasure
plenty
plot
plug
plus
pm
pocket
poem
poetry
point
pointed
poison
poisonous
pole
police
policy
polish
polite
politely
political
politically
politician
politics
pollution
pool
poor
pop
popular
population
port
pose
position
positive
possess
possession
possibility
possible
possibly
post
pot
potato
potential
potentially
pound
pour
powder
power
powerful
practical
practically
practice
practise
praise
prayer
precise
precisely
predict
prefer
preference
pregnant
premises
preparation
prepare
prepared
presence
present
presentation
preserve
president
press
pressure
presumably
pretend
pretty
prevent
previous
previously
price
pride
priest
primarily
primary
prime
prince
princess
principle
print
printer
printing
prior
priority
prison
prisoner
private
privately
prize
probable
probably
problem
procedure
proceed
process
produce
producer
product
production
profession
professional
professor
profit
program
programme
progress
project
promise
promote
promotion
prompt
promptly
pronounce
pronunciation
proof
proper
properly
property
proportion
proposal
propose
prospect
protect
protection
protest
proud
proudly
prove
provide
provided
pt
pub
public
publication
publicity
publicly
publish
publishing
pull
punch
punish
punishment
pupil
purchase
pure
purely
purple
purpose
pursue
push
put
qualification
qualified
qualify
quality
quantity
quarter
queen
question
quick
quickly
quiet
quietly
quit
quite
quote
race
racing
radio
rail
railway
rain
raise
range
rank
rapid
rapidly
rare
rarely
rate
rather
raw
re
reach
react
reaction
read
reader
reading
ready
real
realistic
reality
realize
really
rear
reason
reasonable
reasonably
recall
receipt
receive
recent
recently
reception
reckon
recognition
recognize
recommend
record
recording
recover
red
reduce
reduction
refer
reference
reflect
reform
refrigerator
refusal
refuse
regard
regarding
region
regional
register
regret
regular
regularly
regulation
reject
relate
related
relation
relationship
relative
relatively
relax
relaxed
relaxing
release
relevant
relief
religion
religious
rely
remain
remaining
remains
remark
remarkable
remarkably
remember
remind
remote
removal
remove
rent
rented
repair
repeat
repeated
repeatedly
replace
reply
report
represent
representative
reproduce
reputation
request
require
requirement
rescue
research
reservation
reserve
resident
resist
resistance
resolve
resort
resource
respect
respond
response
responsibility
responsible
rest
restaurant
restore
restrict
restricted
restriction
result
retain
retire
retired
retirement
return
reveal
reverse
review
revise
revision
revolution
reward
rhythm
rice
rich
rid
ride
rider
ridiculous
riding
right
rightly
ring
rise
risk
rival
river
road
rob
rock
role
roll
romantic
roof
room
root
rope
rough
roughly
round
rounded
route
routine
row
royal
rub
rubber
rubbish
rude
rudely
ruin
ruined
rule
ruler
rumour
run
runner
running
rural
rush
sack
sad
sadly
sadness
safe
safely
safety
sail
sailing
sailor
salad
salary
sale
salt
salty
same
sample
sand
satisfaction
satisfied
satisfy
satisfying
saturday
sauce
save
saving
say
scale
scare
scared
scene
schedule
scheme
school
science
scientific
scientist
scissors
score
scratch
scream
screen
screw
sea
seal
search
season
seat
second
secondary
secret
secretary
secretly
section
sector
secure
security
see
seed
seek
seem
select
selection
self
sell
senate
senator
send
senior
sense
sensible
sensitive
sentence
separate
separated
separately
separation
september
series
serious
seriously
servant
serve
service
session
set
settle
several
severe
severely
sew
sewing
sex
sexual
sexually
shade
shadow
shake
shall
shallow
shame
shape
shaped
share
sharp
sharply
shave
she
sheep
sheet
shelf
shell
shelter
shift
shine
shiny
ship
shirt
shock
shocked
shocking
shoe
shoot
shooting
shop
shopping
short
shortly
shot
should
shoulder
shout
show
shower
shut
shy
sick
side
sideways
sight
sign
signal
signature
significant
significantly
silence
silent
silk
silly
silver
similar
similarly
simple
simply
since
sincere
sincerely
sing
singer
singing
single
sink
sir
sister
sit
site
situation
size
skilful
skilfully
skill
skilled
skin
skirt
sky
sleep
sleeve
slice
slide
slight
slightly
slip
slope
slow
slowly
small
smart
smash
smell
smile
smoke
smoking
smooth
smoothly
snake
snow
so
soap
social
socially
society
sock
soft
softly
software
soil
soldier
solid
solution
solve
some
somebody
somehow
something
sometimes
somewhat
somewhere
son
song
soon
sore
sorry
sort
soul
sound
soup
sour
source
south
southern
space
spare
speak
speaker
special
specialist
specially
specific
specifically
speech
speed
spell
spelling
spend
spice
spicy
spider
spin
spirit
spiritual
spite
split
spoil
spoken
spoon
sport
spot
spray
spread
spring
square
squeeze
stable
staff
stage
stair
stamp
stand
standard
star
stare
start
state
statement
station
statue
status
stay
steadily
steady
steal
steam
steel
steep
steeply
steer
step
stick
sticky
stiff
stiffly
still
sting
stir
stock
stomach
stone
stop
store
storm
story
stove
straight
strain
strange
strangely
stranger
strategy
stream
street
strength
stress
stressed
stretch
strict
strictly
strike
striking
string
strip
stripe
striped
stroke
strong
strongly
structure
struggle
student
studio
study
stuff
stupid
style
subject
substance
substantial
substantially
substitute
succeed
success
successful
successfully
such
suck
sudden
suddenly
suffer
suffering
sufficient
sufficiently
sugar
suggest
suggestion
suit
suitable
suitcase
suited
sum
summary
summer
sun
sunday
superior
supermarket
supply
support
supporter
suppose
sure
surely
surface
surname
surprise
surprised
surprising
surprisingly
surround
surrounding
surroundings
survey
survive
suspect
suspicion
suspicious
swallow
swear
swearing
sweat
sweater
sweep
sweet
swell
swelling
swim
swimming
swing
switch
swollen
symbol
sympathetic
sympathy
system
table
tablet
tackle
tail
take
talk
tall
tank
tap
tape
target
task
taste
tax
taxi
tea
teach
teacher
teaching
team
tear
technical
technique
technology
telephone
television
tell
temperature
temporarily
temporary
tend
tendency
tension
tent
term
terrible
terribly
test
text
than
thank
thanks
that
the
theatre
their
theirs
them
theme
themselves
then
theory
there
therefore
they
thick
thickly
thickness
thief
thin
thing
think
thinking
thirsty
this
thorough
thoroughly
though
thought
thread
threat
threaten
threatening
throat
through
throughout
throw
thumb
thursday
thus
ticket
tidy
tie
tight
tightly
till
time
timetable
tin
tiny
tip
tire
tired
tiring
title
to
today
toe
together
toilet
tomato
tomorrow
ton
tone
tongue
tonight
tonne
too
tool
tooth
top
topic
total
totally
touch
tough
tour
tourist
towards
towel
tower
town
toy
trace
track
trade
trading
tradition
traditional
traditionally
traffic
train
training
transfer
transform
translate
translation
transparent
transport
trap
travel
traveller
treat
treatment
tree
trend
trial
triangle
trick
trip
tropical
trouble
trousers
truck
true
truly
trust
truth
try
tube
tuesday
tune
tunnel
turn
tv
twice
twin
twist
twisted
type
typical
typically
tyre
ugly
ultimate
ultimately
umbrella
unable
unacceptable
uncertain
uncle
uncomfortable
unconscious
uncontrolled
under
underground
underneath
understand
understanding
underwater
underwear
undo
unemployed
unemployment
unexpected
unexpectedly
unfair
unfairly
unfortunate
unfortunately
unfriendly
unhappiness
unhappy
uniform
unimportant
union
unique
unit
unite
united
universe
university
unkind
unknown
unless
unlike
unlikely
unload
unlucky
unnecessary
unpleasant
unreasonable
unsteady
unsuccessful
untidy
until
unusual
unusually
unwilling
unwillingly
up
upon
upper
upset
upsetting
upside
upstairs
upward
upwards
urban
urge
urgent
us
use
used
useful
useless
user
usual
usually
vacation
valid
valley
valuable
value
van
variation
varied
variety
various
vary
vast
vegetable
vehicle
venture
version
vertical
very
via
victim
victory
video
view
village
violence
violent
violently
virtually
virus
visible
vision
visit
visitor
vital
vocabulary
voice
volume
vote
wage
waist
wait
waiter
wake
walk
walking
wall
wallet
wander
want
war
warm
warmth
warn
warning
wash
washing
waste
watch
water
wave
way
we
weak
weakness
wealth
weapon
wear
weather
web
website
wedding
wednesday
week
weekend
weekly
weigh
weight
welcome
well
west
western
wet
what
whatever
wheel
when
whenever
where
whereas
wherever
whether
which
while
whilst
whisper
whistle
white
who
whoever
whole
whom
whose
why
wide
widely
width
wife
wild
wildly
will
willing
willingly
willingness
win
wind
window
wine
wing
winner
winning
winter
wire
wise
wish
with
withdraw
within
without
witness
woman
wonder
wonderful
wood
wooden
wool
word
work
worker
working
world
worried
worry
worrying
worse
worship
worth
would
wound
wounded
wrap
wrapping
wrist
write
writer
writing
written
wrong
wrongly
yard
yawn
yeah
year
yellow
yes
yesterday
yet
you
young
your
yours
yourself
youth
zero
zone

---

首先，在文件中读取单词 的方法一定要会，尤其是对于结尾换行符的处理，这里用fscanf，不要用fgets，因为fgets会读取到后面的换行符。

int main()
{
    memset(dictionary,0,sizeof(char)*MAXLEN*MAXNUM);
    char buff[21];
    int i=0;
    FILE* fp=fopen("dictionary3000.txt","r");
    if(fp==NULL)
        return 0;
    while((fscanf(fp,"%s",buff))!=EOF)
    {
        strcpy(dictionary[i++],buff);
        memset(buff,0,MAXLEN);
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

完整代码：

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<assert.h>
#define MAXNUM 3367
#define MAXLEN 21
#define NHASH  3001
#define MULT  37
char dictionary[MAXNUM][MAXLEN];
typedef struct node
{
    int start;
    char block[1000][21];
    int total;
}INDEXNODE;
typedef struct node1
{
    char words[21];
    struct node1* next;
}HASHNODE;
unsigned int hash(char *str)
{
       unsigned int h=0;
       char *p;
       for(p=str; *p!='\0'; p++)
              h = MULT*h + *p;
       return h % NHASH;
}
void SequentialSearch(char*);
void BinSearch(char*);
void IndexSearch(char*);
void HashSearch(char*);
int main()
{
    //此处为从文件中读取单词并放在数组里
    memset(dictionary,0,sizeof(char)*MAXLEN*MAXNUM);
    char buff[21];
    int i=0;
    FILE* fp=fopen("dictionary3000.txt","r");
    if(fp==NULL)
        return 0;
    while((fscanf(fp,"%s",buff))!=EOF)
    {
        strcpy(dictionary[i++],buff);
        memset(buff,0,MAXLEN);
    }
    //
    
    //输入目标单词和查询方式，然后跳转到对应的接口
    char target[21];
    int N;
    scanf("%s",target);//注意，这里不能用gets，因为gets要一直读到换行，但是题目要求的输入方式是“单词 方式”，中间有一个空格
    scanf("%d",&N);

    switch (N)
    {
    case 1:
        SequentialSearch(target);
        break;
    case 2:
        BinSearch(target);
        break;
    case 3:
        IndexSearch(target);
        break;
    case 4:
        HashSearch(target);
        break;
    default:
        break;
    }    
    return 0;
}
void SequentialSearch(char* s)
{
    int i=0;
    int num=0;
    for(;i<MAXNUM;i++)
    {
        int cmp=strcmp(s,dictionary[i]);
        num++;
        if(cmp==0)
        {
            printf("%d %d",1,num);
            return;
        }
        else if(cmp<0)
        {
            num++;
            printf("%d %d",0,num-1);
            return;
        }
    }
    //这一步用于解决查找完了整个词典，也没有找到目标单词的情况
    if(i==MAXNUM)
        printf("%d %d",0,MAXNUM);   
}
void BinSearch(char* s)
{
    int left=0,right=MAXNUM-1;
    int num=0;
    while(left<=right)
    {
        int mid=(left+right)/2;
        int cmp=strcmp(s,dictionary[mid]);
        num++;

        if(cmp==0)
        {
            printf("%d %d",1,num);       
            break;   
        }
        else if(cmp>0)
            left=mid+1;
        else 
            right=mid-1;
    }
    if(left>right)
        printf("%d %d",0,num);
}
void IndexSearch(char* s)
{
    INDEXNODE block[26];
    int j=0;
    int num=0;
    int ch='a';
    for(int i=0;i<26;i++)
    {
        num=0;
        block[i].start=ch;
        for(;j<MAXNUM&&dictionary[j][0]==ch;j++)
        {
            strcpy(block[i].block[num++],dictionary[j]);
        }
        block[i].total=num;
        ch++;
    }

    int left=0,right=25,mid;
    while (left<=right)
    {
        mid=left+right;
        if(s[0]==block[mid].start)
        {
            if(block[mid].total==0)
            {
                printf("%d %d",0,0);
                return;
            }
            else
                break;
        }
        else if(s[0]>block[mid].start)
            left=mid+1;
        else
            right=mid-1;
    }

    int low=0,high=block[mid].total-1,middle;
    num=0;
    while(low<=high)
    {
        middle=(low+high)/2;
        int cmp=strcmp(s,block[mid].block[middle]);
        num++;
        if(cmp==0)
        {
            printf("%d %d",1,num);
            return;
        }
        else if(cmp>0)
        {
            low=middle+1;
        }
        else
            high=middle-1;
    }
    if(low>high)
        printf("%d %d",0,num);
}
void HashSearch(char* s)
{
    HASHNODE* table[MAXNUM];
    for(int i=0;i<MAXNUM;i++)
    {
        table[i]=(HASHNODE*)malloc(sizeof(HASHNODE));
        table[i]->words[0]='\0';
        table[i]->next=NULL;
    }

    for(int i=0;i<MAXNUM;i++)
    {
        unsigned int key=hash(dictionary[i]);
        HASHNODE* new = (HASHNODE*)malloc(sizeof(HASHNODE));
        new->next=NULL;
        strcpy(new->words,dictionary[i]);

        HASHNODE* cur=table[key];
        while(cur->next!=NULL)
            cur=cur->next;
        
        cur->next=new;
    }

    unsigned int  key=hash(s);
    int num=0;
    HASHNODE* cur=table[key];
    while(cur->next!=NULL)
    {
        int cmp=strcmp(s,cur->next->words);
        num++;
        if(cmp==0)
        {
            printf("%d %d",1,num);
            break;
        }
        else if(cmp>0)
            cur=cur->next;
        else 
        {
            printf("%d %d",0,num);
            break;
        }   
    }
    if(cur->next==NULL)
        printf("%d %d",0,num);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227

---

排座位（简）a

【问题描述】某班级要进行期末考试，准备考试时打乱座次，现已按照学号顺序人工为学生随机安排了座位号，但其中可能会出现漏排和重复安排座位的情况。编写程序读入人工安排的考试座位安排表T1，对安排情况进行检查，并对漏排和重复安排座位的情况进行修正，修正后，若学生人数为N，则每位学生考试座位安排应在1~N之间，其中没有缺号和重号。假设T1中学号信息不会出现重复，同一座位号最多有两位同学的座位号相同，并且座位号不会连续漏排；初始考试座位安排表存放在当前目录下的in.txt中，其中包括每位学生的学号、姓名和座位号，要求修正后的考试座位安排表输出到当前目录下的out.txt文件中。程序检查座位号的规则如下：
1、首先对考试座位安排表T1按座位号从小到大的顺序排序（原始考试安排可能有座位号相同情况，座位号相同时则按原始学号顺序排序），得到按座位号排序的安排表T2；

2、对表T2从头开始检查漏排座位号情况：假设当前表中安排的最大座位号为M，取M和N的较小值Q；从1号开始检查，若某个小于等于Q的座位序号没有安排学生，则将表T2的最后学生的座位设置为该座位号；若存在多个漏排座位，则从表T2最后依次向前设置；

3、然后再检查表T2中重排座位号情况：假设当前表中安排的最大座位号为m，将座位号重复的、学号较大的学生的座位号依次设置为m+1、m+2、m+3…；

4. 将调整好的表T2按学号由小到大序排序后按输出格式要求输出至指定输出文件中。

【输入形式】
从标准输入中读入学生人数（不超过100的正整数）。

初始考试座位安排表存储在当前目录下的in.txt文件中，已按照学号由小到大的顺序分行存储每位学生座位信息，依次为学生学号（不超过8位的正整数）、姓名（由不超过20位的英文字母组成）和座位号（不超过100的正整数），各数据间以一个空格分隔。最后一个学生座位信息后有回车换行。
【输出形式】
按照学号由小到大的顺序将修正后的考试座位安排表输出到当前目录下的out.txt文件中，每行依次为学号、姓名和座位号，各数据之间以一个空格分隔。
【样例输入】

24

假设当前目录下的in.txt文件内容如下：
18373001 ShiTian 7
18373002 WangLi 15
18373003 LiGuoHong 23
18373005 QianSanQiang 26
18373006 ZhangQiang 8
18373007 SunXiXi 2
18373010 LiXing 12
18373011 TangYing 20
18373012 YangYang 4
18373013 ZhaoGang 27
18373014 ZhouLiang 18
18373015 WuShuo 9
18373016 ZhengSiSi 13
18373017 WangGong 27
18373018 TianTian 21
18373020 LeiLei 16
18373021 ZhangLou 10
18373022 WangLei 17
18373025 SunTian 24
18373026 JinXiang 18
18373028 PangHong 11
18373029 GaoLiang 2
18373030 GaoHang 6
18373031 YangYang 22
【样例输出】
当前目录下的out.txt文件内容应为：
18373001 ShiTian 7
18373002 WangLi 15
18373003 LiGuoHong 19
18373005 QianSanQiang 5
18373006 ZhangQiang 8
18373007 SunXiXi 2
18373010 LiXing 12
18373011 TangYing 20
18373012 YangYang 4
18373013 ZhaoGang 3
18373014 ZhouLiang 18
18373015 WuShuo 9
18373016 ZhengSiSi 13
18373017 WangGong 1
18373018 TianTian 21
18373020 LeiLei 16
18373021 ZhangLou 10
18373022 WangLei 17
18373025 SunTian 14
18373026 JinXiang 24
18373028 PangHong 11
18373029 GaoLiang 23
18373030 GaoHang 6
18373031 YangYang 22
【样例说明】
初始考试座位安排表中有24位学生的排位信息，正确情况下这些学生安排的座位号应为1~24。初始人工安排的座位信息有1、3、5、14和19号座位漏排，有2、18和27号座位重复安排学生。先对漏排的座位进行修正：已安排的最大座位号为27，学号为18373017和18373013的学生分别安排了27号座位，按照漏排座位修正规则，先将18373017学生安排在1号座位，再将18373013学生安排在3号座位；同理分别将18373005学生安排在5号座位，将18373025学生安排在14号座位，18373003号学生安排在19号座位。当前安排的最大座位号为22，还有2号和18号座位重复，将2号重复的学号较大的18373029号学生安排在23号座位，将18号重复的学号较大的18373026号学生安排在24号座位。这样修正后按照学号由小到大的顺序输出学生座位信息到out.txt中。
【评分标准】
按照要求修正学生座位信息，提交程序文件名为seat.c。

---

这个题有一个易错的地方就是：调整规则的第二条。“当前表”应该是每调整一个学生的座位号，表都要更新一次。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct node
{
    int id;
    char name[21];
    int seat;
}STU;
int cmp1(const void*p1,const void*p2)
{
    return (*(STU*)p1).seat-(*(STU*)p2).seat;
}
int cmp2(const void*p1,const void*p2)
{
    return (*(STU*)p1).id-(*(STU*)p2).id;
}
int N=0;
STU* arr;

void SeatSort();//这个函数用于规则1中的初步排序
void CheckNeg();//这个用于规则2中的检查漏排
void CheckSame();//这个用于检查重复的
void OutPut();//这个用于最终打印
int main()
{
    FILE* fp=fopen("in.txt","r");
    if(fp==NULL)
        return 0;
    scanf("%d",&N);
    arr=(STU*)malloc(sizeof(STU)*N);
    for(int i=0;i<N;i++)
    {
        fscanf(fp,"%d %21s %d",&arr[i].id,arr[i].name,&arr[i].seat);
    }
    
    SeatSort();
    CheckNeg();
    CheckSame();
    OutPut();
    fclose(fp);
    return 0;
}
void SeatSort()
{
    qsort(arr,N,sizeof(STU),cmp1);
    for(int i=0;i<N;i++)
    {
        int start=i;
        int num=1;
        while(i+1<N&&arr[i].seat==arr[i+1].seat)
        {
            num++;
            i++;
        }
        if(num>1)
        {
            qsort(arr+start,num,sizeof(STU),cmp2);
        }
    } 
}
void CheckNeg()
{
    int M=arr[N-1].seat;
    int Q=M>N?N:M;
    int last=N-1;
    for(int i=1;i<=Q;i++)
    {
        int j=0;
        for(;j<N;j++)
        {
            if(arr[j].seat==i)
                break;
        }
        if(j==N)
        {
            arr[last].seat=i;
            qsort(arr,N,sizeof(STU),cmp1);
            M=arr[N-1].seat;
            Q=M>N?N:M;
        }
    }
    for(int i=0;i<N;i++)
    {
        int start=i;
        int num=1;
        while(i+1<N&&arr[i].seat==arr[i+1].seat)
        {
            num++;
            i++;
        }
        if(num>1)
        {
            qsort(arr+start,num,sizeof(STU),cmp2);
        }
    } 
}
void CheckSame()
{
    int M=arr[N-1].seat;
    for(int i=0;i<N;i++)
    {
        if(i+1<N&&arr[i].seat==arr[i+1].seat)
        {
            arr[i+1].seat=++M;
            i++;
        }
    }
    qsort(arr,N,sizeof(STU),cmp1);
    for(int i=0;i<N;i++)
    {
        int start=i;
        int num=1;
        while(i+1<N&&arr[i].seat==arr[i+1].seat)
        {
            num++;
            i++;
        }
        if(num>1)
        {
            qsort(arr+start,num,sizeof(STU),cmp2);
        }
    } 
}
void OutPut()
{
    qsort(arr,N,sizeof(STU),cmp2);
    FILE* new=fopen("out.txt","w");
    for(int i=0;i<N;i++)
    {
        fprintf(new,"%d %s %d\n",arr[i].id,arr[i].name,arr[i].seat);
    }
    fclose(new);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134