软件设计师 http://www.educity.cn/jiaocheng/zg7.html
若链表的首结点的值为指定值，更改链表的头指针为指向首结点的后继结点； 在链表中寻找指定值的结点； 将找到的结点删除。
1.1.1 栈
栈是一种特殊的线性表，栈只允许在同一端进行插入和删除运算。允许插入和删除的一端称为栈顶，另一端为栈底。称栈的结点插入为进栈，结点删除为出栈。因为最后进栈的结点必定最先出栈，所以栈具有后进先出的特征。 1.顺序存储
可以用顺序存储线性表来表示栈，为了指明当前执行插入和删除运算的栈顶位置，需要一个地址变量 top指出栈顶结点在数组中的下标。 2.链接存储栈
栈也可以用链表实现，用链表实现的栈称为链接栈。链表的第一个结点为顶结点，链表的首结点就是栈顶指针top,top为NULL的链表是空栈。
1.1.2 队列
队列也是一种特殊的线性表，只允许在一端进行插入，另一端进行删除运算。允许删除运算的那一端称为队首，允许插入运算的一端称为队尾。称队列的结点插入为进队，结点删除为出队。因最先进入队列的结点将最先出队，所以队列具有先进先出的特征。 1.顺序存储
可以用顺序存储线性表来表示队列，为了指明当前执行出队运算的队首位置，需要一个指针变量head（称为头指针），为了指明当前执行进队运算的队尾位置，也需要一个指针变量tail（称为尾指针）。
软件设计师 http://www.educity.cn/jiaocheng/zg7.html
若用有N个元素的数组表示队列，随着一系列进队和出队运算，队列的结点移向存放队列的数组的尾端，会出现数组的前端空着，而队列空间已用完的情况。一种可行的解决办法是当发生这样的情况时，把队列中的结点移到数组的前端，修改头指针和尾指针。另一种更好的解决办法是采用循环队列。
循环队列就是将实现队列的数组a[N]的第一个元素a[0]与最后一个元素a[N–1]连接起来。队空的初态为 head=tail=0.在循环队列中，当tail 赶上head时，队列满。反之，当head赶上tail时，队列变为空。这样队空和队满的条件都同为head=tail,这会给程序判别队空或队满带来不便。因此，可采用当队列只剩下一个空闲结点的空间时，就认为队列已满的简单办法，以区别队空和队满。即队空的判别条件是head=tail,队满的判别条件是head=tail+1。 2.链接存储
队列也可以用链接存储线性表实现，用链表实现的队列称为链接队列。链表的第一个结点是队列首结点，链表的末尾结点是队列的队尾结点，队尾结点的链接指针值为NULL.队列的头指针head 指向链表的首结点，队列的尾指针tail指向链表的尾结点。当队列的头指针head值为NULL时，队列为空。
1.1.3 稀疏矩阵
在计算机中存储一个矩阵时，可使用二维数组。例如，M×N阶矩阵可用一个数组a[M][N]来存储（可按照行优先或列优先的顺序）。如果一个矩阵的元素绝大部分为零，则称为稀疏矩阵。若直接用一个二维数组表示稀疏矩阵，则会因存储太多的零元素而浪费大量的内存空间。因此，通常采用三元组数组或十字链表两种方法来存储稀疏矩阵。 1.三元组数组
软件设计师 http://www.educity.cn/jiaocheng/zg7.html
稀疏矩阵的每个非零元素用一个三元组来表示，即非零元素的行号、列号和它的值。然后按某种顺序将全部非零元素的三元组存于一个数组中。
如果只对稀疏矩阵的某些单个元素进行处理，则宜用三元组表示。 2.十字链表
在十字链表中，矩阵的非零元素是一个结点，同一行的结点和同一列的结点分别顺序循环链接，每个结点既在它所在行的循环链表中，又在它所在列的循环链表中。每个结点含5个域，分别为结点对应的矩阵元素的行号、列号、值，以及该结点所在行链表后继结点指针、所在列链表后继结点指针。
为了处理方便，通常对每个行链表和列链表分别设置一个表头结点，并使它们构成带表头结点的循环链表。为了引用某行某列的方便，全部行链表的表头结点和全部列链表的表头结点分别组成数组，这两个数组的首结点指针存于一个十字链表的头结点中，最后由一个指针指向该头结点。
例如有矩阵A如图1-1所示。 则其十字链表如图1-2所示。
图1-1 矩阵A示意图图1-2
软件设计师 http://www.educity.cn/jiaocheng/zg7.html
矩阵A十字链表存储示意图
如果对稀疏矩阵某行或某列整体做某种处理，可能会使原来为零的元素变为非零，而原来非零的元素变成零。对于这种场合，稀疏矩阵宜用十字链表来表示。
1.1.4 字符串
字符串是由某字符集上的字符所组成的任何有限字符序列。当一个字符串不包含任何字符时，称它为空字符串。一个字符串所包含的有效字符个数称为这个字符串的长度。一个字符串中任一连续的子序列称为该字符串的子串。
字符串通常存于足够大的字符数组中，每个字符串的最后一个有效字符之后有一个字符串结束标志，记为\通常由系统提供的库函数形成的字符串的末尾会自动添加\但当由用户的应用程序来形成字符串时，必须由程序自行负责在最后一个有效字符之后添加\以形成字符串。
对字符串的操作通常有： 统计字符串中有效字符的个数；
软件设计师 http://www.educity.cn/jiaocheng/zg7.html
把一个字符串的内容复制到另一个字符串中；
把一个字符串的内容连接到另一个足够大的字符串的末尾； 在一个字符串中查找另一个字符串或字符；
按字典顺序比较两个字符串的大小。
1.2 树和二叉树
1.2.1 树 1.树的基本概念
树是由一个或多个结点组成的有限集合T,它满足以下两个条件： （1）有一个特定的结点，称为根结点；
（2）其余的结点分成m（m≥0）个互不相交的有限集合。其中每个集合又都是一棵树，称 T1,T2,…，
Tm–1为根结点的子树。
显然，以上定义是递归的，即一棵树由子树构成，子树又由更小的子树构成。由条件（1）可知，一棵树至少有一个结点（根结点）。一个结点的子树数目称为该结点的度（次数），树中各结点的度的最大值称为树的度（树的次数）。度为0的结点称为叶子结点（树叶），除叶子结点外的所有结点称为分支结点，根以外的分支结点称为内部结点。例如，在图1-3所示的树中，根结点的度数为3,结点2的度数为4,结点4的度数为1,结点9的度数为2,其他结点的度数为0,该树的度数4。