线性表

栈&队列

串

二叉树

持续更新中，尽请期待！！！

栈的顺序存储结构代码实现

#include<bits/stdc++.h>
using namespace std;
#define SElemType int
#define Status int
#define STACK_INIT_SIZE 100 
#define STACKINCREMENT 10 

//-------栈的顺序存储结构-----------------
typedef struct{
   
    SElemType *base;    //栈底
    SElemType *top;     //栈顶
    int stacksize;
} SqStack;

Status InitStack(SqStack &s){
   
    s.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
    if (!s.base)
        exit(_OVERFLOW);
    s.top = s.base;
    s.stacksize = STACK_INIT_SIZE;
    return 1;
}

Status DestoryStack(SqStack &s){
   
    free(s.base);
    s.base = NULL;
    s.top = NULL;
    s.stacksize = 0;
    return 1;
}

Status ClearStack(SqStack &s){
   
    if(!s.base)
        return 0;
    s.top = s.base;
    return 1;
}

Status StackEmpty(SqStack s){
   
    if(s.top==s.base)
        return 1;
    return 0;
}

int StackLength(SqStack s){
   
    if(!s.base)
        return 0;
    return (int)(s.top - s.base);
}

Status GetTop(SqStack s,SElemType &e){
   
    if(s.base==s.top)
        return 0;
    e = *(s.top - 1);
    return 1;
}

Status Push(SqStack &s,SElemType e){
   
    if(!s.base)
        return 0;
    if (s.top - s.base >= s.stacksize){
   
        s.base = (SElemType *)realloc(s.base, (s.stacksize + STACKINCREMENT) * sizeof(SElemType));
        if(!s.base)
            exit(_OVERFLOW);
        s.top = s.base + s.stacksize;
        s.stacksize += STACKINCREMENT;
    }
    *s.top++ = e;
    return 1;
}

Status Pop(SqStack &s,SElemType &e){
   
    if(!s.base||s.top==s.base)
        return 0;
    e = *--s.top;
    return 1;
}

void visit(SElemType e){
   
    cout << e << " ";
}

Status StackTraverse(SqStack s,void (*visit)(SElemType)){
   
    SElemType *p = s.base;
    if(!s.base)
        return 0;
    while (p < s.top)
        visit(*p++);
    cout << "\n";
    return 1;
}

//算法3.1
void conversion(){
   
    //进制转换
    SqStack S;
    InitStack(S);
    SElemType N, e;
    scanf("%d", &N);
    while(N){
   
        Push(S, N % 8);
        N /= 8;
    }
    while(!StackEmpty(S)){
   
        Pop(S, e);
        cout << e;
    }
}
// int main(){
   
// conversion();
// return 0;
// }

//算法3.2
void LineEdit(){
   
    SqStack S;
    InitStack(S);
    SElemType c;
    char ch = getchar();
    while (ch != EOF){
   
        while (ch != EOF && ch != '\n'){
   
            switch (ch){
   
                case '#':
                    Pop(S, c);
                    break;
                case '@':
                    ClearStack(S);
                    break;
                default:
                    Push(S, ch);
            }
            ch = getchar();
        }
        ClearStack(S);
        if (ch != EOF)
            ch = getchar();
    }
    DestoryStack(S);
}
// int main(){
   
// LineEdit();
// return 0;
// }

//算法3.3
//见后文

//算法3.4
//见后文

//算法3.5
int C = 0;
void move(char x, int n, char z) {
   
    cout << ++C << ". Move disk " << n << " from " << x << " to " << z << "."<<endl;
}
void hanoi(int n, char x, char y, char z) {
    
    if (n == 1)
        move(x, 1, z);        //将编号为１的圆盘从x移到z
    else {
   
        hanoi(n - 1, x, z, y);
        move(x, n, z);        //将编号为n的圆盘从x移到z
        hanoi(n - 1, y, x, z);  //将y上编号为１至n-1的圆盘移到z,x作辅助塔
    }
}

