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

[2-1] 编写一个实现在顺序表中删除给定元素操作的函数：
bool deletion(sqList &L, element e)
{ int i=0;
while(i<L.len && L.data[i]!=e) i++;
if(i==L.len) return false; // 表中不存在元素e
while(i<L.len-1)
{ L.data[i]=L.data[i+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.data[p]，则其前趋为L.data[p-1]，后继为L.data[p+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;
}