重庆科技学院《数据结构》课程设计专业班级: 计科2012级3班学 号: 2012442084姓 名: 赵弈胰成 绩:⏺摘要设计一些简单的程序,来实现屏幕输出,约瑟夫问题,单词的拼写检查,非递减有序集合合并,括号匹配,排队优化,快速排序[1]等功能。我们首先应该想到设计需要的知识点,比如:链表[2]、数组等方法,赋值运算、逻辑运算、括号运算等运算,还有循环等。数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。关键字:数据结构、数组、链表、算法目录摘要 I目录 II1需求分析 11.1功能需求[3] 11.2系统运行环境 22开发环境 22.1 QT简介 22.2开发环境搭建 32.1.1安装g++ 32.1.2安装QT5.0 33总体设计 43.1简要说明 4currentFile--;DisplayImage(dirCurrent->absoluteFilePath(*currentFile));UpdateUI();}void ImageViewer::on_actionZoomOut_triggered()(scaleImage(0.8);UpdateUI();)void ImageViewer::on_actionZoomIn_triggered()(scaleImage(1.25);UpdateUI();)void ImageViewer::on_actionNormalSize_triggered()(scaleFactor = 1.0;scaleImage(1.0);UpdateUI();)void ImageViewer::on_treeView_clicked ( const QModelIndex index )(const QString path = dirModel->data(index, QDirModel::FilePathRole).toString();dirCurrent->setPath(path);displayFiles = dirCurrent->entryList(supportFormat, QDir::Files);currentFile = displayFiles.constBegin();if(currentFile != displayFiles.constEnd())DisplayImage(dirCurrent->absoluteFilePath(*currentFile));UpdateUI();)const char *htmlAboutText ="""This program is subject to GPL license.""Writed by Eric Guo""https:/ericguo.cnblogs.com/""";void ImageViewer::on_actionAbout_triggered()(QMessageBox::about(this, tr("About Qt Mini Image Viewer"), htmlAboutText);)3.2总体程序框图 44详细设计[4] 54.1界面设计 54.2函数代码实现 55功能测试 85.1下一张 85.2上一张 95.3放大 95.4缩小 106总结 117参考文献 12附录 13⏺1需求分析1.1功能需求1)编写一个程序,从键盘输入整数n, 在屏幕上输出1~n之间的所有整数,每个数字之间保留3个空格。2)有n只猴子,按顺时针方向围成一圈选大王(编号从1到n),从第1号开始报数,一直数到m,数到m的猴子退出圈外,剩下的猴子再接着从1开始报数。就这样,直到圈内只剩下一只猴子时,这个猴子就是猴王,编程求输入n,m后,输出最后猴王的编号。3)现在有一些英语单词需要做拼写检查,你的工具是一本词典。需要检查的单词,有的是词典中的单词,有的与词典中的单词相似,你的任务是发现这两种情况。单词A与单词B相似的情况有三种:A. 删除单词A的一个字母后得到单词B; B. 用任意一个字母替换单词A的一个字母后得到单词B; C. 在单词A的任意位置增加一个字母后得到单词B。 D. 你的任务是发现词典中与给定单词相同或相似的单词。 E. LA和线性表[5]LB中的数据元素按值非递减有序排列,现要求将LA和LB归并为一个新的线性表LC,且LC中的元素仍按值非递减有序排列。 F. [(}])或( ][()]))等均为正确的格式,而([]))}或([()]或([])均为不正确的格式. G. xtra right brackets 如果输入的左括号多余, 输出:Extra left brackets 如果输入的括号不匹配,输出:Brackets not match 如果输入的括号匹配,输出:Brackets match 6)设某银行有A、B两个业务窗口,且处理业务的速度不一样,其中A窗口处理速度是B窗口的2倍---即当A窗口处理完2个顾客时,B窗口处理完一个顾客。给定到达银行的顾客序列,请按业务完成的顺序输出顾客序列。假定不考虑顾客先后到达的时间间隔,并且当不同窗口同时处理完2个顾客时,A窗口顾客优先输出。 A. R. Hoare想出了一种很快的排序方法,由于它的确很快,于是我们就叫它快速排序。快速排序的原理其实很简单。假设我们需要将一些待排序的数从小到大排序。首先,我们从这些数中随便找一个数(key),然后把比它小的放到它的左边,比它大的放到它的右边,这样它左边的任意一个数都比右边的任意一个数小,我们把这个操作叫做“划分”。这时候我们再递归调用[6]快排函数,将key的左边、右边都排好,整个集合的数字就有序了。 1.2环境需求 VC++6.0编辑器 PC机一台 2详细设计 2.1屏幕输出题 1)程序说明:这个程序主要就是运用循环来输出数字 2)主要代码: nf("%d",n); or(int i=1; i<=n; i++) ( printf("%d ",i); ) 3)程序流程图, , 。初始化 。 。 , 。初始化 。 。 Y N 程序结束 , 。初始化 。 。 图2.1 2.2约瑟夫问题 K代表被叫出去的人数,每次加1;喊道最后一个时,接着第一个数数,如此循环,直到还剩一个时结果输出。 2)主要代码: or(i=1; i<=n; i++) ( [i]=1; ) or(i=1; i<=n; i++) ( [i]==1) { [i]; n",j); if(j==m) { n",i); j=0; [i] = 0; k++; ) if(k==n) ( n",i); k; ) } 3)程序流程图: , 。初始化 。 。 , 。初始化 。 。 , 。初始化 。 。 , 。初始化 。 。, 。初始化 。 。 , 。初始化 。 。, 。初始化 。 。, 。初始化 。 。 循环遍历 j!=m j=m 跳出一个,k+1 , 。初始化 。 。 , 。初始化 。 。 , 。初始化 。 。 I=n , 。初始化 。 。 图2.2 2.3单词检查 ,b)),输出:x is correct,X代表需要检查的单词,直到把词库单词遍历完;然后再重新遍历一次,比较两个单词的长度,词库单词比需要检查的单词多一位时:去遍历两个单词的每一个字符,如果词库单词前面每一个字符都和X的每一个字符相等,则输出X:X1 X2 X3…;词库单词比需要检查的单词少一位时:去遍历两个单词的每一个字符,如果X前面每一个字符都和词库单词的每一个字符相等,则输出X:X1 X2 X3…;词库单词和X的字符个数相同时:去遍历两个单词的每一个字符,如果词库单词前面每一个字符都和X的每一个字符相等,则输出X:X1 X2 X3…;每个单词以空格隔开;如果没有以上几种情况,则直接输出X:即可。 2)主要代码: [k][0]!='#') ( /strlen是一个计数器,到字符串末尾结束,判断从开始计数到末尾的字符个数 c[k]=strlen(a[k]); nf("%s",a[++k][0]); ) nf("%s",b[0]); [0]!='#') ( len=strlen(b);/输入单词的长度 nf("%s",b); /cout< /cout< X is correct or(i=0;i { /strcmp比较两个字符串,如果相等返回0 c[i]==len strcmp(a[i],b)==0) { c[i]; out<<<" is correct"< k; ) } if(i==k) ( /cout< /cout< out<<<":"; or(i=0;i { (Find(i,len)==true) [i]; ) out< } nf("%s",b); } /单词相似的方法 ind(int n,int m) ( int i,j; c[n]-m; /cout< /需要检查的单词比词典里的少一位 if(j==1) { [n][i]==b[i];i++); [n][i+1]==b[i];i++); [n][i]<< /cout<<< [n][i+1]<< if(i==m)return true; ) /需要检查的单词和词典里的长度相同 if(j==0) ( [n][i]==b[i];i++); [n][i]==b[i];i++); if(i==m)return true; ) /需要检查的单词比词典里的多一位 if(j==-1) ( c[n] a[n][i]==b[i];i++); c[n] a[n][i]==b[i+1];i++); c[n])return true; ) lse; } X代表需检查单词,Y代表词库单词 , 。初始化 。 。 , 。初始化 。 。 , 。初始化 。 。 , 。初始化 。 。, 。初始化 。 。 , 。初始化 。 。 , 。初始化 。 。, 。初始化 。 。, 。初始化 。 。 X-Y=-1 X-Y=0 X-Y=1 X=Y , 。初始化 。 。 6总结 QT学习以及上学期的C++学习,深刻的了解到设计程序并不是一件简单的事情。并且通过网上了解到QT的强大功能,虽然现在本人的技术及知识还很贫乏,但是相信通过现在及日后的学习一定可以达到自己想要达到的水平。 ++程序语言设计》和《高级程序设计》课程学习的内容,掌握工程软件设计的基本方法,强化上机动手编程能力,体验理论与实践相结合的过程,最后感谢周老师的悉心指导。 7参考文献 [1] 邹思轶.嵌入式 Linux 设计与应用[M].北京:清华大学出版社,2002:318-325. [2]闫锋欣,曾泉人.C++ GUI QT4编程(第二版)[M].北京:电子工业出版社,2010:108-232. [3] 闫放莺.基于嵌入式 Linux 软件平台技术的研究[D].西安:西北大学,2006. [4] 谭浩强.C++面向对象程序设计[M].北京:清华大学出版社,2006.69-111. 附录 QMessageBox> QHeaderView> QScrollBar> QImageReader> include "ImageViewer.h" ImageViewer::ImageViewer(QWidget *parent) QMainWindow(parent), scaleFactor(1) ( upUi(this); geLabel = new QLabel; geLabel->setBackgroundRole(QPalette::Base); geLabel->setSizePolicy(QSizePolicy::Ignored, QSizePolicy::Ignored); geLabel->setScaledContents(true); = new QScrollArea; rea->setBackgroundRole(QPalette::Dark); ; Model = new QDirModel(this); Model->setFilter(QDir::Dirs | QDir::Drives); urrent = new QDir(); geInfo = new QLabel(this); geInfo->setSizePolicy(QSizePolicy::Expanding,QSizePolicy::Expanding); geInfo->setAlignment(Qt::AlignCenter); geInfo->setStatusTip(tr("Display image infomation in the selected folder")); ar->addWidget(imageInfo); View->setModel(dirModel); View->header()->setVisible(false); View->setColumnHidden(1,true); / Size View->setColumnHidden(2,true); / Type View->setColumnHidden(3,true); / Modified Date resize(780,580); ile = displayFiles.constBegin(); UpdateUI(); ) ImageViewer::~ImageViewer() ( urr irCurrent; ) djustScrollBar(QScrollBar *scrollBar, double factor) ( ar->setValue(int(factor * scrollBar->value() ctor - 1) * scrollBar->pageStep()/2))); ) id ImageViewer::scaleImage(double factor) ( Q_ASSERT(imageLabel->pixmap()); leFactor *= factor; geLabel->resize(scaleFactor * imageLabel->pixmap()->size()); djustScrollBar(scrollArea->horizontalScrollBar(), factor); djustScrollBar(scrollArea->verticalScrollBar(), factor); ) id ImageViewer::DisplayImage(const QString fileName) ( QImage image(fileName); ge.isNull()) { QMessageBox::information(this, tr("Image Viewer"), annot load %1.").arg(fileName)); return; ) geLabel->setPixmap(QPixmap::fromImage(image)); leImage(1.0); } id ImageViewer::UpdateUI() ( ctionZoomIn->setEnabled(scaleFactor < 3.0); ctionZoomOut->setEnabled(scaleFactor > 0.333); ) id ImageViewer::on_actionNext_triggered() ( ile++; (currentFile == displayFiles.constEnd()) ile = displayFiles.constBegin(); isplayImage(dirCurrent->absoluteFilePath(*currentFile)); UpdateUI(); ) id ImageViewer::on_actionPrevious_triggered() { (currentFile == displayFiles.constBegin()) ile = displayFiles.constEnd();

重庆科技学院

《数据结构》课程设计

专业班级: 计科2012级3班

学 号: 2012442084

姓 名: 赵弈胰

成 绩:

⏺

摘要

设计一些简单的程序,来实现屏幕输出,约瑟夫问题,单词的拼写检查,非递减有序集合合并,括号匹配,排队优化,快速排序^[1]等功能。我们首先应该想到设计需要的知识点,比如:链表^[2]、数组等方法,赋值运算、逻辑运算、括号运算等运算,还有循环等。

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。

关键字:数据结构、数组、链表、算法

目录

摘要 I

目录 II

1需求分析 1

1.1功能需求^[3] 1

1.2系统运行环境 2

2开发环境 2

2.1 QT简介 2

2.2开发环境搭建 3

2.1.1安装g++ 3

2.1.2安装QT5.0 3

3总体设计 4

3.1简要说明 4

currentFile--;

DisplayImage(dirCurrent->absoluteFilePath(*currentFile));

UpdateUI();

}

