链队列的基本操作

definition.h =================================== typedef char ElemType;

typedef struct{ ElemType data; struct Qnode *next; }Qnode, *Qptr;//队列结点

typedef struct{ Qptr front, rear;//队头指针，队尾指针 }LinkQueue;

int InitQueue(LinkQueue *);//建立空队列 void Destroy(LinkQueue *);//销毁队列 int EnQueue(LinkQueue *, ElemType);//进入队列 int DeQueue(LinkQueue *);//出队 =====================================================================

main.c ==================================== #include<stdio.h> #include"definition.h"

int main() { return 0; } ================================================

function.c ================================================= #include <stdio.h> #include <malloc.h> #include "definition.h"

int InitQueue(LinkQueue *Q)//建立空队列 { Q->rear=Q->front=(Qptr)malloc(sizeof(Qnode)); if(!Q->front) return 1; Q->front->next=NULL; return 0; }

void Destroy(LinkQueue *Q)//销毁队列 { while(Q->front){ Q->rear=Q->front->next; free(Q->front); Q->front=Q->rear; } }

int EnQueue(LinkQueue *Q, ElemType e)//进入队列 { Qptr tmp;

tmp=(Qptr)malloc(sizeof(Qnode)); if(!tmp) return 1; tmp->data=e; tmp->next=NULL; Q->rear->next=tmp; Q->rear=tmp;

return 0; }

int DeQueue(LinkQueue *Q)//出队 { Qptr tmp;

if(Q->front==Q->rear) return 1;//如果队列已空，返回1

tmp=Q->front->next; Q->front->next=tmp->next; if(Q->rear==tmp)//如果队尾元素被删除，则队尾指针要指向头结点 Q->rear=Q->front;

free(tmp); return 0; } ============================================================================

循环队列的基本操作

definition.h ====================================== #define MAXSIZE 100 //最大队列长度

typedef char ElemType;

