Welcome to Aoki's Blog!

"吾生也有涯，而知也无涯"

指针，又见指针

2019-06-10

C++

C++ 指针
指针，又见指针

一、指针简介

一般来说，指针是一个其数值为地址的变量（或更一般地说是一个数据对象）。正如char类型的变量用字符作为其数值，而int类型变量的数值是整数，指针变量的数值表示的是地址。

如果你将某个指针变量命名为ptr，就可以使用如下语句：
```
ptr=&pooh;   //把pooh的地址赋给ptr
```
对于这个语句，我们称ptr指向pooh。ptr和&pooh的区别在于前者是变量，后者是常量。ptr可以指向任何地方：
```
ptr=&bath;    //令ptr指向bath  
```
二、间接运算符

假定ptr指向bath：ptr=&bath

这时就可以使用间接运算符*（也称取值运算符）来获取bath中存放的数值。
```
val=*ptr;    //得到ptr指向的值
```
语句ptr=&bath；以及语句val=*ptr；放在一起等同于下面的语句：
```
val=bath;
```
下面进行举例：
```
nurse=22;
ptr=&nurse;  //指向nurse的指针
val=*ptr;  //将ptr指向的值赋给val
```
上述语句实现的功能是把数值22赋给变量val

三、指针声明

例如：long和float两种类型的数值可能使用相同大小的存储空间，但是他们的数据存储方式完全不同，指针的声明形式如下：
```
int *pi;  //pi是指向一个整数变量的指针
char *pc;  //pc是指向一个字符变量的指针
float *pf,*pg;  //pf和pg是指向浮点变量的指针
```
类型标识符表明了被指向变量的类型，而表示该变量是一个指针。声明int * pi;的意思是pi是一个指针，而且pi是int类型的。

*和指针名之间地空格是可选的。通常程序员在声明中用空格，而在指向变量时将其省略。

pc所指向的值（*pc）是char类型的。而pc本身是什么类型的？

我们将其描述为“指向char的指针”类型。pc的值是一个地址，在大多数系统中，它是由一个无符号整数表示。但是这并不表示可以把指针当做整数类型。一些处理整数的方法不能用来处理指针，反之亦然。例如，可以进行两整数相乘，而指针不能。因此指针的确是一种新的数据类型，而不是整数类型。

四、使用指针在函数间通信

在下面的程序中，函数interchange（）只用了指针参数，我们将对该函数进行详细的讨论。
```
#include<stdio.h>
void interchange(int * u, int * v);
int main(void)
{
	int x = 5, y = 10;
	printf("Originally x=%d and y= %d.\n", x, y);
	interchange(&x, &y); //向函数传送地址
	printf("Now x= %d and y=%d.\n", x, y);
	return 0;
}

void interchange(int * u, int * v)
{
	int temp;
	temp = *u;//temp得到u指向的值。
	*u = *v;
	*v = temp;
}
```
下面我们分析以上程序的运行情况。首先，函数调用语句如下：
```
interchange(&x, &y); //向函数传送地址
```
可以看出，函数传递的是x和y的地址而不是他们的值。这就意味着intechange（）函数原型声明和定义中的形式参数u和v将使用地址作为它们的值。因此他们应该声明为指针，由于x和y都是整数，所以u和v是指向整数的指针。其声明如下：
```
void interchange(int * u, int * v);
```
接下来，函数体进行如下声明：
```
int temp;
```
从而提供了所需要的临时变量。为了把x的值存在temp中，需要使用下面语句：
```
temp = *u;//temp得到u指向的值。
```
注意，因为u的值是&x，所以u指向x的地址，这就以意味着*u代表了x的值，而这正是我们需要的数值。

在示例程序中，我们用一个函数实现x和y的数值交换。首先函数使用x和y的地址作为参数，这使得它可以访问x和y变量。通过使用指针和运算符*，函数可以获得相应存储地址的数据，从而就可以改变这些数据。

在ANSI原型中可以省略变量名称。这样，函数原型可以按如下形式进行声明：
```
void interchange (int * ,int *);
```
通常情况下，可以把关于变量的两类信息传递给一个函数，如果函数的调用形式为：
```
function1(x);
```
这时传递的是x的值，但是如果使用下面这种函数调用形式：
```
function2(&x);
```
那么会把x的地址传递给函数。第一种调用形式要求函数定义部分必须包含一个和x具有相同数据类型的形式参数。如下所示：
```
int function1(int num);
```
而第二种形式要求函数定义部分的形式参数必须是指向相应数据类型的指针：
```
int function2(int *ptr);
```
使用函数进行数据计算等操作时，可以使用第一种调用形式。但是如果需要改变调用函数中的多个变量的值时，就需要使用第二种调用形式。

