实验报告群体类和群体数据模板.doc

学校代码: 10128
学 号: 20905060

《面向对象程序设计》试验汇报

（

题 目: 群体类和群体数据
学生姓名: 燕飞
学 院: 理学院
系 别: 数学系
专 业: 信息与计算科学
班 级: 信计12-2
任课老师: 侯睿

二 〇 一 五 年 十 一 月

一、 试验目
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 name[21]、 成绩short score; 在试验七student类中增加属性; 所修课程course, 为课程类对象链表。在测试程序中测试这个类, 学生类与课程类关系如图

5、 将直接插入排序、 直接选择排序、 冒泡排序、 次序查找函数封装到第九章数组类中, 作为组员函数, 实现并测试这个类。
三、 试验程序
1、
#ifndef NODE_CLASS
#define NODE_CLASS
template <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;
next = p;
}
template <class T>
Node<T> *Node<T>::DeleteAfter(void)
{
Node<T> *tempPtr = next;
if (next == NULL)
return NULL;
next = tempPtr->next;
return tempPtr;
}
#endif
#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();
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)
{
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;
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;
}
head = NULL;
}
#endif
#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++)
{
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);
}
2、
#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.Reset();
while(!B.EndOfList())
{
A.InsertRear(B.Data());
B.Next();
}
A.Reset();
cout << "此时, 链表A元素为: " ;
while(!A.EndOfList())
{
cout << A.Data() << " ";
A.Next();
}
cout << endl;
}
#ifndef LINKEDLIST_CLASS
#define LINKEDLIST_CLASS
#include <iostream>
#include <cstdlib>
using namespace std;
#ifndef NULL
const int NULL = 0;
#endif // NULL
#include "9-3.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;
int ListEmpty(void) const;
void Reset(int pos = 0);
void Next(void);
int EndOfList(void) const;
int CurrentPosition(void) const;
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
3、
#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())
{
cerr << "Calling QDelete for an empty queue!" << endl;
exit(1);
}
return queueList.DeleteFront();
}
template <class T>
T Queue<T>::QFront(void)
{
if (queueList.ListEmpty())
{
cerr << "Calling QFront for an empty queue!" << endl;
exit(1);
}
queueList.Reset();
return queueList.Data();
}
#endif
#ifndef LINKEDLIST_CLASS
#define LINKEDLIST_CLASS
#include <iostream>
#include <cstdlib>
using namespace std;
#ifndef NULL
const int NULL = 0;
#endif
#include "9-3.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;
int ListEmpty(void) const;
void Reset(int pos = 0);
void Next(void);
int EndOfList(void) const;
int CurrentPosition(void) const;
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 Li