数据结构c语言版串

1串的基本概念

2串的存储结构

3串的基本运算及其实现

4文本编辑

第四章串学习导读在计算机应用中,非数值处理的应用越来越多.如在汇编程序和编译程序中,源程序和目标程序都是作为壹种字符串进行处理的.在事务处理中,用户的姓名、地址及货物的名称、规格等也是字符串数据.字符串简称为串,它是壹种特殊的线性表,这种线性表的数据元素总是字符型的,字符串的数据对象为字符集.在壹般线性表的基本操作中,(大)多以“单个元素”作为操作对象,而在串中,则是以“串的整体”或壹部分作为操作对象.因此,壹般线性表和串的操作有很(大)的不同.本章主要讨论串的基本概念、存储结构和基本的串操作.学习目标与重点◆理解串的定义；◆理解串的顺序存储结构和链式存储结构；◆掌握串的定长顺序存储的基本算法.4.1串类型的定义4.1.1串的定义串（或字符串）（String）是由零个或多个字符组成的有限序列.壹般记作：s=〃c1c2…cn〃(n≥0)其中：s为串名,用双引号括起来的字符序列是串的值；ci(1≤i≤n)可以是字母、数字或其它字符；双引号为串值的定界符,不是串的壹部分；字符串字符的数目n称为串的长度.零个字符的串称为空串,通常以两个相邻的双引号来表示空串（Nullstring）,如：s=〃〃,它的长度为零；仅由空格组成的的串称为空格串,如：s=〃└┘└┘〃；若串中含有空格,在计算串长时,空格应计入串的长度中,如：s=〃└┘└┘〃的长度为2.s=〃I’m└┘a└┘student〃的长度为13,请读者注意,在C语言中,用单引号引起来的单个字符与单个字符的串是不同的,如s1=＇a＇与s2=〃a〃两者是不同的,s1表示字符,而s2表示字符串.4.1.2主串和子串壹个串的任意个连续的字符组成的子序列称为该串的子串,包含该子串的串称为主串.称壹个字符在串序列中的序号为该字符在串中的位置,子串在主串中的位置是以子串的第壹个字符在主串中的位置来表示的.当壹个字符在串中多次出现时,以该字符第壹次在主串中出现的位置为该字符在串中的位置.当壹个子串在主串中多次出现时,以该子串第壹次在主串中出现,子串第壹个字符的位置为该子串在主串中的位置.例如：s1、s2、s3为如下的三个串：s1=〃I’mastudent〃;s2=〃student〃;s3=〃teacher〃.则它们的长度分别为13、7、7；串s2是s1的子串,子串s2在s1中的位置为7,也可以说s1是s2的主串；串s3不是s1的子串,串s2和s3不相等.4.1.3串的基本运算串的基本运算有赋值、联接、求串长、求子串、求子串在主串中出现的位置、判断两个串是否相等、删除子串等.在本节中,我们尽可能以C语言的库函数表示其中的壹些运算,若没有库函数,则用自定义函数说明.（1）strcpy(str1,str2)字符串拷贝（赋值）：把str2指向的字符串拷贝到str1中,返回str1.库函数和形参说明如下：charstrcpy(charstr1,charstr2)（2）strcat(str1,str2)字符串的联接：把字符串str2接到str1后面,str1最后的结尾符‘\0’被取消.返回str1.库函数和形参说明如下：charstrcat(charstr1,charstr2)（3）strlen(str)求字符串的长度：统计字符串str中字符的个数（不包括‘\0’）,返回字符的个数,若str为空串,则返回值为0.库函数和形参说明如下：unsignedintstrlen(charstr)（4）strstr(str1,str2)子串的查询：找出子串str2在主串str1第壹次出现的位置（不包括子串str2的结尾符）,返回该位置的指针,若找不到,返回空指针NULL.库函数和形参说明如下：charstrstr(charstr1,charstr2)（5）strcmp(str1,str2)字符串的比较：比较两个字符串str1、str2.若str1＜str2,则返回负数；若str1＞str2,则返回正数；若str1＝str2,则返回0.库函数和形参说明如下：intstrcmp(charstr1,charstr2)（6）substr(str1,str2,m,n)求子串：在字符串str1中,从第m个字符开始,取n个长度的子串str2；若m＞strlen(str)或n≤0,则返回空值NULL.自定义函数和形参说明如下：intsubstr(charstr1,charstr2,intm,intn)（7）delstr(str,m,n)字符串的删除：在字符串str中,删除从第m个字符开始的n个长度的子串.自定义函数和形参说明如下：Voiddelstr(charstr,intm,intn)（8）Insstr(str1,m,str2)字符串的插入：在字符串str1第m个位置之前开始,插入字符串str2.返回str1.自定义函数和形参说明如下：Voidinsstr(charstr1,intm,charstr2)对字符串的置换可以通过求串长,删除子串,字符串的联接等基本运算来实现.算法4-14.2串的表示和实现串的存储结构有3种方法：定长顺序存储表示,堆分配存储表示和串的块链存储表示.4.2.1定长顺序存储表示类似于线性表的顺序存储结构,用壹组地址连续的存储单元存储串值的字符序列.由于壹个字符只占1个字节,而现在(大)多数计算机的存储器地址是采用以字编址,壹个字（即壹个存储单元）占多个字节,因此顺序存储结构方式有两种：（1）紧缩格式：即壹个字节存储壹个字符.这种存储方式可以在壹个存储单元中存放多个字符,充分地利用了存储空间.但在串的操作运算时,若要分离某壹部分字符时,则变得非常麻烦.t图4-1串值的紧缩格式存储daa└┘structure\0