void ImageViewer::on_actionZoomOut_triggered()

{

scaleImage(0.8);

UpdateUI();

}

void ImageViewer::on_actionZoomIn_triggered()

{

scaleImage(1.25);

UpdateUI();

}

void ImageViewer::on_actionNormalSize_triggered()

{

scaleFactor = 1.0;

scaleImage(1.0);

UpdateUI();

}

void ImageViewer::on_treeView_clicked ( const QModelIndex index )

{

const QString path = dirModel->data(index, QDirModel::FilePathRole).toString();

dirCurrent->setPath(path);

displayFiles = dirCurrent->entryList(supportFormat, QDir::Files);

currentFile = displayFiles.constBegin();

if(currentFile != displayFiles.constEnd())

DisplayImage(dirCurrent->absoluteFilePath(*currentFile));

UpdateUI();

}

const char *htmlAboutText =

""

"

This program is subject to GPL license.

"

"

Writed by Eric Guo

"

"

https://ericguo.cnblogs.com/

"

"";

void ImageViewer::on_actionAbout_triggered()

{

QMessageBox::about(this, tr("About Qt Mini Image Viewer"), htmlAboutText);

}

3.2总体程序框图 4

4详细设计^[4] 5

4.1界面设计 5

4.2函数代码实现 5

5功能测试 8

