数据结构算法设计与实现指导(C语言版)
第3章栈——实验三
3.1 实验目的及要求
1．理解特殊的线性结构——顺序栈的抽象数据类型的定义，及其在C语言环境中的表示方法。
2．理解顺序栈的基本操作的算法，及其在C语言环境中一些主要基本操作的实现。
3．在C语言环境下实现顺序栈的应用操作：
①利用栈实现十进制数转换成八进制数。
②利用栈实现一位数的加减乘除的表达式求解。
3.2 实验内容
经过对实验目的及要求的分析，本实验仍然采用首先描述栈的基本操作集函数，然后分别在两个应用操作中使用基本操作集函数来实现。
由于栈是一种特殊的线性结构，仅在栈顶进行插入和删除操作，即栈具有后进先出的特点，故其操作比一般的线性表更为容易，所以在本实验中有关栈的基本操作集的实现都比较简单，没有做过多的说明，而是在数制转换和表达式求解的应用操作中加入了更多的编程技巧，使读者通过本实验不仅了解栈这种特殊结构的线性表，而且掌握利用栈可实现很多的应用，尤其是在实现表达式求解时用到了两个顺序栈，并且加入了运算符的优先关系的判断等，实现稍有难度。
在程序Stack.c中，只包含了数制转换和一位数的表达式求解，多位数的表达式求解思想与一位数表达式求解思想一致，但需要添加多位数的接收处理，请读者自行编写代码。
程序名为：Stack.c。
在Stack.c中包含的函数如图3.1所示。
数据结构算法设计与实现指导（C语言版）
28
图3.1 Stack.c中包含的函数一览表
3.3 功能函数的分析设计及源代码
本部分列出了实现顺序栈的操作的源代码，并在适当的位置上添加了一些文字和流程图的注释，帮助读者理解顺序存储的栈的存储结构及操作算法。
文件名：Stack.c
#include "alloc.h"
#include "stdio.h"
#define STACK_INIT_SIZE 10
#define STACKINCREMENT 2
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int SElemType;
typedef int Status;
//定义顺序栈的结构
typedef struct SqStack
{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
//初始化一个空栈
Status InitStack(SqStack *S)
{
(*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!(*S).base)
exit(OVERFLOW);
第3章栈——实验三
29
(*S).top=(*S).base;
(*S).stacksize=STACK_INIT_SIZE;
return OK;
}
//数据元素入栈
Status Push(SqStack *S,SElemType e)
{
if((*S).top-(*S).base>=(*S).stacksize)
{
(*S).base=(SElemType*)realloc((*S).base, ((*S).stacksize+STACKINCREMENT)
*sizeof(SElemType));
if(!(*S).base)
exit(OVERFLOW);
(*S).top=(*S).base+(*S).stacksize;
(*S).stacksize+=STACKINCREMENT;
}
*((*S).top)++=e;
return OK;
}
//数据元素出栈
Status Pop(SqStack *S,SElemType *e)
{
if((*S).top==(*S).base)
return ERROR;
*e=*--(*S).top;
return OK;
}
//判断一个栈是否为空
Status StackEmpty(SqStack S)
{
if(S.top==S.base)
return TRUE;
else
return FALSE;
}
//销毁一个栈
Status DestroyStack(SqStack *S)
{
free((*S).base);
(*S).base=NULL;
(*S).top=NULL;
(*S).stacksize=0;
return OK;
}
//十进制数转换成八进制
本函数实现了无符号十进制数和八进制数间的转换功能。
如输入的是负数，由于系统使用补码表示负数，会自动将其进行补码转换，再通过本
数据结构算法设计与实现指导（C语言版）
30
函数对其实现八进制转换。如，当输入－1时，结果显示65535。
如果需要将十进制转换成十六进制应该如何修改本函数？方法有两种，第一种，在入栈时，存入十六进制数；第二种，在出栈时，输出十六进制数。请读者自己编写代码。
void conversion()
{
SqStack s;
unsigned n;
SElemType e;
InitStack(&s);
printf("Please input a decimal number:");
scanf("%u",&n);
while(n)
{
Push(&s,n%8);
n=n/8;
}
printf("The corresponding octal number is:");
while(!StackEmpty(s))
{
Pop(&s,&e);
printf("%d",e);
}
printf("\n");
DestroyStack(&s);
}
//取栈顶的数据元素
Status GetTop(SqStack S,SElemType *e)
{
if(S.top>S.base)
{
*e=*(S.top-1);
return OK;
}
else
return ERROR;
}
//按照四则运算法则定义的运算符（包括：＋、－、*、/、（）、＃）运算的优先关系，即按照表3.1
//判断输入的运算符与运算符栈中的运算符的优先关系
表3.1的运算符间的优先关系是按照四则运算法则定义的，也就是本函数的运行结果。
如果读者希望在运算中再加入其他运算符（如乘方等），则必须先定义它们的关系，丰富表
3.1的内容，同时在函数中添加所加入的运算符的比较内容。其中θ1为栈顶元素，θ2为输
入元素。定义“#”运算符为输入表达式时的结束符及存放运算符的栈的栈底元素。
本函数不包含任何数据结构的内容，仅是在输入表达式的过程中，按照表3.1判断运算符栈的栈顶元素与输入的运算符的关系（＜、＞、＝）。因一个表达式包含多个运算符，故将此部分作为一个独立的函数进行编写。
第3章栈——实验三
31
表3.1 运算符间的优先关系
SElemType Precede(SElemType t1,SElemType t2)
{
SElemType f;
switch(t2)
{
case '+':
case '-':if(t1=='('||t1=='#')
f='<';
else
f='>';
break;
case '*':
case '/':if(t1=='*'||t1=='/'||t1==')')
f='>';
else
f='<';
break;
case '(':if(t1==')')
{
printf("Input Error\n");
exit(ERROR);
}
else
f='<';
break;
case ')':switch(t1)
{
case '(':f='=';
break;
case '#':printf("Input ERROR\n");
exit(ERROR);
default: f='>';
}
break;
case '#':switch(t1)
{
case '#':f='=';
break;
数据结构算法设计与实现指导（C语言版）
32
case '(':printf("Input Error\n");
exit(ERROR);
default: f='>';
}
}
return f;
}
//判断c是否为运算符（运算符包括：＋、－、*、/、（）、＃）
Status In(SElemType c)
{
switch(c)
{
case'+':
case'-':
case'*':
case'/':
case'(':
case')':
case'#':return TRUE;
default:return FALSE;
}
}
//计算a和b，返回运算结果
SElemType Operate(SElemType a,SElemType theta,SElemType b)
{
SElemType c;
switch(theta)
{
case'+':c=a+b;
break;
case'-':c=a-b;
break;
case'*':c=a*b;
break;
case'/':c=a/b;
}
return c;
}
//表达式求解
在栈的基本操作集中，主要就是入栈和出栈操作，而且栈的数据元素的特点是后进先出，表达式求解的应用正是利用栈的这个特性。
在对这个应用进行分析时，设计了中间函数，如算符优先级别判断，计算每次运算的结果等。
在这个函数中定义了两个栈，一个栈用来存放操作数，另一个栈用来存放运算符，由此又设计了对输入字符的判断函数。这样就使得表达式求解的函数更直观、简单、易理解。
该函数处理过程有一定难度，其流程图如图3.2所示。
第3章栈——实验三
33
图3.2 表达式求解的流程图
SElemType EvaluateExpression(SElemType *e)
{
SqStack OPTR,OPND;
SElemType a,b,c,x,theta;
InitStack(&OPTR); Push(&OPTR,'#');
InitStack(&OPND); c=getchar();
数据结构算法设计与实现指导（C语言版）
34
GetTop(OPTR,&x);
while(c!='#'||x!='#')
{
if(In(c))
switch(Precede(x,c))
{
case'<':Push(&OPTR,c);
c=getchar();
break;
case'=':Pop(&OPTR,&x);
c=getchar();
break;
case'>':Pop(&OPTR,&theta);
Pop(&OPND,&b);
Pop(&OPND,&a);
Push(&OPND,Operate(a,theta,b));
break;
}
else if(c>='0'&&c<='9')
{
Push(&OPND,c-48);
c=getchar();
}
else
{
printf("Input Error\n");
return ERROR;
}
GetTop(OPTR,&x);
}
GetTop(OPND,&x);
*e=x;
return OK;
}
//主函数
本实验实现两个功能，一是十进制转换成八进制，二是实现10以内个位数字的加、减、乘、除运算。
main()
{
char chs[256],ch;
SElemType e=0;
clrscr();
printf("\n1:Decimal-octal Conversion");
printf("\n2:Numeric Expression Evaluator");
printf("\n0:Exit\n");
printf("\ninput function select:");
gets(chs);
第3章栈——实验三
35
while (1)
{
if (strlen(chs)==1)
{
ch=chs[0];
switch (ch)
{
case '1':conversion();
break;
case '2':printf("Input expression ended by '#'.\n");
printf("(Notice: Operand should be 0-9):");
if(EvaluateExpression(&e))
printf("%d\n",e);
break;
case '0': return OK;
default: printf("\nBad input...\n");
}
}
else
{
printf("\nBad input...\n");
}
printf("\ncontinue input function select:");
fflush(stdin);
gets(chs);
}
}
3.4 习题
1．验证栈顺序存储时的基本操作集函数和利用基本操作集实现十进制和八进制转换、
一位数的加减乘除的表达式求解功能。
2．在主函数中编写代码实现十进制和八进制转换功能。
3．在主函数中编写代码实现一位数表达式求解功能。
数据结构和算法习题及答案解析
第1章绪论 习题 1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。 2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。 3．简述逻辑结构的四种基本关系并画出它们的关系图。 4．存储结构由哪两种基本的存储方法实现 5．选择题 （1）在数据结构中，从逻辑上可以把数据结构分成（）。 A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．内部结构和外部结构 （2）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。 A．存储结构 B．存储实现 C．逻辑结构 D．运算实现 （3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。 A．数据具有同一特点 B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等 （4）以下说法正确的是（）。 A．数据元素是数据的最小单位 B．数据项是数据的基本单位 C．数据结构是带有结构的各数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 （5）以下与数据的存储结构无关的术语是（）。 A．顺序队列 B. 链表 C.有序表 D. 链栈 （6）以下数据结构中，（）是非线性数据结构 A．树 B．字符串 C．队 D．栈 6．试分析下面各程序段的时间复杂度。 （1）x=90; y=100; while(y>0) if(x>100) {x=x-10;y--;} else x++; （2）for (i=0; i 《数据结构与算法设计》 实验报告 ——实验一 学院： 班级： 学号： 姓名： 一、实验目的 第一题利用单向环表实现约瑟夫环。 第二题归并顺序表。 二、实验内容 第一题采用单向环表实现约瑟夫环。 请按以下要求编程实现： ①从键盘输入整数m，通过create函数生成一个具有m个结点的单向环表。环表中的结点编号依次为1，2，……，m。 ②从键盘输入整数s（1<=s<=m）和n，从环表的第s个结点开始计数为1，当计数到第n个结点时，输出该第n结点对应的编号，将该结点从环表中消除，从输出结点的下一个结点开始重新计数到n，这样，不断进行计数，不断进行输出，直到输出了这个环表的全部结点为止。 例如，m=10，s=3，n=4。则输出序列为：6，10，4，9，5，2，1，3，8，7。 第二题选作：归并顺序表。 请按以下要求编程实现： ①从键盘输入两个升序排列的整数序列linka和linkb，每个序列以输入0为结束标记。 ②将链表linka和linkb归并为linkc，linkc仍然为升序排列。归并完成后，linka 和linkb为空表。输出linkc。 ③对linkc进行处理，保持升序不变，删除其中重复的整数，对重复的整数只保留一个，输出删除重复整数后的链表。 例如：linka输入为：10 20 30 40 50 0 linkb输入为：15 20 25 30 35 40 45 50 0 归并后的linkc为：10 15 20 20 25 30 30 35 40 40 45 50 50 删除重复后的linkc为：10 15 20 25 30 35 40 45 50 三、程序设计 1、概要设计 第一题为了实现程序功能，应当建立单向环表来寄存信息及结点，通过查找结 《数据结构》 Part1 一．选择 1. 组成数据的基本单位是（） A）数据项B）数据类型C）数据元素D）数据变量 2．算法分析的目的是（） A）找出数据结构的合理性B）研究算法的输入/输出关系 C）分析算法的效率以求改进D）分析算法的易读性 3．在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（）A）O(1) B）0(n) C）O(n^2) D）O(nlog2n) 4．若线性表采用顺序存储结构，每个元素占用4个存储单元，第一个元素的存储地址为100，则第12个元素的存储地址是（） A）112 B）144 C）148 D）412 5．下面关于线性表的叙述中，错误的是（） A）顺序表使用一维数组实现的线性表B）顺序表必须占用一片连续的存储单元. C）顺序表的空间利用率高于链表D）在单链表中,每个结点只有一个链域. 6．在需要经常查找结点的前驱与后继的情况下，使用（）比较合适 A）单链表B）双链表C）顺序表D）循环链表 7．队列通常采用的两种存储结构是（） A）顺序存储结构和链式存储结构B）散列方式和索引方式 C）链表存储结构和线性存储结构D）线性存储结构和非线性存储结构 8．在一个单链表中，若删除p所指结点的后继结点，则执行（） A）p->next=p->next->next；B）p=p->next；p->nex=p->next->next； C）p->next=p->next；D）p=p->next->next； 9．若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间 A）单链表B）仅有头指针的单循环链表C）双链表D）仅有尾指针的单循环链表 10．按二叉树的定义，具有三个结点的二元树共有（）种形态。 A）3 B）4 C）5 D）6 11．任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）A）发生改变B）不发生改变C）不能确定D）以上都不对12．深度为5的二叉树至多有（）个结点 A）16 B）32 C）31 D）10 13．在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，那么度为0的结点数为（）个。 A）4 B）5 C）6 D）7 14．对于一个具有n个顶点的无向图，若采用邻接表表示，则存放表头结点的数组(顶点表)的大小为（） A）n B）n+1 C）n-1 D）n/2 15．静态查找表和动态查找表二者的根本差别在于（） 数据结构与算法设计知识点 试题类型： 本课程为考试科目（闭卷笔试），试题类型包括：概念填空题（10 %），是非判断题（10 %），单项选择题（40 %），算法填空题（10%），算法应用题（20 %)，算法设计题（10 %）。 第一章绪论 重点内容及要求： 1、了解与数据结构相关的概念（集合、数据、数据元素、数据项、关键字、元 素之间的关系等）。 数据：所有能被输入到计算机中，且能被计算机处理的符号的 集合。是计算机操作的对象的总称。是计算机处理的信息的某种特定 的符号表示形式。 数据元素：是数据（集合）中的一个“个体”，数据结构中的基本 单位，在计算机程序中通常作为一个整体来考虑和处理。 数据项：是数据结构中讨论的最小单位，数据元素可以是一个或 多个数据项的组合 关键码：也叫关键字（Key），是数据元素中能起标识作用的数 据项。 其中能起到唯一标识作用的关键码称为主关键码（简称主码）； 否则称为次关键码。通常，一个数据元素只有一个主码，但可以有多 个次码。 关系：指一个数据集合中数据元素之间的某种相关性。 数据结构：带“结构”的数据元素的集合。这里的结构指元素之 间存在的关系。 数据类型：是一个值的集合和定义在此集合上的一组操作的总 称。 2、掌握数据结构的基本概念、数据的逻辑结构（四种）和物理结构（数据元素 的表示与关系的表示、两类存储结构：顺序存储结构和链式存储结构）。 数据结构包括逻辑结构和物理结构两个层次。 数据的逻辑结构：是对数据元素之间存在的逻辑关系的一种抽象的描述，可以用一个数据元素的集合和定义在此集合上的若干关系来表示 逻辑结构有四种：线性结构、树形结构、图状结构、集合结构数据的物理结构：是其逻辑结构在计算机中的表示或实现，因此又称其为存储结构。 存储结构：顺序存储结构和链式存储结构 顺序存储结构：利用数据元素在存储器中相对位置之间的某种特定的关系来表示数据元素之间的逻辑关系； 链式存储结构：除数据元素本身外，采用附加的“指针”表示数据元素之间的逻辑关系。 3、了解算法分析的基本方法，掌握算法时间复杂度相关的概念。 算法：是为了解决某类问题而规定的一个有限长的操作序列 或处理问题的策略 一个算法必须满足以下五个重要特性：1．有穷性2．确定性3．可行性4．有输入5．有输出 设计算法时，通常还应考虑满足以下目标： 1.正确性， 2.可读性， 3.健壮性 4.高效率与低存储量需求 算法设计题 1. 设二叉树bt采用二叉链表结构存储。试设计一个算法输出二叉树中所有非叶子结点，并求出非叶子结点的个数。 【答案】 int count=0; void algo2(BTNode *bt){ if (bt){ if(bt->lchild || bt->rchild){ printf(bt->data); count++; } algo2(bt->lchild); algo2(bt->rchild); } } 2. 阅读下列函数arrange() int arrange(int a[],int 1,int h,int x) {//1和h分别为数据区的下界和上界 int i,j,t； i=1；j=h； while(i 烟台大学计算机学院课程设计（算法与数据结构） 设计题目： 班级 姓名 学号 指导教师 成绩 二○一三年四月十日 内容包括： 一、课程设计题目： 二、课程设计内容： 三、算法设计： 四、程序正确性验证（指边界测试数据，即程序对于精心选择的典型、苛刻 而带有刁难性的几组输入数据能够得出满足要求的结果）： 五、课程设计过程中出现的主要问题、原因及解决方法： 六、课程设计的主要收获： 七、对今后课程设计的建议： 算法与数据结构课程设计题目 一、单项分值：25分 1、约瑟夫环游戏 2、八皇后问题(图形表示加20分) 3、表达式的求值问题 4、迷宫问题(图形表示加10分) 二、单项分值：80分 5、HTML文档标记匹配算法 要求：输入一段HTML代码，判断该代码是否符合HTML的语法 提示：HTML文档由不同的标记划分为不同的部分与层次。与括号类似，这些标记需要成对出现，对于名为 北方民族大学课程设 计 课程名称: 数据结构与算法 院(部)名称:信息与计算科学学院 组长姓名学号 同组人员姓名 指导教师姓名:纪峰 设计时间:2010.6.7----2009.6.27 一、《数据结构与算法》课程设计参考题目 （一）参考题目一（每位同学选作一个,同组人员不得重复） 1、编写函数实现顺序表的建立、查找、插入、删除运算。 2、编写函数分别实现单链表的建立、查找、插入、删除、逆置算法。 3、编写函数实现双向链表的建立、插入、删除算法。 4、编写函数实现顺序栈的进栈、退栈、取栈顶的算法。 5、编写函数实现链栈的进栈、退栈、取栈顶的算法。 6、编写函数实现双向顺序栈的判空、进栈、出栈算法。 7、编写函数实现循环队列的判队空、取队头元素、入队、出队算法。 8、编写函数实现链环队列的判队空、取队头节点、入队、出队算法。 9、编写函数实现串的，求串长、连接、求字串、插入、删除等运算。 10、分别实现顺序串和链串的模式匹配运算。 11、实现二叉树的建立，前序递归遍历和非递归遍历算法。 12、实现二叉树的建立，中序递归遍历和非递归遍历算法。 13、实现二叉树的建立，后序递归遍历和非递归遍历算法。 14、实现二叉树的中序线索化，查找*p结点中序下的前驱和后继结点。 15、分别以临接表和邻接矩阵作为存储就够实现图的深度优先搜索和广度优先搜索算法。 16、利用线性探测处理冲突的方法实现散列表的查找和插入算法。 (二)参考题目二（每三人一组，任选三个题目完成） 1.运动会分数统计（限1 人完成） 任务：参加运动会有n个学校，学校编号为1……n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1……m，女子m+1……m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m<=20,n<=20） 功能要求： 1)可以输入各个项目的前三名或前五名的成绩； 2)能统计各学校总分， 3)可以按学校编号或名称、学校总分、男女团体总分排序输出； 4)可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。 5)数据存入文件并能随时查询 6)规定：输入数据形式和范围：可以输入学校的名称，运动项目的名称 输出形式：有合理的提示，各学校分数为整形 界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。 存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。（数据文件的数据读写方法等相关内容在c语言程序设计的书上，请自学解决）请在最后的上交资料中指明你用到的存储结构； 内江师范学院 数据结构与算法设计课程设计实验报告册 编制算法设计课题组审定曾意 数学与信息科学学院 2014年9月 1. 学生在做实验之前必须要准备实验，主要包括预习与本次实验相关的理论知识，熟练与本次实验相关的软件操作，收集整理相关的实验参考资料，要求学生在做实验时能带上充足的参考资料；若准备不充分，则学生不得参加本次实验，不得书写实验报告； 2. 要求学生要认真做实验，主要是指不得迟到、早退和旷课，在做实验过程中要严格遵守实验室规章制度，认真完成实验内容，极积主动地向实验教师提问等；若学生无故旷课，则本次实验等级计为D； 3. 学生要认真工整地书写实验报告，实验报告的内容要紧扣实验的要求和目的，不得抄袭他人的实验报告； 4. 实验成绩评定分为A+、A、A-、B+、B、C、D 各等级。根据实验准备、 实验态度、实验报告的书写、实验报告的内容进行综合评定，具体对应等级如下：完全符合、非常符合、很符合、比较符合、基本符合、不符合、完全不符 合 实验名称：算法设计基础实验(实验一) 指导教师：牟廉明，刘芳实验时数： 4 实验设备：安装了VC++计算机 实验日期：年_月_日实验地点：第五教学楼北802 实验目的： 掌握算法设计的基本原理，熟悉算法设计的基本步骤及其软件实现。 实验准备： 1. 在开始本实验之前，请复习相关实验内容； 2. 需要一台准备安装Windows XP Professional操作系统和装有VC++6.0的计算机。 实验内容： 求n至少为多大时，n个1组成的整数能被2013整除。 实验过程： 1.1算法思想 2013=61*33,6个1能够整除33,寻找满足n个1能够整除61的n即可。 1.2算法步骤 1?定义变量y储存余数，i储存1的个数，m为被除数，初始化为111111； 2?如果被除数能够除尽61,输出i; 如果被除数不能够除尽61，while继续循环，m=y*1000000+111111,i++; 3?重复2，直到找到满足条件的m为止，输出i; 1.3算法实现(C++程序代码) #in clude 第一章绪论 一．选择题 1．数据结构被形式地定义为（K，R），其中K是①_B_的有限集合，R是K上的②_D_的有限集合。 ①A．算法B．数据元素C．数据操作D．逻辑结构 ②A．操作B．映象C．存储D．关系 2．算法分析的目的是①C，算法分析的两个主要方面是②A。 ①A．找出数据结构的合理性 B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进 D．分析算法的易懂性和文档性 ②A．空间复杂性和时间复杂性 B．正确性和简明性 C．可读性和文档性 D．数据复杂性和程序复杂性 3．在计算机存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为(B) A．逻辑结构B．顺序存储结构 C．链表存储结构D．以上都不对 4．数据结构中，在逻辑上可以把数据结构分成：( C ）。 A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．内部结构和外部结构5．以下属于顺序存储结构优点的是（A ）。 A．存储密度大B．插入运算方便 C．删除运算方便D．可方便地用于各种逻辑结构的存储表示 6．数据结构研究的内容是（D ）。 A．数据的逻辑结构B．数据的存储结构 C．建立在相应逻辑结构和存储结构上的算法D．包括以上三个方面 7．链式存储的存储结构所占存储空间（A ）。 A．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 B．只有一部分，存放结点值 C．只有一部分，存储表示结点间关系的指针 D．分两部分，一部分存放结点值，另一部分存放结点所占单元数 8．一个正确的算法应该具有5 个特性，除输入、输出特性外，另外3 个特性是（A ）。 A．确定性、可行性、有穷性B．易读性、确定性、有效性C．有穷性、稳定性、确定性D．可行性、易读性、有穷性9．以下关于数据的逻辑结构的叙述中正确的是（A）。 A．数据的逻辑结构是数据间关系的描述 B．数据的逻辑结构反映了数据在计算机中的存储方式 C．数据的逻辑结构分为顺序结构和链式结构 D．数据的逻辑结构分为静态结构和动态结构 10．算法分析的主要任务是（C ）。 A．探讨算法的正确性和可读性B．探讨数据组织方式的合理性C．为给定问题寻找一种性能良好的解决方案D．研究数据之间的逻辑关系 二．解答 设有一数据的逻辑结构为：B=(D, S)，其中： D={d1, d2, …, d9} S={ 二、算法设计 1、设计一个算法，通过一趟遍历在单链表中确定值最大的结点。 ElemType Max (LinkList L ){ if(L->next==NULL) return NULL; pmax=L->next; //假定第一个结点中数据具有最大值 p=L->next->next; while(p != NULL ){//如果下一个结点存在 if(p->data > pmax->data) pmax=p; p=p->next; } return pmax->data; 2、设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间。 void inverse(LinkList &L) { // 逆置带头结点的单链表L p=L->next; L->next=NULL; while ( p) { q=p->next; // q指向*p的后继 p->next=L->next; L->next=p; // *p插入在头结点之后 p = q; } } 3、设计一个算法，删除递增有序链表中值大于mink且小于maxk的所有元素（mink和maxk 是给定的两个参数，其值可以和表中的元素相同，也可以不同）。 void delete(LinkList &L, int mink, int maxk) { p=L->next; //首元结点 while (p && p->data<=mink) { pre=p; p=p->next; } //查找第一个值>mink的结点 if (p) { while (p && p->data 算法与数据结构的关系 摘要：何为数据；算法分析研究的内容；数据结构研究的内容；算法与数据结构的联系与区别；数据结构的选择对算法效率的影响。 关键词：算法、数据结构、程序 正文： 一、数据结构研究的内容： 为了了解什么是数据结构先必须明白数据的概念。数据是人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的抽象描述。例如，日常生活中使用的各种文字、数字、和特定的符号都是数据。从计算机的角度来看，数据是所有能被输入到计算机中，且能被计算机处理的符号的集合。他是计算机处理信息的某种特定的符号表示形式。计算机解决问题的实质是对数据进行加工处理。另外，数据元素是数据（集合）中的一个“个体”，是数据的基本单位。 数据结构是指数据以及相互之间的关系，可以看做是相互之间存在的某种特定关系的数据元素的集合，因此，可以吧数据结构看成是带结构的数据元素的集合。数据结构研究的内容可以包含以下几个方面： （1）数据元素之间的逻辑关系，即数据的逻辑结构； （2）数据元素及其关系在计算机存储其中的存储方式，即数据的存储结构，也称为数据的物理结构； （3）施加在该数据结构上的操作，即数据运算。 常见的数据逻辑结构包括：集合、线性结构、树形结构、图形结构等。常见的数据存储结构包括：顺序存储结构、链式存储结构、索引存储结构、哈希存储结构（也叫散列存储结构）。 二、算法分析研究的内容： 算法是指在解决问题时按照某种机械步骤一定可以得到问题的结果（有解时给出解，无解时给出无解的结论）的处理过程。简言之，算法就是计算机解决问题的步骤。当面临某个问题时，需要找到用计算机解决这个问题的方法和步骤，算法就是解决这个问题的方法和步骤的描述。所谓机械步骤是指，算法中有待执行的运算和操作，必须是相当基本的。换言之，他们都是能够精确地被计算机运行的算法，计算机甚至不需要掌握算法的含义，即可根据该算法的每一步骤要求，进行操作并最终得出正确的结果。算法由操作、控制结构、数据结构3要素构成。 算法分析的主要任务是对设计出的每一个具体的算法，利用数学工具，讨论其复杂度。对算法的分析一方面能深刻地理解问题的本质以及可能的求解技术，另一方面可以探讨某种具体算法实用于哪类问题，或某类问题宜采用哪种算法。算法分析就是研究算法从而达到优化计算机解决问题的效率的目的。 对算法的分析和评价，一般应考虑正确性、可维护性、可读性、运算量、占用存储空间等诸多因素。其中评价算法的3条主要标准是： （1）算法实现所耗费的时间； （2）算法实现所好费的存储空间，其中主要考虑辅助存储空间； （3）算法应易于理解，易于编码，易于调试等。 课程名称: 数据结构与算法 学院:计算机科学与技术 学号：11003070429 姓名张茂盛 指导教师:陈媛 设计时间: 2012/12/09 1.运动会分数统计（限1 人完成） 任务：参加运动会有n个学校，学校编号为1……n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1……m，女子m+1……m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m<=20,n<=20） 功能要求： 1)可以输入各个项目的前三名或前五名的成绩； 2)能统计各学校总分， 3)可以按学校编号或名称、学校总分、男女团体总分排序输出； 4)可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。 5)数据存入文件并能随时查询 6)规定：输入数据形式和范围：可以输入学校的名称，运动项目的名称 输出形式：有合理的提示，各学校分数为整形 界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。 存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。（数据文件的数据读写方法等相关内容在c语言程序设计的书上，请自学解决）请在最后的上交资料中指明你用到的存储结构； 测试数据：要求使用1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明； 2.飞机订票系统 任务：通过此系统可以实现如下功能： 录入： 可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）查询： 可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）； 可以输入起飞抵达城市，查询飞机航班情况； 订票：（订票情况可以存在一个数据文件中，结构自己设定） 可以订票，如果该航班已经无票，可以提供相关可选择航班； 退票：可退票，退票后修改相关数据文件； 客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。 修改航班信息： 当航班信息改变可以修改航班数据文件 要求： 根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能； 3.文章编辑 功能：输入一页文字，程序可以统计出文字、数字、空格的个数。 静态存储一页文章，每行最多不超过80个字符，共N行；要求（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。 存储结构使用线性表，分别用几个子函数实现相应的功能； 输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。 输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出"全部字母数"、"数字个数"、"空格个数"、"文章总字数"（3）输出删除某一字符串后的文章； 4.宿舍管理查询软件 1)任务：为宿舍管理人员编写一个宿舍管理查询软件, 程序设计要求： A.采用交互工作方式 B.建立数据文件，数据文件按关键字（姓名、学号、房号）进行排序(冒泡、选择、插入排序等任选一种) 数据结构与算法课程设计 一、课程设计的目的、要求和任务 本课程设计是为了配合《数据结构与算法》课程的开设，通过设计完整的程序，使学生掌握数据结构的应用、算法的编写等基本方法。 1.课程的目的 （1）使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。 （2）使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。（3）使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力； 2.课程的基本要求与任务 （1）巩固和加深对数据结构基本知识的理解，提高综合运用课程知识的能力。 （2）培养学生自学参考书籍，查阅手册、图表和文献资料的能力。 （3）通过实际课程设计，初步掌握简单软件的分析方法和设计方法。 （4）了解与课程有关的工程技术规范，能正确解释和分析实验结果。 （5）题目具有足够的工作量。 二、课程设计的一般步骤 （1）划分课程设计小组：由不超过2名同学组成一个课程设计小组，自愿组队。 （2）选题与搜集资料：每个课程设计小组在参考选题中选择课题，并保证每人一题。（3）分析与概要设计：根据搜集的资料，进行程序功能与数据结构分析，并选择合适的数据结构、并在此基础上进行实现程序功能的算法设计。 （3）程序设计：运用掌握C/C++语言编写程序，实现所有程序的各个模块功能。 （4）调试与测试：调试程序，并记录测试情况。 （5）完成课程设计报告。 （6）验收与评分：指导教师对每个同学的开发的系统进行综合验收。 三、任务完成形式 1．完整的软件系统 最终必须向指导老师提交完整的程序源代码(.c和.cpp以及.h为后缀的文件)、数据文件以及使用说明文件等。源代码文件要特别注意编程规范、代码风格，关键代码需有合理的注释，不含任何无用代码；数据文件内要求有一定数量的“真实”数据（如对于记录文件，需要有5条以上记录）；使用说明文件的第一行，需要给出设计者的学号、姓名，后面为其它说明。2．课程设计报告 报告总体上主要包括以下几个部分，封面、目录、课程设计报告正文、使用说明、参考文献。其中课程设计报告正文(12-20页之间，5000字以上)，书写规范，应包括如下8个部分： （1）问题描述：描述要求编程解决的问题。 （2）功能要求：给出程序要达到的具体的要求。 （3）算法思想：描述解决相应问题算法的设计思想。 （4）模块划分：描述所设计程序的各个模块（即函数）功能。 （5）数据结构：给出所使用的基本抽象数据类型,所定义的具体问题的数据类型,以及新定义的抽象数据类型。 （6）核心源程序：给出核心算法源代码，要求有充分的注释语句，至少要注释每个函数参数的含义和函数返回值的含义。 （7）测试数据：设计测试数据，或具体给出测试数据。要求测试数据能全面地测试所设计程序的功能。 （8）测试情况与结果分析：给出程序的测试情况，并分析运行结果。 四、成绩评定标准 学生成绩以优、良、中、及格和不及格5个等级评定。其中： （1）学生编写的实际软件和运行结果，占总成绩45%； （2）设计报告，占总成绩45%。 （3）小组合作情况，占总成绩的10%。该部分由指导教师进行现场口试，依据表现给分。 只有程序验收通过后，才能按以下方法核定本次课程设计的总成绩。以下几点是决定总成绩的关键因素： （1）考勤、纪律、实验室卫生 （2）工作量（代码量、功能多少、难度） （3）所用到的关键技术 （4）实用性、创新 （5）代码书写规范性 （6）程序界面美观、新技术运用得当 （7）个人答辩及小组合作情况 以下几种情形认定为成绩不合格： （1）未能独立完成设计或概念不清； （2）有效代码总量不足600行(不含自动生成代码)； （3）“管理系统”类课题中使用现有数据库系统如access，SQL Server等； （4）课程设计报告或源代码有抄袭行为； （5）3次(含)以上点名未到； 精心整理 第1章绪论 习题 1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。 3．简述逻辑结构的四种基本关系并画出它们的关系图。 4．存储结构由哪两种基本的存储方法实现 5 A 6 {x=x-10;y--;} elsex++; （2）for(i=0;i （4）i=1; while(i<=n) i=i*3; （5）x=0; for(i=1;i 内容包括： 一、课程设计题目： 二、课程设计内容： 三、算法设计： 四、程序正确性验证（指边界测试数据，即程序对于精心选择的典型、苛刻 而带有刁难性的几组输入数据能够得出满足要求的结果）： 五、课程设计过程中出现的主要问题、原因及解决方法： 六、课程设计的主要收获： 七、对今后课程设计的建议： 算法与数据结构课程设计题目 一、单项分值：25分 1、约瑟夫环游戏 2、八皇后问题(图形表示加20分) 3、表达式的求值问题 4、迷宫问题(图形表示加10分) 二、单项分值：80分 5、HTML文档标记匹配算法 要求：输入一段HTML代码，判断该代码是否符合HTML的语法 提示：HTML文档由不同的标记划分为不同的部分与层次。与括号类似，这些标记需要成对出现，对于名为 ' 算法设计题 1. 设二叉树bt采用二叉链表结构存储。试设计一个算法输出二叉树中所有非叶子结点，并求出非叶子结点的个数。 【答案】 int count=0; void algo2(BTNode *bt){ if (bt){ if(bt->lchild || bt->rchild){ / printf(bt->data); count++; } algo2(bt->lchild); algo2(bt->rchild); } } 2. 阅读下列函数arrange() — int arrange(int a[],int 1,int h,int x) {i]上，使所有≥x的元素均落在a[i＋1..h]上。 （2）int f(int b[],int n) 或 int f(int b[],int n) { { int p,q； int p,q； p=arrange(b,0,n－1,0)； p=arrange(b,0,n－1,1)； q= arrange(b,p+1,n－1,1)； q= arrange(b,0,p,0)； return q－p； return p－q； ) } } 3. 假设线性表以带表头结点的循环单链表表示。试设计一个算法，在线性表的第k个元素前插入新元素y。假如表长小于k，则插在表尾。 【答案】 void algo1(LNode *h,int k,ElemType y){ q=h; P=h->next; j=1; while( p!=h && j 数据结构与算法设计的关系 学号：2009221104220066 姓名：曹丹专业：09软工 摘要：分别介绍数据结构和算法设计所研究的内容，以及数据结构和算法设计的区别和联系，最后举例说明。 关键字：数据结构算法设计 正文： 一、数据结构研究的内容 数据结构是指数据以及相互之间的联系，可以看做是相互之间存在着某种特定关系的数据元素的集合，因此，可以把数据结构看成是带结构的数据元素的集合。主要包括以下几个方面： （1）数据元素之间的逻辑关系，即数据的逻辑结构。 （2）数据元素及其关系在计算机存储器中的存储方式，即数据的存储结构，也称为数据的物理结构。 （3）施加在该数据上的运算，即数据的运算。 数据的逻辑结构包括：集合、线性结构、树形结构、图形结构等；存储结构包括：顺序存储结构、链式存储结构、索引存储结构、哈希（散列）存储结构等。 二、算法设计的研究内容 算法设计作为用计算机解决问题的一个步骤，其任务是对各类具体问题设计出良好的算法。算法设计作为一门课程，是研究设计算法的规律和方法。 算法是指在解决问题时按照某种机械步骤一定可以得到问题的 结果（有解时给出解，无解时给出无解的结论）的处理过程。简言之，算法就是计算机解决问题的步骤。当面临某个问题时，需要找到用计算机解决这个问题的方法和步骤，算法就是解决这个问题的方法和步骤的描述。所谓机械步骤是指，算法中有待执行的运算和操作，必须是相当基本的。换言之，他们都是能够精确地被计算机运行的算法，计算机甚至不需要掌握算法的含义，即可根据该算法的每一步骤要求，进行操作并最终得出正确的结果。 算法由操作、控制结构、数据结构3要素构成。 算法分析的主要任务是对设计出的每一个具体的算法，利用数学工具，讨论其复杂度。对算法的分析一方面能深刻地理解问题的本质以及可能的求解技术，另一方面可以探讨某种具体算法实用于哪类问题，或某类问题宜采用哪种算法。算法分析就是研究算法从而达到优化计算机解决问题的效率的目的。 对算法的分析和评价，一般应考虑正确性、可读性、稳健性、高效率与低存储量需求等诸多因素。其中评价算法的3条主要标准是：（1）算法实现所耗费的时间； （2）算法实现所好费的存储空间，其中主要考虑辅助存储空间；（3）算法应易于理解，易于编码，易于调试等。 其中时间复杂度是评价算法优劣的一条最重要的标准。 三、数据结构与算法设计的关系 算法设计的实质是对实际问题要处理的数据选择一种恰当的存储结构，并在选定的存储结构上设计一个好的算法，实现对数据的处 数据结构课程设计 一、考核方法和内容 根据课程设计过程中学生的学生态度、题目完成情况、课程设计报告书的质量和回答问题的情况等按照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.通讯录管理系统的设计与实现——顺序表 3.广义表的应用 4.学生成绩管理系统的设计与实现 5.家谱管理系统的设计与实现 6.集合的并、交和差运算的程序 7.运动会分数统计 8.一元多项式计算器 9.文章编辑 10.哈夫曼树及其编码 11.校园导游咨询 12.通讯录管理系统的设计与实现——单链表 13.地图着色问题 14.内部排序算法比较 15.火车售票系统 16.图书管理系统 17.客户消费积分管理系统 18.产品进销存管理系统 19. 迷宫求解数据结构与算法设计实验一
数据结构和C++程序设计_题库
数据结构与算法设计知识点
数据结构算法设计题复习题
《算法与数据结构》课程设计报告书
:节的头部 ●数据结构和算法课程设计题目
数据结构与算法设计课程设计
数据结构与算法习题库(考前必备)
数据结构算法设计期末复习题
算法与数据结构的关系
《数据结构与算法》课程设计题目及要求
数据结构与算法课程设计
数据结构与算法习题及答案
《算法与数据结构》课程设计
:节的头部 ●数据结构算法设计题复习题
数据结构与算法设计的关系
数据结构课程设计题目