尽管interchange（）只使用局部变量，但是通过使用指针，该函数可以操作main（）中的变量的值。

The End
Read All
顺序循环队列的实现

2019-03-31

数据结构

数据结构队列
顺序循环队列的实现

写在前面

队列（Queue)是一种特殊的线性表，是一种只允许在表的一端进行插入操作，在表的另一端进行删除操作的线性表。表中允许进行插入操作的一端称为队尾，允许进行删除操作的一端为队头。队头和队尾分别由队头指示器和队尾指示器指示。队列的插入操作通常称为入队，队列的删除操作通常称为出队。当队列中没有元素时，为空队列。
根据队列的定义，每次进队列的数据元素都放在原来的队尾之后成为新的队尾元素，每次出队列得到数据元素都是原来的队头元素。这样，最先入队的数据元素总是最先出队，所以队列也被称为先进先出表。
对队列的操作主要有：初始化建立队列、入队列、出队列、取队头元素、判断队列是否为空等操作。

1.顺序队列的类定义
```
const int maxsize = 10;
template<class T>
class Queue
{
public:
	Queue();//构造函数
	~Queue() {};//析构函数
	void insert(const T&item);//入队
	T delet();//出队列
	T readFront() const;//读队头元素
	bool empty() const;//判断队列是否为空
	void clearQueue();//清空队列
	int getsize() const;//获取队列长度
	void display() const;//输出队列中的元素

private:
	T data[maxsize];
	int front;
	int rear;
	int count;
};
```
2.顺序队列类的实现
Read All

链式队列的实现

2019-03-31

数据结构

数据结构链式队列

链式队列的实现

写在前面

链式队列是队列的链式存储结构表示。队列是操作受限的表，队列有队头和队尾，插入元素的一端称为队尾，删除元素的一端称为队头。这和一般排队的概念一样，后来的人排在队尾，首先对队头的人进行服务，对队头的人服务后，原当前队头后的人就排在了当前队头。新来的人排在队尾后，原队尾的人就不再是当前队尾了，新来的人就成了当前队尾。
链式队列的队头指针指在队列的当前队头节点位置，队尾指针指在队列的当前队尾节点位置。不带头节点的链式队列，出队列时可直接删除头指针所指的节点，因此，链式队列不带头指针时更加方便。

1.链式队列节点类的定义和实现

template<class T>
class LinkQueue;

template<class T>
class QueueNode
{
	friend class LinkQueue<T>;
public:
	T data;
	QueueNode<T>(const T& item, QueueNode<T> *ptrNext = NULL);
	~QueueNode() {};

private:
	QueueNode<T> *next;
};

template<class T>
inline QueueNode<T>::QueueNode(const T & item, QueueNode<T>* ptrNext)
{
	this->data = item;
	this->next = ptrNext;
}

2.链式队列类的定义

template<class T>
class LinkQueue
{
public:
	LinkQueue();//构造函数
	~LinkQueue();//析构函数

	void insert(const T& item);//入队
	T delet();//出队
	T readFront() const;//读队头元素
	bool empty() const;//判断队列是否为空
	void clearQueue();//清空队列
	int getSize() const;//取队列长度
	void display() const;//输出队列元素

private:
	QueueNode<T> *front;//指向队头的指针
	QueueNode<T> *rear;//指向队尾的指针
	int size;
};

3.链式队列类的实现

template<class T>
inline LinkQueue<T>::LinkQueue()
{
	size = 0;
	front = rear = NULL;
}

template<class T>
inline LinkQueue<T>::~LinkQueue()
{
	clearQueue();
	front = rear = NULL;
}

template<class T>
inline void LinkQueue<T>::insert(const T & item)
{
	QueueNode<T> *new_node = new QueueNode<T>(item);
	if (rear != NULL)
	{
		rear->next = new_node;
	}
	rear = new_node;
	if (front == NULL)
	{
		front = new_node;
	}
	size++;
}

template<class T>
inline T LinkQueue<T>::delet()
{
	if (size == 0)
	{
		cout << "Queue is empty" << endl;
		exit(1);
	}
	T member = front->data;
	QueueNode<T> *p = front->next;
	delete front;
	front = p;
	size--;
	return member;
}

template<class T>
inline T LinkQueue<T>::readFront() const
{
	return front->data;
}

template<class T>
inline bool LinkQueue<T>::empty() const
{
	return (size==0);
}

template<class T>
inline void LinkQueue<T>::clearQueue()
{
	QueueNode<T> *p1, *p2;
	p1 = front;
	while (p1 != NULL)
	{
		p2 = p1;
		p1 = p1->next;
		delete p2;
	}
	size = 0;
}

template<class T>
inline int LinkQueue<T>::getSize() const
{
	return size;
}

