家具品牌网站,广州大型网站设计公司,免费做橙光封面的网站,乐清外贸网站建设http://blog.csdn.net/fisherwan/article/details/20055179 首先要感谢这位大牛的一篇博客#xff0c;地址如下#xff1a;http://blog.csdn.net/hguisu/article/details/7674195 当然还有网上一些其他的资料#xff0c;今天自己写了一下链式栈和链式队列的程序。其中在释放…http://blog.csdn.net/fisherwan/article/details/20055179 首先要感谢这位大牛的一篇博客地址如下http://blog.csdn.net/hguisu/article/details/7674195 当然还有网上一些其他的资料今天自己写了一下链式栈和链式队列的程序。其中在释放内存的时候遇到了些许问题通过调找出了原因在这里我与大家分享一下。 1链式栈的相关代码块 Stack.h 头文件——定义了节点结构和链式栈结构以及基本操作函数的声明部分 [cpp] view plain copy #ifndef _STACK_H_H #define _STACK_H_H typedef struct Node { int data; struct Node *pNext; }NODE, *pNODE; typedef struct Stack { pNODE top; }STACK, *pSTACK; //栈初始化 void InitStack(pSTACK stack); //入栈 void PushStack(pSTACK stack, int data); //出栈 void PopStack(pSTACK stack, int *data); //判断栈是否为空 int IsEmptyStack(pSTACK stack); //获得栈顶元素 int GetTopStack(pSTACK stack); //释放内存 void FreeMemory(pSTACK stack); #endif Stack.cpp源文件——定义链式栈的基本操作函数的定义 说明一开始对栈初始化但是这个栈是没有头节点的直接定义了一个指针top刚开始指向NULL。 入栈的时候就是让top指针始终指向栈顶元素入栈的节点的指针指向top指针这样不断的进行入栈操作节点不断增加但是top指针一直是指针最后插入的节点。 出栈的时候就是从top指针指向的节点还是释放然后让top指针指向被释放节点的下一个节点这样节点不断释放top指针不断向下移动。 所以栈就成了一个“先进后出”的结构。 [cpp] view plain copy #include Stack.h #include stdlib.h #include stdio.h //栈初始化 void InitStack(pSTACK stack) { stack-top NULL; } //入栈 void PushStack(pSTACK stack, int data) { pNODE p_new (pNODE)malloc(sizeof(NODE)); if (NULL p_new) { printf(内存分配失败\n); exit(EXIT_FAILURE); } p_new-data data; p_new-pNext stack-top; //这里要注意 stack-top p_new; } //出栈 void PopStack(pSTACK stack, int *data) { pNODE p_delete stack-top; if (IsEmptyStack(stack)) exit(EXIT_FAILURE); *data p_delete-data; stack-top p_delete-pNext; free(p_delete); p_delete NULL; } //判断栈是否为空 int IsEmptyStack(pSTACK stack) { if (stack-top NULL) return 1; else return 0; } //获得栈顶元素 int GetTopStack(pSTACK stack) { int data; if (stack-top NULL) exit(EXIT_FAILURE); data stack-top-data; return data; } //释放内存 void FreeMemory(pSTACK stack) { pNODE p_delete NULL; while (stack-top ! NULL) { p_delete stack-top; stack-top p_delete-pNext; free(p_delete); p_delete NULL; } } main.cpp 测试程序——通过简单的交互界面测试函数的功能 [cpp] view plain copy #include stdio.h #include Stack.h int main(void) { int number, i, data, flag; STACK s; InitStack(s); printf(请输入入栈个数); scanf(%d, number); for (i1; inumber1; i) { printf(请输入第%d个栈点元素值, i); scanf(%d, data); PushStack(s, data); } PopStack(s ,data); printf(出栈的元素值为%d\n, data); data GetTopStack(s); printf(当前栈顶元素值为%d\n, data); FreeMemory(s); flag IsEmptyStack(s); if (flag) printf(内存释放成功\n); else printf(内存释放失败\n); return 0; } 2链式队列的相关代码 Queue.h 头文件——定义了节点结构和队列结构以及链式队列的基本操作函数的声明 [cpp] view plain copy #ifndef _QUEUE_H_H #define _QUEUE_H_H typedef struct Node { int data; struct Node *pNext; }NODE, *pNODE; typedef struct Queue { pNODE front; pNODE rear; }QUEUE, *pQUEUE; //初始化队列 void InitQueue(pQUEUE queue); //入队列 void EnQueue(pQUEUE queue, int data); //出队列 void DeQueue(pQUEUE queue, int *data); //判断队列是否为空 int IsEmptyQueue(pQUEUE queue); //获得队头元素值 int GetFrontQueue(pQUEUE queue); //释放内存 void FreeMemory(pQUEUE queue); #endif Queue.cpp源文件——定义了基本操作函数的定义 说明一开始对链式队列进行初始化这里就创建了一个节点但是记得后面释放内存的时候这里也要释放创建了这个节点是为了方便后面的操作这样一开始队列的头指针和尾指针都指向了这个节点但是此时的队列是空的就像循环链表里头节点不参与运行是一样的道理。 入队列的时候就是进入的节点排在初始化时创建的节点后面然后尾指针指针指着新进入的节点但是头指针不动节点不断进入队列尾指针不断向后移动保持尾指针一直指着刚进入的节点。 出队列的时候就是让头指针指向的节点的指针指向要释放节点的下一个节点节点不断出队列这里头指针实质上并没有移动但是它指向的节点的指针一直在变化一直保持者指向要释放节点的下一个节点但是这里要注意就是当队列中只剩下一个节点的时候这里不包含初始化创建的那个节点释放了这个节点以后尾指针成了野指针那么这个时候就要让尾指针和头指针指向同一位置那么这样判断队列是否为空的时候就是空了。 [cpp] view plain copy //链式队列代码 #include stdlib.h #include stdio.h #include Queue.h //初始化队列 void InitQueue(pQUEUE queue) { queue-front (pNODE)malloc(sizeof(NODE)); queue-front-data 0; queue-front-pNext NULL; if (NULL queue-front) { printf(内存分配失败\n); exit(EXIT_FAILURE); } queue-rear queue-front; } //入队列 void EnQueue(pQUEUE queue, int data) { pNODE p_new (pNODE)malloc(sizeof(QUEUE)); if (NULL p_new) { printf(内存分配失败\n); exit(EXIT_FAILURE); } p_new-data data; p_new-pNext NULL; queue-rear-pNext p_new; queue-rear p_new; } //出队列 void DeQueue(pQUEUE queue, int *data) { if (IsEmptyQueue(queue)) exit(EXIT_FAILURE); pNODE p_delete queue-front-pNext; *data p_delete-data; queue-front-pNext p_delete-pNext; if (p_delete-pNext NULL) queue-rear queue-front; free(p_delete); p_delete NULL; } //判断队列是否为空 int IsEmptyQueue(pQUEUE queue) { if (queue-front queue-rear) return 1; else return 0; } //获得队头元素值 int GetFrontQueue(pQUEUE queue) { int data; if (IsEmptyQueue(queue)) exit(EXIT_FAILURE); data queue-front-data; return data; } //释放内存 void FreeMemory(pQUEUE queue) { pNODE p_delete NULL; while (queue-front ! NULL) { p_delete queue-front; queue-front p_delete-pNext; if (p_delete-pNext NULL) //如果到达最后一个节点时队尾指针为NULL queue-rear NULL; free(p_delete); p_delete NULL; } } main.cpp 测试程序——简单的交互界面测试函数功能 [cpp] view plain copy #include stdio.h #include Queue.h int main(void) { int number, i, data, flag; QUEUE q; InitQueue(q); flag IsEmptyQueue(q); if (flag) printf(初始化成功\n); printf(请输入入队列个数); scanf(%d, number); for (i1; inumber1; i) { printf(请输入第%d个队点元素值, i); scanf(%d, data); EnQueue(q, data); } DeQueue(q ,data); printf(出队列的元素值为%d\n, data); data GetFrontQueue(q); printf(当前栈顶元素值为%d\n, data); FreeMemory(q); if (q.front NULL q.rear NULL) printf(内存释放成功\n); else printf(内存释放失败\n); return 0; }
