C 数据结构
数据结构包括：线性结构和非线性结构
线性结构是最常用的，特点是数据元素之间存在一对一的线性关系，有两种存储结构：顺序存储（数组）和链式存储结构（链表）。
顺序存储的线性表称为顺序表，顺序表中的存储元素是连续的。
链式存储的线性表称为链表，链表中的存储元素不一定是连续的，元素节点中存放数据元素以及相邻元素的地址信息。
线性结构常见的：数组、队列、链表、栈
非线性结构：
非线性常见的包括：二位数组、多维数组、广义表、树结构、图结构
顺序存储结构：是把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。
链式存储结构：是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可不连续。是用一个指针存放数据元素的地址，这样通过地址就可以找到相关联数据元素的位置。线性表（List）
线性表：有零个或多个数据元素组成的有限序列。
抽象数据类型（Abstract Data Type, ADT）
格式（伪代码）：
ADT 抽象数据类型名
Data
数据元素之间逻辑关系的定义
Operation
操作
/*
InitList(*L):初始化操作，建立一个空的线性表L
ListEmpty(L):判断线性表是否是否为空，若线性表为空，返回true，否则返回false
ClearList(*L):将线性表清空
GetElem(L,i,*e):将线性表L中的第i个位置元素值返回给e
LocateElem(L,e):在线性表L中查找与给定值e相等的元素，如果查找成功，返回该元素在表中序号表示成功；否则，返回0表示失败。
ListInsert(*L,i,e):在线性表L中第i个位置插入新元素e
ListDelete(*L,i,*e):删除线性表L中第i个位置元素，并用e返回其值
Listlength(L):返回线性表L的元素个数
*/
endADT顺序存储结构——数组
指的是用一段地址连续的存储单元依次存储线性表的数据元素区分线性表长度与数组长度：
数组长度是存放线性表的存储空间的长度，存储分配后这个量是一般不变的；
线性表长度是线性表中数据元素的个数，随着线性表插入和删除操作的进行
线性表长度小于或等于数组长度。数组存储的优缺点
优点：
1.可以快速存取表中任一位置的元素
2.不用为表中元素之间的逻辑关系增加额外的存储空间
缺点：
1.插入删除需要移动大量的元素
2.线性表长度变化较大是，难以确定存储空间的容量
3.造成存储空间的“碎片”链式存储结构
特点：用一组任意的存储的单元存储线性表的数据元素，这组存储的那元可以是连续的，也可以是不连续的。
单链表
单链表的插入和删除
插入：
x->next=b->next;
b->next=x;
删除：
a->next=c->next; //或者： b=a->next;a->next=b->next=a->next->next;
例子：根据带有头部的链表，实现商品增删改查，并且也可以针对商品已经编号进行排序，完成排行榜
package com.example.summer01.P2.linearList.LinkList.E1;
public class GoodsNode {
public int id;
public String name;
public double price;
public GoodsNode next;
public GoodsNode(int id, String name, double price) {
}
}
**********************************************************************************************
package com.example.summer01.P2.linearList.LinkList.E1;
public class DLLinkedLIst {
//头部结点
private GoodsNode node = new GoodsNode(0,"",0);
//往链表中添加节点 ----->> 直接插入在链表的尾端
public void add(GoodsNode goodsNode){
GoodsNode temp = goodsNode;
while (true){
if (temp.next == null) {
break;
}
temp=temp.next;
}
temp.next = goodsNode;
}
//根据商品的编号id ，按顺序插入
public void insert(GoodsNode goodsNode) {
//头结点
GoodsNode temp = node;
boolean flag = false;
while (true) {
if (temp.next == null) {
break;
}
if (temp.next.id > node.id){
break;
}else if (temp.next.id == node.id){
flag = true;
break;
}
}
temp=temp.next;
if (flag) {
System.out.println("已经存在该商品，不能重复元素！！");
}else {
goodsNode.next=temp.next;
temp.next=goodsNode;
}
}
//修改结点的方法
/**
* 1.先找到链表中目标结点
* 2.根据新的数据修改
* 3.跟商品id进行查找
*
* 循环结束的条件，满足其一就可以：1.直到链表中的最后一个结点还未找到，则结束循环
* 2.找到了结点，结束循环
*/
public void updateNode(GoodsNode goodsNode){
//如果链表为空
if(node.next == null){
System.out.println("链表为空~~~~");
return;
}
GoodsNode temp = node.next;
//标识符，表示找到了结点
boolean flag = false;
while (true){
if(temp == null) {
break;
}
if(temp.id == goodsNode.id) {
flag = true;
break;
}
temp = temp.next;
}
if (flag) {
//真正的修改结点
temp.name = goodsNode.name;
temp.price = goodsNode.price;
}else {
System.out.println("在整个链表中未找到目标结点....");
}
}
/**
* 结点删除功能
* 条件：根据结点的编号删除
*/
public void delNode(int id){
GoodsNode temp = node;
boolean flag = false;
while (true) {
if (temp.next == null) {
break;
}
if (temp.id == id){
flag = true;
break;
}
temp = temp.next;
}
if (flag) {
temp.next = temp.next.next;
System.out.println("未找到要删除的结点....");
}
}
/**
* 定义查看链表中每一个结点的元素
*/
public void list(){
if (node.next == null){
System.out.println("空链表");
return;
}
GoodsNode temp = node.next;
while (true) {
if (temp == null) {
break;
}
System.out.println(temp);
temp=temp.next;
}
}
}面试题：
/**
* 面试题：计算单链表中存在的结点个数，不统计头结点
*/
public int getLen() {
if (node.next == null){
System.out.println("空链表");
return 0;
}
GoodsNode temp = node.next;
int length=0;
while (temp != null){
//当前结点的个数
length++;
temp = temp.next;
}
return length;
}静态链表（数组）
优点：
在插入删除时只需要修改游标，无需移动元素。
缺点：
没有顺序存储随机存取的特性；没有解决表长问题。循环链表
合并两个循环链表
p=rearA->next;
rearA->next = rearB->next->next;
rearB->next=p;
free(p);
双向链表：
是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。在双向链表中的结点都有两个指针域，一个指向直接后继，另一个指向直接前驱。
双向链表——插入
s->prior=p;
s->next=p->next;
p->next->prior=s;
p->next=s;
Java实现：
package com.example.summer01.P2.linearList.LinkList.E2;
public class DoubleLinkedList {
public static void main(String[] args) {
DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
BookNode b1 = new BookNode(1,"小米手机",4599);
BookNode b2 = new BookNode(2,"小米充电宝",89.9);
BookNode b3 = new BookNode(3,"iPad",2559);
BookNode b4 = new BookNode(4, "air15",4799);
doubleLinkedList.addList(b1);
doubleLinkedList.addList(b2);
doubleLinkedList.addList(b3);
doubleLinkedList.addList(b4);
// doubleLinkedList.deleteNode(1);
doubleLinkedList.updateNode(new BookNode(3,"计算机",9999));
System.out.println("");
}
private void updateNode(int i, String 计算机, double v) {
}
//双向链表
//头部节点
private BookNode head = new BookNode(0,"",0);
//添加结尾新的节点
public void addList(BookNode newNode){
BookNode temp = head;
while (true){
//表示双向链表是空链表
if (temp.next == null) {
break;
}
temp = temp.next;
}
//需要把新的节点给上一个节点，需要把上一个节点next指向新的节点
temp.next = newNode;
newNode.previous = temp;
}
删除
p->prior->next=p->next;
p->next->prior=p->prior;
Java实现：
/**
* 双向链表的删除
* 条件：根据id编号进行删除结点
*/
public void deleteNode(int id){
if(head.next == null){
System.out.println("空链表....");
return;
}
BookNode temp = head.next;
boolean flag = false;
while (true){
if (temp == null){
break;
}
if(temp.id == id){
flag = true;
break;
}
temp=temp.next;
}
if (flag) {
temp.previous.next=temp.next;
if(temp.next !=null){
temp.next.previous=temp.previous;
}
}else {
System.out.println("未找到节点...");
}
}
}
修改节点
/**
* 修改节点
* 条件：双向链表中的每一个结点的id和修改的id对比，如果对比成功，则进行修改该结点，如果没有对比成功，双向链表中未找到目标结点
*/
public void updateNode(BookNode node){
if (head.next == null){
//空链表
System.out.println("空链表");
return;
}
BookNode temp = head.next;
boolean flag = false;
while (true) {
if (temp == null) {
break;
}
if (temp.id == node.id){
flag = true;
break;
}
temp = temp.next;
}
if (flag) {
temp.name = node.name;
temp.price = node.price;
}else {
System.out.println("未找到要修改的结点...");
}
}
链表反转
需求：
原链表中数据为：1 -> 2 -> 3 -> 4
反转后的链表数据为: 4 -> 3 -> 2 -> 1反转API：
public void reverse() :对整个链表反转
public Node reverse(Node cur) :反转链表中某个结点cur,并把反转后的cur结点返回单向环形链表
约瑟夫问题：设编号1，2，3......n的n个人围坐一圈，约定编号为k(1 <= k <= n)的人开始报数，数到m的那个人出列，他的下一位又从1开始报数，数到m的那个人出列，他的下一位又从1开始报数，数到m的那个人出列，以此类推，直到所有人出列为止，由此产生一个出队编号的序列。
#include <stdio.h>
#include <malloc.h>
typedef int DataType;
typedef struct Node
{
DataType data;
struct Node *next;
} Node;
Node *Creat(int n)
{
Node *rear = NULL, *s;
int i;
rear = (Node *)malloc(sizeof(Node));
rear->data = 1;
rear->next = rear;
for (i = 2; i <= n; i++)
{
s = (Node *)malloc(sizeof(Node));
s->data = i;
s->next = rear->next; //将结点s插入尾结点rear的后面
rear->next = s;
rear = s; //指针rear指向当前最后一个结点
}
return rear;
}
void Joseph(Node *rear, int m)
{
Node *pre = rear;
Node *p = rear->next;
int count = 1;
printf("出环的顺序是：\n");
while (p->next != p)
{
if (count < m)
{
pre = pre->next; //工作指针pre 和 p后移
p = p->next;
count++;
}
else
{
printf("%d ", p->data); //输出
pre->next = p->next; //删除结点p
free(p); //释放结点p
p = pre->next; //保持p位于pre的next
count = 1; //将计数归1
}
}
printf("%d", p->data);
free(p); //不要忘记释放最后一个结点
}
int main()
{
int n, m;
Node *rear = NULL;
printf("请输入约瑟夫环的长度：");
scanf("%d", &n);
printf("请输入密码：");
scanf("%d", &m);
rear = Creat(n);
Joseph(rear, m);
return 0;
}受限线性表——栈与队列
栈（stack）
栈是限定仅在表尾进行插入和删除擦欧总的线性表。
把允许插入或删除的一端称为栈顶（top），另一端称为栈底（bottom），不含任何数据元素的栈称为空栈。
栈又称为后进先出的线性表，简称LIFO(Last In Frist Out)
栈元素具有线性关系，即前驱后继关系。栈的顺序存储结构（静态栈）
栈是限制插入和删除只能在一个位置（即栈顶top）上进行的线性表。不允许插入和删除的另一端为栈底（bottom）。
C语言实现
#include <stdlib.h>
#include "stack1.h"
#include<string.h>
#include<stdlib.h>
#include <stdio.h>
#define MAX 1024
#define _CRT_SECURE_ND_WARNINGS
//栈的结构体
struct SStack
{
void * data[MAX]; //数组
//栈的元素个数
int m_Size;
};
typedef SStack * seqStack;
//初始化栈
seqStack init_seqStack() {
// struct SStack * stack = malloc(sizeof(struct SStack));
// if (stack == NULL)
// {
// return NULL;
// }
//清空数组中的每个元素
// memset(stack->data, 0, sizeof(void*) * MAX);
// stack->m_Size = 0;
// return stack;
}
//入栈
void push_Stack(seqStack stack, void* data) {
if (stack == NULL)
{
return;
}
if (data == NULL)
{
return;
}
//判断是否已经满栈.如果满了，不可以再入栈了
struct SStack* myStack = stack;
if (myStack->m_Size == MAX)
{
return;
}
myStack->data[myStack->m_Size] = data;//入栈插入
myStack->m_Size++; //更新栈的大小
}
//出栈
void pop_Stack(seqStack stack, void* data) {
if (stack == NULL)
{
return;
}
//如果时空栈，不执行出栈
struct SStack* myStack = stack;
if (myStack->m_Size <= 0)
{
return;
}
//执行出栈操作
myStack->data[myStack->m_Size - 1] = NULL;
//更新栈的大小
myStack->m_Size--;
}
//获取栈顶元素
void* top_seqStack(seqStack stack) {
if (stack == NULL)
{
return NULL;
}
struct SStack* myStack = stack;
//如果时空栈，返回NULL
if (myStack->m_Size == 0)
{
return NULL;
}
return myStack->data[myStack->m_Size - 1];
}
//栈的大小
int size_seqStack(seqStack stack) {
if (stack == NULL)
{
return -1;
}
struct SStack* myStack = stack;
return myStack->m_Size;
}
//判断栈是否为空
int isEmpty_Stack(seqStack stack) {
if (stack == NULL)
{
return -1; //真
}
struct SStack* myStack = stack;
if (myStack->m_Size <= 0)
{
return 0; //真
}
return 0; //假，不是空栈
}
//销毁栈
void destroy_Stack(seqStack stack) {
if (stack == NULL)
{
return;
}
free(stack);
stack = NULL;
}
//测试
struct Person
{
char name[64];
int age;
};
void test01() {
//准备出数据
struct Person p1 = {"aaa",10};
struct Person p2 = { "bbb",20 };
struct Person p3 = { "ccc",30 };
struct Person p4 = { "ddd",40 };
//初始化栈
seqStack stack = init_seqStack();
//入栈
push_Stack(stack, &p1);
push_Stack(stack, &p2);
push_Stack(stack, &p3);
push_Stack(stack, &p4);
while (isEmpty_Stack(stack) == 0) //如果栈不为空，进行访问栈顶元素，并且出栈
{
// struct Person* pTop = top_seqStack(stack); //栈顶元素
// printf("栈顶元素 姓名： %s 年龄： %d\n",pTop->name,pTop->age);
//出栈
// pop_Stack(stack);
}
}
int main() {
system("pause");
return EXIT_SUCCESS;
}Java实现
package com.example.summer01.P2.stack;
@SuppressWarnings("all")
//栈的顺序存储结构 代码实现
public class ArraryStack {
//栈的大小
private int maxStack;
//数组用来模拟栈
private int[] stack;
//表示栈顶所在的位置，默认情况下如果没有数据即空栈时，使用-1
private int top = -1;
public ArraryStack(int maxStack){
this.maxStack = maxStack;
stack = new int[maxStack];
}
/**
* 1.压栈
* 2.弹栈
* 3.判断是否是空栈
* 4.当前栈中是否是满栈
*/
/**
* 先判断是否是满栈
*/
public boolean isFull() {
return this.top == this.maxStack - 1;
}
/**
* 判断是否是空栈
*/
public boolean isEmpty() {
return this.top == -1;
}
/**
* 压栈
*/
public void push(int val){
//是否已经满栈
if(isFull()){
throw new RuntimeException("此栈已满");
}
top++;
stack[top] = val; //压栈的过程
}
/**
* 出栈
*/
public int pop() {
//如果栈中是空的
if(isEmpty()){
throw new RuntimeException("空栈，未找到数据");
}
int value = stack[top];
top--;
return value;
}
/**
* 查看栈中所有元素
*/
public void list() {
//是否是空栈
if (isEmpty()) {
throw new RuntimeException("空栈，未找到数据");
}
int value = stack[top];
for (int i = 0 ; i < stack.length; i++) {
System.out.printf("stack[%d]=%d\n",i,stack[i]);
}
}
public int length() {
return this.top+1;
}
}栈的插入操作，叫做进栈/压栈,push
----------------------->>>>>>>>>> 推导出 top1 +1 = top2时，栈满
没栈满的情况：
在栈1中插入数据时，top1=top1 + 1 ; 在栈2中插入数据时，top2=top2 - 1;
栈的删除操作，叫做出栈/弹栈，pop
注意：首先得先判断是否空栈
if(S->top == -1) ----->说明是空栈事实上，使用这样的数据结构，通常都是当这两个栈的空间需求有相反关系时，也就是一个栈增长时另一个栈在缩短的情况。而且是具有相同数据类型的栈。
例子：回文数
计算机需求实现：运算
package com.example.summer01.P2.stack;
public class TestCount {
public static void main(String[] args) {
String str = "4+3+2+1*5";
/**
* 1.需要遍历字符串，获取每一个字符
* 2.判断当前字符是一个运算符还是一个数字
* 3.把数字存放在数字中，把运算符放在运算符栈
* 4.运算符栈：如果是空栈，那么运算符直接入栈，
* 如果运算符栈不是空栈，那么就需要先对比运算符优先级，新进来的运算符如果小于等于原来栈中运算符，那么需要把原运算 符弹出，
* 数字栈中数字进行弹栈，进行运算，运算后的结果重新放入数字栈中，新运算符入栈。如果新运算符优先级大于原符号栈中的 运算符，那么新的符号直接入栈。
*
*/
ArraryStack numStack = new ArraryStack(10);
ArraryStack symbolStack = new ArraryStack(10);
int temp1=0;
int temp2 = 0;
int symbolChar = 0;
int result=0;
String values = "";
//获取字符串的长度
int length = str.length();
for (int i = 0; i < length; i++) {
char c = str.charAt(i);
//是否是一个运算符
if(symbolStack.isOper(c)){
//如果不是一个空符号栈
if (!symbolStack.isEmpty()) {
//比较运算符的优先级
if (symbolStack.priority(c) <= symbolStack.priority(symbolStack.peek())) {
/**
* 1.去符号栈中获取栈顶符号
* 2.去数字栈中获取两个数字
*/
temp1 = numStack.pop();
temp2 = numStack.pop();
symbolChar = symbolStack.pop();
result=numStack.calculate(temp1, temp2, symbolChar);
//把运算结果再次放入数字栈中
numStack.push(result);
//把当前的运算符号压入符号栈中
symbolStack.push(c);
} else {
symbolStack.push(c);
}
}else {
//如果是空符号栈，直接将符号压栈
symbolStack.push(c);
}
}else {
//比如 33+44
values+=c;
if(i == length-1){
numStack.push(Integer.parseInt(values));
}else {
char data = str.substring(i + 1, i + 2).charAt(0);
if(symbolStack.isOper(data)){
numStack.push(Integer.parseInt(values));
values="";
}
}
}
}
while (true) {
if (symbolStack.isEmpty()) {
break;
}
temp1=numStack.pop();
temp2 = numStack.pop();
symbolChar = symbolStack.pop();
result=numStack.calculate(temp1,temp2,symbolChar);
numStack.push(result);
}
int res = numStack.pop();
System.out.println(str+"的结果=："+res);
}
}栈的链式存储结构（动态栈）
C实现
#include <stdlib.h>
#include "stack1.h"
#include<string.h>
#include<stdlib.h>
#include <stdio.h>
#include <string>
#define MAX 1024
#define _CRT_SECURE_ND_WARNINGS
struct StackNode
{
struct StackNode* next; //只维护指针域
};
//链式的栈结构体
struct LStack {
struct StackNOde pHeader; //头节点
int m_Size; //栈的大小
};
typedef void* LinkStack;
//初始化栈
LinkStack init_LinkStack() {
struct LStack * myStack = malloc(sizeof(struct LStack));
if (myStack == NULL)
{
return NULL;
}
myStack->pHeader.next = NULL;
myStack->m_Size = 0;
return myStack;
}
//入栈
void push_LinkStack(LinkStack stack,void * data) {
if (stack == NULL)
{
return;
}
if (data == NULL)
{
return;
}
//入栈 就是头插
struct LStack* myStack = stack;
//拿到用户数据的前四个字节
struct StackNode* myNode = data;
//插入节点
myNode->next = myStack->pHeader.next;
myStack->pHeader.next = myNode;
//更新栈的大小
myStack->m_Size++;
}
//出栈
void pop_LinkStack(LinkStack stack) {
if (stack == NULL)
{
return;
}
struct LStack* myStack = stack;
//如果时空栈 不出栈
if (myStack->m_Size <= 0)
{
return;
}
//保存第一个有数据的节点 栈顶元素
struct StackNode* pFrist = myStack->pHeader.next;
myStack->pHeader.next = pFrist->next;
//更新链表长度 栈大小
myStack->m_Size--;
}
//返回栈顶元素
void* top_LinkStack(LinkStack stack) {
if (stack == NULL)
{
return NULL;
}
struct LStack* myStack = stack;
if (myStack->m_Size <= 0)
{
return NULL;
}
return myStack->pHeader.next; //将第一个有数据的节点返回就可以了
}
//返回栈大小
int size_LinkStack(LinkStack stack) {
if (stack == NULL)
{
return -1;
}
struct LStack* myStack = stack;
return myStack->m_Size;
}
//判断栈是否为空
int isEmpty_LinkStack(LinkStack stack) {
if (stack == NULL)
{
return -1;
}
struct LStack* myStack = stack;
if (myStack->m_Size <= 0)
{
return 1;
}
return 0;
}
//销毁
void destroy_LinkStack(LinkStack stack) {
if (stack == NULL)
{
return;
}
free(stack);
stack = NULL;
}
//测试
struct Person {
char name[64];
int age;
};
void test01() {
//准备出数据
struct Person p1 = { "aaa",10 };
struct Person p2 = { "bbb",20 };
struct Person p3 = { "ccc",30 };
struct Person p4 = { "ddd",40 };
//初始化栈
LinkStack stack = init_LinkStack();
//入栈
push_LinkStack(stack, &p1);
push_LinkStack(stack, &p2);
push_LinkStack(stack, &p3);
push_LinkStack(stack, &p4);
while (isEmpty_LinkStack(stack) == 0) //如果栈不为空，进行访问栈顶元素，并且出栈
{
struct Person* pTop = top_LinkStack(stack); //栈顶元素
printf("栈顶元素 姓名： %s 年龄： %d\n", pTop->name,pTop->age);
//出栈
pop_LinkStack(stack);
}
//栈的大小
int size = size_LinkStack(stack);
printf("栈的大小为： %d\n", size);
//销毁
destroy_LinkStack(stack);
}
int main() {
system("pause");
return EXIT_SUCCESS;
}如果栈的使用过程中元素变化不可预料，有时大有时小，那么选择链栈是最好的，若它的变化是在可控的范围内的话用顺序栈会好点
栈的作用：简化了程序设计的问题，划分了不同关注层次，使得思考范围缩小，更加聚焦于解决问题的核心。
栈的应用——递归
当n=0时,F(n)=0；
n=1时，F(n)=1；
n>1时,F(n)=F(n-1)+F(n-2);
Java/C实现斐波那契数列
package com.example.summer01.P2.stack;
import java.util.Scanner;
@SuppressWarnings("all")
public class Test1 {
// Java/C实现斐波那契数列
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println(Fbi(sc.nextInt()));
// System.out.println(Fbi2(6));
}
// 递归，调用自身函数
static int Fbi(int n){
if (n < 2) {
return n == 1 ? 1 : 0;
}
return Fbi(n-1)+Fbi(n-2);
}
//实现数组
static int Fbi2(int n) {
int[] a = new int[100];
if (n >100 || n <0) {
return -1;
}
a[0]=1;a[1] = 1;
if (n<2){
return n==0 ? 0:1;
}
for (int i = 2; i < n; i++) {
a[i] =a[i-1]+a[i-2];
}
return a[n-1];
}
}C语言实现：
//C语言：递归实现 Fibonacci数列
//输入n,求 Fibonacci[n] （在数学中，常常写作Fibonacci(n) ）
#include <stdio.h>
#define N 100
long Fibonacci(int n);
int main(){
int n;
long k;
printf("请输入n:");
scanf("%d",&n);
k=Fibonacci(n);
putchar('\n');
printf("Fibonacci(%d)=%ld\n",n,k);
return 0;
}
long Fibonacci(int n){
if(n==1||n==2)
{
return 1;
}
else{
return Fibonacci(n-1)+Fibonacci(n-2);
}
}递归：把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称为递归函数。
每个递归定义必须至少有一个条件，满足时递归不再进行，即不再引用自身而是返回值退出。迭代跟递归的区别：
迭代使用的是循环结构，递归使用的是选择结构。栈的应用
1.基于后缀表达式的计算
计算规则：
遍历后缀表达式中的数字和符号
对于数字：进栈
对于符号：
从栈中弹出右操作数
从栈中弹出左操作数
根据符号进行运算
将运算结果压入栈中
遍历结束：栈中的唯一数字为计算结果后缀表达式：9 3 1 - 3 * + 10 2 / +2.中缀表达式转后缀表达式
5+4 ----》》 5 4 +
1+2*3 ----》》 1 2 3 * +
8+(3-1)*5 ---->> 8 3 1 - 5 * +中缀表达式：9+(3-1)*3+10/2 -------->>>转为后缀表达式：9 3 1 - 3 * + 10 2 / +
代码实现：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct node//压栈和出栈都在栈顶进行(这里的栈顶指前一段)
{
char val;//数据
struct node* next;//指针
}pnode;
typedef struct seqstack
{
int size;//记录栈的大小
pnode* top;//指向栈顶元素
}phead;
phead* initstack()//创建栈
{
phead* istack=(phead*)malloc(sizeof(phead));//为头节点分配空间
if(istack!=NULL)//健壮性判断
{
istack->top=NULL;
istack->size=0;
}
return istack;
}
int isempty(phead* istack)//判断栈为空
{
if(istack->top==NULL)
{
return 1;//栈为空
}
return 0;//栈不为空
}
pnode* seqstack_top(phead* istack)//获取栈顶元素的数据节点
{
if(istack->size!=0)//栈不为空
{
return istack->top;//返回的是栈顶的数据节点而不是栈顶的元素
}
return NULL;
}
pnode* seqstack_pop(phead* istack)//弹出栈顶元素
{
if(isempty(istack)==0)//栈不为空
{
pnode* account=istack->top;//记录栈顶的数据节点
istack->top=istack->top->next;//指向栈顶下一个元素
istack->size--;//记录栈的大小
return account;//返回弹出的数据节点
}
return NULL;
}
void seqstack_push(phead* istack,char x)//压栈(入栈)
{
pnode* temp;//进行压栈的数据节点
temp=(pnode*)malloc(sizeof(pnode));
temp->val=x;//填充数据域
temp->next=istack->top;//连接栈顶的数据节点
istack->top=temp;//充当栈顶
istack->size++;//记录栈大小的变化
return;
}
//下面是中缀表达式转后缀表达式的函数
char buffer[256]={0};//即对数组中每个数据都初始化为'\0'(\0的ascill码是0)
//buffer为结果串
void char_put(char ch)//用来将字符放入放入结果串
{
static int index=0;//static定义静态变量,放函数中表示index只初始化一次,只保留index的改变
buffer[index++]=ch;
}
int priority(char ch)//用来比较优先级
{
int ret=0;
switch(ch)
{
case '+'://case穿透,即上一个case没有break语句时会继续向下执行
case '-':
ret=1;
break;
case '*':
case '/':
ret=2;
break;
default://这里直接break也可以
break;
}
return ret;
}
int is_number(char ch)//是不是数字
{
return(ch>='0'&&ch<='9');//数字返回1，否则返回0
}
int is_operator(char ch)//是不是运算符
{
return(ch=='+'||ch=='-'||ch=='*'||ch=='/');
}
int is_left(char ch)//是不是左括号
{
return(ch=='(');
}
int is_right(char ch)//是不是右括号
{
return(ch==')');
}
int transform(char str[])//使用const保护数据,函数用来将中缀转换成后缀
{
phead* istack=initstack();//创建一个栈
int i=0;
while(str[i]!='\0')//遍历整个字符串
{
//判断是不是数字
if(is_number(str[i])==1)
{
if(is_number(str[i+1])==1)//后面1也是数字,则直接放
{
char_put(str[i]);//数字直接放入结果串(即输出)
}
else//后面不是数字,添加一个空格作为分隔符
{
char_put(str[i]);
char_put(' ');
}
}
else if(is_operator((str[i]))==1)
{
if(str[i+1]=='0'&&str[i]=='/')
{
printf("ILLEGAL");
return 0;
}
if(isempty(istack)==0)//栈不为空
{
while((isempty(istack)==0)&&(priority(str[i])<=(priority(seqstack_top(istack)->val))))//栈不为空并且新运算符优先级不高于栈顶
{
char_put(seqstack_pop(istack)->val);//满足条件的栈顶就弹出直到不满足条件
char_put(' ');
}
}
seqstack_push(istack,str[i]);//再将该运算符入栈
}
else if(is_left(str[i]))//左括号直接入栈
{
seqstack_push(istack,str[i]);
}
else if(is_right(str[i]))//判断是不是右括号
{
while(is_left(seqstack_top(istack)->val)!=1)//栈顶不是左括号的情况
{
char_put(seqstack_pop(istack)->val);//弹出并存储到结果串
if(isempty(istack)==1)//栈为空仍未找到左括号
{
printf("没有匹配到左括号\n");
return -1;
}
}
//此时匹配到了左括号
seqstack_pop(istack);
//弹出左括号,这里并不用保存,即两个括号相抵消
}
else
{
printf("有不能识别的字符\n");
return -1;
}
i++;
}
//遍历完了已经
if(str[i]=='\0')//成功遍历到字符串末尾
{
while(isempty(istack)==0)//弹出全部栈中元素
{
if(seqstack_top(istack)->val=='(')//栈顶元素为左括号
{
printf("有没有匹配到的'(',缺少')'\n");
return -1;
}
char_put(seqstack_pop(istack)->val);//将栈中元素放入最终串
}
}
else
{
printf("遍历没有完成！\n");
}
return 1;
}再计算结果：
//下方为计算后缀表达式需要的函数
typedef struct node1//这里的栈是整型栈
{
int val;//数据
struct node1* next;//指针
}pnode1;
typedef struct seqstack1
{
int size;//记录栈的大小
pnode1* top;//指向栈顶元素
}phead1;
phead1* initstack1()//创建栈
{
phead1* istack=(phead1*)malloc(sizeof(phead1));//为头节点分配空间
if(istack!=NULL)//健壮性判断
{
istack->top=NULL;
istack->size=0;
}
return istack;
}
int isempty1(phead1* istack)//判断栈为空
{
if(istack->top==NULL)
{
return 1;//栈为空
}
return 0;//栈不为空
}
int seqstack_top1(phead1* istack)//获取栈顶元素
{
if(istack->size!=0)//栈不为空
{
return istack->top->val;//返回的是栈顶的数据
}
return 99999;
}
int seqstack_pop1(phead1* istack)//弹出栈顶元素
{
if(isempty1(istack)==0)//栈不为空
{
int account=istack->top->val;//记录栈顶的数据节点
istack->top=istack->top->next;//指向栈顶下一个元素
istack->size--;//记录栈的大小
return account;//返回弹出的数据节点
}
return 99999;
}
void seqstack_push1(phead1* istack,int x)//压栈(入栈)
{
pnode1* temp;//进行压栈的数据节点
temp=(pnode1*)malloc(sizeof(pnode1));
temp->val=x;//填充数据域
temp->next=istack->top;//连接栈顶的数据节点
istack->top=temp;//充当栈顶
istack->size++;//记录栈大小的变化
return;
}
int express(int left,int right,char op)//op为运算符,返回运算结果
{
switch (op)
{
case '+':
return left+right;
case '-':
return left-right;
case '*':
return left*right;
case '/':
if(right==0)
{
return 999;
}
return left/right;
default:
break;
}
return -1;
}
int getsize(phead1* stack)
{
return stack->size;
}
int calculate(char str[])//计算后缀表达式
{
phead1* istack2=initstack1();//创建栈
int i=0;
while(str[i]!='\0')//遍历整个后缀表达式
{
char a[6]={0};
int index=0;
if(is_number(str[i])==1)
{
while(is_number(str[i])==1)
{
a[index]=str[i];
index++;
i++;
}
//成功读取数字
seqstack_push1(istack2,atoi(a));//将该整数入栈
}
else if(is_operator(str[i])==1)
{
int right=seqstack_pop1(istack2);
int left=seqstack_pop1(istack2);
int ret=express(left,right,str[i]);
if(ret==999)//被除数为0了
{
printf("ILLEGAL");
return 999;
}
seqstack_push1(istack2,ret);//运算结果入栈
}
else if(str[i]==' ')
{
}
else
{
printf("error\n");
break;
}
i++;
}
if(str[i]=='\0'&&getsize(istack2))
{
return seqstack_top1(istack2);
}
return 0;
}
int main()
{
char str[1024]={0};//将数组每个元素赋值为'\0'
printf("请输入四则运算表达式:\n");
scanf("%s",str);
int number=transform(str);
if(number==-1)
{
printf("表达式转换错误:\n");
}
else if(number==1)
{
printf("转化后的表达式: %s\n",buffer);
}
else
{
return 0;
}
//成功换成后缀表达式
//下方计算后缀表达式
int num=calculate(buffer);
if(num==999)
{
return 0;
}
printf("%d\n",num);
}队列
队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
队列是一种先进先出的线性表，FIFO(Frist In Frist Out)。允许插入一端称为队尾，允许删除的一端称为对头。
队列先进先出
队列为空相当于队首等于队尾
队列的抽象数据类型
循环队列
队列顺序存储
front指针指向对头元素，rear指针指向队尾元素的下一个位置，这样当front等于rear时，此队列不是还剩一个元素，而是空队列
front指针指向的是对头元素，rear是指向队尾元素的下一个位置；如果队列中有一个元素的，front指针指向的是下标为0的位置，而rear指针指向的是下标为1的位置，说明这个时候就是队列中有一个元素。
出队列，front指针指向的下标一直在变，而rear的指针不变，但是当这个时候进入一个元素a5时却出现rear指针移动到数字之外的情况，然而其实前面已经出队列的位置是空的，这时就会出现“假溢出”的现象。
不难看出顺序存储会出现“假溢出”的现象，那么解决”假溢出“的办法是 ：循环队列
“真溢出”：整个队列数组真的全都满了
队空条件：rear==front
队满条件：(rear+1) %QueueSIze==front，其中QueueSize为循环队列的最大长度
计算队列长度：（rear-front+QueueSize）%QueueSize
入队：（rear+1）%QueueSize
出队：（front+1）%QueueSize循环队列：把对俄的这种头尾相接的顺序存储结构 称为循环队列
那么上面那个图就会变成：
方法一：设置一个标志变量flag，当front == rear时，且flag = 0时队列为空；当front == rear，且flag = 1时队列为满。
方法二：当队列空时，条件就是front == rear，当队列满时，修改其条件，保留一个元素空间。就是说，队列满时，数字中还是有一个空闲单元。
计算队列长度：
当rear > front,长度为rear-front
当rear < front,一段为QueueSize-front，一段是0 + rear ，长度为(QueueSize - front + 0 + rear) %QueueSize
队列满的条件：(rear + 1) %QueueSize == front
代码实现循环队列的顺序存储结构：
//1.循环队列的入队
if((Q ->rear+1) % MaxSize == Q->rear){
// 队列满的判断
return error;
}
Q->data[Q->rear]=e; //将元素e赋值给队尾
Q->rear = (Q->rear + 1) %MAXSIZE; //rear指针向后移一位置
return OK;
//2.循环队列的出队
if(Q->front == Q->rear){
// 队列空的判断
return error;
}
*e = Q->data[Q->front]; //将对头元素赋值给e
//front指针向后移一位置
Q->front=(Q->front + 1) %MAXSIZE; //若到最后则转到数组头部
return OK;队列的链式存储
队列的链式存储结构就是线性表的单链表，只不过只能是尾进头出 ——>>> 链队列
typedef struct QNode{
QElemType data;
struct Qnode *next;
}Qnode, *QueuePtr;
typedef struct {
QueuePtr front; //队头指针
QueuePtr rear; //队尾指针
}LinkQueue;
//初始化
Status InitQueue (LinkQueue &Q){
Q.front=Q.rear=(QueuePtr) malloc(sizeof(QNode));
if(!Q.front) exit(OVERFLOW);
Q.front->next=NULL;
return OK;
}判断是否为空
Status GetHead (LinkQueue Q, QElemType &e){
if(Q.front==Q.rear) return ERROR;
e=Q.front->next->data;//有头结点
return OK;
}入队代码实现：就是在队链表尾部插入结点
Status EnQueue(LinkQueue &Q,QElemType e){
p=(QueuePtr)malloc(sizeof(QNode));
if(!p) exit(OVERFLOW);
p->data=e; p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return OK;
}出队代码实现：就是头结点的后继结点出队，将头结点的后继改为它后面的结点，若链表除头结点外只剩一个元素时，则需将rear指向头结点
/* 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR */
Status DeQueue(LinkQueue *Q, QElemType *e)
{
QueuePtr p;
if (Q->front == Q->rear)
return ERROR;
p = Q->front->next; /* 将欲删除的队头结点暂存给p，见图中① */
*e = p->data; /* 将欲删除的队头结点的值赋值给e */
Q->front->next = p->next; /* 将原队头结点的后继p->next赋值给头结点后继，见图中② */
if (Q->rear == p) /* 若队头就是队尾，则删除后将rear指向头结点，见图中③ */
Q->rear = Q->front;
free(p);
return OK;
}完整代码
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */
typedef int Status;
typedef int QElemType; /* QElemType类型根据实际情况而定，这里假设为int */
typedef struct QNode /* 结点结构 */
{
QElemType data;
struct QNode *next;
} QNode, *QueuePtr;
typedef struct /* 队列的链表结构 */
{
QueuePtr front, rear; /* 队头、队尾指针 */
} LinkQueue;
Status visit(QElemType c)
{
printf("%d ", c);
return OK;
}
/* 构造一个空队列Q */
Status InitQueue(LinkQueue *Q)
{
Q->front = Q->rear = (QueuePtr)malloc(sizeof(QNode));
if (!Q->front)
exit(OVERFLOW);
Q->front->next = NULL;
return OK;
}
/* 销毁队列Q */
Status DestroyQueue(LinkQueue *Q)
{
while (Q->front)
{
Q->rear = Q->front->next;
free(Q->front);
Q->front = Q->rear;
}
return OK;
}
/* 将Q清为空队列 */
Status ClearQueue(LinkQueue *Q)
{
QueuePtr p, q;
Q->rear = Q->front;
p = Q->front->next;
Q->front->next = NULL;
while (p)
{
q = p;
p = p->next;
free(q);
}
return OK;
}
/* 若Q为空队列,则返回TRUE,否则返回FALSE */
Status QueueEmpty(LinkQueue Q)
{
if (Q.front == Q.rear)
return TRUE;
else
return FALSE;
}
/* 求队列的长度 */
int QueueLength(LinkQueue Q)
{
int i = 0;
QueuePtr p;
p = Q.front;
while (Q.rear != p)
{
i++;
p = p->next;
}
return i;
}
/* 若队列不空,则用e返回Q的队头元素,并返回OK,否则返回ERROR */
Status GetHead(LinkQueue Q, QElemType *e)
{
QueuePtr p;
if (Q.front == Q.rear)
return ERROR;
p = Q.front->next;
*e = p->data;
return OK;
}
/* 插入元素e为Q的新的队尾元素 */
Status EnQueue(LinkQueue *Q, QElemType e)
{
QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
if (!s) /* 存储分配失败 */
exit(OVERFLOW);
s->data = e;
s->next = NULL;
Q->rear->next = s; /* 把拥有元素e的新结点s赋值给原队尾结点的后继，见图中① */
Q->rear = s; /* 把当前的s设置为队尾结点，rear指向s，见图中② */
return OK;
}
/* 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR */
Status DeQueue(LinkQueue *Q, QElemType *e)
{
QueuePtr p;
if (Q->front == Q->rear)
return ERROR;
p = Q->front->next; /* 将欲删除的队头结点暂存给p，见图中① */
*e = p->data; /* 将欲删除的队头结点的值赋值给e */
Q->front->next = p->next; /* 将原队头结点的后继p->next赋值给头结点后继，见图中② */
if (Q->rear == p) /* 若队头就是队尾，则删除后将rear指向头结点，见图中③ */
Q->rear = Q->front;
free(p);
return OK;
}
/* 从队头到队尾依次对队列Q中每个元素输出 */
Status QueueTraverse(LinkQueue Q)
{
QueuePtr p;
p = Q.front->next;
while (p)
{
visit(p->data);
p = p->next;
}
printf("\n");
return OK;
}
int main()
{
int i;
QElemType d;
LinkQueue q;
i = InitQueue(&q);
if (i)
printf("成功地构造了一个空队列!\n");
printf("是否空队列？%d(1:空 0:否) ", QueueEmpty(q));
printf("队列的长度为%d\n", QueueLength(q));
EnQueue(&q, -5);
EnQueue(&q, 5);
EnQueue(&q, 10);
printf("插入3个元素(-5,5,10)后,队列的长度为%d\n", QueueLength(q));
printf("是否空队列？%d(1:空 0:否) ", QueueEmpty(q));
printf("队列的元素依次为：");
QueueTraverse(q);
i = GetHead(q, &d);
if (i == OK)
printf("队头元素是：%d\n", d);
DeQueue(&q, &d);
printf("删除了队头元素%d\n", d);
i = GetHead(q, &d);
if (i == OK)
printf("新的队头元素是：%d\n", d);
ClearQueue(&q);
printf("清空队列后,q.front=%u q.rear=%u q.front->next=%u\n", q.front, q.rear, q.front->next);
DestroyQueue(&q);
printf("销毁队列后,q.front=%u q.rear=%u\n", q.front, q.rear);
return 0;
}递归
就是方法自己去调用自己，每次调用的时候传入的参数是不同的，递归有助于解决程序中复杂的问题，同时可以让代码更为简洁。
可以解决的问题：
1.解决数学问题，汉诺塔，迷宫问题，8皇后问题等
2.各种算法的递归，如快排，归并排序，二分查找，分治算法等。规则：
1.执行一个方法时，就创建一个新的受保护的独立栈空间
2.方法的局部变量时独立的，不会相互影响。
3.如果方法中使用的时引用型类型变量，比如数组，则会共享引用型的数据
4.递归必须向退出递归的条件接近，否则就是无限递归，会出现StackOverflowError;
5.一个方法执行完毕后，或者遇到return就会返回数据，遵守调用就将结果返回给谁，同时当方法执行完毕或者返回时，该方法也就执行完毕，package com.example.summer01.P2.queue;
// 递归
public class MazeApp {
public static void main(String[] args) {
int[][] map = new int[8][7];
//设置第一行和最后一行，设置为1
for (int i = 0; i < 7;i++) {
map[0][i]=1;
map[7][i] =1;
}
//设置第一列和第七列为墙
for (int i = 0; i < 8;i++) {
map[i][0] = 1;
map[i][6] = 1;
}
//设置障碍墙
map[3][1] = 1;
map[3][2] = 1;
System.out.println("新的迷宫");
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 7; j++) {
System.out.print(map[i][j]+" ");
}
System.out.println();
}
isRun(map,1,1);
System.out.println("小球走的路线");
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 7; j++) {
System.out.print(map[i][j]+" ");
}
System.out.println();
}
}
/**
* 1.小球从哪个位置出发的，起始位置 1:1
* 2.map时地图对象
* 3.最终小球到达了 6:5
* 4.元素为0时表示该点没有走过，元素为1表示墙，元素为2表示可以走，元素为3表示已经走过了但是走不通了
*/
public static boolean isRun(int[][] map,int i ,int j){
if(map[6][5] == 2){
return true;
}else {
if (map[i][j] == 0){
//没有走过该值
map[i][j] = 2;
//下 右 上 左
if(isRun(map,i +1 ,j)){
return true;
}else if (isRun(map, i, j+1)){
return true;
}else if (isRun(map,i-1,j)){
return true;
}else if (isRun(map, i, j-1)) {
return true;
}else {
map[i][j] = 3;
return false;
}
}else {
return false;
}
}
}
}
