第一篇:数据结构作业一范文
南京工业大学 数据结构 作业答案 作业3(推荐)
第三次作业
1.假设正读和反读都相同的字符序列为“回文”,例如,‘abba’和‘abcba’是回文,‘abcde’ 和‘ababab’则不是回文。假设一字符序列已存入计算机,请分析用线性表、堆栈和队列等方式正确输出其回文的可能性?
2. 顺序队的“假溢出”是怎样产生的?如何知道循环队列是空还是满?
3. 设循环队列的容量为40(序号从0到39),现经过一系列的入队和出队运算后,有
① front=11,rear=19;② front=19,rear=11;问在这两种情况下,循环队列中各有元素多少个?
4. 试将下列递归过程改为非递归过程。
void test(int &sum){
int x;
Sanf(x);
if(x= =0) sum=0;
else {test(sum);sum+=x;}
printf(sum);
}
1.假设正读和反读都相同的字符序列为“回文”,例如,‘abba’和‘abcba’是回文,‘abcde’ 和‘ababab’则不是回文。假设一字符序列已存入计算机,请分析用线性表、堆栈和队列等方式正确输出其回文的可能性?
答:线性表是随机存储,可以实现,靠循环变量(j--)从表尾开始打印输出;
堆栈是后进先出,也可以实现,靠正序入栈、逆序出栈即可;
队列是先进先出,不易实现。
哪种方式最好,要具体情况具体分析。若正文在机内已是顺序存储,则直接用线性表从后往前读取即可,或将堆栈栈顶开到数组末尾,然后直接用POP动作实现。(但堆栈是先减后压还是„„)
若正文是单链表形式存储,则等同于队列,需开辅助空间,可以从链首开始入栈,全部压入后再依次输出。
2. 顺序队的“假溢出”是怎样产生的?如何知道循环队列是空还是满?
答:一般的一维数组队列的尾指针已经到了数组的上界,不能再有入队操作,但其实数组中还有空位置,这就叫“假溢出”。
采用循环队列是解决假溢出的途径。
另外,解决队满队空的办法有三:
① 设置一个布尔变量以区别队满还是队空;
② 浪费一个元素的空间,用于区别队满还是队空。
③ 使用一个计数器记录队列中元素个数(即队列长度)。
我们常采用法②,即队头指针、队尾指针中有一个指向实元素,而另一个指向空闲元素。
判断循环队列队空标志是: f=rear队满标志是:f=(r+1)%N
3. 设循环队列的容量为40(序号从0到39),现经过一系列的入队和出队运算后,有
① front=11,rear=19;② front=19,rear=11;问在这两种情况下,循环队列中各有元素多少个?
答:用队列长度计算公式:(N+r-f)% N
① L=(40+19-11)% 40=8② L=(40+11-19)% 40=32
4. 参考程序:
void test(int &sum){
Stack S;
int x;
Sanf(x);
InitStack(S);
While(x){
Push(S,x);
Scanf(x);
}
sum=0;
printf(sum);
while(Pop(S,x)){
sum+=x;
printf(sum);
}
}
第二篇:数据结构作业——二叉树
数据结构实验报告二
题目:
用先序递归过程监理二叉树(存储结构:二叉链表)
输入数据按先序遍历输入,当某节点左子树或者右子树为空时,输入‘*’号,如输入abc**d**e**时,得到的二叉树为:
并用如下实力测试:
算法思路:
显然,建立一个二叉链表存储的二叉树,如果不考虑效率要求,考虑到程序的简介性,递归建立和递归遍历是一种很好的办法。
利用C++的类模板的方法实现建立,遍历,输出等二叉树操作。首先利用构造函数实现先序遍历建立二叉树,然后调用类模板中已经声明好的四种遍历函数,将遍历结果输出,检验建立好的二叉树是否为要求的二叉树。
初始化:利用构造函数建立二叉树。采用先序递归的调用方法,构造函数主体如下:
template BiTree::BiTree( ) { this->root = Creat( );//利用this指针调用creat函数 }
template BiNode* BiTree::Creat()//定义构造函数 { BiNode* root; T aa; cout<<"请按前序序列方式输入节点数据,每次输入一个"<>aa; if (aa=="*") root = NULL; else{
root = new BiNode;
//生成一个结点 root->data=aa;
root->lchild = Creat();
//递归建立左子树
root->rchild = Creat();
//递归建立右子树
} return root; } 构造这样的函数,可以在输入时,按先序遍历顺序每次输入一个节点的数据,可以实现任意二叉树的构造。
为了检验构造的二叉树是否为预先设想的二叉树,需要遍历二叉树并进行输出。考虑到单一的输出并不能确定唯一的二叉树,因此对遍历二叉树的四种常用发方法,即先序遍历,中序遍历,后续遍历,层次遍历分别实现,通过遍历结果检验构造的二叉树是否为预先设计好的二叉树。
先序遍历:采用递归的方法建立。 template voidBiTree::xianxu(BiNode *root) { if(root==NULL) return;//如果节点为空,则返回空 else{ cout
xianxu(root->lchild);//先序遍历树的左子树 xianxu(root->rchild);//先序遍历树的右子树
} 中序遍历:递归方法建立: template voidBiTree::zhongxu (BiNode *root) {
if (root==NULL) return;
//如果节点为空,则返回空 else{ zhongxu (root->lchild);
//中序递归遍历root的左子树 cout
//访问根结点
zhongxu (root->rchild);
//中序递归遍历root的右子树
}
} 后序遍历:递归方法建立: template voidBiTree::houxu(BiNode *root) {
if (root==NULL)
return;
//如果节点为空,返回空 else{ houxu(root->lchild);
//后序递归遍历root的左子树 houxu(root->rchild);
//后序递归遍历root的右子树 cout
//访问根节点
} } 层序遍历:采用非递归方法。利用队列的方法层序遍历二叉树。建立一个队列,在访问一个节点的时候,把它的左孩子和右孩子入队,并且将这个节点出队。当队列为空时,就完成了对二叉树的层序遍历。
template voidBiTree::cengxu(BiNode *root) { constintMaxSize = 100; int front = 0; int rear = 0; //利用队列的方法对树进行层序遍历 BiNode* Q[MaxSize]; BiNode* q; if (root==NULL) return;// 如果节点为空,返回空 else{
Q[rear++] = root;// 若节点不为空,则该节点入队 while (front != rear)
{
q = Q[front++]; //只要队列不为空,则节点依次出队 cout
if (q->lchild != NULL)
Q[rear++] = q->lchild;
if (q->rchild != NULL)
Q[rear++] = q->rchild;// 同时,该节点的双子入队
} } } 函数主体部分:声明一个类中的对象,调用构造函数,建立二叉树,并输出四种遍历结果,检验输出结果。
int main() {
BiTreeshu; //声明类中一个对象,在构造了一颗树
BiNode* root = shu.Getroot( ); //获取指向根结点的指针
cout<<"前序遍历序列为 "<
程序结构:
主函数建立一个类模板定义构造函数,析构函数,以及成员函数声明类中的一个对象调用构造函数,构造一颗二叉树层序遍历二叉树后序遍历二叉树中序遍历二叉树前序遍历二叉树获取该二叉树的根节点将结果输出,人工检验 源代码:
#include using namespace std;
template struct BiNode
{
T data;
BiNode *lchild, *rchild; };
template class BiTree
{ public: BiTree( );
//构造函数,初始化一棵二叉树 ~BiTree(void);
//析构函数,释放二叉链表中各结点的存储空间
BiNode* Getroot();
//获得指向根结点的指针
void xianxu(BiNode *root);
//前序遍历二叉树
void zhongxu(BiNode *root);
//中序遍历二叉树
void houxu(BiNode *root);
//后序遍历二叉树
void cengxu(BiNode *root);
//层序遍历二叉树 private:
BiNode *root;
BiNode *Creat( );
void Release(BiNode *root);
}; template BiTree::BiTree( ) { this->root = Creat( );//利用this指针调用creat函数 }
template BiNode* BiTree::Creat()//定义构造函数 { BiNode* root; T aa; cout<<"请按前序序列方式输入节点数据,每次输入一个"<>aa;
if (aa=="*") root = NULL;
else{
root = new BiNode;
//生成一个结点
root->data=aa;
root->lchild = Creat();
//递归建立左子树
root->rchild = Creat();
//递归建立右子树
}
return root; }
template BiTree::~BiTree(void) { Release(root);//析构函数,释放存储指针所需要的空间 }
template BiNode* BiTree::Getroot( )//获取根节点所在指针的位置 { return root; }
template void BiTree::xianxu(BiNode *root) { if(root==NULL) return;//如果节点为空,则返回空
else{
cout
xianxu(root->lchild);//先序遍历树的左子树
xianxu(root->rchild);//先序遍历树的右子树
} }
template void BiTree::zhongxu (BiNode *root) {
if (root==NULL) return;
//如果节点为空,则返回空
else{
zhongxu (root->lchild);
//中序递归遍历root的左子树
cout
//访问根结点
zhongxu (root->rchild);
//中序递归遍历root的右子树
} }
template void BiTree::houxu(BiNode *root) {
if (root==NULL)
return;
//如果节点为空,返回空
else{
houxu(root->lchild);
//后序递归遍历root的左子树
houxu(root->rchild);
//后序递归遍历root的右子树
cout
//访问根节点
} }
template void BiTree::cengxu(BiNode *root) {
const int MaxSize = 100; int front = 0; int rear = 0; //利用队列的方法对树进行层序遍历
BiNode* Q[MaxSize];
BiNode* q; if (root==NULL) return;// 如果节点为空,返回空
else{
Q[rear++] = root;// 若节点不为空,则该节点入队
while (front != rear)
{
q = Q[front++]; //只要队列不为空,则节点依次出队
cout
if (q->lchild != NULL)
Q[rear++] = q->lchild;
if (q->rchild != NULL)
Q[rear++] = q->rchild;// 同时,该节点的双子入队
} } }
template void BiTree::Release(BiNode* root)//析构函数,释放存储空间 {
if (root != NULL){
Release(root->lchild);
//释放左子树
Release(root->rchild);
//释放右子树
delete root;
}
}
int main() {
BiTree shu; //声明类中一个对象,在构造了一颗树
BiNode* root = shu.Getroot( ); //获取指向根结点的指针
cout<<"前序遍历序列为 "<
cout<<"层序遍历序列为"<
通过对结果的分析,发现输出结果与建立二叉树时的输入完全符合,说明程序的运行结果是正确的。
心得体会:
1) 函数递归的方法可以在相当程度上使程序简洁,避免代码的冗长复杂。 2) 构造函数如果带参数,在声明对象的时候应该将实参指出来。但是本题中构造函数位递归调用,初始的根节点的数据值由键盘输入,因此无法在声明对象时引入实参。所以最后选择了无参但是引用了this指针的构造函数。可见,对于构造函数的含参调用应该小心谨慎。
3) 编程时,要不停得检验自己的输入与输出,必要的时候需要人工进行计算,以保证程序的运行按照预先的设想。
第三篇:《数据结构》上机作业——实验报告(五)[推荐]
“计算机软件技术基础”课程实验报告
(五)
实验名称:排序算法
班级_______ 姓名__________ 学号______实验日期:
实验机时:3 学时实验成绩:
-----------------
一.实验目的:
1、 掌握主要排序算法的思想和实现技术。
二.实验内容:
1、 设计一程序,要求:输入学生“软件技术基础”课的成绩(学
号、姓名、平均成绩、总学分);按总学分对学生数据进行排序。(要求:实现任选3种排序算法)
三.程序:
1、程序规范(输入数据、功能、输出数据)
2、设计分析(数据表示、算法)
3、C源代码(电子版)
四.程序调试:
第四篇:数据仓库与数据挖掘第一次作业
电子商务这一行业目前还处于摸索期,有很多需要完善和可以创新的地方。这学期选修了袁老师的《电子商务》,印象最深的就是老师提过这样的想法:电商(主要是B2B)、百度等搜索引擎以及新浪微博等社交平台都是可以做咨询业的,即根据客户的消费(或搜索)记录、评价等信息定期为企业生成反馈报告。要实现之一定是需要数据仓库和数据挖掘等这类技术,通过收集、分析大量客户数据,为企业的预测、决策提供情报。
企业通过电子商务网站开展网络经营的过程中,利用数据仓库组织和存储大量的客户信息,在此基础上利用数据挖掘技术对这些信息进行抽取、分析,找出更深层次的隐藏信息,从而使企业的电子商务网站达到更高的客户满意度,将大大地提高企业网络经营的效率,大大降低企业的运营成本。具体功能和作用如下: 首先,电子销售商可以获知访问者的个人爱好,更加充分地了解顾客的需要,并根据顾客的资料分析潜在的目标市场。
其次,企业也可以了解客户的价值,利用数据仓库的资料,发现什么样的顾客群在网站上购买什么商品,区分高价值顾客和一般价值顾客,对各类顾客采取相应的营销策略。
再次,根据顾客的历史资料,不仅可以预测需求趋势,还可以评估需求倾向的改变,为顾客提供更好的服务。
另外,企业通过理解访问者的动态行为可以优化电子商务网站的经营模式。 最后,对涉及消费行为的大量信息进行收集、加工和处理,企业就可以确定特定消费群体或个体的兴趣、消费习惯、消费倾向和消费需求,进而推断出相应消费群体或个体下一步的消费行为,然后以此为基础,对所识别出来的消费群体进行特定内容的定向营销。例如:(1)对那些要通过网站发送广告的企业,分析用户访问模式有助于针对性地在某些用户经常访问的地方插播广告条。这样,根据这些信息,网站的建设者就可以对特定的顾客群提供个性化广告服务。这种广告要比泛泛的、随意的广告有价值得多;(2)在强大的数据挖掘技术与全面的顾客资料数据基础上,企业可以根据各个细分市场,甚至是每一个顾客的独特需求来为他们设计“量身定造”的产品。高度细分化、定制化的产品有利于提高顾客满意度,巩固与他们的长久关系,最终达到留住顾客的目的;(3)针对顾客设计个性化网站。利用数据挖掘工具,电子商务网站可以做到以顾客需求为导向,达到一对一行销的目的。网站将改变原有的千篇一律的形式,而强调信息个性化,亦即顾客所得到的信息将是网站针对其个人喜好、需求与特点的设定所给予的,也就是符合顾客的个人信息需求。例如顾客可以到一些新闻上去订阅他喜欢看的信息类别,如政治新闻或科技新闻。当使用者再次拜访此网站时,网站就会智能地只显示出该顾客所喜欢看的信息。
第五篇:数据库设计(大作业)
第七章 数据库设计 大作业
题目:
现在要求为某学校图书馆设计一个图书管理系统的数据库,背景如下:
该学校是一所多学科、多层次大学,学校有高职生、本科生(含一本、二本、三本)、硕士研究生(含MBA)和博士研究生等多种层次的学生,图书馆为全校学生和教职工提供图书借阅服务。
图书馆按照图书的性质(中文图书、外文图书、新书)将借阅分为不同的借阅种类:中文图书借阅、外文图书借阅和(新书)短期外借;不同的读者对象也有不同的借阅要求。
对每种借阅类型和读者,其借阅册数、借期、是否允许续借、续借期限等不同。不同借阅种类和借阅对象的借阅要求规定如附1所示。例如:本专科学生可以借中文图书5本,借期30天,可以续借一次,续借15天。
“新书”的概念是相对的,一本新书在上架(或入库)后的60天内只提供短期外借,此后即自动地成为中文图书或者外文图书。 借出的图书不能在当天归还。
每次借阅后读者最多可以续借一册图书一次。
在本馆所借的文献资料,均应在规定的期限内按时归还。逾期不还者,将分别按以下规定处理:
1、 中文图书借阅:每册每天罚款0.2元。
2、 新书借阅和外文图书借阅:每册每天罚款0.5元。
3、 在超期图书归还并缴清罚款之前,读者不可借阅图书;超期图书也不能续借。
对于超期的图书,图书管理系统将自动向读者电子邮箱中发一封电子邮件催还图书。
每个读者都要有一个编号,并记录读者的姓名、性别、类型(学生、教师等)、单位、电子信箱等。
图书馆采编部负责对入库的文献资料按规定进行编目、著录、加工、建库。对每本图书、杂志,要记录其基本信息,如名称、作者、ISBN号、出版地、出版社、出版时间、字数、单价、内容简介、所属分类号等,其中,图书分类按照中图法分类规则进行分类。中图法分类简表见后。
学校有三个校区,相应地,馆藏分布于三个分馆中:A图书馆(侧重于经济管理、综合类)、B图书馆(侧重于理工、计算机类)和C图书馆(侧重于法学、外语、体育、艺术、音乐等方面)。图书馆中每种图书可能采购多册,分布在多个馆中。全校师生可以在任何一个分馆中借阅。
每个分馆中的图书借完为止,如本部图书馆有某图书1本,这本图书借出后,在归还之前,本部图书馆中就查阅到该图书为借出状态,而且,馆藏已空,但是读者可以到其他馆中借阅。 图书的归还遵循属地原则,即从哪个分馆借出的图书必须要在那个分馆中归还。 图书馆管理员有权更改图书到期时间,比如将本来暑假到期的图书的到期时间改为9月10日。
读者可以在网上查询自己的图书借阅情况,一般读者只可以查阅到自己的借阅情况和图书的信息,而管理员可以查看任何读者的信息、借阅情况,任何图书的信息和借阅情况。
在网上查询系统中,每个用户都分配了用户名(唯一)和密码,其中,用户名就是读者号,密码初始值为读者的学号或者工号,可以修改。
附1:图书借阅册数与期限表
附2:中图法分类号示例:
A 马克思主义、列宁主义、毛泽东思想、邓小平理论 A1 马克思、恩格斯著作 A2 列宁著作 A3 斯大林著作 A4 毛泽东著作 A49 邓小平著作
A5 马克思、恩格斯、列宁、斯大林、毛泽东、邓小平著作汇编 A7 马克思、恩格斯、列宁、斯大林、毛泽东、邓小平生平和传记 A8 马克思主义、列宁主义、毛泽东思想邓小平理论的学习和研究 B 哲学、宗教
B0 哲学理论
B2 中国哲学
B4 非洲哲学
B6 大洋洲哲学
B80 思维科学
B82 伦理学(道德学)B84 心理学
B1
世界哲学
B3 亚洲哲学
B5 欧洲哲学
B7 美洲哲学 B81 逻辑学(论理学) B83 美学
B9 宗教
作业要求:请设计一个图书馆管理系统的数据库(用SQL SERVER 2000),具体要求如下:
1、 完成设计报告,报告内容包括:需求分析、概念设计、逻辑结构设计、物理设计等。
2、 用SQL SERVER 2000建立数据库,并完成表的设计及基础数据入库。
(报告要求A4纸打印,17周交)