数据结构与算法-大作业(1)

数据结构与算法初步大作业院别电子信息工程学院专业电子信息工程班级电子信息工程1班学号姓名教师郑国杰西安思源学院电信学院编制实验序号： 1 实验名称：用栈完成算术表达式求值一、实验预备知识1.复习C语言种的编写函数的相关内容。

2.复习栈的运算。

二、实验目的1.用栈结构完成一个算法：可以计算较复杂的数学中缀表达式。

三、实验要求1.编写创建并初始化栈的算法。

2.编写对输入的较复杂的数学中缀表达式进行计算的算法3.编写主函数，将上面的函数连接在一起，构成一个完整的程序。

4.将实验源程序调试并运行，写入输入、输出结果，并对结果进行分析。

四、实验步骤栈的应用实验内容：1.编写能将较为复杂的数学中缀表达式通过栈运算的方式，进行正确计算的函数。

2.由键盘输入“ (62+95)*106-1024/768*(3972-2436) ”3.计算得到正确的结果五、程序调试过程（列出程序清单，写出运行结果，运行结果截图）#include<stdio.h>#include<stdlib.h>#include<math.h>#define Maxsize 20typedef struct SqStack1{ float stack[Maxsize];int top;}SeqStack1;typedef struct SqStack2{ char stack[Maxsize];int top;}SeqStack2;void InitStack1(SeqStack1 *s){ s->top=-1; }void InitStack2(SeqStack2 *s){ s->top=-1; }void push1(SeqStack1 *s,float item) { if(s->top==Maxsize-1){ printf("数字栈满了\n");system("pause");exit(1);}s->top++;s->stack[s->top]=item;}void push2(SeqStack2 *s,char item) { if(s->top==Maxsize-1){printf("符号栈满了\n");system("pause");exit(1);}s->top++;s->stack[s->top]=item;}float Pop1(SeqStack1 *s){ char panduan;if(s->top==-1){ printf("数字栈是空的\n");system("pause");exit(1);}s->top--;return s->stack[s->top+1];}char Pop2(SeqStack2 *s){char panduan;if(s->top==-1){ printf("符号栈是空的\n");system("pause");exit(1);}s->top--;;return s->stack[s->top+1];}char GetTop(SeqStack2 *s){char panduan;if(s->top==-1){printf("符号栈是空的，没有第一个\n");system("pause");exit(1);}return s->stack[s->top];}int main(){ int i=0,j;float x;char fuhao,luru[30];SeqStack1 *s1;SeqStack2 *s2;s1=(struct SqStack1*)malloc(sizeof(struct SqStack1));s2=(struct SqStack2*)malloc(sizeof(struct SqStack2));InitStack1(s1);InitStack2(s2);printf("请输入计算式:");scanf("%s",luru);for(j=0;luru[j]!='\0';j++);//用j表示luru数组的长度luru[j]=';';luru[j+1]='\0';push2(s2,';');while(luru[i]){ if(luru[i]>=48&&luru[i]<=58){push1(s1,atof(luru+i));}while(luru[i]>=48&&luru[i]<=58||luru[i]=='.'){i++;}switch(luru[i]){case '+': if(GetTop(s2)==';'||GetTop(s2)=='(')push2(s2,luru[i]);else {x=Pop1(s1);fuhao=Pop2(s2);if(fuhao=='+')x=x+Pop1(s1);else if(fuhao=='-')x=Pop1(s1)-x;else if(fuhao=='*')x=x*Pop1(s1);else if(fuhao=='/')x=Pop1(s1)/x;push1(s1,x);push2(s2,luru[i]);}break;case '-': if(GetTop(s2)==';'||GetTop(s2)=='(')push2(s2,luru[i]);else {x=Pop1(s1);fuhao=Pop2(s2);if(fuhao=='+')x=x+Pop1(s1);else if(fuhao=='-')x=Pop1(s1)-x;else if(fuhao=='*')x=x*Pop1(s1);else if(fuhao=='/')x=Pop1(s1)/x;push1(s1,x);push2(s2,luru[i]);}break;case '*': if(GetTop(s2)==';'||GetTop(s2)=='('||GetTop(s2)=='+'||GetTop(s2)=='-')push2(s2,luru[i]);else {x=Pop1(s1);fuhao=Pop2(s2);if(fuhao=='+')x=x+Pop1(s1);else if(fuhao=='-')x=Pop1(s1)-x;else if(fuhao=='*')x=x*Pop1(s1);else if(fuhao=='/')x=Pop1(s1)/x;push1(s1,x);push2(s2,luru[i]);}break;case '/': if(GetTop(s2)==';'||GetTop(s2)=='('||GetTop(s2)=='+'||GetTop(s2)=='-')push2(s2,luru[i]);else {x=Pop1(s1);fuhao=Pop2(s2);if(fuhao=='+')x=x+Pop1(s1);else if(fuhao=='-')x=Pop1(s1)-x;else if(fuhao=='*')x=x*Pop1(s1);else if(fuhao=='/')x=Pop1(s1)/x;push1(s1,x);push2(s2,luru[i]);}break;case ')': if(GetTop(s2)=='(')Pop2(s2);else {x=Pop1(s1);fuhao=Pop2(s2);if(fuhao=='+')x=x+Pop1(s1);else if(fuhao=='-')x=Pop1(s1)-x;else if(fuhao=='*')x=x*Pop1(s1);else if(fuhao=='/')x=Pop1(s1)/x;push1(s1,x);push2(s2,luru[i]);}break;case '(': push2(s2,luru[i]);break;case ';':while(GetTop(s2)!=';'){x=Pop1(s1);fuhao=Pop2(s2);if(fuhao=='+')x=x+Pop1(s1);else if(fuhao=='-')x=Pop1(s1)-x;else if(fuhao=='*')x=x*Pop1(s1);else if(fuhao=='/')x=Pop1(s1)/x;push1(s1,x);}printf("%s\b=%f\n\n\n\n\n\n\n\t\t\t\t\t\t\t\t\n",luru,Pop1(s1));break;}i++;}system("pause");}六、总结检验1、是否达到实验目的？何处体现？答：达到实验目的，如上程序与截图，按要求得到正确答案。

