数据结构和算法（五）

刺骨的言语ヽ痛彻心扉 2022-12-13 12:54 206阅读 0赞

链式栈  
=============   
     1.  不论是顺序栈还是链式栈，写法并不唯一  
               struct  linkstack  
              \{  
                     int  data; //真实数据  
                     struct  linkstack \*top;  //指向当前链式栈的栈顶节点位置  
                     struct  linkstack \*next; //指向下一个节点  
             \}  
     2. 栈的作用  
              操作系统中的栈内存的实现

练习：  
       1.   动手实现链式栈的初始化，压栈，出栈，销毁

队列  
===============  
      1. 顺序队列和链式队列  
      2. 特点:  先进先出  
         基本操作：  
                初始化  
                入队  
                出队  
                销毁  
             struct  queue  //顺序队列  
             \{  
                    int a\[20\];  
                    int qhead; //标记队首位置  方便出队操作  
                    int qtail;  //标记队尾位置  方便入队操作  
            \} ;  
            struct  linkque  //链式队列  
           \{  
                  int  data;  
                  //指针标记队首或者队尾位置     
                  struct  linkque \*next;  
          \};  
       3. 队列的应用  
                  cpu的调度算法： cpu在执行多个进程的时候依照什么规则去执行  
                                            先进先出的调度策略(用的队列这种数据结构实现的)

线性结构(线性表)和非线性结构  
=============  
     线性结构：任意一个数据，有且仅有一个前驱和一个后继（除开起始位置和末尾位置）    
                     前驱：前面一个数据  
                     后继:  后面一个数据  
                     比如： 顺序表    链表   
    非线性结构：不满足线性结构要求的  
                     比如： 树   图

树和二叉树  
=============  
     1. 树有关的理论概念  
             根节点：最顶层的那个节点就是根节点，整个树的根节点只有一个  
             子树：  
             节点：  
             树的度：由这棵树中节点度数最大的来决定  
             节点的度：该节点分了多少个树杈，树杈的数目，就是节点的度数  
             叶子节点：一个节点的度数为0，它就是叶子节点  
       二叉树：每个节点度数最多不能超过2，这棵树就是二叉树  
             二叉树是严格区分左右的    
             左孩子(左子树)：  
             右孩子(右子树)：  
             树的深度(树的高度): 树有多少层，深度就是多少  
             满二叉树：除了最后一层的叶子节点以外，其它的节点度数全部都是2  
             完全二叉树：从上到下，从左到右连续不能间断  
                                完全二叉树的叶子节点只能出现在最后一层或者倒数第二层  
        二叉树的一些数学上规律：  
             一个节点数目是n的满二叉树，它的分支数目是多少？？    
             一个节点数目是n的满二叉树，它的叶子节点是多少？

作业：  
       1.  用队列保存  员工信息。（员工号、姓名、工资）  
            输入正整数，添加员工信息(入队)，用这个正整数表示员工号；输入负整数，出队（队首），打印该员工的所有信息；否则(你输入既不是正数也不是负数)就退出程序

## 链式栈 ##

#include "myhead.h"
    /*
    	所有的节点都包含有top指针，但是我只想把头节点中的top拿来标记栈顶位置
    	其它节点的top指针不去理会
    */
    //定义一个结构体表示链式栈
    struct linkstack
    {
    	int data; //存放真实数据
    	struct linkstack *top; //指向栈顶的指针
    	struct linkstack *next; //指向下个节点的指针
    };
    
    //栈的初始化
    struct linkstack *init_stack()
    {
    	struct linkstack *mystack=malloc(sizeof(struct linkstack));
    	mystack->next=NULL;
    	mystack->top=mystack;  //栈顶指向目前链表中最后一个节点的位置
    	return mystack;
    }
    
    //压栈
    int push_stack(int new,struct linkstack *stack)
    {
    	//把new对应的节点保存到栈顶(链表的末尾)
    	struct linkstack *newnode=malloc(sizeof(struct linkstack));
    	newnode->data=new;
    	newnode->top=NULL;
    	newnode->next=NULL;
    	
    	//保存到栈顶
    	stack->top->next=newnode;
    	
    	//更新栈顶
    	stack->top=newnode;
    	return 0;
    }
    
    //弹栈
    int pop_stack(struct linkstack *stack)
    {
    	//判断链式栈是否空了
    	if(stack->top==stack)
    	{
    		printf("对不起栈已经空了!\n");
    		return -1;
    	}
    	//把最后一个节点(栈顶的值保存，方便等会返回)
    	int num=stack->top->data;
    	//把栈顶的节点free掉
    	struct linkstack *p=stack;
    	while(p->next!=stack->top)
    		p=p->next;
    	p->next=NULL;
    	free(stack->top);
    	
    	//更新top
    	stack->top=p;
    	return num;
    }
    
    int main()
    {
    	//初始化栈
    	struct linkstack *mystack=init_stack();
    	
    	//压栈几个数据
    	push_stack(15,mystack);
    	push_stack(25,mystack);
    	push_stack(35,mystack);
    	push_stack(15,mystack);
    	push_stack(25,mystack);
    	push_stack(35,mystack);
    	push_stack(15,mystack);
    	push_stack(25,mystack);
    	push_stack(35,mystack);
    	
    	//弹栈
    	int ret=pop_stack(mystack);
    	while(ret!=-1)
    	{
    		printf("ret is:%d\n",ret);
    		ret=pop_stack(mystack);
    	}
    		
    }

