北工大(数据结构)报告

上机题三报告姓名:学号：完成日期：2015年5月5日题目：表达式可以用表达式二义树来表示。

对于简单的四则运算表达式，请实现以下功能；（1）对于任意给出的前缀表达式（不带括号）、中缀表达式（可以带括号）或后缀表达式（不带括号），能够在计算机内部构造出一棵表达式二义树，并且以图示显示出来（字符图或图形的形式）。

（2）对于构造好的内部表达式二叉树，按照用户要求，输出相应的前缀表达式（不带括号）、中缀表达式（可以带括号）或后缀表达式（不带括号）.一、需求分析1.输入形式、输入值的范围；输入前缀表达式（不带括号）、中缀表达式（可以带括号）或后缀表达式（不带括号）2.输出形式^表达式二叉树，前缀表达式、中缀表达式和后缀表达式。

3・程序功能；用表达式二叉树表示表达式，并转换为前缀表达式、中缀表达式或后缀表达式。

4.测试数据正确的输入输出：错误的输入输出:二、概要设计1. ADT定义class TNode//W 点类3.各程序模块间的调用关系2.主程序流程Main ()求二叉树表达式模块求前、中、后缀表达式模块打印树删除树三、详细设计1.实现ADT定义的数据类型class TNode//节点类{ public:char oper;//数据域，为简便起见，操作数用单个字符代替TNode *left;TNode *right;int s;int t;〃计算树的层数使用TNode()//缺省构造函数{ left 二right二NULL;opei-O;}TNode(char op)//赋值构造函数{ left 二right 二NULL;opei-op;}1；2.算法描述表达式转化为二叉树void pre2tree(TNode *&p, string str)//#缀表达式生成二叉树{ 碰到操作数则把英值赋给相应的新申请的二叉树结点，地址压栈：碰到操作符则把其值赋给相应的新申请的二叉树，并从栈中弹出两个地址，分别作为英左指针和右指针，然后再把其地址压栈，最后一个地址即为二叉树的根结点地址。

《数据结构》实验报告模板(附实例)---实验一线性表的基本操作实现实验一线性表的基本操作实现及其应用一、实验目的1、熟练掌握线性表的基本操作在两种存储结构上的实现，其中以熟悉各种链表的操作为重点。

2、巩固高级语言程序设计方法与技术，会用线性链表解决简单的实际问题。

二、实验内容√ 1、单链表的表示与操作实现 ( * )2、约瑟夫环问题3、Dr.Kong的艺术品三、实验要求1、按照数据结构实验任务书，提前做好实验预习与准备工作。

2、加“*”题目必做，其他题目任选；多选者并且保质保量完成适当加分。

3、严格按照数据结构实验报告模板和规范，及时完成实验报告。

