Tim的资源站一、初始化
void Link::Initiate() {
DeleteAll();
head = NULL;
}
二、建立单链表
（一）从表尾到表头建立单链表（不带有空白头结点）
链表与顺序表不同，它是一种动态管理的存储结构，链表中的每个结点占用的存储空间不是预先分配的，而是在运行时系统根据需求动态生成的，因此建立单链表应该从空表开始。
可以在每读入一个数据元素后申请一个结点，然后插在链表的头部（从表尾到表头建立单链表）。
下图体现了线性表（20，50，10，80，40）的链式存储结构的建立过程。因为是在链表的头部插入，读入数据的顺序和线性表中的逻辑顺序是相反的。
从表尾到表头建立单链表
算法实现如下：
void Link::HeadCreate(int n) {
DeleteAll();
Item *s, *p;
int i;
p = NULL;
for(i = 1; i <= n; i++) {
s = new Item();
cin >> s->data;
s->next = p;
p = s;
}
head = p;
}
（二）从表头到表尾建立单链表（不带有空白结点）
从表尾到表头插入结点建立单链表比较简单，但读入的数据元素的顺序与生成的单链表中元素的顺序是相反的。若希望次序一致，则用从表头到表尾建立单链表的方法。因为每次是将新结点插入链表的尾部，所以需加入一个指针 r 用来始终指向链表中的尾结点，以便能够将新结点插入链表的尾部。
初始状态：头指针 P=NULL，尾指针 r=NULL。按线性表中元素的顺序依次读入数据元素，只要不是结束标志，即申请结点，并将新结点插入 r 所指结点的后面，然后 r 指向新结点（但第一个结点有所不同，注意下面算法中的有关部分）。
从表头到表尾建立单链表
算法实现如下：
void Link::TailCreate(int n) {
DeleteAll();
Item *s,*r,*p;
int i;
p = NULL;
for (i = 1; i <= n; i++) {
s = new Item();
cin >> s->data;
s->next = NULL;
if (p == NULL) p = r = s;
else {
r->next = s;
r = s;
}
}
head = p;
}
在上面的算法中，第一个结点的处理和其他结点是不同的，原因是第一个结点加入前链表为空，它没有直接前驱结点，它的地址就是整个链表的指针，需要放在链表的头指针变量中；而其他结点有直接前驱结点，其地址放入直接前驱结点的指针域。
「第一个结点」的问题在很多操作中都会遇到。在链表中插入结点时，将结点插在第一个位置和其他位置是不同的；在链表中删除结点时，删除第一个结点和删除其他结点的处理也是不同的；为了方便操作，有时在链表的头部加入一个空白的「头结点」，头结点的类型与数据结点一致，数据域为空，在标识链表的头指针变量 H 中存放该结点的地址。这样即使是空表，头指针变量 H 也不再为空了。头结点的加入使得「第一个结点」的问题不再存在，也使得「空表」和「非空表」的处理成为一致。
带空白头结点的单链表为空表和非空表
（三）从表尾到表头建立单链表（带有空白头结点）
void Link::HeadCreateWithHead(int n) {
DeleteAll();
Item *s,*p;
int i;
p = new Item();
p->next = NULL;
for(i = 1; i <= n; i++) {
s = new Item();
cin >> s->data;
s->next = p->next;
p->next = s;
}
head= p;
}
（四）从表头到表尾建立单链表（带有空白头结点）
void Link::TailCreateWithHead(int n) {
DeleteAll();
Item *s,*r,*p;
int i;
p = new Item();
p->next = NULL;
r = p;
for(i = 1; i <= n; i++) {
s = new Item();
cin >> s->data;
r->next = s;
r = s;
}
r->next = NULL;
head = p;
}
从上面 4 个算法可以看出，对于不带空白头结点的单链表，空表情况下需要单独处理，而带上空白头结点之后则不用了，算法的时间复杂度均为 O（n）。在以后的单链表算法中，如不加说明则认为单链表是带空白头结点的。
三、求表长
顺序表的表长可以方便获得。相比而言，求单链表的表长稍微复杂些。设有一个移动指针 p 和计数器 j，初始化后，p 所指结点后面若还有结点，p 向后移动，计数器加 1。
算法实现如下：
int Link::Length() {
int j;
Item *p;
j = 1;
p = head->next;
while(p != NULL) {
j++;
p = p->next;
}
return --j;
}
上述算法的时间复杂度为O（n）。
四、查找操作
（一）按序号查找
从单链表的第一个元素结点起，判断当前结点是否是第 i 个，若是，则返回该结点的指针；否则继续下一个结点的查找，直到表结束为止。若没有第 i 个结点，则返回空；如果 i=0；则返回头指针。
算法实现如下，其时间复杂度为O（n）：
Item * Link::Locatei(int i) {
int j = 1;
Item *p;
if (i == 0) return head;
p = head->next;
while((p != NULL) && (j < i)) {
p = p->next;
j++;
}
if (j == i)
return p;
else {
cout << "position is not correct!" << endl;
return NULL;
}
}
（二）按值查找（定位）
从链表的第一个元素结点起，判断当前结点值是否等于 x，若是，返回该结点的指针，否则继续下一个结点的查找，直到表结束为止。若找不到，则返回空。
算法实现如下，其时间复杂度为O（n）：
Item * Link::Locatex(DataType x) {
Item *p;
p = head->next;
while ((p != NULL) && (p->data != x))
p = p->next;
if (p)
return p;
else {
cout << x << " is not exist!" << endl;
return NULL;
}
}
（三）读取第 i 个位置上的元素值
算法实现如下，其时间复杂度为O（n）：
DataType Link::Get(int i) {
int j;
Item *p;
j = 1;
p = head->next;
while((j < i) && (p != NULL)) {
j++;
p = p->next;
}
if ((p == NULL) || (j > i)) {
cout << "position is not correct!" << endl;
return NULL;
} else
return p->data;
}
五、插入
（一）后插结点
设 p 指向单链表中某结点，s 指向待插入的值为 x 的新结点，将*s插入*p的后面，插入示意图如上图（a）所示：
代码操作顺序为：
s->next = p->next;p->next = s;
（二）前插结点
设 p 指向链表中某结点，s 指向待插入的值为 x 的新结点，将*s插入*p的前面，插入示意图如上图（b）所示。
与后插不同的是，首先要找到*p的前驱*q，再完成在*q之后插入*s。设单链表头指针为 L，操作如下：
q=L;
while(q->next != p)
q = q->next； //找*p 的直接前驱
s->next = q->next;
q->next = s;
后插操作的时间复杂度为 O(1)，前插操作因为要找*p的前驱，时间复杂度为 O（n）。其实，我们关心的是数据元素之间的逻辑关系，所以仍然可以将*s插入*p的后面，然后将 p->data 与 s->data 交换即可。这样既满足了逻辑关系，也能使得时间复杂度为 O(1)。
（三）插入算法
-
找到第 i-1 个结点；若存在，继续步骤2，否则结束。
-
申请新结点，将数据填入新结点的数据域。
-
将新结点插入。
前插结点算法如下：
bool Link::Insert(DataType x, int i) {
Item *p, *s;
p = Locatei(i-1);
if(p == NULL) {
cout << "position is not correct!" << endl;
return false;
}
s = new Item();
s->data = x;
s->next = p->next;
p->next = s;
return true;
}
六、删除
单列表删除结点示意图：
（一）删除结点
设p指向单链表中某结点，删除*p。操作示意图如上所示。通过示意图可见，要实现对结点*p的删除，首先要找到*p的前驱结点*q，然后完成指针的删除操作即可。指针的操作，由下列语句实现。
q->next = p->next;
delete p;
显然，找*p前驱的时间复杂度为 O（n）。
若要删除*p的后继结点（假设存在），则可以直接完成：
s = p->next;
p->next = s->next;
delete s;
该操作的时间复杂度为 O(1)。
（二）删除运算
-
找到第 i-1 个结点，若存在，继续步骤 2，否则结束。
-
若存在第 i 个结点，则继续步骤 3，否则结束。
-
删除第 i 个结点，结束。
算法实现如下，其时间复杂度为O（n）：
bool Link::Deleted(int i) {
Item *p = Locatei(i-1);
Item *q;
if (p == NULL) {
cout << "position is not correct!" << endl;
return false;
}
q = p->next;
if (q != NULL) {
p->next = q->next;
delete q;
return true;
} else {
cout << "position is not correct!" << endl;
return false;
}
}
七、打印
void Link::Print() {
Item *p;
p = head->next;
while (p! = NULL) {
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
八、删除所有结点
void Link::DeleteAll() {
Item *p = head, *q;
while (p != NULL) {
q = p->next;
delete p;
p = q;
}
head = NULL;
}
通过上面的基本操作可知：
- 在单链表上插入、删除一个结点，必须知道其前驱结点的指针；
- 单链表不具有按序号随机访问的特点，只能从头指针开始一个个顺次进行。
