二、算法设计题：
2.7 (本题感谢pastar的指正)
解：
算法如下:
#define ListSize 100// 假定表空间大小为100
#include
#include
void Error(char * message)
{
fprintf(stderr,"错误:%s/n",message);
exit(1);
}//从0开始计， 表空间大小应为101了
typedef int Datatype ;//假定Datatype的类型为int型
typedef struct{
Datatype data[ListSize];// 向量data用于存放表结点
int length; // 当前的表长度
} Seqlist;
//以上为定义表结构
//------------以下为要求算法----------
void InsertList ( Seqlist *L, Datatype x, int i)
{
//将新结点x插入L所指的顺序表的第i个结点ai的位置上
int j;
if ( i < 0 || i > L -> length )
Error("position error");// 非法位置，退出
if ( L->length>=ListSize )
Error("overflow");
for ( j=L->length-1 ; j >= i ; j --)
L->data[j+1]=L->data [j];
L->data[i]=x ;
L->length++ ;
}
void DeleteList ( Seqlist *L, int i )
{// 从L所指的顺序表中删除第i个结点ai
int j;
if ( i< 0 || i > L-> length-1)
Error( " position error" ) ;
for ( j = i+1 ; j < L-> length ; j++ )
L->data [ j-1 ]=L->data [ j]; // 结点前移
L-> length-- ; //表长减小
}
//===========以下为验证算法而加=======
void Initlist(Seqlist *L)
{
L->length=0;
}
void main()
{
Seqlist *SEQA=new Seqlist;
Initlist(SEQA);
int i;
for (i=0;i {
InsertList (SEQA,i,i);
printf("%d/n",SEQA->data[i]);
}
DeleteList (SEQA,99);
for (i=0;i {
printf("%d/n",SEQA->data[i]);
}
}
--------------------------------------------------------------------------------
(答案及点评) 2.8 试分别用顺序表和单链表作为存储结构，实现将线性表(a0,a1,...an-1)就地逆置的操作，所谓"就地"指辅助空间应为O(1)。
2.8 解：
按题意，为将线性表逆置，但辅助空间不能随表的规模增大。我们分别讨论顺序表和单链表的情况：
1. 顺序表：
要将该表逆置，可以将表中的开始结点与终端结点互换，第二个结点与倒数第二个结点互换，如此反复，就可将整个表逆置了。算法如下：
// 表结构定义同上
void ReverseList( Seqlist *L)
{
Datatype t ; //设置临时空间用于存放data
int i;
for ( i=0 ; i < L->length/2 ; i++)
{ t = L->data[i];//交换数据
L -> data[ i ] = L -> data[ L -> length - 1 - i ] ;
L -> data[ L -> length - 1 - i ] = t ;
}
}
2. 链表：
也是可以用交换数据的方式来达到逆置的目的，但是由于是单链表，数据的存取不是随机的，因此算法效率太低，我们可以利用指针的指向转换来达到表逆置的目的。算法是这样的：
// 结构定义略
LinkList ReverseList( LinkList head )
{
// 将head 所指的单链表逆置
ListNode *p ,*q ;//设置两个临时指针变量
if( head->next && head->next->next)
{
//当链表不是空表或单结点时
p=head->next;
q=p->next;
p -> next=NULL;//将开始结点变成终端结点
while (q)
{//每次循环将后一个结点变成开始结点
p=q;
q=q->next ;
p->next = head-> next ;
head->next = p;
}
return head;
}
return head;//如是空表或单结点表，直接返回head
}
--------------------------------------------------------------------------------
(答案及点评) 2.9 设顺序表L是一个递增有序表，试写一算法，将x插入L中，并使L仍是一个有序表。
2.9 解：
因已知顺序表L是递增有序表，所以只要从头找起找到第一个比它大(或相等)的结点数据，把x插入到这个数所在的位置就是了。算法如下：
void InsertIncreaseList( Seqlist *L , Datatype x )
{
int i;
for ( i=0 ; i < L -> length && L->data[ i ] < x ; i++) ; // 查找并比较,分号不能少
InsertList ( L ，x , i ); // 调用顺序表插入函数
}
--------------------------------------------------------------------------------
(答案及点评) 2.10 设顺序表L是一个递减有序表，试写一算法，将x插入其后仍保持L的有序性。
2.10 解：
与上题相类似，只要从头找到第一个比x小(或相等)的结点数据，在这个位置插入就可以了。算法如下：
void InsertDecreaseList( Seqlist *L, Datatype x )
{
int i;
for (i=0; i< L -> length && L-> data[i] > x ; i++) ; //查找
InsertList ( L , x , i ); // 调用顺序表插入函数
}
--------------------------------------------------------------------------------
(答案及点评) 2.11 写一算法在单链表上实现线性表的ListLength(L)运算。
2.11 解：
求单链表长只能用遍历的方法了，从头数到尾，总能数出来吧。算法如下：
int ListLength ( LinkList L )
{
int len=0 ;
ListNode *p;
p=L; //设该表有头结点
while ( p->next )
{
p=p->next;
len++;
}
return len;
}
--------------------------------------------------------------------------------
(答案及点评) 2.12 已知L1和L2分别指向两个单链表的头结点，且已知其长度分别为m和n。试写一算法将这两个链表连接在一起，请分析你的算法的时间复杂度。
2.12 解：
算法如下:
LinkList Link( LinkList L1 , LinkList L2 )
{
//将两个单链表连接在一起
ListNode *p , *q ;
p=L1;
q=L2;
while ( p->next ) p=p->next; //查找终端结点
p->next = q->next ; //将L2的开始结点链接在L1之后
return L1 ;
}
本算法的主要操作时间花费在查找L1的终端结点上，与L2的长度无关，所以本算的法时间复杂度为：
m+1=O(m)
--------------------------------------------------------------------------------
(答案及点评) 2.13 设 A和B是两个单链表，其表中元素递增有序。试写一算法将A和B归并成一个按元素值递减有序的单链表C，并要求辅助空间为O(1)，请分析算法的时间复杂度。
2.13 解：
根据已知条件，A和B是两个递增有序表，所以我们可以以A表为基础，按照插入单个元素的办法把B表的元素插入A表中，完成后，将表逆置就得到了一个按元素值递减有序的单链表C了。
算法如下：
LinkList MergeSort ( LinkList A , LinkList B )
{
// 归并两个递增有序表为一个递减有序表
