数据结构与算法（3）— 链表
(mi6236)
1、链表简述
链接表（linked list）分为线性链接表（用于线性表）和非线性链接表（用于树型结构，图型结构等）。
一个链表由n个（n>＝0，若n=0，则称为空表）节点所组成，每个节点除了包含有存储数据元素的值域外还包含有用来实现数据元素之间逻辑关系的一个或若干个指针域，每个指针域的值为其后继元素或前驱元素所在结点的存贮位置，若某个指针域不需要指向任何结点，则令它的值为null。
在一个链接表中，若每个结点只包含有一个指针域，则被称为单链表，否则被称为多链表。对于结尾数据结构来说，由于数据元素之间是1：1的联系，所以当进行链接存贮时，一种方式是：在每个结点中只设置一个指针域，用以指向其后继结点，这样构成的链接表称为单向链接表；另一种方法是：在每个结点中设置两个指针域，分别用以指向其前驱结点和后继结点，这样构成的链接表称为双向链接表。
每个链表都有一个指针指向其第一个结点，称做表头指针。沿着表头指针可以访问到任一个结点。线性单链表分为带头结点和不带头结点两种类型，它们之间区别主要体现在其结构上和算法操作上。在结构上，带头结点的单链表不管链表是否为空，均含有一个头结点；而不带头结点的单链表为空。在操作上带头结点的单链表的初始化为申请一个头结点，且在任何结点位置进行操作算法一致；而不带头结点的单链表让头指针为空，同时其他操作要特别注意空表和第一个结点的处理。常常为了运算的方便在第一个结点之间增设一个结点，把它称为附加表头结点，并让链接表的表头指针指向这个结点，而这个结点的指针域指向第一个结点。
线性表的顺序存储结构和链式存储结构的区别：若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的存取线性表中的元素应采用顺序存储结构。因为由于顺序存储结构一旦确定了起始位置，线性表中的任何一个元素都可以进行随机存取存取速度较高；并且，由于线性表的总数基本稳定，且很少进行插入和删除，这一特点恰好避开了顺序存储结构的特点。若需要在线性表的任意位置进行频繁的插入和删除，则采用链式存储结构比较合适。链式存储结构中的结点内部存储空间是连续的，但结点之间存储空间不一定连续。尽管存储结构的物理地址未必连续，但结点之间仍然保持其逻辑次序，逻辑次序关系隐含在结点中。
顺序表和链表各有优缺点，在实际应用中，应根据问题的特点具体分析：
基于空间考虑，当要求存储的线性表升序变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表升序变化大，难以估计其存储规模时，采用动态链表。
基于时间考虑，若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之，若需要对线性表进行频繁插入或删除等操作时，宜采用链表做存储结构。且，若链表的插入和删除主要发生在表的首尾两端，则采用指针表示的单循环链表。
2、单链表存储结构C语言描述。
#include <stdio.h>
#include <stdlib.h>
#define limit 10
typedef int ElemType;
typedef struct node{
ElemType data;
struct node *next;
}LNode,*LinkList;
3、单链表基本函数算法描述
注：一下程序在VC6.0+WIN2K下测试通过。
3.1、链表初始化
初始化函数用于创建一个头结点，由head指向它，该结点的next域为空，data域未设定任何值。由于调用该函数时，指针head在本中指向的内容发生改变，为了返回改变的值，形参使用指针型，其时间复杂度为O（1）。
/*初始化单向链表*/
LNode * initlist()
{
LNode *head;
head=(LNode *)malloc(sizeof(LNode));/*创建头结点*/
head->next=NULL;
return head;
}
//void initlist(LNode **head)
//{
// *head=(LNode *)malloc(sizeof(LNode));/*创建头结点*/
// (*head)->next=NULL;
//}
/*初始化单向循环函数*/
LNode * initCycList()
{
LNode *head;
head=(LNode *)malloc(sizeof(LNode));/*创建头结点*/
head->next=head;
return head;
}
3.2、求单链表的长度
单链表的长度是指单链表中所含结点的个数。此算法需要从表头指针出发，沿着每个结点的链，每次向下访问并进行计数，起到最后一个结点为止，其时间复杂度为O（n）。
/*求单链表的长度*/
int lenth(LNode *head)
{
int len=0;
LNode *p;
p=head;
while(p->next)
{
p=p->next;
len++;
}
return len;
}
3.3、从单链表中找出关键字等于给定值k的结点
从表头第一个结点起，依次使每个结点的关键字同给定值进行比较，直到某个结点的关键字等于给定值k或者查到表尾为止，其时间复杂度为O（n）。
LNode * get(LNode *head,ElemType k)
{
LNode *p;
int i=0;
p=head;
while(p)
if (p->data==k)
{
printf("从链表中找到%d位置为%d/n",k,i);
return p;
}
else
{
p=p->next;
i++;
}
printf("未从链表中找到%d这个元素/n",k);
return NULL;
}
3.4、在单链表中第i个接点之后插入一个元素为x的新结点
创建一个data域值为x的新结点*p，然后插入到head所指向的单链表的第i个结点之前。若i值超出链表的长度，做“超出范围处理” ，其时间复杂度为O（n）。
/*在单链表中第i个接点之后插入一个元素为x的新结点*/
int insert(LNode *head,int i,ElemType x)
{
LNode *p,*q;
int j=0;
p=head;
while(p&&j<i-1) /*查找p结点应插入的位置*/
{
p=p->next;
++j;
}
if(!p||j!=i-1||i<1)
{
printf("插入元素位置超界/n");
return 0;
}
q=(LNode *)malloc(sizeof(LNode));
q->data=x; /*生成p节点，x是元素的值*/
q->next=p->next;
p->next=q;
return 1;
}
3.5、删除元素
线性链表中的元素的删除要修改被删元素前驱的指针，回收被删除元素所占用的空间。主要的耗时在查找上，因而长度为n线性单链表进行删除操作的时间复杂度为O（n）。
/*删除链表中的元素*/
int del(LNode *head,int i,ElemType x) /*删除第i个节点，并通过x返回值*/
{
LNode *p,*q;
int j=0;
p=head;
while(p->next &&j<i-1) /*查找第i个节点的前驱位置p*/
{
p=p->next;
j++;
}
if(!(p->next)||j>i-1)
return 0;
q=p->next;
p->next=q->next;
x=q->data;
free(q);
return 1;
}
3.6、已知在一个数组A中存放着一个具有n个元素的线性表，按关键字把他们链结成一个带有附加表头节点的循环单链有序表，时间复杂度为O（n2）
void create(LNode *head,ElemType A[],int n)
{
for(int i=0;i<n;i++)
insert(head,i+1,A[i]);
}
3.7、显示单向链表中的元素。
/*显示单链表中的所有元素*/
void ShowLinkList(LNode *head)
{
LNode *p;
int i=0;
p=head;
while(p->next)
{
p=p->next;
i++;
printf("链表的第%d个元素的值为:%d/n",i,p->data);
}
if (i==0)
printf("链表中没有元素/n");
}
3.8、在带有附加表头结点的循环双向链表中进行插入和删除。
3.8.1、存储结构
typedef int ElemType;
typedef struct node{
ElemType data;
struct node *left;
struct node *right;
}p,q;
3.8.2、若要在链表中p所指向的结点之后插入一个q所指向的新结点，则运算步骤为：
q->right=q->right;/*使q结点的右指针指向p结点的后继指针*/
q->left=p; /*使q结点的左指针指向p结点*/
p->right->left=q;/*使p结点的后继结点的做指针指向q结点*/
p->right=q; /*使p结点的右指针指向q结点*/
3.8.3、若要删除指针p所指向的结点，则运算步骤为：
p->left->right=q->right; /*使p结点的前驱结点的右指针指向p的后继结点*/
p->right->left=p->left; /*使p结点的后继结点的左指针指向p的前驱结点*/
free(p); /*回收p结点*/
3.9、测试程序
int main()
{
LNode *link,*arrayToLink;
int i=0;
char temp;
ElemType x;
ElemType array[limit]={1,3,5,7,9,11,13,15,17,19};
link=initlist();
printf("链表中元素有:%d个/n",lenth(link));
ShowLinkList(link);
while(1)
{
x=-1;
printf("请输入您要插入元素的值（输入q自动结束初始化）:");
scanf("%d",&x);
if (x<0 || x>32767)
{
temp=getchar();
break;
}
printf("请输入您要插入元素的位置:");
scanf("%d",&i);
if(insert(link,i,x)==0)
break;
}
printf("链表中元素有:%d个/n",lenth(link));
ShowLinkList(link);
printf("请输入您所要查找的元素");
scanf("%d",&x);
get(link,x);
printf("请输入您所要删除元素的位置:");
scanf("%d",&i);
if(del(link,i,x))
{
printf("链表中元素有:%d个/n",lenth(link));
ShowLinkList(link);
}
else
printf("删除失败,可能您输入的下标越界/n");
arrayToLink=initCycList();
create(arrayToLink,array,limit);
for(i=0;i<limit;i++)
{
arrayToLink=arrayToLink->next;
printf("链表的第%d个元素的值为:%d/n",i,arrayToLink->data);
}
return 1;
}