if ( i< 0 || i >= L-> length) Error( \
for ( j = i ; j < L-> length ; j++ )
L->data [ j ]=L->data [ j+1]; //结点前移 L-> length-- ; //表长减小 } 关闭
2.8 试分别用顺序表和单链表作为存储结构，实现将线性表(a0,a1,...an-1)就地逆置的操作，所谓\就地\指辅助空间应为O(1)。 答：
1. 顺序表：
要将该表逆置，可以将表中的开始结点与终端结点互换，第二个结点与倒数第二个结点互换，如此反复，就可将整个表逆置了。算法如下： // 顺序表结构定义同上题
void ReverseList( Seqlist *L) {
DataType temp ; //设置临时空间用于存放data int i;
for (i=0;i<=L->length/2;i++)//L->length/2为整除运算 { temp = L->data; //交换数据
L -> data[ i ] = L -> data[ L -> length-1-i]; L -> data[ L -> length - 1 - i ] = temp; } }
2. 链表： 分析：
可以用交换数据的方式来达到逆置的目的。但是由于是单链表，数据的存取不是随机的，因此算法效率太低。可以利用指针改指来达到表逆置的目的。具体情况入下：
(1)当链表为空表或只有一个结点时，该链表的逆置链表与原表相同。 (2)当链表含2个以上结点时，可将该链表处理成只含第一结点的带头结点链表和一个无头结点的包含该链表剩余结点的链表。然后，将该无头结点链表中的所有结点顺着链表指针，由前往后将每个结点依次从无头结点链表中摘下，作为第一个结点插入到带头结点链表中。这样就可以得到逆置的链表。算法是这样的：
结点结构定义如下：
typedef char DataType; //假设结点的数据域类型的字符 typedef struct node{ //结点类型定义 DataType data; //结点的数据域 struct node *next;//结点的指针域 }ListNode;
typedef ListNode *LinkList;
ListNode *p; LinkList head;
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仍是一个有序表。 答：
因已知顺序表L是递增有序表，所以只要从顺序表终端结点（设为i位置元素）开始向前寻找到第一个小于或等于x的元素位置i后插入该位置即可。 在寻找过程中，由于大于x的元素都应放在x之后，所以可边寻找，边后移元素，当找到第一个小于或等于x的元素位置i时，该位置也空出来了。 算法如下：
//顺序表存储结构如题2.7
void InsertIncreaseList( Seqlist *L , Datatype x ) {
int i;
if ( L->length>=ListSize) Error(“overflow\
for ( i=L -> length ; i>0 && L->data[ i-1 ] > x ; i--) L->data[ i ]=L->data[ i ] ; // 比较并移动元素 L->data[ i ] =x; L -> length++; } 关闭
2.10 设顺序表L是一个递减有序表，试写一算法，将x插入其后仍保持L的有序性。 答：
与上题相类似，只要从终端结点开始往前找到第一个比x大(或相等)的结点数据，在这个位置插入就可以了。（边寻找，边移动）算法如下： void InsertDecreaseList( Seqlist *L, Datatype x ) {
int i;
if ( L->length>=ListSize) Error(“overflow\
for ( i=L -> length ; i>0 && L->data[ i-1 ] < x ; i--) L->data[ i ]=L->data[ i ] ; // 比较并移动元素 L->data[ i ] =x; L -> length++; } 关闭
2.11 写一算法在单链表上实现线性表的ListLength(L)运算。 解：
由于在单链表中只给出一个头指针，所以只能用遍历的方法来数单链表中的结点个数了。算法如下：
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。试写一算法将这两个链表连接在一起，请分析你的算法的时间复杂度。 解：
分析：
由于要进行的是两单链表的连接，所以应找到放在前面的那张表的表尾结点，再将后表的开始结点链接到前表的终端结点后即可。该算法的主要时间消耗是用在寻找第一张表的终端尾结点上。这两张单链表的连接顺序无要求，并且已知两表的表长，则为了提高算法效率，可选表长小的单链表在前的方式连接。 具体算法如下：
LinkList Link( LinkList L1 , LinkList L2，int m,int n ) {//将两个单链表连接在一起 ListNode *p , *q, *s ;
//s指向短表的头结点,q指向长表的开始结点，回收长表头结点空间 if (m<=n)
{s=L1;q=L2->next;free(L2);} else {s=L2;q=L1->next;free(L1);} p=s;
while ( p->next ) p=p->next; //查找短表终端结点 p->next = q; //将长表的开始结点链接在短表终端结点后 return s; }
本算法的主要操作时间花费在查找短表的终端结点上，所以本算的法时间复杂度为：
O(min(m,n)) 关闭
2.13 设 A和B是两个单链表，其表中元素递增有序。试写一算法将A和B归并成一个按元素值递减有序的单链表C，并要求辅助空间为O(1)，请分析算法的时间复杂度。 解：
根据已知条件，A和B是两个递增有序表，所以可以先取A表的表头建立空的C表。然后同时扫描A表和B表，将两表中最大的结点从对应表中摘下，并作为开始结点插入C表中。如此反复，直到A表或B表为空。最后将不为空的A表或B表中的结点依次摘下并作为开始结点插入C表中。这时，得到的C表就是由A表和B表归并成的一个按元素值递减有序的单链表C。并且辅助空间为O(1)。 算法如下：
LinkList MergeSort ( LinkList A , LinkList B )
{// 归并两个带头结点的递增有序表为一个带头结点递减有序表 ListNode *pa , *pb , *q , *C ; pa=A->next;//pa指向A表开始结点
C=A;C->next=NULL;//取A表的表头建立空的C表 pb=B->next;//pb指向B表开始结点 free(B);//回收B表的头结点空间 while ( pa && pb) {
if ( pb->data <= pa->data ) { // 当B中的元素小于等于A中当前元素时，将pa表的开始结点摘下
q=pa;pa=pa->next; } else
{// 当B中的元素大于A中当前元素时，将pb表的开始结点摘下
q=pb;pb=pb->next;}
q->next=C->next;C->next=q;//将摘下的结点q作为开始结点插入C表
}
//若pa表非空，则处理pa表 while(pa){
q=pa;pa=pa->next;
q->next=C->next;C->next=q;} //若pb表非空，则处理pb表 while(pb){
q=pb;pa=pb->next;
q->next=C->next;C->next=q;} return(C); }
该算法的时间复杂度分析如下：
算法中有三个while 循环，其中第二个和第三个循环只执行一个。每个循环做的工作都是对链表中结点扫描处理。整个算法完成后，A表和B表中的每个结点都被处理了一遍。所以若A表和B表的表长分别是m和n，则该算法的时间复杂度O(m+n) 关闭
2.14 已知单链表L是一个递增有序表，试写一高效算法，删除表中值大于min 且小于max的结点(若表中有这样的结点)，同时释放被删结点的空间，这里min 和 max是两个给定的参数。请分析你的算法的时间复杂度。 解：
要解这样的问题，我们首先想到的是拿链表中的元素一个个地与max和min比较，然后删除这个结点。由于为已知其是有序链表，则介于min 和max之间的结点必为连续的一段元素序列。所以我们只要先找到所有大于min结点中的最小结点的直接前趋结点*p后，依次删除小于max的结点，直到第一个大于等于max结点*q位置，然后将*p结点的直接后继指针指向*q结点。 算法如下：
void DeleteList ( LinkList L, DataType min , DataType max ) {
ListNode *p , *q , *s; p=L;
while( p->next && p->next->data <=min ) //找比min大的前一个元素位置 p=p->next;
q=p->next;//p指向第一个不大于min结点的直接前趋，q指向第一个大于min的结点
while(q &&q->data
free(s);//删除结点，释放空间 }