C语言数据结构栈与队列 C语言编程数据结构栈与队列的全面讲解示例教程(IT技术) | 您所在的位置:网站首页 › c语言队列库 › C语言数据结构栈与队列 C语言编程数据结构栈与队列的全面讲解示例教程(IT技术) |
想了解C语言编程数据结构栈与队列的全面讲解示例教程的相关内容吗,高邮吴少在本文为您仔细讲解C语言数据结构栈与队列的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:C语言编程教程,C语言数据结构栈与队列,下面大家一起来学习吧。
一、栈的表示和实现
1栈的概念和结构
栈:一种特殊的线性表(逻辑上数据是连着放的),其只允许在固定的一端进行插入和删除操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵循后进先出的原则。 压栈:栈的插入操作叫作进栈/压线/入线,入数据在栈顶。 出栈:栈的删除操作叫做出栈。出数据也在栈顶。 (图片来自比特就业课) 先入后出就类似与你装手枪弹夹,你先放入的子弹会在弹夹底部,最后放入的子弹是在弹夹顶部,你开手枪是先打出弹夹顶端的子弹。 我们这里先定义一个栈的类型: typedef int STDataType;//方便将来如果需要其他类型的数据,可以直接修改int的类型 typedef struct Stack { STDataType*a;//栈底指针 int top;//栈顶标号 int capacity;//容量 }ST;本文介绍以顺序表(数组)实现栈,由此,所谓的入栈压栈也不过是顺序表的尾插尾删,如果读者想以链表实现也是可以的,方法不唯一。 2栈的初始化关于栈的初始化:我们这里以容量大小4的栈为例,刚开始因为栈里没有数据我们用top=0标记,需要注意的是:传过来的栈底指针不能为空,开辟空间时万一没有开辟成功返回一个空指针也要丢弃。 #include #include//malloc函数头文件 void StackInit(ST*ps)//栈初始化 { assert(ps);//防止传过来的指针是空指针 ps->a = (STDataType)malloc(sizeof(STDataType) * 4);//malloc开辟一块空间出来,由STDataType类型进行管理 //malloc,及后文出现的realloc、free函数详情见笔者动态内存管理文章 if (ps->a == NULL) { printf("realloc fail\n"); exit(-1);//终止程序 } ps->capacity=4; //这里以开辟4个数据容量大小的栈为例,你也可以写其他数字 //如果压栈的时候内存不够,可以在后面提到的压栈函数里面进行扩容 ps->top = 0;//刚开始栈里没有值时,用top=0标记,后续每放入一个top++ //关于top详细用法请往下看1.3压栈部分 } 3压栈(栈顶插入一个数据)如上图,我们现在开辟了一块空间,a和top都在栈顶,我们往里面入一个数据1 1进入栈之后,1就是栈顶元素了,那如果我想继续入栈,就是要在top的位置放入一个数据让新放入的数据成为新的栈顶元素,然后以此类推,每次入一个元素,top++,top不是表示栈顶元素位置,而是栈顶元素下一个位置。 出栈非常简单,我们以下图为例: 图中我们栈里已经存放了4个数据1、2、3、4,那我们现在要进行出栈操作,也就是删除4怎么办?直接top–即可 到这里肯定会有小伙伴有疑问,凭什么你top–一下就是出栈了,你4都没删除啊?解释如下:我们在1.3压栈部分就说过“top不是表示栈顶元素位置,而是栈顶元素下一个位置”,那现在我top在4这里,说明3才是真正的栈顶元素,4已经不在栈的管辖范围内了。 void StackPop(ST*ps)//栈顶删除数据(出栈) { assert(ps); assert(ps->top > 0);//栈空了,调用Pop,直接中止程序报错 ps->top--; }关于ps->top > 0,是这样的:假设你原先栈里没有有一个元素 你top–就是往下访问未知的领域了,这是非常严重的问题,所以我们这里用assert断言一下,防止栈里什么元素也没有让top标记到了未知领域。(再次强调一下:top不是表示栈顶元素位置,而是栈顶元素下一个位置) 5取栈顶元素 STDataType StackTop(ST*ps)//取栈顶数据 { assert(ps); assert(ps->top > 0);//栈空了,调StackTop,直接中止程序报错 return ps->a[ps->top - 1];//top是栈顶元素下一个位置,top-1是栈顶元素 //a[m]==*(a+m) }这里的思路和1.4几乎一样,也要防止栈里什么也没有的情况,然后正常返回栈顶元素即可,因为top是栈顶元素下一个位置,top-1是栈顶元素,然后你正常写就行,这里的 a[ps->top - 1]你也可以写成*(a+(ps->top - 1)),这个写法读者可参加笔者以前的指针文章,这里不再赘述。 6取栈顶元素 int StackSize(ST*ps)//栈的数据个数 { assert(ps); return ps->top; }这个就更简单了,直接返回top的值就可以了,为什么呢,我们看两张图即可 图一: 图二: 图一是压栈前,没有一个元素,top=0,图二是压栈后,top++,top=1。同样的以此类推,我们每加入1个元素,top++,每减去一个元素,top–。元素个数永远=top值,所以我们这里的函数直接返回top值即可。 7判断栈是否为空 int StackEmpty(ST*ps)//判断栈是不是空 { assert(ps); return ps->top == 0; }由1.6知,我们的top值是和栈里元素个数一样的,所以我们直接return ps->top == 0;即可,如果ps->top == 0这个表达式成立表达式值为1,反之为0。 二、队列的表示和实现 1队列的概念及结构队列:只允许在一端插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出的性质 入队列:进行插入操作的一端称为队尾 出队列:进行删除操作的一端称为队头 (图片来自比特就业课) 类似你走人工通道那样,你排在前面的,你先出去 2队列的实现由于队列的队头出,队尾入,非常类似单链表的头删和尾插,我们这里介绍以单链表实现队列,如下图,现有3个节点的单链表: 比如现在,我要队头出一个,也就是把单链表节点第一个节点删掉(头删) 或者队尾入一个,也就是单链表的尾插 代码如下(示例): typedef int QDataType; typedef struct QueueNode { struct QueueNode*next; QDataType data; }QNode;//这里和单链表定义一样,有需要的可以看一下笔者之前的单链表文章 typedef struct Queue//定义一个结构体存储头节点地址和尾节点地址,方便后面头删和尾插 { QNode*head; QNode*tail; }Queue; 3队列初始化代码如下(示例): void QueueInit(Queue*pq)队列初始化,pq是一个结构体指针 { assert(pq);//判断pq是否是空指针 pq->head = NULL; pq->tail = NULL; } 4入队(队尾插入一个数据) void QueuePush(Queue*pq, QDataType x)//入队(队尾入) { assert(pq); QNode*newnode = (QNode*)malloc(sizeof(QNode));//开辟出一块空间给newnode if (newnode == NULL)//有可能剩余内存不够开辟空间,malloc开辟失败会返回空指针 { printf("开辟空间失败\n"); exit(-1);//退出程序 } newnode->data = x; newnode->next = NULL; if (pq->tail == NULL)//原先队列里没有任何数据,头和尾指针都指向NULL { pq->head = pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail = newnode; } }关于下面if这段代码解释如下: if (pq->tail == NULL) { pq->head = pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail = newnode; }原先队列里没有任何数据,头和尾指针都指向NULL 当你往队列里面放了一个数据,头和尾指针是指向新的数据(头和尾指针仍指向一个) 如果你想再加1个节点,你首先得把两节点连上,也就是pq->tail->next = newnode;(没接上之前tail还指向第一个节点),接上之后tail指针指向第二节点 关于出队,这里要分2种情况讨论: 1.原队列只有1个数据 只有一个数据的时候,头和尾指针都指向1节点,他们的next是空指针,所以我们以这个条件为判断。又因为要出队(队头删除一个数据),因为只有一个节点,也就是把这个节点给删掉,我们用free函数释放掉head指向的空间。释放完,那块空间已经还给内存了,这时你的头和尾指针就不能指向那块空间了,我们用空指针赋值。 2.原队列有多个数据 我们现在要出队(队头删除一个数据),也就是把1节点删掉,我们先创建一个变量next找到2节点位置,然后free掉1节点的空间 1节点空间free掉之后,把next(指向2节点)赋给head,让头指针指向2节点。 6取队头数据 QDataType QueueFront(Queue*pq)//取队头数据 { assert(pq); assert(pq->head); return pq->head->data; } 7取队尾数据 QDataType QueueBack(Queue*pq)//取队尾数据 { assert(pq); assert(pq->head); return pq->tail->data; } 8计算队列中数据个数 int QueueSize(Queue*pq)//队内数据个数 { assert(pq); int size = 0; QNode*cur = pq->head; while (cur)//cur!=NULL进行循环,NULL是遍历完tail之后出现的 { size++; cur = cur->next; } return size; } 9判断队列是否为空 bool QueueEmpty(Queue*pq) { assert(pq); return pq->head == NULL; }这一般是作为一个辅助函数来使用,bool 就是用来判断真假的数据类型,如果表达式:pq->head == NULL成立返回true,反之返回false 10销毁队列 void QueueDestory(Queue*pq)//队列销毁 { assert(pq); QNode*cur = pq->head; while (cur)//cur!=NULL进行循环,NULL是遍历完tail之后出现的 { QNode*next = cur->next; free(cur);//free是释放指向的空间,指针还是在的 cur = next; } pq->head = pq->tail = NULL; }如上图,我们创建一个变量cur并用head指针赋值。然后找到第二个节点,用cur->next标记,标记完我们释放掉cur(释放的第一个节点空间,指针还是在的),释放完,cur开始遍历第二个节点,也就是我们先前用next标记的空间。。。剩下的以此类推。cur!=NULL进行循环,NULL是遍历完tail之后出现的,当循环不进行说明已经遍历完了尾指针指向的节点,头和尾节点已经不需要了,我们用空指针赋值。 总结本文介绍了栈和队列的相关原理及各个接口函数,内容较多,知识点量大,希望读者耐心学习,相信你一定会有所收获,祝读者学习愉快~更多关于C语言数据结构栈与队列的资料请关注其它相关文章! 相关文章JS中 querySelector 与 getElementById JS中 queryPOST方法@RequestBody传参数失败 POST方法给@Reques |
CopyRight 2018-2019 实验室设备网 版权所有 |