首页 > 代码库 > 基础数据结构 链表、栈、队列

基础数据结构 链表、栈、队列

数据结构是程序设计中一个非常重要的部分,基本的数据结构包括链表、栈和队列,当然高级一点的还有树、图等,实际上链表、栈和队列都是线性表,只是在操作和表示方式上有所不同,线性表用顺序结构表示就是顺序表,用链结构表示就是链表,如果对线性表的操作加以限制,只能有在表尾进行插入和删除元素,这就变成栈了,如果只能允许元素从表尾插入,表头删除,这就变成队列了。


链表

/*
 *	数据结构 链表
 *	链式结构
 */

#include <iostream>
using namespace std;

enum Status 
{
	ERROR = -1,
	OK = 0
};

typedef int ElemType;
//定义链表的节点
typedef struct LNode 
{
	ElemType data;
	LNode *next;
} LNode, *LinkList;


/*
 *	创建一个长度为size的单链表,并返回链表头结点
 *	从后先前不断插入新的元素,每次新元素都添加到头结点后面
 */
LinkList createList(int size)
{
	if (size <= 0)
		return NULL;

	//定义头节点
	LinkList list = new LNode[1];
	list->next = NULL;

	for (int i=size; i>=1; i--)
	{
		LNode *node = new LNode[1];
		cin>>node->data;
		node->next = list->next;
		list->next = node;
	}

	return list;
}

/*
 *	从链表 list 中取第 pos 个元素,并将元素值付给 elem
 */
Status getElem(LinkList list, int pos, ElemType &elem)
{
	if (! list)
	{
		return Status::ERROR;
	}

	LNode *p = list->next;
	int j = 1;

	while (p && j<pos)
	{
		p = p->next;
		j++;
	}
	//判断是否存在第 pos 个元素,或者 pos 值输入不合法(负值或0)
	if (! p || j > pos)
	{
		return Status::ERROR;
	}

	elem = p->data;
	return Status::OK;
}

/*
 *	将元素elem插入到链表list中的第pos个位置
 *	要想在第pos个位置插入元素,需要先找到第
 *	pos-1个位置
 */