typedef struct{ ElemType *base; unsigned front, rear;//队头指针，队尾指针 }SqQueue;

int InitQueue(SqQueue *);//建立空队列 int EnQueue(SqQueue *, ElemType);//进入队列 int DeQueue(SqQueue *);//出队 int Length(SqQueue *);//队列长度 =========================================================

main.c ============================================ #include<stdio.h> #include"definition.h"

int main() { return 0; } =============================================

function.c ==================================== #include <stdio.h> #include <malloc.h> #include "definition.h"

int InitQueue(SqQueue *Q)//建立空队列 { Q->base=(ElemType *)malloc( MAXSIZE*sizeof(ElemType) ); if(!Q->base) return 1; Q->front=Q->rear=0; return 0; }

int EnQueue(SqQueue *Q, ElemType e)//进入队列 { if( (Q->rear+1)%MAXSIZE==Q->front ) return 1;//队满(此判断队满法的代价是，少利用一个空间) Q->base[Q->rear]=e; Q->rear=++Q->rear % MAXSIZE; return 0; }

int DeQueue(SqQueue *Q)//出队 { if(Q->front==Q->rear) return 1;//队空 Q->front= ++Q->front % MAXSIZE; return 0; }

int Length(SqQueue *Q)//队列长度 { return (Q->rear - Q->front + MAXSIZE) % MAXSIZE; }

银行业务模拟（计算客户平均等待时间）

definition.h ============================================== #define CLOSETIME 1440

typedef struct{ unsigned OccurTime, NType;//事件发生时刻；事件类型，6代表到达事件，0-5代表6个窗口的

离开事件 }Event;//链表数据元素类型

typedef struct{ Event event; struct Enode *next; }Enode, *EventList;

typedef struct{ unsigned ArrTime, Duration;//到达时刻；办理时间 }QElem;//队列数据元素类型

typedef struct{ QElem Cust;//客户记录 struct Qnode *next; }Qnode, *Qptr;

typedef struct{ Qptr front, rear;//队头指针，队尾指针 }LinkQueue;

EventList ev;//事件表 Event en;//事件 LinkQueue q[6];//6个客户队列 QElem customer;//客户记录 unsigned TotalTime, CustNum;//累计客户逗留时间，客户数

int Open();//初始化操作 int CustArr();//处理客户到达事件 EventList InitList();//创建链表 int OrderInsert(EventList, Event);//插入事件表 int InitQueue(LinkQueue *);//建立空队列 short Minimun();//求长度最短队列 unsigned QueueLength(LinkQueue);//计算队列长度 int EnQueue(LinkQueue *, QElem);//进入队列 int CustDepart();//处理客户离开事件 int DeQueue(LinkQueue *);//出队 void DelFirst();//删除事件表第一个节点，并把值赋给en ==========================================================================

main.c ============================================================ #include <stdio.h> #include "definition.h"

int main() { if( !Open() ) return 1;//初始化失败，退出 while(ev->next){ DelFirst();//删除事件表第一个节点，并把值赋给en if( en.NType == 6 ){ if( !CustArr() ) return 1; } else{ if( !CustDepart() ) return 1; } }

printf( "平均逗留时间为：%g\n", (float)TotalTime / CustNum ); return 0; }

//还没回收动态分配了的空间，懒得写了 =====================================================================

function.c ===================================================== #include <stdio.h> #include <malloc.h> #include <stdlib.h> #include <time.h> #include "definition.h"

int Open()//初始化操作 { short i;

srand(time (NULL));//生成随机数种子 CustNum=TotalTime=0;//初始化累计时间和客户数 if( !(ev=InitList()) )//初始化事件链表 return 0;//创建失败，返回0 en.OccurTime=0; en.NType=6;//设定第一个客户到达事件 if( !OrderInsert(ev, en) )//插入事件表 return 0;//插入失败，返回0 for(i=0; i<6; i++){//置空队列 if( !InitQueue(&q[i]) ) return 0;//创建队列失败，返回0 } return 1; }

int CustArr()//处理客户到达事件，en.NType==6 { unsigned durtime, intertime; QElem e; short i;

CustNum++; //生成随机数 durtime = rand() % 30 + 1;//事务处理时间不超过30分钟 intertime = rand() % 5 + 1;//5分钟内有一位客人到达银行 e.ArrTime=en.OccurTime; e.Duration=durtime; en.OccurTime += intertime;//下一客户到达时间 if(en.OccurTime < CLOSETIME){//银行尚未关门，插入事件表 if( !OrderInsert(ev, en) )//插入失败 return 0; }

i=Minimun();//求长度最短队列 if( !EnQueue(&q[i], e) ) return 0; if( QueueLength(q[i]) == 1 ){//设定第i队列的一个离开事件并插入事件表 en.NType=i; en.OccurTime=e.ArrTime+durtime; OrderInsert(ev, en); }

return 1; }

int CustDepart()//处理客户离开事件，en.NType==(0 — 5) { Qptr tmp; unsigned i = en.NType;

if( !DeQueue( &q[i] ) )//删除排头客户 return 0; TotalTime = TotalTime + en.OccurTime - customer.ArrTime;//累计逗留时间 if( q[i].front != q[i].rear ){ tmp = q[i].front->next; customer = tmp->Cust; en.OccurTime += customer.Duration; if( !OrderInsert(ev, en) ) return 0; }

return 1; }

int DeQueue(LinkQueue *Q)//出队 { Qptr tmp;

if(Q->front==Q->rear) return 0;//如果队列已空，返回0

tmp=Q->front->next; customer=tmp->Cust; Q->front->next=tmp->next; if(Q->rear==tmp)//如果队尾元素被删除，则队尾指针要指向头结点 Q->rear=Q->front;

free(tmp); return 1; }

int EnQueue(LinkQueue *Q, QElem e)//进入队列 { Qptr tmp;

tmp=(Qptr)malloc(sizeof(Qnode)); if(!tmp) return 0;//进栈失败，返回0 tmp->Cust=e; tmp->next=NULL; Q->rear->next=tmp; Q->rear=tmp;

return 1; }

short Minimun()//求长度最短队列 { unsigned h=0, i, j, k;

j=QueueLength(q[0]); for(i=1; i<6; i++){ k = QueueLength(q[i]); if( j > k ){ j = k; h = i; } } return h; }

unsigned QueueLength(LinkQueue Q)//计算队列长度 { unsigned i;

for(i=0; Q.front->next; i++) Q.front=Q.front->next;