//简单测试主函数
int main(){
   
    SqStack s;
	cout << "InitStack" << endl;
	InitStack(s);
	cout << "StackEmpty" << endl;
	StackEmpty(s) ? cout << "yes\n" : cout << "no\n";
	cout << "Push" << endl;
	for (int i = 1; i <= 6; i++)
		Push(s, i);
	cout << "StackTraverse" << endl;
	StackTraverse(s, visit);
	cout << "StackLength" << endl;
    cout << StackLength(s) << endl;
    cout << "Pop" << endl;
	SElemType e;
	Pop(s, e);
	cout << e << endl;
	StackTraverse(s, visit);
	cout << "GetTop" << endl;
	GetTop(s, e);
	cout << e << endl;

	return 0;
}

算法3.3 迷宫求解【顺序栈代码实现】

#include<bits/stdc++.h>
using namespace std;
#define Status int
#define STACK_INIT_SIZE 100 
#define STACKINCREMENT 10 
typedef int DirectiveType; //下一个通道方向
#define RANGE 100 //迷宫大小
#define ROW 10 //迷宫的行数
#define COL 10 //迷宫的列数
#define step ord
typedef struct{
   
    int m, n;
    int arr[RANGE][RANGE]; //迷宫数组
} MazeType; //迷宫的类型

typedef struct{
   
    int row; //迷宫中的行
    int col; //迷宫中的列
} PosType; //坐标(row,col)

typedef struct
{
   
    int ord; //当前位置在路径上的"序号"
    PosType seat; //当前的坐标位置
    int di; //往下一个坐标位置的方向
} SElemType; //栈的元素类型


typedef struct{
   
    SElemType *base;    //栈底
    SElemType *top;     //栈顶
    int stacksize;
} SqStack;

Status InitStack(SqStack &s){
   
    s.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
    if (!s.base)
        exit(_OVERFLOW);
    s.top = s.base;
    s.stacksize = STACK_INIT_SIZE;
    return 1;
}

Status DestoryStack(SqStack &s){
   
    free(s.base);
    s.base = NULL;
    s.top = NULL;
    s.stacksize = 0;
    return 1;
}

Status ClearStack(SqStack &s){
   
    if(!s.base)
        return 0;
    s.top = s.base;
    return 1;
}

Status StackEmpty(SqStack s){
   
    if(s.top==s.base)
        return 1;
    return 0;
}

int StackLength(SqStack s){
   
    if(!s.base)
        return 0;
    return (int)(s.top - s.base);
}

Status GetTop(SqStack s,SElemType &e){
   
    if(s.base==s.top)
        return 0;
    e = *(s.top - 1);
    return 1;
}

Status Push(SqStack &s,SElemType e){
   
    if(!s.base)
        return 0;
    if (s.top - s.base >= s.stacksize){
   
        s.base = (SElemType *)realloc(s.base, (s.stacksize + STACKINCREMENT) * sizeof(SElemType));
        if(!s.base)
            exit(_OVERFLOW);
        s.top = s.base + s.stacksize;
        s.stacksize += STACKINCREMENT;
    }
    *s.top++ = e;
    return 1;
}

Status Pop(SqStack &s,SElemType &e){
   
    if(!s.base||s.top==s.base)
        return 0;
    e = *--s.top;
    return 1;
}

Status StackTraverse(SqStack s,void (*visit)(SElemType)){
   
    SElemType *p = s.base;
    if(!s.base)
        return 0;
    while (p < s.top)
        visit(*p++);
    cout << "\n";
    return 1;
}
//-----------迷宫部分函数-------------
bool InitMaze(MazeType &maze, int a[ROW][COL], int row, int col)  //初始化迷宫
{
   
    int i, j;                            //设置迷宫maze的初值,包括加上边缘一圈的值
    for (i = 1; i<row - 1;i++){
   
       for (j = 1; j<col - 1; j++)
        {
   
           maze.arr[i][j] = a[i][j];
        }
    }                                          
    for (j = 0; j<row; j++)                     //加上围墙
        maze.arr[0][j] = maze.arr[row - 1][j] = 1;
    for (i = 0; i<col; i++)
        maze.arr[i][0] = maze.arr[i][col - 1] = 1;
    return true;
}

