链式队列的实现

#include<stdio.h>
#include<stdlib.h>
typedef struct Node{
	int data;
	struct Node*next;
}NODE,*PNODE;
typedef struct{
	PNODE front;
	PNODE rear;
	int len;
}Queue;
void InitQueue(Queue &queue);
void DestroyQueue(Queue &queue);
void ClearQueue(Queue &queue);
bool QueueEmpty(Queue &queue);
int QueueLength(Queue &queue);
bool GetHead(Queue &queue,int &e);
bool EnQueue(Queue &queue,int e);
bool DeQueue(Queue &queue,int &e);
bool QueueTraverse(Queue &queue);
int main()
{
	Queue queue;
	int e;
	/*
	InitQueue(queue);
	EnQueue(queue,1);
	EnQueue(queue,2);
	EnQueue(queue,3);
	EnQueue(queue,4);
	EnQueue(queue,5);
	QueueTraverse(queue);
	printf("%d\n",queue.len);
	DeQueue(queue,e);
	QueueTraverse(queue);
	printf("%d\n",queue.len);
	DestroyQueue(queue);
	system("pause");
	*/
	return 0;
}
void InitQueue(Queue &queue)
{
	queue.front=queue.rear=(PNODE)malloc(sizeof(NODE));
	if(!queue.front) exit(-1);
	queue.front->next=NULL;
	queue.len=0;
	return;
}
void DestroyQueue(Queue &queue)
{
	while(queue.front)
	{
		queue.rear=queue.front->next;
		free(queue.front);
		queue.front=queue.rear;
	}
	queue.len=0;
	return;
}
void ClearQueue(Queue &queue)
{
	PNODE p=queue.front->next,q;
	if(QueueEmpty(queue))
		return;
	while(p)
	{
		q=p;
		p=p->next;
		free(q);
	}
	queue.front->next=NULL;
	queue.rear=queue.front;
	queue.len=0;
	return;
}
bool QueueEmpty(Queue &queue)
{
	if(queue.len==0)
		return true;
	else
		return false;
}
int QueueLength(Queue &queue)
{
	return queue.len;
}
bool GetHead(Queue &queue,int &e)//获取首节点的值
{
	if(queue.len==0)
		return false;
	e=queue.front->next->data;
	return true;
}
bool EnQueue(Queue &queue,int e)
{
	PNODE p=(PNODE)malloc(sizeof(NODE));
	if(!p)
		return false;
	p->data=e;
	queue.rear->next=p;
	p->next=NULL;
	queue.rear=p;
	(queue.len)++;
	return true;
}
bool DeQueue(Queue &queue,int &e)
{
	if(queue.len==0)
		return false;
	PNODE p=queue.front->next;
	e=p->data;
	queue.front->next=p->next;
	if(queue.rear==p)
		queue.rear=queue.front;
	(queue.len)--;
	return true;
}
bool QueueTraverse(Queue &queue)
{
	if(queue.len==0)
		return false;
	PNODE p=queue.front->next;
	while(p)
	{
		printf("%d ",p->data);
		p=p->next;
	}
	printf("\n");
	return true;
}

静态链表的实现

老姐结婚了,于是国庆只好挤车回家。。在回来的路上一直在构思静态链表的实现。严蔚敏的书上只是简单的提了一下,写了free和malloc函数,但是没有一个完整的静态链表程序,遂决定完成之。。写的挺顺利,难得的是调试过程相当脆。。
具体程序如下,因为调试比较顺利,没有做很多调试,出现错误,请读者留言指正。以后还会加入更多操作。各位中秋快乐!

(二叉)树笔记

1.二叉树分类:
(1)一般二叉树
(2)满二叉树:在不增加树的层数的前提下不能再添加一个节点的二叉树
完全二叉树:如果只是删除满二叉树最底层最右边的连续若干个节点,这样形成的树是完全二叉树。
完全二叉树包括满二叉树
2.二叉树的存储:
(1)连续存储
必须转化为完全二叉树,否则无法还原原来的树
缺点:耗内存
优点:可以快速找到指定编号节点的父节点和子节点
(2)链式存储
3,一般树的存储:
(1)双亲表示法:求父节点方便
(2)孩子表示法:求子节点方便
(3)双亲孩子表示法:求父节点和子节点都比较方便
(4)二叉树表示法:
一般树转成二叉树方法:
<1>使每个节点的左指针指向它的第一个孩子
<2>右指针指向它的右边相邻的兄弟
4.森林的存储:先转化为二叉树再存储
转化方法同上(树的根节点之间看成兄弟关系)
5.二叉树的操作:
遍历:
(1)前序遍历
先访问根节点
再先序遍历左子树
再先序遍历右子树

静态队列的实现

1.静态队列一般必须是循环的。显然
2.循环队列需要两个参数确定。front、rear
3.队首删除元素,队尾泽插入元素。
4.两个参数在不同场合的不同含义:
(1)队列初始化:front=rear=0
(2)队列非空:front指向第一个元素,rear指向最后一个元素的下一个元素
(3)队列空:front=rear
5.出队伪算法:
a[rear]=val
rear=(rear+1)%数组长度
6.入队伪算法:
front=(front+1)%数组长度
7.如何判满:
少用一个元素法:
(rear+1)%数组长度=front
8.下面是具体的代码,其实是比较简单的: