数据结构 第4讲 单链表
链表是线性表的链式存储方式，逻辑上相邻的数据在计算机内的存储位置不一定相邻，那么怎么表示逻辑上的相邻关系呢？可以给每个元素附加一个指针域，指向下一个元素的存储位置。如图所示：
从图中可以看出，每个结点包含两个域：数据域和指针域，指针域存储下一个结点的地址，因此指针指向的类型也是结点类型。
结点结构体的定义：
定义了结点之后，我们就可以把若干个结点连接在一起，形成一个链表：
是不是像一个铁链子，一环扣一环的连在一起？
不管这个铁链子有多长，只要我们找到它的头，就可以拉起整个铁链子，因此我们给这个链表设置一个头指针，这个链表中的每个结点都可以找到了。
有时候为了操作方便，我们还会给链表增加一个不存放数据的头结点：
就像是给铁链子加个钥匙扣：
我们可以看到刚才的链表每个指针都是指向下一个结点，都是朝向一个方向的，这样的链表称为单向链表，或单链表。
在顺序表中，想找第i个元素，就可以立即通过L.elem[i-1]找到，称为随机存取方式，而在单链表中，想找第i个元素？没那么容易，必须从头开始，按顺序一个一个来，一直数到第i个元素，称为顺序存取方式。
下面以带头结点的单链表为例，讲解单链表的初始化、创建、取值、查找、插入、删除操作。
1. 单链表初始化
单链表初始化是指构建一个空表：
bool InitList_L(LinkList &L)//构造一个空的单链表L
{
L=new LNode; //生成新结点作为头结点，用头指针L指向头结点
if(!L)
return false; //生成结点失败
L->next=NULL; //头结点的指针域置空
return true;
}
2. 单链表的创建
创建单链表分为前插法和尾插法两种，前插法创建的单链表和输入顺序正好相反，因此称为逆序建表，尾插法创建的单链表和输入顺序一致，因此称为正序建表。
前插法建表如图：
初始状态
输入数据元素1，创建新结点，把元素1放入新结点数据域：
s=new LNode; //生成新结点s
cin>>s->data; //输入元素值赋给新结点的数据域
前插操作，插入到头结点的后面：
输入数据元素2，创建新结点，把元素2放入新结点数据域：
前插操作，插入到头结点的后面：
解释：
为什么要先修改后面那个指针呢？
因为一旦修改了L结点的指针域指向s，那么原来L结点后面的结点就找不到了，
注意：修改指针顺序的原则：先修改没有指针标记的那一端。
如果要插入结点的两端都有标记，例如再定义一个指针q指向第1个结点，那么先修改哪个指针都无所谓了。
拉直链表之后：
继续依次输入数据元素3，4，5，6，7，8，9，10，前插法创建链表的结果：
void CreateList_H(LinkList &L)//前插法创建单链表
{
int n; //输入n个元素的值，建立到头结点的单链表L
LinkList s; //定义一个指针变量
L=new LNode;
L->next=NULL; //先建立一个带头结点的空链表
cout <<"请输入元素个数n：" <
cin>>n;
cout <<"请依次输入n个元素：" <
cout <<"前插法创建单链表..." <
while(n--)
{
s=new LNode; //生成新结点s
cin>>s->data; //输入元素值赋给新结点的数据域
s->next=L->next;
L->next=s; //将新结点s插入到头结点之后
}
}
尾插法建表如图：
初始状态(尾插法需要一个尾指针永远指向链表的尾结点)
输入数据元素1，创建新结点，把元素1放入新结点数据域：
s=new LNode; //生成新结点s
cin>>s->data; //输入元素值赋给新结点的数据域
尾插操作，插入到尾结点的后面：
解释：
输入数据元素2，创建新结点，把元素2放入新结点数据域：
尾插操作，插入到尾结点的后面：
继续依次输入数据元素3，4，5，6，7，8，9，10，前插法创建链表的结果：
void CreateList_R(LinkList &L)//尾插法创建单链表
{
//输入n个元素的值，建立带表头结点的单链表L
int n;
LinkList s, r;
L=new LNode;
L->next=NULL; //先建立一个带头结点的空链表
r=L; //尾指针r指向头结点
cout <<"请输入元素个数n：" <
cin>>n;
cout <<"请依次输入n个元素：" <
cout <<"尾插法创建单链表..." <
while(n--)
{
s=new LNode;//生成新结点
cin>>s->data; //输入元素值赋给新结点的数据域
s->next=NULL;
r->next=s;//将新结点s插入尾结点r之后
r=s;//r指向新的尾结点s
}
}
3. 单链表取值
单链表的取值不像顺序表那样可以随机访问任何一个元素，单链表只有头指针，各个结点的物理地址是不连续的，要想找到第i个结点，就必须从第一个结点开始按顺序往后数，一直数到第i个结点。
那么具体怎么做呢？
注意：链表的头指针不可以随意改动！一个链表是由头指针来标识的，一旦头指针改动或丢失，这个链表就不完整或找不到了。想想看，你拉着铁链子一头，另一端绑着水桶，到井里打水，你手一松，链子掉井里，找不到了。所以链表的头指针是不能随意改动的，如果需要用指针移动，可定义一个指针变量进行移动。
可以定义一个p指针，指向第一个元素结点，用j作为计数器，j=1；
然后p指向p的下一个结点，即：
p=p->next; //p指向下一个结点
j++; //计数器j加1
直到p为空或者j=i停止，p为空说明没有数到i，链表就结束了，j=i说明找到了第i个结点。
bool GetElem_L(LinkList L, int i, int &e)//单链表的取值
{
//在带头结点的单链表L中查找第i个元素
//用e记录L中第i个数据元素的值
int j;
LinkList p;
p=L->next; //p指向第一个数据结点
j=1; //j为计数器
while (j
{
p=p->next; //p指向下一个结点
j++; //计数器j相应加1
}
if (!p || j>i)
return false; //i值不合法i＞n或i<=0
e=p->data; //取第i个结点的数据域
return true;
}
4. 单链表查找
在一个单链表中查找是否存在元素e，可以定义一个p指针，指向第一个元素结点，比较p指向结点的数据域是否为e，如果相等，查找成功返回true，如果不等，则p指向p的下一个结点，即：
p=p->next; //p指向下一个结点
继续比较，如果p为空，查找失败返回false。
bool LocateElem_L(LinkList L, int e) //在带头结点的单链表L中查找值为e的元素
{
LinkList p;
p=L->next;
while (p && p->data!=e)//沿着链表向后扫描，直到p空或p所指结点数据域等于e
p=p->next; //p指向下一个结点
if(!p)
return false; //查找失败p为NULL
return true;
}
5. 单链表插入
如果要在第i个结点之前插入一个元素，则必须先找到第i-1个结点，想一想：为什么？
单链表只有一个指针域，是向后操作的，不可以向前处理，第i个结点之前插入一个元素相当于把新结点放在第i-1个结点和第i个结点之间。
解释：
是不是有似曾相识的感觉？
前面讲的前插法建链表，就是每次将新结点插入到头结点和第一个结点之间。
bool ListInsert_L(LinkList &L, int i, int &e)//单链表的插入
{
//在带头结点的单链表L中第i个位置插入值为e的新结点
int j;
LinkList p, s;
p=L;
j=0;
while (p&&j
{
p=p->next;
j++;
}
if (!p || j>i-1) //i＞n+1或者i＜1
return false;
s=new LNode; //生成新结点
s->data=e; //将新结点的数据域置为e
s->next=p->next; //将新结点的指针域指向结点ai
p->next=s; //将结点p的指针域指向结点s
return true;
}
6. 单链表删除
删除一个结点，实际上是把这个结点跳过去。如图：
要想跳过第i个结点，就必须先找到第i-1个结点，否则是无法跳过去的。
p->next=q->next；含义是将q结点的下一个结点地址赋值给p结点的指针域。在这些有关指针的赋值语句中，很多同学不理解，容易混淆，在此说明一下，等号的右侧是结点的地址，等号的左侧是结点的指针域：
q结点的下一个结点地址存储在q->next里面，等号右侧的q->next就相当于把q结点的下一个结点地址读出来，赋值给p结点的next指针域，这样，就把q结点跳过去了。然后用delete q释放被删除结点的空间。
bool ListDelete_L(LinkList &L, int i) //单链表的删除
{
//在带头结点的单链表L中，删除第i个位置
LinkList p, q;
int j;
p=L;
j=0;
while((p->next)&&(j
{
p=p->next;
j++;
}
if (!(p->next)||(j>i-1))//当i>n或i<1时，删除位置不合理
return false;
q=p->next; //临时保存被删结点的地址以备释放空间
p->next=q->next; //改变删除结点前驱结点的指针域
delete q; //释放被删除结点的空间
return true;
}
单链表基本操作完整代码：
完整代码：
#include
#include
#include
#include
using namespace std;
typedef struct LNode {
int data; //结点的数据域
struct LNode *next; //结点的指针域
}LNode, *LinkList; //LinkList为指向结构体LNode的指针类型
bool InitList_L(LinkList &L)//构造一个空的单链表L
{
L=new LNode; //生成新结点作为头结点，用头指针L指向头结点
if(!L)
return false; //生成结点失败
L->next=NULL; //头结点的指针域置空
return true;
}
void CreateList_H(LinkList &L)//前插法创建单链表
{
//输入n个元素的值，建立到头结点的单链表L
int n;
LinkList s; //定义一个指针变量
L=new LNode;
L->next=NULL; //先建立一个带头结点的空链表
cout <<"请输入元素个数n：" <
cin>>n;
cout <<"请依次输入n个元素：" <
cout <<"前插法创建单链表..." <
while(n--)
{
s=new LNode; //生成新结点s
cin>>s->data; //输入元素值赋给新结点的数据域
s->next=L->next;
L->next=s; //将新结点s插入到头结点之后
}
}
void CreateList_R(LinkList &L)//尾插法创建单链表
{
//输入n个元素的值，建立带表头结点的单链表L
int n;
LinkList s, r;
L=new LNode;
L->next=NULL; //先建立一个带头结点的空链表
r=L; //尾指针r指向头结点
cout <<"请输入元素个数n：" <
cin>>n;
cout <<"请依次输入n个元素：" <
cout <<"尾插法创建单链表..." <
while(n--)
{
s=new LNode;//生成新结点
cin>>s->data; //输入元素值赋给新结点的数据域
s->next=NULL;
r->next=s;//将新结点s插入尾结点r之后
r=s;//r指向新的尾结点s
}
}
bool GetElem_L(LinkList L, int i, int &e)//单链表的取值
{
//在带头结点的单链表L中查找第i个元素
//用e记录L中第i个数据元素的值
int j;
LinkList p;
p=L->next;//p指向第一个结点，
j=1; //j为计数器
while (j
{
p=p->next; //p指向下一个结点
j++; //计数器j相应加1
}
if (!p || j>i)
return false; //i值不合法i＞n或i<=0
e=p->data; //取第i个结点的数据域
return true;
}
bool LocateElem_L(LinkList L, int e) //按值查找
{
//在带头结点的单链表L中查找值为e的元素
LinkList p;
p=L->next;
while (p && p->data!=e)//顺链域向后扫描，直到p为空或p所指结点的数据域等于e
p=p->next; //p指向下一个结点
if(!p)
return false; //查找失败p为NULL
return true;
}
bool ListInsert_L(LinkList &L, int i, int &e)//单链表的插入
{
//在带头结点的单链表L中第i个位置插入值为e的新结点
int j;
LinkList p, s;
p=L;
j=0;
while (p&&j
{
p=p->next;
j++;
}
if (!p || j>i-1)//i＞n+1或者i＜1
return false;
s=new LNode; //生成新结点
s->data=e; //将新结点的数据域置为e
s->next=p->next; //将新结点的指针域指向结点ai
p->next=s; //将结点p的指针域指向结点s
return true;
}
bool ListDelete_L(LinkList &L, int i) //单链表的删除
{
//在带头结点的单链表L中，删除第i个位置
LinkList p, q;
int j;
p=L;
j=0;
while((p->next)&&(j
{
p=p->next;
j++;
}
if (!(p->next)||(j>i-1))//当i>n或i<1时，删除位置不合理
return false;
q=p->next; //临时保存被删结点的地址以备释放空间
p->next=q->next; //改变删除结点前驱结点的指针域
delete q; //释放被删除结点的空间
return true;
}
void Listprint_L(LinkList L) //单链表的输出
{
LinkList p;
p=L->next;
while (p)
{
cout <data <<"\t";
p=p->next;
}
cout<
}
int main()
{
int i,x,e,choose;
LinkList L;
cout << "1. 初始化\n";
cout << "2. 创建单链表（前插法）\n";
cout << "3. 创建单链表（尾插法）\n";
cout << "4. 取值\n";
cout << "5. 查找\n";
cout << "6. 插入\n";
cout << "7. 删除\n";
cout << "8. 输出\n";
cout << "0. 退出\n";
choose=-1;
while (choose!=0)
{
cout<<"请输入数字选择:";
cin>>choose;
switch (choose)
{
case 1: //初始化一个空的单链表
if (InitList_L(L))
cout << "初始化一个空的单链表!\n";
break;
case 2: //创建单链表（前插法）
CreateList_H(L);
cout << "前插法创建单链表输出结果:\n";
Listprint_L(L);
break;
case 3: //创建单链表（尾插法）
CreateList_R(L);
cout << "尾插法创建单链表输出结果:\n";
Listprint_L(L);
break;
case 4: //单链表的按序号取值
cout << "请输入一个位置i用来取值:";
cin >> i;
if (GetElem_L(L,i,e))
{
cout << "查找成功\n";
cout << "第" << i << "个元素是："<
}
else
cout << "查找失败\n\n";
break;
case 5: //单链表的按值查找
cout<<"请输入所要查找元素x:";
cin>>x;
if (LocateElem_L(L,x))
cout << "查找成功\n";
else
cout << "查找失败! " <
break;
case 6: //单链表的插入
cout << "请输入插入的位置和元素（用空格隔开）:";
cin >> i;
cin >> x;
if (ListInsert_L(L, i, x))
cout << "插入成功.\n\n";
else
cout << "插入失败!\n\n";
break;
case 7: //单链表的删除
cout<<"请输入所要删除的元素位置i:";
cin>>i;
if (ListDelete_L(L, i))
cout<<"删除成功!\n";
else
cout<<"删除失败!\n";
break;
case 8: //单链表的输出
cout << "当前单链表的数据元素分别为:\n";
Listprint_L(L);
cout << endl;
break;
}
}
return 0;
}
本文来自本人博客：http://blog.csdn.net/rainchxy
