C++学习笔记（Day16 实验九）

//
// Created by BoBo on 2021/10/26.
//

#ifndef NODE_H
#define NODE_H
template 
class Node {
private:
    Node* next;
public:
    T data;
    Node() {data = 0;next = NULL;}
    Node(const T& data, Node* next = 0);
    void insertAfter(Node* p);
    Node* deleteAfter();
    Node* nextNode();
    const Node* nextNode() const;
};
template 
Node::Node(const T &data,Node *next):data(data),next(next){}

template 
Node* Node::nextNode(){
    return next;
}
template
const Node* Node::nextNode() const{
    return next;
}

template 
void Node::insertAfter(Node *p) {
    p->next = next;
    next = p;
}
template 
Node* Node::deleteAfter() {
    Node* temPtr = next;
    if(next == 0)
        return 0;
    next = temPtr->next;
    return temPtr;
}
#endif //NODE_H

#include 
#include "Node.h"
using namespace std;

int main() {
    int a[10];
    Node n[10];
    cout << "输入10个整数：" << endl;
    for(int i = 0;i<10;i++){
        cin >> a[i];
    }
    for(int i =0;i<9;i++){
        n[i].data = a[i];
        n[i].insertAfter(&n[i+1]);
    }
    n[9].data = a[9];
    Node*  np = &n[0];
    while(np !=NULL){
        cout << np->data<< " ";
        np = np->nextNode();
    }
    cout << endl;
    int f;
    cout<<"请输入要查找的数： ";
    cin >> f;
    Node p(0,&n[0]);//定义了一个新的对象，其中指针指向数组n的首地址，调用当前对象的nextNode方法返回地址，用此指针调用数组n中的data
    np = &p;
    while(np->nextNode()!=NULL){
        while(np->nextNode()->data == f)
            np->deleteAfter();
        np = np->nextNode();
    }
    cout << "删除后的链表： " <data<<" ";
        np = np->nextNode();
    }
    np = &p;
    while(np->nextNode()!= NULL)
        np->deleteAfter();
    cout << endl;
    return 0;
}

实验9-2

编写程序实现链表类，在测试程序中声明两个整型链表A和B，分别插入5个元素，然后把B中的元素加入A的尾部。

#ifndef NODE_H_
#define NODE_H_

template 
class Node {
private:
	T data;
public:
	Node* next;
	Node();
	Node(const T& data, Node* nt = 0);
//	Node(T data, Node* n = NULL);
	T& getData();
};

template 
Node::Node() {
	data = 0;
	next = NULL;
}

template 
Node::Node(const T& d, Node* nt) {
	data = d;
	next = nt;
}

template 
T& Node::getData() {
	return data;
}

#endif //NODE_H_

#ifndef link_H_
#define link_H_

#include "node.h"


template 
class linkedList {
private:
	Node *front, *rear; //表头和表尾指针
	Node *prevPtr, *currPtr; //记录表当前遍历位置的指针，由插入和删除操作更新
	int size; //表中元素个数
	int position; //当前元素在表中的位置序号。由函数reset使用

	Node* newNode(const T& item, Node *ptrNext = NULL); //生成新节点，数据与为item，指针域为prtNext
	void freeNode(Node *p); //释放节点

	void copy(const linkedList& L); //将链表L复制到当前表（假设当前表为空），被复制构造函数和operator=调用

public:
	linkedList(); //构造函数
	linkedList(const linkedList& L); //复制构造函数
	~linkedList(); //析构函数
	linkedList& operator = (const linkedList& L); //重载赋值运算符

	int getSize() const; //返回链表中元素个数
	bool isEmpty() const; //链表是否为空

	void reset(int pos = 0); //初始化游标的位置
	void next(); //使游标移动到下一个节点
	bool endOfList() const; //游标是否移动到链尾
	int currentPosition() const; //返回游标当前的位置
	
	void insertFront(const T& item); //在表头插入节点
	void insertRear(const T& item); //在表尾插入节点
	void insertAt(const T& item); //在当前节点之前插入节点
	void insertAfter(const T& item); //在当前节点之后插入节点

	T deleteFront(); //删除头节点
	void deleteCurrent(); //删除当前节点
	
	T& data(); //返回对当前节点成员数据的引用
	const T& data() const; //返回对当前节点成员数据的常引用

	void clear(); //清空链表：释放所有节点的内存空间，被析构函数和operator=使用
};

//生成新节点，数据与为item，指针域为prtNext
template 
Node* linkedList::newNode(const T& item, Node *ptrNext) {
	Node *n = new Node(item, ptrNext);
	return n;
}

