几种数据存储结构详解

附注说明：上图中删完尾节点之后，新链表的尾节点下标应为n-1。不过由于作图时只做了尾节点，故用图中的n2节点代替。

删除尾节点的代码如下：

if(p->next == NULL) /***p指向链表中的某一节点***/ { q->next = NULL; /***q指向链表中的p节点的前一节点**/ }
③. 删除非头尾节点，如图

删除非头尾节点的代码如下：

q->next = p->next; /***p指向链表中的某一节点，q指向链表中的p节点的前一节点***/
4.查询节点：在链表中找到你想要找的那个节点。此操作是根据数据域的内容来完成的。查询只能从表头开始，当要找的节点的数据域内容与当前不相符时，只需让当前节点指向下一结点即可，如此这样，直到找到那个节点。

附注：此操作就不在这用图和代码说明了。

5.修改节点：修改某个节点数据域的内容。首先查询到这个节点，然后对这个节点数据域的内容进行修改。
附注：同上

ok，链表的几种操作介绍完了，接下来我们来总结一下链表的几个特点。

链式存储结构的特点：
1.易插入，易删除。不用移动节点，只需改变节点中指针的指向。
2.查询速度慢：每进行一次查询，都要从表头开始，速度慢，效率低。

扩展阅读
链表：http://public.whut.edu.cn/comptsci/web/data/512.htm

第二节 树形存储结构

所谓树形存储结构，就是数据元素与元素之间存在着一对多关系的数据结构。在树形存储结构中，树的根节点没有前驱结点，其余的每个节点有且只有一个前驱结点，除叶子结点没有后续节点外，其他节点的后续节点可以有一个或者多个。

如下图就是一棵简单的树形结构：

说到树形结构，我们最先想到的就是二叉树。我们常常利用二叉树这种结构来解决一些算法方面的问题，比如堆排序、二分检索等。所以在树形结构这节我只重点详解二叉树结构。那么二叉树到底是怎样的呢？如下图就是一颗简单的二叉树：

附注：有关树的概念以及一些性质在此不做解释，有意者请到百科一览。

二叉树的类型描述如下：

typedef struct tree { char data; struct tree * lchild,* rchild; /***左右孩子指针***/ }tree;
二叉树的操作：创建节二叉树，创建节点，遍历二叉树，求二叉树的深度。

1.创建二叉树：声明一棵树并为其申请存储空间。

struct tree * T = NULL; T = (struct tree *)malloc(sizeof(struct tree));
2.创建节点：除根节点之外，二叉树的节点有左右节点之分。

创建节点的代码如下：

struct tree * createTree() { char NodeData; scanf(" %c",&NodeData); if(NodeData == '#') return NULL; else { struct tree * T = NULL; T = (struct tree *)malloc(sizeof(struct tree)); T->data = NodeData; T->lchild = createTree(); T->rchild = createTree(); return T; } }
3.遍历二叉树：分为先序遍历、中序遍历、后续遍历。

①.先序遍历：若二叉树非空，则依次执行如下操作：
(1) 访问根结点；
(2) 遍历左子树；
(3) 遍历右子树。

如图：

先序遍历的代码如下：

void PreTravser(struct tree * T) { if(T == NULL) return; else { printf("%c",T->data); PreTravser(T->lchild); PreTravser(T->rchild); } }
②.中序遍历：若二叉树非空，则依次执行如下操作：
(1)遍历左子树；
(2)访问根结点；
(3)遍历右子树。
如图：

中序遍历的代码如下：

void MidTravser(struct tree * T) { if(!T) { return; } else { MidTravser(T->lchild); printf("%c",T->data); MidTravser(T->rchild); } }
③.后续遍历：若二叉树非空，则依次执行如下操作：
(1)遍历左子树；
(2)遍历右子树；
(3)访问根结点。
如图：