下载文档原格式
目录1问题描述 (2)2基本要求 (2)2.1问题分析及解决法案框架确定 (2)2.2程序设计 (2)2.3详细设计和编码 (2)3算法思想 (2)4模块划分 (3)4.1对各个模块进行功能的描述 (3)4.2模块之间关系及其相互调用 (3)5数据结构 (5)5.1定义栈 (5)5.2定义队列 (5)5.3栈的基本操作 (5)5.4队列的基本操作 (6)6测试数据 (6)7测试情况 (6)8总结 (9)1 问题描述试写一个算法，判断依次读入的一个以@为结束符的字母序列，是否为形如‘序列1&序列2’模式的字符序列。
其中序列1和序列2中都不含字符‘&’，且序列2是序列1的逆序列。
例如，‘a+b&b+a’是属该模式的字符序列，而‘１+３&３－１’则不是。
栈和队列是一种常见的数据结构，是两种非常重要的线性结构，也都是线性表，它们是操作受限的的线性表，有顺序栈、链式栈、链式队列和循环队列等形式。
它们广泛应用在各种软件系统中。
本题就是要用这些线性结构先完成基本的应用，如回文，逆置。
2 基本要求2.1问题分析及解决法案框架确定充分地分析和理解问题本身，使程序结构清晰合理简单和易于调试，并确定每个函数的简单功能，以及函数之间的调用关系。
2.2程序设计1、选择顺序栈和链队列，完成回文判断、字符串的逆置；2、选择链栈和循环队列，完成回文判断、字符串的逆置；3、运用掌握C语言编写程序，实现所编程序的各个模块功能。
2.3详细设计和编码给出所有源程序清单，要求程序有充分的注释语句，至少要注释每个函数参数的含义和函数返回值的含义。
3 算法思想运用栈和队列算法，在序列依次输入时将序列分别入栈和入队列，利用栈FILO 和队列FIFO的特点，通过出栈和出队列实现序列顺序和逆序的比较，根据题目描述的回文序列判断并输出结果。
定义顺序栈和链队列及关于它们的基本操作，如定义栈和队列、求栈和队列的长度、入栈出栈、入队列出队列等。
一、单项选择题1．有下列程序段落:int i,a[5]；for(i=0;i<5;i++)scanf(“%d”,&a[i]);若要使数组元素的值分别为1，2，3，4，5，应从键盘输入（B）。
Ａ．1,2,3,4,5↙Ｂ．1 2 3 4 5↙Ｃ．12345↙Ｄ．1;2;3;4;5↙2．数组名作为函数参数进行传递时，形参获得的是（D）。
A．该数组第一个元素的值B．该数组所有元素的值C．该数组所有元素的地址D．该数组的首地址3.设有如下宏定义:#define A 3+2#define B A*A则表达式“B*B”的值为（ A ）。
Ａ．23Ｂ．5 Ｃ．25Ｄ．6254．在下列说明中，结构类型变量x 所占用内存字节数为（D）。
struct exp{ int i;float j;double k;}x;Ａ．8个Ｂ．7个Ｃ．14个Ｄ．随计算机而定5．设有定义：int k=3,*p=&k; 则表达式*p的值是（D）。
Ａ．1 Ｂ．0 Ｃ．2 Ｄ．36．下列程序的输出结果为（A）。
main（）{ int i=3，b；b=(i--)+(i--)；printf（“%d”，b）；}Ａ．6 Ｂ．2 Ｃ．3 Ｄ．47．当c的值不为0时，在下列选项中能正确将c的值赋给变量a、b的是（D）。
Ａ．c=b=a Ｂ. (a=c)||(b=c) Ｃ. a=c=b Ｄ. (a=c)&&(b=c)8．下列叙述不正确的是（ A ）。
Ａ．函数定义可以嵌套Ｂ．宏定义可以嵌套Ｃ．函数调用可以嵌套Ｄ．循环结构可以嵌套9．设char *p=“abcde”，则printf(“%s”, p ) 的输出结果为（ D ）。
Ａ．c Ｂ．cde Ｃ．b Ｄ．abcde10．p1,p2 为指向浮点的指针变量，下列运算没有意义的是（D）。
Ａ．*p1－*p2 Ｂ．p1++ Ｃ．*p1+*p2 Ｄ．p1+p211．设有int i=010,j=10; 则printf( “%d,%d\n”,++i,j--);的输出是（B）。
902数据结构与C语言程序设计考研大纲902 数据结构与C语言程序设计考研大纲一、考试内容（一）数据结构1.线性表1）线性表的定义2）线性表的顺序存储和基本运算（查找、插入和删除）的实现3）线性表的链式存储和基本运算（查找、插入和删除）的实现4）线性表的应用2.栈、队列和矩阵1）栈和队列的定义2）栈和队列的实现（1）栈的顺序存储和基本操作（入栈、出栈和判栈空、栈满）的实现（2）栈的链式存储和基本操作（入栈、出栈和判栈空）的实现（3）队列的链式存储和基本操作（入队、出队和判队空）的实现（4）循环队列的定义和基本操作（入队、出队和判队空、队满）的实现3）栈和队列的应用4）矩阵的压缩存储（1）特殊矩阵（对称矩阵、三角矩阵、对角矩阵）的压缩存储（2）稀疏矩阵的压缩存储3.树与二叉树1）树的基本概念2）二叉树（1）二叉树的定义及性质（2）二叉树的顺序存储和链式存储（3）二叉树的先序、中序、后序遍历和层序遍历运算（4）线索二叉树的定义3）树和森林（1）树的存储结构（2）树（森林）与二叉树的相互转换（3）树和森林的遍历4）树与二叉树的应用（1）二叉查找树（Binary Search Tree）（2）平衡二叉树（Balanced Binary Tree 或Height-Balanced Tree或A VL Tree）（3）哈夫曼（Huffman）树和哈夫曼编码4.图1）图的基本概念2）图的存储（1）数组表示法（邻接矩阵表示法）（2）邻接表表示法3）图的遍历（1）深度优先搜索（DFS）算法（2）广度优先搜索（BFS）算法4）图的应用（1）最小（代价）生成树求解方法（Prim算法和Kruskal算法）（2）最短路径求解方法（Dijkstra算法和Floyd算法）（3）AOV-网和拓扑排序方法（4）AOE-网和关键路径求解方法5.查找1）查找的基本概念2）顺序查找法（1）顺序查找算法（2）平均查找长度计算3）折半查找法（1）折半查找算法（2）折半查找判定树的构造（3）平均查找长度计算4）动态查找表（1）二叉查找树（也称为二叉排序树）的构造及查找、插入和删除运算（2）平衡二叉树的构造及查找运算（3）B-树的特点及查找运算（4）平均查找长度计算5）哈希表（1）哈希表的构造及查找运算（2）平均查找长度计算6）字符串的模式匹配（1）基本的模式匹配算法（2）KMP模式匹配算法（模式串的next函数计算）6.内部排序1）简单排序方法（1）直接插入排序算法（2）冒泡排序算法（3）简单选择排序算法（4）简单排序算法的时间复杂度、空间复杂度及稳定性分析2）快速排序（1）划分过程及分析（2）快速排序算法及其时间复杂度、空间复杂度及稳定性分析3）堆排序（1）堆的定义及初始堆的建立（2）堆排序算法及其时间复杂度、空间复杂度及稳定性分析4）归并排序（1）归并过程及分析（2）二路归并排序算法的时间复杂度、空间复杂度及稳定性分析5）基数排序（1）多关键排序方法（2）链式基数排序方法及特点6）内部排序方法的比较和应用（二）C语言程序设计1. C语言基础（1）数据类型（基本类型和复合类型），常量与变量，运算符与表达式，类型转换；（2）关键字（保留字），用户定义标识符；（3）typedef，sizeof，static，extern，const。
结构化程序设计方法的基本要点简介结构化程序设计方法是一种用于构建大型程序的系统性方法。
它通过将程序分解为一系列小的、可管理的模块，以及规定了模块之间的交互方式，从而降低程序的复杂性，提高程序的可维护性和可读性。
本文将从以下几个方面详细介绍结构化程序设计方法的基本要点。
1. 模块化模块化是结构化程序设计方法的核心思想之一。
模块化将程序分解为多个功能相对独立的模块，每个模块负责完成一个特定的任务。
模块化有助于提高程序的可读性，可维护性和可重用性。
1.1 模块划分在进行模块划分时，可以按照功能划分原则，将程序划分为几个不同的功能模块，每个模块负责完成一个特定的功能。
也可以按照数据划分原则，将程序划分为几个处理不同数据的模块。
模块应该具有清晰的职责和界限，不同模块之间的功能和数据交互应该通过接口进行。
1.2 接口设计模块之间的接口设计是模块化的关键。
接口应该明确定义模块之间的输入和输出，以及数据的传递方式。
良好的接口设计可以降低模块之间的耦合度，提高代码的可复用性，使得模块可以独立开发和测试。
1.3 函数与过程模块可以通过函数或过程来实现。
函数是一段可重用的代码，用于执行特定的计算或操作，并返回一个结果。
过程是一段可重用的代码，用于执行一系列操作，不返回结果。
函数和过程有助于将程序划分为更小的单元，提高程序的可读性和可维护性。
2. 控制结构控制结构是结构化程序设计方法的另一个重要要点。
控制结构用于控制程序的执行流程，改变程序的执行顺序或执行条件。
2.1 顺序结构顺序结构是程序从上到下按照顺序执行的控制结构。
顺序结构是程序的基础，所有的程序都是从顺序结构开始进行。
2.2 选择结构选择结构用于根据条件选择执行不同的代码块。
常见的选择结构包括if语句和switch语句。
if语句用于判断一个条件是否成立，如果条件成立，则执行其中的代码块；否则执行其他代码块。
switch语句可以根据一个表达式的值选择执行不同的代码块。
什么是程序设计意思与概念程序设计是一门关于编写计算机程序的学科，它涉及到定义、设计和实现算法和数据结构，以及编写、测试和维护这些计算机程序的过程。
程序设计是计算机科学的重要组成部分，也是计算机软件开发中的核心环节。
本文将介绍程序设计的意义和基本概念。
一、程序设计的意义程序设计在日常生活和工作中扮演着重要的角色，它的意义主要体现在以下几个方面。
1. 自动化处理：程序设计可以让计算机完成各种复杂的任务和处理过程，实现自动化处理。
例如，我们可以设计一个程序来自动化处理大量的数据，提高工作效率。
2. 解决实际问题：通过程序设计，我们可以解决和改进许多实际问题。
例如，我们可以利用程序设计实现在线购物、在线支付等功能，方便人们日常生活。
3. 提高效率和精确度：通过程序设计，可以使计算机以更高的速度和更高的准确性处理数据和任务，从而提高工作效率和精确度。
二、程序设计的基本概念1. 算法：算法是程序设计的基础，它是由一系列明确指令组成的计算步骤序列，用于解决特定问题或完成特定任务。
一个好的算法应该具有清晰、可执行和高效的特点。
2. 数据结构：数据结构是程序设计中用于组织和存储数据的方式。
常见的数据结构包括数组、链表、栈、队列、树和图等。
不同的数据结构适用于不同的应用场景，选择合适的数据结构可以提高程序的运行效率和可扩展性。
3. 编程语言：编程语言是进行程序设计的工具，它是一种用于定义和组织计算机程序的规范或语法。
常见的编程语言包括C、C++、Java、Python等。
不同的编程语言适用于不同的应用领域，选择合适的编程语言可以提高编程效率和程序性能。
4. 软件开发过程：软件开发过程是指从需求分析到软件发布的整个过程。
它包括需求分析、系统设计、编码实现、测试和维护等阶段。
良好的软件开发过程可以提高软件质量和开发效率。
5. 调试和错误处理：在程序设计过程中，出现错误是常见的。
调试和错误处理是程序设计中重要的环节，它们用于找出程序中的错误并对其进行修复。
程序设计基本概念程序设计是计算机科学的核心领域之一，它涉及到如何编写、测试和维护被计算机执行的指令序列。
程序设计的基本概念包括算法、数据结构、编程语言和软件开发流程等。
一、算法算法是解决问题的一系列步骤或规则。
在程序设计中，算法描述了解决特定问题的方法。
一个好的算法应当具备清晰、可执行、高效和正确性的特点。
清晰：算法的描述应当清晰明了，便于程序员理解和实现。
可执行：算法应当能够被转化为具体的计算机指令，才能被电脑执行。
高效：算法应当在合理的时间范围内完成任务，而不是消耗大量的计算资源。
正确性：算法应当能够正确地解决问题，符合预期的结果。
二、数据结构数据结构是程序设计中封装数据和操作的方式。
常见的数据结构包括数组、链表、栈、队列、树和图等。
选择合适的数据结构对于解决问题和提高程序的效率非常重要。
数组：用于存储一组固定大小的元素，访问元素的时间复杂度为O(1)。
链表：由节点组成，每个节点包含数据和指向下一个节点的引用，支持高效的插入和删除操作。
栈：后进先出的数据结构，支持压栈和弹栈操作。
队列：先进先出的数据结构，支持入队和出队操作。
树：由节点组成，每个节点可以有多个子节点，常用于快速搜索和排序。
图：由节点和边组成，用于表示多对多的关系。
三、编程语言编程语言是程序员与计算机之间进行沟通的桥梁，它定义了一套语法和语义规则。
常见的编程语言包括C、C++、Java、Python和JavaScript等。
选择合适的编程语言取决于问题的复杂度、语言的特性和个人经验等。
C语言：低级别、高效的编程语言，广泛应用于操作系统和底层开发。
C++语言：面向对象的扩展C语言，支持更高级的抽象和模块化。
Java语言：跨平台的编程语言，具有良好的可移植性和安全性。
Python语言：简洁易读的解释型语言，适合快速开发和原型设计。
JavaScript语言：主要用于前端开发，处理网页交互和动态效果。
四、软件开发流程软件开发流程是指将程序设计从概念阶段转化为可执行程序的一系列步骤。
第 1 章 绪 论1.1 数据结构的兴起和发展一、数据结构起源于程序设计。
·程序设计的新问题：应如何组织待处理的数据以及数据之间的关系（结构）。
·70年代初，数据结构作为一门独立的课程开始进入大学课堂。
二、数据结构随着程序设计的发展而发展。
程序设计经历了三个阶段：无结构阶段、结构化阶段和面向对象阶段，相应地，数据结构的发展也经历了三个阶段：三、数据结构的发展并未终结。
1． 数据结构将继续随着程序设计的发展而发展；2． 面向各专门领域的数据结构得到研究和发展，各种空间数据结构也在探索中。
应用领域：科学计算；程序设计面向计算机 应用领域：科学计算与非数值处理；算法＋数据结构=程序 应用领域：更多地应用于非数值处理；（算法＋数据结构）=程序1.2 数据结构的研究对象例1-1 学籍管理问题例1-2 人——机对弈问题例1-3 教学计划编排问题表1-1 学生学籍登记表 (a) 井字棋的一个格局 (b) 对弈树的局部 图1-2 对弈问题中格局之间的关系1.3 数据结构的基本概念1.3.1 数据结构1. 数据：在计算机科学中是指所有能输入到计算机中并能被计算机程序识别和处理的符号集合。
2. 数据元素：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
构成数据元素的不可分割的最小单位称为数据项。
3. 数据对象：是具有相同性质的数据元素的集合，是数据的子集。
4. 数据结构：是指相互之间存在一定关系的数据元素的集合。
按照视点的不同，数据结构分为逻辑结构和存储结构。
数据的逻辑结构是指数据元素之间逻辑关系的整体。
根据数据元素之间逻辑关系的不同，数据结构分为四类：⑴集合数据元素之间的关系是。
⑵线性结构数据元素之间的关系是。
⑶树结构数据元素之间的关系是。
⑷图结构数据元素之间的关系是。
数据的存储结构又称为物理结构，是数据及其逻辑结构在计算机中的表示。
有两种存储结构：顺序存储结构和链接存储结构。
黄河科技学院课程设计 1 《数据结构》课程设计 题 目：确定任两个交通站点间最短路径的算法及实现
姓 名： 学 院： 信息工程学院 专 业： 12级计科 班 级： 物联网工程 学 号： 指导教师： 叶茂功
2014年6月10日 黄河科技学院课程设计
2 确定任两个交通站点间最短路径的算法及实现 摘要：在纷繁复杂的城市公交网中，如果想寻找到一条从当前某
个站点到达另一个目的站点的最短路径，应该怎样实现呢？针对这个问题，采用数据结构中最短路径的思想进行了思考和研究，并采用(Floyd)算法来实现搜寻计算操作和过程. 黄河科技学院课程设计
3 目录 一 课题分析 ........................................................................................................ 4 设计要求............................................................................................................ 4 一、 目的 ..................................................................................................... 4 二、实验内容............................................................................................................ 4 三、数据结构及算法思想 ................................................................................. 4 四、弗洛伊德（Floyd)算法流程 ....................................................................... 5 五、基本需求 ..................................................................................................... 5 六、程序设计 .................................................................. 错误！未定义书签。 七、运行及调试结果 ......................................................................................... 9 八、总结............................................................................................................ 10 参考文献........................................................................................................ 10 黄河科技学院课程设计
4 设计要求
一、目的 1、掌握图的基本存储方法； 2、掌握有关图的操作算法并用高级语言实现； 3、熟练掌握图的两种搜索路径的遍历方法。
二、实验内容 假设以一个带权有向图表示某一区域的公交线路网，图中5个顶点代表区域中的重要交通站点，弧代表已有的公交线路，弧上的权表示该线路上的距离（或搭乘所需时间），试设计一个交通指南系统，指导前来咨询者以最短的距离（或最少的时间）从区域中的某一交通站点到达另一交通站点。 三、数据结构及算法思想
用Floyd求每对顶点之间最短路径算法解决，矩阵A用来进行n次迭代的数值，矩阵P用来记录路径，P[i][j]为迭代过程中当前已经求得的从顶点i到顶点j的最短路径上最后被插入的那个顶点。
黄河科技学院课程设计
5 四、弗洛伊德（Floyd）算法流程
五、基本需求 1.建立交通网络图的存储结构； 2.单元最短路径问题； 3．实现两个交通站点间的最短路径问题
开始 初始化距离和路径
设Di,j,k为从i到j的只以（1…k）集合中的节点为中间节点的最短路径的长度
Di,j,k=Di,k,k-1+Dk,j,k-1
Di,j,k=min(Di,k,k-1+Dk,j,k-1,Di,j,k-1)
Di,j,k=Di,j,k-1
最短路径不过 点 k 最短路径过点k 黄河科技学院课程设计
6 六、程序设计
#define m 9 #define MaxNum 999 /*定义一个最大数*/ #include /* 定义邻接矩阵类型 */ typedef int adjmatrix[m][m]; /* 建立图的邻接矩阵 */ void CreatMatrix(adjmatrix G,int n) {int i,j,k,t,e,arcnum; printf("请输入图的类型0-无向图，1-有向图"); scanf("%d",&t); for(i=0;ifor(j=0;j if(i==j) G[i][j]=0; /*对角线的值置为0*/ else G[i][j]=MaxNum; /*其它位置的值初始化为一个最大数*/ printf("请输入边(弧)的条数(%d-%d):",n-1,n*(n-1)/(2-t)); scanf("%d",&arcnum); printf("请输入边的信息,按照起点(1-5) 终点(1-5) 权值的形式输入:\n"); for(k=0;k{scanf("%d %d %d",&i,&j,&e); 黄河科技学院课程设计 7 if(t==0) G[j-1][i-1]=G[i-1][j-1]=e; else G[i-1][j-1]=e; } } /*弗洛伊德算法*/ void Floyd(int G[m][m], int A[m][m], int P[m][m],int n) { int i, j, k; for (i=0; ifor(j=0;j{A[i][j]=G[i][j];P[i][j]=0;} for (k=0; kfor (i=0; ifor (j=0; jif(A[i][k] +A[k][j]{ A[i][j]=A[i][k]+A[k][j]; P[i][j]=P[i][k]*10+P[k][j]*10+k+1; } } void main(){ int i,j,n; adjmatrix G,A,P; printf("交通站点的个数(2-9)"); 黄河科技学院课程设计 8 scanf("%d",&n); CreatMatrix(G,n); Floyd(G, A, P,n); printf("原图的临界矩阵\n"); for(i=0;i{for(j=0;jprintf("%3d",G[i][j]); printf("\n");} printf("两点间的距离\n"); for(i=0;i{for(j=0;jprintf("%3d",A[i][j]); printf("\n");} printf("两点间路径的中介点\n"); for(i=0;i{for(j=0;jprintf("%3d",P[i][j]); printf("\n");} } 黄河科技学院课程设计
9 七、运行及调试结果 5
2交通站点
3交通站点
1交通站点
5交通站点
4交通站点
4 4 2 6 5
3 3 黄河科技学院课程设计
10 八、总结
通过这次数据结构试验，我学习会了关于图的操作弗洛伊德（Floyd）算法，运用所学的知识实现了两个交通站点间最短路径的算法。更重要的是通过这次实践操作学会了完成一个设计的基本方法和步骤，拿到一个问题不能急于开始书写代码要将问题理清楚、找清思路、分好模块再开始敲代码，代码只是实现一个功能的工具，只有好的解决问题的思路，才能做出好的程序。写完一个程序，只是完成一个设计的一小部分，后期的调试和验证也是重要的一部分，这次设计完成代码后编译都没错，但运行结果却不正确，通过调试后才的找出错误，运行成功，但经过一些数据的验证却又发现问题，再经过改正和完善代码才完成整个设计。通过这次实验，又明白了许多道理，知道要想学好数据结构这门课，必须付出自己的努力和汗水，这样才能学有所得，相信在以后的实验中，自己会做得更加得心应手，更加的顺利。
参考文献 [1] 严蔚敏,吴伟民.数据结构（C语言版）[M].北京:清华大学出版社,2009. [2] 谭浩强.C程序设计[M]. 北京:清华大学出版社,2005. [3] 余孟尝.数字电子技术基础简明教程[M].北京:高等教育出版社,2009.