四、实验步骤（说明：依据实验内容分别说明实验程序中用到的数据类型的定义、主程序的流程以及每个操作（成员函数）的伪码算法、函数实现、程序编码、调试与分析、总结、附流程图与主要代码）㈠、数据结构与核心算法的设计描述（程序中每个模块或函数应加注释，说明函数功能、入口及出口参数）1、单链表的结点类型定义/* 定义DataType为int类型 */typedef int DataType;/* 单链表的结点类型 */typedef struct LNode{ DataType data;struct LNode *next;}LNode,*LinkedList;2、初始化单链表LinkedList LinkedListInit( ){ // 每个模块或函数应加注释，说明函数功能、入口及出口参数 }3、清空单链表void LinkedListClear(LinkedList L){// 每个模块或函数应加注释，说明函数功能、入口及出口参数}4、检查单链表是否为空int LinkedListEmpty(LinkedList L){ …. }5、遍历单链表void LinkedListTraverse(LinkedList L){….}6、求单链表的长度int LinkedListLength(LinkedList L){ …. }7、从单链表表中查找元素LinkedList LinkedListGet(LinkedList L,int i){ //L是带头结点的链表的头指针，返回第 i 个元素 }8、从单链表表中查找与给定元素值相同的元素在链表中的位置LinkedList LinkedListLocate(LinkedList L, DataType x){ …… }9、向单链表中插入元素void LinkedListInsert(LinkedList L,int i,DataType x) { // L 为带头结点的单链表的头指针，本算法// 在链表中第i 个结点之前插入新的元素 x}10、从单链表中删除元素void LinkedListDel(LinkedList L,DataType x){ // 删除以 L 为头指针的单链表中第 i 个结点 }11、用尾插法建立单链表LinkedList LinkedListCreat( ){ …… }㈡、函数调用及主函数设计（可用函数的调用关系图说明）㈢程序调试及运行结果分析㈣实验总结五、主要算法流程图及程序清单1、主要算法流程图：2、程序清单（程序过长，可附主要部分）说明：以后每次实验报告均按此格式书写。

一、实验名称数据结构实验二：链表的基本操作二、实验目的1. 理解链表的基本概念和结构。

2. 掌握链表的创建、插入、删除、查找等基本操作。

3. 提高编程能力，巩固数据结构知识。

三、实验环境1. 操作系统：Windows 102. 编程语言：C++3. 开发环境：Visual Studio 2019四、实验原理链表是一种常见的线性数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。

链表具有以下特点：1. 无固定长度，可以根据需要动态地添加或删除节点。

2. 链接方式灵活，便于实现各种操作。

3. 适合存储具有动态变化的数据。

本实验主要实现以下功能：1. 创建链表：根据用户输入的数据，创建一个单链表。

2. 插入节点：在链表的指定位置插入一个新节点。

3. 删除节点：删除链表中的指定节点。

4. 查找节点：在链表中查找一个指定的节点。

5. 打印链表：遍历链表并打印所有节点数据。

五、实验步骤1. 创建链表```cppstruct ListNode {int data;ListNode next;ListNode(int x) : data(x), next(nullptr) {}};ListNode createList() {ListNode head = nullptr, tail = nullptr;int data;cout << "请输入链表数据（输入-1结束）：" << endl; while (cin >> data && data != -1) {ListNode node = new ListNode(data);if (head == nullptr) {head = node;tail = node;} else {tail->next = node;tail = node;}}return head;}```2. 插入节点```cppvoid insertNode(ListNode head, int data, int position) { ListNode node = new ListNode(data);if (position == 0) {node->next = head;head = node;} else {ListNode current = head;for (int i = 0; i < position - 1; ++i) {if (current == nullptr) {cout << "插入位置超出链表长度！" << endl; return;}current = current->next;}node->next = current->next;current->next = node;}}```3. 删除节点```cppvoid deleteNode(ListNode head, int position) {if (head == nullptr) {cout << "链表为空！" << endl;return;}if (position == 0) {ListNode temp = head;head = head->next;delete temp;} else {ListNode current = head;for (int i = 0; i < position - 1; ++i) {if (current == nullptr) {cout << "删除位置超出链表长度！" << endl; return;}current = current->next;}if (current->next == nullptr) {cout << "删除位置超出链表长度！" << endl;return;}ListNode temp = current->next;current->next = temp->next;delete temp;}}```4. 查找节点```cppListNode findNode(ListNode head, int data) { ListNode current = head;while (current != nullptr) {if (current->data == data) {return current;}current = current->next;}return nullptr;}```5. 打印链表```cppvoid printList(ListNode head) {ListNode current = head;while (current != nullptr) {cout << current->data << " ";current = current->next;}cout << endl;}```六、实验结果与分析通过以上步骤，成功实现了链表的基本操作。

一、实验背景数据结构是计算机科学中一个重要的基础学科，它研究如何有效地组织和存储数据，并实现对数据的检索、插入、删除等操作。

为了更好地理解数据结构的概念和原理，我们进行了一次数据结构实训实验，通过实际操作来加深对数据结构的认识。

二、实验目的1. 掌握常见数据结构（如线性表、栈、队列、树、图等）的定义、特点及操作方法。

2. 熟练运用数据结构解决实际问题，提高算法设计能力。

3. 培养团队合作精神，提高实验报告撰写能力。

三、实验内容本次实验主要包括以下内容：1. 线性表（1）实现线性表的顺序存储和链式存储。

（2）实现线性表的插入、删除、查找等操作。

2. 栈与队列（1）实现栈的顺序存储和链式存储。

（2）实现栈的入栈、出栈、判断栈空等操作。

（3）实现队列的顺序存储和链式存储。

（4）实现队列的入队、出队、判断队空等操作。

3. 树与图（1）实现二叉树的顺序存储和链式存储。

（2）实现二叉树的遍历、查找、插入、删除等操作。

（3）实现图的邻接矩阵和邻接表存储。

（4）实现图的深度优先遍历和广度优先遍历。

4. 算法设计与应用（1）实现冒泡排序、选择排序、插入排序等基本排序算法。

（2）实现二分查找算法。

（3）设计并实现一个简单的学生成绩管理系统。

四、实验步骤1. 熟悉实验要求，明确实验目的和内容。

2. 编写代码实现实验内容，对每个数据结构进行测试。

3. 对实验结果进行分析，总结实验过程中的问题和经验。

4. 撰写实验报告，包括实验目的、内容、步骤、结果分析等。

五、实验结果与分析1. 线性表（1）顺序存储的线性表实现简单，但插入和删除操作效率较低。

（2）链式存储的线性表插入和删除操作效率较高，但存储空间占用较大。

2. 栈与队列（1）栈和队列的顺序存储和链式存储实现简单，但顺序存储空间利用率较低。

（2）栈和队列的入栈、出队、判断空等操作实现简单，但需要考虑数据结构的边界条件。

3. 树与图（1）二叉树和图的存储结构实现复杂，但能够有效地表示和处理数据。

《数据结构与算法统计》实验报告——实验三一、实验目的1. 熟悉VC环境，掌握对二叉树的基本操作。

2. 在上机、调试的过程中，加强对二叉树的理解和运用。

3. 复习线性链表和递归4. 锻炼动手编程和独立思考的能力。

二、实验内容遍历二叉树。

请输入一棵二叉树的扩展的前序序列，经过处理后生成一棵二叉树，然后对于该二叉树输出前序、中序和后序遍历序列。

三、程序设计1、概要设计本程序包含三个模块：1.构造二叉树模块2.遍历二叉树模块3.主程序模块采用二叉链表作为存储结构。

（1）二叉树的抽象数据类型定义为：ADT BinaryTree {数据对象D：D是具有相同特性的数据元素的集合。

数据关系R：若D=Φ，则R=Φ，称BinaryTree为空二叉树；若D≠Φ，则R={H}，H是如下二元关系；（1）在D中存在惟一的称为根的数据元素root，它在关系H下无前驱；（2）若D-{root}≠Φ，则存在D-{root}={D1,Dr}，且D1∩Dr =Φ；（3）若D1≠Φ，则D1中存在惟一的元素x1，<root,x1>∈H，且存在D1上的关系H1 ⊆H；若Dr≠Φ，则Dr中存在惟一的元素xr，<root,xr>∈H，且存在上的关系Hr ⊆H；H={<root,x1>,<root,xr>,H1,Hr}；（4）(D1,{H1})是一棵符合本定义的二叉树，称为根的左子树；(Dr,{Hr})是一棵符合本定义的二叉树，称为根的右子树。

基本操作：CreatBiTree(BiTree &T)操作结果：按先序次序建立二叉链表表示的二叉树TPreOrderTraverse(BiTree T,int (*visit)(char e))初始条件：二叉树T已经存在，visit是对结点操作的应用函数操作结果：先序遍历二叉树T ，对每个结点调用visit函数仅一次；一旦visit（）失败，则操作失败。

实验一：约瑟夫环问题一．实验目的：要求设计一个程序模拟约瑟夫环问题过程，求出出列编号序列。

二．实验内容：约瑟夫环问题：设编号为1，2，3，……，n的n(n>0)个人按顺时针方向围坐一圈，每个人持有一个正整数密码。

开始时任选一个正整数做为报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m是停止报数，报m的人出列，将他的密码作为新的m值，从他的下一个人开始重新从1报数。

如此下去，直到所有人全部出列为止。

令n最大值取30。

要求设计一个程序模拟此过程，求出出列编号序列。

三．实验过程：用一个不带头结点的循环链表来处理Josephu 问题：先构成一个有n个结点的单循环链表，然后由k结点起从1开始计数，计到m时，对应结点从链表中删除，把被删除结点的密码作为新的m值，然后再从被删除结点的下一个结点又从1开始计数，直到最后一个结点从链表中删除算法结束。

#include<stdio.h>#include<stdlib.h>#define MAX_NODE_NUM 30#define TRUE 1#define FALSE 0typedef struct NodeType{ int number;int password;struct NodeType *next;} NodeType;/* 创建单向循环链表*/static void CreaList(NodeType **, const int);/* 运行"约瑟夫环"问题*/static void StatGame(NodeType **, int);/* 打印循环链表*/static void PrntList(const NodeType *);/* 得到一个结点*/static NodeType *GetNode(const int, const int);/* 测试链表是否为空, 空为TRUE，非空为FALSE */static unsigned EmptyList(const NodeType *);int main(void){ int n, m;NodeType *pHead=NULL;while(1){printf("输入总的人数n(<=%d):",MAX_NODE_NUM);scanf("%d",&n);printf("初始循环的密码为:");scanf("%d",&m);if(n>MAX_NODE_NUM){printf("数字太大，请重新输入!\n");continue;}elsebreak;}CreaList(&pHead,n);printf("\n打印出原始每个结点的序列号和密码\n"); PrntList(pHead);printf("\n最终每个结点退出的序列号和密码\n"); StatGame(&pHead,m);return 0;}static void CreaList(NodeType **ppHead, const int n){int i,iCipher;NodeType *pNew, *pCur;for(i=1;i<=n;i++){printf("第%d个人的密码为:",i);scanf("%d", &iCipher);pNew=GetNode(i,iCipher);if(*ppHead==NULL){*ppHead=pCur=pNew;pCur->next=*ppHead;}else{pNew->next=pCur->next;pCur->next=pNew;pCur=pNew;}}printf("已完成结点初始化!\n");}static void StatGame(NodeType **ppHead, int iCipher){int iCounter, iFlag=1,i=1;NodeType *pPrv, *pCur, *pDel;pPrv=pCur=*ppHead;while(pPrv->next!=*ppHead)pPrv=pPrv->next;while(iFlag){for(iCounter=1;iCounter<iCipher;iCounter++){pPrv=pCur;pCur=pCur->next;}if(pPrv==pCur)iFlag=0;pDel=pCur;pPrv->next=pCur->next;pCur=pCur->next;iCipher=pDel->password;printf("第%d个退出的是序列号为%d的人,其密码为:%d\n",i, pDel->number,pDel->password);free(pDel);++i;}*ppHead=NULL;}static void PrntList(const NodeType *pHead){const NodeType *pCur=pHead;if (EmptyList(pHead))return;do{printf("第%d 个人,密码:%d\n",pCur->number,pCur->password);pCur=pCur->next;} while (pCur!=pHead);}static NodeType *GetNode(const int iId,const int iCipher){NodeType *pNew;pNew=(NodeType *)malloc(sizeof(NodeType));if(!pNew){printf("错误，内存不足!\n");exit(-1);}pNew->number=iId;pNew->password=iCipher;pNew->next=NULL;return pNew;}static unsigned EmptyList(const NodeType *pHead){if(!pHead){printf("列表为空!\n");return TRUE;}return FALSE;}参考至“百度文库”《C语言约瑟夫环问题》收获：学会了创建循环链表及相关操作，巩固了线性链表的知识。

数据结构实验报告一、实验目的数据结构是计算机科学中非常重要的一门课程，通过本次实验，旨在加深对常见数据结构（如链表、栈、队列、树、图等）的理解和应用，提高编程能力和解决实际问题的能力。

二、实验环境本次实验使用的编程语言为C+＋，开发工具为Visual Studio 2019。

操作系统为 Windows 10。

三、实验内容1、链表的实现与操作创建一个单向链表，并实现插入、删除和遍历节点的功能。

对链表进行排序，如冒泡排序或插入排序。

2、栈和队列的应用用栈实现表达式求值，能够处理加、减、乘、除和括号。

利用队列实现银行排队系统的模拟，包括顾客的到达、服务和离开。

3、二叉树的遍历与操作构建一棵二叉树，并实现前序、中序和后序遍历。

进行二叉树的插入、删除节点操作。

4、图的表示与遍历用邻接矩阵和邻接表两种方式表示图。

实现图的深度优先遍历和广度优先遍历。

四、实验步骤及结果1、链表的实现与操作首先，定义了链表节点的结构体：｀｀｀cppstruct ListNode ｛int data;ListNode next;ListNode(int x) ： data(x)， next(NULL) ｛｝｝；｀｀｀插入节点的函数：｀｀｀cppvoid insertNode(ListNode& head, int val) ｛ListNode newNode ＝ new ListNode(val)；head ＝ newNode;｝ else ｛ListNode curr ＝ head;while （curr>next!＝ NULL) ｛curr ＝ curr>next;｝curr>next ＝ newNode;｝｝｀｀｀删除节点的函数：｀｀｀cppvoid deleteNode(ListNode& head, int val) ｛if （head ＝＝ NULL) ｛return;｝ListNode temp ＝ head;head ＝ head>next;delete temp;return;｝ListNode curr ＝ head;while （curr>next!＝ NULL ＆＆ curr>next>data!＝ val) ｛curr ＝ curr>next;｝if （curr>next!＝ NULL) ｛ListNode temp ＝ curr>next;curr>next ＝ curr>next>next;delete temp;｝｝｀｀｀遍历链表的函数：｀｀｀cppvoid traverseList(ListNode head) ｛ListNode curr ＝ head;while （curr!＝ NULL) ｛std:：cout ＜＜ curr>data ＜＜＂＂；curr ＝ curr>next;｝std:：cout ＜＜ std:：endl;｝｀｀｀对链表进行冒泡排序的函数：｀｀｀cppvoid bubbleSortList(ListNode& head) ｛if （head ＝＝ NULL ｜｜ head>next ＝＝ NULL) ｛return;｝bool swapped;ListNode ptr1;ListNode lptr ＝ NULL;do ｛swapped ＝ false;ptr1 ＝ head;while （ptr1-＞next!＝ lptr) ｛if （ptr1-＞data ＞ ptr1-＞next>data) ｛int temp ＝ ptr1-＞data;ptr1-＞data ＝ ptr1-＞next>data;ptr1-＞next>data ＝ temp;swapped ＝ true;｝ptr1 ＝ ptr1-＞next;｝lptr ＝ ptr1;｝ while （swapped)；｝｀｀｀测试结果：创建了一个包含 5、3、8、1、4 的链表，经过排序后，输出为 1 3 4 5 8 。