template<class T>
inline void LinkQueue<T>::display() const
{
	QueueNode<T> *p = front;
	int i = 0;
	while (p != NULL)
	{
		cout << "第" << i << "号元素为：" << p->data << endl;
		i++;
		p = p->next;
	}
}

4.测试主函数

void test()
{
	LinkQueue<int> queue;
	for (int i = 0; i < 10; i++)
	{
		queue.insert(i * 10);
	}
	cout << "队列长度为：" << queue.getSize() << endl;
	queue.display();
	cout << "栈顶元素为：" << queue.readFront() << endl;
	for (int i = 0; i < 10; i++)
	{
		cout << "元素：" << queue.delet() << "被删除" << endl;
	}
	cout << "队列长度为：" << queue.getSize() << endl;
}

int main()
{
	test();
	system("pause");
	return EXIT_SUCCESS;
}void test()
{
	LinkQueue<int> queue;
	for (int i = 0; i < 10; i++)
	{
		queue.insert(i * 10);
	}
	cout << "队列长度为：" << queue.getSize() << endl;
	queue.display();
	cout << "栈顶元素为：" << queue.readFront() << endl;
	for (int i = 0; i < 10; i++)
	{
		cout << "元素：" << queue.delet() << "被删除" << endl;
	}
	cout << "队列长度为：" << queue.getSize() << endl;
}

int main()
{
	test();
	system("pause");
	return EXIT_SUCCESS;
}

输出结果如下：

The End

Read All

双向循环链表

2019-03-28

数据结构

数据结构双向循链表

双向循环链表

写在前面

双向循环链表（Double Circular Linked List)是每个节点有前趋指针和后继指针，且后继指针和前趋指针各自构成自己的单循环链表的链表。
在单链表中查找当前节点的后继节点并不困难，可以通过当前节点的next指针进行，但要查找当前节点的前趋节点就要从头指针head开始重新进行。对于一个要进行频繁查找当前节点的后继节点和当前节点的前趋节点的应用来说，使用单链表的时间效率是非常低的，双向链表是有效解决这类问题的选择。
在双向链表中，每个节点包括三个域，分别是data,next,prior。其中data为数据域，next为后继节点指针，prior为前趋节点指针。
双向链表通常均为双向循环链表，这是因为读双向循环链表，不论是插入还是删除，对第一个节点、最后一个节点的操作和对链表中间任意一个节点的操作过程是一样的。而双向非循环链表对这些节点的操作是不同的。

1.节点类的定义和实现

template<class T>
class DCirlist;
template<class T>
class DLnode
{
	friend class DCirlist<T>;
public:
	T data;
	//构造函数，无数据域的头结点
	DLnode<T>(DLnode<T> *ptrn = NULL, DLnode<T> *ptrp = NULL){};
	//构造函数，非头节点的节点
	DLnode<T>( T item, DLnode<T> *ptrn = NULL, DLnode<T> *ptrp = NULL);
	//析构函数
	~DLnode() {};
private:
	DLnode<T> *next;
	DLnode<T> *prior;
};

template<class T>
inline DLnode<T>::DLnode(T item, DLnode<T>* ptrn, DLnode<T>* ptrp)
{
	this->data = item;
	this->next = ptrn;
	this->prior = ptrp;
}

双向循环链表只是在单循环链表的基础上又增加了一个指向前趋节点的指针，而且指向前趋节点指针也构成了自己的单循环链表。双循环链表的定义与单循环链表的定义非常相似。

2.双向循环链表类的定义

template <class T>
class DCirlist
{
public:
	DCirlist();//构造函数
	~DCirlist();//析构函数
	int listsize() const;//返回链表长度
	bool empty() const;//判断链表是否为空
	DLnode<T> *index(int pos) const;//返回指向第pos个节点的指针

	void insert(const T &item, int pos);//在第pos个节点插入item
	T del(int pos);//删除第pos个节点，并返回数据域
	T getdata(int pos) const;//返回第pos个节点的值
	void clearlist();//清空表

	DLnode<T> *reset(int pos = 0);
	DLnode<T> *next();
	DLnode<T> *prior();
	bool EndOfList() const;//是否到链表尾

	bool nextEndoflist() const;//currPtr->next是否到链表尾
	bool PriorEndoflist() const;//currPtr->prior是否到链表尾
	T deleprior();//删除currPtr节点，新currPtr是原currPtr的前趋，返回数据域

private:
	DLnode<T> *head;
	DLnode<T> *currPtr;
	int size;
};

3.双向循环链表类的实现

template<class T>
inline DCirlist<T>::DCirlist()
{
	head = new DLnode<T>();
	head->next = head;
	head->prior = head;
	size = 0;
}

template<class T>
inline DCirlist<T>::~DCirlist()
{
	clearlist();
	delete head;
	head = NULL;
}