return i; }

EventList InitList()//创建链表 { EventList h;

if( !( h=(EventList)malloc(sizeof(Enode)) ) )//创建失败，返回0 return 0;

h->next=NULL; return h; }

int OrderInsert(EventList ev, Event a)//插入事件表 { EventList tmp, h=ev, e=ev->next;

if( !(tmp=InitList()) )//分配空间失败，返回0 return 0; //插入 tmp->event=a; while( e && (a.OccurTime > e->event.OccurTime) ){ h=e; e=e->next; } h->next=tmp; tmp->next=e;

return 1; }

int InitQueue(LinkQueue *Q)//建立空队列 { Q->rear=Q->front=(Qptr)malloc(sizeof(Qnode)); if(!Q->front)//创建失败，返回0 return 0; Q->front->next=NULL; return 1; }

void DelFirst()//删除事件表第一个节点，并把值赋给en { EventList tmp = ev->next;

ev->next = tmp->next; en = tmp->event;

free(tmp); }

二叉树

definition.h ========================================= #define INIT_SIZE 100 //存储空间初始分配量 #define INCREMENT 10 //存储空间分配增量

typedef char TElemType;

typedef struct{ TElemType data; struct BiTNode *lchild, *rchild;//左右孩子指针 }BiTNode, *BiTree;//二叉树的二叉链表存储表示

typedef struct{ BiTree *top, *base; //栈顶指针和栈底指针 unsigned stacksize; //当前已分配的存储空间，以元素为单位 }SqStack;

BiTree CreateBiTree(void);//按先序次序输入二叉树中结点的值，'#'代表空树 void PreOrderTraverse(BiTree);//先序遍历二叉树 int InOrderTraverse(BiTree);//中序遍历二叉树，非递归 int InOrderTraverse2(BiTree); int InitStack(SqStack *);//创建一个空栈 int Push(SqStack *, BiTree); //插入栈顶 ===========================================================================

main.c ================================================ #include <stdio.h> #include "definition.h"

int main() { BiTree bt;

printf("请输入根结点："); bt = CreateBiTree();//按先序次序创建二叉树 PreOrderTraverse(bt); //先序遍历二叉树 printf("\n"); if( InOrderTraverse(bt) )//中序遍历二叉树，非递归 return 1;//遍历失败，返回 printf("\n"); if( InOrderTraverse2(bt) )//中序遍历二叉树，非递归 return 1;//遍历失败，返回 printf("\n");

return 0; } ===================================================================

function.c ====================================================== #include <stdio.h> #include <malloc.h> #include "definition.h"

BiTree CreateBiTree(void)//按先序次序输入二叉树中结点的值，'#'代表空树 { TElemType e; BiTree tmp = NULL;

if( (e=getchar())!='#' ){ getchar();//接收回车符 tmp=(BiTree)malloc(sizeof(BiTNode)); if(!tmp) return NULL; tmp->data=e; printf("请输入左孩子："); tmp->lchild=CreateBiTree(); printf("请输入右孩子："); tmp->rchild=CreateBiTree(); } else getchar();//接收回车符

return tmp; }

void PreOrderTraverse(BiTree bt)//先序遍历二叉树 { if(bt){ printf("%c", bt->data); PreOrderTraverse(bt->lchild); //printf("%c", bt->data);不要上面的printf，而用这个printf，则为中序遍历 PreOrderTraverse(bt->rchild); //printf("%c", bt->data);不要上面的printf，而用这个printf，则为后序遍历 } }

int InOrderTraverse(BiTree bt)//中序遍历二叉树，非递归 { SqStack S; BiTree tmp;

if( InitStack(&S) ) return 1;//如果创建空栈失败，返回1 if( Push(&S, bt) )//根指针进栈 return 1;//如果压栈失败，返回1 while(S.base!=S.top){ while( tmp=*(S.top-1) ){ if( Push(&S, tmp->lchild) )//向左走到尽头 return 1; //printf("%c", tmp->data);//printf放于此处即为先序遍历 } --S.top;//空指针退栈 //访问结点，向右一步 if(S.base!=S.top){ tmp = *(--S.top); printf("%c", tmp->data); if( Push(&S, tmp->rchild) ) return 1; } }

free(S.base); return 0; }

int InOrderTraverse2(BiTree bt) { SqStack S; BiTree tmp = bt;

if( InitStack(&S) ) return 1;//如果创建空栈失败，返回1 while( tmp||(S.base!=S.top) ){ if(tmp){ if( Push(&S, tmp) )//根指针进栈，遍历左子树 return 1; //printf("%c", tmp->data);//printf放于此处即为先序遍历 tmp = tmp->lchild; } //根指针退栈，访问根结点，遍历右子树 else{ tmp = *(--S.top); printf("%c", tmp->data); tmp = tmp->rchild; } }

free(S.base); return 0; }

int InitStack(SqStack *S) //创建一个空栈 { S->base=(BiTree *)malloc( INIT_SIZE * sizeof(BiTree) ); if(!S->base) //空间分配失败 return 1; //空间分配成功 S->top=S->base;//置栈顶指针 S->stacksize=INIT_SIZE;//栈大小 return 0; }

int Push(SqStack *S, BiTree T) //插入栈顶 { if( (unsigned)(S->top - S->base) >= S->stacksize){//栈满，追加存储空间 S->base=(BiTree *)realloc(S->base, (S->stacksize+INCREMENT)*sizeof(BiTree) ); if(!S->base)//分配失败，返回1 return 1; //分配成功 S->top = S->base + S->stacksize;//置栈顶指针 S->stacksize += INCREMENT;//栈大小 } *S->top++ = T;//接收输入后，S->top指向栈顶元素的下一个位置

return 0; }

