기본 데이터 구조 링크, 스 택, 대기 열

데이터 구 조 는 프로 그래 밍 에서 매우 중요 한 부분 이다. 기본 적 인 데이터 구 조 는 링크, 스 택 과 대기 열 을 포함한다. 물론 고 급 스 러 운 것 은 나무, 그림 등 도 있다. 실제 적 으로 링크, 스 택 과 대기 열 은 모두 선형 표 이 고 조작 과 표현 방식 이 다 를 뿐이다. 선형 표 는 순서 구조 로 표시 하면 순서 표 이 고 체인 구조 로 표시 하면 링크 이다.선형 표 의 조작 을 제한 하면 표 끝 에 요 소 를 삽입 하고 삭제 할 수 밖 에 없다. 이것 은 스 택 이 된다. 만약 에 요소 가 표 끝 에서 삽입 되 고 표 끝 에서 삭제 할 수 밖 에 없다 면 이것 은 대기 열 이 된다.
체인 테이블

/*
 *	       
 *	    
 */

#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 = 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 && j<pos-1)
	{
		p = p->next;
		j++;
	}

	if (! p || j>pos-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="")
{
	cout<<str<<endl;

	if (list == NULL)
		return;

	LNode *p = list->next;
	while (p)
	{
		cout<<p->data<<" ";
		p = p->next;
	}
	cout<<endl;
}

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;
	}
	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 = 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;
	}

	cout<<str<<endl;

	QNode* p = queue->front->next;
	while (p)
	{
		cout<<p->data<<" ";
		p = p->next;
	}
	cout<<endl;
}

대기 열 은 팀 머리 에서 요 소 를 삭제 하기 때문에 팀 꼬리 에서 요 소 를 삽입 합 니 다. 요 소 를 삭제 한 후에 대기 열 에 있 는 모든 요 소 를 앞으로 이동 시 킬 수 없습니다. 팀 머리 지침 을 뒤로 한 위치 로 줄 일 수 밖 에 없 기 때문에 앞 에 공간 이 비어 있 습 니 다. 이 공간 을 사용 하기 위해 서 는 순환 대기 열 을 사용 하여 팀 머리 와 팀 꼬리 를 연결 해 야 합 니 다.이러한 진정한 팀 헤드 는 반드시 신청 한 순서 공간의 첫 번 째 주소 가 아 닙 니 다. 팀 의 끝 도 반드시 순서 공간의 끝 주소 가 아 닙 니 다. 그래서 순환 대기 열 이 가득 찬 후에 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;
}