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

Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date“数据结构”作业 02 - 解答“数据结构”作业 02 - 解答2-1 编写一个实现在顺序表中删除给定元素操作的函数：bool deletion(sqList &L, element e) int i=0; while(i<L.len && L.datai!=e) i+; if(i=L.len) return false;/ 表中不存在元素e while(i<L.len-1) L.datai=L.datai+1; i+; L.len-; return true;2-2 编写一个实现在单链表中的元素a之前插入元素b操作的函数： bool insertion(linknode *hp, element a, element b) linknode *p; while(hp->next!=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 <iostream.h>typedef struct node int number; struct node *next; linknode;void main() linknode *R, *p, *q; int n, k, m, i; cout<<"n = " cin>>n;/ n个人 cout<<"k = " cin>>k;/ 第k个开始 cout<<"m = " cin>>m;/ 报数到m /* 初始化单向循环单链表 */ i=1; R=new link_node; / 建立第一个结点 R->number=i; i+; p=R; while(i<=n) / 建立后续各结点 q=new link_node; q->number=i; i+; p->next=q; p=q; p->next=R; / 使最后一个结点的后继为第一个结点 /*/ /* 定位到编号为k的结点 */ i=1; p=R; while(i<k) q=p; / q指向前驱结点 p=p->next; i+; /*/ while(p->next!=p) / 环中有1个以上结点时 i=1; while(i<m) / 报数到m q=p; p=p->next; i+; cout<<p->number<<", " / 出列 q->next=p->next; delete p; p=q->next; cout<<p->number<<endl; / 最后一个出列 delete p;-