作业2及答案

作业2及答案1.描述以下三个概念的区别:头指针,头结点,首元结点(第一个元素结点).答:图示如下:头指针:是一个指针变量,指向头结点；头结点:是一个结构体变量,但data域不用于存储线性表中的数据,可以存储其他数据,首元结点:即第一个元素结点,用于存储线性表中a1的结点.2.填空题.(1)在顺序表中插入或删除一个元素,需要平均移动大约一半元素,具体移动的元素个数与表长和插入位置有关.(2)顺序表中逻辑上相邻的元素的物理位置一定紧邻.单链表中逻辑上相邻的元素的物理位置不一定紧邻.(3)在单链表中,除了首元结点外,任一结点的存储位置由其直接前驱的next域指示.(4)在单链表中设置头结点的作用是方便操作.3.在什么情况下用顺序表比链表好?答:在进行存取时用顺序表比链表好.4.已知指针la和lb分别指向两个无头结点单链表中的首元结点.下列算法是从表la中删除自第i个元素起共len个元素后,将它们插入到表lb中第j个元素之前,试问此算法是否正确？若有错,则请改正之.StatusDeleteAndInsertSub(LinkedListla,LinkedListlb,inti,intj,intlen){if(i0||j0||len0)returnINFEASIBLE;p=la;k=1;while(ki){p=p-next;k++;}q=p;while(k=len){q=q-next;k++;}s=lb;k=1;while(kj){s=s-next;k++;}s-next=p;q-next=s-next;returnOK;}//DeleteAndInsertSub答案:此算法不正确.注意此题中的条件是,采用的存储结构(单链表)中无头结点,因此在写算法时,特别要注意空表和第一个结点的处理.算法中尚有其他类型的错误,如结点的计数,修改指针的次序,k变量的初始化,插入和删除位置的定位等.此题的正确算法如下:StatusDeleteAndInsertSub(LinkedListla,LinkedListlb,inti,intj,intlen){if(i0||j0||len0)returnINFEASIBLE;p=la;k=1;pre=NULL;while(p&&ki){pre=p;p=p-next;k++;}if(!p)returnINFEASIBLE;q=p;k=1;while(q&&klen){q=q-next;k++;}if(!q)returnINFEASIBLE;…a1头指针头结点首元结点if(!pre)la=q-next;elsepre-next=q-next;if(j=1){q-next=lb;lb=p;}else{//j=2s=lb;k=1;while(s&&kj-1){s=s-next;k++;}if(!s)returnINFEASIBLE;q-next=s-next;s-next=p;returnOK;}}//DeleteAndInsertSub