折半查找法查找关键字
河北联合大学
2011-2012第2学期
《软件设计基础-C++》
课程设计
设计名称: 折半查找法查找关键字
姓 名: 学 号:
专业班级: 学 院: 设计时间:
设计地点:
指导教师评语:
成绩:
指导教师签字:
年 月 日
目 录
1.课程设计目的 ...................................................................................................... 3
2.课程设计任务与要求 .......................................................................................... 4
3.课程设计说明书 .................................................................................................. 5
4.课程设计成果 ...................................................................................................... 9
5.程序调试过程 .................................................................................................... 13
6.设计问题的不足和改进
............................................................................. 16
7.课程设计心得 .................................................................................................... 17
8.参考文献 ............................................................................................................ 18
1(课程设计目的
《软件设计基础-C++》课程设计是这门课程的实践性教学环节之一,本次设计结合实际应用的
要求,使课程设计既覆盖C++的知识点,又接近工程实际需要。目的是通过课程设计的综合训练,培
养学生实际分析问题、解决问题的能力,以及编程和动手能力,最终目标是通过课程设计这种形式,
帮助学生系统掌握C++这门课程的主要内容,养成良好的编程习惯,更好的完成教学任务。
通过产品管理系统的设计,培养学生综合利用C++语言进行程序设计的能力,加强函数的运用及
学生对软件工程方法的初步认识,提高软件系统分析能力和程序文档建立、归纳总结的能力,培养学
生利用系统提供的
函数及典型算法进行设计。
2(课程设计任务与要求:
要求:
本次课程设计利用《软件设计基础-C++》课程中所学到的编程知识和编程技巧,完成具有一定难度和工作量的程序设计题目,帮助学生掌握编程、调试的基本技能,独立完成所布置的任务。 要求:
1、对系统进行功能需求分析
2、设计合理的数据结构和系统框架
3、编程简练,程序功能齐全,能正确运行
4、说明书、流程图要清楚
5、课题完成后必须按要求提交课程设计报告
任务:
设计一个简单的产品管理系统:
某工厂有5种产品,每种产品包括:产品代码,产品名称,产品数量,销售量,要求编写函数实现下列功能:
(1)从键盘输入这些产品的信息;
(2)按照产品的库存量进行升序排序,使用选择法排序,在主函数中输出;
(3)使用折半查找法进行循环查询,当用户给出某种产品的代码时,在主函数中显示该产品的
信息,如果没找到则给出未找到的信息,退出程序的运行;
(4)输出产品信息。
1( 基本要求:
(1)要求用C++的思想来完成程序的设计;
(2)要求使用结构数组和结构指针,各个功能分别使用函数来完成,主函数和各个函数分别存放在不同的.cpp文件中,要求使用头文件;
(3)要求使用选择法排序,折半查找法进行查找。
2( 创新要求
在基本要求达到后,进行创新设计,如能够实现产品的删除或插入操作,动态更新产品数据库。
3(课程设计说明书
?概要设计
模块说明:
?详细设计
总体流程图:
nin int main()
desktop()
n=1 N Y
intput()
n=2 N
Y
soft()
n=3
N
Y
n=4 search() N
Y
reput()
n!=0 Y
N
Return0
各功能模块
4(课程设计成果
折半查找
顺顺顺
序序序
函查
数 找
#include
#include
#include
using namespace std;
#define NULL 0
typedef struct{
string key; //关键字域设置为string }ElemType;
typedef struct {
ElemType *elem; // 数据元素存储空间基址,建表时按实际长度分配,0号单元留空
int length; // 表结点的索引值 }SSTable;
//******************************
//按用户输入的顺序建立顺序表
//******************************
SSTable Creat_Seq(int n)
{
SSTable ST;
ST.elem=new ElemType[n+1];
cout<<"请输入顺序表每一个元素的值:\n";
for(int i=1;i<=n;i++)
{
cin>>ST.elem [i].key;
}
ST.length=n;
return ST;
}
//********************************************* //备份原始的顺序表,以供各种排序算法使用 //********************************************* SSTable Copy_Seq(SSTable T)
{
SSTable copy;
copy.elem=new ElemType[T.length+1];
copy.length=T.length;
for(int i=1;i<=T.length;i++)
copy.elem[i]=T.elem[i];
return copy;
}
//********************************************** //打印顺序表函数
//********************************************** void printSeq(SSTable ST)
{
for(int i=1;i<=ST.length;i++)
cout<1)
{
lastExchange=1;
for(int j=1;jST.elem[j+1].key)
{
temp=ST.elem[j];
ST.elem[j]=ST.elem [j+1];
ST.elem [j+1]=temp;
lastExchange=j; //记下进行交换的位置
}
}
i=lastExchange; // 本趟进行过交换的 // 最后一个记录的位置
printSeq(ST) ;
}
cout<<"---------------------------------------"<ST.elem [j].key)
k=j;
if(k!=i) //把最小值与当前值交换
{
temp=ST.elem [i] ;
ST.elem [i]=ST.elem [k];
ST.elem [k]=temp;
printSeq(ST) ;
}
}
cout<<"---------------------------------------"<=high+1; --j )
ST.elem [j+1] = ST.elem [j]; // 记录后移
ST.elem [high+1] = ST.elem [0]; // 插入
printSeq(ST) ;
}
cout<<"---------------------------------------"<>len;
ST=Creat_Seq(len); //创建顺序表
cout<<"请输入要查找的关键字:\n";
cin>>key;
Search_Seq(ST,key); //顺序查找关键字
cop1=Copy_Seq(ST);
cout<<"冒泡排序法:"<