以纯C实现几个基本的数据结构(2)

开场

前篇算是开宗明义,此篇接续第一部分的单向队列数据结构。

队列

1、设计

队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列中没有元素时,称为空队列。队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队,从队列中删除一个队列元素称为出队。因为队列只允许在一端插入,在另一端删除,所以只有最早进入队列的元素才能最先从队列中删除,故队列又称为先进先出(FIFO—first in first out)线性表。

从上可知,队列首先是一个线性表,也就是说其数据元素是按照顺序存放在一个连续的内存空间内的。然后遵顼先入先出原则,所以删除和添加的操作,只能从队尾和队头进行操作。

所以我们这么设计(和前篇的链表不一样,这里的设计是完全遵照基本的队列结构来的,所以算是通用的设计原理):

  • 队列的数据节点
    1. 一个大小固定(100)的数组空间。(因为是顺序表,所以用数组来模拟)
    2. 一个头指针和尾指针,但是为了方便操作(相对于数组),所以打算使用下标来获取数据,所以头指针和尾指针其实只是int类型的数字而已。(另外多一句嘴,下标其实只是指针的语法糖,arr[i] 就是 *(arr + i) 罢了)
    3. 队列中元素的数量,这个其实是可以通过遍历获得的,但是我倾向与将一些基本的属性早早地确定下来。尤其是在如今硬件不再昂贵地现在。
    4. 最大数据空间。
struct Queue {
	int data[100];
	int head;
	int tail;
	int count;
	int maxLength;
};
typedef struct Queue t_Queue;
  • 对队列的基本操作
    1. 初始化队列
    2. 增加一个元素
    3. 删除一个元素
    4. 判断是否为空队列
    5. 获取数量
    6. 按照位置查找
void Q_InitQueue(t_Queue *queue);
int Q_AddItem(t_Queue *queue, int item);
int Q_IsEmpty(const t_Queue queue);
int Q_DeleteItem(t_Queue *queue);
int Q_Count(const t_Queue queue);
int Q_IndexOf(const t_Queue queue, int item);
void Q_PrintQueue(const t_Queue queue);

因为队列相对来说比较简单,所以就不再分开来阐述了,也不对每一个函数进行讲解,因为大多就是数组的操作而已。不过说回来,如果按照上一篇节点+队列本身这种方式来设计的话,那样一定会更加有意思。这我会留到双向队列里去实现。

2、实现代码

#define OK 1
#define ERROR -1
#define FAIL -1
#define YES 1
#define NO -1
#define DMAX 100

void Q_InitQueue(t_Queue *queue) {
	queue->head = 0;
	queue->tail = 0;
	queue->count = 0;
	queue->maxLength = DMAX;
}

int Q_IsEmpty(const t_Queue queue) {
	if (queue.head == queue.tail) {
		return YES;
	}
	return NO;
}

int Q_AddItem(t_Queue *queue, int item) {
	if (queue->count == queue->maxLength || queue->tail == queue->maxLength) {
		return FAIL;
	}
	queue->data[queue->tail] = item;
	queue->tail++;
	queue->count++;
	return OK;
}

int Q_DeleteItem(t_Queue *queue) {
	if (queue->head == queue->tail || queue->count == 0) {
		return FAIL;
	}
	queue->head++;
	queue->count--;
	return OK;
}

int Q_Count(const t_Queue queue) {
	return queue.count;
}

int Q_IndexOf(const t_Queue queue, int item) {
	for (int i = queue.head; i < queue.tail; i++) {
		if (queue.data[i] == item) {
			return i - queue.head;
		}
	}
	return NO;
}

void Q_PrintQueue(const t_Queue queue) {
	if (queue.head == queue.tail) {
		printf("this queue is empty.\n");
		return;
	}
	for (int i = queue.head; i < queue.tail; i++) {
		printf("%d\t", queue.data[i]);
	}
	printf("\r\n");
}

虽然不想这么直接贴代码上来,但是其实也没什么好讲的。

3、测试

t_Queue queue;
Q_InitQueue(&queue);
Q_AddItem(&queue, 12);
Q_AddItem(&queue, 6);
Q_AddItem(&queue, 8);
Q_AddItem(&queue, 0);
Q_AddItem(&queue, 9);
Q_AddItem(&queue, -9);
Q_AddItem(&queue, 1023);
Q_AddItem(&queue, 65);
Q_AddItem(&queue, 7);
Q_PrintQueue(queue);

Q_DeleteItem(&queue);
Q_DeleteItem(&queue);
Q_PrintQueue(queue);

int index = Q_IndexOf(queue, 1);
printf("%d\n", index);
index = Q_IndexOf(queue, 65);
printf("%d\n", index);
index = Q_IndexOf(queue, 7);
printf("%d\n", index);

printf("The count is:%d\n", Q_Count(queue));
return 0;

测试结果如下:
以纯C实现几个基本的数据结构(2)

4、小结

下一章我将实现顺序表和堆栈(栈,stack),因为顺序表完全类似于数组,所以我会使用节点+顺序表这种方式来模拟整个数组的操作方式。

;