北京工业大学- 第学期信息学部计算机学院3月31日报告题目：输入中缀体现式，输出后缀体现式，并对体现式求值A．分析中缀体现式旳运算顺序受运算符优先级和括号旳影响。

因此，将中缀体现式转换成等价旳后缀体现式旳核心在于如何恰当旳去掉中缀体现式中旳括号，然后在必要时按照先乘除后加减旳优先规则调换运算符旳先后顺序。

在去括号旳过程中用栈来储存有关旳元素。

基本思路：从左至右顺序扫描中缀体现式，用栈来寄存体现式中旳操作数，开括号，以及在这个开括号背面旳其她临时不能拟定计算顺序旳内容。

（1）当输入旳是操作数时，直接输出到后缀体现式（2）当遇到开括号时，将其入栈（3）当输入遇到闭括号时，先判断栈与否为空，若为空，则表达括号不匹配，应作为错误异常解决，清栈退出。

若非空，则把栈中元素依次弹出，直到遇到第一种开括号为止，将弹出旳元素输出到后缀体现式序列中。

由于后缀体现式不需要括号，因此弹出旳括号不放到输出序列中，若没有遇到开括号，阐明括号不匹配，做异常解决，清栈退出。

（4）当输入为运算符时（四则运算+ - * / 之一）时：a.循环，当（栈非空&&栈顶不是开括号&&栈顶运算符旳优先级不低于输入旳运算符旳优先级）时，反复操作将栈顶元素弹出，放到后缀体现式中。

