数据结构第02章_线性表(I)

*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,退出,数据结构,李云清 杨庆红 揭安全,高等学校精品课程,人民邮电出版社,（第,2,版）,数据结构,揭安全,江西省高等学校精品课程,E_mail,: jieanquan,江西师范大学计算机信息工程学院,第,2,章 线性表及其顺序存储,线性表,顺序表,栈,队列,线性表是一种常用的数据结构，本章介绍线性表及其顺序存储，并对栈和队列及它们的顺序实现给出了详细的设计描述。,2.1,线性表,线性表是一个线性结构，它是一个含有,n0,个结点的有限序列，对于其中的结点，有且仅有一个开始结点没有前驱但有一个后继结点，有且仅有一个终端结点没有后继但有一个前驱结点，其它的结点都有且仅有一个前驱和一个后继结点。一般地，一个线性表可以表示成一个线性序列：,k,1,k,2,k,n,，,其中,k,1,是开始结点，,k,n,是终端结点。,例,1,、,26,个英文字母组成的字母表,（,A,，,B,，,C,、,、,Z,）,例,2,、某校从,1978,年到,1983,年各种型号的计算机拥有量的变化情况。,（,6,，,17,，,28,，,50,，,92,，,188,）,姓 名,学 号,性 别,年 龄,健康情况,王小林,790631,男,18,健康,陈 红,790632,女,20,一般,刘建平,790633,男,21,健康,张立立,790634,男,17,贫血,.,.,.,.,.,例,3,学生健康情况登记表如下：,例,4,、一副扑克的点数,（,2,，,3,，,4,，,，,J,，,Q,，,K,，,A,）,从以上例子可看出线性表的逻辑特征是：,在非空的线性表，有且仅有一个开始结点,a,1,，,它没有直接前趋，而仅有一个直接后继,a,2,；,有且仅有一个终端结点,a,n,，,它没有直接后继，而仅有一个直接前趋,a,n-1,；,其余的内部结点,a,i,(2in-1),都有且仅有一个直接前趋,a,i-1,和一个直接后继,a,i+1,。,线性表是一种典型的线性结构。,2.2.1,顺序表,线性表采用顺序存储的方式存储就称之为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。,如顺序表的每个结点占用,len,个内存单元,，用,location (,k,i,),表示顺序表中第,i,个结点,k,i,所占内存空间的第,1,个单元的地址。则有如下的关系,location (k,i+1,) = location (,k,i,) +len,location (,k,i,) = location(k,1,) + (i-1)len,2.2,顺序表,顺序表的存储结构如下图所示：,存储结构要体现数据的逻辑结构，顺序表的存储结构中，内存中物理地址相邻的结点一定具有顺序表中的逻辑关系。,存储地址,location(k,1,) location(k,1,)+(i-1)l en,结点序号,1 2 i n,len len len len,k,1,k,2,k,i,k,n,内存状况,2.2.2,顺序表的实现,用,C,语言中的数组存储顺序表。,C,语言中数组的下标是从,0,开始的，即数组中下标为,0,的元素对应的是顺序表中的第,1,个结点，数组中下标为,i,的元素对应的是顺序表中的第,i+1,个结点。为了方便，将顺序表中各结点的序号改为和对应数组元素的下标序号一致，即将顺序表中各结点的序号从,0,开始编号。这样，一个长度为,n,的顺序表可以表示为,k,0, k,1, k,2, , k,n-1,顺序表的存储结构的,C,语言描述如下：,/*,顺序表的头文件，文件名,sequlist.h,*/,#define MAXSIZE 100,typedef,int,datatype,;,typedef,struct,datatype,aMAXSIZE;,int,size;,sequence_list;,表长,顺序表的几个基本操作的具体实现 ：,/,/,/,函数功能,:,顺序表的初始化,置空表,/,/,函数参数,:,指向,sequence_list,型变量的指针变量,slt,/,/,函数返回值,:,空,/,/,文件名,:,sequlist.c,函数名,:init(),/,/,/,void,init(sequence_list,slt,),slt,-size=0;,算法,2.1,顺序表的初始化,-,置空表,/,/,/,函数功能,:,在顺序表后部进行插入操作,/,/,函数参数,:,指向,sequence_list,型变量的指针变量,slt,/,/,datatype,类型的变量,x,/,/,函数返回值,:,空,/,/,文件名,:,sequlist.c,函数名,:append(),/,/,/,void,append(sequence_list,slt,datatype,x),if(slt,-size=MAXSIZE),printf,(,顺序表是满的,!);exit(1);,slt,-,aslt,-size=x;,slt,-size=,slt,-size+1;,算法,2.2,在顺序表后部进行插入操作,打印顺序表的各结点值,/,/,/,函数功能,:,打印顺序表的各结点值,/,/,函数参数,:,sequence_list,型变量,slt,/,/,函数返回值,:,空,/,/,文件名,:,sequlist.c,函数名,:display(),/,/,/,void,display(sequence_list,slt,),int,i;,if(!slt.size,),printf(n,顺序表是空的,!);,else,for(i,=0;i,slt.size;i,+) printf(%5d,slt.ai);,算法,2.3,打印顺序表的各结点值,判断顺序表是否为空,/,/,/,函数功能,:,判断顺序表是否为空,/,/,函数参数,:,sequence_list,型变量,slt,/,/,函数返回值,:,int,类型。,1,表示空,0,表示非空,/,/,文件名,:,sequlist.c,函数名,:empty(),/,/,/,int,empty(sequence_list,slt,),return(,slt.size,=0 ? 1:0);,算法,2.4,判断顺序表是否为空,查找顺序表中值为,x,的结点位置,/,/,/,函数功能,:,查找顺序表中值为,x,的结点位置,/,/,函数参数,:,sequence_list,型变量,slt,datatype,型变量,x,/,/,函数返回值,:,int,类型。返回,x,的位置值,-1,表示没找到,/,/,文件名,:,sequlist.c,函数名,:find(),/,/,/,int,find(sequence_list,slt,datatype,x),int,i=0;,while(i,slt.size&slt.ai,!=x) i+;,return(i,size=MAXSIZE),printf(n,顺序表是满的,!,没法插入,!);exit(1);,if(position,slt,-size),printf(n,指定的插入位置不存在,!);exit(1);,for(i,=,slt,-,size;i,position;i,-),slt,-,ai,=,slt,-ai1;,slt,-,aposition,=x;,slt,-size+;,算法,2.7,在顺序表的,position,位置插入值为,x,的结点,算法,2.7,中，所花费的时间主要是元素后移操作，对于在第,i,个位置上插入一个新的元素，需要移动（,n-i,）,个元素，设在第,i,个位置上插入一个元素的概率为,p,i,，,且在任意一个位置上插入元素的概率相等，即,p,0,=p,1,=p,2,=,p,n,=1/(n+1),，则在一个长度为,n,的顺序表中插入一个元素所需的平均移动次数为：,即在长度为,n,的顺序表中插入一个元素平均需要移动表中的一半元素。该算法的时间复杂度为,O,（,n,）。,顺序表的删除操作是指删除顺序表中的第,i,个结点，,0in-1,，,一般地可表示为：,删除前：,k,0, k,1, , k,i-1,k,i, k,i+1, , k,n-1,删除后：,k,0, k,1, , k,i-1, k,i+1, , k,n-1,删除过程的图示见下图 ：,k,i,k,0,k,1,k,i-1,k,n-1,k,0,k,1,k,i-1,k,n-1,k,i+1,前移结束位置,前移开始位置,删除前,删除后,k,i+1,删除操作的具体实现见算法,2.8,/,/,/,函数功能,:,删除顺序表中第,position,位置的结点,/,/,函数参数,:,指向,sequence_list,型变量的指针变量,slt,/,/,int,型变量,position,/,/,函数返回值,:,空 文件名,:,sequlist.c,函数名,:dele(),/,/,/,void,dele(sequence_list,slt,int,position),int,i;,if(slt,-size=0),printf(n,顺序表是空的,!);exit(1);,if(position,=,slt,-size),printf(n,指定的删除位置不存在,!);exit(1);,for(i,=,position;i,size-1;i+),slt,-,ai,=,slt,-ai+1;,slt,-size-;,算法,2.8,删除顺序表中第,position,位置的结点,要删除顺序表中的第,i,个结点，则需要称动（,n-i-1,）,个元素，设删除表中第,i,个结点的概率为,q,i,，,且在表中每一个位置删除的概率相等，即：,q,0,=q,1,=q,n-1,=1/n,则在一个长度为,n,的顺序表中删除一个结点的平均移动次数为：,这表明，在一个长为,n,的顺序表中删除一个元素平均需要移动表中大约一半的元素。该算法的时间复杂度为,O,（,n,）。,（,1,）,void verge(sequence_list l),将顺序表,L,就地转置，即借助于,O,（,1,）,的辅助空间。,（,2,）,void,sprit(sequence_lsit,*l1,sequence_list *l2, sequence_list *l3) ,略,将有序顺序表,L1,分裂成两个线性表,L2,与,L3,，,L2,由表中所奇数组成，,L3,由所有偶数组成。,顺序表上的一些其它常见算法,（,3,）,void,merge(sequence_lsit,*l1,sequence_list *l2, sequence_list *l3),将有序顺序表,L1,与,L2,合并成有序顺序表,L3,。,2.3,栈,2.3.1,栈,栈是一种特殊的线性表，对于这种线性表规定它的插入运算和删除运算均在线性表的同一端进行，进行插入和删除的那一端称为,栈顶,，另一端称为,栈底,。栈的插入操作和删除操作也分别简称进栈和出栈。,如果栈中有,n,个结点,k,0, k,1, k,2, , k,n-1,，,k,0,为栈底，,k,n-1,是栈顶，则栈中结点的进栈顺序为,k,0, k,1, k,2, , k,n-1,，,而出栈的顺序为,k,n-1, k,n-2, , k,1, k,0,。,如图所示。,栈具有后进先出或先进后出（,FILO,First In Last Out,）,的性质,k,0,k,1,k,n-1,栈顶,栈底,出栈 进栈,2.3.2,顺序栈及其实现,栈的顺序存储方式就是在顺序表的基础上对插入和删除操作限制它们在顺序表的同一端进行，所以同顺序表一样也可用一维数组表示。,一般地，可以设定一个足够大的一维数组存储栈，数组中下标为,0,的元素就是栈底，对于栈顶，可以设一个指针,top,指示它。,为了方便，设定,top,所指的位置是下一个将要插入的结点的存储位置，这样，当,top=0,时就表示是一个空的栈。一个栈的几种状态以及在这些状态下栈顶指针,top,和栈中结点的关系如下图所示。,k,0,k,1,k,0,k,2,k,1,k,数组下标 数组下标 数组下标,MAXSIZE-1 MAXSIZE-1 MAXSIZE-1,2 top 2 2,1 1 1,top 0 0 0,top,(a),空栈,(b),有两个结点的栈,(c),栈已满,栈的顺序存储结构的,C,语言描述如下：,/,/,/,栈（顺序存储）的头文件,/,/,文件名,seqstack.h,/,/,/,#define MAXSIZE 100,typedef,int,datatype,;,typedef,struct,datatype,aMAXSIZE,;,int,top;,sequence_stack,;,下面是顺序存储栈的几个基本操作的具体实现,/,/,/,函数功能,:,栈（顺序存储）初始化,/,/,函数参数,:,指向,sequence_stack,型变量的指针变量,st,/,/,函数返回值,:,空,/,/,文件名,:,seqstack.c,函数名,:init(),/,/,/,void,init(sequence_stack,st,),st,-top=0;,算法,2.9,栈（顺序存储）初始化,说明,:top=0,表示栈空，这种情况下栈顶指示位内容始终为空。,/,/,/,函数功能,:,判断栈（顺序存储）是否为空,/,/,函数参数,:,sequence_stack,型变量,st,/,/,函数返回值,:,int,类型。,1,表示空,0,表示非空,/,/,文件名,:,seqstack.c,函数名,:empty(),/,/,/,int,empty(sequence_stack,st,),return(st.top,? 0:1);,算法,2.10,判断栈（顺序存储）是否为空,/,/,/,函数功能,:,读栈顶（顺序存储）结点值,/,/,函数参数,:,sequence_stack,型变量,st,/,/,函数返回值,:,datatype,类型。返回栈顶结点值,/,/,文件名,:,seqstack.c,函数名,:read(),/,/,/,datatype,read(sequence_stack,st,),if (,empty(st,),printf(n,栈是空的,!);exit(1);,else,return st.ast.top-1;,算法,2.11,取得栈顶（顺序存储）结点值,顺序栈的进栈与出栈操作,下图表明进出栈情况。,5,4,3,2,1,0,top,（,a,）,空栈,5,4,3,2,1,0,top,A,（,b,）,A,进栈,5,4,3,2,1,0,-1,top,A,（,c,）,B,、,C,、,D,进栈,B,C,D,top,top,top,5,4,3,2,1,0,A,（,d,）,D,C,出栈,B,C,D,top,5,4,3,2,1,0,（,e,）,E,进栈,A,B,C,D,top,E,top,5,4,3,2,1,0,A,B,E,D,top,（,f,）,E,、,B,、,A,出栈,/,/,/,函数功能,:,栈（顺序存储）的插入（进栈）操作,/,/,函数参数,:,指向,sequence_stack,型变量的指针变量,st,/,/,datatype,型变量,x,/,/,函数返回值,:,空,/,/,文件名,:,seqstack.c,函数名,:push(),/,/,/,void,push(sequence_stack,st,datatype,x),if(st,-top=MAXSIZE),printf(nThe,sequence stack is full!);exit(1);,st,-,ast,-top=x;,st,-top+;,算法,2.12,栈（顺序存储）的插入操作,/,/,/,函数功能,:,栈（顺序存储）的删除（出栈）操作,/,/,函数参数,:,指向,sequence_stack,型变量的指针变量,st,/,/,函数返回值,:,空,/,/,文件名,:,seqstack.c,函数名,pop(),/,/,/,void,pop(sequence_stack,st,),if(st,-top=0),printf(nThe,sequence stack is empty!);exit(1);,st,-top-;,算法,2.13,栈（顺序存储）的删除操作,思考,:,如果将栈空表示为,top=-1,则所有栈的所有操作为何变化呢,?,2.3.3,栈的应用之一,-,括号匹配,设一个表达式中可以包含三种括号：小括号、中括号和大括号，各种括号之间允许任意嵌套，如小括号内可以嵌套中括号、大括号，但是不能交叉。举例如下：,(),正确的,(),正确的,(),正确的,(),不正确的,(),不正确的,如何去检验一个表达式的括号是否匹配呢？大家知道当自左向右扫描一个表达式时，凡是遇到的开括号（或称左括号）都期待有一个和它对应的闭括号（或称右括号）与之匹配。,按照括号正确匹配的规则，在自左向右扫描一个表达式时，后遇到的开括号比先遇到的开括号更加期待有一个闭括号与之匹配。,/,/,/,函数功能,:,判断表达式括号是否匹配,/,/,函数参数,:char,类型数组,c,/,/,函数返回值,:,int,类型。返回,1,为匹配,返回,0,为不匹配,/,/,文件名,:,seqmatch.c,函数名,:,match_kouhao,(),/,/,/,int,match_kuohao(char,c),int,i=0;,sequence_stack,s;,init(&s,);,while(ci,!=#),switch(ci,),case :,case :,case (:,push(break,;,case :,if(!empty(s)&read(s,)= ),pop(break,; else return 0;,case :,if(!empty(s)&read(s,)= ),pop(break,; else return 0;,case ):,if(!empty(s)&read(s,)=( ),pop(break,; else return 0;,i+;,return (,empty(s,); /,栈为空则匹配,否则不匹配,/,算法,2.14,判断表达式括号是否匹配,算术表达式通常是由操作数、算术运算符和一对圆括号“（”和“）”组合而成。其中操作数允许是程序语言中任意合法的变量名或常数。,以下我们讨论,+,、,-,、*、,/,四种算术运算。,表达式求值中的首要问题：如何确定表达式中所含运算的计算次序。,算术运算的规则：,1,）先乘除、后加减,2,）从左算到右,3,）先括号内、后括号外,2.3.4,栈的应用之二,-,算术表达式求值,按此原则，算术表达式,A+B*,（,C+D,）,的运算次序为：,A+B*,（,C+D,）,而不是,A+B*,（,C+D,）,1,2,3,1,2,3,问题：,如何让计算机也遵守算术运算规则，正确计算表达式的值？,方法,1,：,加括号，即对每个一运算都用一对括号将与其配对的左、右操作对象括在一起，由此上面算术表达式将写成（,A+,（,B*,（,C+D,）,利用栈求表达式的值：,1,）自左至右的扫描加括号的算术表达式,2,）将非右括号“）”的符号进栈,3,）每当遇见右括号“）”，从栈顶向下扫描至第一个左括号“（”，这就是和遇见的右括号“）”配对的左括号“（”，该左括号“（”上面的表达式就是现在应该计算的表达式，从栈中弹出对应的左括号“（”以上的所有符号（含左括号”（“），计算相应表达式，并将结果压入栈中。,重复,1,）,2,）,3,）即可计算出表达式的值。,特点：方法简单明了，但要求人们事先为要计算的表达式加好括号，这既繁琐，又易出错。,方法,2,：,重新改写表达式为后缀表达式。,在计算机中，表达式可以有三种不同的标识方法,设,Exp = S1 + OP + S2,则称,OP + S1 + S2,为表达式的前缀表示法,称,S1 + OP + S2,为表达式的中缀表示法,称,S1 + S2 + OP,为表达式的后缀表示法,可见，它以运算符所在不同位置命名的。,例：,中缀表达式 后缀表达式,（,1,）,A A,（,2,）,A+B AB+,（,3,）,A+B*C ABC*+,（,4,）,A*,（,B-C,）,+D ABC-*D+,（,5,）,D+A/,（,B-C,）,DABC-/+,结论,:,操作数之间的相对次序不变,;,运算符的相对次序不同,;,后缀表达式中没有括号，运算符排在其第二个操作数之后,;,前缀式的运算规则为,:,连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式,;,后缀式的运算规则为,:,运算符在式中出现的顺序恰为表达式的运算顺序,;,每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式,;,+-*/,四则运算的计算方法：,第一步：将中缀表达式转换成等价的后缀表达式,第二步：使用后缀表达式进行计算。,算法：利用后缀表达式求值,基本思想：,1,）从左到右扫描后缀表达式，遇到操作对象进栈。,2,）遇到运算符，弹出栈顶的元素，其中栈顶为第二操作对象，次栈顶为第一操作对象，对其按遇到的运算符进行运算，并将结果进栈。,重复上述动作最后即可求出表达式的值。,例如有中缀表达式：,A/B-,（,C+D,）*,E,其对应的后缀表达式为：,AB/CD+E*-,利用后缀表达式求值过程如下所示：,步骤 操作数栈 后缀表达式 说明,1 AB/CD+E*-#,初始栈空，,A,进栈,2 A AB/CD+E*-#,B,进栈,3 AB AB/CD+E*-#,遇,/,，弹出栈顶两元素做,A/B=,，,并将其进栈,4,AB/CD+E*-#,C,进栈,5,C,AB/CD+E*-#,D,进栈,步骤 操作数栈 后缀表达式 说明,6,CD,AB/CD+E*-#,遇,+,，弹出,CD,做,C+D=,，,并将其进栈,7,AB/CD+E*-#,E,进栈,8,E,AB/CD+E*-#,遇*，弹出栈顶两元做,*,E=,，,并将结果进栈,9,AB/CD+E*-#,遇,-,，弹出栈顶二元做,-,=,，并将结果进栈,10,AB/CD+E*-#,遇,#,，结束，栈顶就是表达式的计算结果,在实际应用中，操作数可设为实数，且两个实数间用空格隔开。,问题：后缀表达式为字符串，如何从其中分离出每一个操作数。,解决办法：,用函数,Readnumber,(),实现将扫描到的数字字符序列转换成相应实数：,float,readnumber,(,char,f,int,*i),float x=0.0;,int,k=0;,while(f,*i=0&f*i=0& f*i=0 & fi=0 & ei=priority(ei),fj+=,pop(&opst,);,push(&opst,ei,); /*,当前元进栈*,/,i+; /*,处理下一元*,/,while (!,stackempty(&opst,),fj+=,pop(&opst,);,fj=0;,判断是否为运算符,int,is_operation(char,op),switch(op,), case +:,case -:,case ,:,case /:return 1;,default:return,0;,返回运算符的优先级,int,priority(char op), switch(op),case (:return 0;,case +:,case -:return 1;,case *:,case /:return 2;,default: return -1;, ,两个辅助函数：,本题源程序,后缀式,.c,习题,:,数制转换问题,十进制,n,和其它进制数的转换是计算机实现计算的基本问题，其解决方法很多，其中一个简单算法基于下列原理,:,n=(n div d)*d+n mod d,(,其中,:div,为整除运算,mod,为求余运算,),例如,(,1348),10,=(2504),8,，,其运算过程如下：,n n div 8 n mod 8,1348 168 4,168,21,0,21,2 5,2 0 2,倒取余数,(,1348),10,=(2504),8,例用栈,的知识实现任意正的,10,进制整数到其它进位制的转换程序。,算法设计题,:,2,、回文是指正读和反读均相同的字符序列，如“,abba,”,和“,abdba,”,均是回文，但“,good”,不是回文，试写一个算法判定给定的字符向量是否为回文。,void conversion( ),init(s,);,scanf,(“%d”,while(n) /,余数进栈,push(,n=n/8;,while(!,Stackempty(s,), e=,pop(&s,); /,余数出栈,printf(“%d”,e,);,习题一解答,:,2.4,队列,2.4.1,队列,队列是一种特殊的线性表，它的特殊性在于队列的插入和删除操作分别在表的两端进行。插入的那一端称为队尾，删除的那一端称为队首。队列的插入操作和删除操作也分别简称进队和出队。,对于一个队列：,k,0, k,1, k,2, , k,n-1,则,k,0,是这些结点中最先插入的结点，若要做删除操作，,k,0,将首先被删除，所以说，队列是具有“先进先出”（,FIFO,First In First Out,）,特点的线性结构。,队列类型的描述如下：,ADT,sequence_queue,数据集合,K,:,K,=,k,1,k,2,kn,n,0,K,中的元素是,datatype,类型,;,数据关系,R,:,R,=,r,r,= |,i,=1,2,n,1,。,操作集合,:,（,1,）,void init (,sequence_queue,sq),队列（顺序存储）初始化,;,（,2,）,int,empty (,sequence_queue,sq),判断队列（顺序存储）是否为空,;,（,3,）,void display (,sequence_queue,sq),打印队列（顺序存储）的结点值,;,（,4,）,datatype,get(sequence_queue,sq),取得队列（顺序存储）的队首结点值,;,（,5,）,void,insert(sequence_queue,sq,datatype,x),队列（顺序存储）的插入操作,;,（,6,）,void,dele(sequence_queue,sq),队列（顺序存储）的删除操作。, ADT,sequence_queue,;,2.4.2,顺序队列及其实现,队列的顺序存储在,C,语言中可以用一维数组表示，为了标识队首和队尾，需要附设两个指针,front,和,rear,，,front,指示的是队列中最前面，即队首结点在数组中元素的下标，,rear,指示的是队尾结点在数组中元素的下标的下一个位置，也就是说,rear,指示的是即将插入的结点在数组中的下标。,队列的几种状态 ：,队首、队尾指针,front rear,数组下标,0 1 MAXSIZE-1,(a),初始状态,-,空队列,A,B,队首、队尾指针,front rear,数组下标,0 1 MAXSIZE-1,(b),连续插入几个结点后的状态,D,C,队首、队尾指针,front rear,数组下标,0 1 2 3 MAXSIZE-1,(c),连续删除几个结点后的状态,-,此时队列中只有一个结点,D,队首、队尾指针,front rear,数组下标,0 1 MAXSIZE-1,(d),在,(c),状态下再删除一个结点后的状态,-,空队列,X,队首、队尾指针,front rear,数组下标,0 1 2 3 MAXSIZE-1,(e),连续插入若干结点后的状态,-,此时队列呈现满的状态，但数组前部有空位子,D,E,队列的顺序存储结构的,C,语言描述如下：,/,/,/,队列（顺序存储）的头文件,/,/,文件名,seqqueue.h,/,/,/,#define MAXSIZE 100,typedef,int,datatype,;,typedef,struct,datatype,aMAXSIZE,;,int,front;,int,rear;,sequence_queue,;,顺序存储队列的几个基本操作的具体实现,:,/,/,/,函数功能,:,队列（顺序存储）初始化,/,/,函数参数,:,指向,sequence_queue,类型变量的指针变量,sq,/,/,函数返回值,:,空,/,/,文件名,:,seqqueue.c,函数名,:init(),/,/,