【Day10 数据结构学习-3】

一、双向循环链表

1.1 概念

1.2 操作

定义一个结点结构体

#ifndef _DOUBLELIST_H_
#define _DOUBLELIST_H_
#include <stdio.h>
#include <stdlib.h>
typedef int DataType;
//定义结点结构体
typedef struct doublelist
{DataType data;struct doublelist *front;   //保存前一个结点的地址struct doublelist *next;   //保存后一个结点的地址
}doublelist;

创建一个空的双向循环链表

//创建一个空的双向循环链表
doublelist * DoubleListCreate()
{doublelist *head = (doublelist *)malloc(sizeof(doublelist));head->front = head;head->next = head;return head;
}

插入数据

//插入数据
void DoubleListInsert(doublelist *head,DataType value)
{doublelist *tmp = (doublelist *)malloc(sizeof(doublelist));tmp->front = NULL;tmp->next = NULL;tmp->data = value;tmp->next = head->next;tmp->front = head;head->next->front = tmp;head->next = tmp;
}

遍历链表

//遍历双向循环链表
void DoubleListPrint(doublelist *head)
{doublelist *p = head;while(p->next != head){p = p->next;printf("%d ",p->data);}putchar(10);
}

头删法删除数据

//头删法删除数据
DataType DoubleListDelete(doublelist *head)
{if(head->next == head){printf("双向循环链表为空！\n");return (DataType)-1;}doublelist *tmp = head->next;head->next = tmp->next;tmp->next->front = head;DataType value = tmp->data;free(tmp);tmp = NULL;return value;
}

整体代码

doublelink.h

#ifndef _DOUBLELIST_H_
#define _DOUBLELIST_H_#include <stdio.h>
#include <stdlib.h>typedef int DataType;
//定义结点结构体
typedef struct doublelist
{DataType data;struct doublelist *front; //保存前一个结点的地址struct doublelist *next; //保存后一个结点的地址
}doublelist;//创建一个空的双向循环链表
doublelist * DoubleListCreate();//插入数据
void DoubleListInsert(doublelist *head,DataType value);//遍历双向循环链表
void DoubleListPrint(doublelist *head);//判断双向循环链表是否为空
int DoubleListIsEmpty(doublelist *head);//头删法删除数据
DataType DoubleListDelete(doublelist *head);#endif

doublelist.c