数据结构与算法练习题+参考答案一、单选题（共100题，每题1分，共100分）1.手写板或鼠标属于：A、中央处理器B、输出设备C、存储器D、输入设备正确答案：D2.下列叙述中错误的是A、采用顺序存储的完全二叉树属于线性结构B、循环队列属于线性结构C、具有多个指针域的链表也可能是线性结构D、具有两个以上根结点的数据结构一定是非线性结构正确答案：A3.定义学生选修课程的关系模式如下：SC (S#, Sn, C#, Cn,G，Cr)（其属性分别为学号、姓名、课程号、课程名、成绩、学分）该关系可进一步归范化为A、S(S#,Sn)， C(C#,Cn,Cr)， SC(S#,C#,G)B、S(S#, Sn, C#,Cn,Cr)， SC(S#,C#,G)C、C(C#,Cn,Cr)， SC(S#,Sn,C#,G)D、S(S#,Sn)， C(C#,Cn)， SC(S#,C#,Cr,G)正确答案：A4.郭老师想要把已在Word 2010 中组织好的论文大纲应用到PowerPoint 2010 中生成一份演示文稿，最优的操作方法是：A、排列好窗口，对照 Word 中的大纲文字重新输入到 PowerPoint 中生成演示文稿B、在 PowerPoint 中，通过“插入”→“对象”命令，将 Word 文档插入到演示文稿中进行C、将 Word 中的大纲文字逐一复制到PowerPoint 中生成演示文稿D、通过“发送到Microsoft PowerPoint”命令直接生成演示文稿内容正确答案：D5.设二叉树的后序序列为 DGHEBIJFCA，中序序列为 DBGEHACIFJ。

则前序序列为A、ABDEGHCFIJB、JIHGFEDCBAC、GHIJDEFBCAD、ABCDEFGHIJ正确答案：A6.关系数据库中的键是指A、能唯一标识元组的属性或属性集合B、关系的名称C、关系的专用保留字D、关系的所有属性正确答案：A7.设循环队列的存储空间为 Q(1:m)，初始状态为空。

数据结构作业（1）年级：2004级（2）班专业：计算机科学与技术专业学号：200431500066姓名：秦博纯病人看病模拟程序编写一个程序，反映病人到医院看病，排队看医生的情况。

在病人排队过程中，主要重复两件事：1.病人到达诊室，将病历本交给护士，排到等待队列中候诊。

2.护士从等待队列中取出下一们病人的病历，该病人进入人诊室就诊。

要求模拟病人等待这一过程，程序采用菜单方式，其选项及功能说明如下：a.排队——输入排队病人的病历号，加入病人排队队列中;b.就诊——病人排队队列中最前面的病人就诊，并将其从队列中删除;c.查看排队——从队首到队尾列出所有的排队病人的病历号;d.不再排队，余下依次就诊——从队首到队尾列出所有的排队病人的病历号，并退出运行;e.下班——退出运行。

解：本项目的组成结构如图1所示，本程序的模块结构图如图2所示，图中方框表示函数，方框中指出函数名，箭头方向表示函数间的调用关系，虚线方框表示文件的组成，即指出该虚线方框中的函数存放在哪个文件中。

文件包含如下函数:. SeeDoctor():模拟病人看病的过程。

病人排队看医生，所以要用到一个队列，这里设计了一个不带头结点的单链表作为队列。

源程序如下：图1 项目组成#include<stdio.h>#include<malloc.h>typedef struct qnode{int data;struct qnode *next;}QNode;typedef struct{QNode *front,*rear;}QuType; 图2 项目的程序结构图void SeeDoctor(){int sel,flag=1,find,no;QuType *qu;QNode *p;qu=(QuType *)malloc(sizeof(QuType)); /*创建空队*/qu->front=qu->rear=NULL;while(flag==1) /*循环执行*/{printf("1:排队2：就诊3：查看排队4：不再排队，余下依次就诊5：下班请选择");scanf("%d",&sel);switch(sel){case 1:printf(">>输入病历号：");do{scanf("%d",&no);find=0;p=qu->front;while(p!=NULL&&!find){if(p->data==no)find=1;elsep=p->next;}if(find)printf(">>输入的病历号重复，重新输入：");}while(find==1);p=(QNode *)malloc(sizeof(QNode)); /*创建结点*/p->data=no;p->next=NULL;if(qu->rear==NULL) /*第一个病人排队*/ {qu->front=qu->rear=p;}else{qu->rear->next=p; /*将*p结点入队*/qu->rear=p;}break;case 2: /*队空*/ if(qu->front==NULL)printf(">>没有排队的病人!\n");else /*队不空*/{p=qu->front;printf(">>病人%d就诊\n",p->data);if(qu->rear==p) /*只有一个病人排队*/{qu->front=qu->rear=NULL;}elsequ->front=p->next;free(p);}break;case 3: /*队空*/ if(qu->front==NULL)printf(">>没有排列的病人!\n");else /*队不空*/{p=qu->front;printf(">>排队病人: ");while(p!=NULL){printf("%d ",p->data);p=p->next;}printf("\n");}break;case 4: /*队空*/ if(qu->front==NULL)printf(">>没有排队的病人!\n");else /*队不空*/{p=qu->front;printf(">>病人按以下顺序就诊: ");while(p!=NULL){printf("%d ",p->data);p=p->next;}printf("\n");}flag=0; /*退出*/break;case 5: /*队不空*/ if(qu->front!=NULL)printf(">>请排队的病人明天就医!\n");flag=0; /*退出*/break;}}}void main(){SeeDoctor();}程序运行结果如下：。

哈工大数据结构作业14./*升序创建两个含有整形数据的链表，其中Create函数中调用Insert函数实现升序排列。

再通过Combine函数将两个链表合并，用Print函数输出。

代码如下。

*/#include "stdafx.h"#include <iostream>struct node {int data ;struct node *next ;} ;using namespace std;node* Insert(node *head,node *n)/*数据插入,升序排列*/{node *p1,*p2;p1=p2=head;if(head==NULL){head=n;n->next=NULL;return head;}if(head->data>=n->data) //新结点插入首结点之前{n->next=head;head=n;return head;}//在首结点之后寻找位置插入新结点while(p2->next&&p2->data<n->data){p1=p2;p2=p2->next;}if(p2->data<n->data){p2->next=n;n->next=NULL;}else{n->next=p2;p1->next=n;}return head;}/*创建有序链表*/node * Create(void){node *head,*n;int a ;head=NULL;cout<<"升序插入法产生链表，请输入数据（-1结束）：\n";for(cin>>a;a!=-1;cin>>a){n=new node;n->data=a;head=Insert(head,n);}return head;}void Print( node *head){cout<<"链表的结点数据（升序）为：\n";while(head){cout<<head->data<<'\t';head=head->next;}}node * Combine(node *p,node *q){ node *hc,*pc;node *pa,*pb;pa=p->next;pb=q->next;hc=pc=p;while(pa&&pb){if(pa->data<=pb->data){pc->next=pa;pa=pa->next;pc=pc->next;}else {pc->next=pb;pb=pb->next;pc=pc->next;}}pc->next=pa?pa:pb;return hc;}int main(){node *ha,*hb,*hc;cout<<"链表a添加数据\n";ha=Create();cout<<"链表b添加数据\n";hb=Create();Print(ha);Print(hb);hc=Combine(ha,hb);Print(hc);return 0;}8.XSXXXSSSXXSXXSXXSSSS15.//设置链表结点：struct celltype{Elementtype element;celltype *next;int a; //在结点中设置一个int型a来表示链表元素总数};/*顺时针方向查找：即为普通单向链表的查找。

《数据结构与算法》习题与答案（解答仅供参考）一、名词解释：1. 数据结构：数据结构是计算机存储、组织数据的方式，它不仅包括数据的逻辑结构（如线性结构、树形结构、图状结构等），还包括物理结构（如顺序存储、链式存储等）。

它是算法设计与分析的基础，对程序的效率和功能实现有直接影响。

2. 栈：栈是一种特殊的线性表，其操作遵循“后进先出”（Last In First Out, LIFO）原则。

在栈中，允许进行的操作主要有两种：压栈（Push），将元素添加到栈顶；弹栈（Pop），将栈顶元素移除。

3. 队列：队列是一种先进先出（First In First Out, FIFO）的数据结构，允许在其一端插入元素（称为入队），而在另一端删除元素（称为出队）。

常见的实现方式有顺序队列和循环队列。

4. 二叉排序树（又称二叉查找树）：二叉排序树是一种二叉树，其每个节点的左子树中的所有节点的值都小于该节点的值，而右子树中的所有节点的值都大于该节点的值。

这种特性使得能在O(log n)的时间复杂度内完成搜索、插入和删除操作。

5. 图：图是一种非线性数据结构，由顶点（Vertex）和边（Edge）组成，用于表示对象之间的多种关系。

根据边是否有方向，可分为有向图和无向图；根据是否存在环路，又可分为有环图和无环图。

二、填空题：1. 在一个长度为n的顺序表中，插入一个新元素平均需要移动______个元素。

答案：(n/2)2. 哈希表利用______函数来确定元素的存储位置，通过解决哈希冲突以达到快速查找的目的。

答案：哈希（Hash）3. ______是最小生成树的一种算法，采用贪心策略，每次都选择当前未加入生成树且连接两个未连通集合的最小权重边。

答案：Prim算法4. 在深度优先搜索（DFS）过程中，使用______数据结构来记录已经被访问过的顶点，防止重复访问。

答案：栈或标记数组5. 快速排序算法在最坏情况下的时间复杂度为______。

一、选择题1.下列哪种数据结构适合用于实现优先队列？A.栈B.队列C.二叉堆（正确答案）D.链表2.在进行图的深度优先搜索（DFS）时，使用哪种数据结构可以帮助记录已访问过的顶点，从而避免重复访问？A.栈B.队列C.集合（正确答案）D.哈希表3.下列排序算法中，哪种算法的时间复杂度在最坏情况下为O(n2)，但在平均情况下和最好情况下可以达到O(nlogn)？A.快速排序（正确答案）B.归并排序C.堆排序D.插入排序4.在二叉树的遍历中，前序遍历的顺序是？A.根节点-> 左子树-> 右子树（正确答案）B.左子树-> 根节点-> 右子树C.左子树-> 右子树-> 根节点D.根节点-> 右子树-> 左子树5.下列哪种查找算法在有序数组中查找特定元素时，具有最优的时间复杂度O(logn)？A.顺序查找B.二分查找（正确答案）C.插值查找D.斐波那契查找6.在哈希表中，处理哈希冲突的一种常见方法是？A.开放寻址法（正确答案）B.链地址法C.再哈希法D.以上都是7.下列关于二叉搜索树（BST）的说法中，哪一项是正确的？A.在BST中，每个节点的左子树只包含小于该节点的数B.在BST中，每个节点的右子树只包含大于该节点的数C.在BST中，每个节点的左子树只包含小于该节点的数，右子树只包含大于该节点的数（正确答案）D.BST中不允许有重复值的节点8.下列哪种算法是解决最短路径问题的经典算法，适用于带权重的图？A.迪杰斯特拉算法（Dijkstra）（正确答案）B.弗洛伊德算法（Floyd）C.贝尔曼-福特算法（Bellman-Ford）D.A*算法（A-star）。

《数据结构与算法》作业说明：1、题号形式: 每题都以【sn，cha，sec】开头，sn表明本题的题目序号，每道题都有唯一的序号；cha表示内容所在的章；sec表示内容所在的节。

如【17，2，1】表示序号17的题来自第2章第1节。

2、题型：1) 选择题：序号1-180题2) 是非题：序号181-220题3) 分析计算作图题：序号221-250题（选自《数据结构题集》—严蔚敏等编）3、内容取舍：根据本学期上课课件中的内容，未上课章节的练习可舍弃。

