基于AI的C语言程序设计（微课版）课件 第13章 数据结构和算法应用

第13章

数据结构和算法应用数据结构×算法：程序效率的双引擎主

讲

:蒋亚平目录CONTENTS01程序=数据结构+算法02数据结构03算法应用04本章小结问题导入时间复杂度为何不同算法（或数据结构）处理同类问题，时间复杂度会有显著区别？BF算法和KMP算法在字符串匹配中的“时间复杂度”有什么差异？校园快递站校园快递站要给5栋宿舍楼送快递，如何规划路线才能让快递员“走的总路程最短”？这个问题需要用到哪些数据结构和算法思想？01程序=数据结构+算法数据结构决定存取效率数据结构：存储和组织信息的方式数组：适合处理需要快速访问的固定大小的元素集合。栈：适合处理后进先出（LIFO）的问题，如浏览器的历史记录。队列：适用处理先进先出（FIFO）的问题，如任务调度。算法：操作和处理数据的步骤算法是程序中的“灵魂”，它定义了如何对数据进行处理、计算和转化。数据结构与算法的紧密联系没有合适的数据结构，算法的实现将变得低效；而没有合适的算法，数据结构的存在也无法发挥应有的价值。示例排序算法：优化数据的查找效率。搜索算法：用来查找特定的数据或路径。程序设计中的实践在实际开发中，程序员不仅需要选择合适的数据结构，还要根据需求选择高效的算法。两者的结合往往是程序设计的关键。02数据结构线性表

线性表线性表线性表是由n个数据元素（n≥0）构成的有限序列，记为（a1,a2,a3,...,an)，其中所有元素的数据类型相同。当n=0时，称为空表；当n>0时，线性表包含n个数据元素。线性表的概念存在唯一的首个数据元素a1。存在唯一的末尾数据元素an。除首个数据元素外，结构中的每个数据元素均有一个前驱元素。除末尾数据元素外，结构中的每个数据元素均有一个后继元素。线性表的特点

