南通网站建设企业,php sqlite 做网站,网站后台 黑链接,黄江网站仿做文章目录 一、栈1.栈的概念及结构1.栈的概念及结构2.栈的实现 2.栈的顺序表实现1.栈的结构体和实现的功能函数2.栈的初始化#xff0c;入栈和出栈操作3.栈的其他操作 3.栈的链表实现1.栈的结构体和实现的功能函数2.栈功能函数的实现 二、队列1.队列的概念及结构1.队列的概念及… 文章目录 一、栈1.栈的概念及结构1.栈的概念及结构2.栈的实现 2.栈的顺序表实现1.栈的结构体和实现的功能函数2.栈的初始化入栈和出栈操作3.栈的其他操作 3.栈的链表实现1.栈的结构体和实现的功能函数2.栈功能函数的实现 二、队列1.队列的概念及结构1.队列的概念及结构2.队列的实现 2.队列的顺序表实现循环队列1.循环队列分析2.循环队列的结构体和实现的功能函数2.循环队列初始化和插入2.循环队列的其他操作 3.队列的链表实现1.队列的结构体和实现的功能函数2.队列功能函数的实现 二、栈和队列应用实列实现简单计算器1.问题分析1.代码实现 总结 一、栈
1.栈的概念及结构
1.栈的概念及结构
栈是一种特殊的线性表只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端其称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出的原则。
2.栈的实现
栈的实现一般可以使用数组或者链表实现 栈的数组实现 栈的链表实现 对比两种方式的插入和删除数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
2.栈的顺序表实现
1.栈的结构体和实现的功能函数
typedef int STDataType;
typedef struct Stack
{STDataType* data;int top; // 栈顶int capacity; // 容量
}Stack;
void StackInit(Stack* ps);// 初始化栈
void StackPush(Stack* ps, STDataType data);// 入栈
void StackPop(Stack* ps);// 出栈
STDataType StackTop(Stack* ps);// 获取栈顶元素
int StackSize(Stack* ps);// 获取栈中有效元素个数
bool StackEmpty(Stack* ps);// 检测栈是否为空如果为空返回非零结果如果不为空返回0
void StackDestroy(Stack* ps);// 销毁栈 这里我们使用动态开辟的结构保证栈的空间足够。数组实现我们需要一个变量来保存栈顶元素。栈顶元素也是我们栈中有效元素的个数。
2.栈的初始化入栈和出栈操作
// 初始化
void StackInit(Stack* ps)
{ps-top 0;//指向栈顶的位置置为数组的起始位置ps-capacity 0;//把容量进行初始化ps-data NULL;//把数据区进行初始化
}
// 入栈
void StackPush(Stack* ps, STDataType data)
{assert(ps);if (ps-top ps-capacity)//判断空间是否已满已满就进行扩容{int newcapacity ps-capacity 0 ? 4 : ps-capacity * 2;//产生新的容量Stack* p (Stack*)realloc(ps-data, sizeof(Stack)* newcapacity);//进行扩容if (p NULL)//判断是否扩容成功{perror(realloc);exit(-1);}ps-data p;//指向扩容后的地址ps-capacity newcapacity;//更新容量为新的容量}ps-data[(ps-top)] data;//把数据弹入栈顶
}
// 出栈
void StackPop(Stack* ps)
{assert(ps);if (ps-top 0)//判断是否还有元素{return;}ps-top--;//弹出栈顶元素
}这里初始化入栈和出栈操作和顺序表的操作没什么区别。
3.栈的其他操作
// 获取栈顶元素
STDataType StackTop(Stack* ps)
{assert(ps);return ps-data[(ps-top) - 1];//栈顶的前一个位置为我们的栈顶元素因为我们设置的起始位置从0开始
}
// 获取栈中有效元素个数
int StackSize(Stack* ps)
{assert(ps);return ps-top;//栈顶元素就是栈中有效元素个数
}
// 检测栈是否为空如果为空返回非零结果如果不为空返回0
bool StackEmpty(Stack* ps)
{assert(ps);return ps-top 0;//返回判断结果等于0则代表没有元素则返回真。反之则为假。
}
// 销毁栈
void StackDestroy(Stack* ps)
{assert(ps);free(ps-data);//释放掉我们开辟的数据空间ps-data NULL;//把指向我们开辟数据的空间指向空ps-top 0;ps-capacity 0;
}这里销毁注意我们的数据区的也要进行空间释放防止造成空间泄露。 测试代码
void test1()
{Stack ps;StackInit(ps);StackPush(ps, 1);StackPush(ps, 2);StackPush(ps, 3);StackPush(ps, 4);StackPush(ps, 5);printf(栈顶%d\n, StackTop(ps));// 获取栈顶元素 printf(个数%d\n, StackSize(ps));// 获取栈中有效元素个数if (!StackEmpty(ps)){printf(Stack is not NULL\n);}StackPop(ps);printf(栈顶%d\n, StackTop(ps));// 获取栈顶元素 if (!StackEmpty(ps)){printf(Is not Empty\n);}StackDestroy(ps);
}
int main()
{test1();//test2();//test3();//test4();//test5();return 0;
}3.栈的链表实现
1.栈的结构体和实现的功能函数
typedef int STDataType;
typedef struct StackNode
{STDataType data;struct StackNode* next; //记录下一个区域的指针
}StackNode;
typedef struct Stack//头节点
{int size;//记录元素的个数StackNode head;
}Stack;
void StackInit(Stack* ps);// 初始化栈
void StackPush(Stack* ps, STDataType data);// 入栈
void StackPop(Stack* ps);// 出栈
STDataType StackTop(Stack* ps);// 获取栈顶元素
int StackSize(Stack* ps);// 获取栈中有效元素个数
bool StackEmpty(Stack* ps);// 检测栈是否为空如果为空返回非零结果如果不为空返回0
void StackDestroy(Stack* ps);// 销毁栈 我们这里和实现双链表一样设置了一个特殊的头节点。头节点比正常节点多了一个变量用来记录栈中的元素个数可以避免返回栈的元素个数时对栈进行遍历。
2.栈功能函数的实现
// 初始化栈
void StackInit(Stack* ps)
{ps-size 0;//初始元素为0ps-head.next NULL;//无元素时头节点的下一个指向空ps-head.data 0;
}
// 入栈
void StackPush(Stack* ps, STDataType data)
{assert(ps);StackNode* add (StackNode*)malloc(sizeof(StackNode));//创建节点if (add NULL)//判断节点是否创建成功{perror(malloc);exit(-1);}add-data data;//给节点赋上数据StackNode* pos (ps-head);//要取地址add-next pos-next;//进行头插pos-next add;ps-size;
}
// 出栈
void StackPop(Stack* ps)
{assert(ps);StackNode* pos (ps-head);if (pos-next NULL){return;}StackNode* del pos-next;//进行头删pos-next del-next;free(del);ps-size--;
}
// 获取栈顶元素
STDataType StackTop(Stack* ps)
{assert(ps);StackNode* pos ((ps-head))-next;if (pos NULL)//判断头指针的下一个是否为空{return;}return pos-data;
}
// 获取栈中有效元素个数
int StackSize(Stack* ps)
{assert(ps);return ps-size;
}
// 检测栈是否为空如果为空返回非零结果如果不为空返回0
bool StackEmpty(Stack* ps)
{assert(ps);return ps-size 0;
}
// 销毁栈
void StackDestroy(Stack* ps)
{assert(ps);StackNode* pos (ps-head);if (pos-next NULL)//判断头指针的下一个是否为空{return;}StackNode* del pos-next;while (del ! NULL){pos-next del-next;free(del);del pos-next;}
}这里就是沿用链表的操作注意释放节点时避免节点丢失。 测试函数
void test2()
{Stack ps;StackInit(ps);StackPush(ps, 1);StackPush(ps, 2);StackPush(ps, 3);StackPush(ps, 4);StackPush(ps, 5);printf(栈顶%d\n, StackTop(ps));// 获取栈顶元素 printf(个数%d\n, StackSize(ps));// 获取栈中有效元素个数if (!StackEmpty(ps)){printf(Stack is not NULL\n);}StackPop(ps);printf(栈顶%d\n, StackTop(ps));// 获取栈顶元素 StackDestroy(ps);
}
int main()
{//test1();test2();//test3();//test4();//test5();return 0;
}二、队列
1.队列的概念及结构
1.队列的概念及结构
队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出的特点。进行插入操作的一端称为队尾 进行删除操作的一端称为队头。
2.队列的实现
队列的实现一般可以使用数组或者链表实现 队列的链表实现 对比两种方式的插入和删除使用链表的结构实现更优一些因为如果使用数组的结构出队列在数组头上出数据需要频繁移动数据效率会比较低。
2.队列的顺序表实现循环队列
由于队列使用数组需要扩容和频繁移动数据这样的结构并不常用所以我们用顺序表实现循环的队列。
1.循环队列分析
我们假设数组的大小有五个元素 我们如何判断队列中的元素是否已经满了呢 用头位置等于尾位置吗 上述一个元素也没有会不会直接判断为数组已满呢 我们的解决办法是保证一个位置为空当尾位置等于头位置时即为队列满即队尾不存储数据。
2.循环队列的结构体和实现的功能函数
#define MAXNUM 5
typedef int QDataType;
typedef struct QListNode
{QDataType data[5];int head;//对头元素int end;//队尾元素
}QNode;
void QueueInit(QNode* q);// 初始化队列
void QueuePush(QNode* q, QDataType data);// 队尾入队列
void QueuePop(QNode* q);// 队头出队列
QDataType QueueFront(QNode* q);// 获取队列头部元素
QDataType QueueBack(QNode* q);// 获取队列队尾元素
int QueueSize(QNode* q);// 获取队列中有效元素个数
int QueueEmpty(QNode* q);// 检测队列是否为空如果为空返回非零结果如果非空返回0
void QueueDestroy(QNode* q);// 销毁队列 2.循环队列初始化和插入
// 初始化队列
void QueueInit(QNode* q)
{q-head 0;q-end 0;
}
// 队尾入队列
void QueuePush(QNode* q, QDataType data)
{assert(q);if ((q-end - q-head) (MAXNUM-1))//尾元素和首元素相差最大数量减一个元素代表队列已满{printf(队列已满无法插入\n);return;}q-data[(q-end) % MAXNUM] data;q-end;
}我们对队列进行插入时要对队尾元素进行取模运算。防止插入时造成越界。
2.循环队列的其他操作
// 队头出队列
void QueuePop(QNode* q)
{assert(q);if (q-head q-end)//尾元素和首元素相同证明队列中没有元素{printf(没有元素可以出队\n);return;}q-head;
}
// 获取队列头部元素
QDataType QueueFront(QNode* q)
{assert(q);if (q-head q-end q-end ! 0)//尾元素和首元素相同证明队列中没有元素{printf(没有元素可以查看\n);return -1;}return q-data[(q-head) % MAXNUM];
}
// 获取队列队尾元素
QDataType QueueBack(QNode* q)
{assert(q);if (q-head q-end q-end ! 0)//尾元素和首元素相同证明队列中没有元素{printf(没有元素可以查看\n);return -1;}return q-data[(q-end - 1) % MAXNUM];
}
// 获取队列中有效元素个数
int QueueSize(QNode* q)
{assert(q);return q-end - q-head;
}
// 检测队列是否为空如果为空返回非零结果如果非空返回0
int QueueEmpty(QNode* q)
{assert(q);return q-head q-end;
}
// 销毁队列
void QueueDestroy(QNode* q)
{assert(q);q-head 0;q-end 0;
}我们返回队头队尾数据要看尾是否在0位置为0代表一个元素还没插入。我们进行插入返回元素的操作都需要进行取模操作 测试函数
void test3()
{QNode qu;QueueInit(qu);int i 0;for(i 0; i 5; i){QueuePush(qu, i);}printf(队头%d\n, QueueFront(qu));printf(队尾%d\n, QueueBack(qu));QueuePop(qu);printf(队头%d\n, QueueFront(qu));printf(个数%d\n, QueueSize(qu));printf(为空%d\n, QueueEmpty(qu));QueuePop(qu);QueuePop(qu);QueuePop(qu);QueuePop(qu);QueueDestroy(qu);
}
int main()
{//test1();//test2();test3();//test4();//test5();return 0;
}3.队列的链表实现
1.队列的结构体和实现的功能函数
typedef int QDataType;
typedef struct QListNode
{QDataType data;struct QListNode* next;
}QNode;
// 队列的结构
typedef struct Queue
{QNode* head;QNode* end;
}Queue;
void QueueInit(Queue* q);// 初始化队列
void QueuePush(Queue* q, QDataType data);// 队尾入队列
void QueuePop(Queue* q);// 队头出队列
QDataType QueueFront(Queue* q);// 获取队列头部元素
QDataType QueueBack(Queue* q);// 获取队列队尾元素
int QueueSize(Queue* q);// 获取队列中有效元素个数
int QueueEmpty(Queue* q);// 检测队列是否为空如果为空返回非零结果如果非空返回0
void QueueDestroy(Queue* q);// 销毁队列 我们设置了一个结构体用来存储头节点和尾节点目的是为了减少遍历。
2.队列功能函数的实现 //初始化队列
void QueueInit(Queue* q)
{assert(q);q-head NULL;q-end NULL;
}
// 队尾入队列
void QueuePush(Queue* q, QDataType data)
{assert(q);QNode* pos (QNode*)malloc(sizeof(QNode));if (pos NULL){perror(malloc);exit(-1);}pos-data data;pos-next NULL;if (q-end NULL){q-head pos;q-end pos;}else{q-end-next pos;q-end q-end-next;}
}
// 队头出队列
void QueuePop(Queue* q)
{assert(q);QNode* del q-head;if (q-head q-end q-end ! NULL)//当头指针等于尾指针时证明队列中没有元素{printf(没有元素可以出队\n);return;}q-head q-head-next;free(del);
}
// 获取队列头部元素
QDataType QueueFront(Queue* q)
{assert(q);if (q-head q-end q-end ! NULL)//当头指针等于尾指针时证明队列中没有元素{printf(没有元素可以查看\n);return -1;}return q-head-data;
}
// 获取队列队尾元素
QDataType QueueBack(Queue* q)
{assert(q);if (q-head q-end q-end ! NULL)//当头指针等于尾指针时证明队列中没有元素{printf(没有元素可以查看\n);return -1;}return q-end-data;
}
// 获取队列中有效元素个数
int QueueSize(Queue* q)
{assert(q);int size 0;QNode* pos q-head;while (pos ! q-end){size;pos pos-next;}return size;
}
// 检测队列是否为空如果为空返回非零结果如果非空返回0
int QueueEmpty(Queue* q)
{assert(q);return q-head q-end;
}
// 销毁队列
void QueueDestroy(Queue* q)
{assert(q);QNode* del q-head;while (del ! q-end){q-head del-next;free(del);del q-head;}free(q-head);q-head NULL;q-end NULL;
}测试函数
void test4()
{Queue qu;QueueInit(qu);int i 0;for(i 0; i 5; i){QueuePush(qu, i);}printf(队头%d\n, QueueFront(qu));printf(队尾%d\n, QueueBack(qu));QueuePop(qu);printf(队头%d\n, QueueFront(qu));printf(个数%d\n, QueueSize(qu));printf(为空%d\n, QueueEmpty(qu));QueuePop(qu);QueuePop(qu);QueuePop(qu);QueuePop(qu);QueueDestroy(qu);
}
int main()
{//test1();//test2();//test3();test4();//test5();return 0;
}二、栈和队列应用实列实现简单计算器
计算10(1020*30)*4-50
1.问题分析
我们计算需要进行优先级比较是否含有括号数据的存储等我们需要两个栈来进行存储一个符号栈一个数字栈。 思路分析
1.代码实现
void Count(Stack* num, int headsign)
{int n1 0;//用于计算的变量1int n2 0;//用于计算的变量2//已经是指针了不可以在取地址了n2 StackTop(num);//n2先进性出栈StackPop(num);//数字出栈n1 StackTop(num);//n2出栈是为了防止除法是顺序错乱StackPop(num);//数字出栈int sum 0;//用来存储两个值的结果switch (headsign)//判断符号{case :sum n1 n2;break;case -:sum n1 - n2;break;case *:sum n1 * n2;break;case /:sum n1 / n2;break;default:exit(-1);//未知符号程序退出}//入数字栈StackPush(num, sum);
}
void Match_Brace(Stack* sign, Stack* num)//开始匹配左括号
{int headsign 0;//存储栈顶的元素符号headsign StackTop(sign);//获取栈顶元素符号while(!StackEmpty(sign))//符号栈不为空则一直进行循环 直到在左括号处结束{if (headsign ()//如果为左括号则直接出栈结束{StackPop(sign);//符号出栈break;}else{//计算Count(num, headsign);//计算函数StackPop(sign);//符号出栈}headsign StackTop(sign);//获取栈顶元素符号}
}
int Priority(int symbol)
{switch (symbol)//判断符号{case (:return 0;case :case -:return 1;case *:case /:return 2;default:exit(-1);//未知符号程序退出}
}
void Match_Symbols(Stack* sign, Stack* num, int symbol)
{if (StackEmpty(sign) || symbol ()//如果栈为空或者为左括号则直接入栈{StackPush(sign, symbol);//入栈return;}int headsign 0;//存储栈顶的元素符号headsign StackTop(sign);//获取栈顶元素符号if (Priority(symbol) Priority(headsign))//优先级比较,该符号优先级高则直接入栈{StackPush(sign, symbol);//入栈return;}while(Priority(symbol) Priority(headsign))//直到优先级高于栈顶元素停止循环{//计算Count(num, headsign);//计算函数StackPop(sign);//栈顶符号出栈if (StackEmpty(sign))//栈为空则退出循环{break;}headsign StackTop(sign);//获取栈顶元素符号}StackPush(sign, symbol);//入栈
}
void test5()
{Stack num;//存储数字所使用的栈Stack sign;//存储算数符号所用的栈StackInit(num);//对数字栈进行初始化StackInit(sign);//对符号栈进行初始化char* s 10(1020*30)*4-50;//要计算的表达式int i 0;//用来判断表达式是否已到结尾int sum 0;//用来存储一个整形数据int flag 0;//用来判断是否取完一个整形元素while (s[i] ! \0){if (isdigit(s[i]))//判断是否为数字{sum sum * 10 (s[i] - 0);//更新sum的值flag 1;//把标志位置为1为后面判断是否入栈准备}else{if (flag 1)//判断该数字是否以入栈{//入数字栈StackPush(num, sum);flag 0;//更新标志位sum 0;//更新sum值防止下次计算时出错}if (s[i] ))//开始匹配左括号{//进行出栈匹配左括号Match_Brace(sign, num);}else//字符为 - * /{//进行优先级比较Match_Symbols(sign, num,s[i]);}}i;}if (flag 1)//判断该数字是否以入栈{//入数字栈StackPush(num, sum);flag 0;//更新标志位sum 0;//更新sum值防止下次计算时出错}int headsign 0;//存储栈顶的元素符号while (!StackEmpty(sign))//符号栈不为空则一直进行计算{headsign StackTop(sign);//获取栈顶元素符号//计算Count(num, headsign);StackPop(sign);//符号出栈}printf(%d\n, StackTop(num));StackDestroy(num);//销毁数字栈StackDestroy(sign);//销毁字符栈
}
int main()
{//test1();//test2();//test3();//test4();test5();return 0;
}注意函数对指针的二次传参不需要在进行取地址在计算机中计算机识别的是字符所以我们需要一个字符一个字符的进行这时间需要我们判断这个数字到底几位数需要我们一个临时量也可以用库函数atoi实现。其他按照思路可以轻而易举的实现。
总结
栈和队列都是含有限制的线性表。前面的知识扎实的话实现栈和队列没有一点问题。都是顺序表和链表的其中一部分。
