[线性表](8)题集_2

21.试写一算法,实现顺序表的就地逆置,即利用原表的存储空间将线性表(a1,....,an)逆序到(an,....,a1)

思路就是创建一个临时变量交换头尾的值,时间复杂度为O(2/n),完整算法如下所示:

void OrderList(SqList *S)
{

    int Max = S->length - 1;
    int Min = 0;
    int temp;
    while (Min < Max)
    {
        temp = S->elem[Min];
        S->elem[Min] = S->elem[Max];
        S->elem[Max] = temp;
        Min++;
        Max--;
    }
}

22.试写一算法,对单链表实现就地逆置

这个....讲真我思考了有一会儿,刚做完顺序表,还想着用同样的方式逆序,但是才发现,单链表无法从尾向前驱,后边想着想着就翻到答案去找思路了,其实蛮简单的,用栈就能实现,先进后出,使用头插

思路:先用一个指针保存首元结点的地址,然后断开头结点的链接,不断将首元结点使用头插插进头结点

其实就是头插跟尾插换了下而已,具体代码实现如下:

void OrderList(LinkList L)
{

    LinkList p,s,node;
    s = L;
    p = L->next;
    L->next = NULL;
    while (p != NULL)
    {
        node = p;
        p = p->next;

        node->next = s->next;
        s->next = node;
    }
}

23.设线性表A=(a1,a2,...,am),B=(b1,b2,....,bn),试写一个按下列规则合并为线性表C的算法,即使的:

C=(a1,b1,...,am,bm,b(m+1),....,bn) 当m<=n时

C=(a1,b1,...,an,bn,b(n+1),....,bm) 当m>n时

线性表A,B和C均以单链表作存储结构,且C表利用A表和B表中的结点空间构成,注意:单链表的长度值m和n均未显示存储。

这题敲黑板,讲过,之前做过,而且之前那个算法是排序算法, 这个更加容易了

直接利用A表的存储,从首元开始,不断隔一个元素插入一个b结点的值。

就是合并两个链表啦。

void MergeList(LinkList A,LinkList B)
{
    LinkList ha, hb, pa, pb;
    ha = A;
    hb = B;
    pa = ha->next;
    pb = hb->next;
    while (pa && pb)
    {
        ha->next = pa;
        ha = ha->next;
        pa = pa->next;

        ha->next = pb;
        ha = ha->next;
        pb = pb->next;

    }
    if (!pa)
    {
        ha->next = pb;
    }
    if (!pb)
    {
        ha->next = pa;
    }
}

这题需要注意的是:

img

在这儿,ha的指针域指向pa后,ha换到了pa的位置,保存了pa的地址后,pa必须立马后移,如果说把这句话放到pb=pb->next后面,那么ha进行两次后移后,pa也指向了pb,需要主要指向问题!!!

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

这道题可以结合第22题思路,头插,然后依次比较A,B两表中的数据,插入其一头结点后。

void MergeList(LinkList A,LinkList B)
{
    LinkList ha, hb, pa, pb, node;
    ha = A;
    hb = B;
    pa = A->next;
    pb = B->next;
    ha->next = NULL;

    while (pa && pb)
    {
        if (pa->data <= pb->data)
        {
            node = pa;
            pa = pa->next;

            node->next = ha->next;
            ha->next = node;
        }
        else
        {
            node = pb;
            pb = pb->next;

            node->next = ha->next;
            ha->next = node;
        }
    }

    if (!pa)
    {
        while (pb)
        {
            node = pb;
            pb = pb->next;
            
            node->next = ha->next;
            ha->next = node;
        }
    }
    if (!pb)
    {
        while (pa)
        {
            node = pa;
            pa = pa->next;

            node->next = ha->next;
            ha->next = node;

        }
    }

}

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

交集就是将两表中相同的元素以递增有序的方式形成一个新表,顺序表很简单....我发现这书指定有点毛病,这是难度4的题.....比难度3的还简单...

