线性结构——栈（c语言）
发布时间：2022-11-09 11:08:49 所属栏目：PHP教程 来源：
导读： 目录
一、栈的概念:
栈是一种只允许在一端插入与删除的线性表,操作受限。只允许插入与删除操作的一端为栈顶，另一端为栈底。栈的操作通常为“入栈或进栈”、“出栈或退栈”
一、栈的概念:
栈是一种只允许在一端插入与删除的线性表,操作受限。只允许插入与删除操作的一端为栈顶，另一端为栈底。栈的操作通常为“入栈或进栈”、“出栈或退栈”
|
目录 一、栈的概念: 栈是一种只允许在一端插入与删除的线性表,操作受限。只允许插入与删除操作的一端为栈顶，另一端为栈底。栈的操作通常为“入栈或进栈”、“出栈或退栈”。当栈中无数据元素时为空栈。栈的特点是：先进后出也就是后进先出。 二、栈的运算： 1.InitStack(S)初始化：初始化一个新的栈 2. Empty(S)栈的非空判断：若栈不空返回TRUE，否为FALSE 3. Push(S,x)入栈：在栈顶的头部插入元素，若栈满返回FALSE 4. Pop（S）出栈：若栈不空，返回栈顶元素，并且删除该元素 5.GetTop（S）取出栈顶元素：若栈不空，返回栈顶元素，否则返回NULL 6.SetEmpty（s)置栈空操作：使栈为空栈。 需要注意： (1)进栈前需要判断栈是否满 （2）出栈和取栈顶元素时判断栈是否为空 （3）出栈与取栈顶元素的不同在于，出栈是返回数据元素的同时，栈顶指针移动到下一位置。取栈顶元素是并不改变栈顶指针的位置，返回栈顶数据元素。 三、栈的顺序存储结构 类似顺序表的操作，栈中需要预设一个足够长度的存储空间，ElemType elem[MAXSIZE]，栈底的位置可以设置在数组的端点，定义一个int top 作为栈顶的指针，指明当前的位置。 (1)栈的初始化操作 typedef struct //定义一个结构 { ElemType elem[MAXSIZE]; int top; }Sepstack; Sepstack InitStack() { Sepstack* s; s = (Sepstack*)malloc(sizeof(Sepstack)); s->top = -1; //栈顶指针初始化，此时为空栈 return s; } （2）判空栈 int Empty(Sepstack* s) { if (s->top == -1) return 1; //判断栈为空 else return 0; } （3）入栈 int Push(Sepstack* s, ElemType x) //Elem自定义一个数据类型 { if (s->top == MAXSIZE - 1) //判断栈满，栈满不能入栈 return 0; else { s->top++; //先使栈顶指针移动到下一个位置接受数据元素 s->elem[s->top] = x; rerurn 1; } } （4）出栈 int Pop(Sepstack* s,ElemType*x) { if (s->top == -1) return 0; else { *x = s->elem[s->top]; //定义一个指针用于接受栈顶元素 s->top--; //出栈，栈顶指针减一 return 1; } } （5）取栈顶元素 int Get(Sepstack* s) { if (s->top == -1) //判断栈是否为空栈 return 0; else return s->elem[s->top]; } （6）遍历出栈 void Traver(Sepstack* s) { while (s->top != -1) { printf("%d", s->elem[s->top]); //此时一整形数据元素举例 s - > top--; } } 四、多栈共享邻接空间 让多个栈共用一个足够大的连续存储空间，利用栈的动态特性使存储空间互补。 两栈共享为例： (1)初始化操作 typedef struct { ElemType elem[MAXSIZE]; int lefttop; //定义一个指向左栈的栈顶指针 int righttop; }Sepstack; Sepstack InitStack() { Sepstack* s; if(s = (Sepstack*)malloc(sizeof(Sepstack))==NULL); //判断申请栈的空间是否成功 return FALSE; s->lefttop = -1; //让一个栈的栈顶在左边，初始化为数组的端点-1 s->righttop = MAXSIZE; //右边的栈，初始化为数组下标最大值+1。 return s; } （2）入栈 int Push(Sepstack* s, ElemType x, char status) //char 是选择将x压入左栈还是右栈 { if (s->lefttop + 1 == s->righttop) // 判断栈是否满 return 0; if (status == 'L') { s->elem[++s->lefttop++] = x; //压栈时左栈栈顶指针先移动下一个空间 } if (status == 'R') { s->elem[--s->righttop] = x; //右端压栈时向左移动空间减一 } return TURE; } （3）出栈 int Pop(Sepstack* s,char status) { if (status == 'L') { if (s->lefttop <0) //判断左栈是否为空 return 0; else return s->elem[s->lefttop--]; //左栈出栈是方向向左 } if (status == 'R') { if (s->righttop > MAXSIZE-1) //判断右栈是否为空 return 0; else return s->elem[s->righttop++]; //右栈出栈方向与左栈相反 } else return NULL; } 五、栈的链式存储结构 避免申请的存储空间过小导致栈满（上溢），可以使用链式存储结构，让多个栈共享存储空间。采用链式存储结构同时满足先进后出的特点，及数据元素进栈时需要采用头插法php指针，栈的进栈和出栈都只允许在一端。所以链栈中的第一个元素即栈顶，最后一个为栈底。 （1）链栈初始化 typedef struct Stacknode { //定义一个结构 Datatype data; struct Stacknode* next; }Slstacktype; Slstacktype* Initslstack() { Slstacktype* top; //对栈顶指针初始化 top = (Slstacktype*)malloc(sizeof(Slstacktype)); top->next = NULL; return top; } （2）入栈 int Pushtack(Slstacktype*top,Datatype x) { Slstacktype* p; //申请一个新的结点 if(p = (Slstacktype*)malloc(sizeof(Slstacktype))==NULL) return FALSE; p->data = x; p->next = top->next; top->next = p; return TRUE; } （3）出栈 Datatype Pop(Slstacktype* top) { Slstacktype* p; Datatype x; if (top->next == NULL) //出栈判断是否为空栈 return; p = top->next; x = p->data; top->next = p->next; free(p); return x; } （4）多个链栈的操作 多个链栈操作，是指将多个单链栈的栈顶指针放在一个一维数组中统一管理（也就是指针数组），及通过一维数组下标就可找到每个单链栈的栈顶指针，就能找到单链栈并且进行操作，定义一个链栈Slstacktype*top[M]。 （编辑：我爱制作网_池州站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
站长推荐
浙公网安备 33038102330577号