【数据结构】栈和链表基本方法的实现

小编主页详情-请点击小编gitee代码仓库-请点击本文主要介绍了数据结构的栈和链表内容全由作者原创无AI同时深度解析了栈和链表基本方法的实现并带有配图帮助博友们更好的理解点个关注不迷路下面进入正文~~目录1.栈1.1栈的概念及结构1.2栈结构的定义1.3栈需要实现的基本功能1.4栈基本方法的实现1.4.1初始化和销毁1.4.2 入栈和出栈1.4.3取栈顶数据1.4.4判空1.4.5获取数据个数2.队列2.1队列的概念及结构2.2队列的实现2.3队列实现的前期准备2.4队列需要实现的基本功能2.5队列基本方法的实现2.5.1初始化和销毁2.5.2队列的插入2.5.3删除数据2.5.4取队头和队尾的数据2.5.5获取数据个数和判空结语1.栈1.1栈的概念及结构栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出LIFOLast In First Out的原则。压栈栈的插入操作叫做进栈/压栈/入栈入数据在栈顶。出栈栈的删除操作叫做出栈。出数据也在栈顶。我们可以形象的将栈比作一个弹夹先装进去的子弹就先射出去。也可以比作我们上电梯的时的先后顺序最后进电梯的人往往最先出去。1.2栈结构的定义栈的实现一般可以使用数组或链表实现那么我们具体要怎么选择呢这里我们首先排除双向链表因为用单链表就足以实现栈用双向链表会额外占用空间。单链表和数组其实在栈的实现上区别不大相对而言数组的结构实现更有一点因为数组在尾上插入数据的代价比较小。这里我们就使用数组实现栈。、typedef int SLDataTtpe; typedef struct Stact { SLDataTtpe* a; int top; int capacity; }ST;这里的top其实就是顺序表的size从下标上看top表示即将要插入数据的位置。1.3栈需要实现的基本功能栈相对与顺序表的实现要简单不少因为栈有限制出数据和入数据的方向需要实现的方法也相对较少常用的方法有如下几种如图所示。// 初始化和销毁 void STInit(ST* pst); void STDestroy(ST* pst); // 入栈 出栈 void STPush(ST* pst,SLDataTtpe x); void STPop(ST* pst); // 取栈顶数据 SLDataType STTop(ST* pst); // 判空 bool STEmpty(ST* pst); // 获取数据个数 int STSize(ST* pst);1.4栈基本方法的实现1.4.1初始化和销毁这里的实现比较简单不过多赘述// 初始化和销毁 void STInit(ST* pst) { assert(pst); pst-a NULL; pst-capacity pst-top 0; } void STDestroy(ST* pst) { assert(pst); free(pst-a); pst-a NULL; pst-capacity pst-top 0; }1.4.2入栈和出栈入栈最需要注意的地方就是扩容的时候先先判断capacity是否为零为零就先赋值不为零就翻倍。这里用三目操作符可以很好的实现出栈的实现方法也比较简单直接让栈顶向前走一位即可前提是栈里面要有数据。// 入栈 出栈 void STPush(ST* pst, SLDataType x) { assert(pst); if (pst-capacity pst-top) { int newcapacity pst-capacity 0 ? 4 : pst-capacity * 2; ST* tmp (ST*)realloc(pst-a, newcapacity * sizeof(SLDataType)); if (tmp NULL) { perror(STpush); return; } pst-a tmp; pst-capacity newcapacity; } pst-a[pst-top] x; pst-top; } void STPop(ST* pst) { assert(pst); assert(pst-top 0); pst-top--; }1.4.3取栈顶数据需要注意的是这里的top指的是下一个需要插入数据的位置因此我们要找的位置应该是top的上一个位置在访问数组时下标应是top-1。// 取栈顶数据 SLDataType STTop(ST* pst) { assert(pst); assert(pst-top 0); return pst-a[pst-top - 1]; }1.4.4判空这里用if判断top是否为可能会更好理解。为了更方便和简洁我们可以直接返回pst-top 0如果为真返回1即为true数组为空如果为假返回0即为false数组不为空// 判空 bool STEmpty(ST* pst) { assert(pst); /*if (pst-top 0) { return true; } return false;*/ return pst-top 0; }1.4.5获取数据个数top指的是下一个需要插入数据的位置同时也是数组元素的个数直接返回top即可。// 获取数据个数 int STSize(ST* pst) { assert(pst); return pst-top; }2.队列2.1队列的概念及结构队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出FIFO(First In First Out)入队列进行插入操作的一端称为队尾出队列进行删除操作的一端称为队头形象的说我们在排队吃饭取号的时候都是先取号的先用餐队列也是如此。2.2队列的实现队列也可以数组和链表的结构实现使用链表的结构实现更优一些因为如果使用数组的结构出队列在数组头上出数据效率会比较低。typedef int QDataType; typedef struct QueueNode { struct QueueNode* next; QDataType val; }QNode;2.3队列实现的前期准备// 队尾插入 void QueuePush(QNode** pphead, QNode** pptail, QDataType x); // 队头删除 void QueuePop(QNode** pphead, QNode** pptail);如果我们这样实现有两个很麻烦的点一个是要使用二级指针逻辑会比较绕。另一个是每次找最后一个节点都要遍历整个数据这样的实现并不是很好为了解决这个问题我们可以重新定义一个结构体Queue储存队列的各种信息typedef struct Queue { QNode* phead; QNode* ptail; int size; }Queue;这里额外定义了size无需反复遍历数组方便后续功能的实现2.4队列需要实现的基本功能void QueueInit(Queue* pq); void QueueDestroy(Queue* pq); void QueuePush(Queue* pq, QDataType x); void QueuePop(Queue* pq); // 取队头和队尾的数据 QDataType QueueFront(Queue* pq); QDataType QueueBack(Queue* pq); int QueueSize(Queue* pq); bool QueueEmpty(Queue* pq);2.5队列基本方法的实现2.5.1初始化和销毁这里的实现比较简单不过多赘述void QueueInit(Queue* pq) { assert(pq); pq-phead pq-ptail NULL; pq-size 0; } void QueueDestroy(Queue* pq) { assert(pq); QNode* cur pq-phead; while (cur) { QNode* next cur-next; free(cur); cur next; } pq-phead pq-ptail NULL; pq-size 0; }2.5.2队列的插入这里用尾插实现插入。需要分两种情况当队列没有数据时直接让头指针和尾指针都指向新节点。当队列有数据时再尾插数据。最后别忘了size下面是详细的代码void QueuePush(Queue* pq, QDataType x) { assert(pq); QNode* newnode (Queue*)malloc(sizeof(QNode)); if (newnode NULL) { perror(QueuePush); return; } newnode-val x; newnode-next NULL; if (pq-phead NULL) { pq-phead pq-ptail newnode; } else { pq-ptail-next newnode; pq-ptail newnode; } pq-size; }2.5.3删除数据常规的思路释放头节点再将头节点移动到下一个节点。可这样做存在一个特殊情况当队列只剩一个数据时phead指向NULL可是ptail却仍指向那个已经被删除的节点这样做会让ptail成为野指针存在很大的风险。最好的解决办法也是对列只剩一个数据单独讨论让ptail和phead都指向NULL。最后别忘了size--哦具体代码如下void QueuePop(Queue* pq) { assert(pq); assert(pq-size ! 0); if (pq-phead pq-ptail) { free(pq-phead); pq-phead pq-ptail NULL; } else { QNode* next pq-phead-next; free(pq-phead); pq-phead next; } pq-size--; }2.5.4取队头和队尾的数据断言后直接返回ptail和phead指向的数据即可。// 取队头和队尾的数据 QDataType QueueFront(Queue* pq) { assert(pq); assert(pq-phead); return pq-phead-val; } QDataType QueueBack(Queue* pq) { assert(pq); assert(pq-ptail); return pq-ptail-val; }2.5.5获取数据个数和判空根据size大小做出对应指令即可int QueueSize(Queue* pq) { assert(pq); return pq-size; } bool QueueEmpty(Queue* pq) { assert(pq); return pq-size 0; }结语这篇文章全文由作者手写图片由画图软件所制无AI制作希望各位博友能有所收获欢迎各位博友的讨论觉得不错的小伙伴别忘了点赞关注哦~