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

[2-1] 编写一个实现在顺序表中删除给定元素操作的函数：

bool deletion(sqList &L, element e)

{ int i=0;

while(iif(i==L.len) return false; // 表中不存在元素e

while(i{ 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

typedef

struct node

{ int number;

struct node *next;

}linknode;

void main()

{ linknode *R, *p, *q;

int n, k, m, i;

cout<<\"n = \"; cin>>n; cout<<\"k = \"; cin>>k; cout<<\"m = \"; cin>>m; // n个人

// 第k个开始

// 报数到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{ q=p; // q指向前驱结点

p=p->next;

i++;

}

//*************************//

while(p->next!=p) // 环中有1个以上结点时

{ i=1;

while(i{ q=p;

p=p->next;

i++;

}

cout<number<<\ // 出列

q->next=p->next;

delete p;

p=q->next;

}

cout<number<}

// 最后一个出列