数据结构课程设计报告_ip数据包捕获与分析

1、中南大学数据结构课程设计报告题 目数据结构课程设计学生姓名廖成指导教师畅金学 院信息科学与工程学院专业班级计算机科学与技术1304班二o五年九月目录1. 需求分析31. 1问题描述31. 2基本要求32. 总体设计32. 1数据结构32. 2模块间调用关系32. 3各模块设计42. 3. 1判读运算符优先级模块42. 3. 2表达式转换模块42. 3. 3表达式求值模块63. 详细设计74. 调试与测试95. 测试结果106. 课程设计心得体会12参考文献13附录131.需求分析1.1问题描述表达式求值是实现程序设计语言的基本问题么一，也是栈的应用的一个典型，设计程序 演示用算符优先法对算术表

2、达式求值的过程。1. 2基本要求(1) 以字符序列的形式从终端上输入语法正确的、不含变量的表达式。实现对算术四则 运算表达式，对任意算术表达式的加法、减法、除法以及乘法求值。(2) 运算数包括整数和小数处理。(3) 演示在求值中运算符栈、运算数栈、输入字符和主要操作的变化过程。(4) 计算器的功能仿真。2. 总体设计2. 1数据结构使用两个数组si, s2分别保存输入的中缀表达式和转换后的后缀表达式。通过使 用char类型栈和double类型栈分别对运算符和操作数执行相应的操作，该栈由vc编 译器支持，声明如下：stack<char> sc;/声明栈sc,对运算符操作stack&l

3、t;double> sf;/声明栈sf,对操作数操作22模块间调用关系2. 3各模块设计2. 3. 1判读运算符优先级模块该模块的功能是判断各种运算符的优先级别，参数是字符型变量op，返回类型为 整型，优先级越高的运算符返回的整型数据越大。2. 3. 2表达式转换模块特殊字符'#'压人字符栈sc,用以判断是否结束表达式的转换。逐个取出数组s1 中的元素，如果是空格字符则不作任何处理；如果是'（'则入栈sc；如果是'）'则 依次将栈顶元素放入数组s2并出栈，直到栈顶元素为'（，再执行一次出栈；如果 是运算符则判断其与当前栈顶元素优先级

4、高低，如果较低则将栈顶元素写入数组s2中, 直到优先级较高然后将其入栈；如果是数字或者小数点，则直接写入到数组s2末尾， 直到遇到字符串结束符'0'。将栈sc中剩余元素写入数组s2末尾并出栈，直到特殊 字符结束表达式的转换。经过以上步骤，保存在si中的中缀表达式转换成后缀表 达式并保存在s2数组中，可以用后缀表达式求值模块计算原表达式的值。2. 3. 3表达式求值模块定义双精度类型变量保存操作数的整数和小数部分，逐个字符扫描s2中的后缀表 达式，如果是空格则不执行任何操作；如果是运算符则从栈sf中取出操作数并执行相 应的运算并把运算结果压入操作数栈sf;如果是数字或者小数点则通

5、过相应的方法计 算出操作数并压入操作数栈sf屮直到遇到字符串结束符,此刻操作数栈中应该只有一个元素，此元素即为表达式的值。3. 详细设计char d_sc_pop() ;/返冋栈顶元素(运算符)并执行一次出栈操作由于在实现表达式求值时要执行多次取栈顶元素并出栈操作，在每次出栈之前都需要检 验栈当前是否为空，而且収栈顶和出栈操作也要分步实现，这样会产牛很多冗余代码，本函 数把这些操作封装在一个函数中，调用该函数即可实现从运算符栈出栈并返回栈顶元素，使 代码看起来更简洁，紧凑。具体实现细节如下：char d_sc_pop()ifdsc. empty()/执行出栈操作前判断栈是否为空a二sc. to

6、p ();/取栈顶元素，并保存在变量a中cout«/z 出栈运算符：a«endl;sc. pop ();/对运算符栈执行一次出栈操作elsecout«/zerror: stack is empty!/z«endl;exit(o);/如果栈为空，提示错误并退出程序return a;/返回栈顶元素double d_sf_pop() ;/返回栈顶元素(操作数)并执行一次出栈操作该函数跟char d_sc pop()函数类似，调用该函数即可从操作数栈屮出栈一个元素并将该元素返回，具体实现细节如下：double d_sf_pop()b=sf. top();/取栈顶

