“数据结构”作业 02 - 解答.doc

2-1 编写一个实现在顺序表中删除给定元素操作的函数：bool deletion(sqList &L, element e) int i=0; while(iL.len & L.datai!=e) i+; if(i=L.len) return false;/ 表中不存在元素e while(inext!=NULL & hp-next-data!=a) hp=hp-next; if(hp-next=NULL) return false;/ 表中不存在元素a p=new linknode; p-data=b;p-next=hp-next; hp-next=p; return true;2-3 若要求在时间复杂度为O(1)的前提下实现线性表访问当前元素的前趋和后继，线性表可以采用哪些存储结构？1. 采用顺序表。设当前元素为L.datap，则其前趋为L.datap-1，后继为L.datap+1。2. 采用双向循环链表。设指针p指向当前元素，则p-prior指向前趋，p-next指向后继。2-4 比较线性表的顺序存储结构和链式存储结构。线性表顺序存储结构的优点是随机存取，缺点是需预分配一个大数组而存在空间冗余，或分配不足易发生溢出，且元素的插入或删除操作需要移动大量元素而费时，尤其在元素结点较大时更不可取。链式存储结构弥补了顺序存储结构的缺陷，但无法进行随机存取，通常需要通过遍历（由头结点开始）实现定位和查找等操作。2-5* 运用单向循环链表求解约瑟夫环问题，试编程实现输出出列序列。#include typedef struct node int number; struct node *next; linknode;void main() linknode *R, *p, *q; int n, k, m, i; coutn;/ n个人 coutk;/ 第k个开始 coutm;/ 报数到m /* 初始化单向循环单链表 */ i=1; R=new link_node; / 建立第一个结点 R-number=i; i+; p=R; while(inumber=i; i+; p-next=q; p=q; p-next=R; / 使最后一个结点的后继为第一个结点 /*/ /* 定位到编号为k的结点 */ i=1; p=R; while(inext; i+; /*/ while(p-next!=p) / 环中有1个以上结点时 i=1; while(inext; i+; coutnumbernext=p-next; delete p; p=q-next; coutnumberendl; / 最后一个出列 delete p;