、数据结构笔记之五链栈实现.docxVIP

5、蛤蟆的数据结构笔记之五链栈实现 本篇名言：“人生就像奕棋，一步失误，全盘皆输。” 昨天对栈和队列进行了定义。这次我们来看下如何使用代码来实现链栈和链队列，后续蛤蟆会记录如何将栈应用到实际问题中。 栈一般是顺序结构，但是也可以采用链式存储结构，具体如下实现。 1. 定义结构体 #define MAX_STACKS 10 typedef struct { int key; /*other fields */ }element; typedef struct stack *stack_pointer; typedef struct stack { element item; stack_pointer link; }; stack_pointer top[MAX_STACKS]; 两个结构体，其中一个结构包含在另一个结构体中。 定义了链栈中节点上限数量为10. 2. 链栈的插入 void add(stack_pointer *top,element item) { stack_pointer temp = (stack_pointer)malloc(sizeof(stack)); if(IS_EMPTY(temp)){ fprintf(stderr,The memory is full\n); exit(1); } temp-item = item; temp-link=*top; *top = temp; } 函数需要输入top 指向栈顶元素。需要入栈的元素，element。 3. 链栈的删除 删除节点函数，返回栈顶元素，并改变top,使其指向包含在其链域中的地址。典型调用item=deletenode(top[stack_no]); element deletenode(stack_pointer *top){ stack_pointer temp = *top; element item; if ( IS_EMPTY(temp)){ fprintf(stderr,The stack is empty\n); exit(1); } item = temp-item; *top = temp-link; free(temp); return item; } 4. 链栈输出 为便于调式，输出整个链栈中的值。 void print_node( stack_pointer top){ if ( IS_EMPTY(top)){ fprintf(stderr,The stack is empty\n); exit(1); } for(top;top;top=top-link) { printf(%d ,top-item); } } 5. 链栈综合 如下代码实现一个综合性的测试，最后如下图 1所示： void main() { int i; element temp ; for(i=0;i10;i++) { top[i] = NULL; } for( i=0;i10;i++) { temp.key = i; add(header,temp); } printf(after add 10 nodes\n); print_node( header); printf(\n); for( i=0;i4;i++) { deletenode(header); } printf(after delete 4 nodes\n); print_node( header); printf(\n); for( i=0;i6;i++) { deletenode(header); } printf(after delete left 6 nodes\n); print_node( header); } 6. 链栈源码 方便大家编译，所有代码复制如下： #include stdio.h #include stdlib.h #define IS_EMPTY(ptr) (!(ptr)) #define IS_FULL(ptr) (!(ptr)) #define MAX_STACKS 10 typedef struct element{ int key; /*other fields */ }element; typedef struct stack *stack_pointer; typedef struct stack { element item; stack_pointer link; }stack; stack_pointer top[MAX_STACKS]; stack_pointer hea