• 1. 14.1 栈 4.2 栈的实现 4.3 栈的应用 4.4 队列 4.5 队列的实现 4.6 队列的应用 栈和队列是运算 受限的线性表。第六章 栈与队列
  • 2. 23.1 栈3.1.1 栈的概念及运算 3.1.2 顺序栈 3.1.3 链栈
  • 3. 33.1.1 栈的概念及运算栈 限制仅在一端进行 插入和删除运算的线性 表栈顶 进行插入、删除的 一端栈底栈顶栈底进栈退栈a2a1an...栈是后进先出表( LIFO 表)
  • 4. 4(1)置空栈 createEmptyStack(void):空栈; (2)判栈空 isEmptytack(st):这是一个布尔函数。 若st为空栈,则函数值为“真”, 否则为“假”。 (3)进栈 push(st,x):在st的顶部插入(亦称压入) 元素 x。 (4)退栈 pop(st):删除(亦称弹出)栈st的顶部元素。 (5)取栈顶 top(st):取栈st的顶部元素。栈的五种基本运算3.1.1 栈的概念及运算
  • 5. 53.1.2 顺序栈栈的顺序存储结构简称为顺序栈,它是运算受限 的顺序表。#define MAXNUM 100 /* 栈中能达到的最大容量*/ typedef int DataType; /* 定义栈元素的数据类型* / struct SeqStack /* 顺序栈类型定义 */ { DataType s[MAXNUM]; int t; /*栈顶*/ }; typedef struct SeqStack, *PSeqStack; PSeqStack pastack; /*指向顺序栈的指针变量*/
  • 6. 6注意: t是 int型简单变量 ,指向栈顶元素在栈中的位置(序号)约定:1、栈空时,t=-1 2、栈满时,t=MAXNUM-1 3、栈顶元素:S[t] 4、若t=-1时,执行pop,产生“下溢” 5、若t=MAXNUM-1时,执行push,产生“上溢”
  • 7. 7 6 5 4 3 2 1 0 -1ABCD进栈和退栈3.1.2 顺序栈
  • 8. 83.1.2 顺序栈(1)置空栈 (2)判栈空 (3)进栈 (4)退栈 (5)取栈顶在顺序栈下实现栈的五种基本运算 当程序中同时使用两个栈时, 可共享存储空间。
  • 9. 91. 置空栈(算法4.1)PSeqStack createEmptyStack_seq(void) { PSeqStack pastack; pastack=malloc(sizeof(struct SeqStack)); if(pastack==NULL) printf(“out of space!\n”); else pastack->t= -1; return pastack; } /*SETNULL*/
  • 10. 102. 判栈空(算法4.2)int isEmptyStack_seq(pastack) PSeqStack pastack; { if (pastack->t>=0) return FALSE; else return TRUE; }
  • 11. 113. 进栈(算法4.3)先修改 t 值,再放入数据t++s[t]=x(*pastack).t++(*pastack).s[(*pastack).t]=xpush_seq(pastack,x)
  • 12. 12push_seq(pastack,x) PSeqStack pastack; datatype x; { if (pastack->t==MAXNUM-1) print(“overflow”); else { pastack->t++; pastack->s[pastack->t]=x;} } /* push_seq */3. 进栈(算法4.3)
  • 13. 134. 退栈(算法4.4)pop_seq(pastack)修改 t 值t--pastack->t - -
  • 14. 14pop_seq(pastack) PSeqStack pastack; { if (pastack->t==-1 ) print(“underflow”); else pastack->t--; } /* pop_seq */4. 退栈(算法4.4)
  • 15. 155. 取栈顶元素(算法4.5)datatype top_seq(pastack) PSeqStack pastack; { if (pastack->t==-1 ) { print(“stack is empty”); return NULL; } else return(pastack->s[pastack->t]; } /* top_seq */
  • 16. 16多个栈共享存储空间 … … ...栈1栈2栈1底栈1顶栈2底栈2顶 让多个栈共享存储空间,可以相互调节余缺, 节约存储空间,降低发生上溢的概率。
  • 17. 17多个栈共享存储空间多栈共享:采用链栈Typedef struct { datatype s[MAXNUM]; int top1,top2; }DStack; Push(x,i) Pop(i)
  • 18. 183.1.3 链栈 栈的链式存储结构称为链栈。它是运算受限的 单链表。 由于只能在链表头部进行操作,故链栈没有必 要象单链表那样需附加头结点。栈顶指针top就是 链表的头指针head。
  • 19. 19 typedef int DataType; struct Node; typedef struct Node *pNode; struct Node /* 单链表结点结构 */ { DataType info; pNode link; }; struct LinkStack /* 链接栈类型定义 */ { pNode top; /* 指向栈顶结点 */ }; typedef struct LinkStack *PLinkStack;3.1.3 链栈
  • 20. pLinkstack plstack; /*变量声明*/^ plstacktopinfolink栈的链接表示
  • 21. 213.1.3 链栈 相当于链表在 top 结点前插入出栈相当于链表在将top 结点删除进栈
  • 22. 22void push_link( PLinkStack plstack, DataType x ) /* 在栈中压入一元素x */ { PNode p; p = (PNode)malloc( sizeof( struct Node ) ); if ( p == NULL ) printf("Out of space!\n"); else { p->info = x; p->link = plstack->top; plstack->top = p; } }进栈算法(算法4.8)
  • 23. 23void pop_link( PLinkStack plstack ) { PNode p; if( isEmptyStack_link( plstack ) ) printf( "Empty stack pop.\n" ); else { p = plstack->top; plstack->top = plstack->top->link; free(p); } } 退栈算法(算法4.9)
  • 24. 243.2 栈的应用 栈的应用非常之广,只要问题满足LIFO 原则, 均可使用栈做数据结构。我们先看几个例子。 例3.1 文字编辑器 例3.2 栈与递归 例3.3 数制转换 例3.4 括号匹配的检验 例3.5 表达式求值
  • 25. 25例3.1 设计一个简单的文字编辑器,使其具有删除打 错字符的功能。‘#’ —— 删除前面一个字符 ‘@’ —— 删除前面所有字符 ‘*’ —— 输入结束“abc#d@efg*”我们用栈来实现这种功能的文字编辑器每读入一个字符 退栈置空栈编辑结束
  • 26. 26PSeqStack str; /*顺序栈 str 是全程变量*/ EDIT( ) /*编辑好的字符串在 str 中*/ { char c; str=createEmptyStack(); c=getchar( ); while(c!=‘*’) /*字符‘*’为编辑结束符*/ { if (c==‘#’) POP(str); else if (c==‘@’) str=createEmptyStack(); else PUSH(str,c); c=getchar( ); } } /*EDIT*/例3.1 设计一个简单的文字编辑器,使其具有删除打 错字符的功能。
  • 27. 27 如果一个对象部分的由自己组成,或者是按它自己定义的,则称为递归的。 一个递归定义必须一步比一步简单,最后是有终结的,决不能无限循环下去。在n阶乘的定义中,当n为0时定义为1,它不再用递归来定义,称为递归定义的出口,简称为递归出口。例3.2 栈与递归递归的定义
  • 28. 28例3.2 栈与递归 递归函数的特点:在函数内部可以直接或间接地 调用函数自身。如阶乘函数:n!=1 , n=0n*(n-1)! , n>0
  • 29. 阶乘的递归计算(算法4.11 ) int fact (int n) { if (n = = 0) return 1; else return(n*fact(n-1)); }; r2 main( ) { int n; scanf(“%d\n”,&n); printf(“%8d%8d\n”,n,fact(n)); } r133r12r21r20r21126
  • 30. 30调用前: (1)为被调用函数的局部变量分配存储区; (活动记录, 数据区) (2)将所有的实参、返回地址传递给被调用函数; 实参和形参的结合,传值。 (3)将控制转移到被调用函数入口。 调用后返回: (1)保存被调用函数的计算结果; (2)释放被调用函数的存储区; (3)依照被调用函数保存的返回地址将控制转 移到调用函数。递归函数到非递归函数的转换
  • 31. 函数嵌套调用时,按照“后调用先返回”的原则进行。int main() { int m,n; ... first(m,n); 1: … }int first(int s, int t) { int i; … second(i); 2: … }int second(int d) { int x,y; 3: … }
  • 32. int main() { int m,n; ... { int i; … { int x,y; 3: … } 2: … } 1: … }firstmainsecond函数嵌套结构
  • 33. 算法4.12 阶乘的非递归计算 程序员自己管理一个栈,并模拟函数调用的执行过程。 int nfact(int n); { int res; pSeqStack st; st=createEmptyStack-seq(); while (n>0) while (!isEmptyStack-seq(st) ) { push-seq(st,n); { res=res*top-seq(st); n=n-1; } pop-seq(st); } res=1; free(st); return(res); }阶乘递归算法: int fact (int n) { if (n = = 0) return 1; else return(n*fact(n-1)); };
  • 34. 34例3.3 数制转换 十进制数N和其它d进制数的转换基于下列 原理: N=( N div d ) x d + N mod dN N div 8 mod 81348 168 4168 21 0 21 2 5 2 0 24052
  • 35. 35 程序要求:对于输入的任意一个非负十进制整 数,打印输出与其等值的八进制数。 由于上述计算过程是从低位到高位顺序产生八 进制数的各个数位,而打印输出,一般来说应从高 位到低位进行,恰好与计算过程相反。例3.3 数制转换 因此,若将计算过程中得到的八进制数的各位 顺序进栈,则按出栈序列打印输出的即为与输入对 应的八进制数。
  • 36. 36PSeqStack str; void CONVERSION( ) {str=createEmptyStack(); scanf(“%d”,X); while(X) { PUSH(str,X%8); X=X/8; } while(!EMPTY(str)) { printf(“%d”,TOP(str)); POP(str); } } /*CONVERSION*/例3.3 数制转换
  • 37. 37例3.3 数制转换void CONVERSION(int X ){ If (X/8!=0) conversion(X/8); Printf(“%d”,X%8);}用递归函数实现:用递归编程时,不需要用户自行定义栈。 它是由编译程序加以设立和处理的。
  • 38. 38例3.4 括号匹配的检验 假设表达式中允许三种括号:()、[ ] 和 { }, 其嵌套的顺序随意。 检验括号是否匹配的方法可用“期待的急迫程度” 这个概念来描述。 在算法中设置一个栈,每读入一个括号,若是右括 号,则或者使置于栈顶的最急迫的期待得以消解,或者 是不合法的情况;若是左括号,则作为一个新的更急迫 的期待压入栈中,自然使原有的在栈中的所有未消解的 期待的急迫性都降了一级。[ ( { } [ ] ) ] 1 2 3 4 5 6 7 8
  • 39. 39Judgement() /*判断表达式是否配对,表达式以‘#’结束*/ { PSeqStack sta; char ch,chpop; int valid; SETNULL(&sta); PUSH(&sta,‘#’); /*把’#’放在栈底*/ ch=getchar(); valid=TRUE; /*valid为FALSE表示括号配对失败*/例3.4 括号匹配的检验
  • 40. 40例3.4 括号匹配的检验while(ch!=‘#’) { /*当读入字符为左括号时进栈*/ if ((ch==‘(’)||(ch==‘[’)||(ch==‘{’) ) PUSH(&sta,ch); /*当读入字符为右括号时出栈*/ else if ((ch==‘)’)||(ch==‘]’)||(ch==‘}’)) { chpop=POP(&sta); if (chpop==‘#’) /*右括号多于左括号*/ { valid=FALSE; break;}
  • 41. 41例3.4 括号匹配的检验 if (!((ch==‘)’)&&(chpop==‘(‘) || (ch==‘]’)&&(chpop==‘[‘) || (ch==‘}’)&&(chpop==‘{‘))) { valid==FALSE; break; } }/*else*/ ch=getchar();/*读入下一字符*/ }/*while*/
  • 42. 42if (POP(&sta)!=‘#’ ) valid=FALSE; /*左括号多于右括号*/ if (valid) printf(“括号配对成功“); else printf(“括号配对不成功”); }例3.4 括号匹配的检验
  • 43. 43 表达式求值是程序设计语言编译中的一个最基本 问题。它的实现是栈应用的一个典型例子。下面我们 介绍一种简单直观、广为使用的算法,通常称为“算 符优先法”。例3.5 表达式求值 要把一个表达式翻译成正确求值的机器指令序列, 或者直接对表达式求值,首先要能够正确解释表达式。 算符优先法就是根据算符优先关系的规定来实现对表达 式的编译或解释执行的。
  • 44. 44 任何一个表达式都是由操作数(operand)、运算 符(operator)和界限符组成的,我们称它们为单词。 我们仅讨论简单表达式的求值问题,这种表达式 只含加、减、乘、除、乘方、括号等运算。例3.5 表达式求值 我们把运算符和界限符统称为算符。
  • 45. 45 对于两个相继出现的算符Q1和Q2,其优先关系:例3.5 表达式求值12+ - * / ^ ( ) #+ > > < < < < > > - > > < < < < > > * > > > > < < > > / > > > > < < > > ( < < < < < < = ) > > > > > > # < < < < < < =
  • 46. 46界限符 ‘#’ 优先级别最低设置两个工作栈:运算符栈OPTR 操作数栈OPND算法的基本思想1)首先置操作数栈为空栈,表达式起始符‘#’为运算符 栈的栈底元素。2)依次读入表达式中每个字符,若是操作数则进OPND 栈,若是运算符则和 OPTR 栈的栈顶运算符比较优先权 后作相应操作,直至整个表达式求值完毕。例3.5 表达式求值
  • 47. 输入:3*(7+3*6/2-5#)操作数栈运算符栈3#*(7+3*618/2916-51133
  • 48. 48例3.5 表达式求值datatype evaluate() { PSeqStack optr,opnd; char ch; SETNULL(&optr); PUSH(&optr,’#’); SETNULL(&opnd); ch=getchar(); while(ch!=‘#’||TOP(&optr)!=‘#’) { if (!In(ch,OP)) /*不是运算符则进栈*/ { PUSH((&OPND,ch); ch=getchar(); }
  • 49. 49 else switch(Precede(TOP(&optr),ch) { case -1: /* ‘<‘:栈顶元素优先权低*/ PUSH(&optr,ch); ch=getchar(); break; case 0: /* ‘=’*脱括号并接收下一字符*/ POP(&optr); ch=getchar(); break; 例3.5 表达式求值
  • 50. 50例3.5 表达式求值 case 1: /* ‘>’:退栈并将运算结果入栈*/ theta=POP(&optr); b=POP(&opnd); a=POP(&opnd); PUSH(&opnd,Operate(a,theta,b)); break; } /*switch*/ } /*while*/ return TOP(&opnd); }/*evalate*/
  • 51. 51 若进栈序列为3,5,7,9,进栈过程中可以出栈,则不可能的一个出栈次序是( )。 (a) 7,5,3,9 (b) 9,7,5,3 (c) 7,5,9,3 (d) 9,5,7,3d练习题
  • 52. 52用一维数组设计栈,初态是栈空,top=0。现有输入序列是 a、b、c、d,经过 push、push、pop、push、pop、push操作后,输出序列是( ),栈顶指针是( )b、c2练习题
  • 53. 53对于下面的程序调用过程,请问入栈序列是 ( ),出栈次序是( )。BCDCBD练习题
  • 54. 544.4 队列队列的概念及运算(逻辑结构)
  • 55. 55队列只允许在表的一端进行插入,而在另一端 进行删除。队头允许删除的一端队尾允许插入的一端队列的概念出队入队队头队尾a1 a2 an ... 队列是先进先出表
  • 56. 56队列的基本运算: 创建一个空队列 Queue createEmptyQueue ( void ) 判队列是否为空队列 int isEmptyQueue ( Queue qu ) 往队列中插入一个元素 void enQueue ( Queue qu, DataType x ) 从队列中删除一个元素 void deQueue ( Queue qu ) 求队列头部元素的值 DataType frontQueue ( Queue qu ) 队列的运算
  • 57. 574.5 队列的实现4.5.1. 顺序队列 4.5.2. 链队列
  • 58. 584.5.1 顺序队列 队列的顺序存储结构简称为顺序队列。顺序队 列实际上是运算受限的顺序表。 由于队列的队头和队尾的位置均是变化的,因 而要设置两个指针,分别指示当前队头元素和队尾 元素在向量空间中的位置。
  • 59. 59#define MAXNUM 100 struct SeqQueue { datatype q[MAXNUM]; int f,r; }; typedef struct SeqQueue *PSeqQueue; PSeqQueue sq;顺序队列的定义4.5.1 顺序队列
  • 60. f r76543210k1k2k3frrfk8k7①队列空④队列数组越界顺序队列②约定③队列满k1k2k3fk8rk4k5k6k7
  • 61. 61开始: sq->f=0; sq->r=0; 入队: sq->data[sq->r]=x; sq->r++; 出队: sq->f++; 顺序队列的入队和出队4.5.1 顺序队列
  • 62. 62元素个数(队列长度):(sq->r) - (sq->f) 若(sq->r) - (sq->f)=0 ,则队列长度 为0,即空队列。再出队会“下溢” 若 (sq->r)-(sq->f)=MAXNUM,则队满。 队满时再入队会“上溢”4.5.1 顺序队列
  • 63. 76543210f rk1k2k3frrfk6k5队列空队列数组越界顺序队列
  • 64. 644.5.1 顺序队列假上溢:当前队列并不满,但不能入队。每次出队时向前移一位置。大量移动元素循环队列原因:被删除元素的空间没有再被使用解决:
  • 65. 65采用循环队列克服“假上溢”。 。 。sq->rsq->fMAXNUM-101指针移动方向
  • 66. 66入队:if (sq->r+1>=MAXNUM) sq->r=0; else sq->r++;利用模运算 sq->r=(sq->r+1)%MAXNUM 出队: sq->f=(sq->f+1)%MAXNUM采用循环队列克服“假上溢”4.5.1 顺序队列
  • 67. 67 某一元素出队后,若头指针已从后面追上尾指针, 则当前队列为空: sq->f=sq->r 某一元素入队后,若尾指针已从后面追上头指针, 则当前队列为满: sq->f=sq->r 因此,仅凭 sq->f=sq->r 是无法区别 队列空还是队列满。 判断队空和队满4.5.1 顺序队列
  • 68. 68解决办法标志变量测试尾指针在循环意义 下是否等于头指针 判别队列满的条件: (sq->r+1)%MAXNUM=sq->f 使 sq->f=sq->r 成为判断队列空的条件4.5.1 顺序队列元素个数是MAXNUM-1
  • 69. sq.rearsq.frontk1k2k7k6k5k4k3sq.frontsq.rear图(a) 空队列图(b) 队列满 图4.9 循环队列
  • 70. 704.5.1 顺序队列在循环队列上实现五种基本运算: 1.置空队 2.判队空 3.取队头元素 4.入队 5.出队
  • 71. 711. 置空队PSeqQueue createEmptyQueue_seq( void ) { PSeqQueue sq; sq = (PSeqQueue)malloc(sizeof(struct SeqQueue)); if (sq==NULL) printf("Out of space!! \n"); else { sq->f = 0; sq->r = 0; } return (sq); } 
  • 72. 722. 判队空int isEmptyQueue_seq( PSeqQueue sq ) { return (sq->f == sq->r); }  
  • 73. 733. 取队头元素DataType frontQueue_seq( PSeqQueue sq ) /* 对非空队列,求队列头部元素 */ { return (sq->q[sq->f]); }
  • 74. 744. 入队void enQueue_seq( PSeqQueue sq, DataType x ) /* 在队列中插入一元素x */ { if( (sq->r + 1) % MAXNUM == sq->f ) printf( "Full queue.\n" ); else { sq->q[sq->r] = x; sq->r = (sq->r + 1) % MAXNUM; } } 
  • 75. 755. 出队void deQueue_seq( PSeqQueue sq ) /* 删除队列头部元素 */ { if( sq->f == sq->r ) printf( "Empty Queue.\n" ); else sq->f = (sq->f + 1) % MAXNUM; }  
  • 76. 764.5.2 链队列 队列的链式存储结构简称为链队列,它是限制仅在 表头删除和表尾插入的单链表。 显然仅有单链表的头指针不便于在表尾做插入操作, 为此再增加一个尾指针,指向链表上的最后一个结点。 于是,一个链队列由一个头指针和一个尾指针唯一地确 定。
  • 77. k0 k1 k2 kn-1…. 图4.10 队列的链接表示plqufr
  • 78. 78 struct Node; typedef struct Node *pNode; struct Node { DataType info; pNode link; }; struct LinkQueue { PNode f; PNode r; }; typedef struct LinkQueue, *PLinkQueue;队列的链接表示
  • 79. 79 ^ *plqu头结点plqu->f plqu->r 头结点 队头结点plqu->fplqu->r空和非空的链队列... ^
  • 80. 804.5.2 链队列在链队列上实现的五种基本运算如下: 1. 置空队 2. 判队空 3. 取队头结点数据 4. 入队 5. 出队
  • 81. 811. 置空队(算法4.21)PLinkQueue createEmptyQueue_link( ) { PLinkQueue plqu; plqu = (PLinkQueue )malloc(sizeof(struct LinkQueue)); if (plqu!=NULL) { plqu->f = NULL; plqu->r = NULL; } else printf("Out of space!! \n"); return (plqu); }
  • 82. 822. 判队空(算法4.22)int isEmptyQueue_link( PLinkQueue plqu ) { return (plqu->f == NULL); }  
  • 83. 833. 取队头结点数据(算法4.25)DataType frontQueue_link( PLinkQueue plqu ) /* 在非空队列中求队头元素 */ { return (plqu->f->info); }  
  • 84. 844. 入队(算法4.23)void enQueue_link( PLinkQueue plqu, DataType x ) { PNode p; p = (PNode )malloc( sizeof( struct Node ) ); if ( p == NULL ) printf("Out of space!"); else { p->info = x; p->link = NULL; if (plqu->f == NULL) { plqu->f = p; plqu->r = p; } else { plqu->r->link = p; plqu->r = p; } } } 
  • 85. 855. 出队(算法4.24)void deQueue_link( PLinkQueue plqu ) { PNode p; if( plqu->f == NULL ) printf( "Empty queue.\n " ); else { p = plqu->f; plqu->f = plqu->f->link; free(p); } }
  • 86. 86农夫过河问题 : 一个农夫带着一只狼、一只羊和一棵白菜,身处河的南岸。他要把这些东西全部运到北岸。问题是他面前只有一条小船,船小到只能容下他和一件物品,另外只有农夫能撑船。显然,因为狼能吃羊,而羊爱吃白菜,所以农夫不能留下羊和白菜自己离开,也不能留下狼和羊自己离开。好在狼属于食肉动物,它不吃白菜。请问农夫该采取什么方案才能将所有的东西运过河? 4.6 队列的应用—农夫过河问题*
  • 87. 87 用计算机实现上述求解的搜索过程可以采用两种不同的策略: 一种是广度优先(breadth_first)搜索, 另一种是深度优先(depth_first)。 --实现这两种策略所依赖的数据结构正好是前面介绍的队列和栈。 本节讨论队列的应用,所以下面重点介绍广度优先的策略。 4.6 队列的应用—农夫过河问题*
  • 88. 模拟农夫过河问题:用四位二进制数分别顺序表示农 夫、狼、白菜和羊的位置。 0表示在南岸,1表示在北岸 Path:15,6,14,2,11,1,9,0 从初始状态0到最终状态15的动作序列为:
  • 89. 89队列的应用 --医院门诊部病人管理系统工作过程:当一病人进入门诊室时,负责挂号的义务人员就根据观察和简短询问发给他一个从0(病危)到4(一般)变化的优先数,让他到相应优先数队列中去排队等待 。当一医生空闲时,就根据优先数和等待时间,通知某候诊病人就诊。 原则:优先级高的先考虑,同一优先级中,则先来先考虑。
  • 90. 90队列的应用 --医院门诊部病人管理系统组织数据的方式--数据结构分析: 系统中的数据:病人的姓名,优先数,到达时间
  • 91. 91队列的应用 --医院门诊部病人管理系统组织方式一:若病人以其到达门诊部的先后次序组织到一个队列,则具体到达时间可不考虑。 到达次序优先数姓名 1 2 3 4 5 6 7 2 3 0 3 0 2 1林文 郑江 鲁明 陈真 李军 王红 张兵这样的单队列对按就诊原则来确定下一就诊病人是很不方便的,还将破坏队列的操作原则。
  • 92. 92队列的应用 --医院门诊部病人管理系统组织方式二:多个队列(队列数组):队列数组的第i个元素是优先级为i的队列。优先数隐含在队列的编号中。 鲁明0 1 2 3 4李军张兵林文王红郑江陈真^^^^^
  • 93. 93队列的应用 --医院门诊部病人管理系统就病人管理系统来说,功能菜单中至少有以下两个功能: (1)病人登记AddPatient( ) ①提示并读入病人优先数i; ②提示并读入病人名 ③调用链队列的入队算法EnQueue() (2)确定下一个就诊病人 GetPatient( ) 按就诊原则确定和显示下一个就诊病人名 即:若优先数0的队列非空,则下一就诊病人为队首元素,否则,考虑优先数1的队列;依次类推。
  • 94. 94线 性 表存储结构 运 算 队列 链 表顺序表 栈 顺序栈 链 栈 顺序队列 链队列 线性表小结
  • 95. 95顺序表typedef int datatype ;#define MAXNUM 1024typedef struct{ datatype data[MAXNUM] ;int last ;} sequenlist;
  • 96. 96链 表typedef int datatype;typedef struct node{ datatype data;struct node *next;} linklist;linklist *head, *p;
  • 97. 97 顺序栈 typedef int datatype; #define MAXNUM 64 typedef struct { datatype data[MAXNUM]; int top; } PSeqStack; PSeqStack *s;
  • 98. 98 链 栈 typedef int datatype; typedef struct node { datatype data; struct node *next; } linkstack; linkstack *top;
  • 99. 99 顺序队列 typedef struct { datatype data[MAXNUM]; int f,r; } sequeue; sequeue *sq;
  • 100. 100 链队列 typedef struct { linklist *f , *r; } linkqueue; linkqueue *q;
  • 101. 1012.6 设计一算法,逆置带头结点的动态单链表 L。void reverse(linklist *L) /*假设链表带有头结点*/ { linklist *p,*s; p=L->next; /*用p指向当前结点*/ L->next=NULL; while (p) { s=p; /*用s保存当前结点地址*/ p=p->next; /*链表指针p后移*/ /*将当前结点链到表头*/ s->next=L->next; L->next=s; } } /*reverse*/
  • 102. 1022.10 已知,由单链表表示的线性表中,含有三类字符的数据元素 (如:字母字符、数字字符和其它字符),试编写算法构造三个以 循环链表表示的线性表,使每个表中只含同一类的字符,且利用原 表中的结点空间作为这三个表的结点空间,头结点可另辟空间。linklist *ra,*rb,*rc; void sort(linklist *head) { linklist *s,*p=head; /*建立三个空的循环链表*/ ra=malloc(sizeof(linklist)); ra->next=ra; rb=malloc(sizeof(linklist)); rb->next=rb; rc=malloc(sizeof(linklist)); rc->next=ra;
  • 103. 103 while (p) { s=p; p=p->next; if ((s->data>=‘0’)&&(s->data<=‘9’)) { s->next=ra->next; ra->next=s; ra=s; } /*将数字字符结点链接到A表*/ else if ((s->data>=‘a’)&&(s->data<=‘z’) ||(s->data>=‘A’)&&(s->data<=‘Z’)) { s->next=rb->next; rb->next=s; rb=s; } /*将字母字符结点链接到B表*/ else { s->next=rc->next; rc->next=s; rc=s; } /*将其它字符结点链接到C表*/ } /*while*/ } /*sort*/
  • 104. 1043.3 设单链表中存放着n个字符,试编写算法,判断该字 符串是否有中心对称关系。要求用尽可能少的时间完成。int Judgement1(linklist *head) /*若对称返回 1,否则返回 0*/ { PSeqStack *s; linklist *p; int i, n=0; /*n为计数器,记录链表的长度*/ p=head; /*先用循环求出链表的长度*/ while(p) { n++ ; p=p->next ; }
  • 105. 1053.3 设单链表中存放着n个字符,试编写算法,判断该字 符串是否有中心对称关系。要求用尽可能少的时间完成。SETNULL(s); /*设置空栈 s*/ p=head; /*先将一半字符进栈* for (i=1;i<=n/2;i++ ) { PUSH(s,p->data); p=p->next; } /*若字符个数为基数,则跳过中间的字符* if (n%2) p=p->next;
  • 106. 1063.3 设单链表中存放着n个字符,试编写算法,判断该字 符串是否有中心对称关系。要求用尽可能少的时间完成。 /*当字符串未扫描完毕且栈非空时进行匹配*/ while(p&&!EMPTY(s)) if (p->data!=POP(s) break; else p=p->next; if (! p&&EMPTY(s)) return 1; else return 0; }/*Judgement*/
  • 107. 1073.4 设计算法判断一个算术表达式的圆括号是否正确配对Judgement2() /*判断表达式是否配对,表达式以‘#’结束*/ { PSeqStack sta; char ch,chpop; int valid; SETNULL(&sta); PUSH(&sta,‘#’); /*把’#’放在栈底*/ ch=getchar(); valid=TRUE; /*valid为FALSE表示括号配对失败*/
  • 108. 108 while(ch!=‘#’) { if (ch==‘(’) /*读入字符为左括号时进栈*/ PUSH(&sta,ch); else if (ch==‘)’)/*读入字符为右括号时出栈*/ { chpop=POP(&sta); if (chpop==‘#’) /*右括号多于左括号*/ { valid=FALSE; break;} } /*else*/ ch=getchar();/*读入下一字符*/ }/*while*/ 3.4 设计算法判断一个算术表达式的圆括号是否正确配对
  • 109. 109if (POP(&sta)!=‘#’ ) valid=FALSE; /*左括号多于右括号*/ if (valid) printf(“括号配对成功“); else printf(“括号配对不成功”); } /*Judgement2*/3.4 设计算法判断一个算术表达式的圆括号是否正确配对
  • 110. 1103.8 对于循环向量中的循环队列,写出求队列长度的公式0MAXNUM-1rf…q->rearq->f: length=q->r-q->f;0MAXNUM-1rf……q->rf: length= MAXNUM- (sq->f-sq->r);
  • 111. 1113.9 假设以数组sequ[m]存放循环队列的元素,同时设变量rear和quelen 分别指示循环队列中队尾元素的位置和内含元素的个数。试给出判断 此循环队列的队满条件,并写出相应的入队列和出队列的算法。 根据题意,定义顺序队列的结构: typedef struct { datatype data[MAXNUM]; int f, r, seqlen; } sequeue;这样,循环队列满的条件为: seqlen=MAXNUM;
  • 112. 1123.9 假设以数组sequ[m]存放循环队列的元素,同时设变量rear和quelen 分别指示循环队列中队尾元素的位置和内含元素的个数。试给出判断 此循环队列的队满条件,并写出相应的入队列和出队列的算法。int ENQUEUD(sq, x) /*将新元素x插入到队列的队尾*/ sequeue *sq; datatype x; { if sq->quelen==MAXNUM /*队满上溢*/ { printf(“queue is full”); return NULL; } else { sq->r=(sq->r+1)%MAXNUM; sq->data[sq->r]=x; return TURE; } } /*ENQUEUE;*/
  • 113. 1133.9 假设以数组sequ[m]存放循环队列的元素,同时设变量rear和quelen 分别指示循环队列中队尾元素的位置和内含元素的个数。试给出判断 此循环队列的队满条件,并写出相应的入队列和出队列的算法。datatype DEQUEUD(sq) /*删除队头元素并返回*/ sequeue *sq; datatype x; { int f; if (EMPTY(sq)) /*队空下溢*/ { printf(“queue is empty”); return NULL; } else { sq->seqlen--; f= (MAXNUM+sq->r-seq->seqlen)%MAXNUM; return(sq->data[f]); } } /*ENQUEUE;*/