[广义表](6.1)头尾链广义表基本操作

广义表的递归算法

在栈那一章我们曾提及,递归函数结构清晰,程序易读,且容易证明正确性,因此时程序设计的有利工具,但有时递归函数的执行效率很低,因此,使用递归应扬长避短

在程序设计的过程中,我们并不一味的追求递归,如果一个问题的求解过程有明显的递推规律,我们也很容易写出它的递推过程(如求阶乘函数f(n)=!n的值),则不必要使用递归

反之,在对问题进行分解、求解的过程中得到的是和原问题性质相同的子问题(如Hanoi塔问题),由此自然得到一个递归算法,且它比利用栈实现的非递归算法更符合人们的思维逻辑,因而更易于理解

但要熟练掌握递归算法也不是一件容易的事,这里我不们介绍如何设计递归,只义广义表为例,讨论如何利用“分治法”(Divide and Conquer)进行递归算法设计的方法

对这类问题设计递归算法时,通常可以先写出问题求解的递归定义,和第二数学归纳法类似,递归定义由 基本项归纳项 两部分组成。

递归定义的基本项描述了一个或几个递归过程的终结状态,虽然是一个有限的递归(且无明显的迭代)可描述一个无限的计算过程,但任何实际应用的递归过程,除错误情况外,必定能经过有限层次的递归而终止

所谓的终结状态值得是不需要继续递归而可直接求解的状态,例如之前提及到的Hanoi塔问题,在n=1时可直接求得解。

即将圆盘从X塔座移动到Z塔座上,一帮情况下,若递归参数为n,则递归的终结状态为n=0,或n=1等。

递归定义的归纳项描述了如何实现从当前状态到终结状态的转化。

递归设计的实质是:

当一个复杂的问题可以分解成若干个子问题来处理时,其中某些子问题与原问题有相同的特征属性,则可利用和原问题相同的分析处理方法。

反之,这些子问题解决了,原问题也就迎刃而解了。

递归定义的归纳项就是描述这种原问题和子问题之间的转化关系。

仍以Hanoi塔为例,原问题是将n个圆盘从X塔座移至Z塔座上,可以把它分解成三个子问题:

  1. 将编号为1至n-1的n-1个圆盘从X塔座移至Y塔座
  2. 将编号为n的圆盘从X塔座移至Z塔座
  3. 将编号为1至n-1的圆盘从Y塔座移至Z塔座

其中(1)和(3)的子问题和原问题特征属性相同,只是参数(n-1和n)不同,由此实现了递归

由于递归函数的设计用的是归纳思维的方法,则在设计递归函数时候,应注意:

  1. 首先应书写函数的首部和规格说明,严格定义函数的功能和接口(递归调用的界面),对求精函数中所得的和原问题性质相同的子问题,只要接口一致,并可进行递归调用
  2. 对函数中的每一个递归调用都看成只是一个简单的操作,只要接口一致,必能实现规格说明中定义的功能,切忌想的太深太远

正如用第二数学归纳法证明命题时,由归纳假设进行归纳证明时决不能怀疑归纳假设是否正确

下面讨论广义表的三种操作,首先约定所讨论的广义表都是非递归表且无共享子表。

以下操作基于头尾链存储结构,我个人喜欢扩展线性存储结构

扩展线性存储结构补充笔记

在补充笔记李,对于扩展线性存储结构的13种基本操作均有记录

求广义表的深度

广义表的深度定义为广义表中括弧的重数,是广义表的一种量度,例如,多元多项式广义表的深度为多项式中变元的个数

设非空广义表为:

LS=(a1,a2,...,an)

其中ai(i=1,2,...,n)或为原子或为LS的子表,则求LS的深度可分解为n个子问题,每个子问题为求ai的深度,若ai是原子,则由定义其深度为零,若ai为广义表,则和上述一元处理,而LS的深度为各ai(i=1,2,...,n)的深度中最大值加1

空表也是广义表,并由定义可知空表的深度为1

由此可见,求广义表的深度的递归算法有两个终结状态:空表和原子,且只要求得ai(i=1,2,..,n)的深度,广义表的深度就容易求得了。显然,他应比子表深度的最大值多1

广义表:

LS=(a1,a2,...,an)

的深度DEPTH(LS)的递归定义如下:

  • 基本项:DEPTH(LS)=1 当LS为空表时

    • DEPTH(LS)=0 当LS为原子时
  • 归纳项:DEPTH(LS)=1+MAX{DEPTH(ai)} n>=1(1<=i<=n)

