数据结构之线性结构和非线性结构

// 倒置线性表 public void Reverse() { T tmp = default(T); int len = GetLength() - 1; for (int i = 0; i <= len / 2; i++) { if (i.Equals(len - i)) { break; } tmp = data[i]; data[i] = data[len - i]; data[len - i] = tmp; } }

（2）链表（链式存储）

寻找物品的时候发现了一个问题，我们从一件物品找下一件物品的时候很容易，但是如果要找上一件物品就得从头开始找，真的很麻烦。为了解决这个问题我们又机智了一把，模仿之前的做法，在存放物品的时候多放置一个小纸条记录上一件物品的位置，这样就可以很快的找到上一件物品了。我们把这种方式我们称为双向链表，前面只放置一张小纸条的方式称为单向链表。

// 倒置单链表 public void Reverse() { Node<T> oldHead = Head; Node<T> tmp ; Head = null; //清空链表，解除Head跟oldHead之间的相同引用 while (oldHead != null) { tmp = Head; Head = oldHead; //解除Head跟oldHead之间的相同引用 oldHead = oldHead.Next; Head.Next = tmp; } }

由于数据存储结构不同导致使用场景上的巨大差异，顺序表由于元素连续具有随机存储的特点，所以查找数据很方便效率很高，但是插入、删除操作为了确保数据元素连续，需要移动大量的数据导致效率很低。而链表由于存储空间不要求连续，插入、删除只需修改相邻元素的引用域地址即可，所以效率很高，但查询需要从头引用开始遍历链表，效率很低。因此，如果只是进行查找操作而不经常插入、删除线性表中的数据元素，则使用顺序存储结构，反之，使用链式存储结构。

（3）栈

其实成功完成顺序表和链表之后，栈已经没太多可说的了，主要是逻辑上的不同，毕竟栈也是一种特殊的线性结构。栈是一种操作限定在表尾部进行的线性表，表尾称为栈顶（Top），另一端固定不动，称为栈底（Bottom）。进栈、出栈示意图如下：

//链栈入驻 public void Push(T item) { Node<T> tmp = new Node<T>(item); if (Top == null) { Top = tmp; } else { tmp.Next = Top; Top = tmp; } Num++; } //顺序栈入栈 public void Push(T item) { if (IsFull()) { throw new Exception("Stack is full"); } data[++Top] = item; }

（4）队列

队列与栈类似，仅仅是逻辑有一丢丢不同。队列是一种插入操作限定在表尾其他操作限定在表头的线性表。把进行插入操作的表尾称为队尾（Rear）,把进行其它操作的头部称为队首（Front）。入队、出队示意图如下：

//链队入队 public void In(T item) { Node<T> node = new Node<T>(item); if (Rear == null) { Rear = node; Front = Rear; } else { Rear.Next = node; Rear = Rear.Next; } ++num; } //循环队列入队 public void In(T item) { if (IsFull()) { throw new Exception("Queue is full"); } data[++Rear] = item; }

二、非线性结构

1、非线性结构的概念

树作为一种应用广泛的一对多非线性数据结构，不仅有数据间的指向关系，还有层级关系，示例见图一。因树的结构比较复杂，为了简化操作及存储，我们一般将树转换为二叉树处理，因此本文主要讨论二叉树。

（1）二叉树

二叉树是每个节点最多拥有两个子节点的树结构，若移除根节点则其余节点会被分成两个互不相交的子树，分别称为左子树和右子树。二叉树是有序树，左右子树有严格的次序，若颠倒则成为一棵不一样的二叉树。

（2）满二叉树

满二叉树，顾名思义除叶子节点外所有节点都拥有两个孩子，且叶子节点在同一层的二叉树，示例见图二。

（3）完全二叉树

完全二叉树，移除最后一层节点后是满二叉树，且最后一层的节点都连续集中在最左面，示例见图三。

2、二叉树存储结构

（1）顺序存储

根据完全二叉树的特性，可以计算出任意节点n的双亲节点及左右孩子节点的序号，因此完全二叉树的节点可以按照从上到下从左到右的顺序依次存储到一维数组中。非完全二叉树存储时应先将其改造为完全二叉树，以空替代不存在的节点，比较浪费存储空间，存储示意图见图四。

（2）链式存储

树结构链式存储类似线性结构链式存储，先定义包含数据域和引用域的节点(Node)，然后通过引用域存储节点之间的关系。根据二叉树的结构来看，节点Node至少包含数据域(Data)，引用域(左孩子LChild、右孩子RChild)，为了方便通过孩子节点查找父节点，引用域中可以考虑添加父节点引用(Parent)，存储示意图见图五。

3、树与二叉树的转换

（1）树转二叉树

加线，所有兄弟结点之间加一条连线。

抹线，对树中的每个结点，只保留他与第一个孩子结点之间的连线，删除它与其它孩子结点之间的连线。

整理，整理前两步得到的树，使之结构层次分明。

（2）二叉树转树

加线，若某结点的左孩子结点存在，将左孩子结点的右孩子结点、右孩子结点的右孩子结点……都作为该结点的孩子结点，将该结点与这些右孩子结点用线连接起来。

抹线，删除原二叉树中所有结点与其右孩子结点的连线。

整理，整理前两步得到的树，使之结构层次分明。

4、树遍历实现

/// <summary> /// 先序遍历（DLR） /// </summary> /// <![CDATA[首先访问跟节点，然后遍历左子树，最后右子树]]> static void PreOrder(Node<char> root) { if (root == null) { return; } Print(root); PreOrder(root.LChild); PreOrder(root.RChild); } /// <summary> /// 中序遍历（LDR） /// </summary> /// <![CDATA[先遍历左子树，然后根节点，最后遍历右子树]]> static void InOrder(Node<char> root) { if (root == null) { return; } InOrder(root.LChild); Print(root); InOrder(root.RChild); } /// <summary> /// 后序遍历（LRD） /// </summary> /// <![CDATA[先遍历左子树，然后遍历右子树，最后遍历根节点]]> static void PostOrder(Node<char> root) { if (root == null) { return; } PostOrder(root.LChild); PostOrder(root.RChild); Print(root); } /// <summary> /// 层序遍历 /// </summary> /// <![CDATA[从上向下从左到右]]> static void LevelOrder(Node<char> root) { if (root == null) { return; } CSeqQueue<Node<char>> sq = new CSeqQueue<Node<char>>(50); sq.In(root); while (!sq.IsEmpty()) { Node<char> tmp = sq.Out(); Print(tmp); if (tmp.LChild != null) { sq.In(tmp.LChild); } if (tmp.RChild != null) { sq.In(tmp.RChild); } } }

免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/140831.html