7、元素，并保存在变量b中cout«tb栈操作数:z/«b«endl:sf. pop () ；/对操作数执行一次出栈操作elsecout«z，error: stack is empty! z，«endl;exit(o);/如果栈为空，提示错误并退出程序return b;/返冋栈顶元素int d_pre(char op) ;/判断运算符的优先级，优先级越高的返回值越大要求表达式的值就必须能对表达式中各种运算符做优先级判断，根据不同的优先级做不 同的处理。该函数对传入的参数做优先级的判断，根据优先级的不同，返回的int型数值也 不同，运算符的优先级越高

8、，返冋的数值越大。具体实现细节如下：int d_pre(char op)switch(op)case ' +':case ' -':retum 1;case ':case ' /':return 2;casedefault:return 0;void d_tras（char si, char s2）;该函数的作用是将输入的中缀表达式（保存在数组si中）转换为后缀表达式（保存在 数组s2屮）。通过逐个字符扫描表达式，根据运算符的优先级将输入的屮缀表达式转换成 后缀表达式，返回类型为空。具体实现细节参见附录中源代码。double d_cmpu

9、（char str）;/求中缀表达式str的值并返冋该函数对转换后的后缀表达式求值，参数为保存后缀表达式的数组，返回值是表达式的 计算结果。该函数实现了加、减、乘、除、乘方以及取负的复合运算，具体实现细节参见附 录中的源代码。4. 测试与调试分析一开始实现了整数和小数的加减乘除运算，也做了表达式的合法性检查；通过测试表明 成功实现了基本的表达式求值。通过后面的改善，添加了求乘方和取负的操作，实现方式是 通过一个bool型标志位'（j标志把单目运算符的取负与双目运算符的减法相区分，可以 实现对加过括号的取负执行正确的操作，但是如果表达式的笫一个操作数是单目运算符，即 表达式开始的取负不必

10、用括号，对这种比较特殊的情况则会出错；经过反复思考单目与双目 运算符的区别后发现，如果对表达式的第一个元素填充特殊字符'#'后，减号前面如果不 是操作数并且不是'）'则一定是单目运算符，在做入栈操作前将其替换为宀'，且其优 先级最高，这样就避免了对上述特殊情况的考虑。最终经过改写代码完美实现了单目运算符 操作。5.测试结果(1)加减法的复合运算"d:program files (x86)microsoft visual达表3的>/m u < * 一 / % 计t :符符=8;6丄7二 5 7;68:7;数数：数数.数t 要54考畫薑

11、量真层畫54入芫元元运元运元运-箧兀 舊元元霍元元援元操+6s > 6 3 2fffi>3戋戋浅戋戋戋戋戋養笺戋戋戋戋戋桟桟我戋戋戋戋戋!3511144 2请<1入入入<3出出入出出入入出出入入出出入出i<10 e y0k(2)带小数的四则运算23<21'-人41y戋戋戋戋戋戋戋戋戋戋戋戋爰戋戋戋戋戋戋戋戋戋戋戋戋戋戋爲tt -询2符.持技墨：薮数：数数；数数:i 数.59 薑>«曇®-m量s-素畫 " 元元元元元运元运元运运运表元元元蠻元元援元元援元援元操:3 義:一岀后4八蚩（3）单目运算符出现在表达式首*d:

12、program files (x86)microsoft visual studiomyprojectsheh<式表算ttz : * 为 9 : - 1 2 : : 2 : : 1 :5k 讦；符： 纵数纵馥数数1 y 要2h0b素恚悬晟蔻多墾畫雀2=“ a2*-兀一兀运一兀一兀运运运表帀操一兀一兀一 _8- 8-兀操2* 膏入人出入入出出出冥出入入入出出入岀出入出9 - - 1 2 - 1 -otye2 s is b9 r -p（4）单目运算符在表达式中间"*d:program files (x86)microsoft visual studiomyprojectshehe式