由此定义容易写出求深度的递归函数,假设L是GList型的变量,则L=NULL(L->tag=1&&L->hp==NULL),表明广义表为空表,L->tag=0表明为原子。

反之,L指向表结点,该结点中的hp指针指向表头,即为L的第一个子表,而结点中的tp指针所指表位结点中的hp指针指向L的第二个子表

在第一层中有tp相连的所有尾结点中的hp指针均指向L的子表,由此,求广仪表深度的递归函数如下所示:

int GListDepth(GList L)
//采用头尾链表存储结构,求广义表L的深度
{
    if (!L)
    {
        return 1;//当L为空表时
    }
    if (L->sign == ATOM)
    {
        return 0;//当L为原子时
    }
    //相当于深度优先搜索
    for (max = 0, pp = L; pp = pp->ptr.tp)
    {
        dep = GListDepth(pp->ptr->hp);
        if (max < dep)
            max = dep;//更新最大值
    }
    return max + 1;
}

上述算法的执行过程实质上是遍历广义表的过程,在遍历中首先求得各子表的深度,然后综合得到广义表的深度,例如下图展示了求广义表D=(( ),(e),(a,(b,c,d)))

深度的过程,图中用虚线示意遍历过程中指针L的变化状况:

img

在指向结点的虚线旁标记的是将要遍历的子表,而在从结点射出的虚线旁标记的数字是刚求得的子表深度为3,若按递归定义分析广义表D的深度,则有:

DEPTH(D)=1+MAX{DEPTH(A),DEPTH(B),DEPTH(C)}
DEPTH(A)=1;
DEPTH(B)=1+MAX{DEPTH(e)}=1+0=1
DEPTH(C)=1+MAX{DEPTH(a),DEPTH((b,c,d))}=2
DEPTH(a)=0
DEPTH((b,c,d))=1+MAX{DEPTH(a),DEPTH(b),DEPTH(c)}
              =1+0=1
由此,DEPTH(D)=1+MAX{1,2,3}=3

复制广义表

在之前的介绍中所提及,任何一个非空广义表可分解成表头和表尾,反之,一对确定的表头和表位可唯一确定一个广义表,由此,复制一个广义表只要分别复制其表头和表尾,然后合成即可。

假设LS是元表,NEWLS是复制表,则复制操作的递归定义如下:

  • 基本项:InitGlist(NEWLS){置空表},当LS为空表时
  • 归纳项:

    • COPY(GetHead(LS)->GetHead(NEWLS)){复制表头}
    • COPY(GetTali(LS)->GetTail(NEWLS)){复制表尾}

只要建立和原表中结点一一对应的新结点,并可得到复制表的新链表,由此可写出广义表的递归算法如下所示:

void CopyGList(GList* T, GList L)
//由L复制表T
{
    if (L == NULL)
    {
        *T = NULL;
    }
    else
    {
        if (!(*T = (GList)malloc(sizeof(GLNode)))) exit(0);
        (*T)->sign = L->sign;
        if ((*T)->sign == ATOM)
        {
            (*T)->data = L->data;
        }
        else
        {
            CopyGList(&(*T)->hp, L->hp);
            CopyGList(&(*T)->tp, L->tp);
        }
    }
}

注意,这里使用了变参,使得这个递归函数简单明了,直接了当的反映出广义表的复制过程,过程如下:

  • 如果为空表,则直接赋为空
  • 如果为原子,则直接复制原子元素
  • 如果为子表,则先传入头表,再传入尾表

这其实和遍历过程大致相同,使用传入指针来节省了连接结点的操作!

下面来到最难的地方,我们如何通过上述笔记,将广义表的操作由代码完成,基本操作如下:

建立广义表的存储结构(头尾链)

从上述两种广义表的算法讨论中可以发现,在对广义表进行的操作递归定义时,可有两种分析方法:

  1. 一种是把广义表分解成表头和表尾两个部分
  2. 另一种是把广义表看成含有n个并列的子表(假设原子也视作子表)的表

在讨论建立广义表的存储结构时,这两种分析方法均可。

假设把广义表的书写形式看成是一个字符串S,则当S为非空白串时广义表非空。

  • 此时可以利用之前定义的取列表表头GetHead和取列表表尾GetTail两个函数建立广义表的链表存储结构,这个递归算法和复制的递归算法极为相似,在后续的补充中将会给出代码,这儿详细介绍第二种方法。

