因为要经常接触字符串和数值混排的数据文本文件，所以，如何有效的读取这类文件成了我头痛的事，不过今日学习了日志[1]，找到的解决方法，编程读写实例如下。
要读取的目标文件dat.txt内容如下：
zzz 8 10.0 2.5 2.55
llz 10 20.2 3.9 4.96
读写方法编程如下：
#include
#include
using namespace std;
void main()
{
ifstream fin;
char name[20];
int inum;
float fnum[3];
fin.open("dat.txt"); // 打开要读的文件
if (fin.good()) // 判断是否成功打开
{
while (!fin.eof())
{
fin >> name; // 读取字符串
fin >> inum; // 读取整数数值
for(int i = 0; i < 3; i++)
{
fin >> fnum[i]; // 循环读取浮点数
}
cout << name << ' ' << inum << ' ' << fnum[2] << endl; //显示检验结果的正确性
}
}
else
{
cout << "File can't open" << endl;
}
fin.close(); // 关闭文件
}
运行结果如下：
zzz 8 2.55
llz 10 4.96
Press any key to continue
数据结构复习资料 一、填空题 1. 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科。 2. 数据结构被形式地定义为（D, R），其中D是数据元素的有限集合，R是D上的关系有限集合。 3. 数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。 4. 数据结构按逻辑结构可分为两大类，它们分别是线性结构和非线性结构。 5. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。 6．在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有1个后续结点。 7. 在树形结构中，树根结点没有前驱结点，其余每个结点有且只有1个前驱结点；叶子结点没有后续结点，其余每个结点的后续结点数可以任意多个。 8. 在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。 9．数据的存储结构可用四种基本的存储方法表示，它们分别是顺序、链式、索引和散列。 10. 数据的运算最常用的有5种，它们分别是插入、删除、修改、查找、排序。 11. 一个算法的效率可分为时间效率和空间效率。 12. 在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与表长和该元素在表中的位置有关。 13. 线性表中结点的集合是有限的，结点间的关系是一对一的。 14. 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动n-i+1 个元素。 15. 向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动n-i 个元素。 16. 在顺序表中访问任意一结点的时间复杂度均为O(1)，因此，顺序表也称为随机存取的数据结构。 17. 顺序表中逻辑上相邻的元素的物理位置必定相邻。单链表中逻辑上相邻的元素的物理位置不一定相邻。 18．在单链表中，除了首元结点外，任一结点的存储位置由其直接前驱结点的链域的值指示。 19．在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O（n）。 20. 向量、栈和队列都是线性结构，可以在向量的任何位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入和队首删除元素。
目录 1 问题描述 (2) 1.1题目 (2) 1.2问题 (2) 1.3要求 (2) 2 设计 (2) 2.1存储结构设计 (2) 2.2主要算法设计 (3) 2.3测试用例及测试结果 (6) 3 调试报告 (9) 4 对设计和编码的讨论和分析 (20) 4.1设计 (20) 4.2对编码的讨论 (21) 5 总结和体会 (22) 附录一 (24) 本科生课程设计成绩评定表................... 错误！未定义书签。
数据结构课程设计 ——判别括号配对 1问题描述 1.1题目： 判别括号配对 1.2问题： 一个算术表达式含圆括号、中括号、花括号,且它们可任意嵌套使用。写一程序，判断任一算术表达式中所含括号是否正确配对。 1.3要求： （1）表达式从键盘输入。 （2）利用栈求解此问题。 （3）测试用例自己设计。 2设计 2.1存储结构设计 题目要求利用栈来求解此问题，因此选择顺序栈作为存储结构，具体表示如下： #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10
char *base; char *top; int stacksize; }SqStack; 2.2主要算法设计 2.2.1算法思想 (1)文字描述 从键盘输入一个表达式； 逐个扫描表达式中的字符； 当遇到左括号时，将左括号入栈； 继续扫描，将此后遇到的第一个右括号与栈顶元素比较，若匹配，则栈顶元素出栈；否则，继续扫描； 当整个表达式扫描完以后，判断栈内是否还有元素，若有，则括号不匹配； 若栈为空，则括号配对成功； 在括号配对不成功的情况下，利用栈顶栈底元素的差值，可以对左右括号数进行比较。（2）流程图表示
贵州大学实验报告 学院：计信学院专业：网络工程班级：091班姓名XXX 学号XXXXXXXXX 实验组 5 实验时间2011.12.02 指导教师XXXXX 成绩 实验项目名称 队列的实现 实 验目的1．掌握队列的思想及其存储实现。2．掌握队列的常见算法的程序实现。 实验原理1.根据实验内容编程，上机调试、得出正确的运行程序。 2. 编译运行程序，观察运行情况和输出结果。 3. 写出实验报告（包括源程序和运行结果）。 实验内容 1．采用链式存储实现队列的初始化、入队、出队操作。 2．采用顺序存储实现循环队列的初始化、入队、出队操作。 3．在主函数中设计一个简单的菜单，分别测试上述算法。
实验数据及其步骤链式存储队列： #include 《数据结构与算法》（c语言版）期末考复习题 一、选择题。 1．在数据结构中，从逻辑上可以把数据结构分为 C 。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指 A 。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑 A 。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是 D 。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。（1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进C．分析算法的易读性和文档性（2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O(n2) 。 s =0; for( I =0; i 实验名称：实验四队列的基本操作 实验目的 掌握队列这种抽象数据类型的特点及实现方法。 实验内容 从键盘读入若干个整数，建一个顺序队列或链式队列，并完成下列操作： （1）初始化队列； （2）队列是否为空； （3）出队； （4）入队。 算法设计分析 （一）数据结构的定义 单链表存储结构定义为： struct Node; //链表单链表 typedef struct Node *PNode; int dui; dui =1; struct Node { int info; PNode link; }; struct LinkQueue { PNode f; PNode r; }; typedef struct LinkQueue *PLinkQueue; （二）总体设计 程序由主函数、创建队列函数、判断是否为空队列函数、入队函数、出队函数、取数函数、显示队列函数、菜单函数组成。其功能描述如下： （1）主函数：调用各个函数以实现相应功能 main() { PLinkQueue a; //定义链表a int b,c,e; //b 菜单选择c选择继续输入e输入元素 do { //菜单选择 mune(); scanf("%d",&b); switch(b) { case 1://初始化 a=create(); //初始化队列 case 2: //入队 do { printf("\n请输入需要入队的数："); if(e!=NULL) { scanf("%d",&e); enQueue(a,e); } printf("是否继续入队？(是:1 否：0)\n"); scanf("%d",&c); } while(c==1); break; case 3: //出队 c=frontQueue(a); deQueue(a); if(dui!=0) { printf("\n出队为:%d\n",c); } dui=1; break; case 4: //显示队中元素 showQueue(a); break; case 5: return; default: printf("输入错误，程序结束!\n"); return; } } while(a!=5); { return 0; } } （三）各函数的详细设计： Function1: PLinkQueue create(void)//创队 数据结构（C语言版）期末复习汇总 第一章绪论 数据结构：是一门研究非数值计算程序设计中的操作对象，以及这些对象之间的关系和操作的学科。 数据结构分为：逻辑结构、物理结构、操作三部分 逻辑结构：集合、线性结构、树形结构、图（网）状结构 物理结构（存储结构）：顺序存储结构、链式存储结构 算法：是为了解决某类问题而规定的一个有限长的操作序列。 算法五个特性：有穷性、确定性、可行性、输入、输出 评价算法优劣的基本标准（4个）：正确性、可读性、健壮性、高效性及低存储量 语句频度的计算。 算法的时间复杂度： 常见有：O(1)，O(n)，O(n2)，O(log2n)，O(nlog2n)，O(2n) 第二章线性表 线性表的定义和特点： 线性表：由n(n≥0)个数据特性相同的元素构成的有限序列。线性表中元素个数n(n≥0)定义为线性表的长度，n=0时称为空表。 非空线性表或线性结构，其特点： （1）存在唯一的一个被称作“第一个”的数据元素； （2）存在唯一的一个被称作“最有一个”的数据元素； （3）除第一个之外，结构中的每个数据元素均只有一个前驱； （4）除最后一个之外，结构中的每个数据元素均只有一个后继。 顺序表的插入：共计n个元素，在第i位插入，应移动（n-i+1）位元素。 顺序表的删除：共计n个元素，删除第i位，应移动（n-i）位元素。 线性表的两种存储方式：顺序存储、链式存储。 顺序存储 概念：以一组连续的存储空间存放线性表； 优点：逻辑相邻，物理相邻；可随机存取任一元素；存储空间使用紧凑； 缺点：插入、删除操作需要移动大量的元素；预先分配空间需按最大空间分配，利用不充分；表容量难以扩充； 操作：查找、插入、删除等 查找： ListSearch(SqlList L,ElemType x,int n) { int i; for (i=0;i 数据结构课程设计报告 设计题目：括号匹配 院系计算机学院 年级11 级 学生刘云飞 学号E01114295 指导教师王爱平 起止时间9-7/9-14 课程设计目的 1.熟悉并写出栈的逻辑结构表示 2.实现栈的存储表示 3.实现栈的操作 内容 括号匹配 课程设计要求 1.在实验报告中写出栈的ADT表示； 2.在实验报告中给出数据类型定义和核心算法和程序； 3.在实验报告中罗列实验过程中出现的问题和解决的方法； 4.打包上交调试后的完整程序，提交实验报告； 5.实验之前写出实验报告的大概框架，实验过程中填写完整。 6.实验时携带需要上机调试的程序； 7.实验评分：实验之前预习占20%，实验报告书写情况占50%，运行情况30%。概要设计 1．栈的ADT表示 ADT Stack{ 数据对象：D={ai|ai∈ ElemSet,i=1，2，…，n,n>=0} 数据关系：R1={ 实验四串 【实验目的】 1、掌握串的存储表示及基本操作； 2、掌握串的两种模式匹配算法：BF和KMP。 3、了解串的应用。 【实验学时】 2学时 【实验预习】 回答以下问题： 1、串和子串的定义 串的定义：串是由零个或多个任意字符组成的有限序列。 子串的定义：串中任意连续字符组成的子序列称为该串的子串。 2、串的模式匹配 串的模式匹配即子串定位是一种重要的串运算。设s和t是给定的两个串，从主串s的第start个字符开始查找等于子串t的过程称为模式匹配，如果在S中找到等于t的子串，则称匹配成功，函数返回t在s中首次出现的存储位置（或序号）；否则，匹配失败，返回0。 【实验内容和要求】 1、按照要求完成程序exp4_1.c，实现串的相关操作。调试并运行如下测试数据给出运行结果： ?求“This is a boy”的串长； ?比较”abc 3”和“abcde“； 表示空格 ?比较”english”和“student“； ?比较”abc”和“abc“； ?截取串”white”，起始2，长度2； ?截取串”white”，起始1，长度7； ?截取串”white”，起始6，长度2； ?连接串”asddffgh”和”12344”； #include typedef struct { char data[MAXSIZE]; int length; } SqString; int strInit(SqString *s); /*初始化串*/ int strCreate(SqString *s); /*生成一个串*/ int strLength(SqString *s); /*求串的长度*/ int strCompare(SqString *s1,SqString *s2); /*两个串的比较*/ int subString(SqString *sub,SqString *s,int pos,int len); /*求子串*/ int strConcat(SqString *t,SqString *s1,SqString *s2); /*两个串的连接*/ /*初始化串*/ int strInit(SqString *s) { s->length=0; s->data[0]='\0'; return OK; }/*strInit*/ /*生成一个串*/ int strCreate(SqString *s) { printf("input string :"); gets(s->data); s->length=strlen(s->data); return OK; }/*strCreate*/ /*（1）---求串的长度*/ int strLength(SqString *s) { return s->length; }/*strLength*/ /*（2）---两个串的比较，S1>S2返回>0，s1 “数据结构”课程设计题目 1、城市链表（3） [问题描述] 将若干城市的信息，存入一个带头结点的单链表。结点中的城市信息包括：城市名，城市的位置坐标。要求能够利用城市名和位置坐标进行有关查找、插入、删除、更新等操作。 [基本要求] （1）给定一个城市名，返回其位置坐标； （2）给定一个位置坐标P和一个距离D，返回所有与P的距离小于等于D的城市。 [测试数据] 由学生依据软件工程的测试技术自己确定。注意测试边界数据。 2、约瑟夫生死者游戏（3） [问题描述] 约瑟夫（Joeph）问题的一种描述是：编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 [基本要求] 利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。 [测试数据] m的初值为20；密码：3，1，7，2，4，8，4（正确的结果应为6，1，4，7，2，3，5）。 [实现提示] 程序运行后首先要求用户指定初始报数上限值，然后读取各人的密码。设n≤30。 [选作内容] 向上述程序中添加在顺序结构上实现的部分。 3、括号匹配的检验（3） [问题描述] 假设表达式中允许有两种括号：圆括号和方括号，其嵌套的顺序随意，即（（）[ ]）或[（[ ] [ ]）]等为正确格式，[（ ]）或（（（]均为不正确的格式。检验括号是否匹配的方法可用“期待的紧迫程度”这个概念来描述。例如：考虑下列的括号序列： 竭诚为您提供优质文档/双击可除串的模式匹配算法实验报告 篇一：串的模式匹配算法 串的匹配算法——bruteForce(bF)算法 匹配模式的定义 设有主串s和子串T，子串T的定位就是要在主串s中找到一个与子串T相等的子串。通常把主串s称为目标串，把子串T称为模式串，因此定位也称作模式匹配。模式匹配成功是指在目标串s中找到一个模式串T；不成功则指目标串s中不存在模式串T。bF算法 brute-Force算法简称为bF算法，其基本思路是：从目标串s的第一个字符开始和模式串T中的第一个字符比较，若相等，则继续逐个比较后续的字符；否则从目标串s的第二个字符开始重新与模式串T的第一个字符进行比较。以此类推，若从模式串T的第i个字符开始，每个字符依次和目标串s中的对应字符相等，则匹配成功，该算法返回i；否则，匹配失败，算法返回0。 实现代码如下： /*返回子串T在主串s中第pos个字符之后的位置。若不存在，则函数返回值为0./*T非空。 intindex(strings,stringT,intpos) { inti=pos;//用于主串s中当前位置下标，若pos不为1则从pos位置开始匹配intj=1;//j用于子串T中当前位置下标值while(i j=1； } if(j>T[0]) returni-T[0]; else return0; } } bF算法的时间复杂度 若n为主串长度，m为子串长度则 最好的情况是：一配就中，只比较了m次。 最坏的情况是：主串前面n-m个位置都部分匹配到子串的最后一位，即这n-m位比较了m次，最后m位也各比较了一次，还要加上m,所以总次数为：(n-m)*m+m=(n-m+1)*m从最好到最坏情况统计总的比较次数，然后取平均，得到一般情况是o(n+m). ?、实验目的 1. 了解队列的特性。 2. 掌握队列的顺序表示和实现。 3. 掌握队列的链式表示和实现。 1、实验内容 实验3. 3队列的顺序表示和实现 编写一个程序实现顺序队列的各种基本运算（采用循环队列）， 主程序，完成如下功能： ⑴ 初始化队列。 ⑵ 建立顺序队列。 ⑶ 入队。 ⑷ 岀队。 (5) 判断队列是否为空。 ⑹ 取队头元素。 (7) 遍历队列。 实验3.4队列的链式表示和实现 编写一个程序实现链队列的各种基本运算，并在此基础上设计 能： (1) 初始化并建立链队列 ⑵ 入链队列。 ⑶ 岀链队列。 ⑷ 遍历链队列。 #i nclude int Ini tQueue(SqQueue &Q) { Q.base=(i nt*)malloc(MAXQSIZE*sizeof(i nt)); if(!Q.base)exit(O); Q.fro nt=Q.rear=0; return 0; }//初始化顺序队列 int QueueLe ngth(SqQueue Q) { int i; i=(Q.rear-Q.fro nt+MAXQSIZE)%MAXQSIZE; printf(“队列长度％5d\n",i); if(i)printf(" 队列非空“)； else printf(" 队列为空"); return 0; }//判断队列是否为空 int En Queue(SqQueue &Q,i nt e) { if((Q.rea 叶1)%MAXQSIZE==Q.fro nt)return 0; Q.base[Q.rear]=e; Q.rear=(Q.rea r+1)%MAXQSIZE; return 0; }//将元素e入队 int DeQueue(SqQueue & Q,i nt e) { if(Q.fro nt==Q.rear)return 0; e=Q.base[Q.fro nt]; prin tf("%5d\n",e); Q.fron t=(Q.fr on t+1)%MAXQSIZE; return 0; }// 删除元素e并返回其值 “数据结构”课程设计题目 1、城市链表 [问题描述] 将若干城市的信息，存入一个带头结点的单链表。结点中的城市信息包括：城市名，城市的位置坐标。要求能够利用城市名和位置坐标进行有关查找、插入、删除、更新等操作。 [基本要求] （1）给定一个城市名，返回其位置坐标； （2）给定一个位置坐标P和一个距离D，返回所有与P的距离小于等于D的城市。 [测试数据] 由学生依据软件工程的测试技术自己确定。注意测试边界数据。 2、约瑟夫生死者游戏 [问题描述] 约瑟夫（Joeph）问题的一种描述是：编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 [基本要求] 利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。 [测试数据] m的初值为20；密码：3，1，7，2，4，8，4（正确的结果应为6，1，4，7，2，3，5）。 [实现提示] 程序运行后首先要求用户指定初始报数上限值，然后读取各人的密码。设n≤30。 [选作内容] 向上述程序中添加在顺序结构上实现的部分。 3、括号匹配的检验 [问题描述] 假设表达式中允许有两种括号：圆括号和方括号，其嵌套的顺序随意，即（（）[ ]）或[（[ ] [ ]）]等为正确格式，[（ ]）或（（（]均为不正确的格式。检验括号是否匹配的方法可用“期待的紧迫程度”这个概念来描述。例如：考虑下列的括号序列： 《数据结构》课程实验报告 一、实验目的和要求 （1）熟悉C语言的上机环境，进一步掌握C语言的结构特点。 （2）掌握队列的顺序表示和实现。 二、实验环境 Windows7 ,VC 三、实验内容及实施 实验三：队列 【实验要求】 构建一个循环队列, 实现下列操作 1、初始化队列(清空)； 2、入队； 3、出队; 4、求队列长度； 5、判断队列是否为空； 【源程序】 #include Q.base=new int[MAXSIZE]; Q.front=Q.rear=0; return OK; }//队列的初始化 int EnQueue(SqQueue &Q,int e) { if((Q.rear+1)%MAXSIZE==Q.front) return ERROR; Q.base[Q.rear]=e; Q.rear=(Q.rear+1)%MAXSIZE; return OK; }//队列的入队 int DeQueue(SqQueue &Q,int &e) { if(Q.front==Q.rear) return ERROR; e=Q.base[Q.front]; Q.front=(Q.front+1)%MAXSIZE; return OK; }//队列的出队 int QueueLength(SqQueue &Q) { int i; i=(Q.rear-Q.front+MAXSIZE)%MAXSIZE; return i; }//求队列长度 void JuQueue(SqQueue &Q) { if(Q.rear==Q.front) printf("队列为空"); else printf("队列不为空"); }//判断队列是否为空 void QueueTraverse(SqQueue &Q) 数据结构C语言版第一 二章习题答案 Document number：BGCG-0857-BTDO-0089-2022 第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 目录 1.1 题目.................................................... 2............... 1.2 问题.................................................... 2............... 2 设计...................................................... 2 ............... 2.1 存储结构设计............................................ 2 ............. 4 对设计和编码的讨论和分析................................. 2..1. 4.1 设计................................................... 2..1.. 4.2 对编码的讨论........................................... 2..1. 5 总结和体会.............................................. 2..3 ........... 附录一 ................................................... 2..4 ............. 本科生课程设计成绩评定表.......................................... 错...误... !未定义书签 1 问题描述 .................................................................................................... 2 ............. 1.3 要求......................................................................................................... 2 .............. 2.2 主要算法设计........................................................................................... 3 ........... 2.3 测试用例及测试结果............................................................................... 6 ......... 3 调试报告 .................................................................................................... 9 ............. 习题三栈和队列 一单项选择题 1. 在作进栈运算时,应先判别栈是否(① ),在作退栈运算时应先判别栈是否(② )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为(③ )。 ①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 2．若已知一个栈的进栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，...，pn，若p1＝3，则p2为( )。 A 可能是2 B 一定是2 C 可能是1 D 一定是1 3. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 4.设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4, s6, s5,s1,则栈的容量至少应该是（） A.2 B. 3 C. 5 D.6 5. 若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（）。 A. |top[2]-top[1]|=0 B. top[1]+1=top[2] C. top[1]+top[2]=m D. top[1]=top[2] 6. 执行完下列语句段后，i值为：（） int f(int x) { return ((x>0) ? x* f(x-1):2);} int i ; i =f(f(1)); A．2 B. 4 C. 8 D. 无限递归 7. 表达式3* 2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（），其中^为乘幂。 A. 3,2,4,1,1；(*^(+*- B. 3,2,8；(*^- C. 3,2,4,2,2；(*^(- D. 3,2,8；(*^(- 8. 用链接方式存储的队列，在进行删除运算时（）。 A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改 9. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（）的数据结构。 A．队列 B．多维数组 C．栈 D. 线性表 10．设C语言数组Data[m+1]作为循环队列SQ的存储空间， front为队头指针，rear为队尾指针，则执行出队操作的语句为（） A.front=front+1 B. front=（front+1）% m C.rear=(rear+1)%(m+1) D. front=(front+1)%(m+1) 11.循环队列的队满条件为 ( ) A. (sq.rear+1) % maxsize ==(sq.front+1) % maxsize; B. (sq.front+1) % maxsize ==sq.rear C. (sq.rear+1) % maxsize ==sq.front D.sq.rear ==sq.front 课程名称: 《数据结构》课程设计课程设计题目: 括号匹配 姓名:*** 院系:计算机科学与技术学院 专业:计算机科学与技术 年级:** 学号:******* 指导教师:*** 2015 年 09月 10 日 目录 1 课程设计的目的 (1) 2 需求分析 (3) 3 课程设计报告内容 (3) 3.1概要设计 (3) 3.2详细设计 (3) 3.3调试分析 (5) 4 总结 (7) 5 程序清单 (8) 6 参考文献 (7) 1.课程设计的目的 (1) 熟练使用C 语言编写程序，解决实际问题; (2) 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力; (3) 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能; (4) 提高综合运用所学的理论知识和方法独立分析和解决问题的能力; 2.需求分析 本程序文件主要的功能是判断括号的匹配问题。 程序的执行是从事先输入好数据的文档中读取，然后对所读取的数据进行括号匹配行的判断。最后输出判断的结果。 程序函数主要有void InitStack(Stack *S)、ElemType GetTop(Stack S,ElemType *e)、void push(Stack *S,ElemType e)、ElemType pop(Stack *S,ElemType *e)、int Judge(ElemType a[])。InitStack函数是用来初始化栈；GetTop函数是用来获取栈顶元素；push是用来把元素压栈、pop函数是用来把元素弹出栈、Judge函数是用来判断括号是否匹配。 3 括号匹配的设计 3.1概要设计 算法分析： 首先设置好一个栈，然后从文件中读入数据，在读入的数据时，从文件中读取的字符串存入到函数定义好的字符数组中。然后把该数组作为函数参数。当每读入一个‘（’或者是‘[’，就把这个元素压栈，若是读入的元素是‘]’或者是‘）’，就调用GetTop函数，来获取栈顶元素，如果获取的栈顶元素和该次读入的元素匹配而且栈不空的话，就说明该元素是匹配的，继续比较下一次的元素；如果获取的栈顶元素和该次读入的元素不匹配的话，就说明该元素是不匹配的，直接结束运行。当所有的‘）’或者是‘]’全部比较完成之后，栈仍然不空，说明栈中还剩有‘[’或者‘(’，括号不匹配。 3.2详细设计 void InitStack(Stack *S)//建造一个栈 { S->base = (ElemType *)malloc(STACK_INIT_SIZE *sizeof(ElemType)); if(!*S->base) printf("error"); S ->top = S ->base;//将栈设置为空栈 S->stacksize = STACK_INIT_SIZE;//将栈的空间大小设置为STACK_INIT_SIZE } 建栈的操作首先将栈指针s->指向新开辟的内存空间。然后将栈顶指针s->top等于s->base。将栈置成空栈。 ElemType GetTop(Stack S,ElemType *e)//获取栈顶元素 { if(S.top!=S.base) { *e=*(S.top-1); return *e; } 软件学院 上机实验报告 课程名称：数据结构 实验项目：队列的应用 实验室：耘慧420 姓名：学号 专业班级：实验时间： 2016.11.17 一、实验目的及要求 (一) 目的 1．掌握栈队列特点及顺序存储结构(循环队列)下基本操作的实现。 2．掌握队列的应用，能根据问题特点选择队列结构。 （二）.要求 1．定义循环队列的存储结构 2．完成入队、出队、取队头等基本操作的实现。 3．利用队列的基本操作实现n行杨辉三角的输出。 4．主函数调用杨辉三角输出函数，实现n行杨辉三角输出。 二、性质 设计性 三、实验学时 2学时 四、实验环境 C与C++程序设计学习与实验系统 五、实验内容及步骤 (一).内容 1．定义循环队列的存储结构，完成入队、出队、取队头等基本操作的实现。 2. 利用循环队列实现杨辉三角的输出 (二).步骤 1.//---------循环队列—队列的顺序存储结构 ----- #define MAXSIZE 100 typedef struct { QElemType *base; //初始化的动态分配存储空间 int front; //头指针，队列不空指向队列头元素 int rear; //尾指针，队列不空指向队列尾元素下一位置 } SqQueue; 2.杨辉三角: 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 …………………… 这是一个初等数学中讨论的问题。系数表中的第 k行有 k个数，除了第一个和最后一个数为1之外，其余的数则为上一行中位其左、右的两数之和。 如果要求计算并输出杨辉三角前n行的值，则队列的最大空间应为 n+2。假设队列中已存有第 k 行的计算结果，并为了计算方便，在两行之间添加一个"0"作为行界值，则在计算第 k+1 行之前，头指针正指向第 k 行的"0"，而尾元素为第 k+1 行的"0"。由此从左到右依次输出第 k 行的值，并将计算所得的第 k+1 行的值插入队列的基本操作为： void YangHui(int n) { printf("1\n"); EnQueue(&q,0); /*开始*/ EnQueue(&q,1); /*第1行*/ EnQueue(&q,1); for(j=2;j<=n;j++) { EnQueue(&q,0); do{ 《数据结构》 第五版 清华大学自动化系 李宛洲 2004年5月 目录 第一章数据结构--概念与基本类型 (6) 1.1概述 (6) 1.1.1数据结构应用对象 (6) 1.1.2学习数据结构的基础 (7) 1.1.2.1 C语言中的结构体 (7) 1.1.2.2 C语言的指针在数据结构中的关联作用 (8) 1.1.2.3 C语言的共用体(union)数据类型 (12) 1.1.3数据结构定义 (15) 1.2线性表 (17) 1.2.1 顺序表 (18) 1.2.2 链表 (20) 1.2.2.1链表的基本结构及概念 (20) 1.2.2.2单链表设计 (22) 1.2.2.3单链表操作效率 (29) 1.2.2.4双链表设计 (30) 1.2.2.5链表深入学习 (32) 1.2.2.6稀疏矩阵的三元组与十字链表 (36) 1.2.3 堆栈 (41) 1.2.3.1堆栈结构 (41) 1.2.3.2基本操作 (42) 1.2.3.3堆栈与递归 (44) 1.2.3.4递归与分治算法 (45) 1.2.3.5递归与递推 (49) 1.2.3.6栈应用 (52) 1.2.4 队列 (57) 1.2.4.1队列结构 (57) 1.2.3.2队列应用 (59) 1.3非线性数据结构--树 (64) 1.3.1 概念与术语 (64) 1.3.1.1引入非线性数据结构的目的 (64) 1.3.1.2树的定义与术语 (65) 1.3.1.3树的内部节点与叶子节点存储结构问题 (66) 1.3.2 二叉树 (66) 1.3.2.1二叉树基本概念 (66) 1.3.2.2完全二叉树的顺序存储结构 (68) 1.3.2.3二叉树遍历 (69) 1.3.2.4二叉树唯一性问题 (71)数据结构(c语言版)期末考试复习试题
数据结构(C语言)队列的基本操作
数据结构(C语言版)期末复习
数据结构实验报告(栈_括号匹配) (1)
数据结构实验报告-串
数据结构课程设计题目
串的模式匹配算法实验报告
数据结构实验——队列(附程序)
数据结构课程设计题
数据结构-队列实验报告
数据结构C语言版第一二章习题答案
数据结构课程设计---括号匹配
数据结构第三章栈和队列习题及答案
括号匹配(数据结构实验报告)
数据结构——队列的应用
《数据结构》c语言版
相关主题
文本预览