直接拿其一表遍历其二表,相同的数值链接到C表中,要注意的是,需要在B表中删除已取出的元素

首先看看无序算法的排列:时间复杂度为O(N*M)

void MagerSqList(SqList A, SqList B,SqList* C)
{

    int cura = 0, curb = 0, curc = 0;
    while (cura < A.length)
    {
        curb = 0;
        while (curb < B.length)
        {
            if (A.elem[cura] == B.elem[curb])
            {
                printf("%d %d ", cura, curb);
                system("pause");
                C->length++;
                C->listsize++;
                C->elem[curc] = A.elem[cura];
                curc++;
                break;
            }
            curb++;
        }
        cura++;
    }
}

上述算法的思路就是拿出一个A表中的一个数去对B表遍历,相同的数就保存到C表中

26.同25题要求,试着对单链表编写C的算法

思路和上述无差别,算法如下

void MergeList(LinkList A,LinkList B,LinkList *C)
{
    LinkList pa, pb, pc, node,pb1;

    pa = A->next;
    pc = *C;
    while (pa)
    {
        pb1 = B;
        pb = B->next;
        while (pb)
        {
            if (pa->data == pb->data)
            {
                node = (LinkList)malloc(sizeof(LNode));
                node->next = NULL;
                node->data = pa->data;
                pc->next = node;
                pc = pc->next;
                pb1->next = pb->next;
                free(pb);
                break;
            }
            pb1 = pb;
            pb = pb->next;
        }
        pa = pa->next;
    }
}

27.对25题的条件作一下两点修改,对顺序表重新编写求的表C的算法

  1. 假设在同一表(A或B)中可能存在值相同的元素,但要求新生成的表C中的元素值各不相同
  2. 利用表A的空间存放表C

这题思路就是求交后将A的头结点链接C表,然后进行去重操作

void MagerSqList(SqList* A, SqList B)
{
    int cura, curb, a,cura1;
    cura = 0; curb = 0;
    while (cura < A->length)
    {
        curb = 0;
        while(curb < B.length)
        {
            a = 1;
            if (A->elem[cura] == B.elem[curb])
            {
                a = 0;
                break;
            }
            curb++;
        }
        if (a == 1)
        {
            int temp = cura;
            while (temp < A->length)
            {
                A->elem[temp] = A->elem[temp + 1];
                temp++;
            }
            A->length--;
        }
        else
        {
            cura++;
        }
    }
    if (A->length == 0)
    {
        printf("没有交集");
    }
    cura = 0;
    cura1 = 1;
    while (cura1 < A->length)
    {
        if (A->elem[cura1] == A->elem[cura])
        {
            int temp = cura1;
            while (temp < A->length)
            {
                A->elem[temp] = A->elem[temp + 1];
                temp++;
            }
            A->length--;
            continue;
        }
        cura++;
        cura1 = cura + 1;
    }
}

上述算法只适用于有序排列的顺序表,如果是无序的顺序表,去重操作那儿需要进行双重循环,依次取出表中元素向后遍历。

28.对25题的条件作一下两点修改,对单链表重新编写求的表C的算法

  1. 假设在同一表(A或B)中可能存在值相同的元素,但要求新生成的表C中的元素值各不相同
  2. 利用原表空间中的结点构造表C,并释放A表中无用的结点空间
void MergeList(LinkList A,LinkList B,LinkList *C)
{
    LinkList pa, pb, pc,node;
    int a;

    pa = A->next;
    pc = *C;
    while (pa)
    {
        pb = B->next;
        while (pb)
        {
            a = 1;
            if (pa->data == pb->data)
            {
                a = 0;
                break;
            }
            pb = pb->next;
        }
        if (a == 0)
        {
            node = pa;
            pa = pa->next;
            node->next = NULL;
            pc->next = node;
            pc = pc->next;
        }
        else
        {
            node = pa;
            pa = pa->next;
            free(node);
        }
    }

    pc = (*C)->next;
    pa = pc->next;
    while (pa != NULL)
    {
        if (pc->data == pa->data)
        {
            pc->next = pa->next;
            free(pa);
            pa = pc->next;
            continue;
        }
        pc = pa;
        pa = pa->next;
    }

}