//释放节点
template 
void linkedList::freeNode(Node *p) {
	Node* temp = front;
	while (temp->next != p) {
		temp = temp->next;
		if (temp == currPtr)
			position ++;
	}
	temp->next = p->next;
	if (currPtr == p)
		currPtr = currPtr->next;
	if (prevPtr == p) {
		prevPtr = prevPtr->next;
		currPtr = currPtr->next;
	}
	delete p;
	size --;
	position --;
}

//将链表L复制到当前表（假设当前表为空），被复制构造函数和operator=调用
template 
void linkedList::copy(const linkedList& L) {
	Node *temp = L.front, *ptr = front;
	while (temp != L.rear) {
		ptr->next = new Node(temp->getData, NULL);
		ptr = ptr->next;
		temp = temp->next;
	}
	ptr->next = rear;
	size = L.getSize();
	position = L.currentPosition();
}

//构造函数
template 
linkedList::linkedList() {
	front = new Node();
	rear = new Node();
	front->next = rear;
	currPtr = rear;
	prevPtr = front;
	size = 0; //不计算front和rear
	position = 0; //在front下一个元素视为0
}

//复制构造函数
template 
linkedList::linkedList(const linkedList& L) {
	clear();
	copy(L);
}

//析构函数
template 
linkedList::~linkedList() {
	linkedList::clear();
	delete front;
	delete rear;
}

//重载赋值运算符
template 
linkedList& linkedList::operator = (const linkedList& L) {
	clear();
	copy(L);
}

//返回链表中元素个数
template 
int linkedList::getSize() const {
	return size;
}

//链表是否为空
template 
bool linkedList::isEmpty() const {
	return (size == 0);
}

//初始化游标的位置
template 
void linkedList::reset(int pos) { //初始化游标位置
	if (pos > size) {
		cout << "越界，无法访问" << endl;
		return;
	}
	int i = 0;
	prevPtr = front;
	currPtr = front->next;
	while (i < pos) {
		if (currPtr == rear) {
			cout << "越界，无法访问" << endl;
			return;
		}
		i ++;
		currPtr = currPtr->next;
		prevPtr = prevPtr->next;
	}
	position = pos;
}

//使游标移动到下一个节点
template 
void linkedList::next() {
	if (currPtr == rear) {
		cout << "已经到达链表尾，无法移动" << endl;
		return;
	}
	currPtr = currPtr->next;
	prevPtr = prevPtr->next;
	position ++;
}

//游标是否移动到链尾
template 
bool linkedList::endOfList() const {
	return (currPtr == rear);
}

//返回游标当前的位置
template 
int linkedList::currentPosition() const {
	return position;
}

//在表头插入节点
template 
void linkedList::insertFront(const T& item) {
	Node* n = new Node(item, front);
	front = n;
	size ++;
	position ++;
}

//在表尾插入节点
template 
void linkedList::insertRear(const T& item) {
	Node* temp = front;
	while (temp->next != rear)
		temp = temp->next;
	Node *n = new Node(item, rear);
	temp->next = n;
	size ++;
}

//在当前节点之前插入节点
template 
void linkedList::insertAt(const T& item) {
	Node* temp = new Node(item, currPtr);
	prevPtr->next = temp;
	prevPtr = temp;
	size ++;
	position ++;
}

//在当前节点之后插入节点
template 
void linkedList::insertAfter(const T& item) {
	Node* temp = new Node(item, NULL);
	temp->next = currPtr->next;
	currPtr->next = temp;
	size ++;
}

//删除头节点，实质是删除front->next
template 
T linkedList::deleteFront() {
	if (front->next == rear) {
		cout << "没有节点可以删除" << endl; 
	}
	if (prevPtr == front->next) {
		prevPtr = prevPtr->next;
		currPtr = currPtr->next;
	}
	Node* temp = front->next;
	T d = temp->getData();
	front->next = temp->next;
	delete temp;
	size --;
	if (front->next != rear)
		position --;
	return d;
}

//删除当前节点
template 
void linkedList::deleteCurrent() {
	Node* temp = currPtr;
	currPtr = currPtr->next;
	delete temp;
	size --;
}
	
//返回对当前节点成员数据的引用
template 
T& linkedList::data() {
	return currPtr->getData();
}

//返回对当前节点成员数据的常引用
template 
const T& linkedList::data() const {
	return currPtr->getData();
}

//清空链表：释放所有节点的内存空间，被析构函数和operator=使用
template 
void linkedList::clear() {
	Node* temp;
	while (front->next != rear) {
		temp = front->next;
		front->next = temp->next;
		delete temp;
	}
	size = 0;
	position = 0;
}

#endif //link_H_

#include "stdafx.h"

#include 
#include "link.h"
using namespace std;