广义表字符串S可能有两种情况:

  1. S=()(带括弧的空白串)

    • 对应于第一种情况S的广义表为空串
  2. S=(a1,a2,...,an),其中ai(i=1,2,...,n)是S的子串

    • 对应于第二种情况S的广义表中含有n个子表

每个子表的书写形式即为子串ai(i=1,2,...,n),此时可类似于求广义表的深度,分析由S建立的广义表和由ai(i=1,2,...,n)建立子表关系。

假设按照第一种存储结构来建立广义表的存储结构,则含有n个子表的广义表中有n个表结点序列,第i(i=1,2,...,n-1)个表结点中的表尾指针指向第i+1个表结点,第n个表结点的表尾指针指向NULL。

并且,如果把原子也看成是子表的话,则第i个表结点的表头指针hp指向由ai建立的子表(i=1,2,...,n)

由此,由S建广义表的问题可转化为由ai(i=1,2,...,n)建子表问题,又ai可能有3种情况

  • 带括弧的空白串
  • 长度为1的单个字符串
  • 长度>1的字符串,显然,前两种情况为递归的终结状态,子表为空表或只含一个原子结点

    • 后一种情况为递归调用

由此在不考虑输入字符串可能出错的前提下,可得到下列建立广义表链表的存储结构的递归定义:

  • 基本项:

    • 置空广义表 当S为空表串时
    • 建原子结点的子表 当S为单字符串时
  • 归纳项:

    • 假设sub为脱去S中最外层括弧的子串,记为‘s1,s2,...,sn’,其中si为非空字符串
    • 对每一个si建立一个表结点,并令其hp域的指针为由s[i]建立的子表的头指针,除最后建立的表结点的尾指针为NULL外,其余表结点的尾指针均指向在它之后建立的表结点

假定函数sever(str,hstr)的功能为,从字符串str中取出第一个“,”之前的子串赋给hstr,并使str称为删去子串hstr和‘,’之后的剩余串,若串str中没有字符‘,’,则操作后的hstr即为操作前的str,而操作后的str为空串NULL,根据上述递归定义可以得到算法如下所示:

Status CreateGList(GList* L, String S)
//采用头尾链表存储结构,由广义表的书写形式串S创建广义表L,设emp="( )"
{
    String sub, hstr;
    GList p = (*L), q = NULL;
    if (StrCompare(S, emp))
    {
        (*L) = NULL;
    }
    else
    {
        if (!((*L) = (GList)malloc(sizeof(GLNode)))) exit(OVERFLOW);//建立表结点
        if (StrLength(S) == 1) {
            (*L)->sign = ATOM;
            (*L)->data = S;//创建单原子广义表
        }
        else
        {
            (*L)->sign = LIST;
            SubString(sub, S, 2, StrLength(S) - 2);//脱外层括号
            do {//重复建立n个子表
                sever(sub, hstr);//从sub中分离表头和表尾
                CreateGList(&p->hp, hstr);
                q = p;
                if (!StrEmpty(sub))
                {
                    if (!(p = (GList)malloc(sizeof(GLNode)))) exit(OVERFLOW);
                    p->sign = LIST;
                    q->tp = p;
                }
            } while (!StrEmpty(sub));
            q->tp = NULL;
        }
        return OK;
    }
}

同时sever函数的算法如下所示:

void sever(String str, String hstr)
//将非空串str分割成两部分:hsub为第一个','之前的子串,str为之后的子串
{
    int n = StrLength(str);
    int i = 0, k = 0;//k记尚未配对的左括号个数
    String ch;
    do {//搜索最外层的第一个逗号
        i++;
        SubString(&ch, str, i - 1, 2);
        if (ch[0] == '(')
            k++;
        else if (ch[0] == ')')
            k--;
    } while (i < n && (ch[0] != ',' || k != 0));
    if (i < n)
    {
        SubString(hstr, str, 1, i - 1);//截取,前面的子串存入hstr
        SubString(str, str, i + 1, n - i);//截取,后面的子串存入hstr
    }
    else
    {
        StrCopy(hstr, str);
        ClearString(str);
    }
}

以上操作对应的字符串可是定长顺序表,也可是动态顺序表,对应字符串下标起始位置从1开始

以上全部操作基于头尾链广义表存储结构。

本文链接:

https://nullcode.fun/38.html
1 + 7 =
快来做第一个评论的人吧~