2011学年数据结构第二章经典题解.doc

2011学年数据结构第二章经典题解1.已知非空带表头结点的线性链表由list指出，链结点的结构为（data，next），请写一算法，将链表中数据域值最小的那个链结点移到链表的最前面。要求：不得额外申请新的链结点。delinsert(LinkListlist)p=list-next;/工作指针pre=list;/最小元素结点前驱q=p;/最小元素结点while(p-next!=NULL)if(p-next-datadata)q=p-next;pre=p;p=p-next;/查找最小元素结点if(q!=list-next)/最小元素结点不是第一个结点pre-next=q-next;/从原位置删除q-next=list-next;list-next=q;/在头结点后插入，使最小元素结点成为第一个结点2.在带头结点的单链表中，设计算法dellist_maxmin，删除所有数据域大于min，而小于max的所有元素。dellist_maxmin(linklist*head,intmin,intmax)pre=head;/工作指针前驱p=head-next;/工作指针while(p!=NULL)if(p-datadata=max)/不满足删除条件pre=p;p=p-next;else/满足删除条件pre-next=p-next;free(p);p=pre-next;/删除3.编写一个将带头结点单链表逆置的算法。voidreverse_list(linklisthead)p=head-next;/待插入结点指针head-next=NULL;while(p!=NULL)s=p;p=p-next;s-next=head-next;head-next=s;/插入4.在一个带头结点的单链表中，head为头指针，p指向链表中的某一个结点，编写算法swapin_list（），实现p所指向的结点和p的后继结点相互交换。Linklistswapin_list(linklisthead,linklistp)q=p-next;if(q!=NULL)r=head;while(r-next!=p)r=r-next;r-next=q;p-next=q-next;q-next=p;return(head);elsereturn(NULL);5.设有一头指针为L的带有表头结点的非循环双向链表，其每个结点中除有pred（前驱指针），data（数据）和next（后继指针）域外，还有一个访问频度域freq。在链表被起用前，其值均初始化为零。每当在链表中进行一次Locate(L,x)运算时，令元素值为x的结点中freq域的值增1，并使此链表中结点保持按访问频度非增（递减）的顺序排列，同时最近访问的结点排在频度相同的结点的最后，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate(L,x)运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型。DLinkListlocate(DLinkListL，ElemTypex)L是带头结点的按访问频度递减的双向链表，本算法先查找数据x，查找成功时结点的访问频度域增1，最后将该结点按频度递减插入链表中适当位置。DLinkListp=L-next,q;p为工作指针，q为p的前驱，用于查找插入位置。while(p&p-data!=x)p=p-next;查找值为x的结点。if(!p)printf(“不存在值为x的结点n”);exit(0);elsep-freq+;令元素值为x的结点的freq域加1。p-next-pred=p-pred;将p结点从链表上摘下。p-pred-next=p-next;q=p-pred;以下查找p结点的插入位置while(q!=L&q-freqfreq)q=q-pred;p-next=q-next;q-next-pred=p;将p结点插入p-pred=q;q-next=p；return(p);返回值为x的结点的指针算法结束6.给定(已生成)一个带表头结点的单链表，设head为头指针，结点的结构为(data,next),data为整型元素，next为指针，试写出算法：按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间。voidMiniDelete（LinkedListhead）head是带头结点的单链表的头指针，本算法按递增顺序输出单链表中各结点的数据元素，并释放结点所占的存储空间。while（head-next!=null）循环到仅剩头结点。pre=head；pre为元素最小值结点的前驱结点的指针。p=pre-next；p为工作指针while（p-next!=null）if（p-next-datanext-data）pre=p；记住当前最小值结点的前驱p=p-next