#include"doublelist.h"//创建一个空的双向循环链表
doublelist * DoubleListCreate()
{doublelist *head = (doublelist *)malloc(sizeof(doublelist));head->front = head;head->next = head;return head;
}//插入数据
void DoubleListInsert(doublelist *head,DataType value)
{doublelist *tmp = (doublelist *)malloc(sizeof(doublelist));tmp->front = NULL;tmp->next = NULL;tmp->data = value;tmp->next = head->next;tmp->front = head;head->next = tmp;head->next->front = tmp;
}//遍历双向循环链表
void DoubleListPrint(doublelist *head)
{doublelist *p = head;while(p->next != head){p = p->next;printf("%d ",p->data);}putchar(10);
}//判断双向循环链表是否为空
int DoubleListIsEmpty(doublelist *head)
{return head->next == head ? 1 : 0;
}//头删法删除数据
DataType DoubleListDelete(doublelist *head)
{if(DoubleListIsEmpty(head)){printf("删除失败，该链表为空！\n");return (DataType)-1;}//临时保存数据DataType value = head->next->data;//tmp指针临时保存第一个结点的地址doublelist *tmp = head->next;head->next = tmp->next;//删除第一个结点后第二个结点的fornt指向head结点tmp->next->front = head;free(tmp);tmp = NULL;return value;}

main.c

#include "doublelist.h"
int main()
{doublelist *head =DoubleListCreate();int i;for(i = 0; i < 10; i++){DoubleListInsert(head,i + 1);}DoubleListPrint(head);DoubleListDelete(head); //去头DoubleListPrint(head);DoubleListDelete(head); //去头DoubleListPrint(head);
}

makefile

run : doublelist.c main.cgcc *.c -o run

【要运行时：直接输入命令 make，然后 ./ 开始执行】

二、栈 （stack）

2.1 概念

栈的性质：后进先出
栈的操作：
入栈（压栈）push
出栈（单栈）pop

2.2 顺序栈 seqstack

定义数据类型

#ifndef _SEQSTACK_H_
#define _SEQSTACK_H_#include <stdio.h>
#include <stdlib.h>
#define N 32
typedef int DataType;
typedef struct seqstack
{DataType data[N];int pos;
}seqstack;#endif

创建栈

//创建一个空的栈
seqstack* SeqStackCreate()
{seqstack *s = (seqstack *)malloc(sizeof(seqstack));s->pos = -1;return s;
}

判断栈是否为满

//判断栈是否为满
int SeqStackIsFull(seqstack *s)
{return s->pos == N -1 ? 1 : 0;
}
判断栈是否为空
//判断栈是否为空
int SeqStackIsEmpty(seqstack *s)
{return s->pos == -1 ? 1: 0;
}

入栈

//入栈
void SeqStackPush(seqstack *s,DataType value)
{if(SeqStackIsFull(s)){printf("栈满了！\n");return;}s->pos++;s->data[s->pos] = value;return;
}

出栈

//出栈
DataType SeqStackPop(seqstack *s)
{if(SeqStackIsEmpty(s)){printf("栈为空！\n");return (DataType)-1;}DataType value = s->data[s->pos];s->pos--;return value;
}

2.3 链栈 linkstack（链式栈）

整体代码

main.c：

//main.c
#include "linkstack.h"
int main(int argc, char const *argv[])
{stack s;InitStack(&s);push(&s,100);push(&s,200);push(&s,300);push(&s,400);push(&s,500);push(&s,600);push(&s,700);while(!EmptyStack(&s)){printf("出栈:%d\n",pop(&s));}return 0;
}

linkstack.c：

//linkstack.c
#include "linkstack.h"
//初始化栈信息
void InitStack(stack *s)
{s->length = 0;s->top = NULL;
}
//入栈
void push(stack *s,DataType value)
{if(NULL == s){printf("栈空间分配失败，初始化失败！\n");return ;}Node *tmp = (Node *)malloc(sizeof(Node));tmp->next = NULL;tmp->data = value;tmp->next = s->top;s->top = tmp;s->length++;
}
//获取栈顶元素
DataType GetTop(stack *s)
{if(NULL == s){return (DataType)-1;}if(s->top == NULL){return (DataType)-1;}return s->top->data;
}
//出栈
DataType pop(stack *s)
{if(NULL == s){return (DataType)-1;}if(s->top == NULL){return (DataType)-1;} Node *tmp = s->top;s->top = tmp->next;DataType value = tmp->data;free(tmp);tmp = NULL;s->length--;return value;
}
//判断栈是否为空
int EmptyStack(stack *s)
{return s->top == NULL ? 1 : 0;
}
//清空栈
int ClearStack(stack *s)
{if(NULL == s){return (DataType)-1;}if(s->top == NULL){return (DataType)-1;}Node *tmp = s->top;while(tmp){s->top = tmp->next;free(tmp);tmp = s->top;s->length--;}     return 1;
}

linklist.h：

#ifndef _LINKSTACK_H_
#define _LINKSTACK_H_#include<stdio.h>
#include<stdlib.h>typedef int DataType;
typedef struct node //保存结点信息
{DataType data;struct node *next;
}Node;typedef struct linkstack //保存栈的信息
{Node *top;int length;
}stack;//初始化栈信息
void InitStack(stack *s);//入栈
void push(stack *s,DataType value);//获取栈顶元素
DataType GetTop(stack *s);//出栈
DataType pop(stack *s);//判断栈是否为空
int EmptyStack(stack *s);//清空栈
int ClearStack(stack *s);//判断符号的优先级
int Priority(char ch);//四则混合计算器
void calculator();#endif

2.4 练习：四则运算器

//判断符号的优先级
int Priority(char ch)
{switch (ch){case '(':return 3;case '*':case '/':return 2;case '+':case '-':return 1;default:return 0;}
}
//四则混合计算器
void calculator()
{stack s_sum, s_opt;InitStack(&s_sum);InitStack(&s_opt);char opt[128] = {0};printf("请输入表达式：\n");scanf("%s",opt);int i = 0,tmp = 0,num1,num2;while(opt[i] != '\0' || EmptyStack(&s_opt) != 1){if(opt[i] >= '0' && opt[i] <= '9')   //运算数{tmp = tmp *10 + opt[i] - '0';i++;if(opt[i] < '0' || opt[i] > '9'){push(&s_sum,tmp);tmp = 0;}}else   //操作符{if(EmptyStack(&s_opt) == 1 || Priority(opt[i]) > Priority(GetTop(&s_opt))||(GetTop(&s_opt) == '(' && opt[i] != ')')){push(&s_opt,opt[i]);i++;continue;}if(GetTop(&s_opt) == '(' && opt[i] == ')'){pop(&s_opt);i++;continue;}if(Priority(opt[i]) <= Priority(GetTop(&s_opt)) ||opt[i] == ')' && GetTop(&s_opt)!= '('||opt[i] == '\0' && EmptyStack(&s_opt) != 1){switch (pop(&s_opt)){case '+':num1 = pop(&s_sum);num2 = pop(&s_sum);push(&s_sum,num1 + num2);break;case '-':num1 = pop(&s_sum);num2 = pop(&s_sum);push(&s_sum,num2 - num1);break;case '*':num1 = pop(&s_sum);num2 = pop(&s_sum);push(&s_sum,num1 * num2);break;case '/':num1 = pop(&s_sum);num2 = pop(&s_sum);push(&s_sum,num2 / num1);break;               default:break;}}}}printf("%d\n",GetTop(&s_sum));
}