精华内容
下载资源
问答
  • 栈的链式结构

    2021-03-30 16:53:42
    栈的链式结构,简称为链栈,其本质就是一种链表加栈的抽象数据结构。在创建一个链栈的时候我们首先要定义一个链表。 typedef struct Node { int date;//数据域 struct Node* next;//指针域 }List; 此时链表的创建...

    栈的链式结构,简称为链栈,其本质就是一种链表加栈的抽象数据结构。在创建一个链栈的时候我们首先要定义一个链表。

    typedef struct Node
    {
    	int date;//数据域
    	struct Node* next;//指针域
    }List;
    

    此时链表的创建,插入就不详述,直接代码略过,值得一提的是,因为栈是一种先进后出(First In Last out)的一种数据结构,所以链表的插入(即为栈的插入)我们采用头插法。

    //创建表头
    List* creatList()
    {
    	List* L = (List*)malloc(sizeof(List));
    	L->next = NULL;
    	return L;
    }
    //创建节点
    List* creatNode(int date)
    {
    	List* newNode = (List*)malloc(sizeof(List));
    	newNode->date = date;
    	newNode->next = NULL;
    	return newNode;
    }
    //插入节点
    void insertNodeByHead(List* L, int date)
    {
    	List* newNode = creatNode(date);
    	newNode->next = L->next;
    	L->next = newNode;
    }
    

    接下来,我们再来定义一个链栈

    typedef struct linkStack
    {
    	List* top;//充当链表的表头
    	int stackSize;//表示链栈的大小
    }LinkStack;
    

    然后链栈的创建即为初始化

    LinkStack* creatStack()
    {
    	LinkStack* ListStack = (LinkStack*)malloc(sizeof(LinkStack));
    	ListStack->stackSize = 0;//链栈初始大小为0
    	ListStack->top = creatList();//栈顶指针即为链表表头
    	return ListStack;
    }
    

    对栈的插入,即为对该栈顶指针(链表表头)的插入

    void pushLinkStack(LinkStack* ListStack, int date)
    {
    	insertNodeByHean(ListStack->top, date);
    	ListStack->stackSize++;
    }
    

    对于栈的删除,因为栈只能从顶端开始进行删除,所以出栈就只需要把栈顶指针往下移一位即可

    void popLinkStack(LinkStack* ListStack)
    {
    	if (ListStack->stackSize == 0)
    	{
    		printf("空栈\n");
    		return;
    	}
    	else
    	{
    		List* L = ListStack->top;//存储删除的栈顶结点
    		ListStack->top = ListStack->top->next;//栈顶指针往下移一位
    		ListStack->stackSize--;
    		free(L);//删除该栈顶结点
    		return;
    	}
    }
    

    对于链栈而已,基本不存在栈满的情况,除非是内存已经没有可以使用的空间,而对于空栈来说,就是top=NULL的情况。
    所以顺序栈与链栈的插入与删除,时间复杂度是一样的均为O(1),但在空间上,如同线性表一样,顺序栈的大小必须先规定好,如果栈的使用过程中,元素不可控,这时候就需要用链栈了

    展开全文
  • 栈的链式结构实现

    2016-01-22 22:26:57
    /* 2 栈的链式结构实现 */ #include #include #include typedef int TYPE;//元素类型别名 //声明顺序栈结构体 typedef struct stack { TYPE data;//存储结点数据 struct stack* next;//记录后继结点的地址 }...
    				/* 2 栈的链式结构实现 */
    
    #include <stdio.h>
    #include <stdbool.h>
    #include <stdlib.h>
    
    typedef int TYPE;//元素类型别名
    
    //声明顺序栈结构体
    typedef struct stack
    {
    	TYPE data;//存储结点数据
    	struct stack* next;//记录后继结点的地址
    }stack;
    
    void init(stack**);//初始化
    
    void push(stack**,TYPE);//入栈
    
    TYPE pop(stack**);//出栈
    
    void clear(stack**);//清空
    
    bool isEmpty(stack*);//判断栈是否已满
    
    int length(stack*);//返回栈的元素个数
    
    void ergodic(stack*);//遍历栈中元素
    
    int search(stack*,TYPE);//搜索,返回具栈顶首次出现位置
    
    int main()
    {
    	stack* top;
    	init(&top);
    
    	//入栈测试
    	int count=0;//记录入栈元素个数
    	printf("输入入栈元素个数:");
    	scanf("%d",&count);
    	int elem;//记录单个入栈元素
    	printf("输入%d个元素:",count);
    	while(count)
    	{
    		scanf("%d",&elem);
    		push(&top,elem);
    		count--;
    	}
    
    	//遍历测试
    	printf("遍历栈中元素:");
    	ergodic(top);
    
    	scanf("%*[^\n]");
    	scanf("%*c");
    
    	//搜索测试
    	printf("输入要搜索的元素:");
    	scanf("%d",&elem);
    	int pos =search(top,elem);
    	if(pos)
    	{
    		printf("查找成功,%d在从栈顶开始第%d个元素\n",elem,pos);
    	}
    	else
    		printf("查找失败!\n");
    
    	//栈长度测试
    	count = length(top);
    	
    	//栈清空测试  栈清空测试与出栈测试不能同时进行
    	//clear(&top);
    	
    	//出栈测试
    	printf("栈中有%d个元素\n",count);
    	while(count--)
    		printf("出栈元素是:%d\n",pop(&top));
    	
    	//栈长度测试
    	printf("栈中有%d个元素\n",length(top));
    
    	return 0;
    }
    
    //栈初始化
    //因为要更新栈顶指针本身的值,所以要用二级指针
    void init(stack** ss)
    {
    	*ss=NULL;
    }
    
    //入栈操作
    //因为要更新栈顶指针本身的值,所以要用二级指针
    void push(stack** ss,TYPE e)
    {
    	stack* p=(stack*)malloc(sizeof(struct stack));
    	if(p)
    	{
    		p->data = e;
    		p->next=*ss;
    		*ss=p;
    	}
    	else
    		printf("内存申请失败,缓冲区将清空!\n");
    }
    
    //出栈操作
    //因为要更新栈顶指针本身的值,所以用二级指针
    TYPE pop(stack** ss)
    {
    	if(!isEmpty(*ss))//栈不为空
    	{
    		stack* q=*ss;//记录原来的栈顶指针
    		int data=q->data;//获取栈顶元素值
    		*ss=(*ss)->next;//更新栈顶指针
    		free(q);//销毁原来栈顶元素
    		q=NULL;
    		return data;
    	}
    }
    
    
    //判断是否为空
    bool isEmpty(stack* s)
    {
    	return s==NULL;
    }
    
    //返回栈的长度
    int length(stack* s)
    {
    	int count=0;
    	while(s)
    	{
    		s = s->next;
    		count++;
    	}
    	return count;
    }
    
    
    //遍历栈
    void ergodic(stack* s)
    {
    	while(s)
    	{
    		printf("%d ",s->data);
    		s=s->next;
    	}
    		printf("\n");
    }
    
    //搜索栈中元素
    //返回元素距离栈顶的位置,如果有多个相同值,则返回首次出现的位置
    int search(stack* s,TYPE e)
    {
    	int pos=0;
    	while(s)
    	{
    		if(s->data==e)
    		{
    			pos++;
    			break;//找到就停止继续寻找
    		}
    			pos++;
    			s=s->next;
    	}
    	return pos;
    }
    
    //清空栈
    //因为要更新栈顶指针本身的值,所以要用二级指针
    void clear(stack** ss)
    {
    	while(*ss)
    	{
    		stack* q=*ss;
    		*ss = (*ss)->next;
    		free(q);
    		q=NULL;
    	}
    }
    
    

    展开全文
  • 数据结构_________栈的链式结构表示 #include <iostream> #include <cstdlib> #include <algorithm> #include <malloc.h> using namespace std; #define OK 1 #define ERROR -1 #define ...

    数据结构_________栈的链式结构表示

    #include <iostream>
    #include <cstdlib>
    #include <algorithm>
    #include <malloc.h>
    using namespace std;
    #define OK  1
    #define ERROR -1
    #define TURE 1
    #define FALSE 0
    typedef int Status;
    typedef int SElemType;
    typedef struct node
    {
     SElemType date;
     int stacklength;
     struct node *next;
    }SNode,*SList;
    //构造一个空栈S 
    Status InitStack(SList &S);
    //销毁栈S,栈S不再存在 
    Status DestoryStack(SList &S);
    //把s置为空栈 
    Status ClearStack(SList &S);
    //若s为空战则返回ture,否则返回FALSE 
    Status StackEmpty(SList S);
    //获取栈顶元素,若栈不为空,则用e返回s的栈顶元素,并返回OK,否则返回ERROR
    Status GetTop(SList S, SElemType &e);
    //插入元素e作为新的栈顶元素
    Status Push(SList &S, SElemType e);
    //若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR
    Status Pop(SList &S, SElemType &e);
    //读出元素
    Status vi(SElemType e);
    //从栈底到栈顶依次对栈中的每个元素调用函数visit(). 一旦visit()失败, 则操作失败
    Status StackTraverse(SList S, Status(*visit)(SElemType));
    int main()
    {
     SList S;
     InitStack(S);
     if(StackEmpty(S))
     {
      printf("创建栈之后,栈为空"); 
     }
     for(int i = 0;i<6;i++)
     {
      Push(S,i);
     }
     if(!StackEmpty(S))
     {
      printf("添加元素之后,栈不为空\n");
     }
     StackTraverse(S,vi); //遍历栈中元素 
     printf("栈的长度:%d\n",S->stacklength);
     SElemType e;
     GetTop(S,e);
     printf("栈顶元素:%d\n",e);
     Pop(S,e);
     printf("删除的栈顶元素:%d\n",e);
     StackTraverse(S,vi);//遍历数组元素
     ClearStack(S);
     if(StackEmpty(S))
     {
      printf("清空栈之后\n"); 
      }
      DestoryStack(S);
       return 0;
     }
    //构造一个空栈
     Status InitStack(SList &S)
     {
      S = (SList)malloc(sizeof(SNode));
      if(!S)
      {
       printf("存储分配失败!\n");
       return ERROR;
      }
      S->next = NULL;
      S->stacklength = 0;
      return OK;
     }
     //销毁栈S,栈S不再存在
     Status DestoryStack(SList &S)
     {
      S->stacklength = 0;  //栈以销毁,空间以释放,当前栈中元素为0
      while(S)
      {
       SList e = S;
       free(e);
       S = S->next; 
       } 
       return OK;
     }
    //把s置为空栈
     Status ClearStack(SList &S)
     {
      while(S->next)
      {
       SList e = S;
       free(e);
       S=S->next;
      }
      S->next = NULL;
      return OK;
      }
      //若S为空栈,则放回ture,否则返回false
      Status StackEmpty(SList S)
      {
       if(!S->next)
       {
        return TURE;
       }
       return FALSE;
       } 
       /*获取栈顶元素,
       若栈不为空,则用e返回S的栈顶元素,并返回OK,
       否则返回ERROR*/
       Status GetTop(SList S,SElemType &e)
       {
         if(!S->next)
         {
          return ERROR;
       } 
       e = S ->next->date;
       return OK;
     }
     //插入元素e作为新的栈顶元素
     Status Push(SList &S,SElemType e)
     {
      SList q = (SList)malloc(sizeof(SNode));
      q->date = e;
      q->next = S->next;
      S->next = q;
      S->stacklength++;
      return OK;
      } 
      //若栈不空,则删除S的栈顶元素,用e返回值,并返回OK ,否则 返回ERROR 
     Status Pop(SList &S,SElemType &e)
     {
      if(!S->next)
      {
       return ERROR;
      }
      S->stacklength--;
      SList q = S->next;
      S = q->next;
      e = q->date;
      free(q);
      return OK; 
      } 
     //读出元素
     Status StackTraverse(SList S,Status(*visit)(SElemType)) 
     {
      SElemType e;
      printf("遍历数组元素:");
      SList p= S->next;
      while(p)
      {
       e = p->date;
       p = p->next;
       if(!(*visit)(e))
       {
        return ERROR;
       }
       printf("\n");
       return OK;
       } 
     }
    
    
    
    展开全文
  • 今天给大家介绍栈的链式结构,用dev-c++4.9.9.2调试通过,少废话直接上代码: 数据结构体存放文件stacklist.h文件如下 #ifndef _STACKLIST_H_ #define _STACKLIST_H_ typedef struct _Node { int data; ...
        今天给大家介绍栈的链式结构,用dev-c++4.9.9.2调试通过,少废话直接上代码:

    数据结构体存放文件stacklist.h文件如下

    #ifndef _STACKLIST_H_
    #define _STACKLIST_H_
    
    typedef struct _Node
    {
        int data;
        
        struct _Node *pre;
        struct _Node *next;
    }Node,*pNode;
    
    typedef struct _Stack_Header
    {
        struct _Node *botton;
        struct _Node *top;
        int  size;    
    }Stack_Header,*pStack_Header;
    
    pStack_Header init_stack_list(void);
    pNode push_node(pStack_Header plist,int data);
    pNode pop_node(pStack_Header plist);
    int print_stack_list(pStack_Header plist);
    
    #endif
    


    函数存放文件stacklist.c

    /*******************************
    时间:2014.12.12
    作者:XIAO_PING_PING
    内容:栈的链式数据结构
    功能:学习些数据结构 
          
    ********************************/
    
    #include <string.h>
    #include <stdlib.h>
    #include <conio.h>
    
    #include "stacklist.h"
    
    /*初始化一个堆栈链表*/
    pStack_Header init_stack_list(void)
    {
        pStack_Header plist;
        pNode p;
        
        plist = (Stack_Header *)malloc(sizeof(Stack_Header));
        plist->botton = NULL;
        plist->top = NULL;
        plist->size = 0;
        
        return plist;              
    }
    
    /*往堆栈里面添加节点,数据data*/
    pNode push_node(pStack_Header plist,int data)
    {
        pNode p;
        
        p = (Node *)malloc(sizeof(Node));
        p->data = data;
        p->next = NULL;
        p->pre = plist->top;
        
        if((plist->top == NULL) && (plist->botton == NULL)) 
        {
            plist->top = p;
            plist->botton = p;
            plist->size = 1; 
            printf("入栈第1个节点\n");
            return  p;            
        }
        
        plist->top->next = p;
        plist->top = p;
        plist->size += 1;
        printf("入栈第%d个节点\n",plist->size);
        
        return plist->top;
    }
    
    /*出栈删除节点*/
    pNode pop_node(pStack_Header plist)
    {
        pNode p;
        
        if(0 == plist->size)
        {
            printf("栈区没有节点,无法完成出栈\n");
            
            return plist->top;                 
        }    
        
        p = plist->top;
        plist->top = plist->top->pre;  
        if(NULL != plist->top)
        {
            plist->top->next = NULL;
        }
        else
        {
            plist->botton = NULL;    
        }
        free(p); 
        
        plist->size -= 1;
        printf("出栈第%d个节点\n",plist->size + 1);
        
        return plist->top;
    }
    
    /*打印入栈数据*/
    int print_stack_list(pStack_Header plist)
    {
        pNode p;
        
        if((plist->top == plist->botton) && (0 == plist->size))
        {
            printf("栈区没有节点\n");
            
            return -1;                 
        }   
        
        p = plist->botton;
        printf("从栈底开始打印数据\n");
        while(plist->top != p)
        {
            printf("%d  ",p->data) ;
            p = p->next;      
        }
        printf("%d  ",p->data) ;
        printf("\n打印完毕\n");
        return 0;
    } 
     
    


    测试文件test.c

    #include <string.h>
    #include <stdlib.h>
    #include <conio.h>
    
    #include "stacklist.h" 
    
    int main()
    {
        pStack_Header plist;
    
        plist = init_stack_list();
        
        push_node(plist,13);
        push_node(plist,1);
        push_node(plist,232);
        push_node(plist,143);
        print_stack_list(plist);  
        
        pop_node(plist);  
        pop_node(plist);  
        pop_node(plist);  
        //pop_node(plist);  
        //pop_node(plist); 
        printf("\n");
        print_stack_list(plist);   
        
        getch();
    }
    


    运行结果如下图:

     

    展开全文
  • 栈的链式结构及实现

    2019-09-17 17:19:08
    1.是一个,栈顶进出元素,单链表有头指针,栈顶也有指针,将它们指针合二为一,将栈顶放在单链表头部比较合适。 2.单链表头结点链栈不需要 进栈 栈顶在头部相当于对头添加元素 public void push(E e) { ...
  • 栈的链式 结构实现

    2016-06-23 14:46:51
    1.这个继承了线性链表特性。 #ifndef _LINKLIST_H_ #define _LINKLIST_H_ typedef void LinkList; typedef struct _tag_LinkListNode LinkListNode; struct _tag_LinkListNode { LinkListNode* next; }; ...
  • 除了我之前一篇文章中介绍的栈的顺序存储,就是底层使用一个数组存储数据元素。其实也是可以使用单链表存储栈中的数据, 然后使用一个top引用来记录栈顶元素进栈:top指向新添加的元素, 新元素的引用指向原来的栈顶...
  • 下面是用链栈做括号匹配,链栈作为头文件,运行时应先将头文件导入 #include&lt;stdio.h&gt; #include&lt;stdlib.h&gt; #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef int ...
  • #include #include typedef int Elemtype; typedef struct StackNode{ Elemtype data; struct StackNode *next;... case '5':printf("栈的当前长度为%d\n",S.size);break; } } return 0; }
  • 链栈 不需要头节点 判断栈为空的条件就是top==NULL typedef struct StackNode { struct StackNode * next; int data; }StackNode;...typedef struct Stack ...栈的初始化 void initStack(Stack * ...
  • 链栈(栈的链式结构)--基本操作

    千次阅读 2018-12-31 19:59:07
    链栈:我是以链尾为底,链头为栈顶,采用头插法入栈,当然并非这一种做法。 见代码(有注释): #include&lt;stdio.h&gt; #include&lt;stdlib.h&gt; #define OK 1 #define ERROR -1 typedef int ...
  • 栈的数据结构就不多说了,后进先出,只有一个出口。最典型的应用就是中缀表达式转后缀表达式,因为计算机不能识别人类所认知的中缀表达式,逆波兰式多用于编译器实现、自然语言处理这些常用的领域。下面介绍中缀转...
  • printf("请输入入栈数据个数:"); scanf("%d",&n); printf("请输入数据:"); for(i=0;i;i++) { scanf("%d",&x); push_link(p,x); } while(p) { printf("%d",p->data); pop_link(p); } return 0; } 从测试各函数来...
  • /// 栈的链式结构基本实现(非泛型) /// public class Stack { /// /// 元素的下标 /// public Node index; /// /// 统计个数 /// private int count; public int Count { get { ...
  • 栈的链式存储结构

    2020-03-19 21:03:19
    栈的链式结构定义有两种说法: 一种是直接用一个结构体表示 另一种就是将栈的栈顶指针和栈的大小额外用结构体定义。使用的时候将整个结构体引入 typedef struct stack_node{ int data;//数据域 struct stack_node * ...
  • 因为我们已经学过了线性表的链式存储结构,所以我们可以基于线性表的链式存储结构来学习栈的链式存储结构队列的链式存储结构,说到这里必须要提一下栈和队列存储元素的特点是什么?当然是栈先进后出,队列先进先出咯...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,169
精华内容 1,667
关键字:

栈的链式结构