文档介绍：作业:分别以顺序表和单链表为存储结构,为线性表类添加一个成员函数,实现线性表中所有元素就地逆置。
顺序表的就地逆置算法:
template <class T>
void SeqList<T>::Reverse()
{
for(int i=0; i<length/2 ; i++)
{
int temp=data[i];
data[i]=data[length-i-1];
data[length-i-1]=temp;
}
}
单链表的就地逆置算法:
算法一:要修改每个结点的指针域,即把指向后继结点的指针改为指向前躯结点,具体实现办法就是在扫描遍历过程中,对工作指针P所指结点作指针域前指操作。需注意事项 :
逆置后原来指向后继结点的指针被破坏,需要保留;
逆置需要将P的前躯结点地址填入后继位置,为此需保存前躯结点地址;
全部逆置后,头结点的指针域应指向最后结点。
template <class T>
void LinkList<T>::Reverse()
{
p=first->next ; pre=null ;
while (p)
{
r=p->next;
p->next=pre;
pre=p;
p=r;
}
first-next=pre;
}
算法二:利用头插法将单链表逆置。将原来表的头结点作为新链表的头结点,依次取原来表中的结点插到新表的头结点之后。注意:后继结点会遭破坏,需暂存。
void LinkList<T>::Reverse()
{
p=first->next ; first->next=null ;
while (p)
{
r=p->next;
p->next=first->next;
first->next=p;
p=r;
}
}
作业:设计一个时间复杂度为O(n)的算法,实现数组A[n]中所有元素循环左移k个位置。
算法一:将数组中的前k个元素存放到一个临时数组中,再将余下的n-k个元素左移k个位置,最后将前k个元素从临时数组复制到原来数组中的后k个位置。
时间复杂度O(n); 空间复杂度O(k)
算法二:先设计一个函数将数组向左循环移动一个位置,然后再调用这个函数k次,显然,该算法的时间复杂度O(n*k)
算法三:将这个问题看做是把数组ab转换成数组ba,(aTbT)T=ba
Void converse ( int A[], int n, int k)
{
Reverse (A, 0, k-1);
Reverse (A, k, n-1);
Reverse (A, 0, n-1);
}
Void Reverse ( int A[], int from, int to)
{
For (i=0; i<(to-from+1)/2; i++)
{
A[from+i]<->A[to-i];
}
}
作业:约瑟夫环问题描述:
设有编号为1,2,…n的n(n>0)个人围坐成一个圈,每个人持有一个密码m,从第1个人开始报数,报到m停止,报m的人出圈,如此下去,直到所有人全部出圈为止。当任意给定n和m后,设计算法求n个人出圈的次序。
要求:
(1)分析问题,建立数据模型;
(2)设计适合的存储结构;
(3)设计相应算法;
(4)分析算法时间和空间复杂度;
(5)调试算法,上机实现。
解:
由约瑟夫环问题的求解过程可以把问题的输入(即n个人的编号)看成是一个线性序列,每个人的编号看成是一个数据元素。因此,问题抽象的数据模型是“线性表”;
线性表有两种基本的存储结构——顺序存储和链接存储;
A. 用顺序存储结构实现约瑟夫问题
void Josephus (int a[ ], int n, int m)
{
//约瑟夫环初始化:
for (int i=0; i<n; i++) { a[i]=i+1;}
int s=0; //开始的报数位置
int length=n; //当前表中长度
while (length>1) // 每出圈一次表长减1
{
s=(s+m-1)% length;
cout<< a[s]; //s 为第m个人
for (int i=s+1; i<length; i++)
a[i-1]=a[i]; //删除第m个人
length--;
}
cout<<a[0]; //最后只剩下最后一个人
}
时间复杂度 O(n2) ; 空间复杂度O(n)
B 用循环链表存储结构实现约瑟夫问题
Struct Node
{
int data;
Node *next