算法:删除单链表和顺序表。删除序列表中具有相同值的冗余节点。

作者:来源:2006年9月4日

13.将哨兵放在R[n]中，将排序后的记录放在R[0..n-1]，并重写直接插入排序算法。

解决方案:

重写的算法如下:

void InsertSort(SeqList R)

{//插入并排序记录r [0...n-1]按升序排列。

int i，j；

for(I = n-2；我& gt=0;I-)//Insert R[n-2]..R[0]依次在有序区域中。

if(R[i]。key & gtR[i+1]。key) //如果不是，R[i]保持不变。

{

R[n]= R[I]；j = I+1；//R[n]是哨兵

Do{ //从左到右查找有序区域中的插入位置。

R[j-1]= R[j]；//移动关键字小于R[i]的记录。钥匙在右边。

j++；

}while(R[j].key & ltR[n]。key])；

R[j-1]= R[n]；//将R[i]插入正确的位置。

}//endif

}//InsertSort。

14.用单链表作为存储结构实现直接插入排序算法。

解决方案:

#define int KeyType //将KeyType定义为int类型。

typedef结构节点{

KeyType键；//关键字字段

其他信息类型信息；//其他信息字段，

结构节点* next//链表中的指针字段

} RecNode//记录节点类型

typedef RecNode * LinkList//单个链表由LinkList表示。

void InsertSort(链表头)

{//链式存储结构的直接插入排序算法，其中head是以前导节点为单位的单链表。

RecNode *p，*q，* s；

如果((head-& gt；接下来)& amp& amp(头-& gt；下一个-& gt；next))///当表中的节点数大于1时。

{

p = head-& gt；下一个-& gt；接下来；//p指向第二个节点。

head->；next = NULL

q =头；//指向插入位置的前置节点。

while(p)& amp；& amp(问->；接下来)& amp& amp(p->；key & ltq->；下一个-& gt；关键)

q = q-& gt；接下来；

如果(p)

{ s = p；p = p-& gt；接下来；//移除要插入的节点。

s-& gt；next = q-& gt；接下来；//在Q节点后插入适当的位置

q->；next = s；

}

}

}

15.设计一个算法，在尽可能短的时间内重新排列数组，把所有否定关键字放在所有非否定关键字之前。请分析算法的时间复杂度。

解决方案:

因为只有否定的关键词需要排在第一位，没有精确的排序顺序，所以这个算法采用了两端扫描的方法，就像快速排序中使用的方法一样。当左侧扫描到正数时，停止向右侧扫描，遇到负数时，与左侧的当前记录进行交换，这样一次行程即可完成排序。

无效度假村(SeqList R)

{//重新排列数组，使negative关键字排在前面。

int i=1，j = n；//数组存储在r [1...n]

while(我& ltj)//I & lt；j表示扫描尚未完成。

{ while(I & lt；强生公司。& ampR[i]。key & lt0) //如果遇到负数，继续扫描。

i++；

R[0]= R[I]；//R[0]是辅助空格。

while(我& lt强生公司。& ampR[j]。key & gt=0)//如果遇到正数，继续向左扫描。

j-；

R[i++]= R[j]；R[j-]= R[0]；//交换当前两个元素并移动指针。

}//结束时间

}//度假村

在任何情况下，该算法中的比较次数为n(每个元素为0)，交换次数小于n/2。一般来说，时间复杂度为O(n)。

*16.写一个双向冒泡排序算法，就是在排序过程中交替改变扫描方向。

解决方案:

算法如下:

void冒泡排序(SeqList R)

{//r [1...n]是要排序的文件，采用双向扫描冒泡排序。

int i，j，k；

布尔交换；//交换标签

I = n；j = 1；

交换=真；

while(I & gt；j)& amp；& amp(交换)

{ k = I-1；交换=假；

while(k & gt；=j)//从下到上扫描

{ if(r[k]& gt；r[k+1])

{ r[0]= r[k]；r[k]= r[k+1]；r[k+1]= r[k]；交换=真；//交换

}//endif

k-；

}//结束时间

如果(交换)

{ exchange = FALSE

j++；k = j+1；

while(k & lt；=i)//从上到下扫描

{ if(r[k]& lt；r[k-1])

{ r[0]= r[k]；r[k]= r[k-1]；r[k-1]= r[k]；交换=真；//交换

}//endif

k++；

}结束时间

I-；

}//endif

}结束时间

}//endsort