13、表w要*2素丰ttto continue、丿3 输<- 青一勺 3 6 5 5 e-< -:* 斗/ 9 3 : - 2 : : - 2 : 1 :1k 符:数：数数.数数.数-y >>bab-mtow墾*2 兀运元运运运表兀元操元元養元蠶元操3> j戋戋戋戋戋<戋戋歩 产产k产产參k k kj 入出入出出出昊入出入入出出入出出入出9-pr戋戋j产旻s 戋戋戋戋戋戋戋戋一 s -mtkjk 产 k < e（5）含有单目运算符的混合运算*8 一| *d:program5 2、一丙一一一、一、一二一二、一二一、一f 22克22克葬2郵髡出入入出入入出出入出

14、熒入出出入出tq台d 11 -* : : - - -7 丄- 8 - 2 - : - 8 - - - 符尊:数：数：数数：饕：数数数8>5 6 = 3 86 一 一 3 268 18 2 一 6 一8 1.58*2tt 8>符 ；： i j 素恚量fs昇恚»昇mb希 j 芫运兀元元运元运运元运运表兀操元元操元元蠻元蠶元元蠶元操5+ 戎啖我桟我桟戎桟戎戎桟我戎6. 课程设计心得体会通过本次课程设计，我再一次熟悉了数据结构课程相关的知识，常握了如何将数据结构 所学的知识合理应用于实践屮并在实践屮总结经验，发现自己在实践中存在的不足之处，通 过查阅相关的资料，弥补自己的知识漏洞

15、，在实践中完善和提高自己；通过实践操作发现自 己在编程中存在一些问题，比如考虑问题不够全面，对程序的需求分析不够仔细，导致最后 的结果不是那么完美，当完成程序设计时再去修改程序的实现方式或者添加新的功能会比较 麻烦，所以在以后的程序设计中会注意这方面的问题，在程序设计之前充分做好需求分析与 总体设计。另外，次课程设计只实现了基本的要求，由于之前学习c+编程的时候没有对界 面编程的学习，在如此仓促的课程设计时间内也没有掌握如何使用mfc实现c+的界面编程, 因此在本次课程设计中没有实现对计算器的功能模拟，我会在以后学习相关知识，弥补自己 的知识漏洞，不断完善自己，我相信通过自己经验的积累，在以后

16、的实践屮会显得更加得心 应手，自己的程序设计水平也会逐步上升。参考文献1数据结构(c+版)/陈宝平主编.-北京：清华大学出版社，2012. 2数据结构与算法：理论与实践/唐培和，徐奕奕编著一北京：电子工业岀版社，2015. 1附录：源代码清单：/head, h 文件#include<string>#include<stack>#include<cmath>int d_pre (char op) ;/判断运算符的优先级char d_sc_pop() ;/从字符栈出栈并返回栈顶元素double d_sf pop() ;/从数据栈出栈并返回栈顶元素void d_t

17、ras (char si , char s2j) ;/将中缀表达式转换为后缀表达式double d cmpu(char str);/求中缀表达式的值/head, cpp 文件#include"head. h"# i nc1ude<iostream>using namespace std;stack<char> sc;/声明栈sc,对运算符操作stack<double> sf;/声明栈sf,对操作数操作char a;double b;/判断运算符的优先级，返回整形数据，优先级越高的返回值越人int d_pre(char op)switch

18、(op)case ' +':case ' -'：return 1;case ' *': case ':return 2;case:return 3;case:return 4;default:return 0;/返冋栈顶元素(运算符)并执行一次出栈操作char d sc pop ()if(!sc.empty()/执行出栈操作前判断栈是否为空a二sc. top ();/取栈顶元素，并保存在变量a中 cout<<"出栈运算符:/z«a«endl;sc. pop ()；/对运算符栈执行一次出栈操作els