int main()
{
	linkedList A, B;
    int i, item;
	
    cout << "请输入加入链表A的五个整数：";
	for (i = 0; i < 5; i ++) {
		cin >> item;
		A.insertRear(item);
	}
	cout << "请输入加入链表B的五个整数：";
	for (i = 0; i < 5; i ++) {
		cin >> item;
		B.insertRear(item);
	}
	cout << endl << "有序链表A中的元素为：";
	A.reset();
	while(!A.endOfList()) {
		cout << A.data() << "  ";
		A.next();
	}
	cout << endl << "有序链表B中的元素为：";
	B.reset();
	while(!B.endOfList()) {
		A.insertRear(B.data());//在遍历链表B的时候，一边插入A、一边输出
		cout << B.data() << "  ";
		B.next();
	}
	
	cout << endl << "加入链表B中元素后，链表A中的元素为：";
	A.reset();
	while(!A.endOfList()) {
		cout << A.data() << "  ";
		A.next();    
	}
	cout << endl;
	return 0;
}

例题9-4

将直接插入排序、直接选择排序、冒泡排序、顺序查找函数封装到数组类Array中，作为成员函数。实现并测试这个类。

#ifndef ARRAY1_H_
#define ARRAY1_H_

template 
class Array
{
	T* alist;
	int size;
public:
	Array() {size = 0;}
	Array(int sz) {alist = new T[sz]; size = sz;}
	Array(T a[], int sz) {
		size = sz;
		alist = new T[size];
		for (int i = 0; i < size; i ++)
			alist[i] = a[i];
	}
	~Array() {size = 0; delete []alist;}
	int getSize() {return size;}
	T& operator [](int i) {return alist[i];}
	void insertSort();
	void selectSort();
	void bubbleSort();
	int seqSearch(T key) {
		int i;
		for (i = 0; i < size; i ++)
			if (alist[i] == key)
				return i;
		if (i == size) {
			cout << "没有找到元素" << endl;
			return -1;
		}
	}
};

template 
void Array::insertSort()
{
	int i, j;
	T temp;
	//将下标为1～size-1的元素逐个插入到已排序序列中适当的位置
	for (i = 1; i < size; i ++) 
	{
		//从a[i-1]开始向a[0]方向扫描各元素,寻找适当位置插入a[i]
		j = i;
		temp = alist[i];
		while (j > 0 && temp < alist[j-1]) 
		{   //逐个比较，直到temp>=a[j-1]时，j便是应插入的位置。
			alist[j] = alist[j-1];  //将元素逐个后移，以便找到插入位置时可立即插入。
			j--;
		}
		//插入位置已找到，立即插入。
		alist[j] = temp;
	}
	//输出数据
	for(i = 0; i < size; i ++)
		cout << alist[i] << "  ";
	cout << endl;
}

template 
void Array::selectSort()
{
	int minIndex; //每一次选出的最小元素之下标
	int i, j;
	T temp;
	//sort a[0]..a[size-2], and a[size-1] is in place
	for (i = 0; i < size - 1; i ++) 
	{
		minIndex = i;    //最小元素之下标初值设为i
		//在元素a[i+1]..a[size-1]中逐个比较显出最小值
		for (j = i + 1; j < size; j++) 
			//minIndex始终记录当前找到的最小值的下标
			if (alist[j] < alist[minIndex])
				minIndex = j;
		//将这一趟找到的最小元素与a[i]交换
		temp = alist[i];
		alist[i] = alist[minIndex];
		alist[minIndex] = temp;
	}
	//输出数据
	for(i = 0; i < size; i ++)
		cout << alist[i] << "  ";
	cout << endl;
}

template 
void Array::bubbleSort()
{
	T temp;
	int i, j;
	for (i = 1; i < size; i ++) {
		for (j = size - 1; j >= i; j --) {
			if (alist[j - 1] > alist[j]) {
				temp = alist[j];
				alist[j] = alist[j - 1];
				alist[j - 1] = temp;
			}
		}
	}
	for(i = 0; i < size; i ++)
		cout << alist[i] << "  ";
	cout << endl;
}

#endif //ARRAY1_H_

#include 
#include "array1.h"
using namespace std;

int main()
{
	int a[5] = {3, 6, 1, 8, 2};
	double d[4] = {4.1, 3.2, 5.6, 1.9};
	char c[3] = {'g', 'c', 'A'};
	Array iArray(a, 5);
	iArray.insertSort();
	Array dArray(d, 4);
	dArray.selectSort();
	Array cArray(c, 3);
	cArray.bubbleSort();
	return 0;
}

C++学习笔记（Day16 实验九）

C/C++/C#相关栏目本月热门文章