顺序栈的基本操作(C语言)

2023-07-11 04:41| 来源: 网络整理| 查看: 265

　　由于现在只学了C语言所以就写这个C语言版的栈的基本操作

这里说一下：网上和书上都有这种写法 int InitStack(SqStack &p)

&p是取地址但是这种用法好像C并不支持，C++才支持，所以用

C语言写就需要使用指针

代码如下：

1 #include 2 #include 3 #define STACK_INIT_SIZE 100//储存空间初始分配量 4 #define STACKINCREMENT 10//存储空间分配增量 5 #define OK 1 6 #define ERROR 0 7 typedef int StackType; //栈元素类型 8 9 typedef struct { 10 StackType *base; //在构造之前和销毁之后，base的值为NULL 11 StackType *top; //栈顶指针 12 int stacksize; //当前已分配的存储空间，以元素为单位 13 }SqStack; //顺序栈 14 15 //栈的初始化 16 int InitStack(SqStack *p) { 17 18 19 p->base = (StackType*)malloc(STACK_INIT_SIZE * sizeof(StackType)); 20 if (p->base == NULL) return ERROR; //内存分配失败 21 p->top = p->base; //栈顶与栈底相同表示一个空栈 22 p->stacksize = STACK_INIT_SIZE; 23 return OK; 24 25 } 26 //判断栈是否为空 27 int EmptyStack(SqStack *p) { 28 //若为空栈则返回OK，否则返回ERROR 29 if (p->top == p->base) return OK; 30 else return ERROR; 31 } 32 //顺序栈的压入 33 int Push(SqStack *p,StackType e) { 34 //插入元素e为新的栈顶元素 35 if ((p->top - p->base)>= p->stacksize) //栈满，追加储存空间 36 { 37 p->base = (StackType*)realloc(p->base, (p->stacksize + STACKINCREMENT) * sizeof(StackType)); 38 if (p->base == NULL) return ERROR;// 储存空间分配失败 39 p->top = p->base + p->stacksize; //可能有人觉得这句有点多余(我当时也是这么想的后面有解释) 40 p->stacksize += STACKINCREMENT; 41 } 42 *(p->top) = e; 43 (p->top)++; 44 return OK; 45 } 46 // 顺序栈的弹出 47 int Pop(SqStack *p,StackType *e) { 48 //若栈不空，则删除p的栈顶元素，用e返回其值 49 if (p->top == p->base) return ERROR; 50 --(p->top); 51 *e = *(p->top); 52 return OK; 53 54 55 } 56 //顺序栈的销毁 57 int DestroyStack(SqStack *p) { 58 //释放栈底空间并置空 59 free(p->base); 60 p->base = NULL; 61 p->top = NULL; 62 p->stacksize = 0; 63 64 return OK; 65 } 66 //将顺序栈置空栈还是存在的，栈中的元素也存在，如果有栈中元素的地址任然能调用 67 int ClearStack(SqStack *p) { 68 p->top= p->base; 69 return OK; 70 } 71 //返回顺序栈的元素个数 72 int StackLength(SqStack p) { 73 //栈顶指针减去栈底指针等于长度，因为栈顶指针指向当前栈顶元素的下一个位置 74 return p.top - p.base; 75 } 76 //返回顺序栈的栈顶元素 77 int GetTop(SqStack *p, StackType *e) { 78 //若栈不为空，则用e返回p的栈顶元素 79 if (p->top > p->base) { 80 *e = *(p->top - 1); return OK; 81 } 82 else return ERROR; 83 } 84 //从栈顶到栈底对每个元素调用某个函数 85 int StackTraverse(SqStack p,void (*pfun)(StackType)/*函数指针*/){ 86 //从栈底到栈顶依次对栈中的每个元素调用函数pfun() 87 while (p.top > p.base) 88 pfun(*(p.base)++); //先调用后递增 89 printf("\n"); 90 return OK; 91 } 92 //打印栈中元素 93 void print(StackType stack) { 94 printf("%d\n", stack); 95 96 } 97 //测试栈的各种操作 98 int main() { 99 int n,i; 100 StackType *e,a; 101 SqStack *pstack,stack; 102 pstack = &stack; 103 e=(StackType*)malloc(sizeof(StackType)); //为指针e分配内存地址 104 InitStack(pstack); //初始化栈 105 106 if (EmptyStack(pstack) == 1) printf("-------栈为空-------\n"); 107 printf("请输入栈的元素个数:"); 108 scanf("%d", &n); 109 for (i = 0; i < n; i++) 110 { 111 scanf("%d", &a); 112 Push(pstack, a); 113 } 114 if (EmptyStack(pstack) == 0) printf("-------栈不为空-----\n"); 115 116 printf("栈的长度为:%d\n", StackLength(stack)); 117 printf("--------------------\n"); 118 printf("请输入一个入栈元素:"); 119 scanf("%d", &a); 120 Push(pstack, a); 121 printf("--------------------\n"); 122 printf("栈中的元素个数为:%d\n", StackLength(stack)); 123 printf("--------------------\n"); 124 GetTop(pstack, e); 125 printf("栈顶元素为:%d\n", *e); 126 printf("--------------------\n"); 127 printf("打印栈中的元素:\n"); 128 StackTraverse(stack, print); 129 printf("---弹出栈顶元素---\n"); 130 Pop(pstack, e); 131 printf("弹出的栈顶元素为:%d\n", *e); 132 printf("--------------------\n"); 133 GetTop(pstack, e); 134 printf("栈顶元素为:%d\n", *e); 135 printf("--------------------\n"); 136 printf("打印栈中的元素:\n"); 137 StackTraverse(stack, print); 138 printf("--------------------\n"); 139 140 printf("----------清空栈-------\n"); 141 if (ClearStack(pstack) == 0) printf("已清空栈\n"); 142 143 printf("----------销毁栈-------\n"); 144 if (DestroyStack(pstack) == 0) printf("已销毁栈\n"); 145 return 0; 146 147 }