上述算法和27题的思路大劲相同,求交部分可用于无序,但是去重部分只可用于有序,如果是无序表,则需要先排序或者双重遍历去重。

29.已知A,B和C为三个递增有序的线性表,现要求对A表作如下操作:

  • 删去那些既在B表中出现又在C表中出现的元素。

并分析该算法的时间复杂度

这题思路依旧简单,是难度5的题,实现容易优化难,初步思路是拿A表中的元素逐次遍历B、C两表,通过计数来控制,如果两表中都有,则计数值为2,当计数值为2的时候,实行删除操作,否则下一个元素。

void MagerSqList(SqList* A, SqList B, SqList C)
{
    int cura, curb, curc;
    int a;
    cura = 0;
    while (cura < A->length)
    {
        a = 0;
        curb = 0;
        curc = 0;
        while (curb < B.length)
        {
            if (A->elem[cura] == B.elem[curb])
            {
                a++;
                int temp = curb;
                while (temp < B.length)
                {
                    B.elem[temp] = B.elem[temp + 1];
                    temp++;
                }
                B.length--;
                break;
            }
            curb++;
        }
        while (curc < C.length)
        {
            if (A->elem[cura] == C.elem[curc])
            {
                a++;
                int temp = curc;
                while (temp < C.length)
                {
                    C.elem[temp] = C.elem[temp + 1];
                    temp++;
                }
                C.length--;
                break;
            }
            curc++;
        }
        if (a == 2)
        {
            int temp = cura;
            while (temp < A->length)
            {
                A->elem[temp] = A->elem[temp + 1];
                temp++;
            }
            A->length--;
        }
        else
        {
            cura++;
        }
    }
}

30.要求同29题,在单链表中循环,并且释放A无用的空间

void MergeList(LinkList A, LinkList B, LinkList C)
{ 
    LinkList pa, pb, pc, pa1, pb1, pc1;
    pa = A->next;
    int a=0;
    pa1 = A;
    while (pa)
    {
        a = 0;
        pb1 = B;
        pc1 = C;
        pb = B->next;
        pc = C->next;
        while (pb)
        {
            if (pa->data == pb->data)
            {
                a++;
                pb1->next = pb->next;
                free(pb);
                pb = pb1->next;
                break;
            }
            pb1 = pb;
            pb = pb->next;
        }
        while (pc)
        {
            if (pa->data== pc->data)
            {
                a++;
                pc1->next = pc->next;
                free(pc);
                pc = pc->next;
                break;
            }
            pc1 = pc;
            pc = pc->next;
        }
        if (a == 2)
        {
            pa1->next = pa->next;
            free(pa);
            pa = pa1->next;
        }
        else
        {
            pa1 = pa;
            pa = pa->next;
        }
    }
}

思路如上题所示

在顺序表中利用如上方法,需要不断取出A的数去跟B和C做循环,同时需要删除B和C中已出现的元素,再要删除A中已出现的元素,时间复杂度为O(AC²)

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

划重点,循环单链,无头结点,从尾结点可找到头结点,思路先利用一个指针指向s,不断后移,当这个指针的指针域的指针域指向s的时候停下来,删除这个结点的后继结点,就完成了。

时间复杂度取决于s的位置 ,平均为O(2/N)

完整代码如下:

void LinkListR(LinkList L,LinkList s)
{
    LinkList p1,p = s;
    while (p->next->next != s)
    {
        p = p->next;
    }
    p1 = p->next;
    p->next = s;
    free(p1);
}