bool Pass(MazeType maze, PosType curpos){
                //判断当前节点是否通过 
    if (maze.arr[curpos.row][curpos.col]== 0)     //当节点为0时返回真
       return true;
    else
       return false;
}

bool FootPrint(MazeType &maze, PosType curpos){
          //留下足迹

    maze.arr[curpos.row][curpos.col] = 2; //走过且走得通
    return true;
}

bool MarkPrint(MazeType &maze, PosType curpos){
        //留下不能通过的标记
    maze.arr[curpos.row][curpos.col] = 3;        //走过但走不通
    return true;
}

SElemType CreateSElem(int step, PosType pos, int di){
              //创建元素e 
    SElemType e;
    e.step = step;
    e.seat = pos;
    e.di = di;
    return e;
}

PosType NextPos(PosType curpos, DirectiveType di){
     //curpos当前位置 //返回当前节点的下一节点 
    PosType pos = curpos;
    switch (di){
   
        case 1:        //右
            pos.col++;
            break;
        case 2:        //下
            pos.row++;
            break;
        case 3:        //左
            pos.col--;
            break;
        case 4:        //上
            pos.row--;
            break;
        }
    return pos;
}

bool PosEqual(PosType pos1, PosType pos2){
                 //判断是不是出口 
    if (pos1.row == pos2.row&& pos1.col == pos2.col)    
       return true;                            
    else
       return false;
}

void PrintMaze(MazeType maze, int row, int col){
         //打印路径 
    int i, j;
    printf(" ");
    for (i = 0; i<col; i++)                    //打印列数名
       printf("%d ", i);
    printf("\n");
    for (i = 0; i<row; i++){
   
       printf("%d",i);                      //打印行数名
       for (j = 0; j<col; j++){
   
            switch (maze.arr[i][j]){
   
                case 0:
                    printf(" ");                 //没走过，但是通路
                    break;
                case 1:
                    printf("■");                  //墙，障碍物
                    break;
                case 2:
                    printf("*");
                    break;
                case 3:
                    printf("@"); 
                    break;
                default:
                    break;
           }
       }
       printf("\n");
    }
}

Status MazePath(MazeType &maze, PosType start, PosType end){
    //求解迷宫maze中,从入口start到出口end的一条路径
    SqStack s;                  //定义栈
    SElemType e;            
    InitStack(s);               //初始化栈
    PosType curpos = start;             
    int curstep = 1;                                //探索第一步
    do {
   
        if (Pass(maze, curpos)){
       //如果当前位置可以通过,即是未曾走到的通道块
            FootPrint(maze,curpos);                //留下足迹
            e = CreateSElem(curstep,curpos, 1);    //创建元素
            Push(s, e);                             //加入路径
            if (PosEqual(curpos,end))              //到达终点（出口）
                return true;                        
            curpos = NextPos(curpos,1);            //获得下一节点
                return true;                        
            curstep++;                              //探索下一步
        }
        else{
          //当前位置不能通过
            if (!StackEmpty(s)){
   
                Pop(s, e);
                while (e.di == 4&& !StackEmpty(s)){
    //找寻了四个方向 
                    MarkPrint(maze,e.seat);
                    Pop(s, e);                      //留下不能通过的标记,并退回一步
                }
                if (e.di<4){
   
                    e.di++;                         //换一个方向探索
                        Push(s, e);
                    curpos =NextPos(e.seat, e.di); //设定当前位置是该方向上的相邻块
                }
            }
        }
    } while (!StackEmpty(s));
    return 0;
}

算法3.4 表达式求值【链式栈代码实现】

