一、初始化
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;
}
通过上面的基本操作可知:
- 在单链表上插入、删除一个结点,必须知道其前驱结点的指针;
- 单链表不具有按序号随机访问的特点,只能从头指针开始一个个顺次进行。