北京工商大学课程设计实践报告学院：计算机与信息工程学院课程名称：算法与数据结构任课教师：叶红班级：工科092学号：姓名：同组学生：无实践地点：北京工商大学良乡校区工二楼406实践时间：2011年1月3日至2011年1月7日1、课程设计题目内容: 对一批汽车牌照进行排序和查找排序和查找是在数据信息处理中使用频度极高的操作。
为加快查找的速度需先对数据记录按关键字排序,在汽车数据的信息模型中,汽车牌照是关键字,而且是具有结构特点的一类关键字。
因为汽车牌照号是数字和字母混编的,例如01B7328, 这种记录集合是一个适于利用多关键字进行排序的典型例子,故我们可以利用链式基数排序方法实现排序。
在排序基础上,利用二分查找的思想,实现对这批汽车记录按关键字的查找。
2、设计要求基本要求: 利用链式基数排序和二分查找的思想完成程序设计任务。
3、设计内容(1) 需求分析程序的功能:主要功能是对含有关键字的批量数据进行排序和查找；另外根据实际增添了输出到文件、删除、插入、简单统计功能。
输入输出的要求:程序会显示提示，根据提示输入数字、字符或数据。
测试数据:测试数据的每个记录包括五项,分别为牌照号码、汽车商标、颜色、注册日期和车主的姓名,其中牌照号码为七位(k0-k6),输入形式如下:K 0和 k1输入值为01-04(代表地区),k2输入值为 A~Z(代表车的使用类型),后4位为 0000~9999(代表车号),例如: O1B7328。
其余四项输入内容因为不涉及本程序的核心思想,故只要求一般字符串类型即可。
查询时,输入合法的汽车牌照号码。
测试数据要求用30个左右的数据项进行测试,头两位暂限定 01~04,第3位为 A~Z,以便可使牌照号码相对集中。
程序测试数据：3001S5842 将明 2007-12-02 blue jid04D2154 陈琳 2005-11-01 yellow jo02A0021 潘晓静 2011-04-22 white jae01S8930 李峰 2010-08-13 green aie03C3589 张三 2007-02-18 blue nhi04E2184 Lucy 2009-11-28 black as604A2505 赵晗 2009-10-30 brown ja03C3269 Lily 2007-11-30 pink jos03B3568 Tom 2005-12-17 blue jos01A8983 Jim 2006-02-19 white kfe02A7777 韩梦龙 2005-02-07 black vds02C2222 钱国正 2009-08-05 green yer01G8652 刘晓莉 2008-11-07 white kfe03H0029 Kasserine 2008-04-08 black xfd04G9665 索海丰 2009-04-09 red trs03B3222 唐如云 2007-10-08 brown htr02L6622 王睫 2007-11-08 blue nrr04L1122 Shelly 2006-11-03 black gf04A2200 David 2009-02-22 red ert01E8000 赵远 2007-03-08 pink tre02V0009 唐文 2006-07-02 blue thh01B3321 郑华 2008-12-02 white jh03S6699 索耀光 2008-01-01 white rd03D4115 赵沙 2007-11-11 yellow kew01F6339 赵欢欢 2007-07-14 red kfe02H7775 叶丽娜 2009-08-15 brown wg02A8993 孙珍珍 2010-11-27 white wb02P8692 赵楠 2006-10-12 black trt04W5524 孙中华 2004-03-21 yellow ms03W6688 John 2007-01-11 pink esg(2) 概要设计本程序所用的抽象数据类型的定义：ArrType // 指针数组类型SLList // 静态链表类型SLCell // 静态链表的结点类型KeysType // 定义关键字类型为字符型InfoType // 定义其它数据项的类型主程序的流程及各程序模块之间的层次关系:开始先选择读入原始数据方式：1: 从文件读入(在桌面建立test.txt文档，第一行为记录数，记录数<=10000，记录数必须符实，否则程序出错；第二行开始数据，数据用空格隔开，例如： 01S5842 将明 2007-12-02 blue jid)；2: 直接用程序内数据。
然后对数据进行操作：1: 按车牌号排序并输出;是否输出到文件？(y/n)2: 查找;1）: 按车牌号查找(排序后进行);0: 退出 1：删除2）: 按车牌号前两位查找;3）: 按车牌号第三位查找。
3: 按顺序插入数据;(排序后)4: 简单统计。
1）: 按车牌号前两位统计;2）: 按车牌号第三位统计。
(3) 详细设计采用C语言定义相关的数据类型：typedef struct InfoType // 车主姓名等其它信息{char name[17];char date[12];char color[11];char mark[10];}InfoType; // 定义其它数据项的类型typedef char KeysType; // 定义关键字类型为字符型typedef struct SLCell // 静态链表的结点类型{KeysType keys[MAX_NUM_OF_KEY+1]; // 关键字（字符串末尾+'\0'）InfoType oth; // 其它数据项int next;}SLCell;typedef struct SLList // 静态链表类型{SLCell r[MAX_SPACE]; /* 静态链表的可利用空间，r[0]为头结点*/int keynum; // 记录的当前关键字个数int recnum; // 静态链表的当前长度}SLList;typedef int ArrType[RADIX]; // 指针数组类型各模块的算法：①基数排序：void Distribute(SLCell r[],int i,ArrType f,ArrType e);/*静态键表L的r域中记录已按(keys[0]，…，keys[i-1])有序。
本算法按第i 个关键字keys[i]建立RADIX个子表，使同一子表中记录的keys[i]相同。
f[0..RADIX-1]和e[0..RADIX-1]分别指向各子表中第一个和最后一个记录*/ void Collect(SLCell r[],ArrType f,ArrType e);/*本算法按keys[i]自小至大地将f[0..RADIX-1]所指各子表依次链接成一个链表，e[0..RADIX-1]为各子表的尾指针。
*/void Sort(SLList L,int adr[]);/*求得adr[1..L.length]，adr[i]为静态链表L的第i个最小记录的序号*/ void Rearrange(SLList &L,int adr[]);/*adr给出静态链表L的有序次序，即L.r[adr[i]]是第i小的记录。
本算法按adr重排L.r，使其有序。
*/void RadixSort(SLList &L);/*L是采用静态链表表示的顺序表。
对L作基数排序，使得L成为按关键字自小到大的有序静态链表，L.r[0]为头结点。
*/void write(SLList l); // 输出到文件②查找：int judge(char s[]); // 判断车牌号是否合法int Search1(SLList ST); /* 在表ST中折半查找其关键字等于key的数据元素。
若找到，则打印该元素在表中的信息*/void Delete(SLList *l,int d); // 删除l中第d个记录void Search2(SLList l); // 据车牌号前两位搜索void Search3(SLList l); // 据车牌号第三位搜索③插入：int Read(SLList l,SLCell *r); /* 读取车牌号到r，若l中有此车牌号则读取失败*/void Insert(SLList *l); /* 在l中按基数排序顺序插入车牌号及其他信息*/④统计：void Statistic1(SLList l); // 据车牌号前两位进行统计void Statistic2(SLList l); // 据车牌号第三位进行统计函数的调用关系图：(4) 调试分析调试中遇到的问题及对问题的解决方法：我在调试中遇到了许多问题,由于问题太多无法一一说明,这里只说一些编译无错误而程序无法正常运行,或者程序的执行结果与预想的不同,其它的大部分错误软件在编译时会有提示,就不说了。
1、出现如图1情况的，我碰到的有几种。
图11）scanf或fscanf语句中一定要用变量的地址，而不是变量本身。
这种错误在学习C语言时就强调过，但编程时还是得小心，我的程序在编了300多行时出现这个错误，费了好些时间才查找出来；2）数组或其它变量定义空间不足。
例如在基数排序中，需要两个指针数组，大小与基数相同，如果小于基数的话，会出现图1所示的情况。
2、程序执行结果与预想结果不同，如图2和图3所示图2这里有一个经常不经意犯的小错误，就是经常把“==”写成“=”，上图中while(a==0)；以下还有一例：图4和图5中，if (c==’y’)。
图3图4图53、有三个问题我不知如何解决：①图4和图5中，运行结果是打印完“是否输出到文件？（y/n）”后直接回车打印“输入错误”，之间并没有让输入字符进行选择；②图5中程序中使用的是scanf函数而不是getch（）函数，因为编译时会提示没有getch（）此函数，应该如何做才能把它找出来？③如图6、图7和图8所示，当进行选择时，若输入字母，则会进入死循环，而输入其它数字时则不会，我试了一下，当输入如！@#等特殊字符时也会进入死循环，我暂时没能解决掉这个问题。
图6图7图8 暂时就这些问题了。
(5) 使用说明及测试结果程序开始后，先选择读入原始数据方式；选择后，程序会先将数据按原来顺序打印出来；然后程序显示主菜单，对数据进行操作；1：按车牌号排序并输出；程序会先对原始数据以车牌号为关键字进行基数排序并输出；输出后程序会提示是否输出到文件，进行选择；若选择“y”，程序会将排好序的数据记录在桌面建立txt文档保存；若选择“n”，程序会继续回到主菜单。