4、必做题或选做题：是非题和选择题（序号1-220）只要在上过课的章节中都是必做题，分析计算作图题（序号221-250）在每题后标出是必做题还是选做题，其中16个必做题14个选做题。

1) 选择题：序号1-180题【1，1，1】数据结构形式地定义为（D，S），其中D是①B 的有限集合，S 是D上的②D 的有限集合。

① A. 算法 B. 数据元素 C. 逻辑结构 D. 数据操作② A. 结构 B. 操作 C. 存储 D. 关系【2，1，1】数据结构中，从逻辑上可以把数据结构分成① D 。

① A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构C. 内部结构和外部结构D. 线性结构和非线性结构【3，1，1】数据结构是研究数据的①C 以及它们之间的相互关系。

① A. 理想结构，物理结构 B. 理想结构，抽象结构（C）物理结构，逻辑结构（D）抽象结构，逻辑结构【4，1，1】数据的定义取决于数据的逻辑结构，而数据的实现取决于数据的物理结构。

A. 正确AB. 不正确【5，1，2】在数据结构中，与所使用的计算机无关的是数据的①C 结构。

① A.存储 B.物理 C.逻辑 D.物理与存储【6，1，3】数据结构课程主要研究以下三方面的内容，它们是①D 。

① A. 数据、数据元素、数据类型1B. 数据元素、数据类型、算法实现C. 数据元素、数据的逻辑结构、数据的存储结构D. 数据的逻辑结构、数据的存储结构、数据的运算【7，1，3】在下列叙述中，正确的是①C 。