## 顺序栈 ##

#include "myhead.h"
    /*
    	主动思路：理解加深印象
    	理解得越多--》记忆的东西就越少
    */
    #define N 32
    typedef int Elemtype;
    
    //定义结构体表示顺序栈
    struct stack
    {
    	Elemtype a[N]; //存放入栈的数据
    	int top;  //标记栈顶位置
    };
    
    //初始化栈
    struct stack *init_stack()
    {
    	struct stack *mystack=malloc(sizeof(struct stack));
    	//清空数组
    	bzero(mystack->a,N*sizeof(Elemtype));
    	mystack->top=0; //栈顶位置，压栈和弹栈都从栈顶开始
    	return mystack;
    }
    
    //判断栈是否满了
    bool is_full(struct stack *somestack)
    {
    	if((somestack->top)>(N-1))
    		return true;
    	else
    		return false;
    }
    
    //判断栈是否空了
    bool is_empty(struct stack *somestack)
    {
    	if((somestack->top)<0)
    		return true;
    	else
    		return false;
    }
    //压栈 
    int push_stack(Elemtype n,struct stack *somestack)
    {
    	//判断栈是否满了
    	if(is_full(somestack))
    		return -1;
    	//压入栈顶，存放到栈顶
    	somestack->a[somestack->top]=n;
    	//更新栈顶
    	somestack->top++;
    	return 0;
    }
    
    //出栈
    int pop_stack(struct stack *somestack)
    {
    	//判断栈是否空了
    	if(is_empty(somestack))
    		return -1;
    	somestack->top--;
    	return somestack->a[somestack->top];
    }
    
    //销毁栈
    int destroy_stack(struct stack *somestack)
    {
    	free(somestack);
    	return 0;
    }
    
    int main()
    {
    	int num;
    	int i;
    	//初始化顺序栈
    	struct stack *mystack=init_stack();
    	
    	printf("请输入任意一个正整数！\n");
    	scanf("%d",&num);
    	//num不断地取余2，余数压栈
    	while(num!=0) 
    	{
    		push_stack(num%2,mystack);
    		//printf("%d\n",num%2);
    		num=num/2;
    	}
    	//出栈，得到二进制
    	//for(i=0; i<N; i++)  //错误的，不能出栈N次，根据栈的实际元素个数来写
    	int size=mystack->top;  //把top最开始的值保存一下
    	for(i=0; i<size; i++)
    		printf("%d",pop_stack(mystack)); //调用的过程中top一直都在改变
    	printf("\n");
    	//销毁栈
    	destroy_stack(mystack);
    	return 0;
    	
    }

## 顺序队列 ##

#include "myhead.h"
    
    //定义一个结构体表示顺序队列
    struct queue
    {
    	int data[20];
    	int qhead;  //标记队头
    	int qtail; //标记队尾
    };
    
    //初始化
    struct queue *init_queue()
    {
    	struct queue *head=malloc(sizeof(struct queue));
    	bzero(head->data,20*4);
    	head->qhead=0;
    	head->qtail=0;
    	return head;
    }
    
    //入队
    int in_queue(int new,struct queue *somequeue)
    {
    	//判断队列满了没有
    	if(somequeue->qtail>=20)
    		return -1;
    	somequeue->data[somequeue->qtail]=new;
    	//更新队尾
    	somequeue->qtail++;
    	return 0;
    }
    
    //出队
    int out_queue(struct queue *somequeue)
    {
    	//判断队列空了没有   
    	if((somequeue->qhead) >= (somequeue->qtail))
    	{
    		printf("对不起队列空了!\n");
    		return -1;
    	}
    	//保存队首位置的数据
    	int num=somequeue->data[somequeue->qhead];
    	//更新队首
    	somequeue->qhead++;
    	return num;
    }
    
    //销毁
    int destroy_queue(struct queue *somequeue)
    {
    	free(somequeue);
    }
    
    int main()
    {
    	//初始化一个队列
    	struct queue *myqueue=init_queue();
    	
    	//入队几个数据
    	in_queue(15,myqueue);
    	in_queue(25,myqueue);
    	in_queue(35,myqueue);
    	in_queue(45,myqueue);
    	
    	//出队
    	printf("出队:%d\n",out_queue(myqueue));
    	printf("出队:%d\n",out_queue(myqueue));
    	printf("出队:%d\n",out_queue(myqueue));
    	printf("出队:%d\n",out_queue(myqueue));
    	printf("出队:%d\n",out_queue(myqueue));
    	
    	//销毁
    	destroy_queue(myqueue);
    }

##      ##