第二章作业答案

第二章作业1.描述以下三个概念的区别：头指针，头结点，首元结点(第一个元素结点)。答：首结点就是存放数据元素的第一个元素结点，头结点是为了插入和删除的方便说增设的一个结点，头指针是指向链表中第一个结点的存储位置，在没有头结点的链表中，头指针指向链表中的首结点，在有头结点的链表中，头指针指向链表中的头结点。2.简述线性表的两种存储结构顺序表和链表的优缺点。3.已知L是无表头结点的单链表，且P是指向表中某个结点的指针，试写出在P所指结点之前插入指针S所指结点的语句序列。P-next-next=P-next;S-next=P;4.已知P是指向双向链表中某个结点的指针，试写出删除P所指结点的前驱结点的语句序列。p是要删除的结点，q是p的前一个结点q-next=p-next;//删除的结点的后一结点的首地址赋值给删除的结点的前一结点的nextp-next-prior=q;//删除的结点的后一结点的prior指向删除的结点的前一结点的首地址5.简述以下算法的功能。(1)StatusA(LinkedListL){//L是无表头结点的单链表if(L&&L-next){Q=L;L=L-next;P=L;while(P-next)P=P-next;P-next=Q;Q-next=NULL;}returnOK;}//A本程序实现的功能就是：如果L的长度不小于2，则将首元结点删去并插入到末尾。(2)voidBB(LNode*s,LNode*q){p=s;while(p-next!=q)p=p-next;p-next=s;}//BBvoidAA(LNode*pa,LNode*pb){//pa和pb分别指向单循环链表中的两个结点BB(pa,pb);BB(pb,pa);}//AA如果L的长度不小于2，将L的首元结点变成尾元结点。将单循环链表拆成两个单循环链表。