文档章节

栈的线性储存结构与链式储存结构的实现(C语言)。

奔跑的码农
 奔跑的码农
发布于 2016/03/27 21:08
字数 1094
阅读 128
收藏 1

顺序栈,即栈的储存结构是利用地址连续的一组储存单元依次存放栈顶到栈底的数据元素.

栈的结构:代码如下

#include<stdio.h>
#include<stdlib.h>
#define STACK_INIT_SIZE 100/*储存空间初始分配量*/
#define STACKINCREMENT 10/*储存空间分配增量*/
typedef int ElemType;
typedef int Status;
/*-----------------栈的顺序储存表示--------------------------*/
typedef struct {
 ElemType *base;/*在栈构造之前和销毁之后base的值为NULL*/
 ElemType *top; /*栈顶指针*/
 int stacksize; /*当前以分配的空间,以元素为单位*/
}SqStack;

构造一个空栈,先为栈分配初始大小,base指向分配空间,并令base==top。用stacksize来储存目前已经分配的空间,以元素的个数为单位。代码如下:

 Status InitStack(SqStack *S){/*构造一个空栈*/
 S->base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType));
 if(!S->base)exit(0);//储存分配失败
 S->top=S->base;
 S->stacksize=STACK_INIT_SIZE;
 return 1;
}

取出元素,即为出栈,首先检测栈是否为空,如果不是取出栈顶元素,栈顶指针向前移位。即向靠近栈底的一方移位。代码如下:

Status GetTop(SqStack *S,ElemType *e)
{/*如果栈不为空,返回栈顶元素*/
 if(S->base==S->top)return 0;
 else
 {
  S->top--;
  *e=*(S->top+1);
  return 1;
 }
}

存入元素即为压栈。首先检测是否有储存空间:如果没有则分配。代码如下:

 Status Push(SqStack *S,ElemType *e)
{/*插入元素e为新的栈顶元素*/
 if(S->top-S->base>=S->stacksize){//栈满,追加空间
  S->base=(ElemType *)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(ElemType));
  if(!S->base)exit(0);
  S->top=S->base+S->stacksize; 
  S->stacksize+=STACKINCREMENT;
 }
 S->top++;
 *S->top=*e;
 return 1;
}

ealloc,malloc,calloc的区别

三个函数的申明分别是:
void* realloc(void* ptr, unsigned newsize);
void* malloc(unsigned size);
void* calloc(size_t numElements, size_t sizeOfElement);
都在stdlib.h函数库内
它们的返回值都是请求系统分配的地址,如果请求失败就返回NULL

malloc用于申请一段新的地址,参数size为需要内存空间的长度,如:
char* p;
p=(char*)malloc(20);

calloc与malloc相似,参数sizeOfElement为申请地址的单位元素长度,numElements为元素个数,如:
char* p;
p=(char*)calloc(20,sizeof(char));

测试函数:

void main()
{
 int z,i;
 SqStack S;
 InitStack(&S);/*初始化栈*/
 printf("压栈,存入数据1,2,3,4,5:\n");
 for(i=1;i<=5;i++)
 {
  Push(&S,&i);
 }
 printf("出栈,取出前两个:");
 for(i=1;i<=2;i++)
 {
  GetTop(&S,&z);
  printf("%d\t",z);
 }
 printf("\n");
 printf("压栈,存入数据11,12,13:\n");
 for(i=11;i<=13;i++)
 {
  Push(&S,&i);
 }
  printf("出栈,取出前四个:\n");
 for(i=1;i<=4;i++)
 {
  GetTop(&S,&z);
  printf("%d\t",z);
 }
  system("pause");
}

运行结果如下:

-----------------------------------------------------------------------------------------------------------------------------

栈的链式储存结构:

#include<stdio.h>
#include<stdlib.h>
typedef int Elemtype;
typedef int Status;
typedef struct Snode
{
 Elemtype data;  /*数据域*/
 struct Snode *next; /*指针域*/
}Snode,*LinkStack;

假设S是linkStack型的变量,s为链栈的头指针,并且始终指向链顶,即线性表的第一个元素。压栈入栈等操作代码如下:

 void Init_StackL(LinkStack *S)
{
 *S=NULL;
}
Status Push_L(LinkStack *S,Elemtype x)   /*将元素x插入到栈顶位置*/
{
 LinkStack p;
 p=(LinkStack)malloc(sizeof(Snode));  /*新节点生成*/
 p->data=x;         /*向新节点赋值*/
 p->next=*S;         /*向栈顶插入新结点*/
 *S=p;
 return 1;
}
Status  Pop_L(LinkStack *S,Elemtype *temp_) /*删除链栈的顶元素*/
{
 LinkStack p;
 Elemtype temp;
 if(*S==NULL) return 0;      /*对于空栈则退出*/
 temp=(*S)->data;       /*暂存栈顶元素值,以便返回*/
 p=*S;           /*使栈顶指向下一结点*/
 *S=p->next;
 free(p);          /*释放栈顶元素*/
 *temp_=temp;
 return 1;
}

