下载文档原格式
川大数据结构课程设计一、课程目标知识目标：1. 学生能够理解数据结构的基本概念，掌握线性表、栈、队列、树和图等常见数据结构的特点与应用。
2. 学生能够描述不同数据结构在解决实际问题中的优势与局限，并分析其时间复杂度和空间复杂度。
3. 学生能够运用所学知识设计简单算法，解决实际问题。
技能目标：1. 学生能够运用C/C++等编程语言实现常见数据结构及其基本操作。
2. 学生能够运用数据结构知识对实际问题进行分析，选择合适的数据结构并编写相应算法。
3. 学生能够运用调试工具和技巧，优化程序性能，提高代码质量。
情感态度价值观目标：1. 学生通过学习数据结构，培养严谨的逻辑思维和问题分析能力。
2. 学生能够认识到数据结构在实际应用中的重要性，激发对计算机科学的兴趣和热情。
3. 学生在团队协作和讨论中，培养良好的沟通能力和合作精神。
课程性质：本课程为计算机科学与技术专业的基础课程，旨在帮助学生掌握数据结构的基本原理和方法，为后续算法分析与设计、软件工程等课程打下基础。
学生特点：大一、大二学生，具备一定的编程基础，对数据结构有一定了解，但尚不深入。
教学要求：注重理论与实践相结合，通过案例分析和实际编程，使学生更好地理解和掌握数据结构知识。
同时，注重培养学生的逻辑思维和问题解决能力，提高其计算机素养。
二、教学内容1. 线性表：介绍线性表的定义、特点和基本操作，包括顺序存储和链式存储结构，分析其优缺点及适用场景。
教材章节：第2章 线性表内容安排：2学时2. 栈与队列：讲解栈和队列的基本概念、操作及应用，分析其时间复杂度和空间复杂度。
教材章节：第3章 栈和队列内容安排：2学时3. 树与二叉树：阐述树和二叉树的基本概念、性质、存储结构及遍历方法，介绍哈夫曼树、平衡二叉树等特殊树及其应用。
教材章节：第4章 树和二叉树内容安排：4学时4. 图：介绍图的定义、存储结构、遍历方法以及最小生成树、最短路径等算法。
教材章节：第5章 图内容安排：4学时5. 排序算法：讲解常见排序算法，如冒泡排序、插入排序、快速排序等，分析其时间复杂度和稳定性。
算术表达式的求解-数据结构课程设计报告数据结构》课程设计报告书题目：算术表达式的求解系别：计算机科学与应用数据结构课程设计目录一、需求分析1、设计要求：本程序需要实现对算术表达式的求解功能，可以支持基本的四则运算，包括加、减、乘、除，同时还需要支持括号的使用。
2、设计构想：我们将使用栈来实现算术表达式的求解。
具体地，我们将把中缀表达式转换为后缀表达式，然后再利用栈来求解后缀表达式。
二、概要设计1、本程序包含的模块：本程序包含两个模块：中缀表达式转后缀表达式模块和后缀表达式求解模块。
三、详细设计1、定义栈结构我们定义一个栈结构，用来存储算术表达式中的运算符和操作数。
具体地，栈中的每个元素都包含两个属性：元素的值和元素的类型。
元素的值可以是一个数字或一个运算符，元素的类型可以是数字或运算符。
我们使用一个数组来实现栈的结构。
为了方便起见，我们还需要定义一些基本的栈操作，如入栈、出栈、判断栈是否为空等。
2、栈的基本操作栈是一种常见的数据结构，具有后进先出（LIFO）的特点。
栈的基本操作包括初始化栈、入栈、出栈、取栈顶元素和运算模块。
1) 初始化栈初始化栈是指将栈的各项属性设置为初始状态。
通常包括将栈顶指针设为-1，表示栈为空。
2) 入栈入栈是指将元素压入栈顶。
入栈操作需要将栈顶指针加1，并将元素存入栈顶位置。
3) 出栈出栈是指将栈顶元素弹出。
出栈操作需要将栈顶元素取出，并将栈顶指针减1.4) 取栈顶元素取栈顶元素是指获取栈顶元素的值，但不将其弹出。
取栈顶元素操作只需要返回栈顶元素的值即可。
5) 运算模块栈可以用于实现各种运算，例如中缀表达式的转换和计算、括号匹配等。
运算模块需要根据具体需求进行设计和实现。
3、判断运算符的优先级在进行中缀表达式的转换和计算时，需要判断运算符的优先级。
通常采用栈来实现这一功能。
具体实现方法是将运算符入栈，当遇到新的运算符时，将其与栈顶运算符进行比较，如果新运算符的优先级高于栈顶运算符，则将其入栈，否则将栈顶运算符弹出并输出，直到新运算符可以入栈为止。
ＸＸXＸXX大学《数据结构》课程设计报告班级：学号：姓名：指导老师:目录一算术表达式求值一、需求分析二、程序得主要功能三、程序运行平台四、数据结构五、算法及时间复杂度六、测试用例七、程序源代码二感想体会与总结算术表达式求值一、需求分析一个算术表达式就是由操作数(oｐeranｄ）、运算符(operator）与界限符（deｌimiter)组成得。
假设操作数就是正整数，运算符只含加减乘除等四种运算符,界限符有左右括号与表达式起始、结束符“#”，如：＃(7+15）*（2３—２8/４）#。
引入表达式起始、结束符就是为了方便.编程利用“算符优先法”求算术表达式得值.二、程序得主要功能（1）从键盘读入一个合法得算术表达式，输出正确得结果。
(2）显示输入序列与栈得变化过程。
三、程序运行平台Ｖｉsｕaｌ C＋+6、0版本四、数据结构本程序得数据结构为栈。
（1）运算符栈部分：struct SqStaｃk ／/定义栈{char *base； //栈底指针ｃｈａr *toｐ; ／/栈顶指针inｔstacｋsiｚe； //栈得长度};inｔInitSｔack (SqＳｔack &ｓ) //建立一个空栈S{ｉf （!(s、ｂａse= (char ＊）ｍalloc(5０＊ｓizeof（chａr）)）)exｉt（0）；ｓ、ｔop=s、bａse;s、staｃksiｚｅ=５0；retuｒn OK；}ｃhar GeｔTop（SqStack s,char &e) /／运算符取栈顶元素｛iｆ (s、ｔop==s、ｂase) //栈为空得时候返回EＲROR｛ﻩ prｉntf(＂运算符栈为空！＼n")；ﻩ reｔurn ERＲＯR;｝elsee＝*（s、ｔoｐ-1); //栈不为空得时候用ｅ做返回值，返回S得栈顶元素，并返回OK returnＯＫ;｝ｉnt Push(SqStacｋ＆s，cｈａr ｅ） //运算符入栈｛if （s、tｏp—s、baｓe >= ｓ、ｓtacksｉzｅ）ﻩ{ｐriｎtf（＂运算符栈满!＼n"）;ﻩs、basｅ=（cｈaｒ*）reａlloｃ(s、bａｓe，(s、sｔackｓｉze+5)*ｓizeoｆ(cｈar））；//栈满得时候,追加5个存储空间ｉf(！s、basｅ)exｉt （OVERＦＬOW）；s、top=s、ｂａsｅ+s、ｓｔacｋsize;s、ｓtaｃksiｚｅ+=５;}ﻩ＊(s、ｔop）＋＋=e；／/把e入栈ﻩｒeturn OK;}ｉnｔ Pop(SqStaｃk &ｓ，char ＆ｅ） /／运算符出栈｛ｉｆ (s、toｐ==s、base) ／/栈为空栈得时候，返回ERＲOＲ｛ｐrintf（＂运算符栈为空!\n”）;ﻩ return ERROＲ;}else｛ﻩﻩe=＊-—ｓ、tｏp；/／栈不为空得时候用e做返回值，删除S得栈顶元素，并返回ＯK return OK；}}iｎt StackTｒaｖerse（ＳqStacｋ&ｓ)／/运算符栈得遍历｛ﻩchar ＊t；ﻩt=s、ｂａｓｅ；ﻩif (s、top＝=s、baｓe）｛ﻩ printｆ（”运算符栈为空！\ｎ”)； //栈为空栈得时候返回ＥＲRORｒeturn ERＲOＲ;}ｗhile（t！＝s、tｏp)｛ﻩﻩｐrｉｎｔf（" %c",＊t)； //栈不为空得时候依次取出栈内元素t++;ﻩ}ｒeturｎ EＲRＯR；｝（2）数字栈部分：strｕｃt SqSｔackn//定义数栈｛ｉnt *bａse; //栈底指针ｉnt＊tｏp； //栈顶指针ｉnｔ sｔacksｉze； //栈得长度｝;inｔIｎｉtStackｎ (SqSｔackn &s) //建立一个空栈Ｓ{s、base=（int＊）malｌoc（50*sｉzeof(int）);if(！ｓ、ｂase）eｘiｔ（OVEＲFLＯW）；//存储分配失败s、top=s、base；s、stacksizｅ=5０;reｔuｒn OK；｝ｉｎt GｅtToｐn(ＳqＳtａcｋn s,inｔ＆e) //数栈取栈顶元素{if（s、ｔop=＝s、base）{prinｔｆ(＂运算数栈为空!\ｎ＂);//栈为空得时候返回ERRORﻩ rｅturｎ ERROR;}eｌseﻩe＝＊（s、toｐ-1);／/栈不为空得时候，用e作返回值，返回S得栈顶元素，并返回OＫreturｎＯK；｝int Pｕshn（SｑStａckn ＆s，int ｅ) //数栈入栈｛if（s、tｏp—s、ｂasｅ＞＝s、stacksiｚe)｛ﻩﻩprｉｎｔf（"运算数栈满!\ｎ"）；／/栈满得时候,追加5个存储空间ﻩs、base=(int＊）realloc (s、baｓe,(s、stａcksize＋5)＊sｉzｅof（ｉnt));ｉf（!s、base) ｅxit (ＯＶERFLOW)；ﻩs、top=ｓ、bａsｅ＋ｓ、stacｋsize;//插入元素e为新得栈顶元素s、stacksｉｚe+=5；}*（s、top）++=e; /／栈顶指针变化returｎOK;}ｉｎt Popｎ(ＳｑSｔacｋn ＆s，iｎt &e)//数栈出栈｛ﻩif （s、top=＝ｓ、base）｛ﻩ pｒiｎtｆ（"运算符栈为空！\n＂);//栈为空栈得视时候，返回ERRＯＲﻩ retｕrn ERROR；ﻩ｝ｅlse｛ﻩﻩe=＊—-ｓ、tｏp；／/栈不空得时候，则删除S得栈顶元素,用e返回其值，并返回OK ﻩreturｎOK；｝}ｉnt StacｋＴraveｒsｅn（SqStackn &s)/／数栈遍历{ﻩiｎｔ＊t;ﻩｔ=s、basｅ ;ﻩif（s、top==s、basｅ）ﻩ｛pｒinｔf(＂运算数栈为空！\n”）；//栈为空栈得时候返回ERRORﻩ rｅｔｕrn ERＲＯＲ；ﻩ｝ﻩwｈile（t！=ｓ、ｔop)ﻩ{priｎtf(” ％d”，*ｔ); /／栈不为空得时候依次输出t＋＋;｝return ERRＯR；｝五、算法及时间复杂度１、算法:建立两个不同类型得空栈,先把一个‘＃’压入运算符栈。
数据结构与算法分析》实验报告《数据结构与算法分析》实验报告一、实验目的本次实验旨在通过实际操作和分析，深入理解数据结构与算法的基本概念和原理，掌握常见数据结构的实现和应用，以及算法的设计和性能评估。
通过实验，提高编程能力和解决实际问题的能力，培养逻辑思维和创新精神。
二、实验环境操作系统：Windows 10编程语言：Python 3x开发工具：PyCharm三、实验内容1、线性表顺序表的实现与操作链表的实现与操作2、栈和队列栈的实现与应用（表达式求值）队列的实现与应用（排队系统模拟）3、树和二叉树二叉树的遍历算法实现（前序、中序、后序）二叉搜索树的实现与操作4、图图的存储结构（邻接矩阵和邻接表）图的遍历算法（深度优先搜索和广度优先搜索）5、排序算法冒泡排序插入排序选择排序快速排序归并排序6、查找算法顺序查找二分查找四、实验步骤及结果1、线性表顺序表的实现与操作定义一个顺序表类，使用数组来存储元素。
实现插入、删除、查找等基本操作。
进行性能测试，分析在不同位置插入和删除元素的时间复杂度。
实验结果表明，在顺序表的前端或中间进行插入和删除操作时，时间复杂度较高，而在末尾操作时效率较高。
链表的实现与操作定义链表节点类和链表类。
实现链表的插入、删除、查找等操作。
比较顺序表和链表在不同操作下的性能差异。
结果显示，链表在频繁插入和删除元素的情况下表现更优，而顺序表在随机访问元素时速度更快。
2、栈和队列栈的实现与应用（表达式求值）用栈来实现表达式求值的算法。
输入表达式，如“2 ＋ 3 （ 4 1 ）”，计算并输出结果。
经过测试，能够正确计算各种复杂的表达式。
队列的实现与应用（排队系统模拟）模拟一个简单的排队系统，顾客到达和离开队列。
输出队列的状态和平均等待时间。
实验发现，队列长度和顾客等待时间与到达率和服务率密切相关。
3、树和二叉树二叉树的遍历算法实现（前序、中序、后序）构建一棵二叉树。
分别实现前序、中序、后序遍历算法，并输出遍历结果。
四川大学《数据结构》课程设计实验项目及内容提要(实验任选一个完成)
试读3页
数据结构实验报告
实验名称： Huffman编码(二叉树应用)
提交文档学生姓名：
提交文档学生学号：
同组成员名单：无
指导教师姓名：
指导教师评阅成绩：
指导教师评阅意见：
.
.
提交报告时间： 2020 年 3 月 26 日
目录
一、概述 (1)
二、系统分析 (1)
三、概要设计 (2)
四、详细设计 (4)
4.1 赫夫曼树的建立 (4)
4.1.1 选择选择parent 为0 且权值最小的两个根结点的算
法 (5)
4.1.2 统计字符串中字符的种类以及各类字符的个数 (7)
4.1.3构造赫夫曼树 (8)
4.2赫夫曼编码 (10)
4.2.1赫夫曼编码算法 (10)
4.2.2建立正文的编码文件 (11)
4.3代码文件的译码 (12)
五、运行与测试 (14)
六、总结与心得 (14)
参考文献................................. 错误!未定义书签。
附录..................................... 错误!未定义书签。
数据结构与算法分析实验报告(川大)《数据结构与算法分析》课程设计报告课题名称：文本编辑器课题设计人（学号）：刘佳玉2012141461134指导教师：朱宏评阅成绩：评阅意见：{case 'a'://当用户选择自行输入文本时······break;case 'b'://当用户选择使用电脑设置的文本时·····break;}2、当用户选择自己输入文本时，就需要写一些函数来存储这些信息，可以将这些函数封装在一个模板类中，只要定义一个之歌类的对象（bianji）就可以在需要的时候调用类的函数。
在这个时候需要调用的函数有：bianji.Sethang(h);//设置文本的行数bianji.Setlie(l);//设置文本的列数bianji.Setwenben();//输入文本bianji.Showwenben();//显示文本3、单用户选择使用程序初始化的文本时，只要显示文本即可。
这个时候需要的函数有：bianji.Showwenben();//显示文本4、该文本编辑器有插入，移除，替换，查找，显示和重置的功能，通过输出语句告知用户文本编辑器的功能，并询问用户要使用哪个功能。
相应代码：char ch='s';//初始化chwhile(ch!='q')//当ch!='q'时，就不会退出循环{cout<<"i代表插入文本 ";cout<<"R代表移除文本 ";cout<<"r代表替换文本 ";cout<<"f代表查找文本 ";cout<<"s代表显示当前文本 ";cout<<"n代表重新建立一个文本 ";cout<<"q代表退出 "<<endl;cout<<"请输入你的选择：";cin>>ch;······}5、当用户选择插入（insert）功能时，就只需要将当前行数加1，将要插入的行及其后面的行的文本往后移一行，在输入要插入的行的文本即可，相应代码：while(h0>bianji.Gethang()||h0<1)//如果要插入的行大于已有的//最大行或者小于第一行就会要求重新输入一个{cout<<"输入错误，请重输：";cin>>h0;}bianji.Sethang(bianji.Gethang()+1);//当前行数加1int i,j;for(i=bianji.Gethang()-1;i>=h0;i--)//把要插入行及后面的行的//文本往后一次移一行{for(j=0;j<bianji.Getlie();j++){bianji.Xiugaiwenben(i,j,i-1,j);}}for(i=0;i<bianji.Getlie();i++)//输入要插入的那一行的文本{cout<<"请输入第"<<h0<<"行第"<<i+1<<"个字符：";bianji.Fuzhiwenben(h0-1,i);cout<<endl;bianji.Showwenben();//显示文本6、当用户选择移除（remove）功能时，只需要将要移除的行的后面的文本依次往前移一行，就会顺便把要移除行的文本覆盖了，相当于达到了移除的效果，相应代码：while(h1>bianji.Gethang()||h1<1)//如果要移除的行大于已有的//最大行或者小于第一行就会要求重新输入一个{cout<<"输入有误，请重输：";cin>>h1;}bianji.Sethang(bianji.Gethang()-1);//将当前行数减1int i1,j1;for(i1=h1-1;i1<bianji.Gethang();i1++)//把要移除的行的后面的//行一次往前移一行就顺便把要移除的那一行给覆盖{ //了，从而达到移除的效果for(j1=0;j1<bianji.Getlie();j1++){bianji.Xiugaiwenben(i1,j1,i1+1,j1);}}bianji.Showwenben();7、当用户选择替换（replace）功能时,只需要重新输入要替换行的文本即可，其他行的文本不变，相应代码：for(i2=0;i2<bianji.Getlie();i2++) //得到要替换的那一行的列//数，然后输入新的文本{cout<<"请输入第"<<h2<<"行第"<<i2+1<<"个字符：";bianji.Fuzhiwenben(h2-1,i2);cout<<endl;bianji.Showwenben();8、当用户选择查找（find）功能时,只要用户输入相应列数的文本，然后将其与每一行的文本进行比较，如果完全相同，则会输出相应的行号，通过循环语句来进行匹配，相应代码：for(i3=0;i3<bianji.Getlie();i3++)//根据当前文本的列数来输入//要查找的文本{cout<<"请输入第"<<i3+1<<"列的字符：";bianji.Fuzhiwenben(bianji.Gethang(),i3);//将输入的文本放//到当前的最后一行，只是暂时的} //在这个功能完了后就会//消失，因为没有改变文本的行列for(i3=0;i3<bianji.Gethang();i3++)//根据输入的文本，一行一行//的搜，将每一行的文本域输入的文本进行匹配{ //如果匹配成功就会输出相应的行数j3=0;while(bianji.Findwenben(i3,j3)==bianji.Findwenben(bianji.Gethang(),j3)&&j3<bianji.Getlie()){j3++;//相同就会在查下一列的字符是否相同，直到这一完// 了}if(j3==bianji.Getlie()){cout<<"你要找的文本在第"<<i3+1<<"行"<<endl;count+=1;}}if(count==0)cout<<"你要找的文本不在现有文本中"<<endl;}cout<<endl;9、当用户选择显示（show）功能时,只需要调用模板类中的显示函数即可，相应代码：bianji.Showwenben();与初始化的部分相同，也只是要调用模板类中的相应函数即可，相应代码：cout<<"请输入新的行数：";cin>>h4;bianji.Sethang(h4);//新行cout<<"请输入新的列数：";cin>>l4;bianji.Setlie(l4);//新列bianji.Setwenben();//新文本bianji.Showwenben();//显示文本10、当用户选择重置（new）功能时，五、源程序清单:该程序代码分为3部分，分别是：1、模板类的代码，文件名“linklist.h”，相应代码：#ifndef LINKLIST_H_#define LINKLIST_H_#include<iostream>using namespace std;template<class ElemType>//队列的模板类class LinkList{private:ElemType wenben[256][256];//创立一个二维数组作为存储文本的空间int hang;//数组的行int lie;//数组的列public:LinkList()//构造函数{hang=1;//初始化行数为1lie=1;//初始化列数为1wenben[0][0]='a';//初始化文本为'a'}~LinkList(){}//析构函数void Xiugaiwenben(int h1,int l1,int h2,int l2)//修改文本，将文本中h2行l2列的{ //字符赋给h1行l1列wenben[h1][l1]=wenben[h2][l2];}void Fuzhiwenben(int h,int l)//给文本中h行l列赋一个字符{cin>>wenben[h][l];}ElemType Findwenben(int h,int l)//返回h行l列的字符{return wenben[h][l];}void Sethang(int h)//设定数组的行数{hang=h;}int Gethang()//得到数组的行数{return hang;}void Setlie(int l)//设定数组的列数{lie=l;}int Getlie()//得到数组的列数{return lie;}void Setwenben()//设立一个文本{int i,j;for(i=0;i<hang;i++){cout<<"请输入第"<<i+1<<"行的文本："<<endl;for(j=0;j<lie;j++){cout<<"请输入第"<<i+1<<"行第"<<j+1<<"列的字符"<<endl;cin>>wenben[i][j];}}}void Showwenben()//显示当前文本{cout<<"当前文本是："<<endl;int i,j;for(i=0;i<hang;i++){for(j=0;j<lie;j++){cout<<wenben[i][j];}cout<<endl;}}};#endif2、编辑类的代码，文件名是“editor.h”，相应代码：#include"linklist.h"class Editor{private:LinkList<char>bianji;//模板类的char型对象，用来调用模板类中的函数int count;//在使用查找功能时用来判断是否要查找的文本在当前文本中public:void Chushihua()//设置文本的函数{cout<<"a代表自己输入文本，b代表使用电脑设置的文本"<<endl;cout<<"请输入你的选择："<<endl;char ch;cin>>ch;switch(ch)//对用户的不同选择执行不同的代码{case 'a'://当用户选择自行输入文本时cout<<"请输入文本的行数：";int h;cin>>h;cout<<endl;cout<<"请输入文本的列数：";int l;cin>>l;bianji.Sethang(h);//设置文本的行数bianji.Setlie(l);//设置文本的列数bianji.Setwenben();//输入文本bianji.Showwenben();//显示文本break;case 'b'://当用户选择使用电脑设置的文本时bianji.Showwenben();//显示初始化的文本break;}}void Edite()//编辑文本的函数{char ch='s';//初始化chwhile(ch!='q')//当ch!='q'时，就不会退出循环{cout<<"i代表插入文本";cout<<"R代表移除文本";cout<<"r代表替换文本";cout<<"f代表查找文本";cout<<"s代表显示当前文本";cout<<"n代表重新建立一个文本";cout<<"q代表退出"<<endl;cout<<"请输入你的选择：";cin>>ch;switch(ch)//根据用户的不同选择执行不同的代码{case 'i'://选择插入（insert）功能bianji.Showwenben();//显示当前文本cout<<"请问要插入到第几行？：";int h0;cin>>h0;while(h0>bianji.Gethang()||h0<1)//如果要插入的行大于已有的最大行或者小于第一行就会要求重新输入一个{cout<<"输入错误，请重输：";cin>>h0;}bianji.Sethang(bianji.Gethang()+1);//当前行数加1int i,j;for(i=bianji.Gethang()-1;i>=h0;i--)//把要插入行及后面的行的文本往后一次移一行{for(j=0;j<bianji.Getlie();j++){bianji.Xiugaiwenben(i,j,i-1,j);}}for(i=0;i<bianji.Getlie();i++)//输入要插入的那一行的文本{cout<<"请输入第"<<h0<<"行第"<<i+1<<"个字符：";bianji.Fuzhiwenben(h0-1,i);cout<<endl;}bianji.Showwenben();//显示文本break;case 'R'://选择移除（remove）功能bianji.Showwenben();cout<<"请问要移除哪一行？：";int h1;cin>>h1;while(h1>bianji.Gethang()||h1<1)//如果要移除的行大于已有的最大行或者小于第一行就会要求重新输入一个{cout<<"输入有误，请重输：";cin>>h1;}bianji.Sethang(bianji.Gethang()-1);//将当前行数减1int i1,j1;for(i1=h1-1;i1<bianji.Gethang();i1++)//把要移除的行的后面的行一次往前移一行就顺便把要移除的那一行给覆盖{ //了，从而达到移除的效果for(j1=0;j1<bianji.Getlie();j1++){bianji.Xiugaiwenben(i1,j1,i1+1,j1);}}bianji.Showwenben();break;case 'r'://选择替换（replace）功能bianji.Showwenben();cout<<"要替换哪一行？：";int h2;cin>>h2;int i2;for(i2=0;i2<bianji.Getlie();i2++)//得到要替换的那一行的列数，然后输入新的文本{cout<<"请输入第"<<h2<<"行第"<<i2+1<<"个字符：";bianji.Fuzhiwenben(h2-1,i2);cout<<endl;}bianji.Showwenben();break;case 'f'://选择查找（find）功能bianji.Showwenben();cout<<"请输入要查找的文件："<<endl;int i3,j3;count=0;for(i3=0;i3<bianji.Getlie();i3++)//根据当前文本的列数来输入要查找的文本{cout<<"请输入第"<<i3+1<<"列的字符：";bianji.Fuzhiwenben(bianji.Gethang(),i3);//将输入的文本放到当前的最后一行，只是暂时的} //在这个功能完了后就会消失，因为没有改变文本的行列/*cout<<"第"<<h3<<"行的文本是："<<endl;//输入行数就会将当前文本中那一行的文本输出for(i3=0;i3<bianji.Getlie();i3++){cout<<bianji.Findwenben(h3-1,i3);}*/for(i3=0;i3<bianji.Gethang();i3++)//根据输入的文本，一行一行的搜，将每一行的文本域输入的文本进行匹配{ //如果匹配成功就会输出相应的行数j3=0;while(bianji.Findwenben(i3,j3)==bianji.Findwenben(bianji.Getha ng(),j3)&&j3<bianji.Getlie()){j3++;//相同就会在查下一列的字符是否相同，直到这一行完了}if(j3==bianji.Getlie()){cout<<"你要找的文本在第"<<i3+1<<"行"<<endl;count+=1;}}if(count==0){cout<<"你要找的文本不在现有文本中"<<endl;}cout<<endl;break;case 's'://选择显示当前文本bianji.Showwenben();break;case 'n'://选择重置（new）功能int h4,l4;cout<<"请输入新的行数：";cin>>h4;bianji.Sethang(h4);//新行cout<<"请输入新的列数：";cin>>l4;bianji.Setlie(l4);//新列bianji.Setwenben();//新文本bianji.Showwenben();//显示文本break;case 'q':break;}}}};3、主函数的代码，文件名是“main.cpp”，相应代码：#include"linklist.h"#include"editor.h"int main(){Editor e;//编辑类的对象，用来调用类中的函数e.Chushihua();//调用设置文本的函数e.Edite();//调用编辑文本的函数return 0;}六、运行结果:1、选择自己输入文本（a），输入文本为（3行2列）：qwerty进行插入操作（i），插入文本as到第2行：进行移除操作（R），移除第3行文本：进行替换操作（t），将第一行文本qw替换为df：进行查找操作（f），查找文本as和qw：进行显示操作（s）：进行重置操作（n）：重置操作和自己输入文本是一样的，在这里就不演示了，有兴趣可以自己尝试。
、实验的目的和要求1.采用算符优先数算法, 能正确求值表达式;2.熟练掌握栈的应用;3•熟练掌握计算机系统的基本操作方法，了解如何编辑、编译、链接和运行一个C++程序; 4.上机调试程序,掌握查错、排错使程序能正确运行。
三、实验的环境:指硬件和软件环境1.硬件环境: Intel 奔腾双核T2390 双核处理器(1.86GHz 主频/1MB 二级缓存/533MHz 前端总线)， RAM:2G .2.软件环境: 操作系统：windows vista编译软件：Microsoft Viual C++6.03.软件环境介绍:Visual C++是一个功能强大的可视化软件开发工具。
自1993年Microsoft公司推出Visual C++1.0后，随着其新版本的不断问世，Visual C++已成为专业程序员进行软件开发的首选工具。
虽然微软公司推出了Visual C++.NET(Visual C++7.0) ，但它的应用的很大的局限性，只适用于Windows 2000,Windows XP 和Windows NT4.0。
所以实际中，更多的是以Visual C++6.0 为平台。
Visual C++6.0不仅是一个C++编译器，而且是一个基于Windows操作系统的可视化集成开发环境( integrated development environment,IDE )。
Visual C++6.0 由许多组件组成，包括编辑器、调试器以及程序向导AppWizard 、类向导Class Wizard 等开发工具。
这些组件通过一个名为Developer Studio 的组件集成为和谐的开发环境。
四、算法描述:1.头文件:Stack.hCalculator.hMethod:Stack method:Push(); // 进栈操作Pop(); // 出栈操作GetHead(); // 返回栈中的最顶层元素MakeEmpty(); // 清空栈操作Calculator method:Calculator();// 计算主体celarstream(); // 清空输入流Prior();// 返回运算符的优先级done(); // 做一次二元运算output(); // 打印结果并输出EnEmpty(); // 调用MakeEmpty(), 并清空栈2.cpp 文件Calculator.cppMethod:int main(); // 主程序3.程序流程图优先级比较算法Data 算法存放操作字符 存放数据调用 Calculator 。
《数据结构与算法分析》课程设计报告课题名称：带括号的算术表达式求值课题负责人名（学号）： **********同组成员名单（角色）：戴维指导教师：评阅成绩：评阅意见：提交报告时间：200 年月日课程名称：数据结构学生姓名：戴维学生学号：0743111298带括号的算术表达式求值软件工程专业学生戴维指导老师朱宏一、实验一:带括号的算术表达式求值二、实验的目的和要求:1.采用算符优先数算法,能正确求值表达式;2.熟练掌握栈的应用;3.熟练掌握计算机系统的基本操作方法,了解如何编辑、编译、链接和运行一个C++程序;4.上机调试程序,掌握查错、排错使程序能正确运行。
三、实验的环境:1.硬件环境:Intel(R) Celeron(R)M CPU***********1.60GHz , 0.99Gb内存2.软件环环境:操作系统：Microsoft Windows XPProfessinal 版本2002编译系统版本：MicroSoft Visual C++6.0包括操作系统,编译系统的版本的特点,编辑软件特点等。
四、算法描述:对于带有括号的算术表达式有以下的运算法则：1．先乘方，再乘除，最后加减。
2．同级运算从左到右。
3．先括号内，再括号外。
具体实现如下：1．先建立两个堆栈，一个是操作符堆栈，一个为操作数堆栈。
并且将这两个堆栈先清空，然后在操作符号堆栈当中放入一个“=”，以便在后面方便判断表达式是否结束。
2．从输入流当中读取一个字符，循环执行下面的操作：⑴去出操作符号堆栈的栈顶元素，如果栈顶元素是不是“=”并且如果当前的字符也是“=”的时候，那么表示表达式已经结束了，当前操作数堆栈的栈顶元素就是表达式的值。
⑵如果当前字符不是操作符，就将当前字符放回到输入流当中，读取操作数，并且将操作数加入到操作数堆栈当中，继续读入下一个字符。
⑶如果当前字符是操作符就进行下面的操作：①．如果当前字符不是“+”或者“-”，则在当前字符前面加一个“0”放入到操作数栈当中。
课程设计报告课程名称：数据结构课程设计设计题目：表达式求值（计算器）学院：信息科学与工程学院专业：计算机科学与技术（软件外包）姓名：指导教师：二零一五年十二月二十九日一、设计容与要求1、问题描述设计一个算术计算器，能运算包括四则运算、括号的表达式的运算。
2、设计要求实现（）、+、-、*、/、^ 等运算，实现小数和整数混合运算，优先级的处理，能判断算术表达式是否正确等。
二、算法设计1、输入并建立表达式，运用数组结构体构建将整型数字与操作符结合定义运算符的优先级。
typedef struct yxj{char operat;int rank;}yxj;2、分别建立一个操作数栈和操作符栈存放数字和操作符，定义操作符栈第一个元素优先级最低。
3、自左向右扫描字符串遇到字符串中的数字时一律提取转换成double型存入操作数栈。
遇到操作符时，则将当前运算符的优先级数与运算符栈顶元素的优先级数相比较。
若当前运算符的优先级数大，则进栈；反之，则取出栈顶的运算符，并在数栈中连续取出两个栈顶元素作为运算对象进行运算，并将运算结果存入数栈，然后继续比较当前运算符与栈顶元素的优先级。
直到当前运算符进栈。
4、对比运算符进行+ - * /（）^ 运算。
三、程序代码#include<stdio.h>#include<stdlib.h>#include<string.h>#include<math.h>#define N 100typedef struct yxj{char operat;int rank;}yxj;typedef struct str{char data[N];}zs;void szys(yxj mark[]){yxj os[N];char ch;double ns[N];zs zhan[20];int numb[N];int Len,p=0,q=1,i,o=1,n=0;char data[N];os[0]=mark[0];printf("请输入算术（+ - * / ^）表达式（以 = 结束）：\n");scanf("%s",data);Len=strlen(data);numb[0]=0;for(i=0;i<20;i++)zhan[i].data[0]='\0';for(i=0;i<Len;i++){int t=0;if(data[i]=='^'||data[i]=='+'||data[i]=='-'||data[i]=='*'||data[i]=='/'||data[ i]=='('||data[i]==')'||data[i]=='='){int j,k=0;if((data[i]=='='||data[i]=='^'||data[i]=='+'||data[i]=='-'||data[i]=='*'||data [i]=='/')&&(data[i-1]=='^'||data[i-1]=='+'||data[i-1]=='-'||data[i-1]=='*'||data[i -1]=='/')){printf("格式错误\n");return;}numb[q++]=i;while(zhan[(p+k)/2].data[0]!='\0'){k++;}for(j=numb[q-2];j<numb[q-1];j++)if(data[j]>='0'&&data[j]<='9'||data[j]=='.')zhan[(p+k)/2].data[t++]=data[j];zhan[(p+k)/2].data[t]='\0';if(zhan[(p+k)/2].data[0]!='\0')ns[n++]=atof(zhan[(p+k)/2].data);p++;for(j=0;j<8;j++)if(mark[j].operat==data[i])break;while(1){if(mark[j].operat=='('){os[o++]=mark[j];break;}else if(mark[j].rank>os[o-1].rank&&mark[j].operat!='(') {os[o++]=mark[j];break;}else{double numb1,numb2,numb;ch=os[--o].operat;if(ch=='+'){numb1=ns[--n];numb2=ns[--n];numb=numb1+numb2;ns[n++]=numb;}if(ch=='-'){numb1=ns[--n];numb2=ns[--n];numb=numb2-numb1;ns[n++]=numb;}if(ch=='*'){numb1=ns[--n];numb2=ns[--n];numb=numb2*numb1;ns[n++]=numb;}if(ch=='/'){numb1=ns[--n];numb2=ns[--n];if(numb1==0){printf("无效操作\n");return;}else{numb=numb2/numb1;ns[n++]=numb;}}if(ch=='^'){numb1=ns[--n];numb2=ns[--n];numb=pow(numb2,numb1);ns[n++]=numb;}}}}else if(data[i]>='0'&&data[i]<='9');else if(data[i]=='.');else{printf("格式错误，请重新输入：\n");szys(mark);break;}}printf("%lf\n",ns[0]);}int main (){yxj mark[9];mark[0].operat='#';mark[0].rank=-1;mark[1].operat='+';mark[1].rank=1;mark[2].operat='-';mark[2].rank=1;mark[3].operat='*';mark[3].rank=2;mark[4].operat='/';mark[4].rank=2;mark[5].operat='(';mark[5].rank=-1;mark[6].operat=')';mark[6].rank=-1;mark[7].operat='=';mark[7].rank=0;mark[8].operat='^';mark[8].rank=3;while(1){char i[N];printf("*****1、计算器*****\n");printf("*****0、退出 *****\n");scanf("%s",&i);if(strcmp(i,"0")==0)break;else if(strcmp(i,"1")==0)szys(mark);elseprintf("没有该选项\n");}}四、运行测试1.正常四则运算2.乘方运算3.除数为零时4.格式出现错误5.小数运算五、结论这次课程设计让我们更加了解大一学到的C和这个学期学到的数据结构。
《数据结构与算法分析》课程设计报告课题名称：带括号的算数表达式求值课题设计人（学号）：指导教师：**评阅成绩：评阅意见：提交报告时间：2014 年12月9日带括号的算数表达式求值计算机类专业学生指导老师朱宏[摘要] 在平时的生活中，我们可以解决一些简单的算术表达式，如果当我们遇到一些式子较为冗长，运算比较复杂的算术表达式时，我们都会选择计算器。
那么，计算器又是通过怎样的原理来进行运算的呢。
本程序利用堆栈先进后出的特点，采用操作数和操作符两个堆栈，实现由中缀表达式到后缀表达式的转换并求值的过程。
带括号的算术表达式的求值是堆栈的一个典型的应用实例。
关键词：计算器堆栈C++一、实验名称:带括号的算术表达式求值二、实验的目的和要求:1.采用算符优先数算法,能正确求值表达式;2.熟练掌握栈的应用;3.熟练掌握计算机系统的基本操作方法,了解如何编辑、编译、链接和运行一个C++程序;4.上机调试程序,掌握查错、排错使程序能正确运行。
三、实验的环境：硬件环境：处理器：Inter(R) Core(TM) i7-4500U内存：8.00GB软件环境：操作系统：Windows8.1编译软件：Microsoft Visual Studio 2012四、算法描述:我设计的带有括号的算术表达式求值的程序中，运算符的优先级是这样子的：1.先乘除，后加减2.同级运算从左到右依次运算。
3.先括号内的运算，再括号外的运算。
我的设计思路是，先输入一个最后不带等于号的中缀表达式，先对表达式检查是否有错误，如果有将会输出“表达式有错误”，否则通过堆栈方法将这个中缀表达式转化为后缀表达式，然后将后缀表达式求值。
transform()——用于将中缀表达式转换为后缀表达式calculate()——将后缀表达式进行求值examine()——检查输入的表达式是否有错误main()——主程序。
五：源程序清单：#include<iostream>#include<cmath>#include<stack>#include<string>using namespace std;string transform(string str)//转换为后缀表达式{stack<char> ope;int i;string exp="";for(i=0;i<int(str.size());i++){if(str[i]=='.'||isdigit(str[i])){exp+=str[i];}else if(str[i]=='+'||str[i]=='-'){int j=i-1;if(isdigit(str[j])){exp+=" ";//每个数字的后面都加一个空格加以区分if(ope.empty()||ope.top()=='('){ope.push(str[i]);}else{while(!ope.empty()&&ope.top()!='('){exp+=ope.top();ope.pop();}ope.push(str[i]);}}else{if(ope.empty()||ope.top()=='(') {ope.push(str[i]);}else{while(!ope.empty()&&ope.top()!='('){exp+=ope.top();ope.pop();}ope.push(str[i]);}}}else if(str[i]=='*'||str[i]=='/'||str[i]=='%') {int j=i-1;if(isdigit(str[j])){exp+=" ";if(ope.empty()||ope.top()=='('||ope.top()=='+'||ope.top( )=='-'){ope.push(str[i]);}else{while(!ope.empty()&&ope.top()!='('&&ope.top()!='+'&&ope.top ()!='-'){exp+=ope.top();ope.pop();}ope.push(str[i]);}}else{if(ope.empty()||ope.top()=='('||ope.top()=='+'||ope.top( )=='-'){ope.push(str[i]);}else{while(!ope.empty()&&ope.top()!='('&&ope.top()!='+'&&ope. top()!='-'){exp+=ope.top();ope.pop();}ope.push(str[i]);}}}//}else if(str[i]=='^'){int j=i-1;if(str[j]!=')'){exp+=" ";}ope.push(str[i]);}else if(str[i]=='('){ope.push(str[i]);}else if(str[i]==')'){exp+=" ";while(ope.top()!='('){exp+=ope.top();ope.pop();}ope.pop();}else{return"有错误";}}while(!ope.empty())//遍历完表达式将堆栈中的所有运算符输出{if(isdigit(exp[exp.length()-1])){exp=exp+" "+ope.top();ope.pop();}else{exp=exp+ope.top();ope.pop();}}return exp;}int examine(string str)//检查输入的表达式是否有误{if((isdigit(str[str.length()-1])!=0||str[str.length()-1] ==')')&&(isdigit(str[0])!=0||str[0]=='+'||str[0]=='-'||str[ 0]=='(')){int i;for(i=0;i<int(str.length());i++){if(str[i]=='/'||str[i]=='%'||str[i]=='*'||str[i]=='^') {int a=i+1;if(str[a]=='/'||str[a]=='*'||str[a]=='%'||str[a]==')'||str[ a]=='.'){cout<<"表达式有错误"<<endl;return 1;break;}}else if(str[i]=='+'||str[i]=='-'){int a=i+1;if(str[a]=='/'||str[a]=='*'||str[a]=='%'||str[a]==')'||s tr[a]=='.'||str[a]=='^'){cout<<"表达式有错误"<<endl;return 1;break;}}else if(isdigit(str[i])!=0){int a=i+1;if(str[a]=='('){cout<<"表达式有错误"<<endl;return 1;break;}}elseif(isdigit(str[i])==0&&str[i]!='+'&&str[i]!='-'&&str[i]!='* '&&str[i]!='/'&&str[i]!='^'&&str[i]!='%'&&str[i]!='('&&str[ i]!=')'&&str[i]!='.'){cout<<"表达式有错误"<<endl;return 1;break;}else if(str[i]=='.'){int a=i+1;if(isdigit(str[a])==0){cout<<"表达式有错误"<<endl;return 1;break;}}while(i==str.length()-1){cout<<"表达式正确"<<endl;return 2;break;}}}elsecout<<"表达式有错误"<<endl;return 1;}double calculate(string exp){stack<double> number;double digit;string str="";for(int i=0;i<int(exp.length());i++){if(isdigit(exp[i])||exp[i]=='.'){str=str+exp[i];}else if(exp[i]==' '){const char*p=str.c_str();digit=atof(p);//string转换为doublenumber.push(digit);str="";}else//(exp[i]!='.'&&exp[i]!=''&&!isdigit(exp[i])&&number.size()>=2){double result;double right;double left;right=number.top();number.pop();left=number.top();number.pop();switch(exp[i]){case'+':result=left+right;number.push(result);break;case'-':result=left-right;number.push(result);break;case'*':result=left*right;number.push(result);break;case'/':result=left/right;number.push(result);break;case'%':{int(result)=int(left)%int(right);number.push(result);b reak;}case'^':result=pow(left,right);number.push(result);break;}}}double finalresult=number.top();number.pop();return finalresult;}void main(){int x=1;cout<<"计算表达式"<<endl;cout<<"支持加+ 减- 乘* 除/ 整数取余% 次幂^ 小括号()"<<endl;while(x==1){string str;cout<<"请输入表达式，最后不加等号"<<endl;cin>>str;string exp;int a=examine(str);if(a==2){exp=transform(str);cout<<str<<"="<<calculate(exp)<<endl;}cout<<"继续运算请输入Y，否则按任意键退出"<<endl;char ch;cin>>ch;if(ch=='Y'||ch=='y'){x=1;}else{x=2;}}system("pause");}六、运行结果：这个是一开始运行的情况。
