线行链表及其运算.ppt

2 3线性表的链式存储及其运算 线性表的顺序存储结构存在缺点是 插入与删除操作 需大量移动数据元素 再者 在顺序存储结构下 线性表的长度估计困难 并且当有多个顺序表同时共享计算机的存储空间时 不便于对存储空间进行动态分配 由于线性表的顺序存储结构存在以上缺点 因此 对于大的线性表 特别是元素变动频繁的大线性表 不宜采用顺序存储结构 而是采用下面介绍的链式存储结构 2 3 1线性表的链式存储 假设数据结构中的每一个数据结点对应于一个存储单元 这种存储单元称为存储结点 简称结点 若每个结点由两部分组成 一部分用于存放数据元素值 称为数据域 另一部分用于存放指针 称为指针域 其中指针用于指向该结点的前一个或后一个结点 通过每个结点的指针域将n个结点按其逻辑顺序连接在一起而构成的数据存储结构 称为链式存储结构 链式存储结构 既可用来表示线性结构 也可用来表示非线性结构 线性表的链式存储结构 称为线性链表 对线性链表而言 它不要求逻辑上相邻的元素在物理位置上也相邻 其存储单元既可以是连续的 也可以是不连续的 甚至可以零散分布在内存中的任何位置上 通常 为了适应线性链表的存储 计算机的存储空间被划分成一个一个的小块 每一小块占若干字节 这些小块就是存储结点 存储结点的结构 在图中 data域就是数据域 或称值域 next域就是指针域 或称链域 在线性链表中 用一个专门的头指针head指向线性链表中第一个数据元素的结点 即存放线性链表中第一个数据元素的存储序号 线性链表中最后一个元素没有后件 因此 线性链表中最后一个结点的指针域为空 用NULL或0表示 表示链表终止 用下面例子 来说明线性链表的存储结构 设线性表为 a1 a2 a3 a4 存储空间具有9个存储结点 线性链表的物理存储状态举例 2 3 2线性链表的基本运算 1 单链表的基本运算单链表结构类型定义如下 typedefstructnode ElemTypedata 数值域 structnode next 指针域 ListNode LinkList 为了便于实现插入 删除结点的操作 通常在单链表的第一个结点之前增设一个表头结点 该结点的结构与表中其他结点的结构相同 其数据域可以不存储任何信息 也可以存储如线性表的表名 长度等附加信息 其指针域用来存放线性表中的第一个结点的地址 若线性表为空表 则表头结点的指针域为空 设H为单链表的头指针 指向头结点 存储单链表的第一个元素的结点称为开始结点 或称首结点 其指针域存放第二个结点的地址 称存储最后一个元素的结点称终端结点 或称尾结点 其指针域为空 如图3 5所示 1 建立单链表 依据新结点插入位置的不同 将生成的单链表分为先进先出 后进先出及有序三种 先进先出单链表 在建立单链表时 将每次生成的新结点 总是插入到当前链表的表尾作为尾结点 若用换行符 n 作为输入结束标志 用rear作为总是指向链表尾结点的尾指针 则建立带表头结点的先进先出单链表的算法如下 LinkListCreateList ff LinkListH p rear charch H LinkList malloc sizeof ListNode 生成表头结点 if H printf n存储分配失败 exit 1 H next NULL 表初值为空 rear H 尾指针指向表头结点 while ch getchar n p LinkList malloc sizeof ListNode 生成新结点 if p printf n存储分配失败 exit 1 p data ch p next p 新结点插入表尾 rear p 尾指针指向新结点 return H 返回头指针 后进先出表 在建立单连表时 将每次生成的新结点 总是插入到当前链表的表头结点之后作为当前链表的首结点 若用换行符 n 作为输入结束标志 则建立带表头结点的后进先出单链表的算法如下 LinkListCreateList fr LinkListH p charch H LinkList malloc sizeof ListNode 生成表头结点 if H printf n存储分配失败 exit 1 H next NULL 表初值为空 while ch getchar n p LinkList malloc sizeof ListNode 生成新结点 if p printf n存储分配失败 exit 1 p data ch p next H next H next p 插入表头结点之后 return H 返回头指针 有序单链表 是指原表中结点的数据值 按从小到大 或从大到小 的顺序排列 为了建立一个有序单链表 每次生成的新结点 总是插入到当前链表的合适位置 在带表头结点的单链表中 所有位置上的插入操作都是一致的 不需要做特殊处理 若用换行符 n 作为输入结束标志 pre为指向当前结点前件的指针 cur为指向当前结点的指针 则建立带表头结点的有序单链表的算法如下 LinkListCreateList or LinkListH pre cur pre将指向当前结点的前件 cur将指向当前结点 charch H LinkList malloc sizeof ListNode 生成表头结点 if H printf n存储分配失败 exit 1 H next NULL 表初值为空 while ch getchar n pre H pre指向当前结点的前件 cur H next cur指当前结点 while cur cur LinkList malloc sizeof ListNode 生成新结点 if cur printf n存储分配失败 exit 1 cur data ch cur next pre next 新结点插在pre所指结点的后面 pre next cur 尾指针指向新结点 return H 返回头指针 容易看出 以上3个算法的时间复杂度均为O n 2 查找结点在对单链表进行插入或删除运算时 总是首先要找到插入或删除的位置 这就需要对线性链表进行扫描查找 通常 有查找第i个结点或查找具有给定元素值的结点 两种情况 查找单链表中的第i个结点在带表头结点的单链表中 查找第i个结点 不能像在顺序表中那样 只能从单链表的头指针出发 沿着结点的链域逐个向下 直到搜索到第i个结点为止 此时 p指向第i个结点 在带表头结点的单链表H中 查找第i个结点的算法如下 LinkListGetElem LinkListH inti intj 1 j累计当前扫描的结点数 LinkListp p H next p指向第一个结点 while p if j i 第i个结点不存在 返回NULL 在单链表中查找给定值的结点依据给定的数据项的值x 在带表头结点的单链表中查找 若找到 则通过i返回首次找到的结点的位置 同时 返回指向该结点的指针p 若查找失败 则返回NULL 在带表头结点的单链表H中查找x的算法 LinkListLocateElem LinkListH ElemTypex int i LinkListp p为指针 p H next p指向第一个结点 i 1 while p if p data x return p 找到返回结点位置 elsereturn NULL 没找到返回NULL 以上两个 查找算法的时间复杂度均为O n 3 单链表的插入单链表的插入 是指在单链表中插入一个新结点 有两种情况 在单链表的第i个位置插入一个新结点和在有序单链表中插入一个新结点 在单链表的第i个位置插入一个新结点假设单链表中有n个结点 插入位置i的允许取值范围为1至n 1 在第i个位置插入一个新结点 首先 要找到第i 1个结点 然后将新结点插入到第i 1个结点之后 若指针pre指向第i 1个结点 cur指向新结点 插入就是让新结点的指针域指向原来的第i个结点 即cur next pre next 并且修改第i 1个结点的指针域 让其指向新结点 即pre next cur 插入过程如图3 6所示 在第i个位置 插入一个值为x的新结点算法 InsertList LinkListH inti ElemTypex LinkListpre cur pre GetElem H i 1 调用查找函数使pre指向第i 1个结点 if pre printf ni值不合法 exit 1 cur LinkList mallco sizeof ListNode 生成新结点 if cur printf n存储分配失败 exit 1 cur data x 新结点的值为x cur next pre next 新结点的指针域值指向原来的第i个结点 pre next cur 第i 1个结点的指针域值指向新结点 在有序单链表中插入一个新结点要在一个带表头结点的有序单链表H中插入一个值为x的新结点 就必须对生成的新结点 依据值x的大小在表中找到合适的插入位置 然后将其插入到链表中 算法如下 InsertOrder LinkListH ElemTypex LinkListcur pre pre H cur H next while cur cur指向当前结点 cur LinkList malloc sizeof ListNode 生成新结点 if cur printf n存储分配失败 exit 1 cur data x 新结点值为x cur next pre next 插入新结点 pre next cur pre指向新结点 从单链表插入新结点的过程中 可以看出对线性链表进行插入操作时 没有发生数据元素的移动 只是改变了有关结点的指针域 在以上两个插入结点的算法中 时间复杂度的数量级均为O n 4 单链表的删除操作单链表的删除操作 是指在单链表中 删除包括指定元素的结点 有两种情况 一是删除单链表的第i个结点 二是删除单链表中 具有给定值x的结点 均不移动表中的数据元素 只需改变 被删除结点的前一个结点指针 删除单链表的第i个结点设单链表中有n个结点 删除第i个结点时 i的允许取值范围为1至n 与插入类似 首先要找到第i 1个结点 再用指针pre指向该结点 用指针cur指向第i个结点 然后使第i 1个结点的指针指向第i 1个结点 pre next cur next 最后用函数free释放第i个结点所占空间 在带表头结点的单链表H中 删除第i个结点的算法如下 DeleteList1 LinkListH inti ElemType x LinkListpre cur pre GetElem H i 1 用GetElem函数找第i 1个结点并使pre指向它 if pre NULL pre next NULL 判断i值是否合法 printf ni值不合法 exit 1 cur pre next cur指第i个结点 pre next cur next 使第i 1个结点的指针指向第i 1个结点 x cur data 第i个结点的值由x返回 free cur 释放第i个结点所占的空间 删除单链表中具有给定值的结点在带表头结点的单链表H中 搜索具有给定值x的结点 若找到 就删除该结点 这种删除情况的算法如下 DeleteList2 LinkListH ElemTypex LinkListp pre p H next p指向链表的第1个结点 pre H pre指向第1个结点的前件 while p 释放值为x的结点空间 elseprintf n链表中没有具有值为x的结点 此算法的时间复杂度的数量级为O n 2 循环链表及其基本运算从单链表任一结点出发查找其前面的结点是很困难的 为了克服这一缺点 我们使带表头结点的单链表中的最后一个结点的指针指向头结点 使整个链表构成一个环形 这种链式存储结构被称为循环链表 特别地 只有头结点的循环链表称为空循环链表 带头结点的循环链表中 可看出循环链表的结构与前面所讨论的单链表相比 具有以下两个特点 1 头结点的数据域为任意或者根据需要来设置 头结点的指针域指向线性表的第一个元素的结点 头指针指向表头结点 2 最后一个结点的指针域不是NULL 而是指向表头结点 即在循环链表中没有空指针 所有结点的指针构成了一个环状链 在循环链表中 只要指出表中任何一个结点的位置 就可以从它出发访问到表中其他所有的结点 而线性单链表做不到这一点 循环链表的插入和删除的方法与线性单链表基本相同 不再赘述 只须注意一点 在单链表的结构中 空表的条件是H next NULL 而在循环链表结构中 空表的条件是H next H 3 双向链表从循环链表的结构特征可看出 若要找一个结点的直接前件结点需要兜一个圈子才行 这当然是很不方便的 就像乘单向环行的公交车一样 若坐过了站 就要多坐许多站 才能到达预定的地点 因此 任何城市的公交车 除单行道外 都是双向行驶的 为类似的目的 可以将单向链表改为双向链表 双向链表的每个结点含有两个指针域 一个指向其直接前件结点 称为prior 一个指向其直接后件结点 称为next 有了两个方向的链指针之后 在链表上进行访问非常方便 但是在双向链表上进行插入和删除运算 要涉及两个指针的链接 故比单链表的插入与删除运算复杂些 2 3 3线性链表应用举例 设多项式Pn x a0 a1x a2x2 anxn其中ai i 0 1 2 n 是x的i次幂的系数 即x的幂指数为i 线性表 a0 a1 a2 an 可唯一确定多项式Pn x 两个多项式相加 如果采用顺序存储结构来存储此线性表 由于多项式中可能有多项的系数为0 顺序存储就会浪费大量存储空间 故应采用单链表来存储该线性表 在单链表中 每个结点设3个域 分别为系数域coef 指数域exp和指针域next 例如 多项式a x 4 3x 7x5 8x7与多项式b x 3 7x5 6x6相加 所得的和 为多项式c x a x b x 7 3x 6x6 8x7的单链表形式 从图可清楚地看出 多项式a x 与b x 相加的结果为多项式c x 变成由单链表Ha和Hb 求单链表Hc了 假设单链表是以x的幂指数值的递增顺序排列 指针pa pb分别指向Ha Hb当前正被考察的两个结点 比较两个结点的指数域 有以下3种情况 pa expexp 将pa所指的结点插入到Hc链表中 移动指针pa指向下一结点 pa exp pb exp 将pb所指的结点插入到Hc链表中 移动指针pb指向下一结点 pa exp pb exp 将两个结点中的系数相加 若和不为0 则插入到Hc链表中 移动指针pa pb 指向下一结点 重复上述过程 直至pa或pb的值为NULL 当其中一个为空时 说明该表的结点已经处理完 只要将另一表的剩余部分链接到Hc链表之后 定义链表结点结构如下 typedefstructnode floatcoef coef为多项式项的系数 intexp exp为多项式项的x幂指数 structnode next ListNode LinkList 说明ListNode为结构体变量 LinkList为结构体指针 3 栈的链式存储结构及运算栈的链式存储结构可通过单链表来实现 在单链表中 每一个结点表示栈中的一个元素 由于栈是在链表头部进行操作的 故链式栈不需要设置头结点 栈顶指针就是链表的头指针 它唯一的确定了一个栈 假设将元素a1 a2 a3 an顺序进栈 则a1为栈底元素 an为栈顶元素 对链式栈的基本操作与顺序栈相类同 通常进栈和出栈 相对使用较多 进栈就是向链栈的栈顶插入一个元素 此时 可使该元素结点的指针域 指向原来的栈顶结点 而栈顶指针则修改为指向该元素的结点 这样 该结点就成为新的栈顶结点 出栈就是从链栈的栈顶删除一个元素 此时可取出栈顶元素并使栈顶指针指向原栈顶结点的后继结点 链栈的类型说明及其常见基本操作如下 1 链栈的类型说明 typedefcharElemType 新类型ElemType是字符型 typedefstructstacknode ElemTypedata 栈的值域是字符型 structstacknode next StackNode StackNode为结构型 typedefstruct StackNode top 栈顶指针 LinkStack LinkStack为结构类型 2 链栈的基本操作 构造一个空链栈voidInitStack LinkStack s s top NULL 栈顶指针置空 判断链栈是否为空栈intStackEmpty LinkStack s 若栈空 则返回1否则返回0 returns top NULL 进栈 入栈或压栈 voidpush LinkStack s ElemTypex StackNode p p StackNode malloc sizeof StackNode if p printf n存储分配失败 exit 1 p data x 新结点值域赋值x p next s top 新结点 p插入到栈顶 s top p 修改栈顶指针 退栈 出栈 ElemTypepop LinkStack s ElemTypex StackNode p p s top if StackEmpty s 调用判断栈是否为空的函数 若栈空 则下溢 printf n栈已空 下溢 exit 1 x p data x赋值欲删的栈顶结点数据 s top p next 删除栈顶结点 修改栈顶指针 free p 释放已删结点的空间 returnx 返回已删结点的数据 读链栈的栈顶元素ElemTypeGetTop LinkStack s if StackEmpty s printf n栈已空 exit 1 returns top data 若链栈非空 则返回栈顶元素 但不删除 4 栈的应用举例数制转换过程是栈的典型应用 例如将一个十进制整数n转换为r进制数 通常采用 除基数r取余法 的转换方法 即先将n逐次除以r 然后倒序写出余数 在转换过程中依次所得的余数 就是由低到高得到的r进制数中的每一位数字 系统将余数存储到一个栈中 第一个余数存在栈底 最后一个余数存在栈顶 输出时 系统从栈顶依次释放余数所占存储区 也就是说由高到低输出每一数位的值 最终得到转换结果 图4 4所示的是将十进制数74转换为八进制数的过程 结果为八进制数112 下面给出将十进制正整数n转换为r进制数的程序 include include 头文件stdlib h中含有exit defineMaxSize100 说明欲分配的栈空间最多为100个元素 typedefintElemType 说明栈元素的数据类型为整型 typedefstruct ElemTypestack MaxSize inttop SeqStack SeqStack为结构类型 voidInitStack SeqStack s 将顺序栈s初始化为空栈 s top 1 intStackEmpty SeqStack s 判断栈s是否为空若为空则返回1 returns top 1 voidpush SeqStack s ElemTypex 进栈 即向栈s中插入元素 if s top MaxSize 1 printf nstackoverflow exit 1 s top s stack s top x intpop SeqStack s 退栈 即删除栈s的栈顶元素 if StackEmpty s printf nstackunderflow exit 1 returns stack s top voidconversion longnum intr 用除r取余法将结果保存到栈s中 SeqStacks intk intx InitStack 修改num的值为被r除的商 printf n while StackEmpty voidmain 主函数 longn intr printf ninputen r scanf ld d 调用转换函数并输出转换结果 注 r可为8 2 16等 例如 当运行此程序时 n为74 r为2 则转换结果为二进制数1001010 4 2队列及其基本运算 1 什么是队列 队列 queue 是一种只允许在表的一端进行插入 而在另一端进行删除的线性表 允许插入 入队 的一端称为队尾 rear 允许删除 出队 的一端称为队头 front 不含元素的队列称为空队列 若将元素按a1 a2 a3 an的顺序入队 则a1为队头元素 an为队尾元素 如图4 5所示 退出队列时 也只能按a1 a2 a3 an的顺序出队 这和日常生活中的排队是一致的 在队列中 最先插入的元素 将最先能够被删除 反之 最后插入的元素 将最后才能被删除 因此 队列又称为 先进先出 或后进后出的线性表 队列也有顺序存储和链式存储两种情况 2 队列的顺序存储结构和基本运算 队列的顺序存储结构称为顺序队列 顺序队列通常用一个一维数组来存放队列中的数据元素 此外 还需设置两个整形变量front和rear作为队头指示器和队尾指示器 分别指示队头和队尾元素在向量空间中的位置 我们约定在队列初始化时 这两个指示器均置0值 入队时 将新元素插入到rear所指位置后 再将rear的值加1 出队时 删除front所指位置的元素后 再将front的值加1并返回被删元素 由此可见 当队头和队尾指示器值相等时 队列为空 在非空队列里 front始终指向队头元素 而rear始终指向队尾元素的下一位置 在队列中 队尾指示器rear与队头指示器front共同反映了队列中元素动态变化的情况 假设给队列分配的最大存储空间为4 如图4 6所示 在图4 6 b 所示满队列状态下 如果还有新元素请求入队 则会出现 上溢 错误 在图4 6 c 所示状态下 如果还有新元素请求入队 这时 虽然队列的实际可用空间没有占满 但由于尾指针已超越存储空间的上界 故不能做入队操作 否则会出现 假上溢 的错误 在图4 6 d 所示状态下 如果还要进行出队操作 由于这时队列已空 队列的头 尾指针均已超越存储空间的上界 故不能进行出队操作 否则会出现 下溢 的错误 3 循环队列及其运算为避免发生顺序队列的 假上溢 现象 充分利用队列的存储空间 可以将顺序队列存储空间的最后一个位置绕到第一个位置 形成逻辑上的环状空间 供队列循环使用 我们称这样的队列为循环队列 如图4 7所示 在循环队列中进行出队 入队操作时 头 尾指针仍要加1 只不过当头尾指针指向上界时 其加1的操作结果是指向下界0 假设当前循环队列最多能容纳MAXSIZE个元素 这种循环意义下的加1操作可表示为 i i 1 MAXSIZE i表示front或rear 在图4 7所示的循环队列中 队列的最大容量是4 在图4 7 b 所示的状态下 再插入元素D 则队列空间就会被占满 变成图4 7 c 所示的状态 此时 存在与4 7 a 相 同的front rear关系 由此可知 在循环队列中 仅依据头尾指针相等 是无法判断队列是 空 还是 满 要解决这个问题 常用的方法是 少用一个元素空间 约定入队前 若尾指针加1后等于头指针 则认为队列满 rear所指单元始终为空 先给出循环队列类型的定义 再给出用此方法实现循环队列的几种基本操作 defineMAXSIZE100 符号常量MAXSIZE代表队列的最大容量100 typedefcharElemType 说明新类型ElemType是字符型 typedefstruct ElemTypedata MAXSIZE intfront intrear CircularQueue 新类型CircularQueue是结构体 1 构造一个空队列VoidInitQueue CircularQueue q q front q rear 0 2 判断队列空intQueueEmpty CircularQueue q 队列为空返回1 否则返回0 if q front q rear exit 1 elseexit 0 3 入队voidInsertQueue CircularQueue q ElemTypex if q rear 1 MAXSIZE q front printf n队满 上溢 exit 1 q data q rear x 新元素插入到队尾 q rear q rear 1 MAXSIZE 尾指针加1 4 出队ElemTypeDeleteQueue CircularQueue q ElemTypex if QueueEmpty q printf n队空 下溢 exit 1 x q data q front 取出队头元素 q front q front 1 MAXSIZE 队头指针加1 returnx 5 读取队头元素ElemTypeGetHead CircularQueue q ElemTypex if QueueEmpty q printf n队空 下溢 exit 1 x q data q front 取出队头元素 returnx 4 链队列队列的链式存储结构称为链队列 因为需要在表头进行删除操作和在表尾进行插入操作 所以在链队列中 需要使用队头和队尾两个指针 其中队尾指针指向链队列的最后一个结点 于是 一个链队列就由一个头指针和一个尾指针唯一地确定了 链队列和线性表的单链表一样 为了操作方便 可以给链队列增加一个头结点 并令头指针指向头结点 如图4 8所示 链队列的类型定义如下 typedefcharElemType typedefstructqueuenode 链队列中的结点类型 ElemTypedata structqueuenode next QueueNode typedefstruct 将两个指针封装在一起 QueueNode front 队头指针 QueueNode rear 队尾指针 LinkQueue 图4 8 a 是空链队列的示意图 图中q为LinkQueue型指针 图4 8 b 是非空链队列的示意图 链队列的基本操作有5种 相应的算法如下 1 构造一个空队列voidInitQueue LinkQueue q q front q rear QueueNode malloc sizeof QueueNode 建新结点 if q front printf n存储分配失败 exit 1 q front next NULL 2 判断空队列intQueueEmpty LinkQueue q if q front q rear 3 入队voidInsQueue LinkQueue q ElemTypex QueueNode p p QueueNode malloc sizeof QueueNode if p printf n存储分配失败 exit 1 p data x p next NULL q rear next p 新结点插入到队尾 q rear p 队尾指针指向新结点 4 出队ElemTypeDelQueue LinkQueue q QueueNode p ElemTypex if QueueEmpty q printf n队列空 下溢 exit 1 p q front next 指向队头结点 x p data 取出队头结点的数据 q front next p next 修改队头指针即将队头指针从链上摘下 if q rear p q rear q front 若取出队头元素后 原队列为空 修改队尾指针 free p 释放被删的队头结点 return x 返回队头结点的数据 5 读取队头元素ElemTypeGetHead LinkQueue q QueueNode p ElemTypex if QueueEmpty q printf n队列空 下溢 exit 1 p q front next 指向队头结点 x p data 取出队头结点的数据 return x 返回队头结点的数据 5 队列应用举例 例如 某银行储蓄所有一个服务窗口 该窗口在某个时刻只能接待一位顾客 假设为一位顾客服务的时间为定值 在顾客人数众多时需要在窗口排队 若队列用q表示 顾客到达的时间是随机的 约定按如下方式处理 每单位时间内产生一个随机数arrive 0 arrive 1 如果arrive小于prob 0 prob 1 由程序输入的特定值 则记为有1人到达 顾客用整数表示 其值为该顾客进入队列的时间 时间用time表示 其初值为0 假设time每变化一个单位对应于实际时间1分钟 当顾客到达时 若服务窗口空闲 顾客的等待时间为0 否则等待时间为服务窗口开始为顾客服务的时间减去顾客到达的时间 可以模拟计算在时间段simutime 由程序输入 内 上述服务窗口的总服务人数 cus num 和每个顾客平均排队所需的等待时间 aver 程序如下 include include defineMAXSIZE100 符号常量MAXSIZE表示100 typedefstruct intdata MAXSIZE intfront 队头指针 intrear 队尾指针 queue 新类型queue为结构体类型 队列初始化函数 voidInitQueue queue q q front q rear 0 入队函数 voidEnQueue queue q intx if q rear 1 MAXSIZE q front printf noverflow 队满上溢 exit 1 q data q rear x 新元素插入队尾 q rear q rear 1 MAXSIZE 尾指针加1 判断队列是否为空函数 intQueueEmpty queue q 队列为空 返回1 否则返回0 if q rear q front return1 elsereturn0 出队函数 intDeQueue queue q intx if QueueEmpty q printf nunderflow 队空下溢 exit 1 x q data q front 取出头元素 q front q front 1 MAXSIZE 头指针加1 returnx 主函数 voidmain queueq inttime servetime simutime intbusy 0 sumwaits 0 cus num 0 floatprob arrive aver printf ninputtheprob 输入特定检查值 scanf f printf ninputthesimutime 输入模拟时间 scanf d 窗口有顾客 顾客所需时间自减 if busy 0 顾客等待时间累加 if cus num 0 aver 0 0 elseaver 1 0 sumwaits cus num printf n dcus num aver 4 1f cus num aver 输出服务总人数cus num及每位顾客的平均等待时间aver 注 若运行时prob 0 8 servetime 2 simutime 30 则输出结果为cus num 16 aver 6 9