b.将输入旳运算符压入栈中。

（5）最后，当中缀体现式旳符号所有扫描完毕时，若栈内仍有元素，则将其所有依次弹出，放在后缀体现式序列旳尾部。

若在弹出旳元素中遇到开括号，则阐明括号不匹配，做异常解决，清栈退出。

B．实现#include<stdio.h>#include<string.h>#include<stdlib.h>#include<stack>using namespace std;#define N 1000char infix[N]; //中缀体现式（未分离，都在一种字符串里）char expression[N][10]; //保存预解决过旳体现式，也就是每个元素都分离过旳体现式char suffix[N][10]; //保存后缀体现式旳操作数int count;//体现式中元素旳个数（一种完整到数字（也许不止一位数）或者符号）int suffixLength;//后缀体现式旳长度int level(char a){switch(a){case '#':return 0;case '+':case '-':return 1;case '*':case '/':return 2;case '^':return 3;default:break;}return -1;}int isDigital(char x){if( (x>='0'&&x<='9') || (x>='A'&&x<='Z') || (x>='a'&&x<='z') || (x=='.') )return 1;return 0;}int isNumber(char *str){int i;for(i=0;str[i];i++){if(isDigital(str[i])==0)return 0;}return 1;}/*************************************预解决中缀体现式，把持续旳字符分离成不同旳元素，用字符串数组（expression[][]）保存，以便背面旳计算，由于这里考虑了运算数也许不全是个位数例如：（12+3）在解决成后缀体现式时，是123+，容易产生歧义（1+23 ? 12+3）*************************************/void pretreatment(char *str){int i,j,numberFlag;char temp[3];char number[10];count=0;numberFlag=0;for(j=0,i=0;str[i];i++){if(isDigital(str[i])==0){if(numberFlag==1){number[j]=0;strcpy(expression[count++],number); j=0;numberFlag=0;}if(str[i]!=' '){temp[0]=str[i];temp[1]=0;strcpy(expression[count++],temp); }}else {numberFlag=1;number[j++]=str[i];}}puts("分离后旳体现式为");for(i=0;i<count;i++){printf("%s ",expression[i]);}puts("");puts("");}/*****************************************中缀体现式转后缀体现式遍历字符串，对于str[i]str[i]是运算数（或者是字母替代旳运算变量）输出；str[i]是符号，有两种状况(1)，是右括号，栈顶元素输出，直到与str[i]匹配旳左括号出栈（左括号不用输出打印）(2)，是运算符，判断str[i]与栈顶元素旳优先级，str[i]优先级不高于栈顶符号，则栈顶元素输出，直到栈空或者栈顶符号优先级低于str[i]*****************************************/void infix_to_suffix(char str[N][10]){memset(suffix,0,sizeof(suffix));suffixLength=0;stack <char*> st;int i=0;char Mark[2]="#";st.push(Mark);do{if(isNumber(str[i])==1)//运算数直接保存到后缀体现式中strcpy(suffix[suffixLength++],str[i]);else if(str[i][0]=='(') //是左括号，直接入栈st.push(str[i]);else if(str[i][0]==')'){ //是右括号，栈顶出栈，直到与其匹配旳左括号出栈while( strcmp(st.top(),"(")!=0 ){char temp[10];strcpy(temp,st.top());strcpy(suffix[suffixLength++],temp);st.pop();}st.pop();}else if( strcmp(st.top(),"(")==0 )//是运算符，且栈顶是左括号，则该运算符直接入栈st.push(str[i]);else { //是运算符，且栈顶元素优先级不不不小于运算符，则栈顶元素始终//出栈，直到栈空或者遇到一种优先级低于该运算符旳元素while( !st.empty() ){char temp[10];strcpy(temp,st.top());if( level(str[i][0]) > level(temp[0]) )break;strcpy(suffix[suffixLength++],temp);st.pop();}st.push(str[i]);}i++;}while(str[i][0]!=0);while( strcmp(st.top(),"#")!=0 ){ //将栈取空结束char temp[10];strcpy(temp,st.top());strcpy(suffix[suffixLength++],temp);st.pop();}puts("后缀体现式为：");for(i=0;i<suffixLength;i++){printf("%s",suffix[i]);}puts("");puts("");}/**************************************计算后缀体现式旳值**************************************/char kt[N][10];int stackTop;void getResult(char str[N][10]){stackTop=0;/*这里要注意，内存旳分派方案导致 i 旳位置就在temp[9]旁边，然后strcpy()函数直接拷贝内存旳话，在temp越界状况下会覆盖 i 旳值*/int i;char temp[10];for(i=0;i<suffixLength;i++){if(isNumber(str[i])==1){strcpy(kt[stackTop++],str[i]);}else {char a[10],b[10];double na,nb,nc;strcpy(a,kt[stackTop-1]);na = atof(a);stackTop--;strcpy(b,kt[stackTop-1]);nb = atof(b);stackTop--;if(str[i][0]=='+')nc=nb+na;else if(str[i][0]=='-')nc=nb-na;else if(str[i][0]=='*')nc=nb*na;else if(str[i][0]=='/')nc=nb/na;sprintf(temp,"%lf",nc);strcpy(kt[stackTop++],temp);}}puts("\nThe result is : %f\n");printf("%s\n",kt[stackTop-1]);}int main(){printf("Please input calculate Expression :\n"); char temp[N];while(gets(infix)){strcpy(temp,infix);pretreatment( strcat(temp," ") );infix_to_suffix(expression);getResult(suffix);}return 0;}C．总结实验需要细心细心再细心。

