实验二 栈队列、数组及其应用（1.5~2次上机）.doc

《实验二 栈队列、数组及其应用（1.5~2次上机）.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验二栈、队列、数组及其应用（1.5~2次上机）【实验目的】深入理解栈和队列的特性，领会它们各自的应用背景。熟练掌握它们在不同存储结构、不同的约定中，其基本操作的实现方法与差异。体会以下几点（注意你所做的约定）：1、栈：顺序栈（栈空/栈满条件，入栈/出栈）、链栈（栈空条件，入栈/出栈）、栈与递归的关系、回溯的思想；2、队列：链队列（队空条件，入队/出队）、顺序队列/循环顺序队列（队空/队满条件，入队/出队）；掌握稀疏矩阵的压缩存储，主要是三元组表示法。【实验内容】本次实验共四个题目，可任选其中的一题或多题，其中第一题有两小题。1.简单题1

2、)假设一个算术表达式中可以包括三种括号，分别是花括号{，}，小括号(，)，中括号[，]，这三种括号可以任意的次序嵌套，使用，如(…[…{…}…[..]…]…[…]…(…)…)。编写程序判断输入的算术表达式是否配对。要求：算术表达式从标准输入中读入，输出括号是否配对，各种配对括号的数目，最大的括号嵌套层数。2)假设称正读反读都相同的字符序列为回文。例如，’abba’，’abcba’都是回文，’ababab’不是回文，试编写程序判别从标准输入读入的以’@’为结束符的字符序列是否是回文。2．N-皇后问题假设有一N×N的棋盘和N个皇后，请为这N个

3、皇后进行布局使得这N个皇后互不攻击(即任意两个皇后不在同一行、同一列、同一对角线上。要求：输入N，输出N个皇后互不攻击的布局3．背包问题假设有一个能装入总体积为T的背包和n件体积分别为w1,w2,…,wn的物品，能否从n件物品中挑选若干件恰好装满背包，即使w1+w2+…+wn=T，要求找出所有满足上述条件的解。例如：当T=10，各件物品的体积{1，8，4，3，5，2}时，可找到下列4组解：（1，4，3，2）（1，4，5）（8，2）（3，5，2）。提示：可利用回溯法的设计思想来解决背包问题。首先将物品排成一列，然后顺序选取物品装入背包，假设

4、已选取了前i件物品之后背包还没有装满，则继续选取第i+1件物品，若该件物品“太大”不能装入，则弃之而继续选取下一件，直至背包装满为止。但如果在剩余的物品中找不到合适的物品以填满背包，则说明“刚刚”装入背包的那件物品“不合适”，应将它取出“弃之一边”，继续再从“它之后”的物品中选取，如此重复，直至求得满足条件的解，或者无解。4．稀疏矩阵运算器见《数据结构题集》P136的实习4.1。基本要求：带行逻辑链接信息的三元组顺序表表示稀疏矩阵，实现矩阵的相加、相减、相乘。选作：1)以十字链表示稀疏矩阵；2)扩充其他矩阵运算【实验要求】1.时间要求第3

5、次上机为截止时间。2.撰写实验报告。【检查期限】1．上机内容检查时间：第2、3、4次上机时间；2．报告上交截止时间：第12周的星期五13:30前