常用資料結構

前言：常用的資料結構主要包括數組、連結清單、串、棧、隊列、樹、圖

目錄

一、數組

二、連結清單

三、棧

四、隊列

五、樹

六、圖

總結

一、數組

• 數組裡的資料是按順序排列的，每一個元素都有一個下标，标明它在數組中的位置。
• 隻要知道了一個元素的記憶體位址，就能算出數組所有元素的記憶體位址。數組中元素的查找很友善。
• 想要在數組中插入一個資料，先要找到要插入的位置，然後将該位置的元素向後移一個位置，因為後面的位置也是占着的，是以後面所有的元素都要依次向後移一個位置，然後再将資料插入進去。
• 資料的删除也是一樣的，删除資料後，後面的所有資料要依次向前移動一個位置。
• 數組便于查找資料，添加和删除不太友善。

代碼實作：

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組成。其中，為了與樹形結構加以差別，在圖結構中常常将結點稱為頂點，邊是頂點的有序偶對，若兩個頂點之間存在一條邊，就表示這兩個頂點具有相鄰關系。

按照頂點指向的方向可分為無向圖和有向圖：

圖是一種比較複雜的資料結構，在存儲資料上有着比較複雜和高效的算法，分别有鄰接矩陣 、鄰接表、十字連結清單、鄰接多重表、邊集數組等存儲結構，這裡不做展開，讀者有興趣可以自己學習深入。

代碼實作：

總結

以上簡單介紹了常用的資料結構，其中包括數組、連結清單、棧、隊列、樹、圖等等，可以參考《大話資料結構》這本書學習，比較容易了解。