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

《“数据结构”作业-02---解答》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、[2-1]编写一个实现在顺序表中删除给定元素操作的函数：booldeletion(sqList&L,elemente){inti=0;while(inex

2、t!=NULL&&hp->next->data!=a)hp=hp->next;if(hp->next==NULL)returnfalse;//表中不存在元素ap=newlinknode;p->data=b;p->next=hp->next;hp->next=p;returntrue;}[2-3]若要求在时间复杂度为O(1)的前提下实现线性表访问当前元素的前趋和后继，线性表可以采用哪些存储结构？1.采用顺序表。设当前元素为L.data[p]，则其前趋为L.data[p-1]，后继为L.data[p+1]。2.采用双向循环链表。设指针p指向当前元素，则p->prior指向前趋，p->next指向

3、后继。[2-4]比较线性表的顺序存储结构和链式存储结构。线性表顺序存储结构的优点是随机存取，缺点是需预分配一个大数组而存在空间冗余，或分配不足易发生溢出，且元素的插入或删除操作需要移动大量元素而费时，尤其在元素结点较大时更不可取。链式存储结构弥补了顺序存储结构的缺陷，但无法进行随机存取，通常需要通过遍历（由头结点开始）实现定位和查找等操作。[2-5]*运用单向循环链表求解约瑟夫环问题，试编程实现输出出列序列。#includetypedefstructnode{intnumber;structnode*next;}linknode;voidmain(){linknode

4、*R,*p,*q;intn,k,m,i;cout<<"n=";cin>>n;//n个人cout<<"k=";cin>>k;//第k个开始cout<<"m=";cin>>m;//报数到m//***初始化单向循环单链表***//i=1;R=newlink_node;//建立第一个结点R->number=i;i++;p=R;while(i<=n)//建立后续各结点{q=newlink_node;q->number=i;i++;p->next=q;p=q;}p->next=R;//使最后一个结点的后继为第一个结点//*************************////***定位到编号为k的结点

5、***//i=1;p=R;while(inext;i++;}//*************************//while(p->next!=p)//环中有1个以上结点时{i=1;while(inext;i++;}cout<number<<",";//出列q->next=p->next;deletep;p=q->next;}cout<number<