常用数据结构

前言：常用的数据结构主要包括数组、链表、串、栈、队列、树、图

目录

一、数组

二、链表

三、栈

四、队列

五、树

六、图

总结

一、数组

• 数组里的数据是按顺序排列的，每一个元素都有一个下标，标明它在数组中的位置。
• 只要知道了一个元素的内存地址，就能算出数组所有元素的内存地址。数组中元素的查找很方便。
• 想要在数组中插入一个数据，先要找到要插入的位置，然后将该位置的元素向后移一个位置，因为后面的位置也是占着的，所以后面所有的元素都要依次向后移一个位置，然后再将数据插入进去。
• 数据的删除也是一样的，删除数据后，后面的所有数据要依次向前移动一个位置。
• 数组便于查找数据，添加和删除不太方便。

代码实现：

int data[100];
int *arr = (int *)malloc(sizeof(int) * 100);
           

二、链表

• 链表中的数据呈线性排列。
• 每个数据都有一个指针，指向下一个数据的内存地址。
• 如果要访问第9个数据，要从第1个数据一个一个的查到第9个数据，顺着指针顺序访问。
• 如果要添加一个数据到某两个数据中间，比如需要将数据C插到AB之间，只需要将A的指针指到C，将C的指针指到B即可。
• 如果要将C从AB之间删除，只需要将原来A指到C的指针，改为从A指到B即可。
• 链表的添加和删除都很容易，但是不好查找。

代码实现：参考：https://blog.csdn.net/qq_37158051/article/details/108966220

三、栈

• 栈的数据结构类似于往刚好一本书大小的箱子里放书，我们永远只能拿到最后放上去的最上面的那本书。
•  如果想拿到最底下的那本书，必须将上面所有的书都先拿出来。
• 栈的结构可以总结成：后入先出。
• 栈中数据的添加和删除只能在一端进行，访问数据也只能访问到顶端的数据。

代码实现 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


#define ALLOC_SIZE (500)

typedef int KEY_TYPE;

typedef struct _stack
{
	KEY_TYPE *base;
	int top;
	int stack_size;
} STACK;

int init_stack(STACK *s)
{
	if (NULL == s)
	{
		return -1;
	}
	
	s->base = (KEY_TYPE *)calloc(ALLOC_SIZE, sizeof(KEY_TYPE));
	if (NULL == s->base)
	{
		return -2;
	}
	memset(s->base, 0, sizeof(KEY_TYPE) * ALLOC_SIZE);
	
	s->top = 0;
	s->stack_size = ALLOC_SIZE;

	return 0;
}

int destroy_stack(STACK *s)
{
	if (NULL == s)
	{
		return -1;
	}
	
	free(s->base);
	s->base = NULL;
	s->stack_size = 0;
	s->top = 0;

	return 0;
}

int push_stack(STACK *s, KEY_TYPE data)
{
	if (NULL == s)
	{
		return -1;
	}

	if (s->top >= s->stack_size)
	{
		s->base = realloc(s->base, (s->stack_size + ALLOC_SIZE) * sizeof(KEY_TYPE));
		if (NULL == s->base)
		{
			return -2;
		}

		s->stack_size += ALLOC_SIZE;
	}

	s->base[s->top] = data;
	s->top++;

	return 0;
}

int pop_stack(STACK *s, KEY_TYPE *data)
{
	if (NULL == s)
	{
		return -1;
	}

	*data = s->base[--s->top];

	return 0;
}

int is_empty_stack(STACK *s)
{
	if (NULL == s)
	{
		return -1;
	}
	
	return s->top == 0 ? 1 : 0; 
}

int size_stack(STACK *s)
{
	if (NULL == s)
	{
		return -1;
	}
	
	return s->top;
}


int main(int argc, char **argv)
{
	STACK s;

	init_stack(&s);

	int i = 0;
	for (i = 0; i < 1000; i++)
	{
		push_stack(&s, i + 1);
	}

	while (0 == is_empty_stack(&s))
	{
		int data;

		pop_stack(&s, &data);
		printf("%d\n", data);
	}

	destroy_stack(&s);
}

           

