anyview

2.16③  已知指针la和lb分别指向两个无头结点单链表中
的首元结点。 下列算法是从表la中删除自第i个元素起共
len个元素后，将它们插入到表lb中第i个元素之前。试问
此算法是否正确? 若有错，则请改正之。

实现下列函数：
Status DeleteAndInsertSub(LinkList &la, LinkList &lb,
                          int i, int j, int len);
// la和lb分别指向两个单链表中第一个结点，        */
/* 本算法是从la表中删去自第i个元素起共len个元素，*/
/* 并将它们插入到lb表中第j个元素之前，           */
/* 若lb表中只有j-1个元素，则插在表尾。           */

单链表类型定义如下：
typedef struct LNode{
    ElemType      data;
    struct LNode *next;
} LNode, *LinkList;

2.17② 试写一算法，在无头结点的动态单链表上实现
线性表操作INSERT(L,i,b)，并和在带头结点的动态单
链表上实现相同操作的算法进行比较。

实现下列函数：
void Insert(LinkList &L, int i, ElemType b);

单链表类型定义如下：
typedef struct LNode{
    ElemType      data;
    struct LNode *next;
} LNode, *LinkList;

2.18②  同2.17题要求。试写一算法，
实现线性表操作DELETE(L,i)。

实现下列函数：
void Delete(LinkList &L, int i);

单链表类型定义如下：
typedef struct LNode{
    ElemType      data;
    struct LNode *next;
} LNode, *LinkList;

◆2.19③  已知线性表中的元素以值递增有序排列，并以
单链表作存储结构。试写一高效的算法，删除表中所有值
大于mink且小于maxk的元素(若表中存在这样的元素)同时
释放被删结点空间，并分析你的算法的时间复杂度（注意：
mink和maxk是给定的两个参变量，它们的值可以和表中的
元素相同，也可以不同）。

实现下列函数：
void DeleteSome(LinkList &L, ElemType mink, ElemType maxk);
/* Delete all the elements which value is between mink and  */
/* maxk from the single sorted LinkList with head pointer L.*/

单链表类型定义如下：
typedef struct LNode{
    ElemType      data;
    struct LNode *next;
} LNode, *LinkList;

2.20②  同2.19题条件，试写一高效的算法，删除表中所
有值相同的多余元素 (使得操作后的线性表中所有元素的
值均不相同) 同时释放被删结点空间，并分析你的算法的
时间复杂度。

实现下列函数：
void Purge(LinkList &L);

单链表类型定义如下：
typedef struct LNode{
    ElemType      data;
    struct LNode *next;
} LNode, *LinkList;

◆2.21③ 试写一算法，实现顺序表的就地逆置，
即利用原表的存储空间将线性表(a1,a2,…,an)
逆置为(an,an-1,…,a1)。

实现下列函数：
void Inverse(SqList &L);

顺序表类型定义如下：
typedef struct {
    ElemType *elem;
    int       length;
    int       listsize;
} SqList;

◆2.22③  试写一算法，对单链表实现就地逆置。

实现下列函数：
void Inverse(LinkList &L); 
/* 对带头结点的单链表L实现就地逆置 */

单链表类型定义如下：
typedef struct LNode{
    ElemType      data;
    struct LNode *next;
} LNode, *LinkList;

2.23③ 设线性表A=(a1,...,am), B=(b1,...,bn)，试写
一个按下列规则合并A、B为线性表C的算法，即使得
      C=(a1,b1,...,am,bm,bm+1,...,bn)  当m≤n时；
或者  C=(a1,b1,...,an,bn,an+1,...,am)  当m＞n时。
线性表A、B和C均以单链表作存储结构，且C表利用A表和
B表中的结点空间构成。注意：单链表的长度值m和n均未
显式存储。

实现下列函数：
void Merge(LinkList ha, LinkList hb, LinkList &hc)
/* 依题意，合并带头结点的单链表ha和hb为hc  */

单链表类型定义如下：
typedef struct LNode{
    ElemType      data;
    struct LNode *next;
} LNode, *LinkList;

◆2.24④  假设有两个按元素值递增有序排列的线性表
A和B，均以单链表作存储结构，请编写算法将A表和B表
归并成一个按元素值递减有序（即非递增有序，允许表
中含有值相同的元素）排列的线性表C， 并要求利用原
表（即A表和B表）的结点空间构造C表。

实现下列函数：
void Union(LinkList &lc, LinkList la, LinkList lb);
/* 依题意，利用la和lb原表的结点空间构造lc表 */

单链表类型定义如下：
typedef struct LNode{
    ElemType      data;
    struct LNode *next;
} LNode, *LinkList;