5.1下一张 8

5.2上一张 9

5.3放大 9

5.4缩小 10

6总结 11

7参考文献 12

附录 13

⏺

1需求分析

1.1功能需求

1)编写一个程序,从键盘输入整数n, 在屏幕上输出1~n之间的所有整数,每个数字之间保留3个空格。

2)有n只猴子,按顺时针方向围成一圈选大王(编号从1到n),从第1号开始报数,一直数到m,数到m的猴子退出圈外,剩下的猴子再接着从1开始报数。就这样,直到圈内只剩下一只猴子时,这个猴子就是猴王,编程求输入n,m后,输出最后猴王的编号。

3)现在有一些英语单词需要做拼写检查,你的工具是一本词典。需要检查的单词,有的是词典中的单词,有的与词典中的单词相似,你的任务是发现这两种情况。单词A与单词B相似的情况有三种:

A. 删除单词A的一个字母后得到单词B;
B. 用任意一个字母替换单词A的一个字母后得到单词B;
C. 在单词A的任意位置增加一个字母后得到单词B。
D. 你的任务是发现词典中与给定单词相同或相似的单词。
E. LA和线性表^[5]LB中的数据元素按值非递减有序排列,现要求将LA和LB归并为一个新的线性表LC,且LC中的元素仍按值非递减有序排列。
F. [{}])或({[][()]})等均为正确的格式,而{[]})}或{[()]或([]}均为不正确的格式.
G. xtra right brackets 如果输入的左括号多余, 输出:Extra left brackets 如果输入的括号不匹配,输出:Brackets not match 如果输入的括号匹配,输出:Brackets match 6)设某银行有A、B两个业务窗口,且处理业务的速度不一样,其中A窗口处理速度是B窗口的2倍---即当A窗口处理完2个顾客时,B窗口处理完一个顾客。给定到达银行的顾客序列,请按业务完成的顺序输出顾客序列。假定不考虑顾客先后到达的时间间隔,并且当不同窗口同时处理完2个顾客时,A窗口顾客优先输出。
A. R. Hoare想出了一种很快的排序方法,由于它的确很快,于是我们就叫它快速排序。快速排序的原理其实很简单。假设我们需要将一些待排序的数从小到大排序。首先,我们从这些数中随便找一个数(key),然后把比它小的放到它的左边,比它大的放到它的右边,这样它左边的任意一个数都比右边的任意一个数小,我们把这个操作叫做“划分”。这时候我们再递归调用^[6]快排函数,将key的左边、右边都排好,整个集合的数字就有序了。
1.2环境需求
VC++6.0编辑器
PC机一台
2详细设计
2.1屏幕输出题
1)程序说明:这个程序主要就是运用循环来输出数字
2)主要代码:
nf("%d",n);
or(int i=1; i<=n; i++) {
printf("%d ",i);
}
3)程序流程图,