线索二叉树

definition.h ============================================ typedef char TElemType; typedef enum{Link, Thread} PointerTag;//Link==0：指针；Thread==1：线索

typedef struct{ TElemType data; struct BiThrNode *lchild, *rchild;//左右孩子指针 PointerTag LTag, RTag;//左右标志 }BiThrNode, *BiThrTree;//二叉树的二叉链表存储表示

BiThrTree CreateBiThrTree(void);//按先序次序输入二叉树中结点的值，'#'代表空树 void InOrderTraverse_Thr(BiThrTree);//中序遍历二叉线索树，非递归 BiThrTree InOrderThreading(BiThrTree);//中序线索化二叉线索树 BiThrTree InThreading(BiThrTree, BiThrTree);//中序遍历进行中序线索化 =======================================================================

main.c ==================================================== #include <stdio.h> #include "definition.h"

int main() { BiThrTree bt;

printf("请输入根结点："); bt = CreateBiThrTree();//按先序次序创建二叉树 if( !(bt=InOrderThreading(bt)) )//中序线索化二叉线索树 return 1;//线索化失败 InOrderTraverse_Thr(bt);//中序遍历二叉线索树，非递归 printf("\n");

return 0; } =================================================================

function.c ================================================== #include <stdio.h> #include <malloc.h> #include "definition.h"

BiThrTree CreateBiThrTree(void)//按先序次序输入二叉树中结点的值，'#'代表空树 { TElemType e; BiThrTree tmp = NULL;

if( (e=getchar())!='#' ){ getchar();//接收回车符 tmp=(BiThrTree)malloc(sizeof(BiThrNode)); if(!tmp) return NULL; tmp->data=e; tmp->LTag=tmp->RTag=Link; printf("请输入左孩子："); tmp->lchild=CreateBiThrTree(); printf("请输入右孩子："); tmp->rchild=CreateBiThrTree(); } else getchar();//接收回车符

return tmp; }

BiThrTree InOrderThreading(BiThrTree bt)//中序线索化二叉线索树 { BiThrTree thrt, pre;

if( !( thrt=(BiThrTree)malloc(sizeof(BiThrNode)) ) ) return NULL;//建头结点失败 thrt->LTag=Link; thrt->RTag=Thread; thrt->rchild=thrt;//右指针回指 if(!bt) thrt->lchild=thrt;//若二叉树空，左指针回指 else{ thrt->lchild=bt; pre=thrt; pre=InThreading(bt, pre);//中序遍历进行中序线索化 //最后一个结点线索化 pre->rchild=thrt; pre->RTag=Thread; thrt->rchild=pre; }

return thrt; }