《数据结构》实验报告一、题目要求有输入界面（图形或文字界面都可），能区分加法、减法、乘法和转置；能处任意输入的典型数据和进行出错数据处理（例如乘法，当第一个矩阵的列数不等于第二个矩阵的行数时）；必须采用三元组作存储结构，不能采用数组等形式；输出要求用矩阵的形式输出（即习题集136页的形式），当第一个矩阵的行数不等于第二个矩阵的行数时，注意如第三个乘法的形式输出二、算法实现在本次实验中，算法比较简单，所涉及的函数比较少，一共有：创建稀疏矩阵、输出稀疏矩阵、矩阵的乘法、矩阵的加法、矩阵的减法、矩阵的转置。

因为是稀疏矩阵要求以三元组的方式输入，节约了很多时间和空间，只需输入行列下标和非零元即可。

在输出矩阵时，通常以方阵的形式输出。

基本操作：CreateSMatrix(&M); //操作结果:创建稀疏矩阵M.Print SMatrix(M);//初始化条件: 稀疏矩阵M存在.//操作结果:输出稀疏矩阵M.AddSMatrix(M,N,&Q);//初始化条件: 稀疏矩阵M与N的行数和列数对应相等.//操作结果:求稀疏矩阵的和Q=M+N.SubSMatrix(M,N,&Q);//初始化条件: 稀疏矩阵M与N的行数和列数对应相等.//操作结果:求稀疏矩阵的差Q=M-N.MultSMatrix(M,N,&Q);//初始化条件: 稀疏矩阵M的列数等于N的行数.//操作结果:求稀疏矩阵的乘积Q=M*N.TransposeSMatrix(M ,&Q);//初始化条件：存在稀疏矩阵M//操作结果：将稀疏矩阵行列互换输出。

