c++实验题.doc

实验五 结构和类实验目的 学习结构的定义和使用 学习使用结构构建链表式数据结构 理解结构与指针的关系 学习类的定义、实例化的方法 学习使用构造函数和析构函数 学习类成员访问控制的运用 学习使用静态成员、内联成员函数 学习堆对象的分配、使用与释放 体会面向对象程序设计方法实验内容1. 用结构构建链表 设计一个单向链表。从标准输入读取若干整数，建立链表，每次读入的数放入链表结尾。当用户输入 0时，结束链表的建立工作。然后从前往后依次输出链表节点中的内容。每个节点包含两个值，一个是真正存放的整数值，另一个为指向链表中下一个节点的指针。链表中最后一个节点不指向任何节点，所以指针为空（NULL）。表头指针和表尾指针分别指向链表的头节点和尾节点。测试数据程序输出：Please input integers to build the link(0 TO END):用户输入：3 4 5 6 7 8 9 0程序输出：Link elements:3 4 5 6 7 8 9实现要求1. 用链表存放输入的整数。链表节点空间动态申请。链表节点结构和链表数据类型的参考定义为： /定义链表节点类型typedef struct nodeint elem;struct node *next; Node;/定义链表类型typedef Node * Link;2. 在链表建立结束后，输出链表节点内容的同时释放节点空间。 3. 处理申请不到空间的情况。 实现提示1. 因为每次插入节点是在链表尾，而输出链表是从链表头，所以可以用两个指针记录链表。一个为头指针，一个为尾指针。 2. 第一次插入节点时需要考虑链表为空的情况。 3. 建立一个新节点的过程为： / 建立一个新的节点 Node * pNode = new Node; if (pNode = NULL) cout elem = k;pNode-next = NULL;4. 顺序遍历链表的过程为： Node *pNode = head; while (pNode != NULL) 访问pNode所指节点的内容；pNode = pNode-Next;5. 将新节点加到链表中的过程为： if (head = NULL)head = tail = pNode;else tail-next = pNode;tail = pNode;1. pNode-elem = k;pNode-next = NULL;2. 顺序遍历链表的过程为： Node *pNode = head;while (pNode != NULL) 访问pNode所指节点的内容；pNode = pNode-Next;3. 将新节点加到链表中的过程为： if (head = NULL)head = tail = pNode;else tail-next = pNode;tail = pNode;思考问题1. 如果是双向链表，程序要做那些改动？ 2. 队列类 设计一个队列类，模拟实际生活的队列，队列中的元素服从先进先出的规则。每次有新的元素入列时，就放在队列尾。元素出列时，从队列头出。开始时队列为空。队列的示意图为：实现要求1. 利用上一实验设计的链表结构存放队列类中的队列元素。也即队列元素的空间是动态申请的。 2. 在构造队列对象时，初始化该链表，在析构队列对象时，释放链表所占的空间。 3. 队列类用单独的文件”queue.cpp”实现，队列类的定义放在一个头文件”queue.h”中，主文件名为main.cpp。 4. 队列类中的元素为整数，并提供以下服务： void put (int newVal); /在队尾加入一个新元素int get ( ); /取出队头元素，并释放节点空间int getCount()； /取队列中元素的个数bool empty() ； /判断队列是否为空bool是Visual C+定义的数据类型，它其实是一种整数类型。具有bool类型的变量只有两种值：true或false。一个条件表达式返回的值就是bool类型的。如表达式i!=0在i的值为0时返回false，在不为0时返回true。要求将函数empty()和getCount()定义为内联函数，另外两个定义为非内联函数。数据成员全定义为私有成员或保护成员。5. 使用队列类的主程序为： #include #include queue.hint main() Queue q;int i;/输出队列是否为空cout Queue empty:;if (q.empty()cout Yes endl;elsecout No endl;/往队列中依次放入四个数cout endl 4 elements enter queue endl;for(i = 0; i 4; i+)q.put(i);/输出队列是否为空cout Queue empty:;if (q.empty()cout Yes endl;elsecout No endl;/取出两个数cout endl 2 elements leave queue:;cout q.get() ;cout q.get() ;/再放入两个数cout endl 2 elements enter queue endl;q.put(4);q.put(5);/按顺序输出剩下的队列成员cout Elements left: ; int num = q.getCount();for(i = 0; i num; i+)cout q.get() ;cout endl;return 0;实现提示1. 队列中使用的链表定义为： /定义链表节点类型 typedef struct nodeint data;struct node *next; QueueDataNode;/定义链表类型typedef QueueDataNode * QueueData;队列类的私有数据成员定义如下：int count; /队列元素个数QueueData dataLinkHead, dataLinkTail;/队头、队尾指针2. 在队列中插入一个元素的程序如下： void Queue:put (int newData) /建立一个新的结点QueueDataNode *pNew = new QueueDataNode; if (pNew = NULL) /判断是否申请到空间cout data = newData; /为新节点填充内容pNew-next = NULL;/将新节点插入到链表中if (dataLinkTail = NULL) /队列为空, 新结点成为第一个结点dataLinkHead = dataLinkTail = pNew;else /队列不空dataLinkTail-next = pNew; dataLinkTail = pNew;count+;1. 静态成员 修改上一个实验得到的队列类，为其增加一个静态数据成员，可以记录程序中产生的队列个数。实现要求1. 提供静态成员函数getQueueNumber()，可以返回队列的个数，函数原型为： int getQueueNumber(void);2. 每当构建一个新的队列对象时，队列计数自动增1，而队列对象消亡时，队列计数自动减1 3.下面是测试你设计的类的主程序： #include #include queue.hvoid main() Queue q1,q2,q3;Queue *q4,*q5;cout Total Queues: Queue:getQueueNumber() endl;q4 = new Queue;q5 = new Queue;cout Total Queues: Queu