32.已知有一个单向循环链表,其每个结点中含三个域:prior,data和next,其中data为数据域,next为指向后继结点的指针域,prior也为指针域,但它的值为NULL,试编写算法将此单向循环链表改为双向循环链表,即使prior成为指向前驱结点的指针域。

这题依旧简单,构造三个指针,一个指向头,一个为前驱,一个为当前,当当前节点的后继指针域指向了头停止,否则不断后移,在后移前让当前的前驱指针指向前驱。当循环结束后,当前已经走到的尾端,头指针的前驱指向尾端即可

代码如下:

void DBLinkListR(LinkList L)
{
    LinkList p, p2, s;
    p = L;
    p2 = L->next;
    s = L;
    while (p2->next != s)
    {
        p2->prior = p;
        p = p2;
        p2 = p2->next;
    }
    s->prior = p2;
}

33.已知一个线性链表表示的线性表中含有三类字符的数据元素(如:字母字符,数字字符和其他字符),试着将该线性链表分割为三个循环链表,其中每个循环链表表示的线性表中均只含一类字符

刚开始的思路是在一个表中去分割,但是后边想了想,题目并无特殊要求,则可利用一个循环遍历整个数组,然后利用ASCII码去判断属于那一类,利用if else语句即可,完整代码如下所示:

void CutLinkList(LinkList L)
{
    LinkList p, s1, s2, s3, node;
    p = L->next;

    s1 = (LinkList)malloc(sizeof(LNode));
    s1->next = s1;
    s2 = (LinkList)malloc(sizeof(LNode));
    s2->next = s2;
    s3 = (LinkList)malloc(sizeof(LNode));
    s3->next = s3;
    while (p)
    {
        if ((p->data >= 'A' && p->data <= 'Z') || (p->data >= 'a' && p->data <= 'z'))
        {
            node = p;
            p = p->next;
            node->next = s1->next;
            s1->next = node;
            continue;
        }
        else if (p->data >= '0' && p->data <= '9')
        {
            node = p;
            p = p->next;
            node->next = s2->next;
            s2->next = node;
            continue;
        }
        else
        {
            node = p;
            p = p->next;
            node->next = s3->next;
            s3->next = node;
            continue;
        }
    }

    p = s1->next;
    while (p != s1)
    {
        printf("%c ", p->data);
        p = p->next;
    }
    printf("\n");
    p = s2->next;
    while (p  != s2)
    {
        printf("%c ", p->data);
        p = p->next;
    }
    printf("\n");
    p = s3->next;
    while (p != s3)
    {
        printf("%c ", p->data);
        p = p->next;
    }

}

需要注意的是字符输入时,scanf的特性。

在34题和36题中,“异或指针双向链表”类型XorLinkedList和指针异或函数XorP定义为:

typedef struct XorNode
{
    char data;
    struct XorNode LRPtr;
}XorNode,*XorPointer;

typedef struct
{//无头结点的异或指针双向链表
    XorPointer Left,Right;//分别指向链表的左端和右端
}XorLinkedList;

XorPointer XorP(XorPointer p, XorPointer q);
                          //指针异或函数XorP返回指针p和q的异或(XOR)值 

34.假设在算法描述语言中引入指针的二元运算“异或”(用⊕表示),若a和b为指针,则a⊕b的运算结果仍为原指针类型:

a⊕(a⊕b)=(a⊕a)⊕b=b

(a⊕b)⊕b=a⊕(b⊕b)=a

则可利用一个指针域来实现双向链表L,链表L中的每个结点只含两个域:data域和LRPtr域,其中LRPtr域存放该结点的左邻与右邻结点指针(不存在时为NULL)的异或,若设指针L.Left指向链表中的最左结点,L.Right指向链表中的最右节点,则可实现从左向右或从右向左遍历此双向链表的操作,试写一算法按任一方向依次输出链表中各元素的值。

