数据结构作业答案第二章作业答案.doc

第二章作业解答一、基础知识题2.1试描述头指针、头结点、开始结点的区别，并说明头指针和头结点的作用。答：头指针是指向头结点或开始结点的指针，我们就是靠它来描述和访问整个线性链表，如果失去了头指针，整个线性链表也就无法访问，因而线性链表的存在与否也就失去了意义。头结点是为了对线性链表操作的方便而引入的，引入头结点主要有两方面的方便，一是当在线性链表的第一个位置进行操作时无需做特殊处理；二是就整个线性链表而言无论空表和非空表，对表的操作可以保持一致性。头结点的数据域为空而指针域指向开始结点，如果存在头结点，那么线性链表的头指针就指向它。开始结点是真正存储数据的第一个线性链表的结点，如果有头结点的话，头结点的指针域就指向它；如果没有头结点的话，头指针就指向它。2.2何时选用顺序表、何时选用链表作为线性表的存储结构为宜？答：从空间复杂度上考虑：顺序表的存储空间是静态分配的，链表的存储空间是动态分配的，顺序表的存储密度为1，链表的存储密度小于1，因此如果表的长度变化较大，事先难以确定表的规模宜采用链表，否则用顺序表。从时间复杂度上考虑：顺序表的最大优点是，它是一种随机存取结构，查找算法的时间复杂度低；最大缺点是插入删除操作的时间复杂度较链表高；链表的最大优点是插入删除操作的时间复杂度低；最大缺点是查找算法的时间复杂度较顺序表高。因此对于频繁进行插入和删除的线性表，宜采用链表做存储结构。若插入和删除操作较少，而查找操作较多时宜采用顺序表。2.3在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应链表中删除？若可以，其时间复杂度各为多少？答：要删除某结点，我们需要知道该结点的前后两个结点。在单链表中，不知道头指针，则无法访问该结点的前一个结点，因此无法删除。在双链表中可以删除，时间复杂度为O(1)。在单循环链表中可以删除，时间复杂度为O(n)。2.4下述算法的功能是什么？LinkList Demo(LinkList L) /L是无头结点的单链表 ListNode *Q,*P; if(L&L-next) Q=L;L=L-next;P=L; while(P-next)P=P-next; P-next=Q;Q-next=NULL; return L;/Demo功能是：如果线性表的长度大于1，则将线性表第一个位置上结点放到最后一个位置上。二、算法设计题2.5设线性表的n个结点定义为(a0,a1,.,an-1)，重写顺序表上实现的插入和删除算法：InsertList和DeleteList。void InsertList(SeqList *L,DataType x,int i)int j; if(iL-length) Error(position error); if(L-length=ListSize) Error(overflow); for(j=L-length;ji;j-) L-dataj=L-dataj-1; L-datai=x; L-length+;void DeleteList(SeqList *L,int i)int j; if(iL-length-1) Error(position error!); for(j=i;jlength-1;j+) L-dataj=L-dataj+1; L-length-;2.6试分别用顺序表和单链表作为存储结构，实现将线性表(a0,a1,.,an-1)就地逆置的操作。顺序表：void Trans(SeqList *L)DataType x; int i; for(i=0;ilength/2;i+) x=L-datai; L-datai=L-dataL-length-i-1; L-dataL-length-i-1=x; 单链表：void Trans(LinkList *head)/无头结点ListNode *p1,*p2; if(!(head&head-next)return;/如果表的长度为0或1则直接返回 p2=head;head=p2-next;p1=head-next; for(;) head-next=p2; if(!p1)return; p2=head; head=p1; p1=p1-next; 2.7设顺序表L是一个递增有序表，试写一算法将x插入L中，并使L仍是一个有序表。void Insert(SeqList *L,DataType x) int i,j; for(i=0;ilength;i+) if(xdatai)break; for(j=L-length;jdataj=L-dataj-1; L-datai=x;2.8设单链表L是一个递减有序表，试写一算法将x插入其中后仍保持L的有序性。void Insert(LinkList *L,DataType x)ListNode *p1,*p2,*p3; p3=(ListNode *)malloc(sizeof(ListNode); p3-data=x; p1=L;p2=p1-next; while(1) p1=p2; p2=p2-next; if(!p2)|(xp2-data) p1-next=p3;p3-next=p2;return; 2.9写一算法在单链表上实现线性表的ListLength(L)运算。int ListLength(LinkList *L)/没有头结点int i=0; ListNode *p; p=L; while(p)