数据结构课设

课程设计(论文)任务书

信息 学 院 专 业 班

一、课程设计(论文)题目 栈和队列的应用、 敢死队问题 二、 课程设计(论文)工作自 年月 日起至 年 月 日止。

三、课程设计(论文) 地点: 四、课程设计(论文)内容要求： 1．本课程设计的目的

1、 使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结 构、存储结构和操作实现算法，以及它们在程序中的使用方法。

2、了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计 能力；使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设 计的基本能力。初步掌握软件开发过程的问题分析、系统设计、程序编码、测 试等基本方法和技能；

3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 2．课程设计的任务及要求 1）基本要求：

1. 分析题目，查阅相关资料； 2. 算法设计、数据结构设计； 3. 编写代码并调试； 4. 完成课程设计报告。 2）创新要求：

在基本要求达到后，可进行创新设计。 3）课程设计论文编写要求

（1）要按照书稿的规格打印誊写论文

（2）论文包括目录、绪论、正文、小结、参考文献、谢辞、附录等 （3）课程设计论文装订按学校的统一要求完成 4）答辩与评分标准：

（1）完成问题的解决方法分析：20分； （2）算法思想（流程）：20分； （3）数据结构：20分；

- 1 -

（4）测试数据：20分 （5）回答问题：20分。

5）参考文献：

《C程序设计》（第二版） 谭浩强 著 清华大学出版社出版 《C++程序设计》 谭浩强 著 清华大学出版社出版 《数据结构》（C语言版） 严蔚敏、吴伟民 著 清华大学出版社出版

6）课程设计进度安排

内容 天数 地点 构思及收集资料 图书馆 编程与调试 实验室

撰写论文

学生签名： 2011年 12 月 19 日

课程设计(论文)评审意见

（1）完成问题分析（20分）：优（ ）、良（ ）、中（ ）、一般（ ）、差（ ）； （2）算法思想 （20分）：优（ ）、良（ ）、中（ ）、一般（ ）、差（ ）； （3）数据结构 （20分）：优（ ）、良（ ）、中（ ）、一般（ ）、差（ ）； （4）测试数据 （20分）：优（ ）、良（ ）、中（ ）、一般（ ）、差（ ）； （5）回答问题 （20分）：优（ ）、良（ ）、中（ ）、一般（ ）、差（ ）； （6）格式规范性及考勤是否降等级：是（√）、否（ ）

评阅人： 职称：

2012年1 月3 日

- 2 -

目录

课程设计目的????????????????4课程设计内容????????????????5程序截图??????????????????7程序清单??????????????????12测试数据??????????????????32课程设计总结????????????????33

- 3 -

课程设计目的

1、 使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻

辑结

构、存储结构和操作实现算法，以及它们在程序中的使用方法。 2、使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化

软件设计的能力。

3、使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序

设计的基本能力。

- 4 -

课程设计内容

1、课程设计的题目及简介 栈和队列其应用

目的在于使读者深入了解栈和队列的特性，以便在实际问题背景下灵活运用他们；同时还将巩固对这两种结构的构造方法的掌握，接触较复杂问题的递归算法设计。（最少选择4个） （1）：算术表达式转波兰表达式和逆波兰表达式 （2）：栈列操作的验证（建栈、入栈、出栈、销毁栈） （3）：判断表达式中括弧是否正确配对 （4）：队列元素倒置 （5）：判断字符串是否回文

（6）：字符串的基本操作（5个基本函数实现） 敢死队问题

有M个敢死队员要炸掉敌人的一碉堡，谁都不想去，排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务，则要再派一个战士上去。现给每个战士编一个号，大家围坐成一圈，随便从某一个战士开始计数，当数到5时，对应的战士就去执行任务，且此战士不再参加下一轮计数。如果此战士没完成任务，再从下一个战士开始数数，被数到第5时，此战士接着去执行任务。以此类推，直到任务完成为止。

排长是不愿意去的，假设排长为1号，请你设计一程序，求出从

- 5 -

第几号战士开始计数才能让排长最后一个留下来而不去执行任务。

要求：至少采用两种不同的数据结构的方法实现。如果采用三种以上的方法者，可加分。 2、设计说明

（一）对于第一个问题栈和队列及应用分为四个文件，分别是： 1234.cpp HQueue.h HStack.h HString.h

其中第一个是CPP文件，包含的运行程序的界面函数和主函数。 其余三个是ADT头文件，分别包含队列、栈、串的ADT函数。 该程序可实现以下功能：