图4-1串值的紧缩格式存储4.2串的表示和实现串的存储结构有3种方法：定长顺序存储表示,堆分配存储表示和串的块链存储表示.t图4-1串值的紧缩格式存储

图4-1所示是以4个字节为壹个存储单元的存储结构,每个存储单元可以存放4个字符.对于给定的串s=〃data└┘structure〃,在C语言中采用字符＇\0＇作串值的结束符.串s的串值连同结束符的长度共15,只需4个存储单元.daa└┘structure\0

图4-1串值的紧缩格式存储用字符数组存放字符串时,其结构用C语言定义如下：defineMAXSTRLEN255//用户可在255以内定义最(大)串长P73TypedefunsignedcharSSTRING[maxstrlen+1];

//0单元存放串的长度由上述讨论可知,串的顺序存储结构有两(大)不足之处：壹是需事先预定义串的最(大)长度,这在程序运行前是很难估计的.二是由于定义了串的最(大)长度,使得串的某些操作受限,如串的联接运算等.串的实际长度可在预定义长度的范围内随意,超过预定义长度的串值则被“截断”.C语言以“\0”表示串值的终结.图4-2串值的非紧缩格式存储（2）非紧缩格式：这种方式是以壹个存储单元为单位,每个存储单元仅存放壹个字符.这种存储方式的空间利用率较低,如壹个存储单元有4个字节,则空间利用率仅为25%.但这种存储方式中不需要分离字符,因而程序处理字符的速度高.图4-2为串值的非紧缩格式存储.tada└┘st…图4-2串值的非紧缩格式存储

字符串上的运算1）字符串的联接Concat(&T,S1,S2)在这里S1、S2和T都是SString型的串变量,T为串S1与S2的联接结果.其值有三种情况：其壹,S1[0]+S2[0]<=MAXSTRLEN,结果完全正确其二,S1[0]<MAXSTRLEN而S1[0]+S2[0]>MAXSTRLEN,T的值S1的全部与S2的壹部分.其三,S1[0]=MAXSTRLEN,则T=S1.TT（1）S1和S2的完全连接（2）S1的全部和S2的壹部分连接

S1S2T

图4-1S1、S2连接的三种情况图示

（3）S2全部丢失的连接S2S1S2S1S1S2联接的算法描述

