数据结构3——linuxC(栈和队列)

demo1顺序栈

代码语言：javascript复制

#include <stdio.h>

#define SEQ_STACK_SIZE 10

// 顺序栈数据节点
struct seq_stack{
	int data;
};

// 顺序栈下标
int g_n;

// 入栈(压栈)
void stack_push(int new_data, struct seq_stack *s);
// 出栈(弹栈)
int stack_pop(int *pop_data, struct seq_stack *s);
// 显示顺序栈中的每个数据
void stack_show(struct seq_stack *s);

int main()
{
	// 1.初始化一个顺序栈，并清空
	struct seq_stack s[SEQ_STACK_SIZE] = {0};
	g_n = -1;

	// 2.数据操作（输入非0入栈(压栈)、输入0出栈(弹栈)）
	int cmd;
	int pop_data;
	while(1)
	{
		printf("Pls Input: ");
		scanf("%d", &cmd); while(getchar()!='n');
		if(cmd == 0)
		{
			// 出栈(弹栈)
			if(stack_pop(&pop_data, s) == 0)
				printf("%dn", pop_data);
		}
		else
			stack_push(cmd, s);	// 入栈(压栈)
		
		stack_show(s);
	}

	return 0;
}

// 显示顺序栈中的每个数据
void stack_show(struct seq_stack *s)
{
	int i;
	for(i=0; i<=g_n; i  )
		printf("%d ", s[i].data);
	printf("n");
}

// 入栈(压栈)
void stack_push(int new_data, struct seq_stack *s)
{
	// 0.判断是否为满栈
	if(g_n >= SEQ_STACK_SIZE-1)
	{
		printf("ERROR: Full!n");
		return;
	}

	// 1.将新数据放到栈顶下标 1
	s[g_n 1].data = new_data;

	// 2.栈顶下标  
	g_n  ;
}

// 出栈(弹栈)
int stack_pop(int *pop_data, struct seq_stack *s)
{
	// 0.判断是否为空栈？
	if(g_n == -1)
	{
		printf("ERROR: Empty!n");
		return -1;
	}

	// 1.将栈顶元素取出
	*pop_data = s[g_n].data;

	// 2.栈顶下标--
	g_n--;

	return 0;
}

demo2链式栈-进制转换

代码语言：javascript复制

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

//0,设计链表节点
typedef struct stack_node{
	int data;		//数据域
	struct stack_node *next;	//指向下一个节点指针
}S_Node;

//2,压栈
void S_List_Push(S_Node **top, int new_data)
{
	//1) 新数据申请堆空间，并把数据放入
	S_Node *newnode = (S_Node *)malloc(sizeof(S_Node));
	if (NULL == newnode)
	{
		perror("malloc newnode failed");
		return;
	}
	newnode->data = new_data;

	//2）新节点指针域指向栈顶指针 *top(偷)
	newnode->next = *top;

	//3）栈顶指针*top指向新节点
	*top = newnode;
}

//3,出栈 --》data用来存放出栈的数据
int S_List_Pop(S_Node **top, int *data)
{
	//1) 判断栈是否为空 
	if(*top == NULL)
		return -1;

	//2) 取出栈顶节点数据
	*data = (*top)->data;

	//3）修改栈顶指针 *top
	S_Node *temp = *top;
	*top = (*top)->next;

	//4）释放刚才的栈顶指针堆空间
	free(temp);		//删除节点p

	return 0;
}


void S_List_Show(S_Node *top)
{
	S_Node *pos;
	for(pos=top; pos!=NULL; pos=pos->next)
		printf("%d ", pos->data);
	printf("n");
}

/*链式栈demo*/
int main(int argc, char const *argv[])
{
	// 1. 初始化链式栈
	S_Node *stack_top = NULL;

	// 2.输入10进制数，逐个取余并压栈
	printf("Pls Input: ");
	int n;
	scanf("%d", &n); while(getchar()!='n');

	// 3.转换为8进制并压栈
	int data;
	int num = n;
	while(num != 0)
	{
		S_List_Push(&stack_top, num%8);
		num/=8;
	}
	printf("0");
	while(S_List_Pop(&stack_top, &data) == 0)
		printf("%d", data);
	printf("n");

	// 4.转换为2进制并压栈
	num = n;
	while(num != 0)
	{
		S_List_Push(&stack_top, num%2);
		num/=2;
	}
	printf("0b");
	while(S_List_Pop(&stack_top, &data) == 0)
		printf("%d", data);
	printf("n");

	return 0;
}

demo3循环顺序队列

代码语言：javascript复制

#include <stdio.h>

#define SEQ_QUEUE_SIZE 10

// 循环顺序队列节点
struct queue_node
{
	int data;
};

// 显示队列所有数据
void queue_show(struct queue_node *q);
// 入队
void queue_enter(struct queue_node *q, int new_data);
// 出队
int queue_deq(struct queue_node *q, int *de_data);

int front;	//队头下标
int rear;	//队尾下标