（1）：栈列操作的验证（建栈、入栈、出栈、销毁栈） （2）：判断表达式中括弧是否正确配对 （3）：队列元素倒置 （4）：判断字符串是否回文

（5）：字符串的基本操作（5个基本函数实现）

（二）对于第二个问题敢死队问题，分为两个程序，分别以单向列表和循环队列的数据结构方法解决敢死队问题。

- 6 -

程序截图

（一）栈和队列及应用

该图已删除。。。 图0-1主界面

图0-2主界面输入错误

栈列操作的验证第一步 建栈

栈列操作的验证第二步 入栈和出栈

- 7 -

栈列操作的验证第三步 销毁栈

图1-2-1判断括弧是否正确匹配中 括弧匹配

图1-2-2判断括弧是否正确匹配中 左括弧多余

图1-2-3判断括弧是否正确匹配中 右括弧多余

图1-3-1判断回文中 字符串是回文

图1-3-2判断回文中 字符串不是回文

- 8 -

图1-4-1字符串的基本操作中 创建字符串、比较字符串和合并字符串

图1-4-2字符串的基本操作中 求子串

图1-4-3 字符串的基本操作中 字符串比较串1小于串2

- 9 -

图1-4-4字符串的基本操作中 字符串比较串1大于串2

注：串1等于串2出现在图1-4-1

图1-5队列元素倒置功能

（二）敢死队问题 ①单向链表方法

- 10 -

图2

②循环队列

图3

程序清单

- 11 -

（一）栈和队列及应用

①1234.cpp

#define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -1 #define MAX 100

#define STACK_INIT_SIZE 100 // 存储空间初始分配量 #define STACKINCREMENT 10 // 存储空间分配增量

#include #include #include #include #include

#include\ //栈的头文件 #include\ //队列头文件 #include\ //串的头文件

//实现各功能所用的函数 void gongneng1() { SeqStack S;

InitStack( S ); char e; int a[ 100 ]; int i, n; char z, x;

