精华内容
下载资源
问答
  • 使用顺序线性表实现,含有如下功能: 1.创建; 2.销毁; 3.清空; 4.进栈; 5.出栈; 6.获取栈顶元素; 7.获取的大小。
  • 顺序存储结构和链式存储结构

    千次阅读 2018-10-10 08:15:09
    1.的定义: ...:后进先出(last in first out)的线性表,简称LIFO结构的插入称为进栈,也称压栈,入栈。 的删除称为出栈,也称弹。 2.的抽象数据结构  因为本身就是一个...

    1.栈的定义:

    在表尾进行插入和删除操作的线性表(仍然满足线性表的操作,只是在push和pop有些区别)

    栈顶(top)允许插入和删除,另一端称栈底(bottom),不含任何数据元素的栈叫空栈。

    栈:后进先出(last in first out)的线性表,简称LIFO结构。

    栈的插入称为进栈,也称压栈,入栈。

    栈的删除称为出栈,也称弹栈。

    2.栈的抽象数据结构

      因为栈本身就是一个线性表,所以线性表的操作特性它都具备,针对它的特殊性,在它的操作上可能会有一些变化。将进栈和出栈分别改名为push和pop。由于栈本身是一个线性表,所以线性表的顺序存储结构和链式存储结构同样适用于栈。

    3.栈的顺序存储结构

    栈的顺序存储结构,简称顺序栈。定义一个top变量来指示栈定元素在数组中的位置。若存储栈的长度为StackSize,则栈顶位置top必需小于StackSize。下标从0开始,当栈存在一个元素时候,top 等于 0 ,当栈为空栈时候,top 等于 -1。

    栈的结构定义

     typedef int SElemType;
        typedef struct {
            SElemType data[MAXSIZE];
            int top;                //用于栈顶指针
        } SqStack;

     

    若现在有一个栈,StackSize为5,则普通栈、空栈、满栈的情况如下图所示。                                    

    4.进栈

    status pushStack(stack* s ,SElemType e)
    {
    	if(s->top == MaxSize - 1 )
    		exit(error);
    	s->top++;
    	s->data[s->top] = e;
    	//s->top++;
    	return OK;
    }

    5.出栈

    status popStack(stack* s )
    {
    	if(s->top == -1)
    		exit(error);
    	s->top--; //出栈并不是把这个元素改为0才可以。
    
    }
    //栈的顺序存储结构
    #include<iostream>
    #define MaxSize 10
    #define OK 1 
    #define error -1
    using namespace std;
    typedef int SElemType;
    typedef int status;
    typedef struct
    {
    	SElemType data[MaxSize];
    	int top;
    }stack;
    //两栈共享空间
    typedef struct
    {
    	SElemType data[MaxSize];
    	int top1;
    	int top2;
    }DoubleStack;
    stack* creatStack()
    {
    	stack *stack1 = (stack*)malloc(sizeof(stack));
    	stack1->top = -1;
    	return stack1;
    }
    status pushStack(stack* s ,SElemType e)
    {
    	if(s->top == MaxSize - 1 )
    		exit(error);
    	s->top++;
    	s->data[s->top] = e;
    	//s->top++;
    	return OK;
    }
    status popStack(stack* s )
    {
    	if(s->top == -1)
    		exit(error);
    	s->top--; //出栈并不是把这个元素改为0才可以。
    }
    void printStack(stack* s)
    {
    	while(s->top != -1)
    	{
    		//s->data 是栈的首地址
    		cout<<s->data[s->top]<<endl;
    		s->top--;
    	}
    }
    //两栈共享空间
    status pushDoubleStack(DoubleStack *s ,SElemType num ,SElemType insertStack)
    {
    	if(s->top1 + 1 == s->top2)
    		return error;
    	if(insertStack!= 1&&insertStack != 2 )
    		return error;
    	if(insertStack == 1)
    		s->data[++s->top1] = num;
    	else if (insertStack == 2)
    		s->data[--s->top2] = num;
    	return OK
    } //--和 ->运算等级
    
    status popDoubleStack(DoubleStack *s ,SElemType* e  ,SElemType deleteStack) 
    	//SElemType* e 来接受出栈的值  deleteStack从栈1 或者栈2 删除
    {
    	
    	if(deleteStack == 1)
    	{
    		//首先进行判断空处理 
    		if(s->top1 == -1)
    			return error;
    		*e = s->data[s->top1++];
    	}
    	else if(deleteStack == 2)
    	{
    		if(s->top2 == MaxSize)
    			return error;
    		*e = s->data[s->top2--];
    	}
    	return OK;
    
    }
    void main()
    {
    	stack *s = creatStack();
    	pushStack(  s ,5 );
    	printStack(s);
    
    }

    栈的链式存储结构称做链栈。

    链栈空的定义top == NULL

    进栈操作

    status pushStackLinkList(StackLinkList* s,eleType e)
    {
    	Stacknode* p = (Stacknode*)malloc(sizeof(Stacknode));
    	p->data = e;
    	p->next = s->top;
    	s->top = p;
    	s->count++;
    	return OK;
    }

    出栈操作

    status popStackLinkList(StackLinkList* s,eleType* e)
    {
    	//判断空处理
    	if(s->top == NULL)
    		return error;
    	*e = s->top->data;
    	Stacknode* p = s->top;
    	s->top = s->top->next;
    	free(p);
    	s->count--;
    	return OK;
    
    }

    栈的应用 ---递归!(没有写代码)

    展开全文
  • 数据结构栈顺序存储结构
  • 顺序存储结构 1.顺序的存储结构 #define MAXSIZE 100 //顺序存储空间的初始分配 typedef struct{ SElemType *base; //底指针 SElemType *top; //栈顶指针 int stacksize; //可用的最大容量 }...

    栈的顺序存储结构

    1.顺序栈的存储结构

    #define MAXSIZE 100	//顺序栈存储空间的初始分配
    typedef struct{
    	SElemType *base;	//栈底指针
    	SElemType *top;		//栈顶指针
    	int stacksize;		//栈可用的最大容量
    }SqStack;
    

    2.顺序栈的初始化

    初始化就是为顺序栈动态分配一个预定义大小的数组空间

    栈属于逻辑结构
    数组为顺序存储结构(存储/物理结构:逻辑结构在计算机中的存储形式)
    具体关系见本人关于数据结构第一章图解:传送门

    Status InitStack(SqStack &S){	//形参使用引用&,以下函数对S操作就是对实参的操作
    	S.base = new SElemType[MAXSIZE];	//为栈分配一个数组
    	//为顺序栈动态分配一个最大容量为MAXSIZE的数组空间
    	//数组名为指向数组第一个元素的指针,所以将这里的指针赋值给指向栈第一个元素的栈底指针
    	if(!S.base)	//判断是否分配成功
    		exit(OVERFLOW);
    	S.top = S.base;		//初始化时SqStack S为空栈(栈内没有任何元素)
    	S.stacksize = MAXISIZE;	//将栈的大小置为最大容量MAXSIZE
    	return OK;	//返回初始化状态(是否成功完成初始化)
    }
    

    3.顺序栈的入栈操作

    入栈(进栈/压栈)是指在栈顶插入一个新元素

    Status Push(SqStack &S,	SElemType e){	//形参使用引用&,以下函数对S操作就是对实参的操作
    	if(S.top - S.base == S.stacksize)	//判断栈是否已满
    		return ERROR;
    	*S.top++ = e;	//元素e压入栈顶,栈顶指针top加1
    	//后置式递增要拷贝一个临时对象,S.top调用栈顶指针,*(S.top)解引用
    	//将e赋值给临时对象(*S.top),然后再进行自增++
    	return OK;
    }
    

    4.顺序栈的出栈操作

    出栈就是将栈顶元素删除

    Status Pop(SqStack &S, SElemType &e){	//形参使用引用&,以下函数对S和e操作就是对实参的操作
    	if(S.top == S.base)	//判断栈是否为空
    		return ERROR;
    	e = *--S.top;	//栈顶指针先减1,然后将栈顶元素赋值给e
    	return OK;
    }
    

    5.取栈顶元素

    当栈非空时,返回当前栈顶元素的值。栈顶指针保持不变

    SElemType GetTop(SqStack S){
    	if(S.top != S.base)	//栈非空
    		return *(S.top-1);	
    }
    
    展开全文
  • 顺序存储结构

    千次阅读 2018-03-30 14:45:18
    顺序存储结构 是一种重要的线性结构,可以这样讲,是线性表的一种具体形式。 这种后进先出的数据结构应用是非常广泛的。 在生活中,例如我们的浏览器,每点击一次“后退”都是退回到最近的一次浏览网页...

    栈的顺序存储结构

    栈是一种重要的线性结构,可以这样讲,栈是线性表的一种具体形式。

    栈这种后进先出的数据结构应用是非常广泛的。
    在生活中,例如我们的浏览器,每点击一次“后退”都是退回到最近的一次浏览网页。
    例如我们Word,Photoshop等的“撤销”功能也是如此。再例如我们C语言的函数,也是利用栈的基本原理实现的。

    一、定义

    栈(Stack)是一个后进先出(Last in first out,LIFO)的线性表,它要求只在表尾进行删除和插入操作。

    所谓的栈,其实也就是一个特殊的线性表(顺序表、链表),但是它在操作上有一些特殊的要求和限制:

    • 栈的元素必须“后进先出”。
    • 栈的操作只能在这个线性表的表尾进行。

    注:对于栈来说,这个表尾称为栈的栈顶(top),
    相应的表头称为栈底(bottom)。

    栈的操作

    栈的插入操作(Push),叫做进栈,也称为压栈,入栈。
    栈的删除操作(Pop),叫做出栈,也称为弹栈。

    空栈.png

    进栈.png

    出栈.png

    二、栈的存储结构

    因为栈的本质是一个线性表,线性表有两种存储形式,那么栈也有分为

    • 栈的顺序存储结构
    • 栈的链式存储结构

    特性:

    • 最开始栈中不含有任何数据,叫做空栈,此时栈顶就是栈底。
    • 然后数据从栈顶进入,栈顶栈底分离,整个栈的当前容量变大。
    • 数据出栈时从栈顶弹出,栈顶下移,整个栈的当前容量变小。

    栈的顺序存储结构.png

    定义:

    typedef int ElemType;
    typedef struct
    {
        ElemType *base;
        ElemType *top;
        int stackSize;
    }sqStack;
    

    这里定义了一个顺序存储的栈,它包含了三个元素base,top,stackSize。
    base是指向栈底的指针变量,
    top是指向栈顶的指针变量,
    stackSize指示栈的当前可使用的最大容量。

    使用ElemType* base 和 ElemType* top:

    使用指针方式.png

    或:

    typedef int ElemType;
    typedef struct
    {
        ElemType data[MAXSIZE];
        int top;        // 用于标注栈顶的位置
        int stackSize;
    }
    

    使用int:

    使用int.png

    三、栈的操作

    1.创建一个栈

    代码实现:

    #define STACK_INIT_SIZE 100
    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;
    }
    

    2.入栈操作

    入栈操作又叫压栈操作,就是向栈中存放数据。
    入栈操作要在栈顶进行,每次向栈中压入一个数据,top指针就要+1,直到栈满为止。

    代码实现:

    #define SATCKINCREMENT 10
    
    Push(sqStack *s, ElemType 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 = s->stackSize + STACKINCREMENT; // 设置栈的最大容量
        }
    
        *(s->top) = e;
        s->top++;
    }
    

    3.出栈操作

    出栈操作就是在栈顶取出数据,栈顶指针随之下移的操作。
    每当从栈内弹出一个数据,栈的当前容量就-1。

    代码实现:

    Pop(sqStack *s, ElemType *e)
    {
        if( s->top == s->base ){  // 栈已空
            return;
        }
        *e = *--(s->top);
    }
    

    出栈示意图.png

    三、栈的其他操作

    1.清空一个栈

    清空一个栈,就是将栈中的元素全部作废,但栈本身物理空间并不发生改变(不是销毁)。

    思路:
    我们只要将s->top的内容赋值为s->base即可,
    这样s->base等于s->top,也就表明这个栈是空的了。
    这个原理跟高级格式化只是但单纯地清空文件列表而没有覆盖硬盘的原理是一样的。

    代码实现:

    ClearStack(sqStack *s){
        s->top = s->base;
    }
    

    2.销毁一个栈

    销毁一个栈与清空一个栈不同,销毁一个栈是要释放掉该栈所占据的物理内存空间,因此不要把销毁一个栈与清空一个栈这两种操作混淆。

    代码实现:

    DestroyStack(sqStack *s){
        int i, len;
        len = s->stackSize;
        for( i=0; i < len; i++ ){
            free( s->base );
            s->base++;
        }
        s->base = s->top = NULL;
        s->stackSize = 0;
    }
    

    四、计算栈的当前容量

    计算栈的当前容量也就是计算栈中元素的个数,因此只要返回s.top-s.base即可。

    就是将两个指针相减,两个地址相减,减完之后并不是两个地址的差;如果两个指针是指向整型的,那么相减之后是他们中间隔了几个元素;实际上是相当于两个地址相减之后再除以该元素所占的空间;例如整型是占4个字节,那么就是地址相减之后除以4,最后得到中间有多少个元素。(注意两个指针的类型必须相同)

    注意:指针可以++ 或–;指针之间可以相减,但是不能相加。

    注意:栈的最大容量是指该栈占据内存空间的大小,(能够容纳多少数据)其值是s.stackSize,它与栈的当前容量不是一个概念。

    代码实现:

    int StackLen(sqStack s)
    {
        return(s.top – s.base);  // 重点
    }
    
    展开全文
  • 在之前讲解了线性表的链式存储、顺序存储以及静态链表,循环链表和双向链表我们只需了解即可,接下来我们讲解线性表的应用“ 是限定仅在表尾进行插入和删除操作的线性表 我们吧允许插入和删除的一端称为...

    在之前讲解了线性表的链式存储顺序存储以及静态链表循环链表和双向链表我们只需了解即可,接下来我们讲解线性表的应用“

    栈是限定仅在表尾进行插入和删除操作的线性表

    我们吧允许插入和删除的一端称为栈顶,另一端称为栈底,不含任何数据元素的栈我们称为空栈,栈又称为后进先出的线性表,简称为LIFO结构,可以理解为给枪的弹夹装子弹,后装的子弹会被先发射出去

    既然栈是线性表的一种,线性表有顺序存储和链式存储两种结构,那么栈也就有这两种结构

    栈的顺序存储结构

    在栈的顺序存储中我们用下标为0的一端来作为栈底,定义一个变量top变量来指示栈顶元素在数组中的位置,这个top就类似游标卡尺的游标,可以来回移动,top的值必须小于栈的长度StackSize,当栈存在一个元素时,top等于0,因此通常把空栈的判定条件定位top等于-1

    栈的结构

    # define MAXSIZE 1000
    # define OK 1
    # define ERROR 0
    # define TRUE 1
    # define FALSE 0
    
    typedef int SElemType;           //SElemType就是线性表中的元素的类型,这里设置为int
    typedef int Status;
    typedef struct{
    	SElemType data[MAXSIZE];
    	int top;
    } SqStack;
    

    进栈操作

    Status Push(SqStack *S, SElemType e){
    	if(S->top == MAXSIZE - 1){     //栈满 
    		return ERROR;
    	}
    	S->top++;                      //栈顶指针增加1 
    	S->data[S->top] = e;           //将新元素放入栈顶指针所指向空间中 
    	return OK;
    }
    

    出栈操作

    Status Pop(SqStack *S, SElemType *e){
    	if(S->top == -1){
    		return ERROR;
    	}
    	*e =  S->data[S->top];          //取出栈顶元素 
    	S->top--;                       //栈顶指针减少1 
    	return OK;
    }
    

    进栈和出栈这两种操作都是将之前的线性表的顺序存储进行简单的改进,非常简单,这里不做过多讲解

    两栈共享空间

    栈的顺序存储非常方便,只从栈顶进栈和出栈,不存在插入数据后对后续数据的移动,但是和线性表的顺序存储存在相同的问题,就是栈的大小必须提前规定好,如果空间不够用了就必须使用编程手段来对空间进行扩充

    如果现在有两个栈,可能会存在一种情况:一个栈已经满了,再存入数据就溢出了,而另外一个栈还有剩余的存储空间,我们怎样解决这样的问题?

    我们可以使用一个数组来存储两个栈,但是需要一些小技巧:我们让数组的两个端点来分别作为两个栈的栈底,这样我们在两个栈中增加元素时两个栈顶指针就是从数组的两端点想中间移动,只要两个栈顶指针不相遇那么我们就可以一直向栈中存储数据

    这里我们定义两个栈,分别为栈1和栈2,栈1为空时top1等于-1,栈2为空时top2等于n,n就是我们预先定义的数组长度,两栈的共享空间定义为:

    typedef struct{
    	SElemType data[MAXSIZE];
    	int top1;
    	int top2;
    } SqDoubleStack;
    

    当我们在这个栈中进行push时,需要一个判断是栈1还是栈2的参数stackNumber,push方法实现如下:

    Status Push(SqDoubleStack *S, SElemType e, int stackNumber){
    	if(S->top1 + 1 == S->top2){     //栈已满 
    		return ERROR;
    	}
    	if(stackNumber == 1){
    		S->data[++S->top1] = e;
    	}else if(stackNumber == 2){
    		S->data[--S->top2] = e;
    	}
    	return OK;
    }
    

    在编写push的代码实现的时候主要需要注意的是就是判断栈满,若栈不满则后续的操作很简单,不需要担心两个栈顶指针溢出

    接下来讲解pop操作的代码实现:

    Status Pop(SqDoubleStack *S, SElemType *e, int stackNumber){
    	if(stackNumber == 1){
    		if(S->top1 == -1){
    			return ERROR;
    		}
    		*e = S->data[S->top1--];
    	}
    	else if(stackNumber == 2){
    		if(S->top2 == MAXSIZE){
    			return ERROR;
    		}
    		*e = S->data[S->top2++];
    	}
    }
    

    Pop的代码实现主要需要注意的是判断栈是否空,若栈不空则后续操作很简单,不需要担心两个栈顶指针溢出

    展开全文
  • 一、的概念 1.1 的定义 (Stack) :是只允许在一端进行插入或删除操作的线性表。首 先是一种线性表,但限定这种线性表只能在某一端进行插入和删除 操作,如图所示:子弹先进后出或后进先出 的示意图: ...
  • 顺序结构,包括初始化,压栈,出栈,遍历等
  • 顺序存储结构 下标为 0 的一段作为底比较好,因为首元素都存在底,变化量最小。 /* 顺序结构 */ typedef struct { SElemType data[MAXSIZE]; int top; /* 用于栈顶指针 */ }SqStack; 如图所示,结构...
  • 实验三 顺序的实现 实验类型 验证性 实验学时2学时 一实验目的 掌握顺序的基本操作如进栈出栈判断空和满取栈顶元素等运算在顺序存储结构上的运算并能够运用的基本操作解决问题实现相应算法 二实验要求 ...
  • 顺序存储结构及其基本操作的实现比较简单,所以我在这里会很少写实现思路。(博主真心不知道写啥) 头文件,宏定义,结构体初始化销毁清空栈栈判空求长度求栈顶元素插入元素删除栈顶元素输出所有元素十...
  • 栈顺序存储结构利用一个大数组,相当于简化了的线性表,线性表具有查找、插入、删除等功能,而栈则简化为只包括压入、弹出这种更有针对性的功能。下面是自己写的栈的顺序存储C++模板类源代码: //linearstack.h #...
  • 顺序存储结构(C语言版)

    千次阅读 2021-04-19 19:39:56
    #include <stdio.h> #include <stdlib.h> // 初始长度 #define STACK_INIT_SIZE ...// 顺序存储结构 typedef struct { // 栈顶指针 ElemType *top; // 底指针 ElemType *base; // 长 int s
  • 顺序存储结构实现(四)

    千次阅读 2018-11-17 11:35:15
    是一种只限定在表尾进行插入和删除的线性表,这里的表尾指的是栈顶,而不是尾,所以又被称为先进后出的线性表,也就是说是一个类似于木桶之类存在,先放进去的后拿出来,我们通常用一个 我们通常用一个变量...
  • 文章目录概念进栈出栈变化形式顺序存储结构进栈操作出栈操作顺序代码 概念 (stack)是限定仅在表头和表尾进行插入和删除操作的线性表。 我们把允许插入和删除的一端称为栈顶(top),另一端称为底...
  • 2. 掌握顺序存储结构和链式存储结构的实现;3. 熟悉队列的特点(先进先出)及队列的抽象类定义;4. 掌握顺序存储结构和链式存储结构的实现;二、实验要求1. 复习课本中有关和队列的知识;2. 用C++...
  • 和队列的相同点和不同点: 相同点:和队列是两种重要的数据结构,也是两种特殊的线性表结构。从数据的逻辑角度看,和队列是线性表;从操作的角度来看,和队列的基本操作是线性表基本操作的...顺序存储表示
  • //C语言--数据结构--和队列 顺序(顺序存储结构) #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #include&lt;string.h&gt;  #include &lt;iostream&gt; #include ...
  • 一、的定义定义:...又称为“后进先出(Last In First Out,简称LIFO)的线性表”,简称为LIFO结构的插入操作,称为进栈/入栈/压栈。的删除操作,称为出栈/弹。不过要注意的是,最先进的元素不代表...
  • -顺序存储结构(C语言实现)参考:大话数据结构(程杰) 博客:http://cj723.cnblogs.com/ 豆瓣:https://book.douban.com/subject/6424904/主要包括: - 顺序定义 - 初始化 - 置空 - 判断是否为空 -...
  • 顺序存储与实现。采用顺序存储的方式实现,并实现了一些基本功能,包括创建、销毁、清空、出栈、入栈等一些常规的操作。其中包含的头文件dm01_SeqList.h保存在《线性表的顺序存储与实现》资源中。
  • 的定义 (stack )又称堆栈,它是运算受限的线性表。 其限制是仅允许在表的一端进行插入和删除操作,不允许在其他任何位置进行插入、查找、删除等操作。 表中进行插入、删除操作的一端称为 栈顶(top) ,栈顶...
  • 实现线性表的顺序存储结构、链式存储结构,以及定义在上述结构的基本操作,顺序存储结构、链式存储结构,以及定义在上述结构的基本操作
  • 栈顺序存储

    2019-03-16 21:18:11
    一个较为完整的栈顺序存储,包含了很多函数及基础算法。main可运行测试。
  • c++实现顺序存储结构的方法和实现顺序线性表的操作差不多,甚至要比实现线性表还要简单一点,因为可以认为是只允许在表尾(栈顶)进行插入和删除操作的线性表,只在表尾就很方便操作 话不多说,直接代码: ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 172,491
精华内容 68,996
关键字:

栈的顺序存储结构

友情链接: 照相机.rar