严蔚敏数据结构为主的笔记四

   /2005-05-08

 

ListNode  *pa , *pb ,  *qa  , *qb ;
pa=A;
pb=B ;
qa=A->next;
qb=B->next;
while ( qa && qb)
{
if ( qb->data < qa->data )
{
// 当B中的元素小于A中当前元素时,插入到它的前面
pb=qb;
qb=qb->next ;// 指向B中下一元素
pa->next=pb;
pb->next=qa;
pa=pb;

}
             else if ( qb->data  >=  pa->data && qb->data <= qa->data)
{
//   当B中元素大于等于A中当前元素
//   且小于等于A中后一元素时,
//    将此元素插入到A的当前元素之后
pa=qa;
qa=qa->next;   // 保存A的后一元素位置
pb=qb;    
qb=qb->next;   // 保存B的后一元素位置
pa->next=pb;   //插入元素
pb->next=qa;
}

else
{
//  如果B中元素总是更大,指针移向下一个A元素
pa=qa;
qa=qa->next;
}
}

if ( qb )// 如果A表已到终端而B表还有结点未插入
{
// 将B表接到A表后面
pa->next=qb;
}

LinkList  C=ReverseList ( A );// 调用前面2.8题所设计的逆置函数

return     C;  //返回新的单链表C, 已是递减排列
}


该算法的时间复杂度分析如下:
算法中只有一个while 循环,在这个循环中,按照最坏的情况是B元素既有插到A的最前的,也有插到最后的,也就是说需要把A中元素和B中元素全部检查比较过,这时的所费时间就是m+n.  而新链表的长度也是m+n+1 (有头结点),这样逆置函数的执行所费时间为m+n+1.所以可得整个算法的时间复杂度为:
m+n+m+n+1=2(m+n)+1= O(m+n)

---------------------------------------------------------------------------------------------------------

为验证本题,晓津设计了一个程序,清单如下:

//ListStruct.h  将链表结构存为头文件
typedef char DataType; //假设结点的数据类型是字符型
typedef struct node { //结点类型定义
DataType data;
struct node *next;//结点的指针域
}ListNode;

typedef ListNode * LinkList;

// 以下是源文件 //  在VC++中运行通过。

#include
#include
#include "ListStruct.h"
#include

LinkList CreatList (void)
{ //用尾插法建立带头结点的单链表

char ch;
LinkList head = (LinkList)malloc(sizeof( ListNode)); //生成头结点
ListNode *s , *r;
r=head;//尾指针亦指向头结点
while ((ch=getchar())!='/n')
{
s=(ListNode *) malloc (sizeof(ListNode));
s->data=ch;
r->next=s;
r=s;
}
r->next=NULL;
return  head;
}


void OutList( LinkList L)
{
 ListNode *p;
 p=L;
 while (p->next)
 {
 cout <<  p->next->data << "  " ;
 p=p->next;
 }
 cout << endl;
}
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
}

 

LinkList    MergeSort (  LinkList  A  , LinkList B )
{
// 归并两个递增有序表为一个递减有序表

ListNode  *pa , *pb ,  *qa  , *qb ;
pa=A;
pb=B ;
qa=A->next;
qb=B->next;
while ( qa && qb)
{
if ( qb->data < qa->data )
{
// 当B中的元素小于A中当前元素时,插入到它的前面
pb=qb;
qb=qb->next ;// 指向B中下一元素
pa->next=pb;
pb->next=qa;
pa=pb;

}


             else if ( qb->data  >=  pa->data && qb->data <= qa->data)
{
//   当B中元素大于等于A中当前元素
//   且小于等于A中后一元素时,
//    将此元素插入到A的当前元素之后
pa=qa;
qa=qa->next;   // 保存A的后一元素位置
pb=qb;    
qb=qb->next;   // 保存B的后一元素位置
pa->next=pb;   //插入元素
pb->next=qa;
}

else
{
//  如果B中元素总是更大,指针移向下一个A元素
pa=qa;
qa=qa->next;
}
}

if ( qb )// 如果A表已到终端而B表还有结点未插入
{
// 将B表接到A表后面
pa->next=qb;
}

LinkList  C=ReverseList ( A );// 调用前面2.8题所设计的逆置函数

return     C;  //返回新的单链表C, 已是递减排列
}


void main()
{
LinkList A, B, C;
A=CreatList();
OutList (A);
B=CreatList();
OutList (B);
C=MergeSort (A ,B);
OutList (C);
}


---------------------------------------------------


--------------------------------------------------------------------------------

(答案及点评) 2.14 已知单链表L是一个递增有序表,试写一高效算法,删除表中值大于min 且小于max的结点(若表中有这样的结点),同时释放被删结点的窨,这里min 和 max是两个给定的参数。请分析你的算法的时间复杂度。

2.14 解:
要解这样的问题,我们首先想到的是拿链表中的元素一个个地与max和min比较,然后删除这个结点,其实因为已知其是有序链表,所以我们只要找到大于min的结点的直接前趋结点,再找到小于max的结点,然后一并把中间的全部摘掉就可以了。

算法如下:
void DeleteList ( LinkList L, DataType min , DataType max )
{
ListNode *p , *q , *h;
p=L->next;
while( p  && p->data <=min )
{//找比min大的前一个元素位置
q=p;
p=p->next;

}
p=q;//保存这个元素位置


相关话题/

  • 领限时大额优惠券,享本站正版考研考试资料!
    大额优惠券
    优惠券领取后72小时内有效,10万种最新考研考试考证类电子打印资料任你选。涵盖全国500余所院校考研专业课、200多种职业资格考试、1100多种经典教材,产品类型包含电子书、题库、全套资料以及视频,无论您是考研复习、考证刷题,还是考前冲刺等,不同类型的产品可满足您学习上的不同需求。 ...
    本站小编 Free壹佰分学习网 2022-09-19