保定网站建设方案优化,怎样自己做刷赞网站,科技网页制作模板,网站视频提取软件app目录
参考资料 代码实现
有序链表头文件LinkList.h 链队列LinkQueue.h
银行业务模拟程序头文件 Bank_Simulation.h
具体函数实现以及主函数
实验中遇到的问题 参考资料
1、数据结构严蔚敏版
2、大佬已有的成套的作业。基本思路照搬大佬和课本#xff0c;不过自己这些代…目录
参考资料 代码实现
有序链表头文件LinkList.h 链队列LinkQueue.h
银行业务模拟程序头文件 Bank_Simulation.h
具体函数实现以及主函数
实验中遇到的问题 参考资料
1、数据结构严蔚敏版
2、大佬已有的成套的作业。基本思路照搬大佬和课本不过自己这些代码绝不是复制粘贴是自己一个个敲下来并经过测试的。Data-Structure/VisualC/CourseBook/0309_BankQueuing/BankQueuing.c at master · Stronger-Git/Data-Structure · GitHub 代码实现
有序链表头文件LinkList.h
有序链表首次出现在一元多项式相加一节是单链表的扩展多了按顺序插入的函数。
#pragma once
#include cstdio
#include cstdlib
#include cstring#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;//Status是函数的类型其值是函数结果状态代码//-----线性链表的存储结构---------
//-----实现单向非循环有序链表-----
//-----头结点与首元结点不一致-----
//-----从2.4节改编而来------------typedef struct {int OccurTime;//事件发生时刻int NType; //事件类型0表示到达事件1至4表示4个窗口的离开事件
}Event,ElemType;//事件类型有序链表LinkList的数据元素类型typedef struct LNode {//结点类型ElemType data;struct LNode* next;
}LNode, * Link, * Position;typedef struct LinkNode { //链表类型Link head, tail; //分别指向线性链表中的头结点和最后一个结点int len; //指示线性链表中数据元素的个数
}LinkNode, * LinkList;typedef LinkList EvenList;//事件链表类型定义为有序链表Status MakeNode(Link p, ElemType e) {//分配由p指向的值为e的结点并返回OK若分配失败则返回ERRORp (Link)malloc(sizeof(LNode));if (!p)return ERROR;p-data e;return OK;
}
void FreeNode(Link p) {//相当于free函数重命名//释放p所指结点free(p);p NULL;
}Status InitList(LinkList L) {//构造一个空的线性链表LL (LinkList)malloc(sizeof(LinkNode));if (!L)return ERROR;L-head L-tail (Link)malloc(sizeof(LNode));if (!L-head)return ERROR;L-head-next NULL;L-len 0;return OK;
}Status DestroyList(LinkList L) {//销毁线性链表LL不再存在Link p;while (L-head) {//删除所有结点p L-head;L-head L-head-next;free(p);}free(L);L NULL;return OK;
}Status ClearList(LinkList L) {//将线性链表L重置为空表并释放原链表的结点空间Link p L-head;while (L-head-next) {//保留一个结点让其作为头结点p L-head-next;L-head-next p-next;free(p);}L-tail L-head;L-len 0;return OK;
}Status InsFirst(Link h, Link s) {//已知h指向线性链表的头结点将s所指结点插入到首元结点之前s-next h-next;h-next s;//这个函数没修改L-len的值课本算法2.20需要补充L-len。return OK;
}Status DelFirst(Link h, Link q) {//已知h指向线性链表的头结点删除链表中的首元结点并以q返回q h-next;if (q NULL)return ERROR;h-next q-next;q-next NULL;return OK;
}Status Append_add(LinkList L, Link s) {//将指针s所指(彼此以指针相链)的一串结点链接在线性链表L的最后一个结点(用L-tail寻找)//之后并改变链表L的尾指针指向新的尾结点while (s) {L-tail-next s;L-tail s;L-len;s s-next;}return OK;
}Status Append_sub(LinkList L, Link s) {//将指针s所指(彼此以指针相链)的一串结点链接在线性链表L的最后一个结点(用L-tail寻找)//之后并改变链表L的尾指针指向新的尾结点while (s) {s-data s-data;L-tail-next s;L-tail s;L-len;s s-next;}return OK;
}Status Remove(LinkList L, Link q) {//删除线性链表L中的尾节点并以q返回改变链表L的尾指针指向新的尾结点if (!L-tail)return ERROR;Link p L-head;while (p-next ! L-tail)p p-next;//寻找尾结点的上一个结点q L-tail;L-tail p;//改变尾结点L-tail-next NULL;L-len--;return OK;
}Status InsBefore(LinkList L, Link p, Link s) {//已知p指向线性链表L中的一个结点将s所指结点插入在p所指结点之前//并修改指针p指向新插入的结点Link q L-head;while (q-next ! p)q q-next;//寻找结点q的上一个结点q-next s;s-next p;//插入sp s;//修改指针pL-len;return OK;
}Status InsAfter(LinkList L, Link p, Link s) {//已知p指向线性链表L中的一个结点将s所指的结点插入在p所指结点之后//并修改指针p指向新插入的结点s-next p-next;p-next s;p s;L-len;return OK;
}Status SetCurElem(Link p, ElemType e) {//已知p指向线性链表L中的一个结点用e更新p所指结点中数据元素的值p-data e;return OK;
}ElemType GetCurElem(Link p) {//已知p指向线性链表L中的一个结点返回p所指结点中数据元素的值return p-data;
}Status ListEmpty(LinkList L) {//若线性链表L为空表则返回TRUE否则返回FALSEif (!L-len)return TRUE;elsereturn FALSE;
}int ListLength(LinkList L) {//返回线性链表L中元素个数return L-len;
}Position GetHead(LinkList L) {//返回线性链表L中头结点的位置return L-head;
}Position GetLast(LinkList L) {//返回线性链表L中尾结点的位置return L-tail;
}Position PriorPos(LinkList L, Link p) {//已知p指向线性链表L中的一个结点返回p所指结点中的直接前驱的位置//若无前驱则返回NULLLink q L-head;if (p L-head)return NULL;while (q-next ! p)q q-next;return q;
}Position NextPos(LinkList L, Link p) {//已知p指向线性链表L中的一个结点返回p所指结点中的直接后继的位置//若无后继则返回NULLreturn p-next;
}Status LocatePos(LinkList L, int i, Link p) {//返回p指示线性链表L中第i个结点的位置并返回OKi值不合法时返回ERROR//头结点当作第0结点首元结点第1个尾结点第L-len个if (i0 || iL-len)return ERROR;int j 0;Link q L-head;while (j i) {q q-next;j;//j也一样}p q;return OK;
}Status LocateElem(LinkList L, ElemType e, Position q, int(*compare)(ElemType, ElemType))
{ // 若升序链表L中存在与e满足判定函数compare()取值为0的元素则q指示L中// 第一个值为e的结点的位置并返回TRUE否则q指示第一个与e满足判定函数// compare()取值0的元素的前驱的位置。并返回FALSEPosition p L-head;Position pp NULL;while (p ! NULL compare(p-data, e) 0){//没到表尾且没有比当前指数大的指数pp p; //记录当前位置p p-next; //继续往后找}if (p NULL || compare(p-data, e) 0) // 到表尾或比当前指数大的指数{q pp;return FALSE;}else // 找到{// 没到表尾且p-data.expne.expnq p;return TRUE;}
}//有序插入
Status OrderInsert(LinkList L, ElemType e, int(*compare)(ElemType, ElemType)) {//按有序判定函数compare()的约定将值为e的结点插入到有序链表L的适当位置上Position s L-head;Position p L-head-next;while (p ! NULL compare(p-data, e) 0) {p p-next;s s-next;}Link pp (Link)malloc(sizeof(LNode));if (pp NULL)return ERROR;//警告C6011pp-data e;s-next pp;pp-next p;if (pp-next NULL)//在3.5节发现该函数没有修改tail和len。L-tail pp;L-len;return OK;
}//遍历链表
Status ListTraverse(LinkList L, void (*visit)(Link)) {//依次对L的每个元素调用函数visit()。一旦visit()失败则操作失败。Link p L-head;for (int i 1;i L-len;i) {p p-next;visit(p);}printf(\n);return OK;
} 链队列LinkQueue.h
#pragma once
//改编自3.4队列
#include cstdio
#include cstdlib
#include cstring#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;//Status是函数的类型其值是函数结果状态代码
typedef struct {int ArrivalTime;//到达时刻int Duration; //办理事务所需时间int Count; //客户编号
}QElemType;//队列的数据元素类型//-----ADT Queue的表示与实现-----
//-----单链队列——队列的链式存储结构-----
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 (QueuePtr)malloc(sizeof(QNode));if (!Q.front)exit(OVERFLOW);//存储分配失败Q.front-next NULL;return OK;
}Status DestroyQueue(LinkQueue Q) {//销毁队列Qwhile (Q.front) {Q.rear Q.front-next;free(Q.front);Q.front Q.rear;}return OK;
}Status ClearQueue(LinkQueue Q) {//将Q清为空队列QueuePtr p1 Q.front-next,p2 Q.front-next;while (p1) {p1 p1-next;free(p2);p2 p1;}Q.rear Q.front;return OK;
}Status QueueEmpty(LinkQueue Q) {//若队列Q为空队列则返回TRUE否则返回FALSEif (Q.front Q.rear)return TRUE;elsereturn FALSE;
}int QueueLength(LinkQueue Q) {//返回队列长度int n 0;QueuePtr p Q.front;while (p ! Q.rear) {p p-next;n;}return n;
}Status GetHead(LinkQueue Q, QElemType e) {if (Q.front Q.rear)return ERROR;e Q.front-next-data;return OK;
}Status EnQueue(LinkQueue Q, QElemType e) {//插入元素e为Q的新的队尾元素QueuePtr p (QueuePtr)malloc(sizeof(QNode));if (!p)exit(OVERFLOW);p-data e;p-next NULL;Q.rear-next p;Q.rear p;return OK;
}Status DeQueue(LinkQueue Q, QElemType e) {//若队列不空则删除Q的队头元素用e返回其值并返回OK//否则返回ERRORif (Q.front Q.rear)return ERROR;//Q.front-nextNULL;也行QueuePtr p Q.front-next;e p-data;Q.front-next p-next;if (Q.rear p)Q.rear Q.front;//队列为空时将尾指针重置free(p);return OK;
}Status QueueTraverse(LinkQueue Q, Status visit(QElemType)) {if (Q.front Q.rear) {printf(队列为空\n);return OK;}QueuePtr p Q.front-next;while (p) {visit(p-data);p p-next;}printf(\n);return OK;
}银行业务模拟程序头文件 Bank_Simulation.h
#pragma once
#include ctimeEvenList ev; //事件表
Event en; //事件
LinkQueue q[5];//4个客户队列
QElemType customer;//客户记录
int TotalTime;//累计客户逗留时间
int CustomerNum;//客户数
int CloseTime;//银行开门时间//函数太多开个头文件梳理一下
//算法3.6 银行业务模拟统计一天内客户在银行逗留的平均时间
void Bank_Simulation_1();//算法3.7 同上
void Bank_Simulation_2();//初始化操作
void OpenForDay();//释放资源打印统计信息
void CloseForDay();//判断事件表是否为空。
Status MoreEvent();//将待处理事件从事件表中移除并将该事件存储到全局变量gEn中。
//event用来存储该事件的类型
Status EventDrived(char event);//处理客户到达事件
void CustomerArrived();//处理客户离开事件
void CustomerDeparture();//代表遇到了无效的事件
void Invalid();//从这里往上是解决算法3.6的//比较两事件发生次序
int cmp(Event a, Event b);//生成随机数
//durtime: 当前客服办理业务所需时间
//intertime: 下一客户到达间隔的时间
void Random(int durtime, int intertime);//返回长度最短的队列的序号
int Minimum();//显示所有客户队列的排队情况
void Show();具体函数实现以及主函数
#include LinkList.h
#include LinkQueue.h
#include Bank_Simulation.hint cmp(Event a, Event b) {//依事件a的发生时刻或或事件b的发生时刻分别返回-1或0或1if (a.OccurTime b.OccurTime)return -1;else if (a.OccurTime b.OccurTime)return 0;elsereturn 1;
}void OpenForDay() {//初始化操作CloseTime 480; //开门时间为480分钟TotalTime 0;CustomerNum 0; //初始化累计时间和客户数为0InitList(ev); //初始化事件链表为空表en.OccurTime 0;en.NType 0; //设定第一个客户到达事件OrderInsert(ev, en, cmp); //插入事件表for (int i 1;i 4;i)InitQueue(q[i]); //置空队列Show();
}void CustomerArrived() {//处理客户到达事件en.NType0。//QElemType customer;//客户记录//Event e; //事件int durtime; //当前客户办理业务需要的时间int intertime;//下一个客户达到时间间隔int t; //下一个客户到达时间int i; //队列编号CustomerNum;Random(durtime, intertime); //生成随机数t en.OccurTime intertime; //下一客户到达时刻if (t CloseTime) { //银行尚未关门插入事件表en.OccurTime t;//下一客户的到达时间en.NType 0;OrderInsert(ev, en, cmp);}i Minimum();//课本中加了参数。这里可不加因为已定义队列变量为全局变量//上面一行代码在求长度最短队列//记录当前客户信息customer.ArrivalTime en.OccurTime;//到达时间customer.Duration durtime; //办理业务所需时间customer.Count CustomerNum; //客户编号//当前客户进入最短队列排队EnQueue(q[i], customer);printf(第 %3d 个客户到柜台 %d 中排队...\n, customer.Count, i);Show();//如果当前队列只有这一个客户排队则需要计算其离开时间//并构造一个“离开”事件插入事件表中if (QueueLength(q[i]) 1) {en.OccurTime en.OccurTime durtime;//当前客户的离开时间en.NType i; //“离开”事件类型值为1-4指示从第几个队列离开OrderInsert(ev, en, cmp); //“离开”事件插入事件表}
}void CustomerDeparture() {ElemType e;int i en.NType;DeQueue(q[i], customer);//删除第i队列的排头用户printf(第 %3d 个客户离开柜台 %d ...\n, customer.Count, i);Show();TotalTime en.OccurTime - customer.ArrivalTime;//累计客户逗留时间if (!QueueEmpty(q[i])) {//设定第i队列的一个离开事件并插入事件表GetHead(q[i], customer);e.OccurTime en.OccurTime customer.Duration;e.NType i;OrderInsert(ev, e, cmp);}
}void Bank_Simulation_2() {Link p;OpenForDay(); //初始化while (!ListEmpty(ev)) {DelFirst(GetHead(ev), p);if (p NULL)break;//防止出现表内只有头结点无首元结点的局面en GetCurElem(p);if (en.NType 0)CustomerArrived(); //处理客户到达事件elseCustomerDeparture(); //处理客户离开事件}CloseForDay();
}void CloseForDay() {printf(当天共有%d个客户平均逗留时间为%.2f分钟。\n,CustomerNum,(double)TotalTime/CustomerNum);
}void Random(int durtime, int intertime) {srand((unsigned)time(NULL));durtime rand() % 20 1;intertime rand() % 5 1;
}int Minimum() {int i1 QueueLength(q[1]);int i2 QueueLength(q[2]);int i3 QueueLength(q[3]);int i4 QueueLength(q[4]);if (i1 i2 i1 i3 i1 i4)return 1;if (i2 i1 i2 i3 i2 i4)return 2;if (i3 i1 i3 i2 i3 i4)return 3;if (i4 i1 i4 i2 i4 i3)return 4;return 0;
}void Show() {int i;QueuePtr p;//记录到来的客户是第几个//遍历所有客户队列for (i 1;i 4;i) {for (p q[i].front;p;p p-next) {if (p q[i].front) {if (i 1)printf(柜台(1)●);if (i 2)printf(柜台(2)●);if (i 3)printf(柜台(3)●);if (i 4)printf(柜台(4)●);}elseprintf((%03d), p-data.Count);if (p q[i].rear)printf(\n);}}printf(\n);
}//-----上面的是算法3.7所需要的函数-----
//-----下面的是算法3.6特有的部分-------
void Bank_Simulation_1() {char eventType;OpenForDay(); //初始化//如果事件表非空while (!MoreEvent()) {if (EventDrived(eventType) ERROR)break;switch (eventType) {case A:CustomerArrived();//处理客户到达事件break;case D:CustomerDeparture();//处理客户离开事件break;default:Invalid();}}CloseForDay();
}Status MoreEvent() {return ListEmpty(ev);
}Status EventDrived(char eventType) {Link p;DelFirst(GetHead(ev), p);if (p NULL)return ERROR;//防止出现表内只有头结点无首元结点的局面en GetCurElem(p);if (en.NType 0)eventType A;elseeventType D;return OK;
}void Invalid() {printf(运行错误);exit(OVERFLOW);
}int main()
{Bank_Simulation_1();//Bank_Simulation_2();return 0;
}
实验中遇到的问题
1、初始化操作未达到预期标准经检查是OrderInsert函数插入最后的位置未修改对应链表的长度和尾指针所致。
若不修改L-len在Bank_simulation_2函数中将跳出while循环若不修改L-tail呃似乎没有影响。
2、当事件全部结束时事件表内依然有一个结点就是头结点此时虽然表内元素全空但表没空。在Bank_simulation_2函数中p结点为头结点的下一个结点此时pNULLp-data无意义所以在GetCurElem函数上会报错。