功能模块调用关系图三、详细设计1、元素类型 主程序模块 创建稀疏矩阵模块调用矩阵运算模块输出矩阵方阵模块稀疏矩阵运算器 矩阵加法 矩阵减法 矩阵乘法 矩阵转置输入矩阵M 输入矩阵N输出运算结输入矩阵M 输入矩阵N 输出运算结输入矩阵M 输入矩阵N 输出运算结输入矩阵M 输出运算结果typedef struct{int i,j;//该非零元素的列下标和行下标ElemType e;}Triple;typedef struct{Triple data[MAXSIZE+1];//非零元三元组表，data[0]未用int mu,nu,tu;}TSMatrix;2、矩阵运算器void AddSMatrix(M ,N , &Q)void SubSMatrix(M ,N , &Q)void MultSMatrix(M ,N , &Q)void TransposeSMatrix(M ,&T)四、调试分析1、此程序的算法结构比较简单，只要理解了三元组，设计矩阵运算器的方法很简单。

《数据结构》实验报告◎实验题目:合并两个链表◎实验目的：设计合适的数据结构，熟悉链表的构造、合并和输出。

◎实验内容：通过算法实现，构造合适的数据结构，通过输入获得A和B两个有序循环链表，将这两个链表按元素的大小顺序排列合并成一个有序循环链表并输出，例如输入A链表为：1 3 5 7 9，B链表为2 4 6 8 10，的合成的C链表为1 2 3 4 5 6 7 8 9 10。

一、需求分析1．本程序演示中，链表A和链表B的长度m ,n是任意的，开始时输入链表长度，计算机根据此链表创建循环链表，并由人输入链表数据，之后计算机将两链表合并成一个链表C。

2. 演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入相应数据（链表长度和链表中数据）。

3．程序执行的命令包括：（1）构造链表；（2）输入数据；（3）进行链表的合并操作；（4）输出链；（5）结束。

4、测试数据：第一组：A链表长度：5，A链表数据：1 3 5 7 9B链表长度：5，B链表数据：2 4 6 8 10合并的C链表为：1 2 3 4 5 6 7 8 9 10；第二组：A链表长度：4，A链表数据：2 5 6 8A链表长度：5，A链表数据：1 4 7 9 14合并的C链表为：1 2 4 5 6 7 8 9 14第三组：A链表长度：5，A链表为：1 2 4 6 8B链表长度：5，B链表为：1 3 4 5 9合并的C链表为：1 2 3 4 5 6 8 9二概要设计为实现上述算法，选择循环单链表为本程序的存储结构。

1、基本操作：creat()操作结果：构造循环单链表，并通过输入将数据输入链表combine()初始条件：循环单链表已经存在操作结果：将两个链表有序合并为一个链表2、本程序包括三个模块：（1）主程序模块（2）构造链表模块（3）链表合并模块3、模块调用关系图三详细设计1、定义存储链表结构：（1）定义链表结点与指针结构：typedef struct LNODE //*定义链表结点结构*//{int num;struct LNODE *next;}lnode,*Linklist;2、每个模块的分析：（1）主程序模块：void main(){Linklist l1,l2,l3; //*定义链表头指针*// int m,n;lnode *p;printf("请输入链表A的长度:\n");scanf("%d",&m);printf("请输入链表A元素:\n");l1=creat(m);printf("请输入链表B的长度:\n");scanf("%d",&n);printf("请输入链表B元素:\n");l2=creat(n);printf("合并的链表为:\n");l3=combine(l1,l2); //*合并两个链表*//p=l3->next; //*输出合并成的链表*//while(p!=l3){printf("%d ",p->num);p=p->next;}printf("\n");}（2）构造链表模块：lnode *creat(int t) //*创建循环单链表*//{ int i;lnode *l;lnode *p,*q;l=(lnode*)malloc(sizeof(lnode));p=(lnode*)malloc(sizeof(lnode));q=l;for(i=0;i<t;i++){scanf("%d",&(p->num)); //*为链表输入数据*//q->next=p;q=p;p=(lnode*)malloc(sizeof(lnode));}q->next=l; //*链表尾部指针指向头结点*// return(l); //*返回链表头指针*//}（3）链表合并模块：lnode *combine(lnode*l1,lnode*l2) //*链表合并函数*//{Linklist l3;lnode *p1,*p2,*p3,*p;p1=l1->next;p2=l2->next;l3=(lnode *)malloc(sizeof(lnode));p3=l3;l3->next=l3;while(p1!=l1&&p2!=l2){if(p1->num==p2->num){p=(lnode *)malloc(sizeof(lnode));p->num=p1->num;p->next=p3->next;p3->next=p;p3=p;p1=p1->next;p2=p2->next;}else if(p1->num < p2->num){p=(lnode *)malloc(sizeof(lnode));p->num=p1->num;p->next=p3->next;p3->next=p;p3=p;p1=p1->next;}else{p=(lnode *)malloc(sizeof(lnode));p->num=p2->num;p->next=p3->next;p3->next=p;p3=p;p2=p2->next;}}while(p1!=l1) //*当循环退出后，将没有加入链表的元素添加进链表*// {p=(lnode *)malloc(sizeof(lnode));p->num=p1->num;p->next=p3->next;p3->next=p;p3=p;p1=p1->next;}while(p2!=l2){p=(lnode *)malloc(sizeof(lnode));p->num=p2->num;p->next=p3->next;p3->next=p;p3=p;p2=p2->next;}p->next=l3;free(l1); //*释放链表l1空间*//free(l2); //*释放链表l2空间*//return(l3);}四使用说明、测试分析及结果1、程序使用说明：（1）本程序的运行环境为VC6.0。