第39行 p->top = p->base + p->stacksize;这句有必要加上吗? 答案是肯定的。这一个问题的关键在于 realloc 是怎么实现的，有两种情况：

　　如果有足够空间用于扩大mem_address指向的内存块，则分配额外内存，并返回mem_address。这里说的是“扩大”，我们知道，realloc是从堆上分配内存的，当扩大一块内存空间时， realloc()试图直接从堆上现存的数据后面的那些字节中获得附加的字节，如果能够满足，自然天下太平。也就是说，如果原先的内存大小后面还有足够的空闲空间用来分配，加上原来的空间大小= newsize。那么就ok。得到的是一块连续的内存。　　如果原先的内存大小后面没有足够的空闲空间用来分配，那么从堆中另外找一块newsize大小的内存。并把原来大小内存空间中的内容复制到newsize中。返回新的mem_address指针。（数据被移动了）。老块被放回堆上。如果是第二种情况的话，s->top 就不是原来的 top 了 --百度百科

　　写这些代码的时候还是遇到了一些问题在这里总结一下：

　　第一对于指针的使用要慎重因为它传递进函数会改变原始数据，所以对于不需要改变

指针指向的值的情况就不要使用指针。

　　第二对于指针的使用如下定义 int *e=NULL； *e=3;

看着好像没有问题编译也没问题但是运行程序就出错

为什么？没有为指针e分配内存地址所以引用肯定错误啊（我这个逗逼错误-_-）

正确的用法应该是 int *e=NULL；e=(int*)malloc(sizeof(int)); *e=3;

我之前都是 int *e,a; e=&a; e=3; 这种用法所以......

【本文地址】

顺序栈的基本操作(C语言)

顺序栈的基本操作(C语言)

今日新闻

推荐新闻