19、ecout<<，zerror: stack is empty!，z<<endl;exit(0);/如果栈为空，提示错误并退出程序return a;/返回栈顶元素/返回栈顶元素(操作数)并执行一次出栈操作double d_sf_pop()if (!sf. emptyo)/执行岀栈操作前判断栈是否为空b=sf. top() ;/取栈顶元素，并保存在变量b中cout«，z出栈操作数:，z«b«endl;sf. pop ()；/对操作数执行一次出栈操作else!cout«/zerror: stack is empty!z/«en

20、dl;exit(o);/如果栈为空，提示错误并退出程序return b;/返冋栈顶元素/将中缀表达式转换为后缀表达式，si为中缀表达式，s2为后缀表达式void d tras(char si, char s2)/sc. pushc #' ) ；/将特殊字符压栈，用于判定是否结束int i=0, j=0;/i, j变量分别指示数组si和s2的下标,初始时指向第一个元素char ch=sli;/取出数组si的第一个元素while(ch!='0')/扫描屮最表达式，如果不是结束符，则执行下面的操作if(ch=' ')/跳过输入的空格ch二sl+i；/i指针向右

21、移动，并取出中缀表达式数组s1的下一个元素else if(ch=' (' |ch='#')/如果是左括号,入栈!sc. push (ch);cout«/?入栈元素：ch«endl;ch二si 卄i;/i指针向右移动，并取出中缀表达式数组si的下一个元素else if (ch二二')')whi 1 e (sc. top() !二'(')s2j+二d_sc_pop() ;/出栈，保存在后缀表达式数组s2中sc. pop ()；/移除栈顶的左括号ch二sl+i;/i指针向右移动，并取出中缀表达式数组si的下一个元素e

22、lse if (ch 二二'+'| | ch 二二'_'| | ch 二二,*，h ch 二二'/' ch二二, | | ch二二',)char op=sc. top() ;/取出栈顶运算符if (ch二二'-'&&(sl i-叮 >'9' | | si ito' )&&sl it!二')')ch= ;while (d_pre (op) >=d pre (ch)/如果栈顶运算符优先级较高，则出栈并存入数组s2中s2j+=op;cout<

23、;<，/出栈运算符："op<endl ;sc. pop ()；/出栈后取新的栈顶元素op二sc. top ();sc. push (ch) ;/将 ch 入栈cout«/，入栈元素："chendl;ch=sl+i ;/i指针向右移动，并取出中缀表达式数组si的下一个元素elseif(ch<，o' | |ch>'9')&&ch!二!cout«z，error:表达式中存在非法字符!，z«endl;exit(o);/如果输入的表达式存在非法字符，提示错误并退出程序while (ch>

24、;=，o' &&ch二'9') | | ch二二'.')!s2j+二ch;/如果是操作数，直接放入数组s2中ch二sl+i;/i指针向右移动，并取出中缀表达式数组si的下一个元素s2j+=' '/加入空格,将每个数据分割开/表达式扫描完成，while循环结束ch二d_sc_pop ();讪ile(ch!#')/取栈顶并出栈，判断栈中元素是否全被取出if (ch二二(')cout<<z/error:表达式中括号不匹配！ "endl;exit(o);/如果剩余左括号，提示错误信息并结束程序

25、else s2j+二ch;/将剩余的操作数或者运算符依次岀栈并写入数组s2屮 ch=d_sc_pop ();s2 j+=' 0' ;/在数组s2末尾添加结束符/求后缀表达式的值，参数为保存后缀表达式的数组double d_cmpu(char str)double x, y;/x, y保存操作数的整数和小数部分int i=0;/i指示待操作数组元素while (str i!二'0,)if(stri='')i+；switch(str i)case'+':/如果为'+ '运算符，从栈中取出两个操作数并执行加法操作，运算结果暂存在x中x=d sf pop ();x+=d sf pop ();i+；break;case'-':/如果为'-'运算符，从栈中取出两个操作数并执行减法操作，运算结果暂存在x屮x二d sf pop();x二 d_sf_pop() -x;break;case :x=o-d sf pop();i+；break;case'*':/如果为'* '运算符，从栈中取出两个操作数并执行乘法操作，运算结果暂存在x中x=d_sf_pop();x*二d