这题我一直搞不懂题意,哪怕是睡了一觉后依旧搞不懂。答案如下:

设指针p指向当前节点,left指向它的左邻结点,right指向它的右邻结点,则有:

right==left⊕p->LRPtr和left==p->LRPtr⊕right

35.

36.

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

按照题意,这题思路可将链表从中间断开,然后分为两个链表进行插入,第一个链表是首元节点往后插入,然后用a2作为尾节点,结点向前驱插入,等待结点全部插入完成后,将再将两条链表链接起来即可,图如下所示

img

代码如下:

void CmpCentreLinkList(LinkList L)
{
    LinkList p, s, node, s1, s2;
    p = L->next;
    s = p->next;
    node = s->next;
    s->next = L;
    p->prior->prior = s;

    p->next = NULL;
    s->prior = NULL;

    while (node != L)
    {
        s1 = node;
        node = node->next;
        s1->prior = p;
        s1->next = p->next;
        p->next = s1;
        p = p->next;

        if (node == L)
        {
            break;
        }
        
        s2 = node;
        node = node->next;
        s2->next = s;
        s2->prior = s->prior;
        s->prior = s2;
        s = s->prior;
    }

    p->next = s;
    s->prior = p;
}

这样node只需要跑一次即可完成

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

void CompareFreqLinkList(LinkList L, int x)
{
    LinkList p, p1;
    p = L->next;
    while (p->data != x && p != L)
    {
        p = p->next;
    }
    if (p == L)
    {
        printf("未找到该元素\n");
    }
    else
    {
        p->freq++;
        printf("元素值为:%d,当前频度为:%d\n", p->data, p->freq);
        p1 = p->prior;
        while (p1 != L)
        {
            if (p1->freq < p->freq)
            {
                p1->prior->next = p;
                p->prior = p1->prior;

                p1->next = p->next;
                p->next->prior = p1;

                p->next = p1;
                p1->prior = p;
            }
            p = p1;
            p1 = p1->prior;
        }
    }
}

这题重点考察的就是指针域的修改,大家可以在纸上去画一画,就能很清楚的明白。

在39到40题中,稀疏多项式采用的顺序存储结构SqPoly定义为:

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

39.用上述结构构造一个多项式,并且输出结构——40:有序多项式相减,多项式条件:指数递增排列

第40题掌握多项式相减法则即可,可按归并排序进行,根据三种情况对相减后的多项式进行添加结点。

完整测试代码如下:

#define  _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
typedef struct//多项式结构
{
    int cofe;
    int exp;
}PolyTerm;
typedef struct//多项式顺序存储结构
{
    PolyTerm* data;
    int length;
}SqPoly;
typedef struct Res//结果
{
    int *result;
    int length;
}Res;

SqPoly S, S2,S3;

Res R;

void ResPoly(SqPoly, Res*, int x);/*给定一个x,输出它相减后的结果,对应39题*/
void InitPoly(SqPoly*);/*构造多项式顺序存储结构,使用动态数组存储*/
void SubPoly(SqPoly,SqPoly,SqPoly*);/*对应40题,两多项式相减*/
int main()
{
    int c;
    printf("请输入多项式的项数:");
    scanf("%d", &c);
    S.data = (PolyTerm*)malloc(sizeof(PolyTerm) * c);
    S.length = 0;
    while (c)
    {
        InitPoly(&S);
        c--;
    }
    printf("请输入多项式2的项数:");
    scanf("%d", &c);
    S2.data = (PolyTerm*)malloc(sizeof(PolyTerm) * c);
    S2.length = 0;
    while (c)
    {
        InitPoly(&S2);
        c--;
    }

    S3.data = (PolyTerm*)malloc(sizeof(PolyTerm) * 100);
    S3.length = 0;

    /*
    int x;
    printf("请输入X的值:");
    scanf("%d", &x);
    ResPoly(S, &R, x);
    */

    SubPoly(S, S2, &S3);
    /*
    int a = 0;
    while (a < S3.length)
    {
        printf("%d ", R.result[a]);
        a++;
    }
    */

    printf("相减后多项式为:");
    int a = 0;
    while (a < S3.length)
    {
        printf("%dX^%d", S3.data[a].cofe, S3.data[a].exp);
        a++;
    }


    system("pause");
    return 0;
}

