群体类和群体数据

（

二〇一一年 十 一月

《面向对象的程序设计》实验报告

学校代码： 10128 学 号：

题 目：群体类和群体数据 学生姓名： 学 院：理学院 系 别：数学系

专 业：信息与计算科学 班 级： 任课教师：

精选文库

一、实验目的

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、将直接插入排序、直接选择排序、冒泡排序、顺序查找函数封装到第九章的数组类

中，作为成员函数，实现并测试这个类。

三、实验程序及结果

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.h"

using namespace std;

// 生成结点：创建一个结点，数据成员值为item，指向后继结点的指针值为nextPtr

template

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 << currPtr->data << endl;

else

cout << currPtr->data << " ";

// 使currPtr指向下一个结点

currPtr = currPtr->NextNode();

}

}

//查找结点

//在指针head所指向的链表中查找数据域等于item的结点

//找到则返回TRUE及其前趋结点的地址，否则返回FALSE

template

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 < currPtr->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.h"

using namespace std;

int main()

{

// 将表头指针置为 NULL

Node *head = NULL, *prevPtr, *delPtr;

int i, key, item;

// 输入10个整数依次向表头插入

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程序二

//lab9_2.cpp

#include "link.h"

int main()

{

LinkedList 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;

}

//link.h

#ifndef LINKEDLIST_CLASS

#define LINKEDLIST_CLASS

#include

#include

using namespace std;

#ifndef NULL

const int NULL = 0;

#endif // NULL

#include "9-3.h

template

精选文库

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为-1

template

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++;

}

}

// 如果已经遍历完链表则返回True

template

int LinkedList::EndOfList(void) const

{

return currPtr == NULL;

}

// 返回当前结点的位置

template

int LinkedList::CurrentPosition(void) const

{

return position;

}

//将链表当前位置设置为pos

template

精选文库

void LinkedList::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, prevPtr, 和 position

{

currPtr = front->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!" << endl;

精选文库

exit(1);

}

return currPtr->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!" << endl;

exit(1);

}

item = currPtr->data;

DeleteAt();

return item;

}

// 删除链表当前位置的结点

template

void LinkedList::DeleteAt(void)

{

Node *p;

// 如果表空或达到表尾则出错

if (currPtr == NULL)

{

cerr << "Invalid deletion!" << endl;

exit(1);

}

// 删除将发生在表头或链表之中

if (prevPtr == NULL)

{

// 保存头结点地址并将其从链表中分离。

p = front;

front = front->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.h"

template

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 NULL

const int NULL = 0;

#endif // NULL

#include "9-3.h"

template

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);