数据结构3——linuxC(栈和队列)
demo1顺序栈#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 *p
·
demo1顺序栈
#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("%d\n", 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链式栈-进制转换
#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循环顺序队列
#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: %d\n", 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链式队列
#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: %d\n", 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 failed\n");
return NULL;
}
p->data=0;
p->next = NULL;
return p;
}
更多推荐
0
0- 0
已为社区贡献1条内容
所有评论(0)