template<class T>
inline int DCirlist<T>::listsize() const
{
	return size;
}

template<class T>
inline bool DCirlist<T>::empty() const
{
	return (size == 0);
}

template<class T>
inline DLnode<T>* DCirlist<T>::index(int pos) const
{
	if (pos == -1)
	{
		return head;
	}
	if (pos<0 || pos>size)
	{
		cout << "illegal operator" << endl;
		exit(1);
	}
	int i = 0;
	DLnode<T> *p = head->next;
	while (i < pos&&p != head)
	{
		p = p->next;
		i++;
	}
	return p;
}

template<class T>
inline void DCirlist<T>::insert(const T & item, int pos)
{
	DLnode<T> *p = index(pos-1);
	DLnode<T> *new_node = new DLnode<T>(item, NULL, NULL);
	new_node->prior = p;
	p->next->prior = new_node;
	new_node->next = p->next;
	p->next = new_node;
	size++;
}

template<class T>
inline T DCirlist<T>::del(int pos)
{
	if (size == 0)
	{
		cout << "list is empty" << endl;
		exit(1);
	}
	if (pos<0 || pos>size)
	{
		cout << "illegal operator" << endl;
		exit(1);
	}
	DLnode<T> *p = index(pos);
	p->prior->next = p->next;
	p->next->prior = p->prior;
	T data = p->data;
	delete p;
	size--;
	return data;
}

template<class T>
inline T DCirlist<T>::getdata(int pos) const
{
	DLnode<T> *p = index(pos);
	return p->data;
}

template<class T>
inline void DCirlist<T>::clearlist()
{
	DLnode<T> *p1, *p2;
	p1 = head->next;
	while (p1 != head)
	{
		p2 = p1;
		p1 = p1->next;
		delete p2;
	}
	size = 0;
}

template<class T>
inline DLnode<T>* DCirlist<T>::reset(int pos)
{
	if (pos == -1)
	{
		return head;
	}
	if (pos<0 || pos>size)
	{
		cout << "illegal operator" << endl;
		exit(1);
	}
	int i = 0;
	currPtr = head->next;
	while (i < pos&&currPtr != head)
	{
		currPtr = currPtr->next;
		i++;
	}
	return currPtr;
}

template<class T>
inline DLnode<T>* DCirlist<T>::next()
{
	if (currPtr!= NULL)
	{
		currPtr = currPtr->next;
	}
	return currPtr;	
}

template<class T>
inline DLnode<T>* DCirlist<T>::prior()
{
	if (currPtr != NULL)
	{
		currPtr = currPtr->prior;
	}
	return currPtr;
}

template<class T>
inline bool DCirlist<T>::EndOfList() const
{
	return (currPtr == head);
}

template<class T>
inline bool DCirlist<T>::nextEndoflist() const
{
	return (currPtr->next == head);
}

template<class T>
inline bool DCirlist<T>::PriorEndoflist() const
{
	return (currPtr->prior == head);
}

template<class T>
inline T DCirlist<T>::deleprior()
{//删除当前节点的前一节点
	DLnode<T> *p = currPtr->prior;
	currPtr->prior->next = currPtr->next;
	currPtr->next->prior = currPtr->prior;
	T data = currPtr->data;
	delete currPtr;
	size--;
	currPtr = p;
	return currPtr;
}

4.测试主函数

void test()
{
	DCirlist<int> list;
	for (int i = 0; i < 10; i++)
	{
		list.insert(i * 10, i);
	}
	cout << "list中元素的个数为：" << list.listsize() << endl;
	DLnode<int> *p = list.reset();
	while (!list.EndOfList())
	{
		cout << p->data << endl;
		p = list.next();
	}
	p = list.next();
	cout << list.del(1) << "已被删除" << endl;
	cout << "list中元素的个数为：" << list.listsize() << endl;
	while (!list.EndOfList())
	{
		cout << p->data << endl;
		p = list.next();
	}
	cout << list.getdata(1) << endl;
	cout << list.index(2)->data << endl;
}

int main()
{
	test();
	system("pause");
	return EXIT_SUCCESS;
}

输出结果如下：

The End

Read All

2/8

Welcome to Aoki's Blog!

指针，又见指针

指针，又见指针

一、指针简介

二、间接运算符

三、指针声明

四、使用指针在函数间通信

The End

顺序循环队列的实现

顺序循环队列的实现

写在前面

1.顺序队列的类定义

2.顺序队列类的实现

链式队列的实现

链式队列的实现

写在前面

1.链式队列节点类的定义和实现

2.链式队列类的定义

3.链式队列类的实现

4.测试主函数

The End

双向循环链表

双向循环链表

写在前面

1.节点类的定义和实现

2.双向循环链表类的定义

3.双向循环链表类的实现

4.测试主函数

The End