Status insertList(LinkList list, int pos, ElemType elem)
{
	LNode *p = list;
	int j = 0;
	while (p && j<pos-1)
	{
		p = p->next;
		j++;
	}

	if (! p || j > pos-1)
	{
		return Status::ERROR;
	}

	LNode *node = new LNode[1];
	node->data = http://www.mamicode.com/elem;>

/*
 *	数据结构 栈
 *	顺序结构
 */

#include <iostream>
#include <cstdlib>
using namespace std;

#define STACK_INIT_SIZE 100
#define STACK_INCREMENT 10

enum Status
{
	ERROR = -1,
	OK = 0,
	TRUE = 1,
	FALSE = 2
};

typedef int ElemType;

typedef struct Stack 
{
	ElemType *top;//指向栈顶元素的上一个位置
	ElemType *base;//指向栈底元素
	int size;//栈空间的长度
} Stack;

/*
 *	初始化栈操作
 */
Status initStack(Stack* &stack)
{//此处的形参必须使用指针的引用,因为可能会改变指针本身的值,而不是其指向的对象的值
	if (! stack)
	{
		stack = (Stack*)malloc(sizeof(Stack));
	}
	stack->base = (ElemType*)malloc(STACK_INIT_SIZE * sizeof(ElemType));
	if (! stack->base)
	{
		return Status::ERROR;
	}

	stack->top = stack->base;
	stack->size = STACK_INIT_SIZE;

	return Status::OK;
}

/*
 *	获取栈顶元素
 */
Status getTop(Stack *stack, ElemType &elem)
{
	if (! stack || stack->base == stack->top)
	{
		return Status::ERROR;
	}

	elem = *(stack->top-1);
	return Status::OK;
}

/*
 * 压入新的元素到栈顶
 */
Status push(Stack *stack, ElemType elem)
{
	if (! stack) 
	{
		return Status::ERROR;
	}
	//先判断栈是否满
	if (stack->top - stack->base >= stack->size)
	{
		stack->base = (ElemType*)realloc(stack->base, (stack->size+STACK_INCREMENT)*sizeof(ElemType));
		if (! stack->base)
		{
			return Status::ERROR;
		}
		stack->top = stack->base + stack->size;
		stack->size += STACK_INCREMENT;
	}

	*stack->top = elem;
	stack->top++;

	return Status::OK;
}

/*
 *	判断栈是否为空
 */
Status isEmpty(Stack *stack)
{
	if (! stack || stack->base == stack->top)
	{
		return Status::TRUE;
	}

	return Status::FALSE;
}

/*
 *	弹出栈顶元素
 */
Status pop(Stack* stack, ElemType &elem)
{
	if (isEmpty(stack) == Status::TRUE)
	{
		return Status::ERROR;
	}

	stack->top--;
	elem = *stack->top;

	return Status::OK;
}

Status destroyStack(Stack *stack)
{
	if (! stack)
		return Status::OK;

	if (stack->base)
	{
		free(stack->base);
		stack->base = stack->top = NULL;
	}

	return Status::OK;
}

void printStack(Stack *stack, char *str = "")
{
	if (isEmpty(stack) == Status::TRUE)
	{
		return;
	}
	cout<<str<<endl;
	ElemType *p = stack->base;
	while (p != stack->top)
	{
		cout<<*p<<" ";
		p++;
	}
	cout<<endl;
}

队列

/*
 *	数据结构 队列
 *	链式结构
 */

#include <iostream>
using namespace std;

enum Status 
{
	ERROR = -1,
	OK = 0,
	TRUE = 1,
	FALSE = 2
};

typedef int ElemType;

typedef struct QNode 
{
	ElemType data;
	QNode* next;
} QNode;

typedef struct LinkQueue
{
	QNode* front;
	QNode* rear;
} LinkQueue;

/*
 *	初始化队列
 */
Status initQueue(LinkQueue* &queue)
{
	if (! queue)
	{
		queue = (LinkQueue*)malloc(sizeof(LinkQueue));
	}

	queue->front = queue->rear = (QNode*)malloc(sizeof(QNode));
	if (! queue->front)
	{
		return Status::ERROR;
	}

	queue->front->next = NULL;
	
	return Status::OK;
}

/*
 *	入队
 */
Status enQueue(LinkQueue* queue, ElemType elem)
{
	if (! queue)
	{
		return Status::ERROR;
	}

	QNode* node = (QNode*)malloc(sizeof(QNode));
	if (! node)
	{
		return Status::ERROR;
	}

	node->data = http://www.mamicode.com/elem;>
/*
 *	数据结构 队列 
 *	顺序结构,循环队列
 *	因为队列是从队头删除元素,从队尾插入元素
 *	在删除元素之后,不可能让队列中的所有元素都向前移动
 *	只能是将队头指针向后收缩一个位置,则前面空出了空间,为了使用这些空间
 *	就需要使用循环队列,将队头和队尾连接起来,这样真正的队头并不一定就是申请
 *	到的顺序空间的首地址,队尾也并不一定就是顺序空间的尾地址,所以在循环队列满了之后
 *	无法使用realloc重新分配新的空间使用,因为这样会打破原来的队列结构,新的队列空间可能
 *	会插入到队列的任意位置,对队列的头尾操作同样无法进行,所以只能给循环队列设置一个最大
 *	队列长度,无法动态分配,如果最大长度不确定,则使用链式队列较好
 */

#include <iostream>
using namespace std;

#define MAXSIZE 100

enum Status
{
	ERROR = -1,
	OK = 0,
	TRUE = 1,
	FALSE = 2
};

typedef int ElemType;

typedef struct CircleQueue
{
	ElemType* base;
	int front;
	int rear;
} CircleQueue;

/*
 *	初始化队列
 */
Status initQueue(CircleQueue* &queue)
{
	if (! queue)
	{
		queue = (CircleQueue*)malloc(sizeof(CircleQueue));
	}
	if (! queue)
		return Status::ERROR;

	queue->base = (ElemType*)malloc(MAXSIZE * sizeof(ElemType));
	if (! queue->base)
	{
		return Status::ERROR;
	}

	queue->front = queue->rear = 0;

	return Status::OK;
}

/*
 *	获取队列的长度
 */
int getLength(CircleQueue* queue)
{
	if (! queue)
	{
		return 0;
	}

	return (queue->rear - queue->front + MAXSIZE) % MAXSIZE;
}

/*
 *	入队
 */
Status enQueue(CircleQueue* queue, ElemType elem)
{//预留一个空间不放元素,以区别队列满和空的标志
	if (! queue || (queue->rear+1)%MAXSIZE == queue->front)
	{
		return Status::ERROR;
	}

	queue->base[queue->rear] = elem;
	queue->rear = (queue->rear + 1) % MAXSIZE;

	return Status::OK;
}

/*
 *	判断队列是否为空
 */
Status isEmpty(CircleQueue* queue)
{
	if (! queue || ! queue->base || queue->front == queue->rear)
	{
		return Status::TRUE;
	}
	return Status::FALSE;
}

/*
 *	出队
 */
Status deQueue(CircleQueue* queue, ElemType &elem)
{
	if (isEmpty(queue) == Status::TRUE)
	{
		return Status::ERROR;
	}

	elem = queue->base[queue->front];
	queue->front = (queue->front + 1) % MAXSIZE;

	return Status::OK;
}

/*
 *	销毁队列
 */
Status destroyQueue(CircleQueue* queue)
{
	if (! queue)
	{
		return Status::OK;
	}

	if (queue->base)
	{
		free(queue->base);
		queue->base = NULL;
	}

	return Status::OK;
}

void printQueue(CircleQueue* queue, char* str)
{
	if (isEmpty(queue) == Status::TRUE)
		return;

	cout<<str<<endl;

	int pos = queue->front;
	while (pos != queue->rear)
	{
		cout<<queue->base[pos]<<" ";
		pos = (pos+1)%MAXSIZE;
	}
	cout<<endl;
}



基础数据结构 链表、栈、队列