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

   /2005-05-08

 

while( q  && q->data < max ) //找比max小的最后一个元素位置
{
q=q->next;

}
h=p->next;
p->next=q;//把断点链上
free(h);// 释放空间

}

 

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

(答案及点评) 2.15 写一算法将单链表中值重复的结点删除,使所得的结果表中各结点值均不相同。

2.15 解:

本题 可以这样考虑,先取开始结点中的值,将它与其后的所有结点值一一比较,发现相同的就删除掉,然后再取第二结点的值,重复上述过程直到最后一个结点。

第二种算法是将单链表按值的大小排序,排好后的结点按相同的删除。

具体算法略。


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

(答案及点评) 2.16 假设在长度大于1的单循环链表中,既无头结点也无头指针。s为指向链表中某个结点的指针,试编写算法删除结点*s的直接前趋结点。


2.16 解:
已知指向这个结点的指针是*s,那么要删除这个结点的直接前趋结点,就只要找到一个结点,它的指针域是指向*s的,把这个结点删除就可以了。

算法如下:
void DeleteNode( ListNode *s)
{
//删除单循环链表中指定结点的直接前趋结点
ListNode *p, *q;
p=s;
while( p->next->next!=s)
{
q=p; /
p=p->next;
}
q->next=s; //删除结点
free(p); //释放空间
}


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

(答案及点评) 2.17 已知由单链表表示的线性表中,含有三类字符的数据元素(如:字母字符、数字字符和其它字符),试编写算法构造三个以循环链表表示的线性表,使每个表中只含同一类的字符,且利用原表中的结点空间作为这三个表的结点空间,头结点可另辟空间。


2.17  解:

要解决这样的问题,只要新建三个头结点,然后在原来的单链表中依次查询,找到一类字符结点时,就摘下此结点链接到相应头结点指明的新链表中就是了。

算法如下:
//设已建立三个带头结点的空循环链表A,B,C.
//以下是
void DivideList( LinkList L, LinkList A, LinkList B, LinkList C)
{
ListNode *p=L->next, *q;
ListNode *a=A,
ListNode  *b=B;
ListNode  *c=C;
while ( p )
{
if ( p->data>='a' &&p->data<='z'|| p->data>='A' &&p->data<='Z')
{
q=p;//保存字母结点位置
p=p->next;//指向下一结点
a->next=q;//将字母结点链到A表中
q->next=A;// 形成循环链表
a=a->next; // 指向下一结点
}

else if( p->data>='0' && p->data<='9')
{// 分出数字结点
q=p;
p=p->next;
b->next=q;
q->next=B;
b=b->next;
}
else
{//分出其他字符结点
q=p;
p=p->next;
c->next=q;
q->next=C;
c=c->next;
}
}
}//结束

 

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

(答案及点评) 2.18 设有一个双链表,每个结点中除有prior、data和next三个域外,还有一个访问频度域freq,在链表被起用之前,其值均初始化为零。每当在链表进行一次LocateNode(L,s)运算时,令元素值为x的结点中freq域的值加1,并调整表中结点的次序,使其按访问频度的递减序排列,以便使频繁访问的结点总是靠近表头。试写一符合上述要求的LocateNode运算的算法。

2.18  解:

给freq域的值加1比较容易。就是每次加1后需进行排序比较麻烦。我们可以这样考虑,每次访问一个值为x的结点后,从表头开始找,根据结点中的freq值,如果找到比它小的结点,就把当前结点摘下,插入到freq值比它小的结点前面,就完成排序了。

算法如下:

void LocateNode(  LinkList  L,  DataType  x)
{
ListNode  *p, *q;
p=L->next;//带有头结点
q=L->next;
while( p )
{
if( p->data!=x) p=p->next;
else {
p->freq++;
break;
}
}
while ( q )
{
if( q->freq > p->freq) q=q->next;
else {
p->prior->next=p->next; //摘下当前结点
p->next=q;       //插入到freq不大于它的结点前
p->prior=q->p
}
}
}


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

第二章 线性表 复习要点

本章复习要点是:

线性表的逻辑结构特征、常见的线性表的六种基本运算,并可以根据这些基本运算组合得到更复杂的运算。

顺序表的特征、顺序表中结点地址的计算。

顺序表上实现的基本运算(算法):主要是插入和删除的算法。顺序表的算法应该掌握。算法时间复杂度要记住。

单链表的特征、图形表示法。

单链表的各种算法实现,并能运用这些算法解决一些简单问题;

循环链表的特征、双链表的特征以及它们的主要算法实现。

可能出的题型有:填空题、简答题、应用题和算法题.

如:

在双链表中插入运算的时间复杂度为:(...)

A.O(1) B.O(n) C.O(lgn) D.O(nlgn)


请问头指针,开始结点和头结点的区别与联系。


关于单链表上进行排序的算法设计。 等等


相关话题/

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