XX 学 院 计算机工程学院
课程设计报告
设计名称: 数结构课程设计
选题名称: 车牌号理系统
姓 名: 学 号:
专业班级: 软件工程
系 (院): 计算机工程学院
设计时间: 20111219~20111230
设计点: 软件工程实验室教室
成绩:
指导教师评语:
签名:
年 月 日
1.课程设计目
1训练学生灵活应学数结构知识独立完成问题分析结合数结构理知识编写程序求解指定问题
2初步掌握软件开发程问题分析系统设计程序编码测试等基方法技
3提高综合运学理知识方法独立分析解决问题力
4训练系统观点软件开发般规范进行软件开发巩固深化学生理知识提高编程水程中培养严谨科学态度良工作作风
2.课程设计务求:
务
根教材数结构C语言描述(耿国华编)参考书数结构题集(C语言版)(严蔚敏吴伟民编)选择课程设计题目求通设计数结构逻辑特性物理表示数结构选择应算法设计实现等方面加深课程基容理解综合运
设计题目务书列选题表中选取班题超2
学生选课题
学生原结合爱选课题求课题定深度难度定算法复杂性够巩固数结构课程学知识学生选课题需18周前报课程设计指导教师批准方生效
求:
1处理题目时求分析题目需求入手设计抽象数类型构思算法通设计实现抽象数类型编制机程序机调试等干步骤完成题目终写出完整分析报告前期准备工作完备否直接影响序机调试工作效率程序设计阶段应量利已标准函数加代码重率
2设计题目求达定工作量(300行代码)具定深度难度
3程序设计语言推荐CC++程序书写规范源程序需加必注释
4位学需提交独立运行程序
5 位学需独立提交设计报告书(份)求编排格式统规范容充实少10页(代码算)
6课程设计实践作培养学生动手力种手段单独考核
3.课程设计说明书
需求分析
1.功需求:
程序利基数排序思想批具结构特征汽车牌进行排序利二分查找思想排序汽车牌进行查找
2.性需求:
运行程序时输入组求数求操作进行排序查询时程序查找匹配数输出该关键字信息
3.数需求:
数包括3项分牌号码车型号车姓名中牌项输入形式01B7328前两位代表区字母代表车类型四位代表车号查询时求输入正确车牌号码
二 概设计
1.设计静态查找表抽象数类型
ADT RecordType{
char name[20] 车名字
char carname[20] 车名
KeyType key[7] 子关键字
} ADT RecordType
ADT SLinkList{
数元素:关键字RecordType类型数组存放车牌号
数间关系线性关系
}
2程序包含三模块
程序中容
Void main
{
1初始化加入数
2遍历表
3.排序
4.折半查找
5退出
}
系统中子程序功求
1Void Distribute(RecordType r[]int ipvector headpvector tail)
记录 数组r中已低位关键字key[i+1]…key[d]进行低位优先排序算法 第i关键字key[i]建立10队列队列中记录key[i]相Head[j]tail[j]分指队列中第记录(j012…9)head[j]0表示相应队列空队列
2Void collect(RecordType r[]pvctor headpvctor tail)
算法09扫描队列非空队列首尾相接重新链接成链表
3Void RadixSort(Record r[]int length)
Length 记录存放数组r中执行算法进行基数排序链表中记录关键字序链接
5 void arrange(SLinkList *l)
静态表进行整序
6int search_bin(SLList lchar key[])
二分查找
7 void GetData(SLinkList *L)
键盘获数
8 void SLListTraverse(SLinkList *L)
遍历静态表
9 int Equal(char key1[]char key2[])
判断相等
10 int Little(char key1[]char key2[])
判断较
模块间调关系
函数调(35)678
3调12
6调 910
三 详细设计
函数
void Distribute_n(RecordType r[]int ishuzi headshuzi tail) 数字分配
{
int jp
for(j0j<队列数j++) 初始化队列
{
队列头指针0全部0
列尾指针0全部0
}
p第数数组中位置
while(第数数组中位置0)
{
j第数第i位第队列
if(头指针0)
头指针第数载表中位置 else
该队列已数位置p 否该数静态链表中位置放队列数
尾指针p tial[j]该数静态链表中位置
p数位置值
}
}
void Collect_n(RecordType r[]shuzi headshuzi tail) 收集重新构成链表
{
int j0t
while(head[j]0)
++j 找第空队列
r[0]nexthead[j]ttail[j] head[j]第数位置
while(j<9)
{
++j
while((j<9)&&(head[j]0)) 找0队列
++j
if(head[j]0)
{
r[t]nexthead[j]
ttail[j]
}
}
r[t]next0 数next0
}
void radixsort(SLinkList *l) 基数排序
{
int nl>length 数组长度
zimu headtail
shuzi headstails
for(int i0i
l>r[n]next0 数next等0
for(i6i>2i)
{
Distribute_n(l>riheadstails) 调分配函数
Collect_n(l>rheadstails) 调收集函数
}
Distribute_c(l>r2headtail) 调分配函数
Collect_c(l>rheadtail) 调收集函数
for(i1i>0i)
{
Distribute_n(l>riheadstai 调分配函数
Collect_n(l>rheadstails) 调收集函数
}
}
void arrange(SLinkList *l) 整序
{
int pq
RecordType buf 建立中间变量
p第元素表中位置 p指第元素表中位置
for(int i1i<表长度i++)
{
while(p q第p元素数表中位置
if(pi)
{
buf第p元素址
第p元素址第i元素址 交换第i元素址第p元素址
第i元素址buf
第i元素数表中位置p
}
pq
}
}
void GetData(SLinkList *L) 获数
{
char key'0'
int j1
cout<<请输入车牌号码车名车名'#'结束<
for(int i0i<7i++)
{
cin>>key 输入数
第数车牌号码key
}
cout<<车名
cin>>第数车名
cout<<车名
cin>>第数车名
while(key'#')
{
j++
cout<
{
cin>>key 输入第j数车牌号码
if(key'#') {jbreak}
第j数车牌号码key
}
if(key'#') break
cout<<车名
cin>>L>r[j]carname
cout<<车名
cin>>L>r[j]name
}
L>lengthj
}
int binsearch(SLinkList *Lchar s[7]) 折半查找
{
int k0sum0ss0midhighlow1
highL>length
while(low
mid(high+low)2
if(Equal(sL>r[mid]key))return(mid) 调判断相等函数
else if(Little(sL>r[mid]key))highmid1 调较函数
else lowmid+1
}
return(0)
}
四 设计调试分析
1车牌号理
11 初始化输入数车牌号码车名车名键盘输入需数
车牌号:20W4521 车名bmw 车名 zzx
车牌号:11F4587 车名lanbogine 车名 zzp
车牌号:55F1254 车名benz 车名 xcl
初始化成功
12表中容输出
遍历成功
车牌号:20W4521 车名bmw 车名 zzx
车牌号:11F4587 车名lanbogine 车名 zzp
车牌号:55F1254 车名benz 车名 xcl
输入结果致
13车牌号进行排序基数排序方法
11F4587 lanbogine zzp
20W4521 bmw zzx
55F1254 benz xcl
预期结果致
14折半查找需车牌号码输出车牌号码车车名
预期结果致查找成功
15退出
五 户手册
1运行程序首先出现界面选项初始化表加入数选项二遍历表选项三车牌号排序选项四查找选项五退出运行查找前定进行排序折半查找先进行排序
2输入数输入车牌号码例01B3456车姓名车名字
3遍历序输出数
4基数排序方法进行排序
5查找输入查找车牌号码查找成功返回需车牌号车名车名没信息返回没车牌号
六 测试成果
七 附录(源程序清单)
#define KEY_SIZE 7
#define LIST_SIZE 10
#include
using namespace std
typedef struct{
char key[KEY_SIZE]
char name[10]
char carname[20]
int next
}RecordType
typedef struct{
RecordType r[LIST_SIZE]
int length
int keynum
}SLinkList
typedef int shuzi[10]
typedef int zimu[26]
void InitSLList(SLinkList *L) 链表初始化
{
L>length0
L>keynum7
}
void Distribute_n(RecordType r[]int ishuzi headshuzi tail) 数字分配
{
int jp
for(j0j<9j++)
{
head[j]0
tail[j]0
}
pr[0]next
while(p0)
{
jint(r[p]key[i]'0')
if(head[j]0)
head[j]p
else
r[tail[j]]nextp
tail[j]p
pr[p]next
}
}
void Distribute_c(RecordType r[]int izimu headzimu tail) 字母分配
{
int pj
for(j0j<25j++)
{
head[j]0
tail[j]0
}
pr[0]next
while(p0)
{
jint(int(r[p]key[i])'A')
if(head[j]0)head[j]p
else r[tail[j]]nextp
tail[j]p
pr[p]next
}
}
void Collect_n(RecordType r[]shuzi headshuzi tail) 收集重新构成链表
{
int j0t
while(head[j]0)
++j
r[0]nexthead[j]ttail[j]
while(j<9)
{
++j
while((j<9)&&(head[j]0))
++j
if(head[j]0)
{
r[t]nexthead[j]
ttail[j]
}
}
r[t]next0
}
void Collect_c(RecordType r[]zimu headzimu tail) 字母类型收集重新构成链表
{
int j0t
while(head[j]0)
++j
r[0]nexthead[j]ttail[j]
while(j<25)
{
++j
while((j<25)&&(head[j]0))
++j
if(head[j]0)
{
r[t]nexthead[j]
ttail[j]
}
}
r[t]next0
}
void radixsort(SLinkList *l) 基数排序
{
int nl>length
zimu headtail
shuzi headstails
for(int i0i
l>r[n]next0
for(i6i>2i)
{
Distribute_n(l>riheadstails) 调分配函数
Collect_n(l>rheadstails) 调收集函数
}
Distribute_c(l>r2headtail) 调分配函数
Collect_c(l>rheadtail) 调收集函数
for(i1i>0i)
{
Distribute_n(l>riheadstails) 调分配函数
Collect_n(l>rheadstails) 调收集函数
}
}
void arrange(SLinkList *l) 整序
{
int pq
RecordType buf
pl>r[0]next p指第记录前位置
for(int i1i
{
while(pr[p]next 找第i记录p指示表中前位置
ql>r[p]next
if(pi)
{
bufl>r[p]
l>r[p]l>r[i]
l>r[i]buf 交换pi
l>r[i]nextp 移走记录while循环找回
}
pq
}
}
void GetData(SLinkList *L) 获数
{
char key'0'
int j1
cout<<请输入车牌号码车名车名'#'结束<
for(int i0i<7i++)
{
cin>>key
L>r[1]key[i]key
}
cout<<车名
cin>>L>r[1]carname
cout<<车名
cin>>L>r[1]name
while(key'#')
{
j++
cout<
{
cin>>key
if(key'#') {jbreak}
L>r[j]key[i]key
}
if(key'#') break
cout<<车名
cin>>L>r[j]carname
cout<<车名
cin>>L>r[j]name
}
L>lengthj
}
void SLListTraverse(SLinkList *L) 遍历静态表
{
int ij
cout<
for(i1i
{
for(j0j<7j++)
cout<
cout<< <
cout<
}
int Equal(char key1[]char key2[]) 判断相等
{
for(int i0i<7i++)
{if(key1[i]key2[i]) return 0}
return 1
}
int Little(char key1[]char key2[]) 判断较
{
for(int i0i<7i++)
{
if(key1[i]
}
return 0
}
int binsearch(SLinkList *Lchar s[7]) 折半查找
{
int k0sum0ss0midhighlow1
highL>length
while(low
mid(high+low)2
if(Equal(sL>r[mid]key))return(mid)
else if(Little(sL>r[mid]key))highmid1
else lowmid+1
}
return(0)
}
void main()
{
int i
SLinkList l
do
{
cout<<请选择 1初始化表加入数 2遍历表 3车牌号排序 4折半查找(必须先排序) 5退出 <
switch(i)
{
case 1InitSLList(&l)
GetData(&l)
break
case 2SLListTraverse(&l)break
case 3radixsort(&l)
arrange(&l)
SLListTraverse(&l)
break
case 4
int find
char s[7]
cout<<请输入查找车牌号码<
findbinsearch(&ls)
if(find)
{
cout<<表中位置<
cout<
for(int i0i<7i++)
cout<
cout<
else cout<<没车牌号<
case 5break
}
}while(i5)
}
4课程设计心
次课程设计选择车牌号理系统功少两功排序查找排序基数排序方法种关键字排序
查找二分查找然程序容少似简单基数排序难排序理解久弄懂排序非常典排序思想时候感觉排序实绝排序方法排序方法较移动关键字较关键字中子关键字位关键字开始较果数字根关键字中组子关键字分放入十队列中果字母类似放入二十六队列中收集函数队列首尾相连重新构成链表反复调函数会形成序静态链表时静态链表逻辑结构中序储存结构中序进行次整序链表真正序调试程中参考书中代码图书馆中相关书籍程序进行进步调整完成代码调试
折半查找中调较判断相等函数根书折半查找算法进行改进成功
次课程设计中重点掌握基数排序折半查找进行定改进遍历便写行通次课程设计排序方法种认识种理解程序握更加准确增加编程力数结构门课程更深认识更加努力学相关知识弥补方面足缩差距
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容,不代表《香当网》观点或立场,请自行判断内容的真实性和可靠性!
该内容是文档的文本内容,更好的格式请下载文档