《数据结构》实验指导/实验四:队列的存储及操作1 《数据结构》实验指导 实验四:队列的存储及操作 、实验目的 1、掌握队列抽象数据类型的定义 2、掌握队列的存储实现。 3、掌握队列的操作算法实现。 4、了解队列的应用。 二、实验学时 、实验类型 验证性实验 四、实验需求 1、硬件 每位学生配备计算机一台: 2、软件 Windows XP/ Windows7操作系统:开发工具软件: Microsoft visual studio2010。 五、实验理论与预备知识 1、数据结构的基本概念 2、存储结构的特点 3、队列的特点和基本运算 4、队列在不同存储结构下的操作算法 六、实验任务 1、循环顺序队列抽象数据类型的代码实现 2、链队列抽象数据类型的代码实现 3、编写应用程序,用相关数据验证运算算法 管理科学与工程学科/共7页第1页
《数据结构》实验指导 / 实验四：队列的存储及操作 1 管理科学与工程学科 / 共7页,第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、仼务一:代码实现循环顺序队列抽象数据类型:编写应用程序,用相关数据验证运算算法。 实验步骤: (1)启动 sual studio2010,创建窗体应用程序。 (2)增加循环顺序队列类,代码参考如下: class SqQueue class const int Max Size=100; ∥最多元素个数 public stringll data;∥存放队中元素 public int front, rear: /队头和队尾指针 public sq Queue Class ∥构造函数用于初始化队列 i data=new string MaxSize; front=rear=0;通常情况下,循环队列x为0 ∥顺序队基本运算算法 public bool QueueEmptyo return(front-rear); public bool en Queue(string e) ir(rear+1)% Maxsize== front)∥队满上溢出 return false; ∥返回 false rear(rear+1)% MaxSize: datarearl=e: return true: public bool de Queue(ref string e) if(front=rear) /队空下溢出 return false: 返回 false front=(front+1)% Max Size; 管理科学与工程学科/共7页第2页
《数据结构》实验指导 / 实验四：队列的存储及操作 2 管理科学与工程学科 / 共7页,第2页 七、实验内容及步骤 1、任务一：代码实现循环顺序队列抽象数据类型；编写应用程序，用相关数据验证运算算法。 实验步骤： （1） 启动 Visual Studio 2010，创建窗体应用程序。 （2） 增加循环顺序队列类，代码参考如下： class SqQueueClass { const int MaxSize=100; //最多元素个数 public string[] data; //存放队中元素 public int front,rear; //队头和队尾指针 public SqQueueClass() //构造函数,用于初始化队列 { data=new string[MaxSize]; front=rear=0; //通常情况下，循环队列 x 为 0 } //顺序队基本运算算法 public bool QueueEmpty() { return (front==rear); } public bool enQueue(string e) { if ((rear+1)%MaxSize==front) //队满上溢出 return false; //返回 false rear=(rear+1) % MaxSize; data[rear]=e; return true; } public bool deQueue(ref string e) { if (front==rear) //队空下溢出 return false; //返回 false front=(front + 1) % MaxSize;
《数据结构》实验指导/实验四:队列的存储及操作 3 e=data front; return true (3)设计窗体,界面参考如下 例3.6 一个循环队列 下标位置0-4 a,bcde 队首 队尾 进队操作 进队元素e 进队 出队揉作 出队出队元素 求队列中元素个数 队中元素个数元素个数:5 操作提示:成功求出队中元素个数 (4)编写窗体中按钮等控件的代码,调用循环顺序队列类,参考如下 SqQueue Class L=new Sq Queue Class(; private void button Click(object sender, EventArgs e) L en Queue(text BoxlText) private void button2 Click(object sender, eventargs e) 管理科学与工程学科/共7页第3页
《数据结构》实验指导 / 实验四：队列的存储及操作 3 管理科学与工程学科 / 共7页,第3页 e=data[front]; return true; } } （3） 设计窗体，界面参考如下： （4） 编写窗体中按钮等控件的代码，调用循环顺序队列类，参考如下： SqQueueClass L = new SqQueueClass(); private void button1_Click(object sender, EventArgs e) { L.enQueue(textBox1.Text); } private void button2_Click(object sender, EventArgs e)
《数据结构》实验指导/实验四:队列的存储及操作 L de queue(ref s text Box2 Text=s: (5)选择【调试】一【开始执行(不调试)】命令或按【crl+F5】组合键运行程序,并观 察运行情况。 (6)在循环顺序队列类中增加如下两个方法,编写方法代码: 求队列中数据元素个数: public int GetCount0 输出队列中所有元素的值: public string DispQueueO (7)在窗体中增加相应控件和代码,调用步骤(6)中的两个方法,调试运行并观察运行结 果 、仼务二:代码实现链队列抽象数据类型;编写应用程序,用相关数据验证运算算法。 实验步骤: (1)启动 isual Studio2010,创建窗体应用程序 (2)增加链队列类,代码参考如下: class Lin nOd ∥链队数据结点类 public string data ∥结点数据字段 public LinkNode next;∥指向下一个结点 }; class LinkQueue ∥链队结点类 public LinkNode front 指向队头结点 public LinkNode re ∥指向队尾结点 class LinkQueue Class 管理科学与工程学科/共7页第4页
《数据结构》实验指导 / 实验四：队列的存储及操作 4 管理科学与工程学科 / 共7页,第4页 { string s = ""; L.deQueue(ref s); textBox2.Text = s; } （5） 选择【调试】 【开始执行（不调试）】命令或按【Ctrl+F5】组合键运行程序，并观 察运行情况。 （6） 在循环顺序队列类中增加如下两个方法，编写方法代码： 求队列中数据元素个数：public int GetCount()； 输出队列中所有元素的值：public string DispQueue()； （7）在窗体中增加相应控件和代码，调用步骤（6）中的两个方法，调试运行并观察运行结 果。 2、任务二：代码实现链队列抽象数据类型；编写应用程序，用相关数据验证运算算法。 实验步骤： （1） 启动 Visual Studio 2010，创建窗体应用程序。 （2） 增加链队列类，代码参考如下： class LinkNode //链队数据结点类 { public string data; //结点数据字段 public LinkNode next; //指向下一个结点 }; class LinkQueue //链队结点类 { public LinkNode front; //指向队头结点 public LinkNode rear; //指向队尾结点 }; class LinkQueueClass {
《数据结构》实验指导/实验四:队列的存储及操作 5 Link Queue C= new Link Queue(;∥链队结点 public LinkQueue Class0构造函数,用于链队初始化 Ofront= null Q rear= null ∥链队基本运算算法 public bool QueueEmptyO return(Q rear== null) public void en Queue(string e LinkNode p= new LinkNodeo p data=e p next= null; if(Q.rear=nul)∥若链队为空,则新结点是队首结点又是队尾结点 Q front=Q rear= p; else Q rear.next=p;/将p结点链到队尾并将rear指向它 Q rear= p public bool de Queue(ref string e) LinkNode p: if (Q rear== null) 队列为空 return false; p=Q front /p指向第一个数据结点 管理科学与工程学科/共7页第5页
《数据结构》实验指导 / 实验四：队列的存储及操作 5 管理科学与工程学科 / 共7页,第5页 LinkQueue Q = new LinkQueue(); //链队结点 public LinkQueueClass() //构造函数，用于链队初始化 { Q.front = null; Q.rear = null; } //链队基本运算算法 public bool QueueEmpty() { return (Q.rear == null); } public void enQueue(string e) { LinkNode p = new LinkNode(); p.data = e; p.next = null; if (Q.rear == null) //若链队为空,则新结点是队首结点又是队尾结点 Q.front = Q.rear = p; else { Q.rear.next = p; //将 p 结点链到队尾,并将 rear 指向它 Q.rear = p; } } public bool deQueue(ref string e) { LinkNode p; if (Q.rear == null) //队列为空 return false; p = Q.front; //p 指向第一个数据结点
《数据结构》实验指导/实验四:队列的存储及操作 6 if(Q. front= Qrear)/队列中只有一个结点时 Q front=Q rear=null; else 队列中有多个结点时 Q front=Q front. next; p dat p=null return true: (3)设计窗体,界面参考任务 (4)编写窗体中按钮等控件的代码,调用链队列类,参考如下 LinkQueue Class L= new Link Queue Class(; private void button1 Click(object sender, EventArgs e) L en Queue(textBoxl. Text); private void button2 Click(object sender, eventArgs e) strings=; L de queue(ref s) text Box2Text=s (5)选择【调试】—·【开始执行(不调试)】命令或按【ctrH+F5】组合键运行程序,并观 察运行情况 (6)在链队列类中增加如下两个方法,编写方法代码 求队列中数据元素个数: public int Get Count( 输出队列中所有元素的值: public string DispQueueo (7)在窗体中增加相应控件和代码,调用步骤(6)中的两个方法,调试运行并观察运行结 管理科学与工程学科/共7页第6页
《数据结构》实验指导 / 实验四：队列的存储及操作 6 管理科学与工程学科 / 共7页,第6页 if (Q.front == Q.rear) //队列中只有一个结点时 Q.front = Q.rear = null; else //队列中有多个结点时 Q.front = Q.front.next; e = p.data; p = null; return true; } } （3） 设计窗体，界面参考任务一： （4） 编写窗体中按钮等控件的代码，调用链队列类，参考如下： LinkQueueClass L = new LinkQueueClass(); private void button1_Click(object sender, EventArgs e) { L.enQueue(textBox1.Text); } private void button2_Click(object sender, EventArgs e) { string s = ""; L.deQueue(ref s); textBox2.Text = s; } （5） 选择【调试】 【开始执行（不调试）】命令或按【Ctrl+F5】组合键运行程序，并观 察运行情况。 （6） 在链队列类中增加如下两个方法，编写方法代码： 求队列中数据元素个数：public int GetCount()； 输出队列中所有元素的值：public string DispQueue()； （7）在窗体中增加相应控件和代码，调用步骤（6）中的两个方法，调试运行并观察运行结 果
《数据结构》实验指导/实验四:队列的存储及操作 7 八、实验分析 1、分析程序的运行过程,并将核心代码、错误提示及纠错内容记录至实验报告册: 2、队列的存储和运算的代码实现 3、数据结构的应用特点 九、课外自主实验 1、对于循环队列来说,如果知道队头指针和队列中元素个数,则可以计算出队尾指针。 也就是说,可以用队列中元素个数代替队尾指针。设计岀这种循环队列的进队、出队、判队空 和求队中元素个数的算法。 2、采用一个不带头结点只有一个尾结点指针rear的循环单链表存储队列,设计出这种 链队的进队、出队、判队空和求队中元素个数的算法。 3、设计一个循环顺序队列,用 front和rear分别作为队头和队尾指针,另外用一个标 志tag标识队列可能空(0)或可能满(1),加上 front=rear可以作为队空或队满的条件, 要求设计队列的相关基本运算算法。 管理科学与工程学科/共7页第7页
《数据结构》实验指导 / 实验四：队列的存储及操作 7 管理科学与工程学科 / 共7页,第7页 八、实验分析 1、 分析程序的运行过程，并将核心代码、错误提示及纠错内容记录至实验报告册； 2、 队列的存储和运算的代码实现； 3、 数据结构的应用特点。 九、课外自主实验 1、对于循环队列来说，如果知道队头指针和队列中元素个数，则可以计算出队尾指针。 也就是说，可以用队列中元素个数代替队尾指针。设计出这种循环队列的进队、出队、判队空 和求队中元素个数的算法。 2、采用一个不带头结点只有一个尾结点指针 rear 的循环单链表存储队列，设计出这种 链队的进队、出队、判队空和求队中元素个数的算法。 3、设计一个循环顺序队列，用 front 和 rear 分别作为队头和队尾指针，另外用一个标 志 tag 标识队列可能空（0）或可能满（1），加上 front==rear 可以作为队空或队满的条件。 要求设计队列的相关基本运算算法