测试函数如下,与线性栈的测试数据相同,代码如下:

 void main()
{
 int i,z;
 LinkStack S;
 Init_StackL(&S);
 printf("压栈,存入数据1,2,3,4,5:\n");
 for(i=1;i<=5;i++)
 {
  Push_L(&S,i);
 }
 printf("出栈,取出前两个:");
 for(i=1;i<=2;i++)
 {
  Pop_L(&S,&z);
  printf("%d\t",z);
 }
 printf("\n");
 printf("压栈,存入数据11,12,13:\n");
 for(i=11;i<=13;i++)
 {
  Push_L(&S,i);
 }
  printf("出栈,取出前四个:\n");
 for(i=1;i<=4;i++)
 {
  Pop_L(&S,&z);
  printf("%d\t",z);
 }
  system("pause");
}

测试结果与线性栈的结果相同,如上图测试结果。

------------------------------------------华丽分割线----------------------------------------------------------

学习数据结果记录,栈的计数遍历等操作思路与线性表相同。如有错误欢迎指正。

© 著作权归作者所有

奔跑的码农

奔跑的码农

粉丝 15
博文 33
码字总数 40544
作品 0
海淀
程序员
私信 提问
二叉树的性质以及二叉树的遍历(非递归)(c语言)(一)

二叉树的性质: 性质 1 在二叉树的第i层上至多有2^(i-1)个结点(i>=1)。 性质 2 深度为k的二叉树至多有2^k-1个结点,(k>=1)。 性质 3 任何一颗二叉树,终端结点为n0,度为2的结点为n2,那...

奔跑的码农
2016/05/14
359
0
易语言 取自定义数据类型的大小

先说一下易语言的变量储存机制 易语言有基本数据类型和复合数据类型两种 基本数据类型包括:1. 各种整数 2.各种浮点 3. 逻辑值 他们都是储存在栈上的 大小都是固定的 用不着取 复合类型一般储...

apachecn_飞龙
2014/06/02
0
0
数据结构java(一)数组链表

链表是数据结构中最基础的内容,链表在存储结构上分成两种:数组形式储存,链式存储。 相比c语言需要的结构体,在java中由于有了面向对象编程,将指针‘藏’了起来,不需要分配内存。 所以只...

dark_Souls
02/12
0
0
C语言/C++编程新手入门基础知识整理学习

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界
2018/04/01
0
0
《大话数据结构》读书笔记(1)

其实去年的时候就看过这本书了。只是,基本上是走马观花, 了解了一些基本概念。这次,为了看懂里面的代码,又特地去复习了一下c语言。还记得上次看的时候,感觉算法果然名不虚传,真的难!现...

幽灵君
2018/12/16
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Spring Boot + Mybatis-Plus 集成与使用(二)

前言: 本章节介绍MyBatis-Puls的CRUD使用。在开始之前,先简单讲解下上章节关于Spring Boot是如何自动配置MyBatis-Plus。 一、自动配置 当Spring Boot应用从主方法main()启动后,首先加载S...

伴学编程
昨天
7
0
用最通俗的方法讲spring [一] ──── AOP

@[TOC](用最通俗的方法讲spring [一] ──── AOP) 写这个系列的目的(可以跳过不看) 自己写这个系列的目的,是因为自己是个比较笨的人,我曾一度怀疑自己的智商不适合干编程这个行业.因为在我...

小贼贼子
昨天
7
0
Flutter系列之在 macOS 上安装和配置 Flutter 开发环境

本文为Flutter开发环境在macOS下安装全过程: 一、系统配置要求 想要安装并运行 Flutter,你的开发环境需要最低满足以下要求: 操作系统:macOS(64位) 磁盘空间:700 MB(不包含 IDE 或其余...

過愙
昨天
6
0
OSChina 周六乱弹 —— 早上儿子问我他是怎么来的

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @凉小生 :#今日歌曲推荐# 少点戾气,愿你和这个世界温柔以待。中岛美嘉的单曲《僕が死のうと思ったのは (曾经我也想过一了百了)》 《僕が死の...

小小编辑
昨天
2.7K
16
Excption与Error包结构,OOM 你遇到过哪些情况,SOF 你遇到过哪些情况

Throwable 是 Java 中所有错误与异常的超类,Throwable 包含两个子类,Error 与 Exception 。用于指示发生了异常情况。 Java 抛出的 Throwable 可以分成三种类型。 被检查异常(checked Exc...

Garphy
昨天
42
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部