*******大学
《数据结构与算法分析》课程设计
题目：数据结构上机试题
学生姓名：
学号：
专业：信息管理与信息系统
班级：
指导教师：
2014年04月
目录
一、顺序表的操作 (2)
【插入操作原理】 (2)
【删除操作原理】 (2)
【NO.1代码】 (3)
【运行截图演示】 (7)
二、单链表的操作 (10)
【创建操作原理】 (10)
【插入操作原理】 (10)
【删除操作原理】 (10)
【NO.2代码】 (11)
【运行截图演示】 (20)
三、顺序栈的操作 (25)
【数值转换原理】 (25)
【NO.3代码】 (26)
【运行截图演示】 (30)
四、查找算法 (32)
【顺序查找原理】 (32)
【折半查找原理】 (32)
【NO.4代码】 (33)
【运行截图演示】 (38)
五、排序算法 (40)
【直接插入排序原理】 (40)
【快速排序原理】 (40)
【NO.5代码】 (41)
【运行截图演示】 (46)
一、顺序表的操作
（1）插入元素操作：将新元素x 插入到顺序表a 中第i 个位置； （2）删除元素操作：删除顺序表a 中第i 个元素。
【插入操作原理】
线性表的插入操作是指在线性表的第i-1个数据元素和第i 个数据元素之间插入一个新的数据元素，就是要是长度为n 的线性表：
()11,,,,,i i n a a a a -…………
变成长度为n+1的线性表：
()11,,,,,,i i n a a b a a -…………
数据元素1i a -和i a 之间的逻辑关系发生了变化。
（其【插入原理】在课本P23的算法2.3有解释）
【删除操作原理】
反之，线性表的删除操作是使长度为n 的线性表：
()111,,,,,,i i i n a a a a a -+…………
变成长度为n-1的线性表：
()111,,,,,i i n a a a a -+…………
数据元素1i a -、i a 和1i a +之间的逻辑关系发生变化，为了在存储结构上放映这个变化，同样需要移动元素。
（其【删除原理】在课本P24的算法2.4有解释）
【NO.1代码】
#include
#define MAX 100
typedef int datatype;
typedef struct
{
datatype data[MAX];
int list;
}
sequenlist; /*顺序表*/
int main()
{
int insert( sequenlist *L, int x, int i );
int deletee( sequenlist *L, int i );
int input( sequenlist *L );
int output( sequenlist *L );
sequenlist s,*p=&s;
int indata,inlocate,deletedx;
input(p);
printf( "请输入要插入的数：" ); scanf( "%d",&indata );
printf( "请输入要插入的位置：" );
scanf( "%d",&inlocate );
insert( p,indata,inlocate );
printf( "插入后的数据：" );
output(p);
printf( "请输入要删除的位置：" );
scanf( "%d",&deletedx );
deletee( p, deletedx );
printf( "删除后的数据：" );
output(p);
return 0;
}
int output( sequenlist *L )
{
int i;
for( i=0; i<=L->list; i++ )
printf( "%d ",L->data[i] );
printf( "\n\n" );
return(1);
}
int input( sequenlist *L ) {
int i;
printf( "请输入原始数据个数：" );
scanf( "%d",&( L->list ) );
L->list--;
printf( "请输入原始数据：" );
for( i=0; i <= L->list; i++ )
scanf( "%d",&( L->data[i] ) );
printf( "原始数据为：" );
output(L);
return (1);
}
int insert( sequenlist *L, int x, int i )
{
int j;
if ( ( (*L).list )>=MAX-1 )
{
printf( "overflow" ); return 0;
}
else
{
if ( (i<1) || (i> ( (*L).list )+1 ) ) {
printf( "error\n" );
return 0;}
else
{
for ( j=L->list;j>=i-1;j-- )
L->data[j+1]=L->data[j];L->data[i-1]=x;
L->list++;
}
}
return(1);
}
int deletee( sequenlist *L,int i ) /*定义删除函数*/ {
int j;
if ( (i<1) || ( i>(L->list)+1 ) )
{
printf( "error\n" );
return 0;
}
else
{
for ( j=i;j<=L->list;j++ )
L->data[j-1]=L->data[j];
L->list--;
}
return(1);
}
【运行截图演示】
①、如下面的运行截图所示，当输入的线性表长度设置为12的时候，该线性表最多能输入12位数的长度。
输入要插入的数和插入数的位置下标，便可以进行插入操作；同理当输入要执行删除操作数的位置下标，可以将该数删除出线性表。
②、如下面的运行截图所示，当初始设置的线性表长度为5的时候，其5个数分别是-3、4、5、0、1。
若是要执行程序中输入的插入数字“2”，其插入数的位置在“-4”
的时候，程序是不能执行插入操作的。此时的线性表能插入的下标范围为“1——5”，明显“-4”数值<下限“1”数值，所以程序执行“error”。
③、如下面的运行截图所示，同理该线性表要插入数的位置“6”数值>上限“5”数值，所以程序执行“error”。
④、如下面的运行截图所示，初始设置的线性表插入数字2之后，要删除位置7已超过线性表的最大长度n=6，所以程序执行“error”。
⑤、如下面的运行截图所示，同理该线性表要删除数的位置“0”下标不存在，所以程序执行“error”。
二、单链表的操作
（1）创建一个带头结点的单链表；
（2）插入元素操作：将新元素x 插入到单链表中第i 个元素之后； （3）删除元素操作：删除单链表中值为x 的元素。
【创建操作原理】
在单链表的第一个结点之前附设一个结点，称之为头结点。头结点的数据域可以不存储任何信息，也可以存储线性表的长度等的附加信息，头结点的指针域存储指向第一个结点的指针（即第一个元素结点的存储位置）。
【插入操作原理】
为插入数据元素x ，首先要生成一个数据域为x 的结点，然后插入在单链表中。根据插入操作的逻辑定义，还需要修改结点a 中的指针域，令其指向结点x ，而结点x 中的指针域应指向结点b ，从而实现3个元素a 、b 和x 之间逻辑关系的变化。
假设s 为指向结点x 的指针，则上述指针修改用语描述即为：
s ;next p next ->=-> s p n e x t ->=
【删除操作原理】
反之，在线性表中删除元素b 时，为在单链表中实现元素a 、b 和c 之间逻辑关系的变化，仅需要修改结点a 中的指针域即可。
假设p 为指向结点a 的指针，则上述指针修改用语描述即为：
;p next p next next ->=->->
【NO.2代码】
#include
#include
typedef struct node //定义链表
{
int data;
struct node *next;
}
snode;
snode* creat() //创建链表的函数
{
snode *head, *p, *q;
head = (snode *)malloc(sizeof(snode));
p = head;
int x;
printf("请输入创建链表的值，用“0”结束输入。\n"); printf("x = ");
scanf("%d", &x);
while (x != 0)
{
q = (snode *)malloc(sizeof(snode));
q->data = x;
p->next = q;
p = q;
printf("x = ");
scanf("%d", &x);
}
p->next = NULL;
return head;
}
int length(snode *head)//测链表的结点数{
int i = 0;
snode *p = head->next;
while (p != NULL)
{
p = p->next;
i++;
}
return i;
}
void display(snode *head)
{
snode *p = head->next;
for(int i = 0; i < length(head); i++)
{
printf("%4d", p->data);
p = p->next;
}
printf(" ");
}
int locate(snode *head, int x)
{
snode *p = head->next;
int i = 1;
while (p != NULL && x != p->data)
{
p = p->next;
i++;
}
if (p == NULL)
return 0;
else
return i;
}
int insnode(snode *head, int x, int i) //把x插入到链表的第
i的位置
{
int j;
snode *p = head->next, *s;
if(i < 1 || i > (length(head) + 1))
return 0;
else if (i == 1)
{
s = (snode *)malloc(sizeof(snode));
s->next = p;
head->next = s;
s->data = x;
}
else
{
for (j = 1; j < i - 1; j++)
p = p->next;
s = (snode *)malloc(sizeof(snode));
s->next = p->next;
p->next = s;
s->data = x;
}
return 1;
}
int delnode(snode *head, int i)//删除链表中第i个结点{
snode *p = head->next, *q = head;
if(i < 1 || i > length(head))
return 0;
else if (i == 1)
{
head->next = p->next;
free(p);
}
else
{
for (int j = 1; j < i; j++)
{
p = p->next; q = q->next;
}
q->next = p->next;
free(p);
}
return 1;
}
void sort(snode *head) //把链表中每个结点的值按从小到大排列{
snode *p, *q;
int k;
for(p = head->next; p != NULL; p = p->next)
for(q = p->next; q != NULL; q = q->next)
if (p->data > q->data)
{
k = p->data;
p->data = q->data;
q->data = k;
}
}
void insert(snode *head, int x) //在有序链表中插入x,插入后仍保持有序
{
snode *p = head->next, *s, *q = head;
while (p != NULL && p->data < x)
{
q = q->next;
p = p->next;
}
s = (snode *)malloc(sizeof(snode));
s->next = q->next;
s->data = x;
q->next = s;
}
void del_min_max(snode *head, int min, int max) //删除有序链表中值min到值max中的结点
{
snode *p = head->next, *q = head;
while (p != NULL && p->data <= min)
{
q = p;
p = p->next;
}
while (p != NULL && p->data < max)
{
q->next = p->next;
free(p);
p = q->next;
}
}
void del_min(snode *head)
{
snode *p = head->next, *q = head;
snode *p_min, *q_min;
p_min = p;
q_min = q;
while (p != NULL)
{
q = p; p = p->next;
if (p != NULL && p->data < p_min->data) {
q_min = p_min;
p_min = p;
}
}
q_min->next = p_min->next;
free(p_min);
}
int main()
{
int min, max;
snode *headl = creat(); //创建链表
printf("最初的链表如下：");
display(headl);
printf("\n\n");
int num, location;
printf("请输入您要查找的数：");
scanf("%d", &num);
if (locate(headl, num))
printf("数字%d在链表中的位置为：%d\n\n", num, locate(headl, num));
else
printf("数字%d在链表中不存在!\n\n", num);
printf("请分别输入您要插入到链表中的数以及想插入的位置（用空格号间隔开）：");
scanf("%d %d", &num, &location);
if (insnode(headl, num, location))
{
printf("插入新值以后的链表如下：");
display(headl);
printf("\n\n");
}
else printf("输入有误!\n\n");
printf("请输入您想删除的结点位置：");
一、问题描述 1、排序问题描述 排序是计算机程序设计的一种重要操作，他的功能是将一组任意顺序数据元素（记录），根据某一个（或几个）关键字按一定的顺序重新排列成为有序的序列。简单地说，就是将一组“无序”的记录序列调整为“有序”的记录序列的一种操作。 本次课程设计主要涉及几种常用的排序方法，分析了排序的实质，排序的应用，排序的分类，同时进行各排序方法的效率比较，包括比较次数和交换次数。我们利用java语言来实现本排序综合系统，该系统包含了：插入排序、交换排序、选择排序、归并排序。其中包括： （1）插入排序的有关算法：不带监视哨的直接插入排序的实现； （2）交换排序有关算法：冒泡排序、快速排序的实现； （3）选择排序的有关算法：直接选择排序、堆排序的实现； （4）归并排序的有关算法：2-路归并排序的实现。 2、界面设计模块问题描述 设计一个菜单式界面，让用户可以选择要解决的问题，同时可以退出程序。界面要求简洁明了，大方得体，便于用户的使用，同时，对于用户的错误选择可以进行有效的处理。 二、问题分析 本人设计的是交换排序，它的基本思想是两两比较带排序记录的关键字，若两个记录的次序相反则交换这两个记录，直到没有反序的记录为止。应用交换排序基本思想的主要排序方法有冒泡排序和快速排序。 冒泡排序的基本思想是：将待排序的数组看作从上到下排列，把关键字值较小的记录看作“较轻的”，关键字值较大的纪录看作“较重的”，较小关键字值的记录好像水中的气泡一样，向上浮；较大关键字值的纪录如水中的石块向下沉，当所有的气泡都浮到了相应的位置，并且所有的石块都沉到了水中，排序就结束了。 冒泡排序的步骤： 1)置初值i=1； 2)在无序序列｛r[0],r[1],…，r[n-i]｝中，从头至尾依次比较相邻的两个记录r[j] 与r[j+1]（0<=j<=n-i-1）,若r[j].key>r[j+1].key，则交换位置； 3)i=i+1； 4)重复步骤2）和3），直到步骤2）中未发生记录交换或i=n-1为止； 要实现上述步骤，需要引入一个布尔变量flag，用来标记相邻记录是否发生交换。 快速排序的基本思想是：通过一趟排序将要排序的记录分割成独立的两个部分，其中一部分的所有记录的关键字值都比另外一部分的所有记录关键字值小，然后再按此方法对这两部分记录分别进行快速排序，整个排序过程可以递归进行，以此达到整个记录序列变成有序。 快速排序步骤： 1)设置两个变量i、j，初值分别为low和high，分别表示待排序序列的起始下
数据结构课程设计 课程名称：内部排序算法比较 年级/院系：11级计算机科学与技术学院 姓名/学号： 指导老师： 第一章问题描述 排序是数据结构中重要的一个部分，也是在实际开发中易遇到的问题，所以研究各种排算法的时间消耗对于在实际应用当中很有必要通过分析实际结合算法的特性进行选择和使用哪种算法可以使实际问题得到更好更充分的解决！该系统通过对各种内部排序算法如直接插入排序，冒泡排序，简单选择排序，快速排序，希尔排序，堆排序、二路归并排序等，以关键码的比较次数和移动次数分析其特点，并进行比较，估算每种算法的时间消耗，从而比较各种算法的优劣和使用情况！排序表的数据是多种不同的情况，如随机产生数据、极端的数据如已是正序或逆序数据。比较的结果用一个直方图表示。
第二章系统分析 界面的设计如图所示： |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------| |******************************| 请选择操作方式： 如上图所示该系统的功能有： （1）：选择1 时系统由客户输入要进行测试的元素个数由电脑随机选取数字进行各种排序结果得到准确的比较和移动次数并 打印出结果。 （2）选择2 时系统由客户自己输入要进行测试的元素进行各种排序结果得到准确的比较和移动次数并打印出结果。 （3）选择0 打印“谢谢使用！！”退出系统的使用！！ 第三章系统设计 （I）友好的人机界面设计：（如图3.1所示） |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------|
一: 需求分析 (2) 三: 详细设计（含代码分析） (4) 1.程序描述: (4) 2具体步骤 (4) 四调试分析和测试结果 (7) 五，总结 (9) 六.参考文献; (10) 七.致谢 (10) 八.附录 (11)
一: 需求分析 问题描述：设计哈希表实现电话号码查询系统。 基本要求 1、设每个记录有下列数据项：电话号码、用户名、地址 2、从键盘输入各记录，分别以电话号码和用户名为关键字建立哈希表； 3、采用再哈希法解决冲突； 4、查找并显示给定电话号码的记录； 5、查找并显示给定用户名的记录。 6、在哈希函数确定的前提下，尝试各种不同类型处理冲突的方法（至少 两种），考察平均查找长度的变化。 二: 概要设计 进入主函数,用户输入1或者2,进入分支选择结构:选1:以链式方法建立哈希表,选2:以再哈希的方法建立哈希表,然后用户输入用户信息,分别以上述确定的方法分别以用户名为检索以及以以电话号码为检索将用户信息添加到哈希表,.当添加一定量的用户信息后,用户接着输入用户名或者电话号码分别以用户名或者电话号码的方式从以用户名或电话号码为检索的哈希表查找用户信息.程序用链表的方式存储信息以及构造哈希表。 具体流程图如下所示:
三: 详细设计（含代码分析） 1.程序描述: 本程序以要求使用哈希表为工具快速快速查询学生信息，学生信息包括电话号码、用户名、地址；用结构体存储 struct node { string phone; //电话号码 string name; //姓名 string address;//地址 node *next; //链接下一个地址的指针 }; 2具体步骤 1. 要求主要用在哈希法解决冲突，并且至少尝试用两种方法解决冲突，定义两个指针数组存储信息node *infor_phone[MAX]; node *infor_name[MAX];前者以电话号码为关键字检索哈希表中的信息，后者以姓名为关键字检索哈希表中的信息 用链式法和再哈希法解决冲突： int hash(string key) //以姓名或者电话号码的前四位运算结果作为哈{ //希码 int result=1,cur=0,i; if(key.size()<=4) i=key.size()-1; else i=4; for(;i>=0;i--) { cur=key[i]-'0'; result=result*9+cur; } result%=(MOD); return result;
可用C++(Visual C++ 6.0),JA V A（JSP，STRUTS），C#(https://www.doczj.com/doc/1f10061652.html, ，Visual Studio 2005)，试题目而定。 1、综合购物频道（限最多3人选） 项目描述：是一个在线销售系统，是一个B-C模式的电子商务系统，由前台的B/S模式购物系统和后台的C/S模式的管理系统两部分组成。该电子商务系统可以实现会员注册、浏览商品、查看商品详细信息、选购商品、取消订单和查看订单等功能，前台系统的详细功能。目的：了解项目开发的一个基本流程以及如何运用现行的框架搭建一个大型的综合型系统2、某大型企业内部OA（限最多3人选） 项目描述：采用网络办公自动化系统，不仅能快速提高企业的运作效率，节省大量的办公费用，能全面提升企业的核心竞争力和生产力以及提高工作效率。该企业内部OA系统采用模型组件与WEB技术结合的方式，具有强大的功能，广泛的适用性、可靠安全性和可扩展性。目的：学习运用当前热门的前台技术。 3、产品展示厅（限最多3人选） 项目描述： 在互联网发达的今天，当您想客户宣传自己的产品时，最好的方式是拥有自己的网站，通过网络来传播和展示您的产品信息。产品展示系统，为客户详细介绍自己的产品，提供了一个功能强大的平台。 系统界面友好、功能强大、操作简便，用户可以方便迅速掌握系统的操作。 4人事管理系统（限最多3人选） 项目描述：人事档案完整资料、人事分类管理（员工户口状况、员工政治面貌、员工生理状况、员工婚姻状况、员工合同管理、员工投保情况、员工担保情况）、考勤管理、加班管理、出差管理、人事变动管理（新进员工登记、员工离职登记、人员变更记录）、员工培训管理（员工培训、员工学历）、考核奖惩、养老保险等几大模块。系统具有人事档案资料完备，打印灵活，多样、专业的报表设计，灵活的查询功能等特点。 主要技能：掌握项目的开发流程：需求分析、详细设计、测试等；熟悉VC的多文档的开发技能和技巧；利用ADO技术操作SQL Server数据库；掌握数据库的开发和操作技能。 5、即时通讯系统（限最多3人选） 项目描述：系统采用UDP协议，具有：收发在线和离线消息、添加/删除好友、服务器端存储好友列表、在客户端存储好友资料和聊天记录、添加/删除好友组、可以群发消息、收发文件等功能。 主要技能：掌握项目的开发流程：需求分析、详细设计、测试等；熟悉VC的网络通信的开发技能和技巧，包括：TCP和UDP协议、线程等；利用ADO技术操作SQL Server数据库； 6、推箱子（限最多3人选） 【规则】本游戏的目的就是把所有的箱子都推到目标位置上。箱子只能推动而不能拉动。一次只能推动一个箱子。 经典的推箱子是一个来自日本的古老游戏,目的是在训练你的逻辑思考能力。在一个狭小的仓库中,要求把木箱放到指定的位置,稍不小心就会出现箱子无法移动或者通道被堵住的情况,所以需要巧妙的利用有限的空间和通道~！ 7、贪吃蛇（限最多3人选） 【规则】： A 用键盘的方向键控制蛇的上下左右移动。 B 游戏分为三种难度，SLUG为慢速，每吃一朵花得1分；WORM 为中速，每吃一朵花得2分；PYTHON为快速，每吃一朵花得3分。 C 游戏目标：操纵屏幕上那条可爱的小蛇，在黑框中不停吃花，而每吃一朵
实验一顺序表的操作 1.实验题目：顺序表的操作 2.实验目的和要求： 1）了解顺序表的基本概念、顺序表结构的定义及在顺序表上的基本操作(插入、删除、查找以及线性表合并)。 2)通过在Turbo C（WinTc，或visual stdio6）实现以上操作的C语言代码。 3）提前了解实验相关的知识（尤其是C语言）。 3.实验内容：(二选一) 1)顺序表的插入算法,删除算法,顺序表的合并算法 2)与线性表应用相关的实例(自己选择详尽实例) 4.部分参考实验代码： ⑴顺序表结构的定义： #include
{ int j; if(i<0||i>la-> length +1) {printf(“\n the value of i is wrong!”); return 0; } if(la-> length +1>=MAXLEN) { printf(“\n overflow!”); return 0; } . for(j=la-> length;j>=i;j--) la->list[j+1]=la->list[j]; la->list[i]=x; la-> length++; return 1; } ⑶顺序表删除 int ListDelete(sqList *la,int i) { if(i<0||i>la-> length) { printf(“\n the position is wrong!\n”); return 0; }
*******大学 《数据结构与算法分析》课程设计 题目：数据结构上机试题 学生姓名： 学号： 专业：信息管理与信息系统 班级： 指导教师： 2014年04月
目录 一、顺序表的操作 (2) 【插入操作原理】 (2) 【删除操作原理】 (2) 【NO.1代码】 (3) 【运行截图演示】 (7) 二、单链表的操作 (10) 【创建操作原理】 (10) 【插入操作原理】 (10) 【删除操作原理】 (10) 【NO.2代码】 (11) 【运行截图演示】 (20) 三、顺序栈的操作 (25) 【数值转换原理】 (25) 【NO.3代码】 (26) 【运行截图演示】 (30) 四、查找算法 (32) 【顺序查找原理】 (32) 【折半查找原理】 (32) 【NO.4代码】 (33) 【运行截图演示】 (38) 五、排序算法 (40) 【直接插入排序原理】 (40) 【快速排序原理】 (40) 【NO.5代码】 (41) 【运行截图演示】 (46)
一、顺序表的操作 （1）插入元素操作：将新元素x 插入到顺序表a 中第i 个位置； （2）删除元素操作：删除顺序表a 中第i 个元素。 【插入操作原理】 线性表的插入操作是指在线性表的第i-1个数据元素和第i 个数据元素之间插入一个新的数据元素，就是要是长度为n 的线性表： ()11,,,,,i i n a a a a -………… 变成长度为n+1的线性表： ()11,,,,,,i i n a a b a a -………… 数据元素1i a -和i a 之间的逻辑关系发生了变化。 （其【插入原理】在课本P23的算法2.3有解释） 【删除操作原理】 反之，线性表的删除操作是使长度为n 的线性表： ()111,,,,,,i i i n a a a a a -+………… 变成长度为n-1的线性表： ()111,,,,,i i n a a a a -+………… 数据元素1i a -、i a 和1i a +之间的逻辑关系发生变化，为了在存储结构上放映这个变化，同样需要移动元素。 （其【删除原理】在课本P24的算法2.4有解释）
数据结构课程设计哈希表设计问题
目录 1 前言 (1) 2 需求分析 (1) 2.1 任务和要求 (1) 2.2 运行环境 (1) 2.3 开发工具 (1) 3 分析和设计 (2) 3.1 系统分析及设计思路 (2) 3.2 主要数据结构及算法 (2) 3.3 函数流程图 (2) （1）哈希表的创建及初始化流程图 (2) 5 课程设计总结 (13) 5.1 程序运行结果或预期运行结果 (13) 说明：输入的数为30个姓的拼音，查找的为“pan”，输出的如上图所示。 (14) 5.2 设计结论 (15) 参考文献 (15) 致谢 (15)
1 前言 从C语言产生到现在，它已经成为最重要和最流行的编程语言之一。在各种流行编程语言中，都能看到C语言的影子，如Java的语法与C语言基本相同。学习、掌握C语言是每一个计算机技术人员的基本功之一。 根据本次课程设计的要求，我设计小组将编写一个C语言程序来处理哈希表问题，通过这个程序，将针对自己的班集体中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。 2 需求分析 2.1 任务和要求 针对自己的班集体中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。 要求：假设人名为中国姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用链表法处理冲突。 2.2 运行环境 （1）WINDOWS2000/XP系统 （2）Visual C++ 6.0编译环境或TC编译环境 2.3 开发工具 C语言
3 分析和设计 3.1 系统分析及设计思路 （1）创建哈希表 （2）姓名（结构体数组）初始化 （1）用除留余数法构建哈希函数 （2）用链表法处理冲突 (3)查找哈希表 在哈希表中进行查找，输出查找的结果和关键字，并计算和输出查找成功的平均查找长度 (4) 显示哈希表 显示哈希表的的格式： 3.2 主要数据结构及算法 定义结构体typedef struct hashtable创建哈希表 定义函数Hash_Init(HashTable ht)来对哈希表初始化 定义函数Hash_Insert(HashTable ht, Node *node)来为哈希表分配地址 定义函数Hash_Init(ht)输入30个名字 定义函数Hash_Create(HashTable ht)来求哈希表长度 定义函数hash_output(HashTable h)来输出哈希表 定义函数Hash_Link()构造链表函数 定义函数int hash_search(int h[],int key)查找输入的名字 3.3 函数流程图 （1）哈希表的创建及初始化流程图
《HTML网页编程技术综合课程设计》教学实施方案
————————————————————————————————作者：————————————————————————————————日期：
《网页编程技术综合课程设计》教学方案 一、课程设计目标 通过该课程设计综合应用本学期所学的网页制作知识，全面建立对网站的认知，建立网站设计与网页制作的基本思想；学会网站功能规划、网站布局、网页制作、网页配色等的基本技巧，掌握网页制作与网站设计相关软件的使用方法；通过课程设计教学环节能够制作有一定实用性的网站；能解决一些实际应用问题并以此为基础进一步扩展到相关的学科上；通过本课程设计提高网页的审美意识；通过团队合作制作网站，培养团队协作精神，初步了解软件企业开发软件系统模式，为将来适应工作打开良好的基础。 二、设计要求 1．本课程设计分小组进行，各小组成员原则上2~4人，不得超过4人,由小组长协调分工,每个组员充分发挥团队协作精神。 2．自选主题，使用Dreamweaver网页设计与制作软件，设计并制作一个内容完整、结构规范合理的静态网站，要求选取内容健康，网站中出现一定数量的图像和多媒体。网站主题应大小适中、内容健康、具有时代气息；网站提供的信息应与网站主题相符合, 主题突出、内容丰富； 3.页面设计合理、美观，有创意，适用于各种显示器的分辨率和颜色。 4.每个页面都要求有导航条和页脚信息，需要将这些信息制作成库项目，然后根据需要将之插入到模板或其它页面中。各个页面都要有标题，而且布局要合理、美观、大方。布局网页时要尽量主流布局方法（必须使用Div、表格等），并要有一定复杂度。 5.页面中需要有文字、图像、多媒体、超链接等，要求达到图文并茂的效果。所使用的文字的大小、字体和颜色要认真处理，除非特殊需要，不能出现空链接，文字不能简单用截图代替；所需图像和多媒体素材尽量自己设计，如有下载，自己必须再作处理，不得直接使用现有商业网站标志。 6. 为了保证页面的设计效果更好地兼容各种浏览器以及便于改版，要求用独立的CSS文件设置页面内容格式。 7.为主页添加背景音乐。 8.需要使用一定量的JavaScript脚本，使网页具有一定的交互功能。每小组必须制作一个表单，表单输入内容需要使用正则表达式进行验证。
排序算法课程设计 专业 班级 学号 姓名 指导老师
一：课程设计的目的 1.掌握各种排序的基本思想 2.掌握各种排序的算法实现 3.掌握各种排序的算法优劣分析花费的时间计算 4.掌握各种排序算法所适用的不同场合。 二：课程设计的内容 （1）冒泡、直插、选择、快速、希尔、归并、堆排序算法进行比较； （2）待排序的元素的关键字为整数。其中的数据用伪随机产生程序产生（如10000个,1000个），再使用各种算法对其进行排序，记录其排序时间，再汇总比较；（3）将每次测试所用的时间，用条形图进行表示，以便比较各种排序的优劣。 三：课程设计的实现 （1）直接插入排序 #include while(j > -1 && temp.key <= a[j].key) { a[j+1] = a[j]; j--; } a[j+1] = temp; } } void main() { /*srand((unsigned)time(NULL));// 随机种子*/ /*time_t t; srand((unsigned)time(&t));*/ time_t t1,t2; srand((unsigned)GetCurrentTime()); datatype num[10000]; t1=GetCurrentTime(); for(int i=0;i<10000;i++) { num[i].key=rand(); } int n=10000; InsertSort(num,n); for(int j=0;j<10000;j++) cout< 实习6、哈希表设计 一、需求分析 1. 问题描述 针对某个集体（比如你所在的班级）中的“人名”设计一个哈希表，使得平均查找长度均不超过R，完成相应的建表和查表顺序。 2. 基本要求 假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用伪随机探测再散列法处理冲突。 3. 测试数据 取读者周围较熟悉的30个人的姓名。 4. 实现提示 如果随机数自行构造，则应首先调整好随机函数，使其分布均匀。人名的长度均不超过19个字符（最长的人名如：庄双双（Zhuang Shuangshuang））。字符的取码方法可直接利用C 语言中的toascii函数，并可先对过长的人名先作折叠处理。 二、概要设计 ADT Hash { 数据对象D：D是具有相同特征的数据元素的集合。各数据元素均含有类型相同，可唯一标识数据元素的关键字。 数据关系R：数据元素同属一个集合。 InitNameTable() 操作结果：初始化姓名表。 CreateHashTable() 操作结果：建立哈希表。 DisplayNameTable() 操作结果：显示姓名表。 DisplayHashTable() 操作结果：显示哈希表。 FindName() 操作结果：查找姓名。 }ADT Hash 三、详细设计（源代码） （使用C语言） #include 题目1： 利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法进行排序。 要求： 1)至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结 果保存在不同的文件中。 2)统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。 代码如下： #include 课题：内部排序算法比较 第一章问题描述 排序是数据结构中重要的一个部分，也是在实际开发中易遇到的问题，所以研究各种排算法的时间消耗对于在实际应用当中很有必要通过分析实际结合算法的特性进行选择和使用哪种算法可以使实际问题得到更好更充分的解决！该系统通过对各种内部排序算法如直接插入排序，冒泡排序，简单选择排序，快速排序，希尔排序，堆排序、二路归并排序等，以关键码的比较次数和移动次数分析其特点，并进行比较，估算每种算法的时间消耗，从而比较各种算法的优劣和使用情况！排序表的数据是多种不同的情况，如随机产生数据、极端的数据如已是正序或逆序数据。比较的结果用一个直方图表示。 第二章系统分析 界面的设计如图所示： |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------| |******************************| 请选择操作方式： 如上图所示该系统的功能有： （1）：选择 1 时系统由客户输入要进行测试的元素个数由电脑随机选取数字进行各种排序结果得到准确的比较和移动次数并打印出结果。 （2）选择 2 时系统由客户自己输入要进行测试的元素进行各种排序结果得到准确的比较和移动次数并打印出结果。 （3）选择0 打印“谢谢使用！！”退出系统的使用！！ 第三章系统设计 （I）友好的人机界面设计：（如图3.1所示） |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------| |******************************| （3.1） （II）方便快捷的操作：用户只需要根据不同的需要在界面上输入系统提醒的操作形式直接进行相应的操作方式即可！如图（3.2所示） |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------| 数据结构课程设计报告 课题四哈希表查找的设计 1. 任务和功能要求 设哈希表长为20，用除留余数法构造一个哈希函数，以开放定址法中的线性探测再散列法作为解决冲突的方法，编程实现哈希表查找、插入和建立算法。 2. 需求分析 用户输入20个以内的数字存储在哈希表中，并可以在表中查找关键字。3.概要设计 typedef struct { int *key; //关键字 int count; //表长 }HashTable; int creat(HashTable *T) //初始化哈希表 程序调用关系如下： 主函数模块 哈希表初始化模块查询模块 插入模块 4. 详细设计 #include #include 综合课程设计1 一、考核方法和内容 根据课程设计过程中学生的学生态度、题目完成情况、课程设计报告书的质量和回答问题的情况等按照10%、40%、30%、20%加权综合打分。成绩评定实行优秀、良好、中等、及格和不及格五个等级。评分标准： 优秀：答辩所有问题都能答出+报告良好 或报告良好+实现“提高部分”的功能； 良好：答辩所有问题都能答出+报告一般； 或报告一般+实现“提高部分”的功能； 中等：答辩大部分问题能答出+报告良好； 及格：答辩大部分问题能答出+报告一般； 以下四种，都不及格： 1)答辩几乎答不出问题； 2)报告几乎都是代码； 3)雷同部分达到60%以上； 4)课设报告与数据结构和c/c++关联不大。 课设报告的装订顺序如下： 任务书（签名，把题目要求贴在相应位置，注意下划线）-----目录（注意目录的格式，页码）-----1、设计任务（题目要求）-----2、需求分析（准备选用什么数据逻辑结构？数据元素包含哪些属性？需要哪些函数？为什么要这样设计？最后列出抽象数据类型定义）-----3、系统设计（设计实现抽象数据类型，包含选择什么物理存储方式？数据元素的结构体或类定义，以及各函数的设计思路，算法，程序流程图等）----4、编码实现（重要函数的实现代码）-----5、调试分析（选择多组测试数据、运行截图、结果分析）-----6、课设总结（心得体会）-----7、谢辞-----8、参考文献； 课设报告打印要求： B5纸张打印，报告总页数控制在10—15页内，报告中不能全是代码，报告中代码总量控制在3页内。版式：无页眉，有页码，页码居中 字号：小四，单倍行距 字体：宋体+Times new Romar 截图：截图要配图的编号和图的题目，如：“图1 Insert函数流程图” 二、课程设计的具体内容 1.想要优，必须实现“提高部分”的功能，但，实现“提高部分”不代表一定优； 2.其他成绩，不用完成“提高部分”。 要求：全部采用数据结构课程中的内容实现，采用C或C++实现，逻辑结构只能选线性结构、树型结构、图型结构、集合结构中的一种，不能用数据库。 1、算术表达式求解 基本要求：给定一个算术表达式，通过程序求出最后的结果。 (1)从键盘输入要求解的算术表达式； (2)采用栈结构进行算术表达式的求解过程； ? & 数据结构课程设计报告 —几种排序算法的演示( ； 时间：2010-1-14 … 一需求分析 运行环境 Microsoft Visual Studio 2005 程序所实现的功能 对直接插入排序、折半插入排序、冒泡排序、简单选择排序、快速排序、堆排序、归并排序算法的演示，并且输出每一趟的排序情况。 程序的输入（包含输入的数据格式和说明） % <1>排序种类三输入 <2>排序数的个数的输入 <3>所需排序的所有数的输入 程序的输出（程序输出的形式） <1>主菜单的输出 <2>每一趟排序的输出，即排序过程的输出 " 二设计说明 算法设计思想 <1>交换排序（冒泡排序、快速排序） 交换排序的基本思想是：对排序表中的数据元素按关键字进行两两比较，如果发生逆序（即排列顺序与排序后的次序正好相反），则两者交换位置，直到所有数据元素都排好序为止。 <2>插入排序（直接插入排序、折半插入排序） % 插入排序的基本思想是：每一次设法把一个数据元素插入到已经排序的部分序列的合适位置，使得插入后的序列仍然是有序的。开始时建立一个初始的有序序列，它只包含一个数据元素。然后，从这个初始序列出发不断插入数据元素，直到最后一个数据元素插到有序序列后，整个排序工作就完成了。 <3>选择排序（简单选择排序、堆排序） 选择排序的基本思想是：第一趟在有n个数据元素的排序表中选出关键字最小的数据元素，然后在剩下的n-1个数据元素中再选出关键字最小（整个数据表中次小）的数据元素，依次重复，每一趟（例如第i趟，i=1，…，n-1）总是在当前剩下的n-i+1个待排序数据元素中选出关键字最小的数据元素，作为有序数据元素序列的第i个数据元素。等到第n-1趟选择结束，待排序数据元素仅剩下一个时就不用再选了，按选出的先后次序所得到的数据元素序列即为有序序列，排序即告完成。 <4>归并排序（两路归并排序） 两路归并排序的基本思想是：假设初始排序表有n个数据元素，首先把它看成是长度为 《操作系统课程设计》教学大纲 课程类型：专业必修课 学分：0.5 计划周数：1周 预修课程：高级语言程序设计、微机原理、数据结构 开设学期：第四学期 适用专业：计算机科学与技术本科、网络工程本科、软件工程本科 一、课程设计目的与任务 《操作系统》是一门重要的专业基础课，是涉及较多硬件知识的计算机系统软件课程。在计算机软硬件课程的设置上，它起着承上启下的作用。操作系统对计算机系统资源实施管理，是所有其他软件与计算机硬件的唯一接口，用户在使用计算机时都要得到操作系统提供的服务。操作系统课程设计的主要任务是研究计算机操作系统的基本原理和算法，掌握操作系统的进程管理、存储管理、文件管理和设备管理的基本原理与主要算法。目的是使学生掌握常用操作系统（如DOS、Windows或Linux）的一般管理方法，了解它是如何组织和运作的，对操作系统的核心概念和算法有一个透彻的理解，并对系统运行的机制有一个全面的掌握，从而充分理解系统调用与程序设计之间的关系。 二、课程设计选题 设计项目一：动态资源分配算法演示程序（银行家算法） 内容： 主要用于解决多种资源被多个独立执行的进程共享的安全算法。采用矩阵存储资源的数据，通过对系统资源预分配后检查系统状态，以避免死锁的产生。 要求： 1.资源种类与数目可在界面进行设置，在资源分配过程中可以随时增加进程及其对资源的需求。 2.可读取样例数据（要求存放在外部文件中）进行资源种类、数目与进程数的初始化。 3.在资源分配过程中可以随时进行系统安全状态检测。 4.如果能够通过系统安全状态检测，则系统对该进程进行资源分配；当进程满足所有资 源分配后能够自行释放所有资源，退出资源竞争。 5.要求进行安全性检查时按指定策略顺序进行，即按每个进程当前Need数由小至大进 行排序，如果Need数相同，则按序号由小至大进行排序； 6.具有一定的数据容错性。 设计项目二：通用处理机调度演示程序 内容： 设计一个模拟处理机调度算法，以巩固和加深处理机调度的概念。 要求： 1.进程调度算法包括：时间片轮转算法、先来先服务算法、短作业优先算法、静态优先权 优先调度算法、高响应比调度算法。 2.每一个进程有一个PCB，其内容可以根据具体情况设定。 3.进程数、进入内存时间、要求服务时间、作业大小、优先级等均可以在界面上设定。 4.可读取样例数据（要求存放在外部文件中）进行进程数、进入内存时间、时间片长度、 作业大小、进程优先级的初始化 5.可以在运行中显示各进程的状态：就绪、执行（由于不要求设置互斥资源与进程间的同 步关系，故只有两种状态） 6.采用可视化界面，可在进程调度过程中随时暂停调度，查看当前进程的状态及相应的阻 塞队列。 7.有性能比较功能，可比较同一组数据在不同调度算法下的平均周转时间。 设计项目三：用多进程同步方法演示“桔子苹果”问题 内容： 有两类生产者，一类负责生产桔子，一类负责生产苹果；有两类消费者，一类负责消费桔子，一类负责消费苹果；他们共享一个有20个存储单元的有界缓冲区，每个存储单元只能放入一种产品（桔子/苹果）。 要求： 1．二类生产者与二类消费者数目均为20，即20个生产者负责生产桔子，20个生产者负责生产苹果；20个消费者负责消费桔子，20个消费者负责消费苹果。 顺序表的基本操作 /*sqList.h 文件*/ #define LIST_INIT_SIZE 50 /*初始分配的顺序表长度*/ #define INCREM 10 /*溢出时，顺序表长度的增量*/ #define OVERFLOW 1 #define OK 0 #define ERROR -1 typedef int ElemType; /*定义表元素的类型*/ typedef struct SqList{ ElemType *elem; /*存储空间的基地址*/ int length; /*顺序表的当前长度*/ int listsize; /*当前分配的存储空间*/ }SqList; /*sqListOp.h 文件*/ #include "Sqlist.h" int InitList_sq(SqList &L); //顺序表创建函数定义 void FreeList_sq(SqList &L); //顺序表销毁函数定义 int ListInsert_sq(SqList &L, int i, ElemType e); //在顺序表的位置i插入元素e void PrintList_sq(SqList &L); //遍历并输出顺序表所有元素 int ListDelete_sq(SqList &L, int i,ElemType &e); //删除顺序表第i个元素的 bool ListEmpty(SqList &L); //判断顺序表是否为空 int LocateElem_sq(SqList L,ElemType e); //在顺序表里查找出第1个与e相等的数据元素位置//已知线性表La和Lb的元素按值非递减排列 //归并后的La和Lb得到新的顺序线性表Lc，Lc的元素也是按值非递减排列 void MergeList_sq(SqList La,SqList Lb, SqList &Lc); /*sqListOp.cpp文件*/ #include 排序算法： (1) 直接插入排序 (2) 折半插入排序(3) 冒泡排序 (4) 简单选择排序 (5) 快速排序(6) 堆排序 (7) 归并排序 【算法分析】 （1）直接插入排序；它是一种最简单的排序方法，它的基本操作是将一个记录插入到已排好的序的有序表中，从而得到一个新的、记录数增加1的有序表。 （2）折半插入排序：插入排序的基本操作是在一个有序表中进行查找和插入，我们知道这个查找操作可以利用折半查找来实现，由此进行的插入排序称之为折半插入排序。折半插入排序所需附加存储空间和直接插入相同，从时间上比较，折半插入排序仅减少了关键字间的比较次数，而记录的移动次数不变。 （3）冒泡排序：比较相邻关键字，若为逆序（非递增），则交换，最终将最大的记录放到最后一个记录的位置上，此为第一趟冒泡排序；对前n-1记录重复上操作，确定倒数第二个位置记录；……以此类推，直至的到一个递增的表。 (4)简单选择排序：通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i（1<=i<=n）个记录交换之。 (5)快速排序:它是对冒泡排序的一种改进，基本思想是，通过一趟排序将待排序的记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。 (6)堆排序: 使记录序列按关键字非递减有序排列，在堆排序的算法中先建一个“大顶堆”，即先选得一个关键字为最大的记录并与序列中最后一个记录交换，然后对序列中前n-1记录进行筛选，重新将它调整为一个“大顶堆”，如此反复直至排序结束。 (7)归并排序:归并的含义是将两个或两个以上的有序表组合成一个新的有序表。假设初始序列含有n个记录，则可看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2或1的有序子序列；再两两归并，……，如此重复，直至得到一个长度为n的有序序列为止，这种排序称为2-路归并排序。 【算法实现】 （1）直接插入排序： void InsertSort(SqList &L){ for(i=2;i<=L.length ;i++) if(L.elem[i]哈希表设计-数据结构课程设计
数据结构课程设计之综合排序代码及使用方法
数据结构课程设计(内部排序算法比较 C语言)
数据结构课程设计哈希表
综合课程设计1题目2016-2017.2
数据结构课程设计报告---几种排序算法的演示(附源代码)
《操作系统》综合课程设计教学大纲
顺序表的基本操作 (2)
数据结构课程设计排序算法总结
相关主题
文本预览