void InitPoly(SqPoly *S)
{
    
    printf("请输入第%d项系数:", S->length);
    scanf("%d", &S->data[S->length].cofe);
    printf("请输入第%d项指数:", S->length);
    scanf("%d", &S->data[S->length].exp);
    S->length++;
}
void ResPoly(SqPoly S, Res *R, int x)
{
    R->result = (int*)malloc(sizeof(int) * S.length);
    R->length = 0;
    while (R->length < S.length)
    {
        R->result[R->length] = (int)pow(x, S.data[R->length].exp) * S.data[R->length].cofe;
        R->length++;
    }
}
void SubPoly(SqPoly S, SqPoly S2,SqPoly* S3)
{
    int a = 0, b = 0, c = 0;
    while (a<S.length&&b<S2.length)
    {
        if (S.data[a].exp < S2.data[b].exp)
        {
            S3->data[c].cofe = S.data[a].cofe;
            S3->data[c].exp = S.data[a].exp;
            a++;
            c++;
            continue;
        }
        else if (S.data[a].exp > S2.data[b].exp)
        {
            
            S3->data[c].cofe = S2.data[b].cofe;
            S3->data[c].exp = S2.data[b].exp;
            b++;
            c++;
            continue;
        }
        else
        {
            int sub = S.data[a].cofe - S2.data[b].cofe;
            if (sub == 0)
            {
                a++;
                b++;
                continue;
            }
            else
            {
                S3->data[c].cofe = sub;
                S3->data[c].exp = S.data[a].exp;
                a++;
                b++;
                c++;

            }
        }
    }

    while (a < S.length)
    {
        S3->data[c].cofe = S.data[a].cofe;
        S3->data[c].exp = S.data[a].exp;
        a++;
        c++;
    }
    while (b < S2.length)
    {
        S3->data[c].cofe = S2.data[b].cofe;
        S3->data[c].exp = S2.data[b].exp;
        b++;
        c++;
    }
    S3->length = c;
}

上述案例中,第39题的给定X计算结果,时间复杂度为O(n),n为多项式的项数

而40题的相减,由于是有序的,只需要O(n+m)即可,如果是无序的,则需要先进行排序,按指数递增,再使用归并排序进行处理

在41到42题中,稀疏多项式采用循环链表存储结构LinkedPoly定义为:

typedef struct
{
    int coef;
    int exp;
}PolyTerm;
typedef struct PolyNode
{
    PolyTerm* data;
    struct PolyNode* next;
}PolyNode, * PolyLink;

第41题求导,我还得补补求导公式

第42题的按条件分割倒是和之前的33题大劲相同,创建两个循环链表,然后按值判断指数为奇数还是偶数,插入即可

完整代码如下:

void OeCutLinkList(PolyLink A)
{
    PolyLink p, s1, s2, ss1, ss2;//由于不能创建节点,我必须用两个指针作为两循环链表的头指针
    p = A->next;
    while (p != A)
    {
        if (p->data->exp % 2 == 0)
        {
            ss1 = p;
            p = p->next;
            if (s1 == NULL)
            {
                s1 = p;
                s1->next = s1;
            }
            else
            {
                ss1->next = s1->next;
                s1->next = ss1;

            }
        }
        else
        {
            ss2 = p;
            p = p->next;
            if (s2 == NULL)
            {
                s2 = p;
                s2->next = s2;
            }
            else
            {
                ss2->next = s2->next;
                s2->next = ss2;
            }

        }
    }
}

本文链接:

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