17社

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

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


    链表

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

#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];
		cinnode-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  jpos)
	{
		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  jpos-1)
	{
		p = p-next;
		j++;
	}

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

	LNode *node = new LNode[1];
	node-data = elem;
	node-next = p-next;
	p-next = node;

	return Status::OK;
}

/*
 *	从链表list中删除第pos个元素，并将该元素值赋给elem
 *	首先找到第pos-1个元素
 */
Status deleteList(LinkList list, int pos, ElemType elem)
{
	LNode *p = list;
	int j = 0;
	//找到第 pos-1 个元素
	while (p  jpos-1)
	{
		p = p-next;
		j++;
	}

	if (! p || jpos-1 || ! p-next)
	{
		return Status::ERROR;
	}

	LNode *q = p-next;
	elem = q-data;
	p-next = q-next;
	delete q;

	return Status::OK;
}

/*
 *	合并链表list1和list2，并返回合并后的链表头结点
 *	list1和list2均是按值非递减排列
 */
LinkList mergeList(LinkList list1, LinkList list2)
{
	LinkList list;

	if (! list1 || ! list2)
	{
		list = list2==NULL ? list1 : list2;
		return list;
	}

	list = list1;
	
	LinkList p = list, p1 = list1-next, p2 = list2-next;
	while (p1  p2)
	{
		if (p1-data = p2-data)
		{
			p-next = p1;
			p1 = p1-next;
		} else {
			p-next = p2;
			p2 = p2-next;
		}
		p = p-next;
	}

	p-next = p1 ? p1 : p2;
	delete list2;

	return list;
}

void printList(LinkList list, char *str="")
{
	coutstrendl;

	if (list == NULL)
		return;

	LNode *p = list-next;
	while (p)
	{
		coutp-data" ";
		p = p-next;
	}
	coutendl;
}

void destroyList(LinkList list)
{
	if (! list)
	{
		return;
	}

	while (list-next)
	{
		LNode *p = list-next;
		list-next = p-next;
		delete p;
	}

	delete list;
}

    栈 

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

#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;
	}
	coutstrendl;
	ElemType *p = stack-base;
	while (p != stack-top)
	{
		cout*p" ";
		p++;
	}
	coutendl;
}

    队列 

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

#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 = elem;
	node-next = NULL;
	queue-rear-next = node;
	queue-rear = node;

	return Status::OK;
}

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

	return Status::FALSE;
}

/*
 *	出队
 */
Status deQueue(LinkQueue* queue, ElemType elem)
{
	if (isEmpty(queue) == Status::TRUE)
	{
		return Status::ERROR;
	}
	QNode* p = queue-front-next;
	elem = p-data;
	queue-front-next = p-next;
	if (queue-rear == p)
		queue-rear = queue-front;
	free(p);

	return Status::OK;
}

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

	while (queue-front)
	{
		queue-rear = queue-front-next;
		free(queue-front);
		queue-front = queue-rear;
	}

	return Status::OK;
}

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

	coutstrendl;

	QNode* p = queue-front-next;
	while (p)
	{
		coutp-data" ";
		p = p-next;
	}
	coutendl;
}


    由于队列是从队头删除元素，从队尾插入元素，在删除元素之后，不可能让队列中的所有元素都向前移动，只能是将队头指针向后收缩一个位置，则前面空出了空间，为了使用这些空间，就需要使用循环队列，将队头和队尾连接起来，这样真正的队头并不一定就是申请到的顺序空间的首地址，队尾也并不一定就是顺序空间的尾地址，所以在循环队列满了之后无法使用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;

	coutstrendl;

	int pos = queue-front;
	while (pos != queue-rear)
	{
		coutqueue-base[pos]" ";
		pos = (pos+1)%MAXSIZE;
	}
	coutendl;
}



    技术数据结构队列
    最新回复(0)
    /jishuqaid6MLZ_2BrtdR0Kqcx5sKqvBPmBawlAcHdN_2FCg_3D_3D4858381
    8 简首页