StatusConcat(Sstring&T,SstringS1,S2){P73if(S1[0]+S2[0]<=MAXSTRLEN){T[1…S1[0]]=S1[1…S1[0]];（完全联接）T[S1[0]+1..S1[0]+S2[0]]=S2[[1..S2[0]];T[0]=S1[0]+S2[0];uncut=TRUE;}elseif(S1[0]<MAXSTRLEN){（S1全部,S2的壹部分）T[1..S1[0]]=S1[1..S1[0]];T[S1[0]+1..MAXSTRLEN]=S2[1..MAXSTRLEN-S1[0]];T[0]=MAXSTRLEN;uncut=FALSE;}else{T[0..MAXSTRLEN]=S1[0..MAXSTRLEN];uncut=FALSE;（S2全部丢失）}Returnuncut;}//concat求子串SubString(&Sub,S,pos,len)将串S中从第pos个字符开始长度为len的字符序列复制到串Sub中.StatusSubString(SString&Sub,SStringS,intpos,int,len){P75//用Sub返回串S的第pos个字符开始长度为len的子串.//其中,1≤pos≤StrLength(S)且0≤len≤Strlength(S)-pos+1if(pos<1||pos>S[0]||len<0||len>S[0]-pos+1)returnError;Sub[1..len]=S[pos..pos+len-1];Sub[0]=len;returnOK;}//SubString由上可见,特点壹：原操作为串复制,特点二：越界则“截取”.时间复杂度取决于复制的字符序列的长度.4.2.2堆分配存储表示特点：仍以壹组地址连续的存储单元存放串值字符序列,但它们的存储空间是在程序执行过程中动态分配而得.堆的自由存储区由函数malloc()和free()管理.typedefstruct{charch;//若是非空串,则按串长分配存储区,否则ch为NULLintlength;//串长度}HString串的插入算法串的插入算法是为串S重新分配(大)小等于串S和串T长度之和的存储空间,然后进行复制.串的插入算法描述如下：

StatusStrInsret(Hstring&S,intpos,HstringT){P75

//1≤pos≤StrLength(S)+1.在串S的第pos个字符之前插入串T.if(pos<1||pos>S.length+1)returnERROR;（插入位置不合适）if(T.length){（T非空,则重新分配空间,插入T）if((S.ch=(char)realloc(S,ch,(S.length+T.length)sizeof(char))))exit(OVERFLOW);（T非空,空间分配失败）for(i=S.length-1;i>=pos-1;--i)（从最后字符开始移动字符）S.ch[i+T.length]=S.ch[i];（后移T.length个位置）S.ch[pos-1..pos+T.length-2]=T.ch[0..T.length-1];（插入T）S.length+=T.length;（修改S串的长度）}returnOk;}//StrInsret该算法的时间复杂性为O（m+n）.即S串与T串串长之和.赋值运算在内存生成壹个值等于串常量chars的串T.赋值运算的描述如下：StatusStrAssign(Hstring&T,charchars){P76if(T.ch)free(T.ch);(释放T原有空间）for(i=0,c=chars;c;++i,++c);（计算串的长度i）if(i){T.ch=NULL;T.length=0;}else{if((T.ch=(char)malloc(isizeof(char))))exit(OVERFLOW);（为T串分配空间失败）T.ch[0..i-1]=chars[0..i-1];（生成T串）T.length=i;}returnOK;}//StrAssign定位运算又称定位函数Index(S,T,pos).其功能是在主串S中查找T串子串.如果查找成功,返回值为T子串中的第壹个字符在S串中的位置序号.如找不到返回值为0.若存在多个T串,则以第壹个为准.T壹般被称为模式串,所以,定位函数又称为模式匹配.intIndex(SStringS,SStringT,intpos){//返回T在S中第pos个字符之后的位置.若不存在,则函数值为0.P79//其中,T非空,1≤pos≤Strlength(S).i=pos;j=1;while(i<=S[0]&&j<=T[0]){if(S[i]==T[j]){++i;++j}(相同继续比较后继字符）else{i=i-j+2;j=1;}（失配修改指针重新开始匹配）}if(j>T[0])returni-T[0];（匹配成功返回第壹个匹配字符位置elsereturn0;（失败返回０）}//Index注意：壹般的模式匹配仅返回结果是匹配与不匹配.动画求串长：P77IntStrlength(HstringS){returnS.length;}//Strlength比较两个串：IntStrCompare(HstringS,HstringT){//若S＞T,则返回值＞0；若S＝T,则返回值＝0；若S＜T,则返回值＜0for(i=0;i<S.length&&i<T.length;++i)if(S.ch[i]=T.ch[i])returnS.ch[i]-T.ch[i];returnS.length-T.length;}//StrCompare将串清空：StatusClearString(HString&S)P77if(S.ch){free(S.ch);S.ch=NULL;}S.length=0;returnOK;}//ClearString连接两串：StatusConcat(HString&T,HStringS1,S2){if(T.ch)free(T.ch);//释放旧空间if((T.ch=(char)malloc((S1.length+S2.length)sizeof(char))))exit(IVERFLOW);T.ch[0..S1.length-1]=S1.ch[0..S1.length-1];T.length=S1.length+S2.length;T.ch[S1.length..T.length-1]=S2.ch[0..S2.length-1];returnOK;}//Concat求子串运算substring(s,i,j)P77该种运算的功能是在串S中求从起始位置i开始长度为j的子串.源串S不发生任何变化.注意在实际应用中该种运算存在下面几种形式；substring(s,i,j)；substring(s,i)；substring(s,i,0)；例如,S=‘aabcacbbcaabc’;i=6;

substring(s,i)=‘cbbcaabc’；substring(s,i,0)=‘’；S=‘aabcacbbcaabc’;i=6;j=4;substring(s,i,j)=‘cbbc’;注意：1≦i≦s.length+1;0≦j;

若i+j>s.length+1;则,j=s.length-i+1;如i=6;j=14;则substring(s,i,j)=‘cbbcaabc’；StatusSubString(HString&Sub,HStringS,intpos,intlen){//用Sub返回串S的第pos个字符起长度为len的子串//其中,1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1if(pos＜1||pos＞S.length||len＜0||len＞S.length-pos+1)returnERROR;if(Sub.ch)free(Sub.ch);//释放旧空间if(len){Sub.ch=NULL;Sub.length=0;}//空子串else{//完整子串Sub.ch=(char)malloc(lensizeof(char));Sub.ch[0..Len-1]=S.ch[pos-1..Pos+len-2];sub.length=len;}returnOK;}4.2.3串的块链存储表示串属于线性表,所以也可以用链表存储,但是由于串中的每个数据元素是壹个字符,因而,用链表存储串值时,就存在每个结点存放壹个字符,或每个结点存放多个字符的情况.当每个结点存放多个字符时,如果链表中最后壹个结点中存在空字段,则用“”来填充.如图示：headhead为了便于进行串的操作,以链表存储字符串值时,除了设置头指针外,还设置壹个尾指针指示链表中的最后壹个结点,并给出当前串的长度.称串的这种存储结构为块链结构.defineCHUNKSIZE80typedefstructChunk{charch[CHUNKSIZE];structChunknext;}ChunkABCDEFGHI

∧ABCI∧typedefstruct{Chunkhead,tail;//头尾指针intcurlen;//串的当前长度}LString;…在链式存储方式中结点(大)小的选择直接影响串的处理效率.因而要考虑串值的存储密度.

存储密度＝———————显然存储密度小,运算处理方便4.4串的应用1）文本编辑输入到计算机内存中等待加工与修改的源程序通称文本.现在,文本编辑程序的种类有多种,功能强弱不同,但基本操作如串的查找、插入和删除都是相同的.总的存储位数串值所占的存储位例如壹段源程序为：main(){floata,b,max;scanf(“%f,%f”,&a,&b);ifa>bmax=a;elsemax=b;}上述源程序按顺序存储如图4-7.

为了管理文本串的页和行,在进行文本编辑时,编辑程序先为文本串建立相应的页表和行表.页表的每壹项给出页号和该页的起始行号.而行表的每壹项则指示每壹行的行号、起始地址和该行子串的长度.假设上图所示文本只占壹页,且起始行号为201,则该文本串的行表如图4-8.mnin(){floata,b,max;scanf(“%f,%f“,&a,&b);ifa>bmax=a;elsemax=b;}201209226250267282图4-7文本格式示例图4-8图4-7所示文本串的行表

main(){floata,b,max;scanf(“%f,%f”,&a,&b);ifa>bmax=a;elsemax=b;}下面我们就来讨论文本的编辑.（1）插入壹行时,首先在文本末尾的空闲工作区写入该行的串值,然后,在行表中建立该行的信息,插入后,必须保证行表中行号从小到(大)的顺序.若插入行145,则行表中从150开始的各行信息必须向下平移壹行.（2）删除壹行时,则只要在行表中删除该行的行号,后面的行号向前平移.若删除的行是页的起始行,则还要修改相应页的起始行号（改为下壹行）.（3）修改文本时,在文本编辑程序中设立了页指针,行指针和字符指针,分别指示当前操作的页、行和字符.若在当前行内插入或删除若干字符,则要修改行表中当前行的长度.如果该行的长度超出了分配给它的存储空间,则应为该行重新分配存储空间,同时还要修改该行的起始位置.对页表的维护与行表类似,在此不再叙述,有兴趣的同学可设计其中的算法.作业：1、利用学过的字符串上的操作运算,设计检查用户输入的程序编号是否正确的算法.（编号若是四位数字组成为正确）2、假设S、T分别为两个字符串,设计用在S串中与T串中都存在的所有字符构成新串R且打印该字符在S串中第壹次出现时的位置的算法.3、已知S=“aabbbccaabccaabc”,v=‘xxyy’;m=ASSIGN(m,substr(s,LEN(v)));i=INDEX(m,SUBSTR(S,6,LEN(v)));Replace(m,SUBSTR(S,i,LEN(v)),v)=;

4、已知字符串‘1234+-/5678’试编写删除串中‘+-/’子串的算法.5、已知字符串S,若在其中能检索到子串“ON”,则用单引号将它括起来,试编写完成该功能的算法.6、已知字符串S=‘JION’,X=‘FRANG’,试编写将字符串S和X联接成壹个字符串的算法.7、假设S、T分别为两个字符串,设计用在S串中存在而T串中不存在的所有字符构成新串R且打印字符串S最后长度的算法.8、已知字符串S,若在其中能检索到子串‘IHG’,则在其后插入子串‘=’,试编写完成该功能的算法.9、求出子串‘NG’在字符串‘JIAOTONG’中的位置序号.学习目标与重点◆理解串的定义；◆理解串的顺序存储结构和链式存储结构；◆掌握串的定长顺序存储的基本算法.本章小结本章主要介绍了如下壹些基本概念：串：串（或字符串）（String）是由零个或多个字符组成的有限序列.主串和子串：壹个串的任意个连续的字符组成的子序列称为该串的子串,包含该子串的串称为主串.串的定长顺序存储结构：类似于线性表的顺序存储结构,用壹组地址连续的存储单元存储串值的字符序列的存储方式称为串的顺序存储结构.堆分配存储结构：用壹组空间足够(大)的、地址连续的存储单元存放串值字符序列,但其存储空间在程序执行过程中能动态分配的存储方式称为堆存储结构.串的链式存储结构：类似于线性表的链式存储结构,采用链表方式存储串值字符序列的存储方式称为串的链式存储结构.除上述基本概念以外,学生还应该了解串的基本运算（字符串拷贝即赋值、字符串的联接、求字符串的长度、子串的查询、字符串的比较）、串的定长顺序存储结构的表示、串的链式存储结构的表示、串的堆分配存储结构的表示,能在各种存储结构方式中求字符串的长度、能在各种存储结构方式中利用C语言提供的串函数进行操作.习

题

四1．简述空串与空格串、串变量与串常量、主串与子串、串名与串值每对术语的区别2．两个字符串相等的充要条件是什么3．串有哪几种存储结构4．已知两个串：s1=”fgcdbcabcadr”,s2=”abc”,试求两个串的长度,判断串s2是否是串s1的子串,并指出串s2在串s1中的位置.5．已知：s1=〃I’mastudent〃,s2=〃student〃,s3=〃teacher〃,试求下列各运算的结果：strstr(s1,s2)；strlen(s1)；strcat(s2,s3)；delstr(s1,4,10)；6．设s1=”AB”,s2=”ABCD”,s3=”EFGHIJK,试画出堆存储结构下的存储映象图.7．试写出将字符串s2中的全部字符拷贝到字符串s1中的算法,不允许利用库函数strcpy().8．设s1和s2是用结点(大)小为1的单链表表示的串,试写出找出s2中第壹个不在s1中出现的字符的算法.9．设字符串采用块链存储结构,块链中每个结点存放m（m=4）个字符,试写出实现字符串删除的算法.

试题库题

第四章串串单选题1、设字符串s1=‘abcdefg’,s2=‘pqrst’,则运算s=concat(sub(s1,2,len(s2)),sub(s1,len(s2),2))后串值为_____.2、空串与空白串是相同的,这种说法________.3、串是壹种特殊的线性表,其特殊性体现在________.4、_______是C语言中“abcd321ABCD”的子串.1、'bcdef'|'bcdefg'|'bcpqrst'|'bcdefef'D2、正确|不正确||B3、可以顺序存储|数据元素是壹个字符|可以链式存储|数据元素可以是多个字符B4、abcd|321AB|"abcABC"|"21AB"D串单选题5、有串s1=‘ABCDEFG’,s2=‘PQRST’,假设函数con(x,y)返回x和y串的连接串,函数subs(s,i,j)返回串s的从序号(下标)i的字符开始的j个字符组成的子串,函数len(s)返回串s的长度,则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是_______.6、经过以下队列运算后,队头的元素是______.InitQueue(qu);enQueue(qu,'a');enQueue(qu,'b');enQueue(qu,'c');deQueue(qu);7、经过以下队列运算后,QueueEmpty(q)的值是______.InitQueue(qu);enQueue(qu,a);enQueue(qu,b),deQueue(qu,x);deQueue(qu,y);5、BCDEF|BCDEFG|BCPQRST|CDEFGFGD6、a|b|1|0B7、a|b|1|0C串单选题8、元素A、B、C、D顺序连续进入队列qu后,队头元素是______,队尾元素是______.9、壹个队列的入列序列为1234,则队列可能的输出序列是______.10、环形队列qu的队满条件是______.8、A|B|C|DA|D9、4321|1234|1432|3241B10、(qu.rear+1)%MaxSize==(qu.front+1)%MaxSize|(qu.rear+1)%MaxSize==qu.front+1|(qu.rear+1)%MaxSize==qu.front|qu.rear==qu.frontC串单选题11、环形队列qu的队空条件是______.12、设环形队列中数组的下标是0～N-1,其头、尾指针分别为f和r,则其元素个数为______.11、(qu.rear+1)%MaxSize==(qu.front+1)%MaxSize|(qu.rear+1)%MaxSize==qu.front+1|(qu.rear+1)%MaxSize==qu.front|qu.rear==qu.frontD12、r-f|r-f-1|(r-f)%N+1|(r-f+N)%ND

串单选题13、判定壹个环形队列qu(存放元素位置0～QueueSize-1)队满的条件是______.13、qu.front==qu.rear|qu.front+1==qu.rear|qu.front==(qu.rear+1)%QueueSize|qu.rear==(qu.front+1)%QueueSizeC串单选题14、假设用qu[0..M]实现环形队列,qu[f]、qu[r]分别为队首元素的前壹个位置和队尾位置.若用“(r+1)%(M+1)==f”作为队满的标志,则______.15、最适合用作链队的链表是______.16、用单链表表示的链队的队头在链表的______位置.14、可用“f==r”作为队空的标志|可用“f>r”作为队空的标志|可用“(f+1)%(M+1)==r”作为队空的标志|队列中最多可以有M+1个元素A15、带队首指针和队尾指针的循环单链表|带队首指针和队尾指针的非循环单链表|只带队首指针的非循环单链表|只带队首指针的循环单链表B16、链头|链尾|链中|以上都可以A

串单选题17、用单链表表示的链队的队尾在链表的______位置.18、对于链队,在进行删除操作时,______.19、栈和队列的共同点是______.20、判定壹个环形队列Q(存放元素位置为0～QueueSize-1)队满的条件是______.21、栈的插入和删除操作在_________进行.17、链头|链尾|链中|以上都可以B18、仅修改头指针|仅修改尾|头、尾指针都要修改|头、尾指针可能都要修改D19、都是先进后出|都是先进先出|只允许在端点处插入和删除元素|没有共同点C20、Q.front==Q.rear|Q.front+1==Q.rear|Q.front==(Q.rear+1)%QueueSize|Q.rear=(Q.front+1)%QueueSizeC21、栈顶|栈底|任意位置|指定位置A串单选题22、当利用(大)小为N的数组顺序存储壹个栈时,假定用top==N表示栈空,则向这个栈插入壹个元素时,首先应执行_________语句修改top指针.23、假定利用数组a[N]顺序存储壹个栈,用top表示栈顶指针,top==-1表示栈空,并已知栈未满,当元素x进栈时所执行的操作为_________.24、利用数组a[N]顺序存储壹个栈,用top表示栈顶指针,top==-1表示栈空,并已知栈未空,当退栈并返回栈顶元素时所执行的操作为_________.22、top++|top--|top=0|topB23、a[--top]=x|a[top--]=x|a[++top]=x|a[top++}=xC24、returna[--top]|returna[top--]|returna[++torp]|returna[top++]B串单选题25、壹个链栈的栈顶指针用top表示,当p所指向的结点进栈时,执行的操作为_________.26、壹个链栈的栈顶指针用top表示,当进行退栈时所进行的指针操作为_________.27、若让元素1,2,3依次进栈,则出栈次序不可能出现_________种情况.28、在壹个顺序队列中,队首指针指向队首元素的_________位置.25、p->next=top;top=top->next;|top=p;p->next=top;|p->next=top->next;top->next=p;|p->next=top;top=p;D26、top->next=top;|top=top->data;|top=top->next;|top->next=top->next->nextC27、3,2,1|2,1,3|3,1,2|1,2,3C28、前壹个|后壹个|当前|后面C串单选题29、当利用(大)小为N的数组顺序存储壹个队列时,若没有队列长度的变量,则该队列的最(大)长度为_________.30、当利用(大)小为N的数组顺序存储壹个队列时,若不设有队列长度的变量,则该队列的最(大)长度为_________.31、从壹个顺序队列删除元素时,首先需要_________.32、壹个不设队列长度变量的顺序队列的队首和队尾指针分别为f和r,则判断队空的条件为_________.29、N-2|N-1|N|N+1B30、N-2|N-1|N|N+1B31、队首指针循环加１|队首指针循环减１|取出队首指针所指位置上的元素|取出队尾指针所指位置上的元素A32、f+1==r|r+1==f|f==0|f==rD串单选题33、假定壹个链队的队首和队尾指针分别为front和rear,则判断队空的条件为_________.34、假定利用数组a[N]循环顺序存储壹个队列,用f和r分别表示队首和队尾指针,并已知队未满,当元素x进队时所执行的操作为_________.35、在壹个长度为N的数组空间中,顺序存储着壹个队列,该队列的队首和队尾指针分别用front和rear表示,则该队列中的元素个数为_________.33、front==rear|front=NULL|rear=NULL|front==NULLD34、a[++r%N]=x|a[r++%N]=x|a[--r%N]=x|a[r--%N]=xB35、(rear-front)%N|(rear-front+N)%N|(rear+N)%N|(front+N)%NB串判断题1、栈和队列都是限制存取端的线性表.2、队列是壹种对进队列、出队列操作的次序作了限制的线性表.3、n个元素进队列的顺序和出队列的顺序总是壹至的.4、顺序队中有多少元素,可以根据队首指针的值和队尾指针的值来计算.5、队列的输入序列为1234…n,输出序列为a1a2…an,则ai<ai+1(1<=i<=n-1).1、True2、False3、True4、True5、True串填空题1、串的两种最基本的存储方式是_________.2、两个串相等的充分必要条件是________.3、空串是________,其长度等于_________.4、空白串是________,其长度等于_________.1、顺序存