printf(\创建栈\

printf(\请输入栈的长度n: \scanf(\

printf(\请输入栈的元素: \for( i = 0; i < n; i++ )

scanf(\a[i] = '\\0';

- 12 -

}

void gongneng2( char *str ) { SeqStack S;

InitStack( S ); char ch; int m=1;

printf(\请输入待检验括号并以'#'作为结束符: \getchar();

for( int i = 0; ( str[ i ] = getchar() ) != '#'; i++ ) {

switch( str[ i ] ) i = 0;

while( a[ i ] != '\\0' ) { }

printf(\你输入的栈的元素为: \for( i=0; i

printf(\ \printf(\入栈\

printf(\请输入需要入栈的元素: \scanf(\Push( S, x ); StackTraverse( S );

printf(\栈的长度为:%d\printf(\得到栈顶元素\

printf(\栈顶元素为: %d\printf(\退栈\Pop( S, x ); StackTraverse( S ); printf(\销毁栈\

printf(\您确定要销毁栈吗?[y/n]: \getchar(); z = getchar(); if( z=='y'||'Y') { }

DestoryStack( S ); printf(\栈已销毁!\\n\Push( S, a[ i ] ); i++;

printf(\栈的长度\

- 13 -

}

int panduanhuiwen() { //判断回文

SeqStack S; LinkQueue Q; InitStack( S ); } if(m)

if( StackEmpty( S ) ) { }

{ printf(\左括号多余!请检查(、[或{是否有误\\n\}

printf(\括号匹配!\\n\{ case '{': case '[': case '(':

Push( S, str[ i ] ); break;

case '}': case ']': case ')': }

if( StackEmpty( S ) ) { } else { }

GetTop( S, ch );

if( strcmp( &ch, &str[ i ] ) ) { } else { }

printf(\左右括号不匹配!\\n\m=0; Pop( S, ch );

printf(\右边括号多余!请检查)、]或}是否有误\\n\m=0;

else

- 14 -

InitQueue( Q ); char c; DataType a, b; getchar();

while( ( c = getchar() ) != '#' ) { Push( S, c ); //入栈 EnQueue( Q, c ); //入队

}

while( S.top != S.base ) //当栈不为空时 { Pop( S, a ); //将a入栈 DeQueue( Q, b ); //将b出队 if( a != b ) //当a不等于b时，

return 0;

} return 1;

}

void gongneng3() { //实现判断回文功能 printf(\

printf(\你将实现“判断回文”的功能！\

printf(\请输入需要判断的字符串并以 # 作为结束符: if(panduanhuiwen() == 1 ) { printf(\该字符串是回文!\\n\ } else { printf(\该字符串不是回文!\\n\ }

}

void gongneng4() { //串的基本操作 HString T, s1, s2, Sub; char str[ 100 ]; int len, pos, n;

printf(\您选择了实现串的基本功能!\ InitString( s1 );

printf(\初始化完毕！\

printf(\创建字符串\ - 15 -

\

{ //生成一个其值等于串常量chars的串S }

Status StrLength( HString S, int &len ) { //求串的长度 }

Status StrCompare( HString S, HString T ) { //串的比较 }

Status ClearString( HString &S ) { //将S清为空串 }

Status Concat( HString &T, HString S1, HString S2 ) { //用T返回由S1和S2连接而成的新串 - 26 -

if( S.ch )

free( S.ch ); S.ch = NULL; S.length = 0; return TRUE; int i;

{ if( S.ch[ i ] != T.ch[ i ] ) }

return S.ch[ i ] - T.ch[ i ];

for( i = 0; i < S.length && i < T.length; i++ )

len = S.length; return len; int i = 0, j; i = strlen(chars);

S.ch = ( char* )malloc(i * sizeof(char)); for( j = 0; j < i; j++ ) { } S.length=i; S.ch[i] = '\\0'; return OK;

S.ch[ j ] = chars[ j ];

return S.length - T.length;

int i,j;

T.ch = ( char* )malloc( ( S1.length + S2.length )*sizeof( char ) ); if( !T.ch ) }

Status SubString( HString &Sub, HString S, int pos, int len ) { //用Sub返回串S的第pos个字符起长度为len的子串 }

- 27 -

if( pos < 1 || pos > S.length || len < 0 || len > S.length - pos + 1 ) { } else

{ //完整字串 } return OK;

Sub.ch = ( char* )malloc( len * sizeof( char ) ); if( !Sub.ch )

exit( OVERFLOW ); //分配存储空间失败 Sub.ch[ i ] = S.ch[ pos - 1 + i ]; for( i = 0; i <= len -1; i++ ) Sub.length = len; return ERROR; free( Sub.ch ); Sub.ch= NULL; Sub.length = 0; if( Sub.ch ) //释放旧空间 if( !len ) //空子串 { }

{ T.ch[ i ]=S2.ch[ j ]; }

T.length = S1.length + S2.length; printf(\return OK;

exit( OVERFLOW ); T.ch[ i ]=S1.ch[ i ];

for( i = 0; i < S1.length; i++ )

for( i = S1.length, j = 0; j < S2.length; j++, i++ )

T.ch[ i ] = '\\0';

（二）敢死队问题

①单向链表方法

#include

using namespace std; typedef struct node {

void main() {

cout<<\欢迎使用本程序解决敢死队问题\

cout<<\本程序使用是的单向链表的数据结构类型!\int M; //士兵个数 int i; int start,count; lnode *L;

cout<<\初始化完成！\cout<<\请输入士兵总人数 :\

cin>>M; //输入士兵个数 for(start=1;start<=M;start++) // start表示从哪个士兵开始数 { //初始化链表

lnode *p=new lnode; // 分配空间

L=p; // l为始终指向第一个节点的指针

L->num=1; // 第一个节点代表的士兵编号赋值为1，至此第一个节点创建完毕 for(i=2;i<=M-1;i++) {

lnode *q=new lnode; q->num=i;

p->next=q; // 创建其他节点，并将它接到链表尾部 p=q;

int num; node *next;

}lnode; // 定义一个结构体，num表示士兵的编号

}

lnode *t=new lnode; // 从这里开始创建最后一个节点 t->num=M; // 节点编号为M p->next=t; // 连上去 p=t;

- 28 -

}

}

cout<<\请从编号为 \的士兵处开始数数\cout<<\感谢使用本程序\\n\//t将从哪里开始的那个士兵编号输出来

t->next=L; // 并将最后一个节点与第一个节点相连，变成循环链表 //找到起点

p=L; // P指向第一个节点 for(i=1;i

p=p->next;

} //一个一个往下找，一直到找到编号为start的那个节点，从这里开始计数 while(count

for(i=1;i<5;i++) {

t=p; p=t->next;

count=0; //删除的节点的个数

} // 数到5就停下 t->next=p->next; // 将该节点删除 count++; //删除结点的个数加1 p=t->next; // 从下一个节点开始继续数

} //当删除的节点为M-1个时，就结束 if(p->num==1)

break;

//此时表里面应该只有一个节点了，判断节点的编号是不是等于1，也就是是不

是代表排长 ，如果是就结束循环

②循环队列方法

#include using namespace std;

#define QueueSize 100 //假定预分配的队列空间最多为100个元素

typedef struct {

int data[QueueSize];

int front; //代表数组存放的第一个数据对应的下标，队头 int rear; //代表数组存放的最后一个数据对应的下标，队尾 int count; //计数器，记录队中元素总数

- 29 -

}CirQueue;

void InitQueue(CirQueue *Q); int QueueEmpty(CirQueue *Q); int QueueFull(CirQueue *Q); void EnQueue(CirQueue *Q,int x); int DeQueue(CirQueue *Q);

// 初始化队 令队为空 void InitQueue(CirQueue *Q)

{ Q->front=Q->rear=0; // 对头等于对尾代表队列为空 }

// 判断队列是否为空 int QueueEmpty(CirQueue *Q) { }

//判断队列是否满

int QueueFull(CirQueue *Q) { }

//将元素进队

void EnQueue(CirQueue *Q,int x) { }

//元素出队列

int DeQueue(CirQueue *Q)

- 30 -

if (QueueFull(Q)) {

printf(\对不起列满 无法操作\\n\ exit(1);

if(Q->count==QueueSize) return 1; else return 0;

if(Q->count==0) return 1; //如果队里的元素个数为0，队列空，返回1 else return 0; Q->count=0;

}//如果堆满就退出程序

Q->count ++; // 否则就进入，元素总数加一 Q->data[Q->rear]=x; // 数组的最后一位赋值为x Q->rear=(Q->rear+1)%QueueSize;

{ }

void main() {

cout<<\欢迎使用本程序解决敢死队问题\

cout<<\本程序使用的是循环队列的数据结构类型!\int M,i,start,count,j; CirQueue s;

cout<<\初始化完成！\cout<<\请输入士兵总人数 :\ cin>>M;

for(start=1;start<=M;start++) //start为测试起点 {

InitQueue(&s); for(i=1;i<=M;i++) {

EnQueue(&s,i);

} //将所有士兵的编号依次进队 for(i=1;i

j=DeQueue(&s); EnQueue(&s,j);

int temp;

if(QueueEmpty(Q)) { }

temp=Q->data[Q->front]; // 将队头的元素取出到temp里面 Q->count--; //队列元素个数减1

Q->front=(Q->front+1)%QueueSize; //循环意义下的头指针后移 return temp;

printf(\队列为空\\n\下溢,退出运行 exit(1);

}

count=0; //删除结点数 while(count

for(i=1;i<5;i++) { }

j=DeQueue(&s); count++;

j=DeQueue(&s); EnQueue(&s,j);

- 31 -

}

}

cout<<\请从编号为 \的士兵处开始数数\cout<<\感谢使用本程序\\n\

}

if(s.data[s.front]==1)

break; //此时队只剩一个点，如果是排长就输出

测试数据

（一）栈和队列及应用 1.栈元素：1,2,3,4,5,7. 2.字符串：a,b,c,d,e,f,g,h,i,j,k. （二）敢死队问题 3.士兵人数：99.

- 32 -

课程设计总结

经过本次的数据结构课程设计，我可以说是获益匪浅。学习程序设计是一个非常需要实践的过程，这一次的课程设计正是给了我机会。通过设计的题目，我不但巩固了平时所学，更学到了平时没有注意到的一些技巧。这一次课程设计中我的基础题和综合应用题选的都是栈与队列的相关应用，这说明我对其他知识的把握还没有到位。我明白，在程序设计的道路上，我才刚刚起步，我所知道的不过是九牛一毛。学海无涯，我要更加的努力。

参考文献

《C程序设计》（第二版） 潭浩强 著 清华大学出版社出版

《C++程序设计》 潭浩强 著 清华大学出版社出版

《数据结构》（C语言版） 严蔚敏、吴伟民 著 清华大学出版社出版

PS:仅供参考，全抄遭雷劈啊亲！

- 33 -

本文来源：https://www.bwwdw.com/article/05cx.html