1.9【答案】有时为了比较两个同数量级算法的优劣，须突出主项的常数因子，而将低次项用大"O"记号表示。
例如，设T1（n）=1.39nlgn+100n+256=1.39nlgn+O（n）,T2（n）=2.0nlgn-2n=2.0lgn+O（n）,这两个式子表示，当n足够大时T1（n）优于T2（n），因为前者的常数因子小于后者。
请用此方法表示下列函数，并指出当n足够大时，哪一个较优，哪一个较劣?
（1）T1（n）=5n2-3n+60lgn
（2）T2（n）=3n2+1000n+3lgn
（3）T3（n）=8n2+3lgn
（4）T4（n）=1.5n2+6000nlgn
函数 大"O"表示 优劣
（1）T1（n）=5n2-3n+60lgn 5n2+O（n） 较差
（2）T2（n）=3n2+1000n+3lgn 3n2+O（n） 其次
（3）T3（n）=8n2+3lgn 8n2+O（lgn） 最差
（4）T4（n）=1.5n2+6000nlgn 1.5n2+O（nlgn） 最优
第二章
2.1试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。
答：
开始结点是指链表中的第一个结点，也就是没有直接前趋的那个结点。
链表的头指针是一指向链表开始结点的指针（没有头结点时），单链表由头指针唯一确定，因此单链表可以用头指针的名字来命名。
头结点是在链表的开始结点之前附加的一个结点。
有了头结点之后，头指针指向头结点，不论链表否为空，头指针总是非空。
而且头指针的设置使得对链表的第一个位置上的操作与在表其他位置上的操作一致（都是在某一结点之后）。
2.2何时选用顺序表、何时选用链表作为线性表的存储结构为宜?
答:
在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以下几方面的考虑：
1.基于空间的考虑。
当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。
2.基于时间的考虑。
若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之，若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。
并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。
2.3在顺序表中插入和删除一个结点需平均移动多少个结点?
具体的移动次数取决于哪两个因素?
答：
在等概率情况下，顺序表中插入一个结点需平均移动n/2个结点。
删除一个结点需平均移动（n-1）/2个结点。
具体的移动次数取决于顺序表的长度n以及需插入或删除的位置i。
i越接近n则所需移动的结点数越少。
2.4为什么在单循环链表中设置尾指针比设置头指针更好?
答：
尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear->next->next和rear,查找时间都是O
（1）。
若用头指针来表示该链表，则查找终端结点的时间为O（n）。
2.5在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去?
若可以，其时间复杂度各为多少?
答：
下面分别讨论三种链表的情况。
1.单链表。
若指针p指向某结点时，能够根据该指针找到其直接后继，能够顺后继指针链找到*p结点后的结点。
但是由于不知道其头指针，所以无法访问到p指针指向的结点的直接前趋。
因此无法删去该结点。
2.双链表。
由于这样的链表提供双向指针，根据*p结点的前趋指针和后继指针可以查找到其直接前趋和直接后继，从而可以删除该结点。
其时间复杂度为O
（1）。
3.单循环链表。
根据已知结点位置，可以直接得到其后相邻的结点位置（直接后继），又因为是循环链表，所以我们可以通过查找，得到p结点的直接前趋。
因此可以删去p所指结点。
其时间复杂度应为O（n）。
2.6下述算法的功能是什么?
LinkListDemo（LinkListL）{//L是无头结点单链表
ListNode*Q,*P;
if（L&&L->next）{
Q=L;L=L->next;P=L;
while（P->next）P=P->next;
P->next=Q;Q->next=NULL;
}
returnL;
}//Demo
答：
该算法的功能是：
将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。
二、算法设计题
2.7设线性表的n个结点定义为（a0,a1,...an-1），重写顺序表上实现的插入和删除算法：
InsertList和DeleteList.
解：
算法如下:
#defineListSize100//假定表空间大小为100
typedefintDataType;//假定DataType的类型为int型
typedefstruct{
DataTypedata[ListSize];//向量data用于存放表结点
intlength;//当前的表长度
}Seqlist;
//以上为定义表结构
voidInsertList（Seqlist*L,Datatypex,inti）
{
//将新结点x插入L所指的顺序表的第i个结点ai的位置上，即插入的合法位置为：
0<=i<=L->length
intj;
if（i<0||i>L->length）
Error（"positionerror"）;//非法位置，退出，该函数定义见教材P7.
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++;
}
voidDeleteList（Seqlist*L,inti）
{//从L所指的顺序表中删除第i个结点ai,合法的删除位置为0<=i<=L->length-1
intj;
if（i<0||i>=L->length）
Error（"positionerror"）;
for（j=i;jlength;j++）
L->data[j]=L->data[j+1];//结点前移
L->length--;//表长减小
}
2.8试分别用顺序表和单链表作为存储结构，实现将线性表（a0,a1,...an-1）就地逆置的操作，所谓"就地"指辅助空间应为O
（1）。
答:
1.顺序表：
要将该表逆置，可以将表中的开始结点与终端结点互换，第二个结点与倒数第二个结点互换，如此反复，就可将整个表逆置了。
算法如下：
//顺序表结构定义同上题
voidReverseList（Seqlist*L）
{
DataTypetemp;//设置临时空间用于存放data
inti;
for（i=0;i<=L->length/2;i++）//L->length/2为整除运算
{temp=L->data[i];//交换数据
L->data[i]=L->data[L->length-1-i];
L->data[L->length-1-i]=temp;
}
}
2.链表：
分析：
可以用交换数据的方式来达到逆置的目的。
但是由于是单链表，数据的存取不是随机的，因此算法效率太低。
可以利用指针改指来达到表逆置的目的。
具体情况入下：
（1）当链表为空表或只有一个结点时，该链表的逆置链表与原表相同。
（2）当链表含2个以上结点时，可将该链表处理成只含第一结点的带头结点链表和一个无头结点的包含该链表剩余结点的链表。
然后，将该无头结点链表中的所有结点顺着链表指针，由前往后将每个结点依次从无头结点链表中摘下，作为第一个结点插入到带头结点链表中。
这样就可以得到逆置的链表。
算法是这样的：
结点结构定义如下：
typedefcharDataType;//假设结点的数据域类型的字符
typedefstructnode{//结点类型定义
DataTypedata;//结点的数据域
structnode*next;//结点的指针域
}ListNode;
typedefListNode*LinkList;
ListNode*p;
LinkListhead;
LinkListReverseList（LinkListhead）
{//将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;
}
returnhead;
}
returnhead;//如是空表或单结点表，直接返回head
}
2.9设顺序表L是一个递增有序表，试写一算法，将x插入L中，并使L仍是一个有序表。
答：
因已知顺序表L是递增有序表，所以只要从顺序表终端结点（设为i位置元素）开始向前寻找到第一个小于或等于x的元素位置i后插入该位置即可。
在寻找过程中，由于大于x的元素都应放在x之后，所以可边寻找，边后移元素，当找到第一个小于或等于x的元素位置i时，该位置也空出来了。
算法如下：
//顺序表存储结构如题2.7
voidInsertIncreaseList（Seqlist*L,Datatypex）
{
inti;
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大（或相等）的结点数据，在这个位置插入就可以了。
（边寻找，边移动）算法如下：
voidInsertDecreaseList（Seqlist*L,Datatypex）
{
inti;
if（L->length>=ListSize）
Error（“overflow"）;
for（i=L->length;i>0&&L->data[i-1] L->data[i]=L->data[i];//比较并移动元素
L->data[i]=x;
L->length++;
}
2.11写一算法在单链表上实现线性表的ListLength（L）运算。
解：
由于在单链表中只给出一个头指针，所以只能用遍历的方法来数单链表中的结点个数了。
算法如下：
intListLength（LinkListL）
{
intlen=0;
ListNode*p;
p=L;//设该表有头结点
while（p->next）
{
p=p->next;
len++;
}
returnlen;
}
2.12已知L1和L2分别指向两个单链表的头结点，且已知其长度分别为m和n。
试写一算法将这两个链表连接在一起，请分析你的算法的时间复杂度。
解：
分析：
由于要进行的是两单链表的连接，所以应找到放在前面的那张表的表尾结点，再将后表的开始结点链接到前表的终端结点后即可。
该算法的主要时间消耗是用在寻找第一张表的终端尾结点上。
这两张单链表的连接顺序无要求，并且已知两表的表长，则为了提高算法效率，可选表长小的单链表在前的方式连接。
具体算法如下：
LinkListLink（LinkListL1,LinkListL2，intm,intn）
{//将两个单链表连接在一起
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;//将长表的开始结点链接在短表终端结点后
returns;
}
本算法的主要操作时间花费在查找短表的终端结点上，所以本算的法时间复杂度为：
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）。
算法如下：
LinkListMergeSort（LinkListA,LinkListB）
{//归并两个带头结点的递增有序表为一个带头结点递减有序表
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）
升级会员 