括号的匹配
1.需求和规格说明
（1）实现括号的是否匹配的判定。
（2）实现匹配错误的提示。
（3）实现栈内容的动态显示。
2．设计
2.1．设计思想
（1）对于括号匹配的判定，首先输入字符串到缓冲区。逐个字符读取字串，遇到的是左括号则入栈，若是右括号，则出栈。出栈的左括号如果和右括号匹配，则一对括号匹配成功；否则，这对括号匹配失败，并给出错误提示。
（2）分析括号匹配错误出现的情况，主要有三种：左括号数大于右括号数，左括号与右括号不匹配，右括号数大于左括号数。根据栈的存储情况就能判定出这三种情况，并且实时的将信息放映到可视化控件上。
（3）对于匹配过程和栈内容的动态显示，可以用listbox控件实时的显示和更新。窗口上有两个listbox控件，第一个动态显示push和pop动作以及提示错误信息；第二个listbox则动态模拟栈内的存储情况。
2.2．设计表示
(1)存储结构
Node节点
template
class Node
{
public:
element ele;
Node *pre; //前驱指针
Node *next; //后继指针
Node()
{
pre=NULL;
next=NULL;
}
Node(element e)
{
ele=e;
pre=NULL;
next=NULL;
}
Node * MakeNode(element e)//传入参数返回一个节点指针，实现参数的封装。
{
Node
return temp;
}
};
MyListStack链栈
template
class MyListStack
{
public:
Node
Node
int index;
MyListStack() //初始化链表
{
base=new Node
top=base;
index=0;
}
void push(element n) //push
{
Node
top->next=temp;
temp->pre=top;
top=temp;
index++;
}
void pop(element & out) //pop
{
out=top->ele;
top=top->pre;
delete top->next;
top->next=NULL;
index--;
}
BOOL isEmpty(); //返回栈是否为空
{
if(index)
return FALSE;
else
return TRUE;
}
virtual ~MyListStack() //析构链栈，释放空间。
{
Node
Node
while(p->next!=NULL)
{
delete p;
p=q;
q=p->next;
}
delete p;
}
};
(2)涉及的操作
void CKuohaopipeiDlg::OnButtonClear() //清空窗口控件。
void CKuohaopipeiDlg::OnButtonSlowShow( //慢速显示运行过程。
void CKuohaopipeiDlg::OnOK() //进行括号匹配过程。
void CKuohaopipeiDlg::OnSelchangeListInfo() //此函数响应列表框中光标改变的消息，定位错误的位置。
2.3．实现注释
（此部分见源代码中注释）
2.4．详细设计表示
(1)流程示意图
图表 1 匹配流程示意图（2）功能示意图
图表 2 功能示意图
3．用户手册
(1)在编辑框中输入表达式串。
(2)点击开始匹配测试则进行快速匹配。
(3)点击慢速运行。
(4)点击错误信息，定位错误字符。
4．调试报告
输入：{{{[1+1]+(A+d)}}} 结果：正确
输入：{{{{}}}})) 结果：错误
输入：}()){}} 结果：错误
输入：([][])) 结果：错误
5.源代码及运行结果截图
(1)源代码
void CKuohaopipeiDlg::OnOK()
{
// TODO: Add extra validation here
UpdateData(TRUE);
//MyListStack
m_list_info.ResetContent(); //清空list
m_list_stack.ResetContent(); //清空list
BOOL isNum=0;
BOOL isError=0;
int inputlength=m_cstring_input.GetLength();
if (inputlength==0)
{
MessageBox("输入值不能为空!","提示"); //如果字符串为空}
else
{
for(int j=0;j { char str_in=m_cstring_input.GetAt(j); if (str_in=='('||str_in=='['||str_in=='{') { isNum=1; ls.push(str_in); //若为左括号则入栈 CString temp; temp.Format("push %c into stack \r\n",str_in); m_list_info.AddString(temp); } else if(str_in==')'||str_in==']'||str_in=='}') //若为右括号则出栈匹配 { isNum=1; char str_out; if (!ls.isEmpty()) { ls.pop(str_out); BOOL flag=0; if (str_in==')'&&str_out=='(') { flag=1; } if (str_in==']'&&str_out=='[') { flag=1; } if (str_in=='}'&&str_out=='{') { flag=1; } if (!flag //如果匹配不成功,则isError变量为1，并更新提示信息。 { isError=1; CString temp; temp.Format("push %c but can not match %c <--error!",str_out,str_in); m_list_info.AddString(temp); } else //如果匹配成功,更新提示信息。 { CString temp; temp.Format("pop %c out of stack \r\n",str_out); m_list_info.AddString(temp); } } else //如果当前栈为空，且输入为右括号时，isError为1，并更新控件信息。 { isError=1; CString temp; temp.Format("can not match %c <--error!",str_in); m_list_info.AddString(temp); } } m_list_info.RedrawWindow(); UpdateData(FALSE); } if (!ls.isEmpty())//如果栈最后不为空，且栈中还有左括号，则提示栈中左括号没有匹配完成。 { char temp; ls.pop(temp); ls.push(temp); if (temp=='('||temp=='{'||temp=='[') { CString temp; temp="stack is not empty <--error!"; m_list_info.AddString(temp); } } if (ls.isEmpty()&&isNum==1&&!isError) { m_list_info.AddString("match success!"); MessageBox("匹配成功!","提示"); } else if ((!ls.isEmpty()&&isNum==1)||isError) { m_list_info.AddString("match failed!"); MessageBox("匹配失败!","提示"); } else if (isNum==0) { MessageBox("表达式中未出现括号!","提示"); } } char temp; while (ls.index!=0) { ls.pop(temp); } ((CEdit*)GetDlgItem(IDC_EDIT_INPUT))->SetFocus(); ((CEdit*)GetDlgItem(IDC_EDIT_INPUT))->SetSel(0,-1); } void CKuohaopipeiDlg::OnButtonSlowShow() //慢速显示运行过程 { // TODO: Add your control notification handler code here // TODO: Add extra validation here m_list_info.SetRedraw(); m_list_stack.SetRedraw(); UpdateData(TRUE); m_list_info.ResetContent(); m_list_stack.ResetContent(); BOOL isNum=0; //判断是否出现括号 BOOL isError=0; //判断是否出现错误 int inputlength=m_cstring_input.GetLength(); //获取输入字串长度if (inputlength==0) { MessageBox("输入值不能为空!","提示"); } else { for(int j=0;j { char str_in=m_cstring_input.GetAt(j); if (str_in=='('||str_in=='['||str_in=='{') //如果为左括弧，则入栈。 { isNum=1; ls.push(str_in); CString temp; temp.Format("push %c into stack \r\n",str_in); m_list_info.AddString(temp); m_list_info.SetCurSel(m_list_info.GetCount()-1); temp.Format("%c",str_in); m_list_stack.AddString(temp); } else if(str_in==')'||str_in==']'||str_in=='}') //如果为右括弧 { isNum=1; char str_out; if (!ls.isEmpty()) { ls.pop(str_out); //pop括号，判断是否匹配 BOOL flag=0; if (str_in==')'&&str_out=='(') { flag=1; } if (str_in==']'&&str_out=='[') { flag=1; } if (str_in=='}'&&str_out=='{') { flag=1; } if (!flag) { isError=1; //如果不匹配，则此变量为真，便于函数末尾判断。 CString temp; temp.Format("push %c but can not match %c <--error!",str_out,str_in); //将信息传入控件 m_list_info.AddString(temp); m_list_stack.DeleteString(m_list_stack.GetCount()-1); m_list_info.SetCurSel(m_list_info.GetCount()-1); } else //如果匹配成功，将信息显示到控件。 { CString temp; temp.Format("pop %c out of stack \r\n",str_out); m_list_info.AddString(temp); m_list_stack.DeleteString(m_list_stack.GetCount()-1); m_list_info.SetCurSel(m_list_info.GetCount()-1); } } else { //如果栈中无括号了，且输入括号为右括号。 isError=1; CString temp; temp.Format("can not match %c <--error!",str_in); m_list_info.AddString(temp); m_list_info.SetCurSel(m_list_info.GetCount()-1); } } m_list_info.RedrawWindow(); //重画控件 m_list_stack.RedrawWindow(); Sleep(600); UpdateData(FALSE); } if (!ls.isEmpty()) //如果栈中还有左括号，说明右括号的数量小于左括号的数量。{ char temp; ls.pop(temp); ls.push(temp); if (temp=='('||temp=='{'||temp=='[') { CString temp; temp="stack is not empty <--error!"; //提示栈中还有未匹配的左括号。 m_list_info.AddString(temp); m_list_info.SetCurSel(m_list_info.GetCount()-1); } if (ls.isEmpty()&&isNum==1&&!isError) { m_list_info.AddString("match success!"); MessageBox("匹配成功!","提示"); } else if ((!ls.isEmpty()&&isNum==1)||isError) { m_list_info.AddString("match failed!"); MessageBox("匹配失败!","提示"); } else if (isNum==0) { MessageBox("表达式中未出现括号!","提示"); } } char temp; while (ls.index!=0) //清空栈中的内容 { ls.pop(temp); } ((CEdit*)GetDlgItem(IDC_EDIT_INPUT))->SetFocus(); ((CEdit*)GetDlgItem(IDC_EDIT_INPUT))->SetSel(0,-1); } void CKuohaopipeiDlg::OnButtonClear() { // TODO: Add your control notification handler code here ((CEdit*)GetDlgItem(IDC_EDIT_INPUT))->SetWindowText(""); //此函数中清空所有编辑框和listbox中的记录 m_list_info.ResetContent(); m_list_stack.ResetContent(); m_list_info.RedrawWindow(); //重画所有的控件 m_list_stack.RedrawWindow(); } void CKuohaopipeiDlg::OnSelchangeListInfo() //此函数响应列表框中光标改变的消息，定位错误的位置。 { // TODO: Add your control notification handler code here int i; i=m_list_info.GetCurSel(); if(i!=LB_ERR&&i ((CEdit*)GetDlgItem(IDC_EDIT_INPUT))->SetFocus(); //定位错误 ((CEdit*)GetDlgItem(IDC_EDIT_INPUT))->SetSel(i,i+1); } else { ((CEdit*)GetDlgItem(IDC_EDIT_INPUT))->SetFocus(); //定位错误 ((CEdit*)GetDlgItem(IDC_EDIT_INPUT))->SetSel(0,-1); } } （2）运行截图 图表 3 运行效果图1 图表 4 运行效果图2 《数据结构课程实验》大纲 一、《数据结构课程实验》的地位与作用 “数据结构”是计算机专业一门重要的专业技术基础课程，是计算机专业的一门核心的关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用的多种查找和排序技术，并做了性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因，使得掌握这门课程具有较大的难度： （1）内容丰富，学习量大，给学习带来困难； （2）贯穿全书的动态链表存储结构和递归技术是学习中的重点也是难点； （3）所用到的技术多，而在此之前的各门课程中所介绍的专业性知识又不多，因而加大了学习难度； （4）隐含在各部分的技术和方法丰富，也是学习的重点和难点。 根据《数据结构课程》课程本身的技术特性，设置《数据结构课程实验》实践环节十分重要。通过实验实践内容的训练，突出构造性思维训练的特征, 目的是提高学生组织数据及编写大型程序的能力。实验学时为18。 二、《数据结构课程实验》的目的和要求 不少学生在解答习题尤其是算法设计题时，觉得无从下手，做起来特别费劲。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。 为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法，如算法设计的构思方法，动态链表，算法的编码，递归技术，与特定问题相关的技术等，要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。在掌握基本算法的基础上，掌握分析、解决实际问题的能力。 三、《数据结构课程实验》内容 课程实验共18学时，要求完成以下六个题目： 实习一约瑟夫环问题（2学时） 数据结构实验报告全集 实验一线性表基本操作和简单程序 1．实验目的 （1）掌握使用Visual C++ 6.0上机调试程序的基本方法； （2）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2．实验要求 （1）认真阅读和掌握和本实验相关的教材内容。 （2）认真阅读和掌握本章相关内容的程序。 （3）上机运行程序。 （4）保存和打印出程序的运行结果，并结合程序进行分析。 （5）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include iostream.h>//头文件 #include nodetype *create()//建立单链表，由用户输入各结点data域之值，//以0表示输入结束 { elemtype d;//定义数据元素d nodetype *h=NULL,*s,*t;//定义结点指针 int i=1; cout<<"建立一个单链表"< 实验四串 【实验目的】 1、掌握串的存储表示及基本操作； 2、掌握串的两种模式匹配算法：BF和KMP。 3、了解串的应用。 【实验学时】 2学时 【实验预习】 回答以下问题： 1、串和子串的定义 串的定义：串是由零个或多个任意字符组成的有限序列。 子串的定义：串中任意连续字符组成的子序列称为该串的子串。 2、串的模式匹配 串的模式匹配即子串定位是一种重要的串运算。设s和t是给定的两个串，从主串s的第start个字符开始查找等于子串t的过程称为模式匹配，如果在S中找到等于t的子串，则称匹配成功，函数返回t在s中首次出现的存储位置（或序号）；否则，匹配失败，返回0。 【实验内容和要求】 1、按照要求完成程序exp4_1.c，实现串的相关操作。调试并运行如下测试数据给出运行结果： ?求“This is a boy”的串长； ?比较”abc 3”和“abcde“； 表示空格 ?比较”english”和“student“； ?比较”abc”和“abc“； ?截取串”white”，起始2，长度2； ?截取串”white”，起始1，长度7； ?截取串”white”，起始6，长度2； ?连接串”asddffgh”和”12344”； #include typedef struct { char data[MAXSIZE]; int length; } SqString; int strInit(SqString *s); /*初始化串*/ int strCreate(SqString *s); /*生成一个串*/ int strLength(SqString *s); /*求串的长度*/ int strCompare(SqString *s1,SqString *s2); /*两个串的比较*/ int subString(SqString *sub,SqString *s,int pos,int len); /*求子串*/ int strConcat(SqString *t,SqString *s1,SqString *s2); /*两个串的连接*/ /*初始化串*/ int strInit(SqString *s) { s->length=0; s->data[0]='\0'; return OK; }/*strInit*/ /*生成一个串*/ int strCreate(SqString *s) { printf("input string :"); gets(s->data); s->length=strlen(s->data); return OK; }/*strCreate*/ /*（1）---求串的长度*/ int strLength(SqString *s) { return s->length; }/*strLength*/ /*（2）---两个串的比较，S1>S2返回>0，s1 数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include //本程序以经亲测，在VS2008中复制即可实现。 // Stack_made_by_zrz.cpp : 定义控制台应用程序的入口点。 //括号匹配问题。利用栈来解决一个字符串之中使用的括号是否匹配的问题。 /* 在表达式中，相同类型的括号（包括：（）、[ ]、{}）是成对出现的，并且当括号在表达式中嵌套时，不允许出现交叉现象。 检验括号匹配的方法，就是对给定的字符串依次检验：若是左括号，入栈；若是右括号，出栈一个左括号判断是否与之匹配； 是其他字符，不检验。检验到字符串尾，还要检查栈是否为空。只有栈空，整个字符串才是括号匹配的。 */ #include"stdafx.h" #include 目录 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 10 char *base; char *top; int stacksize; }SqStack; 2.2主要算法设计 2.2.1算法思想 (1)文字描述 从键盘输入一个表达式； 逐个扫描表达式中的字符； 当遇到左括号时，将左括号入栈； 继续扫描，将此后遇到的第一个右括号与栈顶元素比较，若匹配，则栈顶元素出栈；否则，继续扫描； 当整个表达式扫描完以后，判断栈内是否还有元素，若有，则括号不匹配； 若栈为空，则括号配对成功； 在括号配对不成功的情况下，利用栈顶栈底元素的差值，可以对左右括号数进行比较。（2）流程图表示 用栈实现括号匹配的检验修改(2008-11-14 19:06:31) 标签：c语言编程turbo c2.0环境实现栈括号匹配it 分类：C语言编程例子数据结构C 语言版 括号匹配问题是编译程序时经常遇到的问题，用以检测语法是否有错。 本文前些天写的用栈实现括号匹配的检验的代码中，其中用了更少变量的代码二有些错误，使得结果总是match，经过修改，现将正确的代码写出，如下 #include 数据结构课程设计报告 设计题目：括号匹配 院系计算机学院 年级11 级 学生刘云飞 学号E01114295 指导教师王爱平 起止时间9-7/9-14 课程设计目的 1.熟悉并写出栈的逻辑结构表示 2.实现栈的存储表示 3.实现栈的操作 内容 括号匹配 课程设计要求 1.在实验报告中写出栈的ADT表示； 2.在实验报告中给出数据类型定义和核心算法和程序； 3.在实验报告中罗列实验过程中出现的问题和解决的方法； 4.打包上交调试后的完整程序，提交实验报告； 5.实验之前写出实验报告的大概框架，实验过程中填写完整。 6.实验时携带需要上机调试的程序； 7.实验评分：实验之前预习占20%，实验报告书写情况占50%，运行情况30%。概要设计 1．栈的ADT表示 ADT Stack{ 数据对象：D={ai|ai∈ ElemSet,i=1，2，…，n,n>=0} 数据关系：R1={ 2009级数据结构实验报告 实验名称：约瑟夫问题 学生姓名：李凯 班级：21班 班内序号：06 学号：09210609 日期：2010年11月5日 1．实验要求 1）功能描述：有n个人围城一个圆圈，给任意一个正整数m，从第一个人开始依次报数，数到m时则第m个人出列，重复进行，直到所有人均出列为止。请输出n个人的出列顺序。 2）输入描述：从源文件中读取。 输出描述：依次从显示屏上输出出列顺序。 2. 程序分析 1）存储结构的选择 单循环链表 2）链表的ADT定义 ADT List{ 数据对象：D={a i|a i∈ElemSet,i=1,2,3,…n,n≧0} 数据关系：R={< a i-1, a i>| a i-1 ,a i∈D,i=1,2,3,4….,n} 基本操作： ListInit(&L)；//构造一个空的单链表表L ListEmpty(L); //判断单链表L是否是空表，若是，则返回1，否则返回0. ListLength(L); //求单链表L的长度 GetElem（L，i）；//返回链表L中第i个数据元素的值； ListSort(LinkList [内容要求] 1、存储结构：顺序表、单链表或其他存储结构，需要画示意图，可参考书上P59 页图2-9 2.2 关键算法分析 结点类： template 括号匹配检验，是假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，即( [ ] ( ) )或[ ( [ ] )]等为正确的格式，[ ( ] )或( [ ( ))或( ( ) ] )均为不正确的格式。检验括号是否匹配的方法可用“期待的急迫程度”概念来描述。整个处理过程与栈的特点相吻合。因此此程序利用链表的头插法特点来完成。 #include "stdlib.h" #include "stdio.h" typedef struct Stack { char ch; struct Stack *next; }Stack,*StackList; char checkinput() /*检查输入数据的合理性*/ { char c; while(1) { printf("input the bracket:"); scanf("%c",&c); getchar(); if(c=='('||c==')'||c=='['||c==']') /*程序的有效性检测*/ break; else { printf("you input wrong! please input again!\n"); continue; } } return c; } int InitStack() /*创建栈的实例*/ { StackList L,s,t; char c; int i=0,n=0; L=(Stack*)malloc(sizeof(Stack));/*创建链表*/ L->next=NULL; while(1) c=checkinput(); switch(c) { case '(': case '[': s=(Stack*)malloc(sizeof(Stack)); s->ch=c; s->next=L->next; /*头插法实现“栈”的功能*/ L->next=s; i=++n; /*n用来记录压入栈里的凡是左括号的数目*/ break; case ')': case ']': if(i==0) return 0; /*i用来判断第一次输入的括号是否为右括号，是则退出程序*/ t=L->next; if(t->ch+1==c) /*检查是否为'('和')'，用他们的ACSII码值来检测*/ { L->next=t->next; /*匹配则删除栈顶元素*/ n--; printf("此项%c括号匹配！\n",t->ch); free(t); } else if(t->ch+2==c) /*检查是否为'['和']'*/ { L->next=t->next; /*匹配则删除栈顶元素*/ n--; printf("此项%c括号匹配！\n",t->ch); free(t); } else return 0; /*此语句判断输入两个括号后不匹配的结果,如'['和'）'*/ break; } if(n==0) return 1; } 宁波工程学院电信学院计算机教研室 实验报告 一、实验目的 1)熟悉串的定义和串的基本操作。 2 )掌握链串的基本运算。 3 )加深对串数据结构的理解，逐步培养解决实际问题的编程能力。 二、实验环境 装有Visual C ++ 6.0的计算机。 三、实验内容 编写一个程序，实现链串的各种基本运算，并在此基础上设计一个主程序。具体如下： 编写栈的基本操作函数 链串类型定义如下所示： typedef struct sno de{ char data; struct snode *n ext; }listri ng; (1)串赋值Assig n(s,t) 将一个字符串常量赋给串s, 即生成一个其值等于t 的串s ( 2 )串复制StrCopy(s,t) 将串t 赋给串s ( 3 )计算串长度StrLength(s) 返回串s 中字符个数 ( 4 )判断串相等StrEqual(s,t) 若两个串s 与t 相等则返回 1 ；否则返回0 。 ( 5 )串连接Concat(s,t) 返回由两个串s 和t 连接在一起形成的新串。 ( 6 )求子串SubStr(s,i,j) 返回串s中从第i(1 w i w StrLength(s))个字符开始的、由连续j 个字 符组成的子串。 ( 7)插入InsStr (s,i,t) 将串t 插入到串s 的第i(1 w i w StrLength(s)+1) 个字符中,即将t 的第一个字符作为s 的第i 个字符,并返回产生的新串( 8)串删除DelStr (s,i,j) 从串s 中删去从第i(1 w i w StrLength(s)) 个字符开始的长度为j 的 子串,并返回产生的新串。 (9)串替换RepStr (s,s1,s2) 在串s 中,将所有出现的子串s1 均替换成s2 。 (10)输出串DispStr(s) 输出串s 的所有元素值 (11 )判断串是否为空IsEmpty(s) 编写主函数 调用上述函数实现下列操作： (1) 建立串s= “ abcdefghijklmn ”,串s1= “xyz ”,串t =" hijk ” ( 2 ) 复制串t 到t1 ，并输出t1 的长度 ( 3) 在串s 的第9 个字符位置插入串s1 而产生串s2 ，并输出s2 ( 4) 删除s 第 2 个字符开始的 5 个字符而产生串s3 ，并输出s3 ( 5) 将串s 第 2 个字符开始的 3 个字符替换成串s1 而产生串s4 ，并输出s4 (6) 提取串s的第8个字符开始的4个字符而产生串S5，并输出S5 ( 7) 将串s1 和串t 连接起来而产生串s6 ，并输出s6 ( 8) 比较串s1 和s5 是否相等，输出结果 括号匹配问题就是给定任意判别式，然后检验括号的配对出现的情况。 可见输入的表达式有四种可能性：右括号配对次序不正确、右括号多于左括号、左括号多于右括号、左右括号匹配正确。可以先检测表达式中的字符，若是左括号就入栈，如果是右括号就出栈一个元素与其配对，配对成功则继续访问下一个字符，否则退出。出现非括号字符则跳过。程序流程图如下： 程序代码如下： #include 实验报告 课程数据结构实验名称实验三串 学号姓名实验日期： 串的操作 实验目的： 1. 熟悉串类型的实现方法，了解简单文字处理的设计方法； 2. 熟悉C语言的字符和把字符串处理的原理和方法； 3. 熟悉并掌握模式匹配算法。 实验原理： 顺序存储结构下的关于字符串操作的基本算法。 模式匹配算法BF、KMP 实验内容： 4-19. 在4.4.3节例4-6的基础上，编写比较Brute-Force算法和KMP算法比较次数的程序。 4-20. 设串采用静态数组存储结构，编写函数实现串的替换Replace（S，start，T，V），即要求在主串S中，从位置start开始查找是否存在字串T。若主串S中存在子串T，则用子串V替换子串T，且函数返回1；若主串S中不存在子串T，则函数返回0；并要求设计主函数进行测试。一个测试例子为：S=“I am a student”,T=“student”,V=“teacher”。程序代码： 4-19的代码： /*静态存储结构*/ typedef struct { char str[MaxSize]; int length; }String; /*初始化操作*/ void Initiate(String *S) { S->length=0; } /*插入子串操作*/ int Insert(String *S, int pos, String T) /*在串S的pos位置插入子串T*/ { int i; if(pos<0||pos>S->length) { printf("The parameter pos is error!\n"); return 0; } else if(S->length+T.length>MaxSize) 5)：利用栈编写满足下列要求的括号匹配检验程序：假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，即（[]（））或[（[][]）]等为正确的格式，[（]或（[（））或（（）]）均为不正确的格式。输入一个包含上述括号的表达式，检验括号是否配对。本题给出部分check()函数，要求将check()函数补充完整，并完成整个程序。 typedef char SElemType; #include"malloc.h" #include"stdio.h" #include"math.h" #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等 #define STACK_INIT_SIZE 10 // 存储空间初始分配量 #define STACKINCREMENT 2 // 存储空间分配增量 struct SqStack { SElemType *base; // 在栈构造之前和销毁之后，base的值为NULL SElemType *top; // 栈顶指针 int stacksize; // 当前已分配的存储空间，以元素为单位 }; // 顺序栈 Status InitStack(SqStack &S) { S.base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base) { return ERROR; } S.top = S.base; S.stacksize=STACK_INIT_SIZE; return OK; } Status StackEmpty(SqStack S) { if(S.top == S.base) return TRUE; else return FALSE; } Status Push(SqStack &S,SElemType e) { if(S.top-S.base>=S.stacksize) 衡阳师范学院 《C语言数据结构》 课 程 设 计 报 告 题目：括号匹配的检验 班级： 1 1 0 1 学号： 作者姓名： 指导教师： 2012年11月 目录 1设计题目与要求 (3) 1.1实验目的 (3) 1.2问题描述 (3) 1.3设计要求 (3) 2总体设计思想及相关知识 (3) 2.1总体设计思想 (3) 2.2开发环境与工具 (4) 3功能设计 (4) 3.1 抽象数据类型的定义 (4) 3.2 栈的基本运算 (4) 3.3栈的基本操作的实现 (4) 3.4模块流程图 (6) 4源程序代码 (6) 5测试及结果 (9) 6总结 (11) 7小组成员任务分配 (11) 参考文献 (12) 1．设计题目与要求 1.1实验目的 通过对括号匹配的检验的程序设计编写，深入了解和掌握栈的使用，了解栈先进后出的特点，掌握栈的表示和实现。 1.2问题描述 假设表达式中允许包括两种括号:圆括号和方括号，其嵌套的顺序随意，即([]())或[([][])]等为正确的格式，[(])或(()]）均为不正确的格式。检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。例如考虑下列括号序列：[ ( [ ] [ ] ) ] 1 2 3 4 5 6 7 8 当计算机接受了第一个括号后，它期待着与其匹配的第八个括号的出现，然而等来的却是第二个括号，此时第一个括号只能暂时靠边，而迫切等待与第二个括号相匹配的，第七个括号的出现，类似的，因等来的第三个括号，其期待的匹配程度较第二个括号更急迫，则第二个括号也只能靠边，让位于第三个括号，显然第二个括号的期待急迫性高于第一个括号；在接受了第四个括号后，第三个括号的期待得到满足，消解之后，第二个括号的期待匹配成了当前最急迫的任务了，······，依次类推。可见，这个处理过程恰与栈的特点相吻合。 1.3设计要求 读入圆括号和方括号的任意序列，输出“匹配”或“此串括号匹配不合法”。2．总体设计思想及相关知识 2.1总体设计思想 最内层（最迟出现）的左括号必须与最内层（最早出现）的同类右括号匹配，它最期待着急迫的配对。配对之后，期待得以消除。因此为左括号设置一个栈，置于栈顶的左括号期待配对的急切程度最高。另外，在算法的开始和结束时，栈都应该是空的。例如：[()[]]、 ([{}]) 、{([]]} 2011~2012第一学期数据结构实验报告 班级：信管一班 学号：201051018 姓名：史孟晨 实验报告题目及要求 一、实验题目 设某班级有M（6）名学生，本学期共开设N（3）门课程，要求实现并修改如下程序（算法）。 1. 输入学生的学号、姓名和 N 门课程的成绩（输入提示和输出显示使用汉字系统）， 输出实验结果。（15分） 2. 计算每个学生本学期 N 门课程的总分，输出总分和N门课程成绩排在前 3 名学 生的学号、姓名和成绩。 3. 按学生总分和 N 门课程成绩关键字升序排列名次，总分相同者同名次。 二、实验要求 1．修改算法。将奇偶排序算法升序改为降序。（15分） 2．用选择排序、冒泡排序、插入排序分别替换奇偶排序算法,并将升序算法修改为降序算法；。（45分）） 3．编译、链接以上算法，按要求写出实验报告（25）。 4. 修改后算法的所有语句必须加下划线，没做修改语句保持按原样不动。 5．用A4纸打印输出实验报告。 三、实验报告说明 实验数据可自定义，每种排序算法数据要求均不重复。 (1) 实验题目：《N门课程学生成绩名次排序算法实现》； (2) 实验目的：掌握各种排序算法的基本思想、实验方法和验证算法的准确性； (3) 实验要求：对算法进行上机编译、链接、运行； (4) 实验环境（Windows XP-sp3,Visual c++)； (5) 实验算法（给出四种排序算法修改后的全部清单）； (6) 实验结果（四种排序算法模拟运行后的实验结果）； (7) 实验体会（文字说明本实验成功或不足之处）。 三、实验源程序（算法） Score.c #include "stdio.h" #include "string.h" #define M 6 #define N 3 struct student { char name[10]; int number; int score[N+1]; /*score[N]为总分,score[0]-score[2]为学科成绩*/ }stu[M]; void changesort(struct student a[],int n,int j) {int flag=1,i; struct student temp; while(flag) { flag=0; for(i=1;i 括号匹配 实验目的： 使用堆栈的存储结构实现括号匹配，即“（”与“）”必须成对出现、“[”与“]”必须成对出现 实验思路： 1、写出堆栈的相关操作函数，如： 创建【int InitStack( SqStack *S )】、 压入【int Push(SqStack *S,int e)】、 弹出【int Pop(SqStack *S,int *e)】、 销毁【void DestroyStack(SqStack *S)】、 判断是否为空【int StackEmpty(SqStack *S)】等。 2、堆栈的各操作函数完成后编写功能函数——括号匹配函数【int match(char *str)】。 3、括号匹配函数之后编写主函数，使用上述函数实现括号匹配的功能 核心代码： 1、括号匹配函数： int match(char *str){ int i,e; SqStack S; InitStack(&S); for(i=0;;i++){ if(str[i]=='\0')break; if(str[i]=='('||str[i]=='['){ Push(&S,str[i]); }; if(str[i]==')'){ Pop(&S,&e); if(e=='('){ continue; }else{ Push(&S,e); } } if(str[i]==']'){ Pop(&S,&e); if(e=='['){ continue; }else{ Push(&S,e); } } } if(StackEmpty(&S)){ printf("恭喜您，括号匹配成功,多项式格式合法！\n"); }else{ printf("警告：多项式格式不合法！\n"); } DestroyStack(&S); return 1; } 2、主函数： int main(){ char str[100]; printf("请输入一个表达式："); scanf("%s",&str); match(str); system("pause"); return 1; } 功能演示： 1、输入：（3+45）*[32-5]/[2-5] 输出：恭喜您，括号匹配成功,多项式格式合法！ 图实验 一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template 课程名称: 《数据结构》课程设计课程设计题目: 括号匹配 姓名:*** 院系:计算机科学与技术学院 专业:计算机科学与技术 年级:** 学号:******* 指导教师:*** 2015 年 09月 10 日 目录 1 课程设计的目的 (1) 2 需求分析 (3) 3 课程设计报告内容 (3) 3.1概要设计 (3) 3.2详细设计 (3) 3.3调试分析 (5) 4 总结 (7) 5 程序清单 (8) 6 参考文献 (7) 1.课程设计的目的 (1) 熟练使用C 语言编写程序，解决实际问题; (2) 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力; (3) 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能; (4) 提高综合运用所学的理论知识和方法独立分析和解决问题的能力; 2.需求分析 本程序文件主要的功能是判断括号的匹配问题。 程序的执行是从事先输入好数据的文档中读取，然后对所读取的数据进行括号匹配行的判断。最后输出判断的结果。 程序函数主要有void InitStack(Stack *S)、ElemType GetTop(Stack S,ElemType *e)、void push(Stack *S,ElemType e)、ElemType pop(Stack *S,ElemType *e)、int Judge(ElemType a[])。InitStack函数是用来初始化栈；GetTop函数是用来获取栈顶元素；push是用来把元素压栈、pop函数是用来把元素弹出栈、Judge函数是用来判断括号是否匹配。 3 括号匹配的设计 3.1概要设计 算法分析： 首先设置好一个栈，然后从文件中读入数据，在读入的数据时，从文件中读取的字符串存入到函数定义好的字符数组中。然后把该数组作为函数参数。当每读入一个‘（’或者是‘[’，就把这个元素压栈，若是读入的元素是‘]’或者是‘）’，就调用GetTop函数，来获取栈顶元素，如果获取的栈顶元素和该次读入的元素匹配而且栈不空的话，就说明该元素是匹配的，继续比较下一次的元素；如果获取的栈顶元素和该次读入的元素不匹配的话，就说明该元素是不匹配的，直接结束运行。当所有的‘）’或者是‘]’全部比较完成之后，栈仍然不空，说明栈中还剩有‘[’或者‘(’，括号不匹配。 3.2详细设计 void InitStack(Stack *S)//建造一个栈 { S->base = (ElemType *)malloc(STACK_INIT_SIZE *sizeof(ElemType)); if(!*S->base) printf("error"); S ->top = S ->base;//将栈设置为空栈 S->stacksize = STACK_INIT_SIZE;//将栈的空间大小设置为STACK_INIT_SIZE } 建栈的操作首先将栈指针s->指向新开辟的内存空间。然后将栈顶指针s->top等于s->base。将栈置成空栈。 ElemType GetTop(Stack S,ElemType *e)//获取栈顶元素 { if(S.top!=S.base) { *e=*(S.top-1); return *e; }数据结构实验报告格式
数据结构实验报告全集
数据结构实验报告-串
数据结构实验报告
C++栈实现括号匹配
数据结构课程设计---括号匹配
用栈实现括号匹配的检验 修改
数据结构实验报告(栈_括号匹配) (1)
数据结构实验报告模板
括号匹配检验
数据结构实验报告3链串
括号匹配问题源代码(C语言)
数据结构串的操作实验报告
C语言之符号匹配
括号匹配的检查 课程设计
数据结构实验报告及心得体会
《C数据结构》括号匹配实验报告
数据结构实验报告图实验
括号匹配(数据结构实验报告)
相关主题
文本预览