四、队列

• 队列的数据正好和栈相反，它是先入先出。
• 有点类似于排队打饭，可以把打饭师傅理解为访问数据的人，先排入队列的人先打到饭，打饭师傅永远也只能给排在最前面的人打饭。

代码实现：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>


#define ALLOC_SIZE 512

typedef int KEY_TYPE;

typedef struct _queue_node
{
	struct _queue_node *next;
	KEY_TYPE key;
} QUEUE_NODE;

typedef struct _queue
{
	QUEUE_NODE *front;
	QUEUE_NODE *rear;

	int queue_size;
} QUEUE;

int init_queue(QUEUE *q)
{
	if (NULL == q)
	{
		return -1;
	}
	
	q->front = q->rear = NULL;
	q->queue_size = 0;

	return 0;
}

int destory_queue(QUEUE *q)
{
	QUEUE_NODE *iter;
	QUEUE_NODE *next;

	if (NULL == q)
	{
		return -1;
	}

	iter = q->front;
	while (NULL != iter)
	{
		next = iter->next;
		
		free(iter);
		iter = next;
	}

	return 0;
}

int push_queue(QUEUE *q, KEY_TYPE key)
{
	if (NULL == q)
	{
		return -1;
	}

	QUEUE_NODE *node = (QUEUE_NODE*)calloc(1, sizeof(QUEUE_NODE));
	if (NULL == node)
	{
		return -2;
	}
	memset(node, 0, sizeof(QUEUE_NODE));
	
	node->key = key;
	node->next = NULL;
	
	if (NULL != q->rear)
	{
		q->rear->next = node;
		q->rear = node;
	}
	else
	{
		q->front = q->rear = node;
	}
	
	q->queue_size ++;

	return 0;
}

int pop_queue(QUEUE *q, KEY_TYPE *key)
{
	if (NULL == q)
	{
		return -1;
	}

	if (NULL == q->front)
	{
		return -2;
	}

	if (q->front == q->rear)
	{
		*key = q->front->key;

		free(q->front);
		q->front = q->rear = NULL;
	}
	else
	{
		QUEUE_NODE *next = q->front->next;

		*key = q->front->key;
		free(q->front);

		q->front = next;
	}
	q->queue_size --;

	return 0;
}

int is_empty_queue(QUEUE *q)
{
	if (NULL == q)
	{
		return -1;
	}

	return q->rear == NULL ? 1 : 0;

	return 0;
}

int size_queue(QUEUE *q)
{
	if (NULL == q)
	{
		return -1;
	}
	
	return q->queue_size;
}

int main()
{
	QUEUE q;

	init_queue(&q);

	int i = 0;
	for (i = 0; i < 1000; i++)
	{
		push_queue(&q, i+1);
	}

	while (0 == is_empty_queue(&q))
	{
		KEY_TYPE key;
		pop_queue(&q, &key);

		printf("%d\n", key);
	}

	destory_queue(&q);
}
           

五、树

树是一种数据结构，它是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做 “树” 是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：

每个节点有零个或多个子节点；

没有父节点的节点称为根节点；

每一个非根节点有且只有一个父节点；

除了根节点外，每个子节点可以分为多个不相交的子树；

在日常的应用中，我们讨论和用的更多的是树的其中一种结构，就是二叉树。

如图所示：

代码实现：

六、图

图是由结点的有穷集合V和边的集合E组成。其中，为了与树形结构加以区别，在图结构中常常将结点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。

按照顶点指向的方向可分为无向图和有向图：

图是一种比较复杂的数据结构，在存储数据上有着比较复杂和高效的算法，分别有邻接矩阵 、邻接表、十字链表、邻接多重表、边集数组等存储结构，这里不做展开，读者有兴趣可以自己学习深入。

代码实现：

总结

以上简单介绍了常用的数据结构，其中包括数组、链表、栈、队列、树、图等等，可以参考《大话数据结构》这本书学习，比较容易理解。