第三节 - 线性表的链式存储结构（二）
发布时间：2020-09-20 10:31来源：未知
第三节 线性表的链式存储结构（二）
二、单链表上的基本运算（考试最重要的内容）
1、单链表的建立
动态建立单链表的常用方法有两种：一种是头插法，另一种则是尾插法。
（1）头插法建表：从一个空表开始，重复读入数据，生成新结点，将读入的数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。
算法描述：
LinkList CreateListF()
{ LinkList head；
ListNode *p； ．
char ch；
head=NULL； //置空单链表
ch=getchar()； //读入第一个字符
while(ch!='\n') //读入字符不是结束标志符时作循环
{ p=(ListNode *)malloc(sizeof(ListNode))； //分配一个类型为ListNode的结点的地址空问，并将其首地址存入指针变量p中。
p->data=ch; //数据域赋值
p->next=head； //指针域赋值
head=p； //头指针指向新结点
ch=getchar(); //读入下一个字符
}
return head； //返回链表的头指针
}
（2）尾插法：将新结点插入在当前链表的表尾上，因此需要增设一个尾指针rear，使其始终指向链表的尾结点。
算法描述：
LinkList CreateListR()
{ LinkList head，rear；
ListNode *p；
char ch；
head=NULL； rear=NULL； //置空单链表
ch=getchar()； //读入第一个字符
while(ch!='\n') //读入字符不是结束标志符时作循环
{ p=(ListNode *)malloc(Sizeof(ListNode))； //申请新结点
p->data=ch； //数据域赋值
if(head==NULL) head=p; //新结点*p插入空表
else rear->next=p； //新结点*p插入到非空表的表尾结点*rear之后
rear=p， //表尾指针指向新的表尾结点
ch=getchar()； //读入下一个字符
}
if(rear!=NULL) rear->next=NULL； //终端结点指针域置空
return head；
}
带头结点的单链表：作用是可以简化单链表的算法
在引入头结点之后，尾插法建立单链表的算法可简化为：
LinkList CreateLlstRl() //尾插法建立带头结点的单链表算法
{ LinkList head=(ListNode*)malloc(Sizeof(ListNode)); //申请头结点
ListNode *p，*r；
DataType ch；
r=head； //尾指针初始指向头结点
while((ch=getchar( ))!='\n')
{ p=(ListNode *)malloc(sizeof(ListNode))； //申请新结点
p->data=ch；
r->next=p； //新结点连接到尾结点之后
r=p; //尾指针指向新结点
}
r->next=NULL； //终端结点指针域置空
return head;
}
真题选解
（例题·单选题）1、在带头结点的单链表h中，若要向表头插入一个由指针p所指向的结点，则执行( )。
A．h=p； p->next=h； B．p->next=h； h=p；
C．p->next=h； p=h； D．p->next=h->next； h->next=p；
2、查找运算
（1）在单链表中要查找第i个结点
算法描述
ListNode *GetNodei(LinkList head，int i)
{ //head为带头结点的单链表的头指针，i为要查找的结点序号
ListNode *p；int j;
p=head->next; j=1； //使p指向第一个结点，j置1
while(p!=NULL&&j<i) //顺指针向后查找，直到p指向第i个结点或p为空为止
{ p=p->next；++j；
}
if(j==i) //若查找成功，则返回查找结点的存储地址(位置)，否则返回NULL
return p；
e1se
return NULL；
}
算法分析
①最好情况是查找第1个元素，循环执行0次
②最坏情况是查找第n+1个元素，循环执行n次。
③在等概率情况下，循环执行次数为：（n +（n - 1）+（n -2）+ …+ 2 + 1+0）/（n+1）= n / 2。故算法平均时间复杂性是O（n）。
（2）在单链表中查找值为k的结点
算法描述
LiStNode * LocateNodek(LinkList head，DataType k)
{ //head为带头结点的单链表的头指针，k为要查找的结点值
ListNode *p=head->next； //p指向开始结点
while(p&&p->data!=k) //循环直到p等于NULL或p->data等于k为止
p=p->next； //指针指向下一个结点
return p； //若找到值为k的结点，则p指向该结点，否则p为NULL
}
算法分析
①最好情况是第1个元素的值为k，循环执行0次
②最坏情况是链表中没有值为k的个元素，循环执行n次。
③在等概率情况下，循环执行次数为：（n +（n - 1）+（n -2）+ …+ 2 + 1+0）/（n+1）= n / 2。故算法平均时间复杂性是O（n）。
