数据结构栈-C语言实现链表

超、凢脫俗 2021-12-03 04:57 383阅读 0赞

## 最近复习数据结构，遇到一道算法题，从尾打印链表，使用的是入栈操作，因为栈属于“先进后出”，正好符合这个题目；借此也把栈复习一下； ##

## 1.什么是栈？ ##

### **答：保存局部变量。栈上的内容旨在函数的范围内存在，当函数运行结束，这些内容也会自动销毁。其特点是效率高，但空间大小有限。** ###

### \*\* 栈是限定仅在表尾进行插入或删除操作的线性表。因此，对栈来说，表尾端有其特殊含义，称为栈顶，相应地表头端称为栈底，不含元素的空表称为空栈。\*\* ###

（手残档 不会画图 凑合看，求推荐画图软件！！！！！！！）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5Mzk3MTY1_size_16_color_FFFFFF_t_70]

## 2. 栈的表示和实现 ##

### 顺序栈；即栈的顺序存储结构是利用一组地址连续的存储单元依次存放来自栈底到栈顶的数据元素，同时附设指针 ###

## 3.代码如下： ##

### 定义结构体如下： ###

/*结构体定义 s_Data 栈中数据 s_Top 指针指向栈顶 s_Bottom 指针指向栈底 s_Next 指针指向上一节点 */
    typedef struct StackStur
    { 
        int s_Data;
        struct StackStur* s_Top;
    	struct StackStur* s_Bottom;
    	struct StackStur* s_Next;
    
    }NonPointer,*Pointer;

### 1.创建一个空栈 ###

/*创建一个空栈*/
    void CreateStack(Pointer variable)
    { 
    	variable->s_Bottom=(Pointer)malloc(sizeof(NonPointer));
        if(NULL==variable->s_Bottom)    //判断内存是否分配成功
    	{ 
    		printf("Error in allocating memory!\r\n");
    	    exit(-1);
    	}
        variable->s_Top=variable->s_Bottom;
        variable->s_Data=0;
        variable->s_Top->s_Next=NULL;   //定义为空 防止出现野指针
    	printf("Create the stack sucessful!");
    }

### 2.入栈函数 ###

/*入栈函数*/
    void PushStack(Pointer variable,int value)
    { 
    	Pointer s_storage=(Pointer)malloc(sizeof(NonPointer));
        if(NULL==s_storage)    //判断内存是否分配成功
    	{ 
    		printf("Error in allocating memory!\r\n");
    	    exit(-1);
    	}
    	s_storage->s_Next=variable->s_Top; //修改节点的指针域
        s_storage->s_Data=value;
        variable->s_Top=s_storage;   //修改栈顶指针，使其指向栈顶元素
        printf("Push to stack sucessful!\r\n");
    	printf("The Value is %d\r\n",s_storage->s_Data);
    
    }

### 3.出栈函数 ###

/*出栈函数*/
    void PopStack(Pointer variable,int *value)
    { 
    
        Pointer s_Popstorage=variable->s_Top;  // 建立一个临时节点指向栈顶节点
    	if(variable->s_Bottom==variable->s_Top)// 判断栈是否为空
    	{ 
    		printf("Pop Stack Fail Stack is NULL!\r\n");
    	}
        *value=s_Popstorage->s_Data;// 把栈顶节点元素弹出，地址放到变量value中
        variable->s_Top=s_Popstorage->s_Next; // 把栈顶指针指向上一个栈节点
        free(s_Popstorage);   // 释放节点内存，防止内存空间泄漏
        s_Popstorage=NULL;   // 防止产生野指针
    	printf("The %d Pop stack!\r\n",*value);
    
    }

### 4.空栈判断函数 ###

// 定义判断栈是否为空函数
    bool StackEmpty(Pointer variable)
    { 
    	if(variable->s_Top==variable->s_Bottom)
    	{ 
    		printf("The stack is empty!\r\n");
    		return true;
    	}
    	else
    		return false;
    }

### 5.遍历栈，打印出来 ###

/*定义遍历栈 函数*/
    void StackTraver(Pointer variable)
    { 
    	Pointer s_Traver=variable->s_Top;  // 建立一个临时节点指针，初始化时指向栈顶
        if(StackEmpty(variable))
    	{ 
    		printf("Traversing the stack is fail!\r\n");
    		exit(-1);
    	}
    	while(s_Traver!=variable->s_Bottom)
    	{ 
    		printf("Traver result is %d\r\n",s_Traver->s_Data);
    		s_Traver=s_Traver->s_Next;
    	}
    }

### 6.清空栈函数 ###

/*栈清空函数*/
    void StackClear(Pointer variable)
    { 
        Pointer s_start=variable->s_Top;
        Pointer s_end=NULL;
        if(StackEmpty(variable))
    	{ 
    		printf("Clear the stack is fail!\r\n");
    		exit(-1);
    	}
    	while(s_start!=variable->s_Bottom)
    	{ 
    		s_end=s_start->s_Next;
    		free(s_start);
            s_start=s_end;        
    	}
        variable->s_Bottom=variable->s_Top;
    	printf("The Stack is clear!\r\n");
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5Mzk3MTY1_size_16_color_FFFFFF_t_70]: /images/20211203/bcfdb515a8b84b8588d4cbf962c3c2ed.png