最近想回过头来看看以前写的一些代码，做的一些项目，可叹为何刚进大学的时候不知道要养成写博客的好习惯。现在好多东西都没有做记录，后面也没再遇到相同的问题，忘的都差不多了。只能勉强整理了下面写的一些笔记和代码，这些代码有的是参考别人的代码，但都是自己曾经一点点敲的，挂出来，虽然很基础，但希望能对别人有帮助。

                                                                                                                               ------Shawn

---

数据结构中最简单和基本的三中数据结构就是表（List），栈（Stack）和队列（Queue），并且，每一个有意义的程序都会使用至少一种这样的数据结构。这篇文章将简单介绍三种基本数据结构以及在C++上的实现。

1.表

有由A1,A2,...,AN组成的表，表的大小为N，称Ai−1是Ai的前驱，Ai+1是Ai的后继。大小为0的表为空表。

表ADT上的操作常见的包括：插入、删除、索引、查找、清空、打印。这是些基本的操作，根据需要可以再添加。

1.1表的数组实现

表可以用数组实现。但是用数组实现表时，需要对表的最大长度进行估计，如果表的长度变化较大，会浪费大量的空间。数组实现的表，索引为O(1)，插入和删除的最坏情况为O(N)，查找、清空和打印为O(N)。数组实现的表的插入和删除较慢，而且对表的大小还要有一定的了解，所以通常不用数组来实现表。

1.2链表

链表由一系列在内存中可以不相连的结构组成，每个结构含有表元素和指向后继结构的指针，最后一个结构的指针为NULL。为了避免删除操作的一些麻烦，一般在链表开始增加一个标志节点，称为表头，它不含有表元素。链表是一种非常基本的数据结构，被广泛的用在各种语言的集合框架中。

创建头节点

手动new一个新的Node，将Node的next置为NULL即可。

head = new Node(0);head->next = NULL;

从头插入一个新的节点

手动new出一个新的节点p，使p的next的指向head->next所指向的地址,然后将head->next从新指向p即可。

Node * p = new Node(int);  p->next = head->next;   head->next = p;

删除指定节点

先遍历到指定节点的前一个节点,然后通过将前一个节点的next指针指向指定节点的下一个节点,达到悬空指定节点的效果,然后删除指定节点即可。

修改指定节点

遍历到指定节点的位置,将其data修改为要修改的值即可。

链表反转

方法1：使用3个指针遍历单链表，逐个链接点进行反转。

定义三个临时节点指向头结点之后的第1个节点p,第2个节点q和第3个节点m。将p->next置为空,然后将q->next = p,然后将p向后移动一个节点,即p = q,最后将q向后移动一个节点,即q = m,最后把m向后移动一个节点,即m = m->next;依此类推直到m等于NULL,然后将q->next = p,最后将head->next指向q(即目前第一个节点疑,也就是原本最后的一个节点)。

通过三个节点达到从头开始逐个逆序的目的。

方法2：从第2个节点到第N个节点，依次逐节点插入到第1个节点(head节点)之后，最后将第一个节点挪到新表的表尾。

从图上观察，方法是：对于一条链表，从第2个节点到第N个节点，依次逐节点插入到第1个节点(head节点)之后，(N-1)次这样的操作结束之后将第1个节点挪到新表的表尾即可。

代码如下:

方法3： 递归

因为发现大部分问题都可以从递归角度想想，所以这道题目也从递归角度想了想。

现在需要把A->B->C->D进行反转，

可以先假设B->C->D已经反转好，已经成为了D->C->B,那么接下来要做的事情就是将D->C->B看成一个整体，让这个整体的next指向A，所以问题转化了反转B->C->D。那么，

可以先假设C->D已经反转好，已经成为了D->C,那么接下来要做的事情就是将D->C看成一个整体，让这个整体的next指向B，所以问题转化了反转C->D。那么，

可以先假设D(其实是D->NULL)已经反转好，已经成为了D(其实是head->D),那么接下来要做的事情就是将D(其实是head->D)看成一个整体，让这个整体的next指向C，所以问题转化了反转D。

上面这个过程就是递归的过程，这其中最麻烦的问题是，如果保留新链表的head指针呢？想到了两个办法。

1.3双链表

链表的倒序遍历效率不高，可以在每个结构上附加一个指向前一结构的指针，形成双链表。这增加了空间需求，也有更多的指针需要定位，但它简化了删除操作。