大学《数据结构》第二章：线性表-第三节-线性表的链式存储结构（二）

第三节线性表的链式存储结构（二）二、单链表上的基本运算（考试最重要的内容）1、单链表的建立动态建立单链表的常用方法有两种：一种是头插法，另一种则是尾插法。（1）头插法建表：从一个空表开始，重复读入数据，生成新结点，将读入的数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。算法描述：LinkListCreateListF(){LinkListhead；ListNode*p；．charch；head=NULL；//置空单链表ch=getchar()；//读入第一个字符while(ch!='\n')//读入字符不是结束标志符时作循环{p=(ListNode*)malloc(sizeof(ListNode))；//分配一个类型为ListNode的结点的地址空问，并将其首地址存入指针变量p中。p->data=ch;//数据域赋值p->next=head；//指针域赋值head=p；//头指针指向新结点ch=getchar();//读入下一个字符}returnhead；//返回链表的头指针}（2）尾插法：将新结点插入在当前链表的表尾上，因此需要增设一个尾指针rear，使其始终指向链表的尾结点。算法描述：LinkListCreateListR(){LinkListhead，rear；ListNode*p；charch；head=NULL；rear=NULL；//置空单链表ch=getchar()；//读入第一个字符while(ch!='\n')//读入字符不是结束标志符时作循环{p=(ListNode*)malloc(Sizeof(ListNode))；//申请新结点p->data=ch；//数据域赋值if(head==NULL)head=p;//新结点*p插入空表elserear->next=p；//新结点*p插入到非空表的表尾结点*rear之后rear=p，//表尾指针指向新的表尾结点ch=getchar()；//读入下一个字符}if(rear!=NULL)rear->next=NULL；//终端结点指针域置空returnhead；}带头结点的单链表：作用是可以简化单链表的算法在引入头结点之后，尾插法建立单链表的算法可简化为：LinkListCreateLlstRl()//尾插法建立带头结点的单链表算法{LinkListhead=(ListNode*)malloc(Sizeof(ListNode));//申请头结点ListNode*p，*r；DataTypech；r=head；//尾指针初始指向头结点while((ch=getchar())!='\n'){p=(ListNode*)malloc(sizeof(ListNode))；//申请新结点p->data=ch；r->next=p；//新结点连接到尾结点之后r=p;//尾指针指向新结点}r->next=NULL；//终端结点指针域置空returnhead;}真题选解（例题·单选题）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；隐藏答案【答案】D【解析】向表头插入，即在第一个结点之前插入，这就要把第一个结点链接到p结点之后，而将p结点链接到头结点之后。2、查找运算（1）在单链表中要查找第i个结点算法描述ListNode*GetNodei(LinkListhead，inti){//head为带头结点的单链表的头指针，i为要查找的结点序号ListNode*p；intj;p=head->next;j=1；//使p指向第一个结点，j置1while(p!=NULL&&j<i)//顺指针向后查找，直到p指向第i个结点或p为空为止{p=p->next；++j；}if(j==i)//若查找成功，则返回查找结点的存储地址(位置)，否则返回NULLreturnp；e1sereturnNULL；}算法分析①最好情况是查找第1个元素，循环执行0次②最坏情况是查找第n+1个元素，循环执行n次。③在等概率情况下，循环执行次数为：（n+（n-1）+（n-2）+…+2+1+0）/（n+1）=n/2。故算法平均时间复杂性是O（n）。（2）在单链表中查找值为k的结点算法描述LiStNode*LocateNodek(LinkListhead，DataTypek){//head为带头结点的单链表的头指针，k为要查找的结点值ListNode*p=head->next；//p指向开始结点while(p&&p->data!=k)//循环直到p等于NULL或p->data等于k为止p=p->next；//指针指向下一个结点returnp；//若找到值为k的结点，则p指向该结点，否则p