Y N 程序结束

图2.1
2.2约瑟夫问题
K代表被叫出去的人数,每次加1;喊道最后一个时,接着第一个数数,如此循环,直到还剩一个时结果输出。
2)主要代码:
or(i=1; i<=n; i++)
{
[i]=1;
}
or(i=1; i<=n; i++)
{
[i]==1)
{
[i];
\n",j);
if(j==m)
{
\n",i);
j=0;
[i] = 0;
k++;
}
if(k==n)
{
\n",i);
k;
}
}
3)程序流程图:




循环遍历 j!=m j=m 跳出一个,k+1



I=n

图2.2
2.3单词检查
,b)),输出:x is correct,X代表需要检查的单词,直到把词库单词遍历完;然后再重新遍历一次,比较两个单词的长度,词库单词比需要检查的单词多一位时:去遍历两个单词的每一个字符,如果词库单词前面每一个字符都和X的每一个字符相等,则输出X:X1 X2 X3…;词库单词比需要检查的单词少一位时:去遍历两个单词的每一个字符,如果X前面每一个字符都和词库单词的每一个字符相等,则输出X:X1 X2 X3…;词库单词和X的字符个数相同时:去遍历两个单词的每一个字符,如果词库单词前面每一个字符都和X的每一个字符相等,则输出X:X1 X2 X3…;每个单词以空格隔开;如果没有以上几种情况,则直接输出X:即可。
2)主要代码:
[k][0]!='#')
{
//strlen是一个计数器,到字符串末尾结束,判断从开始计数到末尾的字符个数
c[k]=strlen(a[k]);
nf("%s",a[++k][0]);
}
nf("%s",b[0]);
[0]!='#')
{
len=strlen(b);//输入单词的长度
nf("%s",b);
//cout<
//cout<
X is correct
or(i=0;i
{
//strcmp比较两个字符串,如果相等返回0
c[i]==len strcmp(a[i],b)==0)
{
c[i];
out<<<" is correct"<
k;
}
}
if(i==k)
{
//cout<
//cout<
out<<<":";
or(i=0;i
{
(Find(i,len)==true)
[i];
}
out<
}
nf("%s",b);
}
//单词相似的方法
ind(int n,int m)
{
int i,j;
c[n]-m;
//cout<
//需要检查的单词比词典里的少一位
if(j==1)
{
[n][i]==b[i];i++);
[n][i+1]==b[i];i++);
[n][i]<<
//cout<<<
[n][i+1]<<
if(i==m)return true;
}
//需要检查的单词和词典里的长度相同
if(j==0)
{
[n][i]==b[i];i++);
[n][i]==b[i];i++);
if(i==m)return true;
}
//需要检查的单词比词典里的多一位
if(j==-1)
{
c[n] a[n][i]==b[i];i++);
c[n] a[n][i]==b[i+1];i++);
c[n])return true;
}
lse;
}
X代表需检查单词,Y代表词库单词






