哪里有网站推广公司,免费做国际网站,精品建设课程网站,美食网站的设计与制作代码1.栈 栈和队列是两种操作受限的线性表。如上图所示显示栈的结构
栈#xff1a;先进后出#xff0c;入栈#xff08;数据进入#xff09; 和出栈#xff08;数据出去#xff09;均在栈顶操作。
常见栈的应用场景包括括号问题的求解#xff0c;表达式的转换和求值#…
1.栈 栈和队列是两种操作受限的线性表。如上图所示显示栈的结构
栈先进后出入栈数据进入 和出栈数据出去均在栈顶操作。
常见栈的应用场景包括括号问题的求解表达式的转换和求值函数调用和递归实现
1.1 栈的代码实现
#includeiostream
#includestdio.h
#includemalloc.h
#includeassert.htypedef int STDataType;
typedef struct node
{STDataType x;struct node* next;
}node;
typedef struct Stack
{node* head;int nums; // 长度
}Stack;// 初始化栈
void StackInit(Stack* ps)
{assert(ps);ps-head NULL;ps-nums 0;
}// 入栈
void StackPush(Stack* ps, STDataType data)
{assert(ps);node* new_node (node*)malloc(sizeof(node));new_node-x data;new_node-next ps-head;ps-head new_node;ps-nums;
}// 检测栈是否为空如果为空返回非零结果如果不为空返回0
int StackEmpty(Stack* ps)
{assert(ps);return ps-nums 0;
}// 出栈
STDataType StackPop(Stack* ps)
{assert(ps);assert(!StackEmpty(ps));STDataType ret ps-head-x;node* del ps-head;ps-head ps-head-next;free(del);ps-nums--;return ret;
}// 获取栈中有效元素个数
int StackSize(Stack* ps)
{assert(ps);return ps-nums;
}// 销毁栈
void StackDestroy(Stack* ps)
{assert(ps);node* tmp ps-head;while (tmp){ps-head ps-head-next;free(tmp);tmp ps-head;}ps-head NULL;ps-nums 0;
}int main()
{Stack sta;StackInit(sta);StackPush(sta, 1);StackPush(sta, 2);StackPush(sta, 3);StackPush(sta, 4);StackPush(sta, 5);std::cout StackSize(sta) std::endl;while (!StackEmpty(sta)){printf(%d\n, StackPop(sta));}
}1.2 进制转化
#include iostream
#include malloc.husing namespace std;/**** 结 构 体 声 明 ****/
typedef struct scStack{struct scStack *next;int elem;
}scStack;/*余数入栈
*/
scStack *push(scStack *stack,int elem){scStack *newStack (scStack *)malloc(sizeof(scStack));newStack-elem elem;newStack-next stack;stack newStack;return stack;
}/*进制转换
*/
scStack *sysConvert(int num,int system,scStack *sys){while(num 0){sys push(sys,num % system);num / system;}return sys; //返回栈顶
}/*余数出栈
*/
void pop(scStack *stack){while(stack){scStack *top stack;top-elem 10 ? printf(%c,top-elem a - 10) : printf(%d,top-elem);stack stack-next;free(top);}coutendl转换完毕endl;
}/*主函数
*/
int main(){scStack *stack NULL; //初始化栈int num,system;cout请输入一个10进制数;cinnum;cout请输入想要转换为多少进制;cinsystem;stack sysConvert(num,system,stack);pop(stack);return 0;
}1.3 括号匹配
#includestdio.h#define MaxSize 10typedef struct { // 定义顺序栈int data[MaxSize]; // 静态数组存放栈中元素int top; // 栈顶指针指向目前栈顶元素的位置
} SeqStack;void InitStack(SeqStack S) {S.top -1;
}bool StackEmpty(SeqStack S) {if(S.top -1) {return true;} else {return false;}
}bool Push(SeqStack S, char x) {if(S.top MaxSize - 1) {return false;}S.top S.top 1;S.data[S.top] x;return true;
}bool Pop(SeqStack S, char x) {if(S.top -1) {return false;}x S.data[S.top];S.top S.top - 1;return true;
}bool bracketCheck(char str[], int length) {SeqStack S;InitStack(S);for(int i 0;i length;i) {if(str[i] ( || str[i] [ || str[i] {) {Push(S, str[i]);} else {if(StackEmpty(S)) {return false;}char topElem;Pop(S, topElem);if(str[i] ) topElem ! () {return false;}if(str[i] ] topElem ! [) {return false;}if(str[i] } topElem ! {) {return false;}}}return StackEmpty(S);
}int main() {char A[] [([][])];if(bracketCheck(A, 8)) {printf(A The match is successful\n);}else{printf(A The match is faild\n);}char B[] [([][]];if(bracketCheck(B, 8)) {printf(B The match is successful\n);}else{printf(B The match is faild\n);}
}1.4 递归
//X有n个盘子从上到下有从小到大的顺序有三个柱子XY, Z,把n个盘子从X移到Z
//Y为辅助并在移动过程中有一个约束条件就是大盘永远不能在小盘上面。
//
#include stdio.h
#include stdlib.h#define MAXSIZE 100typedef int ElemType;//盘子的结构
typedef struct//柱子栈的结构
{char name;ElemType* base;ElemType* top;
}StackType;int initstack(StackType* s,char name)
{s-namename;s-base(ElemType*)malloc(MAXSIZE*sizeof(ElemType));if(s-baseNULL)exit(0);s-tops-base;return 1;}int push(StackType* s,ElemType e)
{if(s-top-s-baseMAXSIZE)exit(0);*(s-top)e;s-top;return 1;
}ElemType pop(StackType* s)
{if(s-tops-base)exit(0);s-top--;return *(s-top);
}int main()
{int all;int i;StackType X;StackType Y;StackType Z;initstack(X,X);initstack(Y,Y);initstack(Z,Z);while(1){printf(请输入X柱子开始有多少个盘子\n);scanf(%d,all);for(iall;i0;i--){push(X,i);}hannota(all,X,Y,Z);}return 1;
}int hannota(int n,StackType* x,StackType* y,StackType* z)
{if(1n){move(x,z);printf(from %c to %c\n,x-name,z-name);return 1;}hannota(n-1,x,z,y);//先解决n-1个盘子移到辅助柱子Y的汉洛塔问题move(x,z);//最后一个从x移到Zprintf(from %c to %c\n,x-name,z-name);hannota(n-1,y,x,z);//解决n-1个盘子移到柱子z的汉洛塔问题return 1;
}int move(StackType* s1,StackType* s2)
{ElemType temp;temppop(s1);push(s2,temp);return 1;
}
2.队列
队列的应用场景包括计算机系统中各种资源的管理消息缓冲器的管理和广度优先搜索遍历等。 队列是先进先出如上图所示队列从队尾入队从队头出队。队列有顺序队列链队列和循环队列
2.1 链队列的代码实现
#include stdio.h
#include malloc.h
typedef char ElemType;
typedef struct DataNode
{ ElemType data;struct DataNode *next;
} DataNode; //链队数据结点类型
typedef struct
{ DataNode *front;DataNode *rear;
} LinkQuNode; //链队类型
void InitQueue(LinkQuNode *q)
{ q(LinkQuNode *)malloc(sizeof(LinkQuNode));q-frontq-rearNULL;
}
void DestroyQueue(LinkQuNode *q)
{DataNode *pq-front,*r;//p指向队头数据结点if (p!NULL) //释放数据结点占用空间{ rp-next;while (r!NULL){ free(p);pr;rp-next;}}free(p);free(q); //释放链队结点占用空间
}
bool QueueEmpty(LinkQuNode *q)
{return(q-rearNULL);
}
void enQueue(LinkQuNode *q,ElemType e)
{ DataNode *p;p(DataNode *)malloc(sizeof(DataNode));p-datae;p-nextNULL;if (q-rearNULL) //若链队为空,则新结点是队首结点又是队尾结点q-frontq-rearp;else{ q-rear-nextp; //将p结点链到队尾,并将rear指向它q-rearp;}
}
bool deQueue(LinkQuNode *q,ElemType e)
{ DataNode *t;if (q-rearNULL) //队列为空return false;tq-front; //t指向第一个数据结点if (q-frontq-rear) //队列中只有一个结点时q-frontq-rearNULL;else //队列中有多个结点时q-frontq-front-next;et-data;free(t);return true;
}
int main()
{LinkQuNode *q; //创建队列q ElemType e;InitQueue(q); //初始化队enQueue(q,a);enQueue(q,b);enQueue(q,c); //依次进队a,b,cdeQueue(q,e);printf(%c\n,e); //出队元素a deQueue(q,e);printf(%c\n,e); //出队元素b deQueue(q,e);printf(%c\n,e); //出队元素cDestroyQueue(q); //销毁队 return 0;
}