《数据结构与算法实践》大作业设计一个校园导游程序，为来访的客人提供各种信息查询服务。

基本要求：（1）设计你所在学校的校园平面图，所含场所不少于10个。

以图中顶点表示校内各场所，存放场所名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。

（2）为来访客人提供图中任意场所相关信息的查询。

（3）为来访客人提供图中任意场所的问路查询，即查询任意两个景点之间的一条最短的简单路径。

（4）请绘制规范流程图（参考《C语言》第二章），附程序清单，及测试结果以及地图。

结果显示：程序代码：#include<stdio.h>#include<string>#include<iostream.h>#define fi 9999#define MAXVEX 10struct node{int num;string name;}xuhao[10];void Floyed(int cost[][MAXVEX],int n,int m,int x){int A [MAXVEX][MAXVEX],path[MAXVEX][MAXVEX];int i,j,k,pre;for(i=0;i<n;i++)for(j=0;j<n;j++){A[i][j]=cost[i][j];path[i][j]=-1;}for(k=0;k<n;k++){ for(i=0;i<n;i++)for(j=0;j<n;j++)if(A[i][j]>(A[i][k]+A[k][j])){A[i][j]=A[i][k]+A[k][j];path[i][j]=k;}}if(m!=x){cout << xuhao[m].name << " ———> " << xuhao[x].name << " ";if(A[m][x]==fi){if(m!=x)cout << "该路径不存在\n" << endl;}else{cout << "最短路径长度是:" << A[m][x] << "米";cout << "具体路径为:" << xuhao[m].name << "----";pre=path[m][x];while(pre!=-1){cout<<xuhao[pre].name << "----";pre=path[pre][x];}cout<<xuhao[x].name<<endl;}}}void main(){ int i,k,l,x;;cout << "宁波大学科学技术学院及周边平面图介绍:" << endl;cout << " 序号———名称——————简介—————————" << endl;cout << " 0 校门口学生、教师进出" << endl;cout << " 1 一号实验楼机房供学生做实验" << endl;cout << " 2 二号实验楼英语听力教室及舞蹈房" << endl;cout << " 3 综合楼老师办公楼/图书馆/机房" << endl;cout << " 4 三号教学楼上课，自习" << endl;cout << " 5 二号教学楼上课，自习" << endl;cout << " 6 一号教学楼上课，自习" << endl;cout << " 7 宁大西区成教学院" << endl;cout << " 8 操场在建中" << endl;cout << " 9 学生村二村学生生活区" << endl;cout<<endl;xuhao[0].num=0;xuhao[0].name="校门口";xuhao[1].num=1;xuhao[1].name="一号实验楼";xuhao[2].num=2;xuhao[2].name="二号实验楼";xuhao[3].num=3;xuhao[3].name="综合楼";xuhao[4].num=4;xuhao[4].name="三号教学楼";xuhao[5].num=5;xuhao[5].name="二号教学楼";xuhao[6].num=6;xuhao[6].name="一号教学楼";xuhao[7].num=7;xuhao[7].name="宁大西区";xuhao[8].num=8;xuhao[8].name="操场";xuhao[9].num=9;xuhao[9].name="学生村二村";cout <<"输入你要查询的起始地点的序号:";cin >> k;cout << k << "\t" << xuhao[k].name << endl;cout << "输入你要查询的终止地点的序号:";cin>>x;cout << x << "\t" << xuhao[x].name << endl;cout << "以下是从" << xuhao[k].name << "出发到" << xuhao[x].name << "其他地方的最短路径：" << endl ;int cost[10][MAXVEX]={{0,100,100,150,fi,fi,fi,fi,fi,150},{100,0,150,100,130,fi,fi,fi,fi,fi},{100,150,0,100,fi,fi,fi,fi,200,fi},{150,100,100,0,50,fi,fi,fi,fi,fi},{fi,130,fi,50,0,20,fi,fi,fi,fi},{fi,fi,fi,fi,20,0,20,fi,fi,fi} ,流程图：开始学生村二村（9）学生村二村（9）起始序号=>k终止序号=>x输出最短路径长度输出具体路径结束100。