四川大学《数据结构与算法分析》课程设计报告-带括号的算术表达式

算术表达式的求解-数据结构课程设计报告课程设计报告题目：算术表达式求值一、需求分析 1、设计要求：给定一个算术表达式，通过程序求出最后的结果 1>、从键盘输入要求解的算术表达式； 2>、采用栈结构进行算术表达式的求解过程； 3>、能够判断算术表达式正确与否；4>、对于错误表达式给出提示；5>、对于正确的表达式给出最后的结果； 2、设计构想：为了实现算符优先算法使用两个工作栈，一个称作OPTR，以寄存运算符；另一个称作OPND，用以寄存操作数或运算结果。

在操作数和操作符入栈前，通过一个函数来判别，输入的是操作数还是操作符，操作数入OPND，操作符入OPTR。

在输入表达式的最后输入‘#’，设定‘#’的优先级最低，代表表达式输入结束。

在表达式输入过程中，遇操作数则直接入栈，遇到运算符则与栈顶运算符比较优先级,若当前运算符优先级高，则当前运算符入栈,扫描下一符号;否则栈顶运算符出栈,两操作数出栈,进行运算,所得结果入数栈,重新比较当前运算符与新栈顶运算符。

如此重复直到栈顶运算符与当前符号均为‘#’，运算结束。

二、概要设计1、本程序包含的模块：栈模块——实现栈抽象数据类型运算模块——实现数据表达式的运算主程序模块算术运算式的求解栈模块主函数模块main 运算模块定义栈结构初始化栈出栈入栈取栈顶元素判断输入字符类型判断符号优先级基础运算函数运算函数三、详细设计栈模块1、定义栈结构 struct Sqstack{elemtype *top;//栈顶元素 elemtype *base; //栈底元素 int stacksize;//栈的大小 };2、栈的基本操作①初始化栈status initstack(struct Sqstack &s) {=(elemtype *)malloc(stack_size*sizeof(elemtype)); if(!) return OVERFLOW; =;=stack_size; return OK; } ②入栈status push(struct Sqstack &s,elemtype e) {if(>=) {=(elemtype*)realloc(,(+stack_increasement)*sizeof(elemtype));if(! ) return OVERFLOW; =+; +=stack_increasement; } * ++=e; return OK; } ③出栈elemtype pop(struct Sqstack &s) {elemtype e; if(= =) return ERROR; e=*--;return e; }④取栈顶元素elemtype gettop(struct Sqstack &s) {elemtype e; if(==) return ERROR; e=* ; return e; } 运算模块1、判断输入字符c是否为操作符：若是，则返回1；否则，返回0 int In(int c) {char p[10]=\ int i=0;while(p[i]!='\\0') {if(p[i]==c) return 1;i++; } return 0; }2、判断运算符的优先级char precede(char top,char c)//该函数为判断当前运算符与前一个运算符的优先级，前一个运算符高于或等于当前运算符的优先级则返回‘>’，前一个运算符小于当前运算符的优先级则返‘'; break; case '+': case '-':if(top=='#'||top=='(')result=''; break; case '*': case '/':if(top=='*'||top=='/'||top=='^') result='>'; elseresult=''; elseresult=''; break;case '(': result='': theta=pop(optr); b=pop(opnd); a=pop(opnd); push(opnd,operate(a,theta,b)); break;// 若当前操作符的优先级低于操作符栈的栈顶元素，则将操作符栈栈顶元素出栈，并将操作数栈的栈顶两个元素出栈，计算两个元素间以操作符栈栈顶元素为运算符的数学运算}//switch }//if}//whilereturn pop(opnd); }主程序模块1、main函数void main(int argc,char *argv) {struct Sqstack opnd; //操作数栈 struct Sqstack optr;//操作符栈initstack(opdn); initstack(optr); elemtype result;printf(\ printf(\算术运算式的求解\printf(\ printf(\请输入算术运算表达式(以'#'结尾):\\n\ printf(\result=evaluate(opnd,optr);printf(\printf(\运算的结果是 :\\n \\n%d\\n\printf(\}四、调试分析 1、测试结果1> 测试数据：3+7*2-1# 测试结果：2> 测试数据：(3+7)*2-1# 测试结果：3> 测试数据： 1/0# 测试结果：2、程序时间复杂度为O；3、设计中出现的问题：在开始的设计中没有注意除数不能为0 ，后来加入if(b==0) {printf(\分母为0,the result is error\\n\ result=0; } elseresult=a/b;break;来判断除数是否为0 4、算法改进：1>输入的操作数和操作码于是字符串类型的，在原设计中实现的操作都是对个位数实现的，实用性不大，故在后来的设计中，通过一个标志flag实现了标志操作数的连续输入的判别，继而实现了多位数的表达式运算2>开始只实现了加、减、乘、除及带小括号的数学运算，考虑到实用性，在后来的设计中引入pow函数，实现了乘方的运算，调整结果如下：3>最初设计的运行界面过于单调，不够友好，改进时加入一些*调整调整结果如下：五、课程设计总结本学期是我第一次接触课程设计，发现了很多学习上的问题，也有很多收获。

川大数据结构课程设计一、课程目标知识目标：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；｝五、算法及时间复杂度１、算法:建立两个不同类型得空栈,先把一个‘＃’压入运算符栈。

数据结构课程设计---括号匹配⽬录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 10char *base;char *top;int stacksize;}SqStack;2.2主要算法设计2.2.1算法思想(1)⽂字描述从键盘输⼊⼀个表达式；逐个扫描表达式中的字符；当遇到左括号时，将左括号⼊栈；继续扫描，将此后遇到的第⼀个右括号与栈顶元素⽐较，若匹配，则栈顶元素出栈；否则，继续扫描；当整个表达式扫描完以后，判断栈内是否还有元素，若有，则括号不匹配；若栈为空，则括号配对成功；在括号配对不成功的情况下，利⽤栈顶栈底元素的差值，可以对左右括号数进⾏⽐较。