#include<bits/stdc++.h>
using namespace std;
#define SElemType char
#define Status int
typedef char OperandType;

// -----栈的链式存储结构----------------------------------
typedef struct SNode {
   
    SElemType data;                 // 数据域
    struct SNode *next;             // 指针域
} SNode, *LinkStack;


Status InitStack(LinkStack &S) {
   
    S = (LinkStack)malloc(sizeof(SNode));
    if(!S)                          // 存储分配失败
        exit(_OVERFLOW);             // exit(-2)程序异常退出
    S->next = NULL;
    return 1;
}
 
// 操作结果：销毁栈S，S不再存在。
Status DestroyStack(LinkStack &S) {
   
    LinkStack p = S->next, ptmp;    // p指向栈顶
    while(p) {
                         // p指向栈底时，循环停止
        ptmp = p->next;
        free(p);                    // 释放每个数据结点的指针域
        p = ptmp;
    }
    free(S);
    return 1;
}
 
// 操作结果：把S置为空栈。
Status ClearStack(LinkStack &S) {
   
    LinkStack p = S->next, ptmp;    // p指向栈顶
    while(p) {
                         // p指向栈底时，循环停止
        ptmp = p->next;
        free(p);                    // 释放每个数据结点的指针域
        p = ptmp;
    }
    S->next = NULL;
    return 1;
}
 
// 操作结果：若S为空栈，返回TRUE，否则返回FALSE
Status StackEmpty(LinkStack S) {
   
    if(S->next == NULL)
        return 1;           
    else
        return 0;      
}
 
// 操作结果：返回S的元素个数，即栈的长度。
int StackLength(LinkStack S) {
   
    int n = 0;
    LinkStack p = S->next;          // p指向栈顶
    while(p) {
   
        n++;
        p = p->next;
    }
    return n;
}
 
// 操作结果：若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR。
Status GetTop(LinkStack S, SElemType &e) {
   
    if ( S->next == NULL )
        return 0;
    e = S->next->data;     // 取栈顶元素
    return 1;
}
 
// 操作结果：插入元素e为新的栈顶元素。
Status Push(LinkStack &S, SElemType e) {
   
    LinkStack p = (LinkStack)malloc(sizeof(SNode));
    p->data = e;
    p->next = S->next;              // 新结点指向栈顶
    S->next = p;                    // 更新栈顶指针
// printf("插入的栈顶元素："); visit(e);
    return 1;
}// Push
 
// 操作结果：若栈不空，则删除S的栈顶元素，并用e返回其值；否则返回ERROR。
Status Pop(LinkStack &S, SElemType &e) {
   
    // 若1个元素也没有：
    if (S->next == NULL)
        return 0;
    // 若有1个以上元素
    e = S->next->data;
    LinkStack ptmp = S->next->next;
    free(S->next);
    S->next = ptmp;
// printf("删除的栈顶元素："); visit(e);
    return 1;
}// Pop
 
 
Status visit(SElemType e) {
   
    printf(" %c\n", e);
    return 1;
}

// 操作结果：从 栈底到栈顶 依次对栈中每个数据元素调用函数visit()。一旦vistit()失败，刚操作失败。
Status StackTraverse(LinkStack S, Status (*visit)(SElemType)) {
   
    if(S->next == NULL){
   
        printf("栈为空!\n");
        return 0;
    }
    for(int i=StackLength(S); i>0; i--){
   
        LinkStack p = S->next;      // p指向栈顶
        int j = 1;                  // j为计数器
        while ( p && j<i ) {
           // 顺指针向后查找，直到p指向第i个元素或p为空
            p = p->next;
            ++j;
        }
        visit(p->data);
    }
    printf("\n");
    return 1;
}

