每个程序员必须知道的数据结构（程序员数据结构算法编程）

本文来讲单链表，主要讲它的结构定义、代码实现以及一些重要的操作。

首先，链表是一种链式存储结构，其特点是用一组任意的存储单元来存储数据元素，每个存储单元需要通过一定方式串联起来，那么这里需要引入节点的概念。一个节点表示链表中的一个数据元素，除了包括存储数据信息外，还需要包含下一个节点的指向信息，所以一个节点会包含数据域和指针域，数据域存储元素的数据信息，指针域指示直接后继的信息。如下图

那么结构体如下

struct node { int val; node *next; };

当然这里的数据域就一个整数值，也可以有更多的值，根据需要而定。另外，为了方便处理空表，通常在单链表前面会引入一个头节点，这个头结点的数据域可以不存放任何数据，如果将每个节点都连接起来，不难想象结构如下

下面实现单链表的定义以及各种常见的操作。

需要有头指针，临时指针变量p和q，分别表示当前节点和它的前驱节点，如下

node *head, *p, *q; void Init() { head = new node(); q = head; }

如果在单链表的尾部插入元素，那么需要创建一个新的节点，将新节点值赋值给数据域，修改其前驱节点的next，使其指向到当前节点，然后将前驱节点的指针后移，并将当前节点的指针域设置为空。代码如下

void Insert(int x) { p = new node(); p->val = x; q->next = p; q = p; q->next = NULL; }

上面这种插入方法叫做尾插法。

直接从链表头开始往后遍历，直接判断有无相等值存在即可。

bool Search(node *t,int x) { node *p = t; while(p != NULL) { if(p->val == x) return true; p = p->next; } return false; }

需要引入一个计数器来记录当前已经遍历到第几个元素了，当遍历元素达到k个，直接输出第k个节点的元素值。代码如下

int Find(node *t,int k) { int cnt = 1; node *p = t; p = t->next; while(p != NULL && (cnt < k)) { p = p->next; cnt ; } return p->val; }

若找到了要删除元素的节点，假如该节点为p，只需要将它的前驱节点的指针域指向p的后继节点，即q->next = p->next，如下图

代码如下

void Delete(node *t,int x) { node *q = t,*p; p = q->next; while(p != NULL && (p->val != x)) { q = p; p = p->next; } q->next = p->next; delete p; }

直接从head指针开始从前往后遍历即可。代码如下

void Print() { node *t = head; t = t->next; while(t != NULL) { printf("%d ", t->val); t = t->next; } printf("\n"); }

以上就是单链表的结构定义和基本操作。