17.下面是一个自上而下冒泡排序的伪代码算法，使用lastExchange记录每次扫描中交换的最后一个元素的位置，并以此作为下一个排序循环终止的控制值。请写一个自下而上扫描的冒泡排序算法。

void BubbleSort(int A[]，int n)

//让A[0..n-1]是整数向量。

int lastExchange，j，I = n-1；

while(I & gt；0)

last exchange = 0；

for(j = 0；j & lt我；J++)//扫描A[0..i]从上到下。

if(A[j+1]& lt；A[j]){

交换A[j]和A[j+1]；

last exchange = j；

}

i = lastExchange//将I设置为最后一个交换位置。

}//结束时间

}//BubbleSort

解决方案:算法如下:

void BubbleSort(int A[]，int n)

//让A[0..n-1]是整数向量。

int lastExchange，j，I = 0；

while(我& ltN) //这个很重要。如果不改为这个，算法会无限循环。

last exchange = n；

for(j = n-1；j & gt我；j-)//扫描A[0..i]从下到上。

if(A[j-1]& lt；A[j]){

交换A[j]和A[j-1]；

last exchange = j；

}

i = lastExchange//将I设置为最后一个交换位置。

}//结束时间

}//BubbleSort

18.要重写快速排序，需要通过选择三个来选择划分的基准记录；如果当前排序的区间长度小于或等于3，则直接插入排序，不进行分割。

解决方案:

重写后的算法如下:

void快速排序(SeqList R，int low，int high)

{//Sort R [low...高]迅速

int pivotpos

if(高-低& lt=2)//如果当前区域中的元素少于3个，

{//执行直接插入排序。

InsertSort(R，low，high)；

}

其他

{

pivot pos = mid partition(R，low，high)；

QuickSort(R，low，pivot pos-1)；

QuickSort(R，pivotpos+1，高)；

}

}//快速排序

int mid partition(seq list R，int i，int j)

{//以三者之法则为基准。

if(R[(i+j)/2]。key & gtR[i]。关键)

{交换R[(i+j)/2]和R[I]；}

if(R[i]。key & gtR[j]。关键)

{交换R[i]和R[j]；}

if(R[i]。键)& ltR[(i+j)/2]。关键)

{交换R[i]和R[(I+j)/2]；}

//上面的三个if语句使区间中第一条记录的键值成为三个键的中间值。

返回部分(R，I，j)；//所以我们还是可以用原来的划分算法。

}

19.对于给定的j(1≤j≤n)，要求在无序记录区R[1中根据关键字从小到大找到第j个位置的记录..n](即寻找无序集合中的第j个最小元素)，并尝试利用快速排序的除法思想编写算法实现上述搜索操作。

答:

int快速排序(SeqList R，int j，int low，int high)

{//Sort R [low...高]迅速

int pivotpos//被分割的基准记录的位置

if(低& ltHigh){//仅当间隔长度大于1时排序。

pivotpos=Partition(R，low，high)；//分频R[低...高]

if (pivotpos==j)返回r[j]；

else if(pivot pos & gt；j) return(R，j，low，pivot pos-1)；

else返回quicksort(R，j，pivotpos+1，高)；

}

}//快速排序

20.写一个以单链表为存储结构的直接选择排序算法。

答:

#define int KeyType //将KeyType定义为int类型。

typedef结构节点{

KeyType键；//关键字字段

其他信息类型信息；//其他信息字段，

结构节点* next//链表中的指针字段

} RecNode//记录节点类型

typedef RecNode * LinkList//单个链表由LinkList表示。

void selectsort(链表头)

{RecNode *p，*q，* s；

if(head-& gt；接下来)& amp& amp(头-& gt；下一个-& gt；下一个)

p = head-& gt；接下来；//p指向当前排序顺序中最大元素的前任。

while(p->；下一个)

{ q = p-& gt；接下来；s = p；

while(q)

{ if(q-& gt；key & lts-& gt；key)s = q；

q = q-& gt；接下来；

}//结束时间

交换S节点和P节点的数据；

p = p-& gt；接下来；

}//结束时间

}//endif

}//endsort

