3、的连续单元中。在表头或中间插入或册除元素都要移动元素，移动多少个。3、用指针表示的线性表structcelltype{Elementtypeelements;celltype*next;};用指针把表中的各个元素（称结点）依次链接起来，形成一个单向链表。在链表中插入或册除结点都不要移动结点，移动多少个。15不带头结点的单链表h:h…..^不带头结点的单链表h为空的判定条件是:h=NULL带头结点的单链表h:h…..^带头结点的单链表h为空的判定条件是:h->next=NULL二、栈1、栈的定义栈是
4、一种特殊的线性表，栈是一种只能在叫做栈顶的一端进行进栈或出栈操作的线性数据结构。栈的特点是“后进先出”。例1、已知一个字符串，次序为3*-y-a/y^2，试利用栈写出把该串的次序改为3y-*ay2^/-的操作步骤。15例2、有6个元素a,b,c,d,e依次进栈，允许任何时候出栈，能否得到下列的每个出栈序列，若能，给出栈操作的过程，若不能，简述其理由。（1）edcba(2)decba(3)dceab(4)abcde解：对于（1）a,b,c,d,e进栈，e,d,c,b,a出栈。对于（2）a,b,c,d
5、进栈，d出栈,e进栈，e,c,b,a出栈。对于（3）a,b,c,d进栈，d出栈,c出栈,e进栈,e出栈,此时栈中，栈底是a,栈顶是b，不可能a先出栈，所以（3）是不可能是出栈序列。对于（4）a进栈,a出栈,b进栈,b出栈,c进栈,c出栈,d进栈,d出栈,e进栈，e出栈。2、栈的表示（1）用数组表示栈栈的结构体：typedefstruct{inttop;elementtypeelements[maxlength];}STACK;STACKS;栈的容量：maxlength–1;栈空：S.top=max
6、length;栈满：S.top=0;栈顶元素：S.elements[S.top];（2）用指针表示栈15栈的结构体：structnode{Elementtypeval;node*next;};typedefnode*STACK;三、队列1、队列的定义队列是一种特殊的线性表，只允许在表的一端进行插入，另一端进行删除。在表的一端进行插入的一端叫队列的尾；在表的一端进行删除的一端叫队列的头。队列的特点是先进先出。例1，一个队列的入队列序列是1，2，3，4，则队列的输出序列是1，2，3，4。2、队列的表示
7、用指针表示队列structcelltype{elementtypeelement；celltype*next；}注意：栈和队列的共同点是只允许在端点处插入和删除元素。15四、广义表一个广义表是n(n³0)个元素的一个有限序列。n是广义表的长度。当n=0时称为空表。若(a1,a2,…,an)表示广义表，则(a1)表示广义表的头，(a2,…,an)表示广义表的尾。广义表的长度指该广义表中所包含的元素的个数。广义表的深度指该广义表中所包含括号的层数。例、广义表((a,b),c,d)的表头是(a,b)，表
8、尾是(c,d)。第3章树一、树1、基本概念树具有层次结构。树是n(n>0)个结点的有限集合T，在一棵树中满足如下两个条件：（1）有且仅有一个根结点；（2）其余的结点可分为m(m>0)棵互不相交的有限集合T1，T2，…,15Tm,其中每个集合Ti又都是一棵树。结点的度：树中每个结点具有的子树。树的度：树中所有结点的度的最大值。叶子：度为0的结点。结点的层数：根结点为第一层，其孩子结点为第二层，如此类推得到每个结点的层数。树的深度：树中结点的最大层数。森林：0个或多个不相交的树的集合。