X-Y=-1 X-Y=0 X-Y=1 X=Y

6总结
QT学习以及上学期的C++学习,深刻的了解到设计程序并不是一件简单的事情。并且通过网上了解到QT的强大功能,虽然现在本人的技术及知识还很贫乏,但是相信通过现在及日后的学习一定可以达到自己想要达到的水平。 
++程序语言设计》和《高级程序设计》课程学习的内容,掌握工程软件设计的基本方法,强化上机动手编程能力,体验理论与实践相结合的过程,最后感谢周老师的悉心指导。
7参考文献
[1] 邹思轶.嵌入式 Linux 设计与应用[M].北京:清华大学出版社,2002:318-325. 
[2]闫锋欣,曾泉人.C++ GUI QT4编程(第二版)[M].北京:电子工业出版社,2010:108-232. 
[3] 闫放莺.基于嵌入式 Linux 软件平台技术的研究[D].西安:西北大学,2006. 
[4] 谭浩强.C++面向对象程序设计[M].北京:清华大学出版社,2006.69-111.
附录
QMessageBox>
QHeaderView>
QScrollBar>
QImageReader>
include "ImageViewer.h"
ImageViewer::ImageViewer(QWidget *parent)
QMainWindow(parent), scaleFactor(1)
{
upUi(this);
geLabel = new QLabel;
geLabel->setBackgroundRole(QPalette::Base);
geLabel->setSizePolicy(QSizePolicy::Ignored, QSizePolicy::Ignored);
geLabel->setScaledContents(true);
= new QScrollArea;
rea->setBackgroundRole(QPalette::Dark);
;
Model = new QDirModel(this);
Model->setFilter(QDir::Dirs | QDir::Drives);
urrent = new QDir();
geInfo = new QLabel(this);
geInfo->setSizePolicy(QSizePolicy::Expanding,QSizePolicy::Expanding);
geInfo->setAlignment(Qt::AlignCenter);
geInfo->setStatusTip(tr("Display image infomation in the selected folder"));
ar->addWidget(imageInfo);
View->setModel(dirModel);
View->header()->setVisible(false);
View->setColumnHidden(1,true); // Size
View->setColumnHidden(2,true); // Type
View->setColumnHidden(3,true); // Modified Date
resize(780,580);
ile = displayFiles.constBegin();
UpdateUI();
}
ImageViewer::~ImageViewer()
{
urr
irCurrent;
}
djustScrollBar(QScrollBar *scrollBar, double factor)
{
ar->setValue(int(factor * scrollBar->value()
ctor - 1) * scrollBar->pageStep()/2)));
}
id ImageViewer::scaleImage(double factor)
{
Q_ASSERT(imageLabel->pixmap());
leFactor *= factor;
geLabel->resize(scaleFactor * imageLabel->pixmap()->size());
djustScrollBar(scrollArea->horizontalScrollBar(), factor);
djustScrollBar(scrollArea->verticalScrollBar(), factor);
}
id ImageViewer::DisplayImage(const QString fileName)
{
QImage image(fileName);
ge.isNull()) {
QMessageBox::information(this, tr("Image Viewer"),
annot load %1.").arg(fileName));
return;
}
geLabel->setPixmap(QPixmap::fromImage(image));
leImage(1.0);
}
id ImageViewer::UpdateUI()
{
ctionZoomIn->setEnabled(scaleFactor < 3.0);
ctionZoomOut->setEnabled(scaleFactor > 0.333);
}
id ImageViewer::on_actionNext_triggered()
{
ile++;
(currentFile == displayFiles.constEnd())
ile = displayFiles.constBegin();
isplayImage(dirCurrent->absoluteFilePath(*currentFile));
UpdateUI();
}
id ImageViewer::on_actionPrevious_triggered()
{
(currentFile == displayFiles.constBegin())
ile = displayFiles.constEnd();