2.26④  假设以两个元素依值递增有序排列的线性表
A和B分别表示两个集合（即同一表中的元素值各不相
同），现要求另辟空间构成一个线性表C，其元素为A
和B中元素的交集，且表C中的元素也依值递增有序排
列。试对单链表编写求C的算法。

实现下列函数：
void Intersect(LinkList &hc, LinkList ha, LinkList hb);

单链表类型定义如下：
typedef struct LNode{
    ElemType      data;
    struct LNode *next;
} LNode, *LinkList;

2.31②  假设某个单向循环链表的长度大于1，且表
中既无头结点也无头指针。已知s为指向链表中某个
结点的指针，试编写算法在链表中删除指针s所指结
点的前驱结点。

实现下列函数：
ElemType DeleteNode(LinkList s); 
/* 删除指针s所指结点的前驱结点，并返回被删结点的元素值 */

单链表类型定义如下：
typedef struct LNode{
    ElemType      data;
    struct LNode *next;
} LNode, *LinkList;

2.32②  已知有一个单向循环链表，其每个结点中
含三个域：prev、data和next，其中data为数据域，
next为指向后继结点的指针域，prev也为指针域，
但它的值为空(NULL)，试编写算法将此单向循环链
表改为双向循环链表，即使prev成为指向前驱结点
的指针域。

实现下列函数：
void PerfectBiLink(BiLinkList &CL);

双向循环链表类型定义如下：
typedef struct BiNode {
    ElemType       data;
    int            freq; // 2.38题用
    struct BiNode *prev,
                  *next;
} BiNode, *BiLinkList;

◆2.33③  已知由一个线性链表表示的线性表中含有
三类字符的数据元素（如：字母字符、数字字符和其
它字符），试编写算法将该线性链表分割为三个循环
链表，其中每个循环链表表示的线性表中均只含一类
字符。

实现下列函数：
void Split(LinkList &lc, LinkList &ld, LinkList &lo, LinkList ll);

单链表类型定义如下：
typedef struct LNode{
    ElemType      data;
    struct LNode *next;
} LNode, *LinkList;

2.37④  设以带头结点的双向循环链表表示的线性
表L=(a1,a2,...,an)。试写一时间复杂度为O(n)的
算法，将L改造为L=(a1,a3,...,an,...,a4,a2)。

实现下列函数：
void ReverseEven(BiLinkList &L);

双向循环链表类型定义如下：
typedef struct BiNode {
    ElemType       data;
    int            freq; // 2.38题用
    struct BiNode *prev,
                  *next;
} BiNode, *BiLinkList;

◆2.38④  设有一个双向循环链表，每个结点中除有
prev、data和next三个域外，还增设了一个访问频度
域freq。在链表被起用之前，频度域freq的值均初始
化为零， 而每当对链表进行一次LOCATE(L,x)的操作
后， 被访问的结点（即元素值等于x的结点）中的频
度域freq的值便增1， 同时调整链表中结点之间的次
序，使其按访问频度递减的次序顺序排列，以便始终
保持被频繁访问的结点总是靠近表头结点。试编写符
合上述要求的LOCATE操作的算法。

实现下列函数：
BiLinkList Locate(BiLinkList dh, ElemType x); 

双向循环链表类型定义如下：
typedef struct BiNode {
    ElemType       data;
    int            freq; 
    struct BiNode *prev,
                  *next;
} BiNode, *BiLinkList;

◆2.39③  试对稀疏多项式Pn(x)采用存储量同多项式项
数m成正比的顺序存储结构，编写求Pn(x0)的算法（x0为
给定值），并分析你的算法的时间复杂度。

实现下列函数：
float Evaluate(SqPoly pn, float x);
/* pn.data[i].coef 存放ai，                      */
/* pn.data[i].exp存放ei (i=1,2,...,m)            */
/* 本算法计算并返回多项式的值。不判别溢出。      */
/* 入口时要求0≤e1<e2<...<em，算法内不对此再作验证*/

多项式的顺序存储结构:
typedef struct {
   int  coef;
   int  exp;
} PolyTerm;

typedef struct {
   PolyTerm *data;
   int       length;
} SqPoly;

◆2.41②  试以循环链表作稀疏多项式的存储结构，
编写求其导函数的算法，要求利用原多项式中的结
点空间存放其导函数（多项式），同时释放所有无
用（被删）结点。

实现下列函数：
void Difference(LinkedPoly &pa);
/* 稀疏多项式 pa 以循环链表作存储结构，     */
/* 将此链表修改成它的导函数，并释放无用结点 */

链式多项式的类型定义：
typedef struct PolyNode {
    int  coef;
    int  exp;
    struct PolyNode *next;
} PolyNode, *PolyLink;  // 多项式元素（项）结点类型

typedef PolyLink LinkedPoly; // 链式多项式