网站优化查询,免费建站网站一级,推广网站都有哪些,网站如何实现微数据结构-栈和队列 2.1栈2.1.1栈的表示和实现2.1.2栈的应用举例数制转换括号匹配检验迷宫给求解表达式求值 2.1.3链栈的表示和实现2.1.4栈与递归的实现遍历输出链表中各个结点的递归算法*Hanoi塔问题的递归算法 2.2队列2.2.1循环队列——队列的顺序表示和实现2.2.2链队——队列… 数据结构-栈和队列 2.1栈2.1.1栈的表示和实现2.1.2栈的应用举例数制转换括号匹配检验迷宫给求解表达式求值 2.1.3链栈的表示和实现2.1.4栈与递归的实现遍历输出链表中各个结点的递归算法*Hanoi塔问题的递归算法 2.2队列2.2.1循环队列——队列的顺序表示和实现2.2.2链队——队列的链式表示和实现 2.1栈 栈是限定仅在表尾进行插入或删除操作的线性表因此对栈来说表尾端有其特殊含义称为栈顶top相应地表头称为栈底。 E为栈底元素A为栈顶元素。也就意味着栈的修改是按后进先出的原则进行的。因此栈又称为后进先出线性表简称LIFO结构。
2.1.1栈的表示和实现
和线性表类似栈也有两种存储表示方式。 顺序栈即栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素同时附设指针top指示栈顶元素在顺序栈中的位置。通常的习惯做法是top0表示空栈鉴于C语言中数组的下标约定从0开始则当以C作描述语言时如设定会带来很大不便另一方面由于栈在使用过程中所需最大空间的大小很难估计一般来说在初始化设空栈时不应限定栈的最大容量。一个较合理的做法是先分配一个基本容量然后在应用过程中当栈的空间不够使用时再逐段扩大。为此可设定两个常量STACK_INIT_SIZE存储空间初始分配量和STACKINCREMENT存储空间分配增量。 top 并不是栈顶元素而是指向栈顶元素的下一个位置。 top - 1 才是真正的栈顶元素位置。 typedef struct{SElemType *base; //栈底指针SElemType *top; //栈顶指针,其初值指向栈底int stacksize; //栈当前可使用的最大容量//每当插入心得栈顶元素时,指针top1
};顺序栈所有操作汇总
#includestdio.h
#includestdlib.h#define SElemType int
#define STACK_INIT_SIZE 100 //存储空间初始分配量
#define STACKINCREMENT 10 //存储空间分配增量
#define Status inttypedef 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(0); //存储分配失败S.top S.base;S.stacksize STACK_INIT_SIZE;return 1;
}Status Push(SqStack S, SElemType e){//插入元素e为新的栈顶元素if(S.top - S.base S.stacksize){ //栈满.追加存储空间 S.base (SElemType *) realloc(S.base, (S.stacksize STACKINCREMENT) * sizeof(SElemType));if(!S.base) exit(0); //存储分配失败S.top S.base S.stacksize;S.stacksize STACKINCREMENT; } *S.top e;return 1;
}Status Pop(SqStack S, SElemType e){//若栈不为空,则删除S的栈顶元素,用e返回其值if(S.top S.base) return 0; //空栈e * --S.top; //先将S.top赋值给e,再自减return 1;
}Status GetTop(SqStack S, SElemType e){//若栈不为空,则用e返回S的栈顶元素if(S.top S.base) return 0;e *(S.top - 1);return 1;
}int StackLength(SqStack S){//返回栈的元素个数,即栈的长度 return S.top - S.base;
}int StackEmpty(SqStack S){//返回栈是否为空,为空返回0,不为空返回1if(!StackLength(S)) return 0;return 1;
}void ClearStack(SqStack S){//把S置为空栈S.top S.base;
}void DestroyStack(SqStack S){//销毁栈 if(S.base){free(S.base);S.base S.top NULL;S.stacksize 0;}
}int main()
{SqStack S;InitStack(S);Push(S, 1);Push(S, 2);int e; Pop(S, e);printf(%d\n, e);GetTop(S, e);printf(%d\n, e);int l StackLength(S);printf(length: %d\n, l);return 0;
}2.1.2栈的应用举例
数制转换
将十进制数N和其他d进制数的转换。算法原理如下 N ( N / d ) ∗ d N m o d d N (N/d)*dN \ \ mod \ \ d N(N/d)∗dN mod d 要求 对于输入的任意一个非负十进制整数打印与其等值的八进制数。
//栈的操作与2.1.1中代码相同
int main()
{SqStack S;InitStack(S);printf(请输入一个非负的十进制数: );int numT;scanf(%d, numT);while(numT){Push(S, numT % 8);numT / 8;} int e;while(StackEmpty(S)){Pop(S, e);printf(%d, e);}return 0;
}括号匹配检验
假设表达式中允许包含两种括号圆括号和方括号其嵌套顺序随意即()为正确格式[{]为不正确格式。 要求 输入只含圆括号和方括号的字符串判断其是否是正确的格式。
//要加上#includestring.h
int main()
{SqStack S;InitStack(S);char str[100];printf(输入只含圆括号和方括号的字符串: );scanf(%s, str);int length strlen(str), i, flag 1, e;//(为1, )为2, [为3, ]为4 for(i 0; i length; i ){if(str[i] [) Push(S, 3);if(str[i] () Push(S, 1);if(str[i] )) {GetTop(S, e);if(e 1) Pop(S, e);} if(str[i] ]) {GetTop(S, e);if(e 3) Pop(S, e);}}if(!StackEmpty(S)) printf(%s是合法字符串\n, str);else printf(%s不是合法字符串\n, str);return 0;
}迷宫给求解
链接: C语言 严蔚敏 数据结构 迷宫求解_顺序栈应用
类似于深度优先搜索用栈去模拟这个过程。
表达式求值
链接: C语言 严蔚敏 数据结构 表达式求值_顺序栈应用 类似于括号匹配检验。
2.1.3链栈的表示和实现
链栈是指采用链式存储结构实现的栈。通常链栈用单链表来实现。 由于栈的主要操作是在栈顶插入和删除显然以链表的头部作为栈顶是最方便的。
#includestdio.h
#includestdlib.h#define List_Init_Size 100 //线性表存储空间的初始分配量
#define ListIncreMent 10 //线性表存储空间的分配增量
#define ElemType int
#define Status inttypedef struct StackNode{ElemType data;struct StackNode *next;
}StackNode, *LinkStack;Status InitStack(LinkStack S) {// 构造一个空栈,栈顶指针为空S NULL;return 1;
}Status Push(LinkStack S, ElemType e) {//和顺序栈的入栈不同,链栈的入栈前不需要判断栈是否满,只需要为入栈动态分配一个节点空间StackNode *p (StackNode *)malloc(sizeof(StackNode)); // 使用 malloc 分配内存if (p NULL) {// 内存分配失败的处理return 0;}p-data e;p-next S;S p; // 栈顶指针指向新节点return 1;
}Status Pop(LinkStack S, ElemType e) {if (S NULL) {return 0; // 空栈返回失败}e S-data; // 获取栈顶元素StackNode *p S; // 声明指针 p指向栈顶元素S S-next; // 将栈顶指针指向下一个元素free(p); // 释放栈顶元素的内存return 1; // 返回成功
}ElemType GetTop(LinkStack S){//返回S的栈顶元素 if(S ! NULL) return S-data;
}int main()
{LinkStack S;InitStack(S);int i, e;for(i 1; i 10; i ){Push(S, i);}Pop(S, e);printf(%d\n, e);
} 2.1.4栈与递归的实现
对于链表,其结点LNode的定义由数据域data和指针域next组成,而指针域next是一种指向LNode类型的指针,即LNode的定义中又用到了其自身所以链表是一种递归的数据结构。
遍历输出链表中各个结点的递归算法
算法从前向后遍历输出链表结点的递归算法直到p为NULL时递归结束在递归过程中p不断指向后续节点。
#includestdio.h
#includestdlib.h#define List_Init_Size 100 //线性表存储空间的初始分配量
#define ListIncreMent 10 //线性表存储空间的分配增量
#define ElemType int
#define Status inttypedef struct LNode{ElemType data;struct LNode *next;
}LNode, *LinkList;void CreateList_L(LinkList L, int n)
{// 尾插法L (LinkList) malloc(sizeof (LNode));L-next NULL; LinkList tail L; // tail指向链表的尾部printf(请输入\n); //先建立一个带头结点的单链表for (int i n; i 0; --i){LinkList p (LinkList) malloc(sizeof (LNode)); //生成新结点scanf(%d, p-data);p-next NULL;tail-next p;tail p;}
}
void TraverseList(LinkList p){if(p NULL) return;else{printf(%d\n, p-data);TraverseList(p-next);}
}
int main()
{LinkList L;int i, e;CreateList_L(L, 10);TraverseList(L-next);return 0;
} *Hanoi塔问题的递归算法
#includestdio.h
#includestdlib.hint m 0;void move(char A, int n, char C){ //将编号为n的圆盘从A移到C printf(%d, %d, %c, %c\n, m, n, A, C);
}void Hanoi(int n, char A, char B, char C){if(n 1) move(A, 1, C); //将编号为1的圆盘从A移到Celse{Hanoi(n-1, A, C, B); //将A上编号1~n-1的圆盘移到B, C做辅助塔move(A, n, C); //将编号为n的圆盘从A到CHanoi(n-1, B, A, C); //将B上编号为1~n-1的圆盘移到C, A做辅助塔 }
}int main()
{int n 3;Hanoi(n, A, B, C);return 0;
} 递归算法的时间复杂度为 O ( 2 n ) O(2^n) O(2n)空间复杂度则为 O ( n ) O(n) O(n)
2.2队列
队列的操作与栈的操作类似不同的是删除实在表的头部即队头进行。 队列Queue是一种 先进先出FIFOFirst-In-First-Out的线性数据结构它的基本特点是元素的插入发生在队尾而元素的删除发生在队头。队列通常用来处理需要按照顺序处理的数据类似于排队的过程。 2.2.1循环队列——队列的顺序表示和实现
队列也有两种表示顺序表示和链式表示。
在队列的顺序存储结构中除了用一组连续的存储单元依次存放从队列头到队列尾的元素外尚需要附设两个整型变量front和rear分别指示队列头元素和队列尾元素的位置。在初始化创建空队列时令front rear 0每当插入新的队列尾元素尾指针1每当删除队列头元素 时头指针front1。在非空队列中头指针始终指向队列头元素而尾指针始终指向队列尾元素的下一个位置。
为了避免队列实际空间并未占满而出现“假溢出现象”我们将顺序队列变为一个环状的空间称为循环队列。头尾指针以及队列元素之间关系不变只是在循环队列中头尾指针“依环状态增1”的操作可用“模”运算来实现。通过取模头指针和尾指针就可以在顺序表空间内以头尾衔接的方式“循环移到”。 假溢出现象解释就是因为删除操作会让头指针1导致头指针之前的空间就不会被利用起来而当尾指针的值到达队列的空间最大值时就会产生假溢出了。 如何判断队列是否为空或者队列是否已满 少用一个元素空间即队列空间大小为m时有m-1个元素就认为是队满。即当头尾指针的值相同时则认为队空而当尾指针在循环意义上1后是等于头指针则认为队满。 队空的条件 Q . f r o n t Q . r e a r Q.front Q.rear Q.frontQ.rear 队满的条件$ Q.front (Q.rear1)%MAXQSIZE $
#includeiostream#define MAXQSIZE 100
#define QElemType int
#define Status intusing namespace std;typedef struct{QElemType *base; // 存储空间的基地址int front; // 队头指针int rear; // 队尾指针
} SqQueue;Status InitQueue(SqQueue Q) {// 构造一个空队列QQ.base new QElemType[MAXQSIZE];if(!Q.base) exit(0);Q.front Q.rear 0;return 1; // 返回成功
}int QueueLength(SqQueue Q){//返回Q的元素个数return (Q.rear - Q.front MAXQSIZE) % MAXQSIZE;
}Status EnQueue(SqQueue Q, QElemType e){//插入元素e为Q的新的队尾元素if((Q.rear 1) % MAXQSIZE Q.front){ //队满return 0;}Q.base[Q.rear] e;Q.rear (Q.rear 1) % MAXQSIZE;return 1;
}Status DeQueue(SqQueue Q, QElemType e){//删除Q的队头元素用e返回其值if(Q.front Q.rear) return 0; //队空e Q.base[Q.front];Q.front (Q.front 1) %MAXQSIZE;return 1;
}QElemType GetHead(SqQueue Q){//返回Q的队头元素不修改队头指针if(Q.front ! Q.rear) return Q.base[Q.front];
}int main()
{SqQueue Q;InitQueue(Q);for(int i 1; i 10; i ){EnQueue(Q, i);}int e GetHead(Q);cout e endl;return 0;} 2.2.2链队——队列的链式表示和实现 一个链队需要两个分别指示队头和队尾的指针才能唯一确定给链队添加一个头结点并令指针始终指向头结点。 链队的操作即为单链表插入和删除操作的特殊情况只是需进一步修改尾指针或头指针。 这个图对于理解链队很重要
#includeiostream#define MAXQSIZE 100
#define QElemType int
#define Status intusing namespace std;typedef struct QNode{QElemType data;struct QNode *next;
} QNode, *QueuePtr; //链队的每个结点typedef struct{QueuePtr front;QueuePtr rear;
}LinkQueue; //这就是链队的头指针Status InitQueue(LinkQueue Q){//构造一个空队列QQ.front Q.rear new QNode;Q.front-next NULL;return 1;
}Status EnQueue(LinkQueue Q, QElemType e){//插入元素e为Q的队尾元素QueuePtr p new QNode; //新节点分配内存 **p-data e;p-next NULL;Q.rear-next p;Q.rear p; //类似尾插法return 1;
}Status DeQUeue(LinkQueue Q, QElemType e){//删除Q的队头元素if(Q.front Q.rear) return 0; //空队QueuePtr p Q.front;e p-data;Q.front-next p-next; //修改头指针if(Q.rear p) Q.rear Q.front; //删除的最后一个元素delete p;return 1;
}QElemType GetHead(LinkQueue Q){//返回Q的队头元素不修改队头指针if(Q.front ! Q.rear)return Q.front-next-data;
}int main()
{LinkQueue Q;InitQueue(Q);for(int i 1; i 10; i ){EnQueue(Q, i);}cout GetHead(Q) endl;return 0;}