线性表示例：使用C语言的结构体数组存储学生信息。struct{ intno; //存储学号charname[50];//存储姓名intage; //存储年龄floatscore;//存储成绩}Student[6]{{1,"王毅一",20,99},...,{6,"蒋赟",19,100}};学生信息的顺序存储结构

线性表示例：使用C语言中的链表存储学生信息。typedefstructStudnode{ intno; //存储学号charname[50];//存储姓名intage; //存储年龄floatscore;//存储成绩structStudnode*next;//存储指向下一个学生结点的指针}StudType;学生信息的顺序存储结构

顺序表的顺序存储示例：通过结构体定义顺序表的长度、存储数据的数组。#include<stdio.h>#include<stdlib.h>#defineMAX_SIZE100//定义最大容量typedefintElemType;//定义元素类型//定义顺序表结构typedefstruct{ElemTypedata[MAX_SIZE];//存储数据的数组intlength;//当前顺序表的长度}SeqList;顺序表的定义一维数组，用于表示顺序表顺序表的当前长度1顺序表的定义顺序表是线性表的顺序存储实现。在C语言中，通常使用一维数组和结构体来实现顺序表。

顺序表的顺序存储示例：初始化顺序表的示例。voidinitList(SeqList*L){ L->length=0;}顺序表的定义示例：实现顺序表尾部添加元素。intappendElem(SeqList*list,ElemTypeelem){if(list->length>=MAX_SIZE){//如果顺序表已满printf("顺序表已满\n");return0;//添加失败}list->data[list->length]=elem;//在末尾添加元素list->length++;//长度增加return1;//添加成功}2顺序表的初始化通过将顺序表的长度设置为0，可以完成顺序表的初始化。3尾部添加元素如果检查顺序表已满，则添加操作失败；否则，将新元素添加到顺序表的末尾，并更新顺序表的长度。

顺序表的顺序存储示例：遍历顺序表并打印所有元素。voidlistElem(constSeqList*list){for(inti=0;i<list->length;i++){printf("%d",list->data[i]);//打印元素}printf("\n");}4遍历顺序表通过遍历顺序表中的所有元素，可以依次打印出每个元素的值。

顺序表的顺序存储指定位置插入数据结点示例：实现插入操作。intinsertElem(SeqList*list,intpos,ElemTypeelem){if(list->length>=MAX_SIZE){//顺序表已满printf("表已经满了\n");return0;//插入失败}if(pos<1||pos>list->length+1){//插入位置不合法printf("插入位置错误\n");return0;//插入失败}//移动元素，为插入腾出位置for(inti=list->length-1;i>=pos-1;i--){list->data[i+1]=list->data[i];}list->data[pos-1]=elem;//插入元素list->length++;//长度增加return1;//插入成功}5指定位置插入结点遍历顺序表找到指定位置，该位置及其之后的元素后移，将新元素插入到指定位置并增加元素长度。

顺序表的顺序存储删除指定位置的数据结点示例：实现删除操作。intdeleteElem(SeqList*list,intpos,ElemType*elem){if(list->length==0){//顺序表为空printf("空表\n");return0;//删除失败}if(pos<1||pos>list->length){//删除位置不合法printf("删除数据位置有误\n");return0;//删除失败}*elem=list->data[pos-1];//保存删除的元素//移动后续元素填补空位for(inti=pos;i<list->length;i++){list->data[i-1]=list->data[i];}list->length--;//长度减少return1;//删除成功}6删除指定位置结点遍历顺序表，将删除位置后面的元素依次向前移动，填补删除位置的空位，并更新顺序表的长度。顺序表的顺序存储查找数据的位置示例：查找数据的位置。intfindElem(constSeqList*list,ElemTypeelem){if(list->length==0){//顺序表为空printf("空列表\n");return0;//查找失败}for(inti=0;i<list->length;i++){if(list->data[i]==elem){//找到元素returni+1;//返回位置（1-based）}}return0;//未找到}7查找数据的位置从顺序表的第一个位置开始，逐个检查元素。找到目标数据后，返回其下标加一的值。顺序表的顺序存储8、初始化顺序表时动态分配内存地址首先创建一个空的顺序表。假设每个元素占用的空间大小为L，而顺序表的最大容量为max，则顺序表的初始空间大小应为max×L，以便存储最多max个元素。然而，由于顺序表的实际元素个数不确定，因此需要提前为顺序表分配max×L个连续的存储单元，以确保可以容纳最大数量的元素。示例：通过动态分配内存进行顺序表初始化。SeqList*initList(){SeqList*list=(SeqList*)malloc(sizeof(SeqList));//动态分配内存list->length=0;//初始化长度为0returnlist;}8动态分配内存地址提前为顺序表分配max×L个连续的存储单元，以确保可以容纳最大数量的元素。顺序表的顺序存储示例：测试顺序表的基本操作示例。intmain(){//声明并初始化一个顺序表SeqList*list=initList();printf("初始化成功，当前长度为：%d\n",list->length);printf("目前占用内存：%zu字节\n",sizeof(list->data));//向顺序表添加元素appendElem(list,79);appendElem(list,87);appendElem(list,30);appendElem(list,18);appendElem(list,9);//打印顺序表元素printf("顺序表元素：");listElem(list);

//在指定位置插入元素printf("在第1个位置插入元素12：");insertElem(list,1,12);listElem(list);//删除指定位置的元素ElemTypedeletedData;deleteElem(list,2,&deletedData);printf("删除数据%d后的数据：",deletedData);listElem(list);//查找元素的位置printf("元素30的位置是：%d\n",findElem(list,30));//释放内存free(list->data);free(list);return0;}运行结果9测试基本操作依次调用初始化函数、添加元素函数、打印元素函数以及插入元素函数等，验证顺序表操作是否正常工作。栈

栈栈栈的概念栈是一种线性表数据结构，其元素间遵循线性关系。栈可以通过不同的物理结构来实现，主要包括顺序存储和链式存储两种方式。顺序栈的实现方式通过数组存储栈元素。入栈操作：将元素添加到栈顶，并更新栈顶指针。

出栈操作：移除栈顶元素，并更新栈顶指针。获取栈顶元素：返回栈顶元素，但不移除它。栈空与栈满的判断：通过栈顶指针判断栈是否为空或已满。1、顺序栈的定义在C语言程序中，栈通过数组实现，并结合数组下标表示的栈顶指针来执行各种栈操作。.LIFO：后进先出栈顶指针toptop+1top-1顺序栈示例：定义顺序栈。#defineMAX_SIZE100//栈的最大容量typedefintElemType;//定义元素类型//顺序栈结构体定义typedefstruct{ElemTypedata[MAX_SIZE];//存储数据的数组inttop;//栈顶指针，指向栈顶元素}SeqStack;顺序栈顺序栈2、顺序栈的创建在对栈中的数据元素进行操作之前，必须首先创建一个空栈。假设每个栈元素的空间大小为L，栈中元素的数量为n，那么栈所占的空间为n*L。示例：实现创建空栈示例。//创建顺序栈SeqStack*createStack(){SeqStack*stack=(SeqStack*)malloc(sizeof(SeqStack));//分配栈的内存if(stack==NULL){printf("内存分配失败\n");returnNULL;//内存分配失败} if(stack->data==NULL){printf("数据区内存分配失败\n");free(stack);returnNULL;//数据区内存分配失败}stack->top=-1;//初始化栈顶指针returnstack;}顺序栈3、入栈在向栈中压入数据元素之前，需要首先判断栈是否已满。如果栈已满，则不允许入栈，以防止发生内存越界。示例：压栈操作必须先进行满栈判断。//判断栈是否已满intisFull(SeqStack*stack){returnstack->top==MAX_SIZE-1;//如果栈顶指针为最大容量-1，栈已满}//入栈操作intpush(SeqStack*stack,intelem){if(isFull(stack)){printf("栈已满，无法入栈\n");return0;//入栈失败}stack->data[++stack->top]=elem;//将元素推入栈中并更新栈顶指针return1;//入栈成功}顺序栈4、出栈在移除栈中的数据元素之前，需要先判断栈是否为空。示例：出栈示例。//判断栈是否为空intisEmpty(SeqStack*stack){returnstack->top==-1;//如果栈顶指针为-1，栈为空}//出栈操作intpop(SeqStack*stack,int*elem){if(isEmpty(stack)){printf("栈为空，无法出栈\n");return0;//出栈失败}*elem=stack->data[stack->top--];//获取栈顶元素并更新栈顶指针return1;//出栈成功}顺序栈5、测试顺序栈的基本操作示例：测试顺序栈的基本操作。//获取栈顶元素inttop(SeqStack*stack,int*elem){if(isEmpty(stack)){printf("栈为空\n");return0;//获取栈顶元素失败}*elem=stack->data[stack->top];//获取栈顶元素return1;//获取栈顶元素成功}//释放栈的内存voidfreeStack(SeqStack*stack){if(stack!=NULL){free(stack->data);//释放栈的数据区内存free(stack);//释放栈的结构体内存}}//测试代码intmain(){SeqStack*stack=createStack();//创建顺序栈if(stack==NULL){return1;}printf("入栈元素(入栈顺序为102030)\n");push(stack,10);push(stack,20);push(stack,30);inttopElem;if(top(stack,&topElem)){printf("栈顶元素是:%d\n",topElem);//打印栈顶元素}printf("出栈元素：\n");intpoppedElem;while(!isEmpty(stack)){pop(stack,&poppedElem);printf("出栈元素:%d\n",poppedElem);}//测试完毕，释放内存freeStack(stack);return0;}运行结果队列

队列队列队列的概念队列（queue）是一种先进先出（FIFO,FirstInFirstOut）的线性数据结构。它只允许在一端插入元素，在另一端删除元素。队列的插入端称为队尾（rear），删除端称为队头（front）。常见的队列操作队空：检查队列是否为空。取头结点：获取队列头部元素的数据。入队：将元素插入到队列的尾部。出队：删除队列头部的元素。1、顺序队列的定义在C语言中，顺序队列通过一维数组实现。队列的操作仅限于在队头和队尾进行，并且在操作过程中不会移动队列中的元素。FIFO：先进先出队列的顺序存储示例：定义顺序队列。#defineMAX_SIZE100//定义队列的最大容量typedefintElemType;//定义队列元素类型//队列结构typedefstruct{ElemTypedata[MAX_SIZE];//存储队列元素的数组intfront;//队头指针，指向队列中的第一个元素intrear;//队尾指针，指向队列中的最后一个元素的下一个位置}Queue;顺序队列队列的顺序存储2、顺序队列的初始化在对队列中的数据结点进行操作之前，首先需要创建一个空队列。假设一个结点所占的内存空间为L，如果队列中有n个结点，那么队列所占的内存空间将为n×L。在初始化队列时，我们需要预先分配足够的内存空间来存储最多max个结点。为此，我们可以一次性分配max×L个连续的内存空间。示例：顺序队列的初始化。Queue*initQueue(){ Queue*q; q=(Queue*)malloc(sizeof(Queue));q->front=0;//队头指针初始化为0q->rear=0;//队尾指针初始化为0returnq;}队列的顺序存储3、入队先判断队列是否已满。如果队列已满，则不能再继续添加元素。如果队列未满，进行入队操作。顺序队列的数据结点处理在初始状态下，队列为空，front和rear都为0。随着入队操作的进行，rear指针会向后移动。当队列已满时，front指针保持不变，而rear指针会指向队列的末尾位置。例如，当顺序队列满时，rear的值可能已经达到了队列的最大容量，此时，如果继续进行入队操作，rear将无法再增加，导致无法使用之前被删除的队列空间。这种情况被称为“溢出”。队列的顺序存储为了避免“溢出“这一问题并保持队列操作的正常进行，可以将顺序队列设计为一个循环队列。循环队列在循环队列中，队列的首尾是连接的，当rear达到最大容量后，可以回绕到队列的起始位置，从而复用之前已删除元素的空间。这种设计使得队列在未满时可以继续添加数据，在未空时也能够删除数据，极大地提高了队列的空间利用效率。

队列的顺序存储示例：判断队列是否为满和入队操作。//判断队列是否为满intisFull(Queue*q){return(q->rear+1)%MAX_SIZE==q->front;}//入队操作intenqueue(Queue*q,ElemTypee){if(isFull(q)){printf("队列已满，无法入队\n");return0;//如果队列满，返回失败}q->data[q->rear]=e;//将元素添加到队尾q->rear=(q->rear+1)%MAX_SIZE;//更新队尾指针，确保循环使用return1;//入队成功}队列的顺序存储4、出队在执行出队之前，需要判断顺序队列是否为空，如果为空，没有数据可以移出。示例：出队示例。//判断队列是否为空intisEmpty(Queue*q){returnq->front==q->rear;//队列为空时，队头和队尾指针相等}//出队操作intdequeue(Queue*q,ElemType*e){if(isEmpty(q)){printf("队列为空，无法出队\n");return0;//如果队列为空，返回失败}*e=q->data[q->front];//获取队头元素q->front=(q->front+1)%MAX_SIZE;//更新队头指针，确保循环使用return1;//出队成功}队列的顺序存储5、获取队头元素在判断队列非空之后，可以通过队头指针获取队头元素。示例：获取队头元素。ElemTypegetFront(Queue*q){if(isEmpty(q)){printf("队列为空\n");return-1;//如果队列为空，返回-1表示错误}returnq->data[q->front];//返回队头元素}队列的顺序存储6、测试示例：测试示例。intmain(){Queue*q;ElemTypee;q=initQueue();//初始化队列//测试入队enqueue(q,10);enqueue(q,20);enqueue(q,30);enqueue(q,40);enqueue(q,50);//尝试在队列满时再入队if(!enqueue(q,60)){printf("无法继续入队，队列已满\n");}//测试出队dequeue(q,&e);printf("出队元素:%d\n",e);//输出出队的元素dequeue(q,&e);printf("出队元素:%d\n",e);//输出出队的元素//获取队头元素printf("队头元素:%d\n",getFront(q));//输出队头元素return0;}运行结果字符串字符串1、串的基本概念串是由n（n≥0）个字符组成的有限序列，记为S="c₁c₂…cₙ"。其中：

当n=0时，称为空串（记为""），空串不包含任何字符；S为串名；

cᵢ（1≤i≤n）是串的元素，取值为ASCII码或Unicode字符（C语言中默认使用ASCII码）；

n为串的长度，表示串中字符的个数；

注意区分“空串”与“空格串”：空格串的长度n≥1，且每个字符均为空格（如""是长度为3的空格串）。串的定义字符串1、串的基本概念

子串：串中任意连续的字符组成的序列。例如串"abcde"中，"bcd"是子串，"ace"（不连续）不是子串。

主串：包含子串的串。若子串T在主串S中出现，则称T是S的子串，S是T的主串。

模式串：在主串中需要查找的子串（也称为“匹配串”），例如在“查找‘ab’在‘aabbcc’中的位置”问题中，"ab"是模式串，"aabbcc"是主串。

串的位置：字符位置：串中字符的序号（C语言中串的字符默认从下标0开始，与数组一致）；子串位置：子串在主串中首次出现时，其第一个字符在主串中的位置。例如"bcd"在"abcde"中的位置为1（下标从0开始）。串的相关术语字符串2、串的模式匹配串的模式匹配是串的核心操作之一，定义为：给定主串S（长度n）和模式串T（长度m，m≤n），在主串S中查找与模式串T完全一致的子串，若找到则返回子串在S中的起始位置，否则返回-1（表示匹配失败）。例如：主串S="abcdeabc"（n=8），模式串T="abc"（m=3），匹配结果为起始位置0和5；主串S="hello"，模式串T="world"，匹配结果为-1。图图图可分为有向图和无向图有向图：有向图中的边具有明确方向，例如从A点到B点的单向通道，在图中可表示为一条从顶点A指向顶点B的有向边。有向图如图13-14所示。无向图：无向图的边则没有方向，意味着A与B之间的路径是双向通行的，边可连接A与B，也可连接B与A。无向图如图13-15所示。校园快递场景示例：校园内分布的5个快递点（A、B、C、D、E）可看作图的顶点，而连接这些快递点的道路就是图的边，边的长度对应道路的实际距离，如此便构建出一个图模型，可用于解决快递配送路径规划等问题。​图由顶点集合（VertexSet）和边集合（EdgeSet）构成，通常记为G=(V,E)。代表顶点的有限集合边的有限集合图的存储方式用二维数组存储顶点间的连接关系，适合顶点数少的图。邻接矩阵用链表存储每个顶点的邻接顶点，适合顶点数多、边少的图。邻接表

图示例：校园快递点图示例，若有5个快递点A、B、C、D、E，分别对应索引0-4，其邻接矩阵用C语言可表示为：#defineINF10000//表示无穷大（无直接连接）intgraph[5][5]={{0,10,20,INF,INF},//A到各点的距离{10,0,5,15,INF},//B到各点的距离{20,5,0,INF,30},//C到各点的距离{INF,15,INF,0,5},//D到各点的距离{INF,INF,30,5,0}//E到各点的距离};校园快递点图使用邻接表存储，可定义如下结构体：#defineMAX_VERTEX5typedefstructEdgeNode{intadjVertex;//邻接顶点的索引intweight;//边的权重structEdgeNode*next;//指向下一个邻接顶点的指针}EdgeNode;typedefstructVertexNode{charvertex;//顶点名称（如'A'、'B'等）EdgeNode*firstEdge;//指向第一条邻接边}VertexNode;typedefstructGraph{VertexNodevertices[MAX_VERTEX];intvertexCount;}Graph;邻接表方式存储图图的遍历图的遍历是指从图中某个指定顶点出发，按照特定搜索策略访问图中所有顶点，且每个顶点仅被访问一次的过程，这一操作在图的诸多应用中至关重要。深度优先：类似于树的先序遍历，从起始顶点出发，优先沿着一条路径尽可能深入访问，直至无法继续，然后回溯到上一个未完全探索的顶点，继续探索其他路径，直至访问完所有与起始顶点相通的顶点。广度优先：类似树的层次遍历，从起始顶点开始，逐层向外扩展访问，先访问距离起始顶点最近的一层顶点，再访问下一层，直至所有顶点都被访问。常见的遍历方式有深度优先搜索（Depth-FirstSearch，DFS）和广度优先搜索（Breadth-FirstSearch，BFS）。03算法应用算法的时间复杂度

算法的时间复杂度程序运行的总时间12执行每条语句的耗时。每条语句的执行频率。时间复杂度‌是衡量算法执行时间随输入规模增长的增长率量度，用大O符号表示。时间复杂度也称渐近时间复杂度，通常表示为T(n)=O(f(n))。随着问题规模n的增大，算法执行时间和f(n)增长率成正比。时间复杂度‌的概念

算法的时间复杂度示例：通过一个嵌套循环来计算频率。intmain(){ intn=10; intarr[n][n]; for(inti=1;i<=n;i++){//频度为n+1 for(intj=1;j<=n;j++){//频度为(n+1)*(n+1) arr[i][j]=0;//频度为n*n for(intk=1;k<=n;k++){//频度为n*n*(n+1) arr[i][j]=1;//频度为n*n*n } } }}嵌套循环可以分析如下的f(n):时间复杂度为：T(n)=O(f(n))=O(n3)时间复杂度通常包括以下三种类型最好时间复杂度：算法在最优输入情况下的时间复杂度。最坏时间复杂度：算法在最差输入情况下的时间复杂度。平均时间复杂度：算法在所有可能的输入实例中，按照等概率分布计算的加权平均时间复杂度。通常关注的是最坏时间复杂度算法的空间复杂度

算法的空间复杂度空间复杂度的表示S(n)=O(f(n))算法的存储量通常包括以下三个部分（1）输入/输出数据所占空间

。（2）程序代码所占空间

。（3）程序运行临时占用空间

。其中f(n)表示随着输入规模n增长，算法所需额外空间的变化规律。空间复杂度用于描述算法执行过程中，除了存储代码和输入数据所需的内存外，还需要的额外内存空间。

算法的空间复杂度示例：算法占用存储空间的示例。intnum,sum=0,i; printf("请输入一个数字："); scanf("%d",&num); for(i=1;i<=num;i++){ sum=sum+i; printf("%d\n",sum); return0; }S(n)=O(1)变量sum和i所占用的空间大小固定，不随num的变化而变化。逆波兰表达式计算器逆波兰表达式计算器三种常见的算术表达式表示方法例如，A+B、(A+B)*C。例如，+AB、*+ABC。例如，AB+、AB+C*。中缀表达式运算符位于两个操作数之间，它是最常见的表达式形式。

在中缀表达式中，括号用于明确运算顺序，而运算符的优先级和括号决定了计算的顺序。前缀表达式（也称为波兰表达式）：将运算符放在操作数之前。在前缀表达式中，运算符位于操作数的前面，计算顺序由运算符的位置决定，而不需要括号来区分运算优先级后缀表达式（也称为逆波兰表达式）：将运算符放在操作数之后。在后缀表达式中，操作符位于操作数的后面，计算顺序同样由运算符的位置决定，避免了括号的使用。逆波兰表达式计算器中缀表达式与后缀表达式的示例中缀表达式后缀表达式（3+4）*2/734+2*7/3+4*5345*+（3+4）*534+5*a*b/cab*c/a*b-1ab*1-x/y-z+i*j-x*yxy/z-ij*+xy*-逆波兰表达式（RPN）求值是一个理想的应用场景，它有助于理解栈的基本操作（如入栈、出栈）。逆波兰表达式计算器初始化：创建一个空栈用于存储操作数。遍历表达式：逐个处理表达式中的每个元素（数字或运算符）。处理数字：如果当前元素是数字，将其转换为数值并压入栈中。处理运算符：如果当前元素是运算符（如+,

-,

*,

/）：

从栈中弹出两个操作数（先弹出的是右操作数，后弹出的是左操作数）。

使用该运算符对两个操作数进行计算。

将计算结果压入栈中。结束条件：遍历完所有元素后，栈中应只剩一个元素，即表达式的最终结果。逆波兰表达式（ReversePolishNotation,RPN）计算器使用栈来处理后缀表达式，其核心逻辑如下：逆波兰表达式计算器

处理

3

和

4：依次压入栈，栈内容为

[3,4]

处理

+：弹出

4

和

3，计算

3+4=7，压入栈，栈内容为

[7]

处理

2：压入栈，栈内容为

[7,2]

处理

*：弹出

2

和

7，计算

7*2=14，压入栈，栈内容为

[14]

处理

7：压入栈，栈内容为

[14,7]

处理

/：弹出

7

和

14，计算

14/7=2，压入栈，栈内容为

[2]

最终结果为

2示例：计算表达式

34+2*7/（等价于中缀表达式

((3+4)*2)/7）逆波兰表达式计算器执行过程逆波兰表达式计算器#include<stdio.h>#include<stdlib.h>#include<string.h>#include<ctype.h>#defineMAX_STACK_SIZE100#defineMAX_TOKEN_LENGTH10//定义顺序栈结构typedefstruct{doubledata[MAX_STACK_SIZE];inttop;}Stack;//初始化栈voidinitStack(Stack*s){s->top=-1;}//判断栈是否为空intisEmpty(Stack*s){returns->top==-1;}//判断栈是否已满intisFull(Stack*s){returns->top==MAX_STACK_SIZE-1;}//入栈操作intpush(Stack*s,doublevalue){if(isFull(s)){printf("错误：栈溢出\n");return0;}s->data[++(s->top)]=value;return1;}//出栈操作intpop(Stack*s,double*value){if(isEmpty(s)){printf("错误：栈为空\n");return0;}*value=s->data[(s->top)--];return1;}//获取栈顶元素intpeek(Stack*s,double*value){if(isEmpty(s)){printf("错误：栈为空\n");return0;}*value=s->data[s->top];return1;}逆波兰表达式计算器//判断是否为运算符intisOperator(char*token){returnstrcmp(token,"+")==0||strcmp(token,"-")==0||strcmp(token,"*")==0||strcmp(token,"/")==0;}//应用运算符进行计算doubleapplyOp(doublea,doubleb,charop){switch(op){case'+':returna+b;case'-':returna-b;case'*':returna*b;case'/':if(b==0){printf("错误：除数不能为零\n");exit(EXIT_FAILURE);}returna/b;default:printf("错误：不支持的运算符%c\n",op);exit(EXIT_FAILURE);}}//计算逆波兰表达式doubleevaluateRPN(char*tokens[],inttokenCount){Stackstack;initStack(&stack);for(inti=0;i<tokenCount;i++){//如果是数字，转换为double并压入栈if(!isOperator(tokens[i])){doublenum=atof(tokens[i]);push(&stack,num);}//如果是运算符，弹出两个操作数进行计算else{doubleval2,val1;if(!pop(&stack,&val2)||!pop(&stack,&val1)){printf("错误：表达式格式不正确\n");exit(EXIT_FAILURE);}doubleresult=applyOp(val1,val2,tokens[i][0]);push(&stack,result);}}逆波兰表达式计算器//最终栈中应只剩一个元素，即计算结果doublefinalResult;if(!pop(&stack,&finalResult)||!isEmpty(&stack)){printf("错误：表达式格式不正确\n");exit(EXIT_FAILURE);}returnfinalResult;}intmain(){//示例：计算(3+4)*2/7char*tokens[]={"3","4","+","2","*","7","/"};inttokenCount=sizeof(tokens)/sizeof(tokens[0]);printf("逆波兰表达式:");for(inti=0;i<tokenCount;i++){printf("%s",tokens[i]);}printf("\n");doubleresult=evaluateRPN(tokens,tokenCount);printf("计算结果:%.2f\n",result);return0;}运行结果银行排队模拟系统银行排队模拟系统银行排队模拟系统使用队列来管理客户，通过事件调度模拟服务过程。银行排队模拟系统执行过程银行排队模拟系统算法步骤步骤1初始化循环队列步骤2从队头取出客户步骤3模拟业务办理（当前时间+=服务时间）重复步骤2-3，直到队列为空银行排队模拟系统#include<stdio.h>#include<stdlib.h>#defineMAX_CUSTOMERS100//客户结构体typedefstruct{intid;//客户IDintarrivalTime;//到达时间intserviceTime;//服务时间}Customer;//队列结构体（顺序存储）typedefstruct{Customerdata[MAX_CUSTOMERS];//存储客户的数组intfront;//队头索引intrear;//队尾索引intsize;//当前队列大小}Queue;//初始化队列voidinitQueue(Queue*q){q->front=0;q->rear=0;q->size=0;}//判断队列是否为空intisEmpty(Queue*q){returnq->size==0;}//判断队列是否已满intisFull(Queue*q){returnq->size==MAX_CUSTOMERS;}//入队intenqueue(Queue*q,Customercustomer){if(isFull(q)){printf("队列已满，无法加入更多客户！\n");return0;//失败}q->data[q->rear]=customer;q->rear=(q->rear+1)%MAX_CUSTOMERS;//循环队列处理q->size++;return1;//成功}使用顺序队列实现银行排队模拟系统//出队intdequeue(Queue*q,Customer*customer){if(isEmpty(q)){printf("队列已空！\n");return0;//失败}*customer=q->data[q->front];q->front=(q->front+1)%MAX_CUSTOMERS;//循环队列处理q->size--;return1;//成功}//查看队头元素intpeek(Queue*q,Customer*customer){if(isEmpty(q)){printf("队列已空！\n");return0;//失败}*customer=q->data[q->front];return1;//成功}intmain(){QueuebankQueue;initQueue(&bankQueue);//定义并初始化客户数组Customercustomers[]={{1,0,5},//客户1在时间0到达，需要5分钟服务{2,1,3},//客户2在时间1到达，需要3分钟服务{3,3,8},//客户3在时间3到达，需要8分钟服务{4,5,6},//客户4在时间5到达，需要6分钟服务{5,7,2}//客户5在时间7到达，需要2分钟服务};intnumCustomers=sizeof(customers)/sizeof(customers[0]);//将所有客户加入队列for(inti=0;i<numCustomers;i++){enqueue(&bankQueue,customers[i]);}printf("=====银行排队模拟系统=====\n");intcurrentTime=0;

银行排队模拟系统while(!isEmpty(&bankQueue)){Customercurrent;dequeue(&bankQueue,¤t);//如果客户到达时间晚于当前时间，更新当前时间if(current.arrivalTime>currentTime){currentTime=current.arrivalTime;}printf("时间%d:客户%d开始办理业务(到达时间:%d,服务时间:%d分钟)\n",currentTime,current.id,current.arrivalTime,current.serviceTime);//更新当前时间为业务办理结束时间currentTime+=current.serviceTime;

printf("时间%d:客户%d业务办理完成\n",currentTime,current.id);}return0;}对比维度逆波兰表达式计算器银行排队模拟系统数据结构栈（后进先出）队列（先进先出）核心操作入栈、出栈入队、出队应用场景表达式计算资源调度、性能分析算法特性确定性计算随机性模拟结束条件处理完所有表达式元素达到预设模拟时间逆波兰表达式计算器和银行排队模拟系统的对比Brute-Force和KMP算法Brute-Force算法和KMP算法串的模式匹配是文本处理（如文档搜索、代码高亮、日志分析）中的核心问题。Brute-Force算法（暴力匹配）KMP算法逻辑直观、易于实现，适合短串匹配避免主串指针回溯，提升长串匹配效率两种经典的模式匹配算法Brute-Force算法Brute-Force算法（简称BF算法）又称“朴素匹配算法”，其核心思想是“逐位比较、回溯重试”——从主串的每一个字符开始，逐个与模式串的字符比较，若出现不匹配则回溯主串指针，从下一个位置重新开始比较，直到匹配成功或遍历完主串。1、Brute-Force算法处理边界情况：若模式串T为空，直接返回0（空串是任何串的子串）；

若模式串长度m>主串长度n，直接返回-1（不可能匹配）；初始化指针：inti=0,j=0;；循环比较：遍历主串和模式串，执行匹配逻辑；返回结果：根据终止条件返回匹配位置或-1。2、实现步骤：

Brute-Force算法#include<stdio.h>#include<string.h>//BF算法实现：S为主串，T为模式串，返回匹配起始位置（-1表示失败）intbruteForce(charS[],charT[]){intn=strlen(S);//主串长度intm=strlen(T);//模式串长度//边界情况处理if(m==0)return0;//空模式串匹配成功if(m>n)return-1;//模式串过长，匹配失败inti=0,j=0;while(i<n&&j<m){if(S[i]==T[j]){//字符匹配，指针后移i++;j++;}else{//字符不匹配，主串回溯，模式串重置i=i-j+1;j=0;}}//若模式串遍历完毕，返回起始位置；否则返回-1return(j==m)?(i-j):-1;}//测试示例intmain(){charS[]="abcdeabc";charT[]="bcd";intpos=bruteForce(S,T);if(pos!=-1){printf("模式串在主串中的起始位置：%d\n",pos);//输出0}else{printf("匹配失败\n");}return0;}运行结果Brute-Force算法时间复杂度衡量算法“执行时间随输入规模增长的趋势”，BF算法的时间复杂度取决于主串与模式串的匹配情况，需分“最好情况”“最坏情况”讨论：符号定义：主串长度为n，模式串长度为m（m≤n）。3、Brute-Force算法的时间复杂度分析

空间复杂度衡量算法“额外占用内存随输入规模增长的趋势”：

BF算法仅使用了i、j、n、m四个整型变量，未使用“与输入规模（n或m）相关的额外内存”；

无论主串、模式串长度如何变化，额外内存开销始终为“常数”。4、Brute-Force算法的空间复杂度分析时间复杂度：O(n*m)（比较次数与主串、模式串长度的乘积相关）。BF算法的空间复杂度为O(1)（常数空间）。KMP算法KMP算法由Knuth、Morris、Pratt三人共同提出，其核心改进是避免主串指针回溯——通过分析模式串的“最长相等前后缀”（也称为“最长公共前后缀”），提前计算出next数组，当字符不匹配时，仅调整模式串指针（无需回溯主串指针），从而将时间复杂度优化至O(n+m)。1、KMP算法的思想（避免主串指针回溯）BF算法效率低的根源是“主串指针频繁回溯”，例如主串S="aaaaaab"、模式串T="aaab"，每次不匹配时i都要回到上一轮起始位置的下一个，导致重复比较。KMP算法的关键洞察：已匹配的前缀中可能存在“相等的前后缀”，可利用这部分重叠信息直接调整模式串指针。例如模式串T="aaab"，当比较到T[3]='b'（不匹配）时，已匹配的前缀是"aaa"；("aaa")的最长相等前后缀是"aa"（前缀"aa"与后缀"aa"相等，长度为2）；因此，模式串指针j可直接调整到2（而非0），主串指针i保持不变，继续比较S[i]与T[2]，避免重复比较。KMP算法2、next数组的概念与求解方法next数组是KMP算法的核心，它是一个与模式串长度相同的数组，next[j]表示“模式串中第j个字符（T[j]）不匹配时，模式串指针应跳转的位置”，其本质是“T[0..j-1]的最长相等前后缀长度”。next数组的求解过程j01234T[j]ababcnext[j]-10012模式串T的next数组

KMP算法示例：next数组的C语言实现。#include<string.h>//求解模式串T的next数组voidgetNext(charT[],intnext[]){intm=strlen(T);//模式串长度intj=0,k=-1;next[0]=-1;//初始值while(j<m-1){if(k==-1||T[j]==T[k]){j++;k++;next[j]=k;}else{k=next[k];//回溯k，寻找更短的相等前后缀}}}KMP算法3、KMP算法的实现步骤KMP算法分为两步：①求解模式串的next数组；②利用next数组进行模式匹配。#include<string.h>#include<stdio.h>#include<stdlib.h>//求解next数组（同前）voidgetNext(charT[],intnext[]){intm=strlen(T);intj=0,k=-1;next[0]=-1;while(j<m-1){if(k==-1||T[j]==T[k]){j++;k++;next[j]=k;}else{k=next[k];}}}//KMP算法实现intkmp(charS[],charT[]){intn=strlen(S);//主串长度intm=strlen(T);//模式串长度//边界情况处理if(m==0)return0;if(m>n)return-1;//动态分配next数组int*next=(int*)malloc(m*sizeof(int));getNext(T,next);//求解next数组inti=0,j=0;while(i<n&&j<m){//j=-1表示需移动主串指针if(j==-1||S[i]==T[j]){i++;j++;}else{//模式串指针跳转，主串不回溯j=next[j];}}free(next);//释放动态内存，避免泄漏return(j==m)?(i-j):-1;}//测试示例intmain(){charS[]="abcdeabc";charT[]="bcd";intpos=kmp(S,T);if(pos!=-1){printf("模式串在主串中的起始位置：%d\n",pos);//输出0}else{printf("匹配失败\n");}return0;}KMP算法KMP算法的时间开销分为两部分：求解next数组和模式匹配，总时间复杂度为两部分之和。求解next数组的时间复杂度模式匹配的时间复杂度总时间复杂度总时间复杂度=求解next数组时间+模式匹配时间=O(m)+O(n)=O(n+m)，无论最好情况还是最坏情况，时间复杂度均为O(n+m)，显著优于BF算法的最坏情况O(n*m)。4、KMP算法的时间复杂度分析模式匹配的循环执行次数为O(n)。5、KMP算法的空间复杂度分析KMP算法的空间复杂度为O(m)。对比维度Brute-Force算法KMP算法核心逻辑逐位比较，主串指针回溯利用next数组，主串指针不回溯时间复杂度（最坏）O（n*m）O（n+m）空间复杂度O（1）（常数空间）O（m）（需存储next数组）实现难度简单，无需额外逻辑较复杂，需理解next数组与递推适用场景短串匹配、代码调试、简单场景长串匹配、文本编辑器、搜索引擎Brute-Force算法和KMP算法的对比O(m)。优于BFKMP校园快递路径规划系统

校园快递路径规划系统#include<stdio.h>#include<string.h>#defineMAX_NODE5//节点数量（A,B,C,D,E）

#defineINF10000