c语言中的数据结构类型有哪些（数据结构-队列的顺序存储结构及基本操作）

c语言中的数据结构类型有哪些（数据结构-队列的顺序存储结构及基本操作）struct SeqQueue { /*顺序队列的类型定义*/ ElemType data[MaxSize]; /*用一维数组存储队列中的元素*/ int front rear; /*队头、队尾指针*/ }; struct SeqQueue *sq; /*sq是指向顺序队列类型的指针变量*/ （3）顺序队列的结构体类型 用长度为MaxSize的一维数组存储队列元素 整型变量front指示队头元素的位置(队头指针） 整型变量rear指示队尾元素的下一个位置（队尾指针）

1.队列的顺序存储结构

（1） 顺序队列

用顺存储结构存储的队列称为顺序队列。

（2） 队列的数组方式存储

用长度为MaxSize的一维数组存储队列元素

整型变量front指示队头元素的位置(队头指针）

整型变量rear指示队尾元素的下一个位置（队尾指针）

（3）顺序队列的结构体类型

struct SeqQueue { /*顺序队列的类型定义*/ ElemType data[MaxSize]; /*用一维数组存储队列中的元素*/ int front rear; /*队头、队尾指针*/ };

struct SeqQueue *sq; /*sq是指向顺序队列类型的指针变量*/

其中ElemType为队列中元素的数据类型，可根据需要指定其具体的类型，如整型int ，字符型char等。data是一维数组，用于存储队列中所有的数据元素，MaxSize为一维数组的长度，即顺序队列的最大存储容量 *sq是指向顺序队列的指针变量。

2.顺序队列的基本操作

和顺序栈一样，顺序队列也有队空、队满和非空非满这三种状态。由于队头指针和队尾指针所指元素的规定不同，表示方法也不同。因此约定

初始化: 令 rear=front=0； 队满：rear==MaxSise为真 队空：rear==front 为真

假设队列的最大存储空间MaxSize=5，则顺序队列出队和入队时，队头和队尾指针的变化情况如图3-6所示。

顺序队列操作示意图

（1）入队操作

入队是将新元素插入到rear所指的位置，然后再将rear的值加1。

算法要点：

① 检查队列是否已满，若队满，则进行“溢出”错误处理；

② 否则，将元素值x赋给队尾指针所指向的数据单元；

③ 将队尾指针加1。

顺序队列入队算法

void InQueue(struct SeqQueue * sq int x) { if(sq->rear==MaxSize) { /*判队列是否已满*/ printf("队列已满\n"); exit(1); /*入队失败，退出函数运行*/ } sq->data[sq->rear]=x; /*数据送给队尾指针所指单元*/ sq->rear ; /*将队尾指针加1*/ }

图3-6(b)是插入两个元素的队列状况。图3-6(c)队列已满，此时尾指针已超越存储空间的上界，如果再进行入队操作，就会产生“上溢”错误。

（2）出队操作

出队是删除front所指位置的元素后，再将front的值加1并返回被删元素。

算法要点：

① 检查队列是否为空队列，若队空，则进行“下溢”错误处理；

② 将队头指针加1；

③ 返回front所指位置的元素。

顺序队列出队算法

ElemType OutQueue(struct SeqQueue *sq) { if (sq->rear==sq->front) { /*判断队是否为空*/ printf("队列已空，不能进行出队操作\n"); exit(1); /*出队失败，退出函数运行*/ } sq->front ; return sq->data[sq->front-1]; /*返回front所指位置的元素*/ }

图3-6(d)是删除A元素的队列状况，(e)是继续删除B元素的队列状况。每删除一个元素，front指针加1（后移），以保证front始终指向新的队头元素。在图3-6(d)、(e)状态下，如果有新元素请求入队，此时队列的实际可用空间虽然没有占满，但尾指针已超越存储空间的上界，因此不能进行入队操作。但事实上队列中还有空位置 也就是说，队列的存储空间并没有满，但队列却发生了“上溢”错误，称这种现象为“假上溢”。

在图3-6(f)所示状态下，队列已空，队列的头指针和尾指针均已超越存储空间的上界，此时如果仍要进行出队操作，就会产生“下溢”错误。

从图3-6可以看出，在非空队列里，front指针始终指向队头元素，而rear指针始终指向队尾元素的下一位置。当front指针和rear指针值相等时，队列为空。