（2）流程图表⽰2.2.2算法void CharIsCorrect(char a[]){SqStack S;char e;int n,c;InitStack(S);//建⽴⼀个空栈n=strlen(a);//求表达式长度int d=0,b=0;for(int i=0;iif((a[i]=='(')||(a[i]=='[')||(a[i]=='{'))Push(S,a[i]);else{c=StackEmpty(S);if ((c==1)&&((a[i]==')')||(a[i]==']')||(a[i]=='}')))//栈为空且当前扫描的字符为右括号时，右括号多于左括号++b;else{e=GetTop(S);if (((a[i]==')')&&(e=='('))||((a[i]==']')&&(e=='['))||((a[i]=='}')&&(e=='{')))//括号匹配时满⾜的条件e=Pop(S);else if ((a[i]==')')||(a[i]==']')||(a[i]=='}'))++d;}}}//扫描字符串，左括号进栈，右括号出栈if(StackEmpty(S)==1&&(b==0)&&(d==0))cout<<"左右括号配对正确"<else cout<<"左右括号不匹配且左括号与右括号个数差为"<}2.3测试⽤例及测试结果（1）表达式不含除括号外其他字符，配对正确的情况：（2）表达式不含除括号外其他字符且左括号少于右括号的情况：（3）表达式含任意字符且左括号少于右括号的情况：（4）表达式含任意字符且左右括号个数相同但配对不成功的情况：（5）表达式仅含括号且括号个数相同单不匹配的情况：（6）表达式仅含括号且左括号对于右括号的情况：3调试报告1.本次课程设计，主要的调试过程在于对于判别函数的调试，但是除此之外，由于编译过程中发现了⼀些错误，对于栈的⼀些基本操作，以及main函数，也进⾏了调试，其中遇到的主要问题如下：(1)⼤⼩写出错(2)在写“判断栈是否为空”的操作时，将函数的类型标⽰符写错，导致了如下错误：解决办法：将“void”改为“int”后，能够正常运⾏。

四川大学《数据结构》课程设计实验项目及内容提要(实验任选一个完成)
试读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）：重置操作和自己输入文本是一样的，在这里就不演示了，有兴趣可以自己尝试。

实验课程名称专业班级学生姓名学号指导教师20 至 20 学年第学期第至周算术表达式求值演示一、概述数据结构课程设计.要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面.加深对课程基本内容的理解。

同时.在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。

在这次的课程设计中我选择的题目是算术表达式求值演示。

表达式计算是实现程序设计语言的基本问题之一.也是栈的应用的一个典型例子。

设计一个程序.演示用算符优先法对算术表达式求值的过程。

深入了解栈和队列的特性.以便在解决实际问题中灵活运用它们.同时加深对这种结构的理解和认识。

二、系统分析1．以字符列的形式从终端输入语法正确的、不含变量的整数表达式。

利用已知的算符优先关系.实现对算术四则混合运算表达式的求值.并仿照教科书的例子在求值中运算符栈、运算数栈、输入字符和主要操作的变化过程。

2．一般来说.计算机解决一个具体问题时.需要经过几个步骤：首先要从具体问题抽象出一个适当的数学模型.然后设计一个解决此数学模型的算法.最后编出程序.进行测试.调试直至得到想要的答案。

对于算术表达式这个程序.主要利用栈.把运算的先后步骤进行分析并实现简单的运算！为实现算符优先算法.可以使用两个栈.一个用以寄存运算符.另一个用以寄存操作数和运算结果。

3．演示程序是以用户于计算机的对话方式执行.这需要一个模块来完成使用者与计算机语言的转化。

4．程序执行时的命令：本程序为了使用具体.采用菜单式的方式来完成程序的演示.几乎不用输入什么特殊的命令.只需按提示输入表达式即可。

（要注意输入时格式.否者可能会引起一些错误）5. 测试数据。

三、概要设计一个算术表达式中除了括号、界限符外.还包括运算数据和运算符。

由于运算符有优先级别之差.所以一个表达式的运算不可能总是从左至右的循序执行。

每次操作的数据或运算符都是最近输入的.这与栈的特性相吻合.故本课程设计借助栈来实现按运算符的优先级完成表达式的求值计算。

表达式计算1、问题描述与分析算数表达式一般都写成中缀形式，即运算符总是出现在两个操作数之间（单目运算符除外），称为中缀表达式。

编译系统对中缀表达式的处理方法是先把它转换为后缀表达式。

在后缀表达式中，运算符位于两个操作数的后面，并且没有括号，其运算符次序就是其执行计算的次序。

后缀表达式计算过程的规则非常简单：从左到右依次扫描，当读到运算符时，就对该运算符前面的两个操作数执行相应的运算，直至得到表达式的结果。

本程序主要模拟编译系统计算中缀表达式的过程，先将中缀表达式转换成相应的后缀表达式，再根据后缀表达式计算出表达式的值。

这个问题的解决主要是栈的一个应用。

因为本程序仅是模拟，没有判断输入的中缀表达式是否合法，容错性不强，另外也仅能对一位数的中缀表达式进行转换和计算，功能上还有许多局限性，本程序处理的中缀表达式中仅允许出现六种运算符，且都是双目运算符。

2、数据结构设计和基本算法设计方法的选择2.1 中缀表达式转换成后缀表达式为完成中缀表达式转换成相应的后缀表达式，设计了infix2postfix类。

为了方便用户使用，它只有4个接口函数，包括两个构造函数，一个设置中缀表达式的函数setInfixExp 和一个返回后缀表达式的函数postfixExp。

所有表达式均采用string来存储，运算符用堆栈来临时存储，并用map的数据结构来定义优先级。

下面给出了infix2posfix类的声明和部分定义。

class infix2postfix{public:infix2postfix(){};infix2postfix(const string& infixExp):infix(infixExp){};void setInfixExp(const string& infixExp){infix=infixExp;};string postfixExp();private:string infix; //用于转换的中缀表达式string postfix; //后缀表达式stack<string> stk;//用于存储运算符的堆栈map<string,int> oper_prio;//用于存储运算符的优先级void set_priority();//设置运算符('+','-','*','/','%','^')的优先级};中缀表达式转换成后缀表达式功能的实现是栈的一个典型应用，主要应用栈的“后进先出”的特性及预先设计好的运算符优先级。