int main()
{
	// 1.初始化一个空队列
	struct queue_node q[SEQ_QUEUE_SIZE] = {0};
	front=rear=0;

	// 2.数据操作
	int cmd;
	while(1)
	{
		printf("Pls Input: ");
		scanf("%d", &cmd); while(getchar()!='n');
		if(cmd != 0)	// 入队
			queue_enter(q, cmd);
		else if(cmd == 0)	// 出队
		{
			queue_deq(q, &cmd);
			printf("Get: %dn", cmd);
		}

		queue_show(q);
	}

	return 0;
}

// 出队
int queue_deq(struct queue_node *q, int *de_data)
{
	// 0.判断是否为空队列
	if(front == rear)
	{
		printf("ERROR: Empty!n");
		return -1;
	}

	// 1.直接将下标为front的数据取出
	*de_data = q[front].data;
	q[front].data=0;

	// 2.队头后移
	front = (front 1)%SEQ_QUEUE_SIZE;
}

// 入队
void queue_enter(struct queue_node *q, int new_data)
{
	// 0.判断是否为满队列
		// (rear 1)%SEQ_QUEUE_SIZE: 作用为限制(rear 1)的结果小于SEQ_QUEUE_SIZE
	if((rear 1)%SEQ_QUEUE_SIZE == front)
	{
		printf("ERROR: Queue Full!n");
		return;
	}

	// 1.直接将数据写入下标队尾rear位置
	q[rear].data = new_data;

	// 2.队尾后移（效果同上，限制作用）
	rear = (rear 1)%SEQ_QUEUE_SIZE;
}

// 显示队列所有数据
void queue_show(struct queue_node *q)
{
	// 0.判断是否为空队列
	if(front == rear)
	{
		printf("ERROR: Empty!n");
		return;
	}

	// 1.根据队头front和队尾rear的大小，区分2种情况。
	int i;
	if(front < rear)
	{
		for(i=front; i<rear; i  )
			printf("%d ", q[i].data);
		printf("n");
	}
	else if(front > rear)
	{
		for(i=front; i<SEQ_QUEUE_SIZE; i  )
			printf("%d ", q[i].data);
		for(i=0; i<rear; i  )
			printf("%d ", q[i].data);
		printf("n");
	}

#if 0
	int i;
	printf("下标: ");
	for(i=0; i<SEQ_QUEUE_SIZE; i  )
		printf("%d ", i);
	printf("n");

	printf("数据: ");
	for(i=0; i<SEQ_QUEUE_SIZE; i  )
		printf("%d ", q[i].data);
	printf("n");
#endif
}

demo4链式队列

代码语言：javascript复制

#include <stdio.h>
#include <stdlib.h>

// 链式队列节点
struct queue_node
{
	int data;
	struct queue_node *next;
};

// 初始化链式队列节点
struct queue_node *link_queue_init(void);
// 出队
int link_queue_deq(int *de_data);
// 入队
void link_queue_enter(int new_data);
// 链式队列遍历
void link_queue_show(struct queue_node *head);

struct queue_node *front;	//队头指针
struct queue_node *rear;	//队尾指针

int main()
{
	// 1.初始化一个空队列
	struct queue_node *head = link_queue_init();
	front = rear = head;

	// 2.数据操作
	int cmd;
	while(1)
	{
		printf("Pls Input: ");
		scanf("%d", &cmd); while(getchar()!='n');
		if(cmd != 0)	// 入队
			link_queue_enter(cmd);
		else if(cmd == 0)	// 出队
		{
			link_queue_deq(&cmd);
			printf("Get: %dn", cmd);
		}

		link_queue_show(head);
	}
}

// 链式队列遍历
void link_queue_show(struct queue_node *head)
{
	struct queue_node *pos;
	for(pos=head->next; pos!=NULL; pos=pos->next)
		printf("%d ", pos->data);
	printf("n");
}

// 入队
void link_queue_enter(int new_data)
{
	// 1.新节点分配堆空间，并把数据放入
	struct queue_node *new = link_queue_init();
	new->data = new_data;

	// 2.操作新节点
	// new->next = rear->next;	// 效果相同
	new->next = NULL;

	// 3.操作队尾节点
	rear->next = new;

	// 4.队尾指针 *rear指向新节点（新节点成为了新的队尾）
	rear = new;
}

// 出队
int link_queue_deq(int *de_data)
{
	// 0.判断是否为空队列
	if(front->next == NULL)
	{
		printf("ERROR: Empty!n");
		return -1;
	}

	// 1.获取队头 front->next的数据。
	*de_data = front->next->data;

	// 2.修改队头指针域
	struct queue_node *temp = front->next;
	front->next = front->next->next;

	// 3.释放堆空间
	free(temp);

	return 0;
}

// 初始化链式队列节点
struct queue_node *link_queue_init(void)
{
	struct queue_node *p = malloc(sizeof(struct queue_node));
	if(p == NULL)
	{
		printf("malloc failedn");
		return NULL;
	}
	p->data=0;
	p->next = NULL;

	return p;
}

队列

0 人点赞