C语言——链表

链表是一种基础的数据结构类型，一种能够动态维护数据的线性数据表。链表的数据以结点形式存储信息，并通过结点之间的指针实现结点之间的衔接。
为什么要用链表？
链表和数组类似，但是功能比数组强大得多，数组的空间是固定的，在定义数组的时候，数组的大小已经被固定，在使用时有可能会造成空间的浪费或者面临空间不够的风险，而链表的空间是动态的，则避免了这一问题。
我们来看最基础的单向链表：
1.首先要定义结构体作为链表的结点：

typedef struct node {int data;struct node * next;
} Node;

链表的每个结点就如图中所示，结点的两部分一部分用来存储要存储的数据，另一部分存储指向下一结点的指针。
2.初始化链表：
在链表的创建时，首先要创建链表的头结点

Node * InitList() {Node * head = (Node * )malloc(sizeof(Node));head->next = NULL;return head;
}

3.链表的尾插法：
将先插入的结点放在链表的尾部：

void CreatTail(Node *head) {Node * r, * newNode;r = head;int data;scanf("%d", &data);while (data != -1) {newNode = (Node * )malloc(sizeof(Node));newNode->data = data;newNode->next = r->next;r->next = newNode;r = newNode;scanf("%d", &data);}r->next = NULL;
}

每一次循环输入一次data，并把这个data存储在newNode结点中，此时要借助一个Node*r，r初始为head，让新插入的newNode所指向的next为原先r所指向的next（即为代码中的newNode->next = r->next;）；然后将newNode作为r的下一个结点。在输入结束后，此时r指向最后一个插入的newNode结点，将r->next赋值为NULL即可。
这是输入数据前的链表：

这是每一个结点插入时的过程：

4.链表的尾插法：

将先插入的结点放在链表的头部后面：

void CreatHead(Node *head) {Node *newNode;int data;scanf("%d", &data);while (data != -1) {newNode = (Node*)malloc(sizeof(Node));newNode->data = data;newNode->next = head->next;head->next = newNode;scanf("%d", &data);}
}

和尾插法类似，不过这一个每个插入的结点都在head的后面，而head是不改变的，因此省去了Node*r来指向每一次插入结点的前一个结点。

这是每一个结点插入时的过程：

5.链表的输出
将链表遍历一遍，逐个输出每一个结点的data

void print(Node *head) {Node *p;p = head->next;while (p) {printf(" %d\t ", p->data);p = p->next;}
}

6.链表的查找：
输入的x表示要查找链表的第x个结点的，如果存在就返回这个结点，不存在就返回NULL。

Node* FindNode(Node *head, int x) {Node *p = head;while (p && x >= 1) {p = p->next;x--;}if (!p) {printf("该节点不存在");return NULL;}else {return p;}
}

7.在指定的地方插入结点：
在第x个结点前插入含数据data的结点。

void Insert(Node *head, int x, int data) {Node *pre = FindNode(head, x - 1);if (pre == NULL) {printf("请输入正确的插入点");}Node *pNew = (Node *)malloc(sizeof(Node));pNew->data = data;pNew->next = pre->next;pre->next = pNew;
}

8.删除指定的结点：
删除指定的结点：

void Delete(Node *head, int x) {Node *pre = FindNode(head, x);Node *q = pre->next;pre->next = pre->next-next;free(q);
}

9.销毁整个链表
逐个遍历整个链表，free掉除头结点外所有的结点

void DestoryList(Node *head) {Node *p = head->next;Node *q = p;while (p) {p = p->next;free(q);q = p;}head->next = NULL;
}

以上为链表的基本操作，除此之外，链表的应用也同样重要：
接下来我们来看反转链表和合并链表：
反转链表：
顾名思义，就是将链表反过来，能够反转链表的方法有很多，最常用的方法是三指针方法。
定义三个指针分别指向空指针，头结点的下一位，第二个指针的下一位。
代码如下：

void reverseList (Node *head) {    //三指针法if (head == NULL || head->next == NULL) {return head;}Node *p = NULL;Node *q = head->next;Node *next ;while (q != NULL) {next = q->next;q->next = p;p = q;q = next;}head->next=p;
}