BiThrTree InThreading(BiThrTree bt, BiThrTree pre)//中序遍历进行中序线索化 { if(bt){ pre=InThreading(bt->lchild, pre);//左子树线索化 //前驱线索 if(!bt->lchild){ bt->LTag=Thread; bt->lchild=pre; } //后继线索 if(!pre->rchild){ pre->RTag=Thread; pre->rchild=bt; } pre=bt;//保持pre指向p的前驱 pre=InThreading(bt->rchild, pre);//右子树线索化 }

return pre; }

void InOrderTraverse_Thr(BiThrTree bt)//中序遍历二叉线索树，非递归 { BiThrTree tmp = bt->lchild;

while(tmp != bt){ while(tmp->LTag==Link) tmp=tmp->lchild; printf("%c", tmp->data); while(tmp->RTag==Thread && tmp->rchild!=bt){ tmp=tmp->rchild; printf("%c", tmp->data); } tmp=tmp->rchild; } }

赫夫曼树

definition.h ============================================ typedef struct{ unsigned weight; unsigned parent, lchild, rchild; }HTNode, *HuffmanTree;//动态分配数组存储赫夫曼树

typedef char **HuffmanCode;//动态分配数组存储赫夫曼编码表

void Select(HuffmanTree, unsigned, unsigned *, unsigned *);//选择parent为0，且weight最小的两个结点 ==================================================================

main.c ===================================================== #include <stdio.h> #include <malloc.h> #include <string.h> #include "definition.h"

int main() { unsigned n, m, i, s1, s2, start, c, f; char *cd; HuffmanTree HT, p; HuffmanCode HC;

printf("请问您要输入多少个字符？ "); scanf("%d", &n); if(n<2) return 1; m = 2 * n - 1; HT = (HuffmanTree)malloc( (m + 1) * sizeof(HTNode) );//0号单元未用 if(!HT) return 1; for(p=HT+1, i=1; i<=n; i++, p++){ printf("请您输入权值："); scanf("%d", &p->weight); p->lchild = p->parent = p->rchild = 0; } for(; i<=m; i++, p++) p->lchild = p->parent = p->rchild = p->weight = 0;

//建赫夫曼树 for(i=n+1; i<=m; i++){ s1 = s2 = 0; Select(HT, i, &s1, &s2);//选择parent为0，且weight最小的两个结点 HT[s1].parent = HT[s2].parent = i; HT[i].lchild = s1; HT[i].rchild = s2; HT[i].weight = HT[s1].weight + HT[s2].weight; }

//从叶子到根逆向求每个字符的赫夫曼编码 HC = (HuffmanCode)malloc( (n+1) * sizeof(char *) );//分配n个字符编码的头指针向量 if(!HC) return 1; cd = (char *)malloc( n * sizeof(char) );//分配编码的工作空间 if(!cd) return 1; cd[n-1] = '\0';//编码结束符 for(i=1; i<=n; i++){//逐个字符求赫夫曼编码 start = n - 1;//编码结束位置 for(c=i, f=HT[i].parent; f!=0; c=f, f=HT[f].parent){//从叶子到根逆向求编码 if(HT[f].lchild==c) cd[--start]='0'; else cd[--start]='1'; } HC[i] = (char *)malloc( (n-start)*sizeof(char) );//为第i个字符编码分配空间 if(!HC[i]) return 1; strcpy(HC[i], &cd[start]); printf("%s\n", HC[i]); } free(cd);//释放工作空间

return 0; } //其它动态分配的空间还没释放 ==============================================================================

function.c ================================================================= #include "definition.h"

void Select(HuffmanTree p, unsigned i, unsigned *s1, unsigned *s2) {//选择parent为0，且weight最小的两个结点 unsigned j;

for(j=1; j<i; j++){ if( !p[j].parent ){ if( !*s1 ) *s1 = j; else{ if(p[*s1].weight > p[j].weight){ *s2 = *s1; *s1 = j; } else *s2 = j; } } if( *s1 && *s2 ) break; } for(j++; j<i; j++){ if( !p[j].parent ){ if( p[*s1].weight > p[j].weight ){ *s2 = *s1; *s1 = j; } else{ if( p[*s2].weight > p[j].weight ) *s2 = j; } } } }