21.写一个heapInsert(R，key)算法，在堆R中插入关键字，保证插入R后还是堆..提示:应该在heap R中增加一个length属性描述(即应该重写本章定义的SeqList的类型描述，以包含length字段)；将键插入R中现有元素的尾部(即原堆的长度加上位置1，插入堆的长度加上1)，然后自下而上调整，使插入的关键字满足属性。请分析一下算法的时间。

答:

#define n 100//假设文件的长度尽可能长。

typedef int KeyType//将KeyType定义为int类型。

typedef结构节点{

KeyType键；//关键字字段

其他信息类型信息；//其他信息字段，

} Rectype//记录节点类型

typedef结构{

Rectype数据[n]；//存储记录的空间

int长度；//文件长度

} seqlist

void heapInsert(seqlist *R，KeyType key)

{//原堆元素在r->；data[1]~ R-& gt；数据[R-& gt；长度]，

//将新的关键字key插入R-& gt；数据[R-& gt；长度+1]位置，

//带R-& gt；Data[0]是辅助空间，调整为堆(这里设为大根堆)。

int large//large指向调整节点左右子节点中关键字较大的一个。

int低，高；//low和high分别指向要调整的堆的第一条和最后一条记录。

int I；

r-& gt；长度++；r-& gt；数据[R-& gt；长度】。key = key//插入新记录

for(I = R-& gt；长度/2；我& gt0;I-)//构建一个堆

{

低= I；高= R-& gt；长度；

r-& gt；数据[0]。key = R-& gt；数据[低]。关键；//R-& gt；Data[low]是当前调整的节点。

for(大= 2 *低；大号& lt=高；large*=2){

//如果大& gt高表示R-& gt；数据【低】是一片叶子，调整结束；

//否则将大指针指向R-& gt；数据的左子[低]

if(large & lt；高& amp& ampr-& gt；数据[大]。key & ltr-& gt；数据[大+1]。关键)

大++的；//如果R-& gt；数据[低]的右子存在。

//并且关键字大于左兄弟，make large指向它。

if(R-& gt；数据[0]。key & ltr-& gt；数据[大]。关键)

{ R-& gt；数据[低]。key = R-& gt；数据[大]。关键；

低=大；//使低点指向新的调整节点。

}

else break//当前调整节点不小于其子节点的关键字，调整完成。

}//结束

r-& gt；数据[低]。key = R-& gt；数据[0]。关键；//将调整后的节点放在最后的位置。

}//的结尾

} heap insert结束

算法分析:

如果文件长度为n，算法需要调整n/2遍，总时间复杂度和初始堆差不多，最差时间复杂度为O(nlgn)，辅助空间为O(1)。

22.写一个堆构建算法:从一个空堆开始，依次读入元素，调用上面问题中的堆插入算法，将元素插入堆中。

答:

void BuildHeap(seqlist *R)

{

KeyType键；

r-& gt；长度= 0；//生成一个空堆

scanf("%d "，& amp关键)；//将MAXINT设置为不可能的关键字。

而(键！=MAXINT)

{

heapInsert(R，key)；

scanf("%d "，& amp关键)；

}

}

23.写一个堆删除算法:HeapDelete(R，I)，从堆中删除R[i]，分析算法时间。建议:首先将R[i]与堆中的最后一个元素交换，将堆长减少1，然后从位置I向下调整，满足堆性质。

答:

void HeapDelete(seqlist *R，int i)

{//原堆元素在r->；data[1]~ R-& gt；数据[R-& gt；长度]，

//put R-& gt；数据[i]被删除，即R->；数据[R-& gt；长度]放入R-& gt；在数据[i]之后，

//put R-& gt；长度减去1，然后调整堆。

//带R-& gt；Data[0]是辅助空间，调整为堆(这里设为大根堆)。

int large//large指向调整节点左右子节点中关键字较大的一个。

int低，高；//low和high分别指向要调整的堆的第一条和最后一条记录。

int j；

如果(i & gtr-& gt；长度)

错误(“没有这样的节点”)；

r-& gt；数据[i]。key = R-& gt；数据[R-& gt；长度】。关键；

r-& gt；长度-；r-& gt；数据[R-& gt；长度】。key = key//插入新记录

for(j = I/2；j & gt0;j-)//构建一个堆

{

低= j；高= R-& gt；长度；

r-& gt；数据[0]。key = R-& gt；数据[低]。关键；//R-& gt；Data[low]是当前调整的节点。

for(大= 2 *低；大号& lt=高；large*=2){

//如果大& gt高表示R-& gt；数据【低】是一片叶子，调整结束；

//否则将大指针指向R-& gt；数据的左子[低]

if(large & lt；高& amp& ampr-& gt；数据[大]。key & ltr-& gt；数据[大+1]。关键)

大++的；//如果R-& gt；数据[低]的右子存在。

//并且关键字大于左兄弟，make large指向它。

if(R-& gt；数据[0]。key & ltr-& gt；数据[大]。关键)

{ R-& gt；数据[低]。key = R-& gt；数据[大]。关键；

低=大；//使低点指向新的调整节点。

}

else break//当前调整节点不小于其子节点的关键字，调整完成。

}//结束

r-& gt；数据[低]。key = R-& gt；数据[0]。关键；//将调整后的节点放在最后的位置。

}//的结尾

} heap delete结束

24.假设两个单链表中的元素都是升序排列的，试着写一个算法，把这两个有序链表合并成一个升序排列的单链表。该算法应该使用原始的链表节点空间。

答:

typedef结构节点{

KeyType键；//关键字字段

其他信息类型信息；//其他信息字段，

结构节点* next//链表中的指针字段

} RecNode//记录节点类型

typedef RecNode * LinkList//单个链表由LinkList表示。

无效合并排序(链表la，链表lb，链表lc)

{RecNode *p，*q，*s，* r；

lc = la

p = la//p是la表的扫描指针，指向要比较的节点的前一个位置。

q=lb->接下来；//q是lb表的扫描指针，指向比较的节点。

while(p->；接下来)& amp& amp(问)

如果(p->；下一个-& gt；key & lt= q->；关键)

p = p-& gt；接下来；

else { s = q；q = q-& gt；接下来；

s-& gt；next = p-& gt；接下来；p->；next = s；//将S节点插入P节点后，

p = s；}

如果(！p->；下一个)p-& gt；next = q；

免费(磅)；

}

25.设向量A[0..n-1]包含n个不同的整数，每个元素的值在0到n-1之间。试写一个时间为O(n)的算法对向量A排序，结果可以输出到另一个向量B[0..n-1]。

答:

sort(int *A，int *B)

{//对向量A进行排序，并发送给向量b。

int I；

for(I = 0；我& lt= n-1；i++)

b[A[I]]= A[I]；

}

*26.为一组按字典顺序排列的英语单词写一个基数排序算法。让所有单词都由大写字母组成，最长的单词有d个字母。提示:所有长度小于d个字母的单词末尾都要用空格填充，排序时要设置27个方框，分别对应空格，a，B...z分别为。

答:

#define KeySize 10 //设置关键字位数d=10。

#定义基数27 //基数rd是27。

typedef RecType数据类型；//将队列中节点的数据类型更改为RecType类型。

typedef结构节点{

char key[KeySize]；//关键字字段

其他信息类型信息；//其他信息字段，

} RecType//记录节点类型

typedef RecType seqlist[n+1]；

void半径排序

{

link queue B[基数]；

int I；

for(I = 0；我& lt基数；I++)//框是空的

init queue(& amp；b[I])；

for(I = KeySize-1；我& gt=0;I-){//从低到高做D-trip框排序。

Distribute(R，B，I)；//第一个KeySize-i传递分配

Collect(R，B)；//第一个KeySize-i集合

}

}

void Distribute(seqlist R，LinkQueue B[]，int j)

{//根据关键字的第j个分量分配，开头的框为空。

int I；

j = KeySize-j；//从低位开始确定关键字的位置。

for(I = 0；我& ltn；I++) //依次扫描R[i]并装箱。

if (R[i]。键[j]-' A ' & gt；26)

排队(& ampB[0]，R[I])；//将第j个关键字空格记录到第0个队列中。

否则排队(& ampB[0]，R[R[i]。key[j]-' A '+1])；

}

void Collect(seqlist R，LinkQueue B[])

{

//依次收集每个非空盒子里的记录，这个过程结束后所有盒子都是空的。

int i，j；

for(j = 0；j & lt基数；j++)

而(！队列清空(& ampB[j])

r[i++]=出列(& ampb[j])；//将出列记录依次输出到R[i]。

}