群体类和群体数据

学校代码： 10128学 号： 面向对象的程序设计实验报告（题 目：群体类和群体数据学生姓名： 学 院：理学院系 别：数学系专 业：信息与计算科学班 级：任课教师： 二一一年 十 一月1、 实验目的1、 了解节点类的声明和实现，学习其使用方法2、 了解链表类的声明和实现，学习其使用方法3、 了解栈类的声明和实现，学习其使用方法4、 了解队列类的声明和实现，学习其使用方法5、 掌握对数组元素排序的方法6、 掌握对数组元素查找的方法2、 实验内容1.、编写程序Node.h实现例9-5的节点类，并编写测试程序lab9_1.cpp，实现链表的基本操作2、编写程序link.h实现例9-6的链表类，在测试程序lab_2.cpp中声明两个整型链表A和B，分别插入5元素，然后把B中的元素加入A的尾部3、编写程序queue.h，用链表实现队列（或栈），在测试程序lab9_3.cpp中声明一个整型队列（或栈）对象，插入5个整数，压入队列（或栈），再依次取出并显示出来。4、将直接插入排序、直接选择排序、冒泡排序、顺序查找函数封装到第九章的数组类中，作为成员函数，实现并测试这个类。3、 实验程序及结果1. 程序一/9_5.h#ifndef NODE_CLASS#define NODE_CLASS/类定义部分template class Node private: Node *next; /指向后继节点的指针 public: T data; /数据域 / 构造函数 Node (const T& item, Node* ptrnext = NULL); / 在本节点之后插入一个同类节点p void InsertAfter(Node *p); / 删除本节点的后继节点，并返回其地址 Node *DeleteAfter(void); / 获取后继节点的地址 Node *NextNode(void) const;/ 类的实现部分/ 构造函数，初始化数据和指针成员template Node:Node(const T& item, Node* ptrnext) : data(item), next(ptrnext)/ 返回私有的指针成员template Node *Node:NextNode(void) const return next; / 在当前节点之后插入一个节点p template void Node:InsertAfter(Node *p) p-next = next; /p节点指针域指向当前节点的后继节点 next = p; /当前节点的指针域指向p / 删除当前节点的后继节点，并返回其地址template Node *Node:DeleteAfter(void)Node *tempPtr = next; /将欲删除的节点地址存储到tempPtr中 if (next = NULL) /如果当前节点没有后继节点，则返回NULL return NULL; next = tempPtr-next; /使当前节点的指针域指向tempPtr的后继节点 return tempPtr; /返回被删除的节点的地址#endif / NODE_CLASS/Node.h#ifndef NODE_LIBRARY#define NODE_LIBRARY#include #include #include 9_5.husing namespace std;/ 生成结点：创建一个结点，数据成员值为item，指向后继结点的指针值为nextPtrtemplate Node *GetNode(const T& item, Node *nextPtr = NULL) Node *newNode; / 为新结点分配内存空间，然后将item和NextPtr传递给构造函数 newNode = new Node(item, nextPtr); if (newNode = NULL) /如果分配内存失败，程序中止 cerr Memory allocation failure! endl; exit(1); return newNode;enum AppendNewline noNewline,addNewline;/ 输出链表template void PrintList(Node *head, AppendNewline addnl = noNewline) / currPtr初始指向表头结点，用于遍历链表 Node *currPtr = head; / 输出结点数据，直到链表结束 while(currPtr != NULL) / 如果换行标志addl = addNewline，则输出换行符 if(addnl = addNewline) cout data endl; else cout data NextNode(); /查找结点/在指针head所指向的链表中查找数据域等于item的结点/找到则返回TRUE及其前趋结点的地址，否则返回FALSEtemplate int Find(Node *head, T& item, Node* &prevPtr)Node *currPtr = head; /从第一个结点开始遍历prevPtr = NULL;/ 通过循环遍历链表，直到表尾while(currPtr != NULL) /将item与结点的数据域比较，如果相等，则返回，否则继续处理下一个结点 if (currPtr-data = item) return 1; prevPtr = currPtr; /记录下当前结点的地址 currPtr = currPtr-NextNode();return 0; /找不到时/在表头插入结点template void InsertFront(Node* & head, T item) / 建立新结点，使其指针域指向原链表头结点head，然后更新head head = GetNode(item,head);/在表尾添加结点template void InsertRear(Node* & head, const T& item) Node *newNode, *currPtr = head;/ 如果链表为空，则插入在表头 if (currPtr = NULL) InsertFront(head,item); else / 寻找指针域为NULL的结点 while(currPtr-NextNode() != NULL) currPtr = currPtr-NextNode(); / 建立新结点并插入在表尾(在currPtr之后) newNode = GetNode(item); currPtr-InsertAfter(newNode); / 删除链表的第一个结点template void DeleteFront(Node* & head) Node *p = head; /取得将被删除的结点的地址 if (head != NULL) / 确认链表不空 head = head-NextNode(); / 将表头指针head移向第二个结点 delete p; /删除原第一个结点 / 删除链表中第一个数据域等于key的结点template void Delete (Node* & head, T key) / currPtr用于遍历链表，prevPtr跟随其后 Node *currPtr = head, *prevPtr = NULL; / 如果链表为空，则返回 if (currPtr = NULL) return; /通过循环遍历链表，直到找到数据域为key的结点，或达到表尾 while (currPtr != NULL & currPtr-data != key) / currPtr前行，prevPtr跟随其后 prevPtr = currPtr; currPtr = currPtr-NextNode(); /若 currPtr != NULL，则currPtr指向的结点数据域为key if (currPtr != NULL) if(prevPtr = NULL) /找到的是链表第一个结点 head = head-NextNode(); else / 如果找到的是第二个以后的结点，调用前趋结点的成员函数删除之 prevPtr-DeleteAfter(); delete currPtr; /释放被删除的结点所占的内存空间 / 在有序链表中插入一个结点template void InsertOrder(Node* & head, T item) / currPtr用于遍历链表，prevPtr跟随其后 Node *currPtr, *prevPtr, *newNode; / prevPtr = NULL 标志着应插入在表头 prevPtr = NULL; currPtr = head; / 通过循环遍历链表，寻找插入点 while (currPtr != NULL) / 如果item 当前结点数据，则插入点应在当前结点之前if (item data) break; / currPtr前行，prevPtr跟随其后 prevPtr = currPtr; currPtr = currPtr-NextNode(); / 完成插入 if (prevPtr = NULL) /如果插入点在表头 InsertFront(head,item); else / 在prevPtr指向的结点之后插入新结点 newNode = GetNode(item); prevPtr-InsertAfter(newNode); /清空链表-删除链表中的所有结点template void ClearList(Node * &head) Node *currPtr, *nextPtr; / 边遍历边删除结点 currPtr = head; while(currPtr != NULL) / 记录下一个结点的地址，删除当前结点 nextPtr = currPtr-NextNode(); delete currPtr; currPtr = nextPtr; /使指针currPtr指向下一个结点 head = NULL; /将头结点置为NULL，标志着链表为空#endif / NODE_LIBRARY/lab9_1.cpp#include #include 9_5.h#include node.husing namespace std;int main() / 将表头指针置为 NULL Node *head = NULL, *prevPtr, *delPtr; int i, key, item; / 输入10个整数依次向表头插入 for (i=0;i item; InsertFront(head, item); / 输出链表 cout List: ; PrintList(head,noNewline); cout endl; / 输入需要删除的整数 cout key; / 查找并删除结点 prevPtr = head; while (Find(head,key,prevPtr) != NULL) if(prevPtr = NULL) /找到的是链表第一个结点 head = head-NextNode(); else / 如果找到的是第二个以后的结点，调用前趋结点的成员函数删除之 delPtr=prevPtr-DeleteAfter(); delete delPtr; / 输出链表 cout List: ; PrintList(head,noNewline); cout endl;/清空链表 ClearList(head);实验结果如下：2程序二/lab9_2.cpp#include link.hint main()LinkedList A, B;for(int i=0;i5;i+)A.InsertRear(2*i+1);B.InsertRear(2*i+2);A.Reset();cout 链表A的元素为： ;while(!A.EndOfList()cout A.Data() ;A.Next();cout endl; B.Reset();cout 链表B的元素为： ;while(!B.EndOfList()cout B.Data() ;B.Next();cout endl;cout 把B中的元素插入A中. endl;B.Reset();while(!B.EndOfList()A.InsertRear(B.Data();B.Next();A.Reset();cout 此时，链表A的元素为： ;while(!A.EndOfList()cout A.Data() ;A.Next();cout endl;/link.h#ifndef LINKEDLIST_CLASS#define LINKEDLIST_CLASS#include #include using namespace std;#ifndef NULLconst int NULL = 0;#endif / NULL#include 9-3.htemplate class LinkedList private: /数据成员： / 表头和表尾指针 Node *front, *rear; / 记录表当前遍历位置的指针，由插入和删除操作更新 Node *prevPtr, *currPtr; / 表中的元素个数 int size; / 当前元素在表中的位置序号。由函数Reset使用 int position; /函数成员： / 生成新节点，数据域为item，指针域为ptrNext Node *GetNode(const T& item,Node *ptrNext=NULL); /释放节点 void FreeNode(Node *p); / 将链表L 拷贝到当前表（假设当前表为空）。 / 被拷贝构造函数、operator=调用 void CopyList(const LinkedList& L); public: / 构造函数 LinkedList(void); LinkedList(const LinkedList& L); /拷贝构造函数 / 析构函数 LinkedList(void); / 重载赋值运算符 LinkedList& operator= (const LinkedList& L); / 检查表的状态 int ListSize(void) const; /返回链表中元素个数（size） int ListEmpty(void) const; /size等于0时返回TRUE,否则返回FALSE / 遍历表的函数 void Reset(int pos = 0); /将指针currPtr移动到序号为pos的节点，prevPtr相应移动 / position记录当前节点的序号 void Next(void); /使prevPtr和currPtr移动到下一个节点 int EndOfList(void) const; / currPtr等于NULL时返回TRUE,否则返回FALSE int CurrentPosition(void) const; /返回数据成员position / 插入节点的函数：插入一个数据域为item的节点 void InsertFront(const T& item); /在表头插入 void InsertRear(const T& item); /在表尾添加 void InsertAt(const T& item); /在当前节点之前插入 void InsertAfter(const T& item); /在当前节点之后插入 / 删除节点，释放节点空间，更新prevPtr、currPtr和size T DeleteFront(void); /删除头节点 void DeleteAt(void); /删除当前节点 / 返回对当前节点成员data的引用（使数据域可以被使用或修改） T& Data(void); / 清空链表：释放所有节点的内存空间。被析构函数、operator= 调用 void ClearList(void);template Node *LinkedList:GetNode(const T& item, Node* ptrNext) Node *p; p = new Node(item,ptrNext); if (p = NULL) cout Memory allocation failure!n; exit(1); return p;template void LinkedList:FreeNode(Node *p) delete p;/将L复制到当前链表template void LinkedList:CopyList(const LinkedList& L) /P用来遍历L Node *p = L.front; int pos; /将L中的每一个元素插入到当前链表最后 while (p != NULL) InsertRear(p-data); p = p-NextNode(); /如果链表空,返回 if (position = -1) return; /在新链表中重新设置prevPtr和currPtr prevPtr = NULL; currPtr = front; for (pos = 0; pos != position; pos+) prevPtr = currPtr; currPtr = currPtr-NextNode(); /建立一个新链表,即:将有关指针设置为空,size为0,position为-1template LinkedList:LinkedList(void): front(NULL), rear(NULL), prevPtr(NULL),currPtr(NULL), size(0), position(-1)template LinkedList:LinkedList(const LinkedList& L) front = rear = NULL; prevPtr = currPtr = NULL; size = 0; position = -1; CopyList(L);template void LinkedList:ClearList(void) Node *currPosition, *nextPosition; currPosition = front; while(currPosition != NULL) /取得下一结点的地址并删除当前结点 nextPosition = currPosition-NextNode(); FreeNode(currPosition); currPosition = nextPosition; / 移动到下一结点 front = rear = NULL; prevPtr = currPtr = NULL; size = 0; position = -1;template LinkedList:LinkedList(void) ClearList();template LinkedList& LinkedList:operator= (const LinkedList& L) if (this = &L) / 不能将链表赋值给它自身 return *this; ClearList(); CopyList(L); return *this;template int LinkedList:ListSize(void) const return size;template int LinkedList:ListEmpty(void) const return size = 0;/将prevPtr和currPtr向前移动一个结点template void LinkedList:Next(void) if (currPtr != NULL) prevPtr = currPtr; currPtr = currPtr-NextNode(); position+; / 如果已经遍历完链表则返回Truetemplate int LinkedList:EndOfList(void) const return currPtr = NULL;/ 返回当前结点的位置template int LinkedList:CurrentPosition(void) const return position;/将链表当前位置设置为postemplate void LinkedList:Reset(int pos) int startPos; / 如果链表为空，返回 if (front = NULL) return; / 如果位置不合法，中止程序 if (pos size-1) cerr Reset: Invalid list position: pos NextNode(); prevPtr = front; startPos = 1; /移动指针直到 position = pos for(position=startPos; position != pos; position+) / 向前移动遍历指针 prevPtr = currPtr; currPtr = currPtr-NextNode(); /返回一个当前结点数值的引用template T& LinkedList:Data(void) / 如果链表为空或已经完成遍历则出错 if (size = 0 | currPtr = NULL) cerr Data: invalid reference! data;/ 将item插入在表头template void LinkedList:InsertFront(const T& item) / 如果链表不空则调用Reset if (front != NULL) Reset(); InsertAt(item); / 在表头插入/ 在表尾插入template void LinkedList:InsertRear(const T& item) Node *newNode; prevPtr = rear; newNode = GetNode(item);/ 创建新结点 if (rear = NULL)/ 如果表空则插入在表头 front = rear = newNode; else rear-InsertAfter(newNode); rear = newNode; currPtr = rear; position = size; size+;/ 将item插入在链表当前位置template void LinkedList:InsertAt(const T& item) Node *newNode; / 两种情况: 插入在链表头或链表之中 if (prevPtr = NULL) / 插入在链表头，包括将结点插入到空表中 newNode = GetNode(item,front); front = newNode; else / 插入到链表之中. 将结点置于prevPtr之后 newNode = GetNode(item); prevPtr-InsertAfter(newNode); / 如果prevPtr = rear, 说明正在向空表中插入， / 或者是插入到非空表的表尾；更新rear 和 position if (prevPtr = rear) rear = newNode; position = size; /更新currPtr并且使size增值 currPtr = newNode; size+; / 将item 插入到链表当前位置之后template void LinkedList:InsertAfter(const T& item) Node *p; p = GetNode(item); if (front = NULL) / 向空表中插入 front = currPtr = rear = p; position = 0; else / 插入到最后一个结点之后 if (currPtr = NULL) currPtr = prevPtr; currPtr-InsertAfter(p); if (currPtr = rear) rear = p; position = size; else position+; prevPtr = currPtr; currPtr = p; size+; / 使链表长度增值/ 删除表头结点template T LinkedList:DeleteFront(void) T item; Reset(); if (front = NULL) cerr Invalid deletion! data; DeleteAt(); return item;/ 删除链表当前位置的结点 template void LinkedList:DeleteAt(void) Node *p; / 如果表空或达到表尾则出错 if (currPtr = NULL) cerr Invalid deletion! NextNode(); else / 分离prevPtr之后的一个内部结点. 保存其地址 p = prevPtr-DeleteAfter(); / 如果表尾结点被删除, 则新的表尾是prevPtr 并且position自减； / 否则position不变 if (p = rear) rear = prevPtr; position-; / 使currPtr越过被删除的结点 currPtr = p-NextNode(); / 释放结点，并使链表长度自减 FreeNode(p); size-;#endif / LINKEDLIST_CLASS实验结果如下：程序3：/queue.h#ifndef QUEUE_CLASS#define QUEUE_CLASS#include #include using namespace std;#include link.htemplate class Queue private: / 用于存放队列的链表对象 LinkedList queueList; public: / 构造函数 Queue(void); / 队列存取方法 void QInsert(const T& elt); T QDelete(void); / 队列访问 T QFront(void); / 队列监测方法 int QLength(void) const; int QEmpty(void) const; void QClear(void);/ 构造函数template Queue:Queue(void)/ 链表类成员函数ListSize返回链表长度template int Queue:QLength(void) const return queueList.ListSize();/ 链表类成员函数ListEmpty测试队列空否template int Queue:QEmpty(void) const return queueList.ListEmpty();/ 链表类成员函数ClearList 清空队列template void Queue:QClear(void) queueList.ClearList();/ 链表类成员函数InsertRear在队尾插入一项template void Queue:QInsert(const T& elt) queueList.InsertRear(elt);/ 链表类成员函数DeleteFront从队首删除一项template T Queue:QDelete(void)/ 测试队列空否,若空则中止 if (queueList.ListEmpty() cerr Calling QDelete for an empty queue! endl; exit(1); return queueList.DeleteFront();/ 返回队首元素的数值template T Queue:QFront(void)/ 测试队列空否,若空则中止 if (queueList.ListEmpty() cerr Calling QFront for an empty queue! endl; exit(1); / 重新设置队头并返回其值 queueList.Reset(); return queueList.Data();#endif / QUEUE_CLASS/link.h#ifndef LINKEDLIST_CLASS#define LINKEDLIST_CLASS#include #include using namespace std;#ifndef NULLconst int NULL = 0;#endif / NULL#include 9-3.htemplate class LinkedList private: /数据成员： / 表头和表尾指针 Node *front, *rear; / 记录表当前遍历位置的指针，由插入和删除操作更新 Node *prevPtr, *currPtr; / 表中的元素个数 int size; / 当前元素在表中的位置序号。由函数Reset使用 int position; /函数成员： / 生成新节点，数据域为item，指针域为ptrNext Node *GetNode(const T& item,Node *ptrNext=NULL); /释放节点 void