// 操作结果：从 栈顶到栈底 依次对栈中每个数据元素调用函数visit()。一旦vistit()失败，刚操作失败。
Status StackTraverse_Top(LinkStack S, Status (*pfn_visit)(SElemType)) {
   
    if(S->next == NULL){
   
        printf("栈为空!\n");
        return 0;
    }
    LinkStack p = S->next;          // p指向栈顶
    while(p) {
   
        visit(p->data);
        p = p->next;
    }
    printf("\n");
    return 1;
}
 
//----------------------算法部分------------------------------
// 判定运算符栈的（栈顶运算符θ1）与（读入的运算符θ2）之间的优先关系
SElemType Precede(SElemType t1, SElemType t2){
   
    SElemType t;
    switch (t1){
   
        case '+':
        case '-':
            if(t2=='*' || t2=='/' || t2=='(')
                t = '<';
            else t = '>';
            break;
        case '*':
        case '/':
            if(t2 == '(')
                t = '<';
            else t = '>';
            break;
        case '(':
            if(t2 == ')')
                t = '=';
            else if(t2 == '#')
                return 0;
            else t = '<';
            break;
        case ')':
            if(t2 == '(')
                return 0;
            else t = '>';
            break;
        case '#':
            if(t2 == ')')
                return 0;
            else if(t2 == '#')
                t = '=';
            else t = '<';
            break;
    }
    return t;
}

// 进行二元运算 a θ b
SElemType Operator(SElemType a, SElemType theta, SElemType b){
    
    SElemType ret;
    switch(theta){
   
        case '+':
            ret = (a-48) + (b-48) + 48;
            break;
        case '-':
            ret = (a-48) - (b-48) + 48;
            break;
        case '*':
            ret = (a-48) * (b-48) + 48;
            break;
        case '/':
            ret = (a-48) / (b-48) + 48;
            break;
    }
    return ret;
}
 
Status In(SElemType c){
    
    switch(c){
   
        case '+':
        case '-':
        case '*':
        case '/':
        case '(':
        case ')':
        case '#':
        case '=':
            return 1;
            break;
        default:
            return 0;
    }
}
//算法3.4
OperandType ExvaluateExpression()
{
    // 算术表达式求值的算符优先算法。设OPTR和OPND分别为运算符栈和运算数栈，OP为运算符集合。
    LinkStack OPTR;                // 运算符栈：寄存运算符
    LinkStack OPND;                // 运算数栈：寄存操作数或运算结果
    char c, x, theta, a, b, e;
 
    InitStack(OPTR);
    InitStack(OPND);
    Push(OPTR, '#');                // 表达式起始符“#”为运算符栈的栈底元素
    printf("输入表达式:\n");
    c = getchar();
    GetTop(OPTR, e);
    while (c!='#' || e!='#'){
           // 当前读入的字符 或 运算符栈顶元素不为‘#’号
        if (!In(c)) {
                   // 不是运算符(操作数、结果)则进栈
            Push(OPND, c);
            c = getchar();
        }
        else{
                           // 是运算符，则和运算符栈顶的运算符比较优先级 
            GetTop(OPTR, e);
            switch (Precede(e, c)){
   
                case '<':           // 栈顶元素优先权低
                    Push(OPTR, c);
                    c = getchar();
                    break;
                case '=':           // 脱括号并接收下一字符
                    Pop(OPTR, x);
                    c = getchar();
                    break;
                case '>':           // 退栈并将运算结果入栈
                    Pop(OPTR, theta);
                    Pop(OPND, b);
                    Pop(OPND, a);
                    Push(OPND, Operator(a, theta, b));
                    break;
            }
        }
        GetTop(OPTR, e);
    }
    GetTop(OPND, e);
    return e;
}
 
int main(){
   
    // 3*(7-2)#=15
    char c;
    do {
   
        fflush(stdin);      //清空缓冲区
        c = ExvaluateExpression();
        printf("表达式的值:");
        printf("%d\n", c-48);
        printf("是否继续(y/n):");
    } while(scanf("%s", &c)!=0 && (c=='y' || c=='Y'));
    return 0;
}