《数据结构》实验指导/实验三:栈的存储及操作 《数据结构》实验指导 实验三:栈的存储及操作 、实验目的 1、掌握栈抽象数据类型的定义 2、掌握栈的存储实现 3、掌握栈的操作算法实现 4、了解栈的应用 实验学时 2学时 、实验类型 验证性实验 四、实验需求 1、硬件 每位学生配备计算机一台 2、软件 Windows XP/ Windows7操作系统;开发工具软件: Microsoft visual studio2010。 五、实验理论与预备知识 1、数据结构的基本概念 2、存储结构的特点 3、栈的特点和基本运算 4、栈在不同存储结构下的操作算法 六、实验任务 1、循环顺序栈抽象数据类型的代码实现 2、链栈抽象数据类型的代码实现 3、编写应用程序,用相关数据验证运算算法 管理科学与工程学科/共6页第1页
《数据结构》实验指导 / 实验三：栈的存储及操作 1 管理科学与工程学科 / 共6页,第1页 《数据结构》实验指导 实验三：栈的存储及操作 一、实验目的 1、 掌握栈抽象数据类型的定义。 2、 掌握栈的存储实现。 3、 掌握栈的操作算法实现。 4、 了解栈的应用。 二、实验学时 2 学时 三、实验类型 验证性实验 四、实验需求 1、硬件 每位学生配备计算机一台； 2、软件 Windows XP/ Windows 7 操作系统；开发工具软件：Microsoft Visual Studio 2010。 五、实验理论与预备知识 1、数据结构的基本概念 2、存储结构的特点 3、栈的特点和基本运算 4、栈在不同存储结构下的操作算法 六、实验任务 1、循环顺序栈抽象数据类型的代码实现 2、链栈抽象数据类型的代码实现 3、编写应用程序，用相关数据验证运算算法
《数据结构》实验指导/实验三:栈的存储及操作 2 七、实验内容及步骤 1、任务一:有n个元素(假设元素值为1~n),依1~m的次序通过一个栈,设计一个算法判 断序列str是否得为一个出栈序列,若是出栈序列,给出操作过程 实验步骤 (1)启动 isual Studio2010,创建窗体应用程序。 (2)增加顺序栈类,代码参考如下: class Sqstack class const int Max Size =100 public string data ∥放栈中元素 public int top ∥栈顶指针 public SqstackClasso ∥构造函数 data=new string MaxSize ∥-顺序栈的基本运算算法-- public bool Stack Empty ∥判断栈是否为空 return(top==-1) public bool Push( string x)进栈算法 return false data[ top =x public bool Pop( ref string e)∥出栈算法 if (Stack Empty) ∥栈为空的情况,即栈下溢出 e=datal top ∥取栈顶指针元素的元素 ∥栈顶指针减1 return true public bool Get Top(ref string e)//取栈顶元素算法 if(StackEmptyO) ∥栈为空的情况,即栈下溢出 return false e=data topl ∥取栈顶指针位置的元素 管理科学与工程学科/共6页第2页
《数据结构》实验指导 / 实验三：栈的存储及操作 2 管理科学与工程学科 / 共6页,第2页 七、实验内容及步骤 1、任务一：有 n 个元素（假设元素值为 1～n），依 1～n 的次序通过一个栈，设计一个算法判 断序列 str 是否得为一个出栈序列，若是出栈序列，给出操作过程。 实验步骤： （1） 启动 Visual Studio 2010，创建窗体应用程序。 （2） 增加顺序栈类，代码参考如下： class SqStackClass { const int MaxSize = 100; public string[] data; //存放栈中元素 public int top; //栈顶指针 public SqStackClass() //构造函数 { data = new string[MaxSize]; top = -1; } //------ 顺序栈的基本运算算法------------------------- public bool StackEmpty() //判断栈是否为空 { return(top==-1); } public bool Push(string x) //进栈算法 { if (top == MaxSize-1) return false; top++; data[top] = x; return true; } public bool Pop(ref string e) //出栈算法 { if (StackEmpty()) //栈为空的情况，即栈下溢出 return false; e = data[top]; //取栈顶指针元素的元素 top--; //栈顶指针减 1 return true; } public bool GetTop(ref string e) / /取栈顶元素算法 { if (StackEmpty()) //栈为空的情况，即栈下溢出 return false; e = data[top]; //取栈顶指针位置的元素
《数据结构》实验指导/实验三:栈的存储及操作 3 public string DispStacko ∥将栈中元素构成一个字符串返回 Int if(StackEmptyO) mystr="空栈"; else for(i=0 lystr+=datal] return mysti (3)设计窗体,界面参考如下: 例3.3 判断一个序列是否为出栈序列 元素个数n:4 n≤9 序列:1342 判断 列 判断结果:输入序列是一个出栈序 操作过程:元素1进栈 素2 元素3进栈 元素3出栈 元素4进栈 元素4出钱 元素2 操作提示区 (4)编写窗体中按钮等控件的代码,调用循环顺序栈类,参考如下: const int Max Size=10: private void Form4 Load (object sender, EventArgs e) 管理科学与工程学科/共6页第3页
《数据结构》实验指导 / 实验三：栈的存储及操作 3 管理科学与工程学科 / 共6页,第3页 return true; } public string DispStack() //将栈中元素构成一个字符串返回 { int i; string mystr = ""; if (StackEmpty()) mystr = "空栈"; else { for (i = 0; i < top; i++) mystr += data[i] + ","; mystr += data[top]; } return mystr; } } （3） 设计窗体，界面参考如下： （4） 编写窗体中按钮等控件的代码，调用循环顺序栈类，参考如下： const int MaxSize=10; private void Form4_Load(object sender, EventArgs e)
《数据结构》实验指导/实验三:栈的存储及操作 4 text Boxl Text=5 ∥置初值 text Box2 Text="12345 private void button1_ Click(object sender, EventArgs e) string str, mystr"; int[la= new int MaxSize;∥存放输入序列 int|b= new int[ MaxSizel;∥存放输出序列 t n= Convert.Tolnt32(text BoxlText) catch(Exception err) infolabel. text=操作提示输入的元素个数不正确请重新输入”; retur str= text Box2 Text TrimO; if (str Length<n) infolabel. Text:="操作提示输入的序列不正确请重新输入"; retur r(i=0;i<n;i++) a[i=i+ 1; ∥a数组元素置为1n bli=stri-0’;/将判断序列转换成各位数字存放在b数组中 if (isSerial(a, b, n, ref mystr)) textBox3Text="输入序列是一个出栈序列; textBox. Text=mystr else textbox3.Tet="输入序列不是一个出栈序列"; textBox.Text="; private bool is Serial(intl a, intl b, int n, ref string mystr) int i=0,j=0; int I st= new int[ MaxSizel;∥用作顺序栈 用作栈顶指针 管理科学与工程学科/共6页第4页
《数据结构》实验指导 / 实验三：栈的存储及操作 4 管理科学与工程学科 / 共6页,第4页 { textBox1.Text = "5"; //置初值 textBox2.Text = "12345"; } private void button1_Click(object sender, EventArgs e) { int n,i; string str,mystr=""; int[] a = new int[MaxSize]; //存放输入序列 int[] b = new int[MaxSize]; //存放输出序列 try { n = Convert.ToInt32(textBox1.Text); } catch (Exception err) { infolabel.Text = "操作提示:输入的元素个数不正确,请重新输入"; return; } str = textBox2.Text.Trim(); if (str.Length<n) { infolabel.Text = "操作提示:输入的序列不正确,请重新输入"; return; } for (i = 0; i < n; i++) { a[i] = i + 1; //a 数组元素置为 1-n b[i] = str[i]-'0'; //将判断序列转换成各位数字存放在 b 数组中 } if (isSerial(a, b, n, ref mystr)) { textBox3.Text = "输入序列是一个出栈序列"; textBox4.Text = mystr; } else { textBox3.Text = "输入序列不是一个出栈序列"; textBox4.Text = ""; } } private bool isSerial(int[] a, int[] b, int n,ref string mystr) { int i = 0, j = 0; int [] st = new int[MaxSize]; //用作顺序栈 int top=-1; //用作栈顶指针
《数据结构》实验指导/实验三:栈的存储及操作 5 while(i<n &&j<n if (top==-1 st topl!=blin sttop=a mystr+=元素"+ ai.ToString(+"进栈rn"; se mystr+=元素”+ st top ToString0+"出栈rn"; while(top!=-1 & stltop bljD mystr+="元素"+ st topl, ToString0+"出栈rn"; j++; ifj== n) return true else return falses (5)选择【调试】一·【开始执行(不调试)】命令或按【Crl+F5】组合键运行程序,并观 察运行情况 八、实验分析 1、分析程序的运行过程,并将核心代码、错误提示及纠错内容记录至实验报告册 2、栈的存储和运算的代码实现 3、数据结构的应用特点。 九、课外自主实验 1、设计一个算法利用栈的基本运算将链栈中所有元素逆置。参考界面如下 管理科学与工程学科/共6页第5页
《数据结构》实验指导 / 实验三：栈的存储及操作 5 管理科学与工程学科 / 共6页,第5页 while (i < n && j < n) { if (top == -1 || st[top] != b[j]) { top++; st[top] = a[i]; mystr += "元素" + a[i].ToString() + "进栈\r\n"; i++; } else { mystr += "元素" + st[top].ToString() + "出栈\r\n"; top--; j++; } } while (top!=-1 && st[top] == b[j]) { mystr += "元素" + st[top].ToString() + "出栈\r\n"; top--; j++; } if (j == n) return true; else return false; } } （5） 选择【调试】 【开始执行（不调试）】命令或按【Ctrl+F5】组合键运行程序，并观 察运行情况。 八、实验分析 1、 分析程序的运行过程，并将核心代码、错误提示及纠错内容记录至实验报告册； 2、 栈的存储和运算的代码实现； 3、 数据结构的应用特点。 九、课外自主实验 1、设计一个算法利用栈的基本运算将链栈中所有元素逆置。参考界面如下：
《数据结构》实验指导/实验三:栈的存储及操作 6 例3.4 建立链栈 栈底 dc ba 进栈元素d 链栈逆置操作 栈顶 栈底 a.b.c.d 操作提示:栊中元素成功逆置 管理科学与工程学科/共6页第6页
《数据结构》实验指导 / 实验三：栈的存储及操作 6 管理科学与工程学科 / 共6页,第6页