《栈与队列》PPT课件

1、1 4.1 栈 4.2 栈的实现 4.3 栈的应用 4.4 队列 4.5 队列的实现 4.6 队列的应用 栈和队列是运算 受限的线性表。 第四章 栈与队列 2 3.1 栈 3.1.1 栈的概念及运算 3.1.2 顺序栈 3.1.3 链栈 3 3.1.1 栈的概念及运算 栈 限制仅在一端进行 插入和删除运算的线性 表 栈顶 进行插入、删除的 一端 栈底 栈顶 栈底 进栈退栈 a2 a1 an . 栈是后进先出表（ LIFO 表） 4 （1）置空栈 createEmptyStack(void)：空栈； （2）判栈空 isEmptytack（st）：这是一个布尔函数。 若st为空栈，则函数值为“真”

2、, 否则为“假”。 （3）进栈 push（st，x）：在st的顶部插入(亦称压入） 元素 x。 （4）退栈 pop（st）：删除（亦称弹出）栈st的顶部元素。 （5）取栈顶 top（st）：取栈st的顶部元素。 栈的五种基本运算 3.1.1 栈的概念及运算 5 3.1.2 顺序栈 栈的顺序存储结构简称为顺序栈，它是运算受限 的顺序表。 #define MAXNUM 100 /* 栈中能达到的最大容量*/ typedef int DataType; /* 定义栈元素的数据类型* / struct SeqStack /* 顺序栈类型定义 */ DataType sMAXNUM; int t; /*

3、栈顶*/ ； typedef struct SeqStack, *PSeqStack; PSeqStack pastack; /*指向顺序栈的指针变量*/ 6 t是是 int型简单变量型简单变量 ,指向栈顶元素在栈指向栈顶元素在栈 中的位置中的位置(序号序号) 约定: 1、栈空时，t=-1 2、栈满时，t=MAXNUM-1 3、栈顶元素：St 4、若t=-1时，执行pop,产生“下溢” 5、若t=MAXNUM-1时，执行push,产生“上溢 ” 7 6 5 4 3 2 1 0 -1 A B C D 进栈和退栈 3.1.2 顺序栈 8 3.1.2 顺序栈 （1）置空栈 （2）判栈空 （3）进栈

4、（4）退栈 （5）取栈顶 在顺序栈下实现栈的五种基本运算 当程序中同时使用两个栈时， 可共享存储空间。 9 1. 置空栈（算法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 2. 判栈空（算法4.2） int isEmptyStack_seq(pastack

5、) PSeqStack pastack; if (pastack-t=0) return FALSE; else return TRUE; 11 3. 进栈（算法4.3） 先修改 t 值，再放入数据 t+st=x (*pastack).t+ (*pastack).s(*pastack).t=x push_seq(pastack,x) 12 push_seqpush_seq(pastack,x)(pastack,x) PSeqStack pastack; datatype x;PSeqStack pastack; datatype x; if (pastack-t=MAXNUM-1) if (p

6、astack-t=MAXNUM-1) print( print(“overflowoverflow”);); else else pastack-t+; pastack-t+; pastack-spastack-t=x; pastack-spastack-t=x; / /* * push_seqpush_seq * */ / 3. 进栈（算法4.3） 13 4. 退栈（算法4.4） pop_seq(pastack) 修改 t 值 t- pastack-t - - 14 pop_seqpop_seq(pastack)(pastack) PSeqStack pastack;PSeqStack pa

7、stack; if (pastack-t=-1 ) if (pastack-t=-1 ) print( print(“underflowunderflow”); ); else else pastack-t-; pastack-t-; / /* * pop_seqpop_seq * */ / 4. 退栈（算法4.4） 15 5. 取栈顶元素（算法4.5） datatype top_seq(pastack) PSeqStack pastack; if (pastack-t=-1 ) print(“stack is empty”); return NULL; else return(pastack

8、-spastack-t; /* top_seq */ 16 多个栈共享存储空间 . 栈1 栈2 栈1底 栈1顶栈2底栈2顶 让多个栈共享存储空间，可以相互调节余缺， 节约存储空间，降低发生上溢的概率。 17 多个栈共享存储空间 多栈共享：采用链栈 Typedef struct datatype sMAXNUM; int top1,top2; DStack; Push(x,i) Pop(i) 18 3.1.3 链栈 栈的链式存储结构称为链栈。它是运算受限的 单链表。 由于只能在链表头部进行操作，故链栈没有必 要象单链表那样需附加头结点。栈顶指针top就是 链表的头指针head。 19 typed

9、ef 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 链栈 pLinkstack plstack; /*变量声明*/ plstac k topinfolink 栈的链接表示 21 3.1.3 链栈 相当于链表在 top 结点前插入

10、 出栈相当于链表在将top 结点删除 进栈 22 void 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 void pop_link( PLinkStack plstack ) PNode p; i

11、f( isEmptyStack_link( plstack ) ) printf( Empty stack pop.n ); else p = plstack-top; plstack-top = plstack-top-link; free(p); 退栈算法（算法4.9） 24 3.2 栈的应用 栈的应用非常之广，只要问题满足LIFO 原则， 均可使用栈做数据结构。我们先看几个例子。 例3.1 文字编辑器 例3.2 栈与递归 例3.3 数制转换 例3.4 括号匹配的检验 例3.5 表达式求值 25 例3.1 设计一个简单的文字编辑器，使其具有删除打 错字符的功能。 # 删除前面一个字符 删除

12、前面所有字符 * 输入结束 “abc#defg*” 我们用栈来实现这种功能的文字编辑器 每读入一个字符 退栈 置空栈 编辑结束 26 PSeqStack 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

13、 设计一个简单的文字编辑器，使其具有删除打 错字符的功能。 27 如果一个对象部分的由自己组成，或 者是按它自己定义的，则称为递归的。 一个递归定义必须一步比一步简单， 最后是有终结的，决不能无限循环下去。在 n阶乘的定义中，当n为0时定义为1，它不再 用递归来定义，称为递归定义的出口，简称 为递归出口。 例3.2 栈与递归 递归的定义 28 例3.2 栈与递归 递归函数的特点：在函数内部可以直接或间接地 调用函数自身。如阶乘函数： n!= 1 , n=0 n*(n-1)! , n0 阶乘的递归计算（算法4.11 ） int fact (int n) if (n = = 0) return 1

14、; else return(n*fact(n-1); ; r2 main( ) int n; scanf(“%dn”, printf(“%8d%8dn”,n,fact(n); r1 3 3 r1 2 r2 1 r2 0 r2 1 1 2 6 30 调用前： （1）为被调用函数的局部变量分配存储区； （活动记录， 数据区） （2）将所有的实参、返回地址传递给被调用函数； 实参和形参的结合，传值。 （3）将控制转移到被调用函数入口。 调用后返回： （1）保存被调用函数的计算结果； （2）释放被调用函数的存储区； （3）依照被调用函数保存的返回地址将控制转 移到调用函数。 函数嵌套调用时，按照“后调

15、用先返回”的原则进行。 int main() int m,n; . first(m,n); 1: int first(int s, int t) int i; second(i); 2: int second(int d) intx,y; 3: int main() int m,n; . int i; int x,y; 3: 2: 1: first main second 算法4.12 阶乘的非递归计算 程序员自己管理一个栈，并模拟函数调用的执行过程。 int nfact(int n); int res; pSeqStack st; st=createEmptyStack-seq(); whi

16、le (n0) 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 例3.3 数制转换 十进制数N和其它d进制数的转换基于下列 原理： N=( N div d ) x d + N mod d N N div 8 mod 8 1348 168 4 168 21

17、 0 21 2 5 2 0 2 4 0 5 2 35 程序要求：对于输入的任意一个非负十进制整 数，打印输出与其等值的八进制数。 由于上述计算过程是从低位到高位顺序产生八 进制数的各个数位，而打印输出，一般来说应从高 位到低位进行，恰好与计算过程相反。 例3.3 数制转换 因此，若将计算过程中得到的八进制数的各位 顺序进栈，则按出栈序列打印输出的即为与输入对 应的八进制数。 36 PSeqStack str; void CONVERSION( ) str=createEmptyStack(); scanf(“%d”,X); while(X) PUSH(str,X%8); X=X/8; whil

18、e(!EMPTY(str) printf(“%d”,TOP(str); POP(str); /*CONVERSION*/ 例3.3 数制转换 37 void CONVERSION(int X )void CONVERSION(int X ) If (X/8!=0)If (X/8!=0) conversion(X/8); conversion(X/8); Printf(Printf(“%d%d”,X%8);,X%8); 用递归函数实现： 用递归编程时，不需要用户自行定义栈。 它是由编译程序加以设立和处理的。 38 例3.4 括号匹配的检验 假设表达式中允许三种括号：（）、 和 ， 其嵌套的顺序随

19、意。 检验括号是否匹配的方法可用“期待的急迫程度” 这个概念来描述。 在算法中设置一个栈，每读入一个括号，若是右括 号，则或者使置于栈顶的最急迫的期待得以消解，或者 是不合法的情况；若是左括号，则作为一个新的更急迫 的期待压入栈中，自然使原有的在栈中的所有未消解的 期待的急迫性都降了一级。 （ ） 1 2 3 4 5 6 7 8 39 Judgement() /*判断表达式是否配对，表达式以#结束*/ PSeqStack sta; char ch,chpop; int valid; SETNULL( PUSH( /*把#放在栈底*/ ch=getchar(); valid=TRUE; /*va

20、lid为FALSE表示括号配对失败*/ 例3.4 括号匹配的检验 40 例3.4 括号匹配的检验 while(ch!=#) /*当读入字符为左括号时进栈*/ if (ch=()|(ch=)|(ch=) ) PUSH（ if (chpop=#) /*右括号多于左括号*/ valid=FALSE; break; 41 例3.4 括号匹配的检验 if (!(ch=) break; /*else*/ ch=getchar();/*读入下一字符*/ /*while*/ 42 if (POP( /*左括号多于右括号*/ if (valid) printf(“括号配对成功“）； else printf(“括

21、号配对不成功”）； 例3.4 括号匹配的检验 43 表达式求值是程序设计语言编译中的一个最基本 问题。它的实现是栈应用的一个典型例子。下面我们 介绍一种简单直观、广为使用的算法，通常称为“算 符优先法”。 例3.5 表达式求值 要把一个表达式翻译成正确求值的机器指令序列， 或者直接对表达式求值，首先要能够正确解释表达式。 算符优先法就是根据算符优先关系的规定来实现对表达 式的编译或解释执行的。 44 任何一个表达式都是由操作数（operand）、运算 符（operator）和界限符组成的，我们称它们为单词。 我们仅讨论简单表达式的求值问题，这种表达式 只含加、减、乘、除、乘方、括号等运算。 例

22、3.5 表达式求值 我们把运算符和界限符统称为算符。 45 对于两个相继出现的算符Q1和Q2，其优先关系： 例3.5 表达式求值 1 2 + - * / ( ) # + - * / ( # = 46 界限符 # 优先级别最低 设置两个工作栈：运算符栈OPTR 操作数栈OPND 算法的基本思想 1）首先置操作数栈为空栈，表达式起始符#为运算符 栈的栈底元素。 2）依次读入表达式中每个字符，若是操作数则进OPND 栈，若是运算符则和 OPTR 栈的栈顶运算符比较优先权 后作相应操作，直至整个表达式求值完毕。 例3.5 表达式求值 输入： 3 * （7 + 3 * 6 / 2-5#) 操作数栈 运算

23、符栈 3# * ( 7 + 3 * 6 18 / 2 9 16 - 5 11 33 48 例3.5 表达式求值 datatype evaluate() PSeqStack optr,opnd; char ch; SETNULL( PUSH( SETNULL( ch=getchar(); while(ch!=#|TOP( ch=getchar(); 49 else switch(Precede(TOP( b=POP( a=POP( PUSH( break; /*switch*/ /*while*/ return TOP( /*evalate*/ 51 若进栈序列为3，5，7，9，进栈过程中可以出

24、栈，则不可能的 一个出栈次序是（ ）。 (a) 7,5,3,9 (b) 9,7,5,3 (c) 7,5,9,3 (d) 9,5,7,3 d 52 用一维数组设计栈，初态是栈空，top=0。现 有输入序列是 a、b、c、d，经过 push、 push、pop、push、pop、push操作后，输 出序列是（ ），栈顶指针是 （ ） b、c2 练习题 53 对于下面的程序调用过程，请问入栈序列是 （ ），出栈次序是（ ）。 BCDCBD 练习题 54 4.4 队列 队列的概念及运算(逻辑结构) 55 队列只允许在表的一端进行插入，而在另一端 进行删除。 队头允许删除的一端 队尾允许插入的一端 队列

25、的概念 出队入队 队头队尾 a1 a2 an . 队列是先进先出表 56 队列的基本运算： 创建一个空队列 Queue createEmptyQueue ( void ) 判队列是否为空队列 int isEmptyQueue ( Queue qu ) 往队列中插入一个元素 void enQueue ( Queue qu, DataType x ) 从队列中删除一个元素 void deQueue ( Queue qu ) 求队列头部元素的值 DataType frontQueue ( Queue qu ) 队列的运算 57 4.5.1. 顺序队列 4.5.2. 链队列 58 4.5.1 顺序队列

26、 队列的顺序存储结构简称为顺序队列。顺序队 列实际上是运算受限的顺序表。 由于队列的队头和队尾的位置均是变化的，因 而要设置两个指针，分别指示当前队头元素和队尾 元素在向量空间中的位置。 59 #define MAXNUM 100 struct SeqQueue datatype qMAXNUM; int f,r; ; typedef struct SeqQueue *PSeqQueue; PSeqQueue sq; 顺序队列的定义 4.5.1 顺序队列 f r 7 6 5 4 3 2 1 0 k1 k2 k3 f r r f k8 k7 队列空 队列数组越界约定队列满 k1 k2 k3 f

27、k8 r k4 k5 k6 k7 61 开始： sq-f=0; sq-r=0; 入队： sq-datasq-r=x; sq-r+; 出队： sq-f+; 顺序队列的入队和出队 4.5.1 顺序队列 62 元素个数（队列长度）:（sq-r) - (sq-f) 若（sq-r) - (sq-f)=0 ，则队列长度 为0，即空队列。再出队会“下溢” 若 (sq-r)-(sq-f)=MAXNUM，则队满。 队满时再入队会“上溢” 4.5.1 顺序队列 7 6 5 4 3 2 1 0 f r k1 k2 k3 f r r f k6 k5 队列空队列数组越界 64 4.5.1 顺序队列 假上溢：当前队列并不

28、满，但不能入队。 每次出队时向前移一位置。 大量移动元素 循环队列 原因:被删除元素的空间没有再被使用 解决: 65 采用循环队列克服“假上溢” 。 。 。 sq-r sq-f MAXNUM-1 0 1 指针移动方向 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 某一元素出队后，若头指针已从后面追上尾指针， 则当前队列为空： sq-f=sq-r 某一元素入队后，若尾指针已从后面追上头指针， 则

29、当前队列为满： sq-f=sq-r 因此，仅凭 sq-f=sq-r 是无法区别 队列空还是队列满。 判断队空和队满 4.5.1 顺序队列 68 解决办法 标志变量 测试尾指针在循环意义 下是否等于头指针 判别队列满的条件： (sq-r+1)%MAXNUM=sq-f 使 sq-f=sq-r 成为判断队列空的条件 4.5.1 顺序队列 元素个数是MAXNUM-1 sq.rear sq.front k1 k2 k7 k6k5 k4 k3 sq.front sq.rear 图(a)空队列 图(b)队列满 图4.9 循环队列 70 4.5.1 顺序队列 在循环队列上实现五种基本运算： 1.置空队 2.判

30、队空 3.取队头元素 4.入队 5.出队 71 1. 置空队 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 2. 判队空 int isEmptyQueue_seq( PSeqQueue sq ) return (sq-f = sq-r); 73 3. 取队头元素 DataType fr

31、ontQueue_seq( PSeqQueue sq ) /* 对非空队列,求队列头部元素 */ return (sq-qsq-f); 74 4. 入队 void enQueue_seq( PSeqQueue sq, DataType x ) /* 在队列中插入一元素x */ if( (sq-r + 1) % MAXNUM = sq-f ) printf( Full queue.n ); else sq-qsq-r = x; sq-r = (sq-r + 1) % MAXNUM; 75 5. 出队 void deQueue_seq( PSeqQueue sq ) /* 删除队列头部元素 */

32、if( sq-f = sq-r ) printf( Empty Queue.n ); else sq-f = (sq-f + 1) % MAXNUM; 76 4.5.2 链队列 队列的链式存储结构简称为链队列，它是限制仅在 表头删除和表尾插入的单链表。 显然仅有单链表的头指针不便于在表尾做插入操作， 为此再增加一个尾指针，指向链表上的最后一个结点。 于是，一个链队列由一个头指针和一个尾指针唯一地确 定。 k0 k1 k2 kn-1. 图4.10 队列的链接表 示 plqu f r 78 struct Node; typedef struct Node *pNode; struct Node D

33、ataType info; pNodelink; ; struct LinkQueue PNodef; PNoder; ; typedef struct LinkQueue, *PLinkQueue; 队列的链接表示 79 *plqu头结点 plqu-f plqu-r 头结点 队头结点 plqu-f plqu-r 空和非空的链队列 . 80 4.5.2 链队列 在链队列上实现的五种基本运算如下： 1. 置空队 2. 判队空 3. 取队头结点数据 4. 入队 5. 出队 81 1. 置空队（算法4.21） PLinkQueue createEmptyQueue_link( ) PLinkQueu

34、e 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 2. 判队空（算法4.22） int isEmptyQueue_link( PLinkQueue plqu ) return (plqu-f = NULL); 83 3. 取队头结点数据（算法4.25） DataType frontQueue_link( PLinkQueue plqu )

35、 /* 在非空队列中求队头元素 */ return (plqu-f-info); 84 4. 入队（算法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; plq

36、u-r = p; 85 5. 出队（算法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 农夫过河问题 : 一个农夫带着一只狼、一只羊和一棵白菜， 身处河的南岸。他要把这些东西全部运到北岸。 问题是他面前只有一条小船，船小到只能容下 他和一件物品，另外只有农夫能撑船。显然， 因为狼能吃羊，而羊爱吃白菜，所以农夫不能 留下羊和白菜自己离开，也不能留下狼和

37、羊自 己离开。好在狼属于食肉动物，它不吃白菜。 请问农夫该采取什么方案才能将所有的东西运 过河? 4.6 队列的应用农夫过河问题* 87 用计算机实现上述求解的搜索过程可以采用两 种不同的策略： 一种是广度优先(breadth_first)搜索， 另一种是深度优先(depth_first)。 实现这两种策略所依赖的数据结构正好是前面 介绍的队列和栈。 本节讨论队列的应用，所以下面重点介绍广度优先 的策略。 4.6 队列的应用农夫过河问题* 模拟农夫过河问题：用四位二进制数分别顺序表示农 夫、狼、白菜和羊的位置。 0表示在南岸，1表示在北岸 Path：15，6，14，2，11，1，9，0 从初始

38、状态0到最终状态15的动作序列为： 农夫把羊带到北岸; 1 0000 农夫独自回到南岸; 2 1001 农夫把白菜带到北岸; 3 0001 农夫带着羊返回南岸; 5 1101 4 1011 农夫把狼带到北岸; 7 0100 6 0010 农夫独自返回南岸; 8 1110 农夫把羊带到北岸。 9 0110 10 1111 图4.11 广度优先搜索的结果和顺序 89 l工作过程：当一病人进入门诊室时，负责挂号 的义务人员就根据观察和简短询问发给他一个 从0（病危）到4（一般）变化的优先数，让他 到相应优先数队列中去排队等待 。当一医生空 闲时，就根据优先数和等待时间，通知某候诊 病人就诊。 l原则

39、：优先级高的先考虑，同一优先级中，则 先来先考虑。 90 l组织数据的方式数据结构 分析： 系统中的数据：病人的姓名，优先数，到达时间 91 4组织方式一：若病人以其到达门诊部的先后次序组织到一个队列，则具体 到达时间可不考虑。 到达次序优先数 姓名 1 2 3 4 5 6 7 2 3 0 3 0 2 1 林文 郑江 鲁明 陈真 李军 王红 张兵 这样的单队列对按就诊原则 来确定下一就诊病人是很不 方便的，还将破坏队列的操 作原则。 92 4组织方式二：多个队列（队列数组）：队列数组的第i个元素是优先级为i的队 列。优先数隐含在队列的编号中。 鲁明 0 1 2 3 4 李军 张兵 林文王红 郑

40、江陈真 93 就病人管理系统来说，功能菜单中至少有以下两个功能：（1）病人 登记AddPatient( ) 提示并读入病人优先数i； 提示并读入病人名 调用链队列的入队算法EnQueue() （2）确定下一个就诊病人 GetPatient( ) 按就诊原则确定和显示下一个就诊病人名 即：若优先数0的队列非空，则下一就诊病人为队首元素，否则，考虑 优先数1的队列；依次类推。 94 线 性 表 存储结构 运 算 队列 链 表 顺序表 栈 顺序栈 链 栈 顺序队列 链队列 线性表小结 95 顺序表 typedef int datatype ; #define MAXNUM 1024 typedef

41、struct datatype dataMAXNUM ; int last ; sequenlist; 96 链 表 typedef int datatype; typedef struct node datatype data; struct node *next; linklist; linklist *head, *p; 97 顺序栈 typedef int datatype; #define MAXNUM 64 typedef struct datatype dataMAXNUM; int top; PSeqStack; PSeqStack *s; 98 链 栈 typedef int

42、 datatype; typedef struct node datatype data; struct node *next; linkstack; linkstack *top; 99 顺序队列 typedef struct datatype dataMAXNUM; int f,r; sequeue; sequeue *sq; 100 链队列 typedef struct linklist *f , *r; linkqueue; linkqueue *q; 101 2.6 设计一算法，逆置带头结点的动态单链表 L。 void reverse(linklist *L) /*假设链表带有头结点

43、*/ 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 2.10 已知，由单链表表示的线性表中，含有三类字符的数据元素 （如：字母字符、数字字符和其它字符），试编写算法构造三个以 循环链表表示的线性表，使每个表中只含同一类的字符，且利用原 表中的结点空间作为这三个表的结点空间，头结点可另辟空间。 linklist *ra,*rb,

44、*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 while (p) s=p; p=p-next; if (s-data=0) ra-next=s; ra=s; /*将数字字符结点链接到A表*/ else if (s-data=a) rb-next=s; rb=s;

45、/*将字母字符结点链接到B表*/ else s-next=rc-next; rc-next=s; rc=s; /*将其它字符结点链接到C表*/ /*while*/ /*sort*/ 104 3.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 3.3 设单链表中存放着n个字符，试编写算法，判断该字 符串是否有中心对称关系。要求用尽可能少的时间完成。 SETNULL(s); /*设置空栈 s*/ p=head; /*先将一半字符进栈* for (i=1;idata); p=p-next; /*若字符个数为基数，则跳过中间的字符* if (n%2) p=p-next; 106 3.3 设单链表中存放着n个字符，试编写算法，判断该字 符串是否有中心对称关系。要