实验4-群体类和群体数据---吕恩在(共15页).doc

精选优质文档-倾情为你奉上学校代码： 学 号： 面向对象程序设计实验报告（题 目：群体类和群体数据学生姓名：学 院：系 别：专 业：班 级：任课教师： 二一五年十二月群体类和群体数据一、 实验目的1. 了解节点类的声明和实现，学习其使用方法2. 了解链表类的声明和实现，学习其使用方法3. 了解栈类的声明和实现，学习其使用方法4. 了解队列类的声明和实现，学习其使用方法5. 掌握对数组元素排序的方法6. 掌握对数组元素查找的方法二、实验任务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.（选做）声明course（课程）类，有属性：课程名char name21、成绩short score；在实验七的student类中增加属性；所修课程course，为课程类对象的链表。在测试程序中测试这个类，学生类与课程类关系如图5. 将直接插入排序、直接选择排序、冒泡排序、顺序查找函数封装到第九章的数组类中，作为成员函数，实现并测试这个类三、实验内容：1. /9-5.h#ifndef NODE_CLASS#define NODE_CLASStemplate <class T>class Node private: Node<T> *next; /指向后继节点的指针 public: T data; /数据域 Node (const T& item, Node<T>* ptrnext = NULL); void InsertAfter(Node<T> *p); Node<T> *DeleteAfter(void); Node<T> *NextNode(void) const;template <class T>Node<T>:Node(const T& item, Node<T>* ptrnext) : data(item), next(ptrnext) template <class T>Node<T> *Node<T>:NextNode(void) const return next;template <class T>void Node<T>:InsertAfter(Node<T> *p) p->next = next; /p节点指针域指向当前节点的后继节点 next = p; /当前节点的指针域指向ptemplate <class T>Node<T> *Node<T>:DeleteAfter(void)Node<T> *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 <iostream>#include <cstdlib>#include "9_5.h"using namespace std;template <class T>Node<T> *GetNode(const T& item, Node<T> *nextPtr = NULL) Node<T> *newNode; newNode = new Node<T>(item, nextPtr); if (newNode = NULL) /如果分配内存失败，程序中止 cerr << "Memory allocation failure!" << endl; exit(1); return newNode;enum AppendNewline noNewline,addNewline;template <class T>void PrintList(Node<T> *head, AppendNewline addnl = noNewline) Node<T> *currPtr = head; while(currPtr != NULL) if(addnl = addNewline) cout << currPtr->data << endl; else cout << currPtr->data << " " currPtr = currPtr->NextNode(); template <class T>int Find(Node<T> *head, T& item, Node<T>* &prevPtr) Node<T> *currPtr = head; /从第一个结点开始遍历 prevPtr = NULL; while(currPtr != NULL) if (currPtr->data = item) return 1; prevPtr = currPtr; /记录下当前结点的地址 currPtr = currPtr->NextNode(); return 0; /找不到时template <class T>void InsertFront(Node<T>* & head, T item) head = GetNode(item,head);template <class T>void InsertRear(Node<T>* & head, const T& item) Node<T> *newNode, *currPtr = head; if (currPtr = NULL) InsertFront(head,item); else while(currPtr->NextNode() != NULL) currPtr = currPtr->NextNode(); newNode = GetNode(item); currPtr->InsertAfter(newNode); template <class T>void DeleteFront(Node<T>* & head) Node<T> *p = head; /取得将被删除的结点的地址 if (head != NULL) / 确认链表不空 head = head->NextNode(); / 将表头指针head移向第二个结点 delete p; /删除原第一个结点 template <class T>void Delete (Node<T>* & head, T key) Node<T> *currPtr = head, *prevPtr = NULL; if (currPtr = NULL) return; while (currPtr != NULL && currPtr->data != key) / currPtr前行，prevPtr跟随其后 prevPtr = currPtr; currPtr = currPtr->NextNode(); if (currPtr != NULL) if(prevPtr = NULL) /找到的是链表第一个结点 head = head->NextNode(); else prevPtr->DeleteAfter(); delete currPtr; /释放被删除的结点所占的内存空间 template <class T>void InsertOrder(Node<T>* & head, T item) Node<T> *currPtr, *prevPtr, *newNode; prevPtr = NULL; currPtr = head; while (currPtr != NULL) if (item < currPtr->data) break; / currPtr前行，prevPtr跟随其后 prevPtr = currPtr; currPtr = currPtr->NextNode(); if (prevPtr = NULL) /如果插入点在表头 InsertFront(head,item); else newNode = GetNode(item); prevPtr->InsertAfter(newNode); template <class T>void ClearList(Node<T> * &head) Node<T> *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 <iostream>#include "9_5.h"#include "node.h"using namespace std;int main() Node<int> *head = NULL, *prevPtr, *delPtr; int i, key, item; for (i=0;i < 10;i+) cout<<"please input " <<i+1<<" number To insert a header :"<<endl; cin>>item; InsertFront(head, item); cout << "List: " PrintList(head,noNewline); cout << endl; cout << "请输入一个需要删除的整数: " cin >> 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);运行结果：please input 1 number To insert a header :1please input 2 number To insert a header :2please input 3 number To insert a header :3please input 4 number To insert a header :4please input 5 number To insert a header :5please input 6 number To insert a header :6please input 7 number To insert a header :7please input 8 number To insert a header : 8please input 9 number To insert a header :9please input 10 number To insert a header :10List: 10 9 8 7 6 5 4 3 2 1请输入一个需要删除的整数: 2List: 10 9 8 7 6 5 4 3 12. /link.h#ifndef LINKEDLIST_CLASS#define LINKEDLIST_CLASS#include <iostream>#include <cstdlib>using namespace std;#ifndef NULLconst int NULL = 0;#endif / NULL#include "9_5.h"template <class T>class LinkedList private: Node<T> *front, *rear; Node<T> *prevPtr, *currPtr; int size; int position; Node<T> *GetNode(const T& item,Node<T> *ptrNext=NULL); void FreeNode(Node<T> *p); void CopyList(const LinkedList<T>& L); public: LinkedList(void); LinkedList(const LinkedList<T>& L); /拷贝构造函数 LinkedList(void); LinkedList<T>& operator= (const LinkedList<T>& L); int ListSize(void) const; /返回链表中元素个数（size） int ListEmpty(void) const; /size等于0时返回TRUE,否则返回FALSE void Reset(int pos = 0); void Next(void); /使prevPtr和currPtr移动到下一个节点 int EndOfList(void) const; int CurrentPosition(void) const; /返回数据成员position void InsertFront(const T& item); /在表头插入 void InsertRear(const T& item); /在表尾添加 void InsertAt(const T& item); /在当前节点之前插入 void InsertAfter(const T& item); /在当前节点之后插入 T DeleteFront(void); /删除头节点 void DeleteAt(void); /删除当前节点 T& Data(void); void ClearList(void);template <class T>Node<T> *LinkedList<T>:GetNode(const T& item, Node<T>* ptrNext) Node<T> *p; p = new Node<T>(item,ptrNext); if (p = NULL) cout << "Memory allocation failure!n" exit(1); return p;template <class T>void LinkedList<T>:FreeNode(Node<T> *p) delete p;template <class T>void LinkedList<T>:CopyList(const LinkedList<T>& L) Node<T> *p = L.front; int pos; while (p != NULL) InsertRear(p->data); p = p->NextNode(); if (position = -1) return; prevPtr = NULL; currPtr = front; for (pos = 0; pos != position; pos+) prevPtr = currPtr; currPtr = currPtr->NextNode(); template <class T>LinkedList<T>:LinkedList(void): front(NULL), rear(NULL), prevPtr(NULL),currPtr(NULL), size(0), position(-1)template <class T>LinkedList<T>:LinkedList(const LinkedList<T>& L) front = rear = NULL; prevPtr = currPtr = NULL; size = 0; position = -1; CopyList(L);template <class T>void LinkedList<T>:ClearList(void) Node<T> *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 <class T>LinkedList<T>:LinkedList(void) ClearList();template <class T>LinkedList<T>& LinkedList<T>:operator= (const LinkedList<T>& L) if (this = &L) / 不能将链表赋值给它自身 return *this; ClearList(); CopyList(L); return *this;template <class T>int LinkedList<T>:ListSize(void) const return size; template <class T>int LinkedList<T>:ListEmpty(void) const return size = 0;template <class T>void LinkedList<T>:Next(void) if (currPtr != NULL) prevPtr = currPtr; currPtr = currPtr->NextNode(); position+; template <class T>int LinkedList<T>:EndOfList(void) const return currPtr = NULL;template <class T>int LinkedList<T>:CurrentPosition(void) const return position;template <class T>void LinkedList<T>:Reset(int pos) int startPos; if (front = NULL) return; if (pos < 0 | pos > size-1) cerr << "Reset: Invalid list position: " << pos << endl; return; if(pos = 0) prevPtr = NULL; currPtr = front; position = 0; else currPtr = front->NextNode(); prevPtr = front; startPos = 1; for(position=startPos; position != pos; position+) prevPtr = currPtr; currPtr = currPtr->NextNode(); template <class T>T& LinkedList<T>:Data(void) if (size = 0 | currPtr = NULL) cerr << "Data: invalid reference!" << endl; exit(1); return currPtr->data;template <class T>void LinkedList<T>:InsertFront(const T& item) if (front != NULL) Reset(); InsertAt(item); / 在表头插入template <class T>void LinkedList<T>:InsertRear(const T& item) Node<T> *newNode; prevPtr = rear; newNode = GetNode(item); / 创建新结点 if (rear = NULL) / 如果表空则插入在表头 front = rear = newNode; else rear->InsertAfter(newNode); rear = newNode; currPtr = rear; position = size; size+;template <class T>void LinkedList<T>:InsertAt(const T& item) Node<T> *newNode; if (prevPtr = NULL) newNode = GetNode(item,front); front = newNode; else newNode = GetNode(item); prevPtr->InsertAfter(newNode); if (prevPtr = rear) rear = newNode; position = size; currPtr = newNode; size+; template <class T>void LinkedList<T>:InsertAfter(const T& item) Node<T> *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 <class T>T LinkedList<T>:DeleteFront(void) T item; Reset(); if (front = NULL) cerr << "Invalid deletion!" << endl; exit(1); item = currPtr->data; DeleteAt(); return item;template <class T>void LinkedList<T>:DeleteAt(void) Node<T> *p; if (currPtr = NULL) cerr << "Invalid deletion!" << endl; exit(1); if (prevPtr = NULL) p = front; front = front->NextNode(); else p = prevPtr->DeleteAfter(); if (p = rear) rear = prevPtr; position-; currPtr = p->NextNode(); FreeNode(p); size-;#endif / LINKEDLIST_CLASS/lab9_2.cpp#include "link.h"int main() LinkedList<int> A, B; for(int i=0;i<5;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.Ret(); while(!B.EndOfList() A.InsertRear(B.Data(); B.Next(); A.Reset(); cout << "此时，链表A的元素为：" ; while(!A.EndOfList() cout << A.Data() << " " A.Next(); cout << endl;3. /queue.h#ifndef QUEUE_CLASS#define QUEUE_CLASS#include <iostream>#include <cstdlib>using namespace std;#include "link.h"template <class T>class Queue private: LinkedList<T> 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 <class T>Queue<T>:Queue(void)template <class T>int Queue<T>:QLength(void) const return queueList.ListSize();template <class T>int Queue<T>:QEmpty(void) const return queueList.ListEmpty();template <class T>void Queue<T>:QClear(void) queueList.ClearList();template <class T>void Queue<T>:QInsert(const T& elt) queueList.InsertRear(elt);template <class T>T Queue<T>:QDelete(void) if (queueList.ListEmpty()