[线性表](7)题集_1

基本内容:

  • 线性表的逻辑结构定义、抽象数据类型定义和各种存储结构的描述方法
  • 线性表的两类存储结构(顺序的和链式的)上基本操作的实现
  • 稀疏多项式的抽象数据类型定义、表示和加法的实现

线性表的逻辑结构特性是数据元素之间存在着线性关系。

在计算机中表示这种关系的两类不同的存储结构分为:顺序存储结构和链式存储结构

前者表示线性表简称为顺序表,后者表示线性表简称为链表

顺序表:

  • 静态顺序表:内存空间固定的,表的大小固定的,无法改变
  • 动态顺序表:内存空间由用户自定义,可随着数据增大而重新分配

链表:

  • 单向动态链表:只有一个指向后继结点的指针,结点空间由用户分配
  • 双向动态链表:有两个指针,一个指向前置结点,一个指向后继结点,结点空间由用户分配
  • 循环链表:尾结点的指针域指向头结点
  • 静态链表:结合了顺序表易访问和链式表易操作的优点,通过一个整型数据游标来进行结点相链,操作途中要明确“备用表”和“数据表”的关系。空间由用户指定(在C语音里面,利用结构数组来表示)

基础知识题:

1.描述以下三个概念的区别:

  • 头指针
  • 头结点
  • 首元节点

头指针:是指向表头数据的指针,它用于访问整个链表,存放整个链表的基址,在链表操作里边,头指针是不可或缺的角色

头结点:通常指的是头指针指向的结点,头结点可带数据可不带数据,在不带数据的情况下,头结点的指针域指向首元结点,头结点用于链接整个链表

首元结点:位于表头第一个带数据的结点,通常指头结点(不带数据)后的第一个结点,通过它对链表进行一系列操作。

2.填空题:

在顺序表中插入或删除一个元素,需要平均移动n/2个元素,具体移动的元素个数与需要删除或插入元素的位置有关

顺序表中逻辑相邻的元素的物理位置也紧邻,单链表中逻辑相邻的元素的物理位置不紧邻

在单链表中,除了首元结点外,任一节点的存储位置由它 前置结点的指针域指示

在单链表中设置头结点的作用是:用于链表结点的访问,易与控制整个链表,无需改变头指针的指向,链表逻辑清晰

3.在什么情况下用顺序表比链表好

在数据无需进行大规模的增删操作的时候,利用顺序表方便数据的引用以及修改,而在数据需要进行增删等操作的情况下,链表的存储方式比只需修改指针域的指向来修改结点之间的关系,而顺序表则需要大规模的移动数据

在已知数据的情况下利用顺序存储结构能更好的控制数据,而在未知的情况下利用链表能更好的控制数据

4.对以下单链表分别执行下列各程序段,并画出结果示意图

img

  • Q=P->next
  • L=P->next
  • R->data=P->data
  • R->data=P->next->data
  • P->next->next->next->data=P->data
  • T=P

    • while(T!=NULL){T->data=T->data*2; T=T->next}
  • T=P

    • while(T->next!=NULL){T->data=T->data*2; T=T->next}

第一句,将Q指针指向P的后继结点

img

第二句,将L指针指向P的后继结点

img

第三句,将P指针指向的结点的数据域赋值给R指针指向结点的数据域

img

第四句,将P指向结点的后继结点的数据域赋值给R指针指向结点的数据域

img

第五句,将P指针指向结点数据域赋值给P第三个后继结点的数据域

img

第六句,将T指向P当T指向的结点不为空的时候,将T指向结点的数据域*2,T指向下一个结点,继续循环

img

第七句,将T指向P,判断T的下一结点是否为空,将T指向结点的数据域*2,T指向下一个结点,继续循环

img

5.画出执行下列语句后各指针及链表的示意图

L = (LinkList)malloc(sizeof(LNode));
P = L;
for (i = 1; i <= 4; i++)
{
    P->next = (LinkList)malloc(sizeof(LNode));
    P = P->next;
    P->data = i * 2 - 1;
}
P->next = NULL;
for (i = 4; i >= 1; i--)
{
    Ins_LinkList(L, i + 1, i * 2);
}
for (i = 1; i <= 3; i++)
{
    Del_LinkList(L, i);
}

先分析下题目:L作为头结点同时也作为头指针,程序先定义一个操作指针P让他指向L

再不断分配空间,一共分配了四个结点,链接至P后,链接完毕后,P已指向表尾,让P的指针域为空,程序示意图如下:

img

然后进入第二个循环,调用4次Ins_LinkList函数,该操作算法如下:

void Ins_LinkList(LinkList L, int j, int e)
{
    LinkList P, node;
    P = L;
    for (int i = 1; i < j; i++)
    {
        P = P->next;
    }
    node = (LinkList)malloc(sizeof(LNode));
    node->next = P->next;
    P->next = node;
    node->data = e;
}

不断在i+1的位置插入值为i*2的结点

  • 第一次:插入位置为5,插入值为8
  • 第二次:插入位置为4,插入值为6
  • 第三次:插入位置为3,插入值为4
  • 第四次:插入位置为2,插入值为2

运算后示意图如下:

img

后进入第二个循环语块调用三次Del_LinkList函数

删除第i个结点

完成算法如下:

void Del_LinkList(LinkList L, int i)
{

    LinkList p, s;
    p = L;
    s = L->next;
    for (int j = 1; j <= i && s != NULL; j++)
    {
        p = s;
        s = s->next;
    }

    p->next = s->next;
    free(s);
}

操作完成后示意图如下:

img

6.已知L表示无表头结点的单链表,且P结点既不是首元结点,也不是尾元结点,试从下列提供的答案中选择合适的语句序列

  • 在P结点后插入S结点的语句序列是:

    • S->next=P->next;
    • P->next=S;
  • 在P结点前插入S结点的语句序列是:

    • Q=P;
    • P=L;
    • while(P->next!=Q)P=P->next;
    • S->next=P->next;
    • P->next=S;
  • 在表首插入S结点的语句序列是:

    • S->next=L;
    • L=S;
  • 在表尾插入S结点的语句序列是:

    • while(P->next!=NULL)P=P->next;
    • P->next=S;
    • S->next=NULL;
  • 从下列语句中选出

    1. P->next=S;
    2. P->next=P->next->next;
    3. P->next=S->next;
    4. S->next=P->next;
    5. S->next=L;
    6. S->next=NULL;
    7. Q=P;
    8. while(P->next!=Q)P=P->next;
    9. while(P->next!=NULL)P=P->next;
    10. P=Q;
    11. P=L;
    12. L=S;
    13. L=P;

7.已知L是带表头结点的非空单链表,且P结点既不是首元结点,也不是尾元结点,试从下列提供的答案中选择合适的语句序列

  • 删除P结点的直接后继结点的语句序列是

    • Q=P->next;
    • P->next=P->next->next;
    • free(Q);
  • 删除P结点的直接前驱结点的语句序列是

    • Q=P;
    • P=L
    • while(P->next!=Q)P=P->next;
    • Q=P;
    • P=L
    • while(P->next!=Q)P=P->next;
    • P->next=P->next->next;
    • free(Q);
  • 删除P结点的语句序列是

    • Q=P;
    • P=L
    • while(P->next!=Q)P=P->next;
    • P->next=P->next->next;
    • free(Q);
  • 删除首元结点的语句序列是

    • P=L
    • P=P->next;
    • Q=P;
    • P=L
    • P->next=P->next->next;
    • free(Q);
  • 删除尾元结点的语句序列是

    • while(P->next->next!=NULL)P=P->next;
    • P->next=P->next->next;
    • P=P->next;
    • Q=P;
    • free(Q);
  1. P=P->next;
  2. P->next=P;
  3. P->next=P->next->next;
  4. P=P->next->next;
  5. while(P!=NULL)P=P->next;
  6. while(Q->next!=NULL)P=P->next;
  7. while(P->next!=Q)P=P->next;
  8. while(P->next->next!=NULL)P=P->next;
  9. Q=P;
  10. Q=P->next;
  11. P=L
  12. L=L->next;
  13. free(Q);

8.已知P结点是某双向链表的中间结点,试从下列提供的答案中选择合适的语句序列

  • 在P结点后插入S结点的语句序列是

    • S->priou=p;
    • S->next=P->next;
    • P->next->priou=S;
    • p->next=S;
  • 在P结点前插入S结点的语句序列是

    • S->priou=P->priou;
    • P->priou->next=S;
    • S->next=P;
    • p->priou=S;
  • 删除P结点的直接后继结点的语句序列是

    • Q=P->next;
    • P->next=P->next->next;
    • P->next->priou=P;
    • free(Q);
  • 删除P结点的直接前驱结点的语句序列是

    • Q=P->priou;
    • P->priou=P->priou->priou;
    • P->priou->next=P;
    • free(Q);
  • 删除P结点的语句序列是

    • p->priou->next=p->next;
    • P->next->priou=P->priou;
    • free(p);
  1. P->next=P->next->next;
  2. P->priou=P->priou->priou;
  3. p->next=S;
  4. p->priou=S;
  5. S->next=P;
  6. S->priou=p;
  7. S->next=P->next;
  8. S->priou=P->priou;
  9. p->priou->next=p->next;
  10. P->priou->next=P;
  11. P->next->priou=P;
  12. P->next->priou=S;
  13. P->priou->next=S;
  14. P->next->priou=P->priou;
  15. Q=P->next;
  16. Q=P->priou;
  17. free(p);
  18. free(Q);

9.简述以下算法的功能:

Status A(LinkedList L)//L是无表头结点的单链表
{
    if (L && L->next)
    {
        Q = L;
        L = L->next;
        P = L;

        while (P->next)
        {
            P = P->next;
        }
        P->next = Q;
        Q->next = NULL;
    }
    return OK
}

这个算法一看就知道,将表头插到表尾,更新头指针指向。

void BB(LNode* s, LNode* q)
{
    p = s;
    while (p->next != q)
    {
        p = p -> next;
    }

    p->next = s;
}
void AA(LNode* pa, LNode* pb)
//pa和pb分别指向单循环链表中的两个结点
{
    BB(pa, pb);
    BB(pb, pa);
}

这个算法,就是将一个循环链表分割成两个循环链表

第一个函数的作用就将q之前的结点链接到头指针指向的节点,第二个函数的作用就是通过两个结点调用第一个函数,起到分割链表作用。

算法设计题:

按书本要求,以下算法涉及的顺序表和线性链表的类型定义如下:

#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef struct
{
    ElemType* elem;//存储空间的基址
    int length;//当前长度
    int listsize;//当前分配的空间长度
}SqList;

typedef struct LNode
{
    ElemType data;
    struct LNode* next
}LNode, * LinkList;//链表类型

10.指出下列算法中的错误和低效(费时)之处,并将它改写为一个既正确又高效的算法:

Status DeleteK(SqList& a, int i, int k)
//本过程从顺序表a中删除以第i个元素起的k个元素
{
    if (i < || k<0 || i + k>a.length)
    {
        return INFEASIBLE;//参数不合法
    }
    else
    {
        for (count = 1; count < k; count++)
        {
            for (j = a.length; j >= i + 1; j--)
            {
                a.elem[j - 1] = a.elem[j];
            }
            a.length--;
        }
    }
}

错误有两处:

  • 参数不合法的判别条件不完整,合法的入口参数条件为:

    • (0<i<a.length)||(0<=k<=a.length-i)
  • 第二个错误是第二个循环语块中元素前移的次序错误
  • 低效之处就是每次删除一个元素

时间复杂度取决于需要删除的次数和表的长度,正确的算法如下所示(完成测试代码)

#include<stdio.h>
#include<stdlib.h>
typedef struct
{
    int* elem;
    int length;
    int listsize;
}SqList;

SqList S;

void DeleteK(SqList *S, int i, int k);
void InfoSqList(SqList);
int main()
{

    S.elem = (int*)malloc(sizeof(int) * 100);
    S.length = 0;
    S.listsize = 100;
    while (S.length < 10)
    {
        InfoSqList(S);
        S.length++;
        S.listsize--;
    }
    
    for (int i = 0; i < S.length; i++)
    {
        printf("%d ", S.elem[i]);
    }

    int i, e;
    printf("\n请输入需要删除的起始位置:");
    scanf("%d", &i);
    printf("请输入需要删除的元素个数:");
    scanf("%d", &e);

    DeleteK(&S, i, e);


    for (int i = 0; i < S.length; i++)
    {
        printf("%d ", S.elem[i]);
    }

    system("pause");
    return 0;
}
void InfoSqList(SqList S)
{
    scanf("%d", &S.elem[S.length]);
}

void DeleteK(SqList *S, int i, int e)
{
    if (0 > i > S->length || 0 > e > S->length - i)
    {
        printf("删除位置或元素个数不合法");
        exit(0);
    }
    for (int k = i + e; k <= S->length; k++)
    {
        S->elem[k - e] = S->elem[k];
    }
    S->length = S->length - e;
    S->elem[S->length] = NULL;

}

11.设顺序表va中的数据元素递增有序,试写一算法,将x插入到顺序表的适当位置上,以保持该表的有序性

这题,有序,递增,那么一想到,二分查找,找到正确位置后插入:完整算法如下

int ListInsert(SqList *S, int e)
{
    int len = S->length / 2;
    int r = 0;
    int l = S->length;

    if (S->length<0)
    {
        printf("插入位置不合法\n");
        return -1;
    }
    
    if (S->length >= S->listsize)
    {
        S->elem = (int*)malloc(sizeof(int) * (100 + 10));
        S->listsize += 10;
    }

    if (e > S->elem[S->length-1])
    {
        S->elem[S->length] = e;
        S->length++;
        S->listsize--;
        return 0;
    }
    if (S->elem[0] > e)
    {
        for (int k = S->length; k >= 0; k--)
        {
            S->elem[k] = S->elem[k - 1];
        }
        S->elem[0] = e;
        S->length++;
        S->listsize--;
        return 0;
    }

    while (r <= len && len <= l)
    {
        if (S->elem[len - 1] <= e && e <= S->elem[len])
        {
            for (int k = S->length; k >= len; k--)
            {
                S->elem[k] = S->elem[k - 1];
            }
            S->elem[len] = e;
            S->length++;
            S->listsize--;
            break;
        }
        else if (S->elem[len] > e)
        {
            len = len / 2;
        }
        else
        {
            len = (len + l) / 2;
        }        
    }
}

12.设A=(a1,....am)和B=(b1,...,bn)均为顺序表,A’和B’分别为A和B中出去最大共同前缀后的子表,例如:

  • A=(x,y,y,z,x,z)
  • B=(x,y,y,z,y,x,x,z)

则两者中的最大的共同前缀为(x,y,y,z),在两表中除去最大共同前缀的子表分别为A’=(x,z)和B’=(y,x,x,z),出现一下几种结果:

  • 若A’=B’=空表,则A=B
  • 若A’=空表,而B!=空表,或者两则均不为空表,且A’的首元小于B’的首元,则A<B,否则A>B

试着写一个比较A,B大小的算法

这题大水题,用指针走到不相等的地方比较就好了,算法如下:

int CmpSqList(SqList A, SqList B)
{
    int a = 0, b = 0;
    while (A.elem[a] != NULL && B.elem[b] != NULL)
    {
        if (A.elem[a] < B.elem[b])
        {
            printf("\nA<B");
            return -1;
        }
        if (A.elem[a] > B.elem[b])
        {
            printf("\nA>B");
            return 1;
        }
        a++;
        b++;
    }

    if (A.elem[a] == NULL && B.elem[b] == NULL)
    {
        printf("\nA=B");
        return 0;
    }

    if (A.elem[a])
    {
        printf("\nA>B");
        return 1;
    }

    if (B.elem[b])
    {
        printf("\nA<B");
        return -1;
    }
}

13.试写一算法在带表头结点的单链表结构上实现线性表操作LOCATE(L,X)

这题我的理解是在L表中找出X

LinkList LocateList(LinkList L, int x)
{
    LinkList P;
    P = L->next;
    while (P != NULL && P->data != x)
    {
        P = P->next;
    }
    if (P == NULL)
    {
        printf("未找到该元素");
        exit(0);
    }
    else
    {
        return P;
    }
}

14.试写一算法在带表头结点的单链表结构上实现线性表操作LENGTH(L)

int LengthList(LinkList L)
{
    LinkList P;
    int count = 0;
    P = L->next;
    while (P != NULL && P->data != x)
    {
        P = P->next;
        count++; 
    }
    return count;
}

15.已知指针ha和hb分别指向两个单链表的头结点,并且已知两个链表的长度分别为m和n,试写一算法将这两个链表链接到一起(其一链表的首元节点连接到另一链表的尾结点后),假设指针hc指向链接后的链表的头结点,并要求算法以尽可能短的时间完成连接运算,请分析你的算法的时间复杂度

int ConnectList(LinkList A, LinkList B)
{
    LinkList ha, hb, hc;
    ha = A;
    hb = B;
    if (ha->next == NULL && hb->next == NULL)
    {
        return 0;
    }
    while (ha->next != NULL)
    {
        ha = ha->next;
    }
    ha->next = hb->next;
    free(hb);
    hc = ha;
}

时间复杂度与其一链表的长度有关,需要找到链表的表尾才能进行链表,在上述算法中,时间复杂度为O(m)

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

Status DeleteAndInsertSub(LinkList la, LinkList lb, int i, int j, int len)
{
    if (i < 0 || j < 0 || len < 0)
    {
        return INFEASIBLE;
    }
    p = la; k = 1;
    while (k < i)
    {
        p = p->next;
        k++;
    }
    q = p;
    while (k <= len)
    {
        q = q->next;
        k++;
    }
    s = lb;
    k = 1;
    while (k < j)
    {
        s = s->next;
        k++;
    }
    s->next = p;
    q->next = s->next;
    return OK;
}

讲真,看到这算法后,我脑海里边出现的就全是错误

入口条件,首先要规划边界,删除的总数必须小于链表的长度,而因为是不带头节点的,所有首元结点我喜欢称为第一结点,游标都从1,开始,则i,j,len,都不能小于1,主要思路是分割其一结点后,将分割出来的链表链接到另一链表的指定位置,需要保存:

  • 分割链表的头,尾
  • 待分割的前驱,后置
  • 待插入的前驱,后置

还需要注意特殊值:插入到表头和表尾

完整算法如下:

int DeleteAAndInsertSub(LinkList *la, LinkList *lb, int i, int j, int len)
{
    int k;
    LinkList p, s, p1, s1, a, b;
    if (i <= 0 || j <= 0 || len <= 0 || la[i + len] == NULL)
    {
        exit(0);
    }
    k = 1;
    p = *la;
    while (k < i)
    {
        p = p->next;
        k++;
    }
    p1 = p;
    a = p->next;//保存删除的头
    k = 1;
    while (k <= len)
    {
        p = p->next;
        k++;
    }
    s = p;//保存删除的尾
    p1->next = p->next;

    b = *lb;
    if (j == 1)
    {
        s->next = b;
        *lb = a;
    }
    else
    {
        k = 1;
        while (k < j - 1)//从1开始,j-1是找到它的前驱
        {
            b = b->next;
            k++;
        }
        s1 = b->next;
        b->next = a;
        s->next = s1;
    }
}

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

不带头结点:

需要考虑的是,插入的位置是头还是尾,不带头结点我喜欢从1开始,那么需要找到它的前驱和后置,然后前驱链接插入结点,插入结点链接后置,判决条件是不能小于一,也不能大于表长+1

完整代码:

int InsertList(LinkList *L, int i, int b)
{
    int count = 1;
    LinkList s = *L, p = s->next, node;
    if (i <= 0)
    {
        printf("插入位置不合法");
        exit(0);
    }
    if (i == 1)
    {
        node = (LinkList)malloc(sizeof(LNode));
        node->data = b;
        node->next = s;
        *L = node;
        return 0;
    }

    while (s != NULL && count < i - 1)
    {
        s = p;
        p = p->next;
        count++;
    }
    if (s == NULL)
    {
        printf("插入位置不合法");
    }
    else
    {
        node = (LinkList)malloc(sizeof(LNode));
        node->data = b;
        node->next = p;
        s->next = node;
    }

}

带头结点:

从0开始计数,不需要改变头指针位置,头指针后链接首元结点。

判决条件,不能小于1,也不能大于表长+1。完整代码:

int InsertList(LinkList *L, int i, int b)
{
    int count = 0;
    LinkList s = *L, p = s->next, node;
    if (i <= 0)
    {
        printf("插入位置不合法");
        exit(0);
    }
    if (i == 1)
    {
        node = (LinkList)malloc(sizeof(LNode));
        node->data = b;
        s->next = node;
        node->next = p;
        return 0;
    }

    while (s != NULL && count < i - 1)
    {
        s = p;
        p = p->next;
        count++;
    }
    if (s == NULL)
    {
        printf("插入位置不合法");
        exit(0);
    }
    else
    {
        node = (LinkList)malloc(sizeof(LNode));
        node->data = b;
        node->next = p;
        s->next = node;
    }

}

18.同上要求,完成DELETE算法

int LenthList(LinkList L)
{
    int count = 1;
    LinkList p = L;
    if (L == NULL)
    {
        return 0;
    }
    while (p->next != NULL)
    {
        p = p->next;
        count++;
    }
    return count;
}

int DeleteList(LinkList* L, int i)
//删除L表中第i个位置
{
    if (0 >= i || i > LenthList(*L))
    {
        printf("删除位置不合法\n");
        return 0;
    }
    LinkList p,s;
    p = *L;
    s = (*L)->next;
    int count = 1;

    if (i == 1)
    {
        *L = s;
        free(p);
        return 0;
    }

    while (count < i - 1)
    {
        p = s;
        s = s->next;
        count++;
    }

    p->next = s->next;
    free(s);
}

同上所述,不带头结点的元素从1开始,当删除位置到表头的时候,需要改变头指针指向

带头结点:

int DeleteList(LinkList* L, int i)
//删除L表中第i个位置
{
    if (0 >= i || i > LenthList(*L))
    {
        printf("删除位置不合法\n");
        return 0;
    }
    LinkList p,s;
    p = *L;
    s = (*L)->next;
    int count = 0;

    if (i == 1)
    {
        p->next = s->next;
        free(s);
        return 0;
    }

    while (count < i - 1)
    {
        p = s;
        s = s->next;
        count++;
    }

    p->next = s->next;
    free(s);
}

相差不大,不需要改变头指针位置,单链表很好操作,都是基础题。我们看下一题:

总得来说:带头结点的首元结点位于头结点后,在指定位置插入和删除的时候位于第一位,而带头结点的首元节点就是头指针所指向的结点,位于第二位!

19.已知线性表中的元素以值递增有序排列,并以单链表做存储结构,试写一高效算法,删除表中所有值大于mink且小于maxk的元素(若表中存在满足条件的元素)同时释放被删除的结点空间,并分析你的算法的时间复杂度(注意:mink和maxk是给定的两个参变量,它们的值可以和表中的元素相同,也可以不同)

这道题需要注意两个点,一个是有序,一个是单链表,既然是链式存储,而且是动态带头结点的单链表,就不能二分查找,思路就是从首元节点开始,一个指针指向它的前驱,不断后移,知道满足mink的条件的数,利用一个指针指向这个数,继续后移,后移后释放刚刚满足条件的数,最后达到满足maxk元素的时候,将其链接起来,代码如下所示:

void MinkMaxkList(LinkList L, int i, int j)
{
    LinkList p, s, p1, P;
    s = L;
    p = L->next;
    while (p != NULL)
    {
        if (p->data > i && p->data < j)
        {
            p1 = p;
            p = p->next;
            free(p1);
            continue;
        }
        if (p->data >= j)
        {
            s->next = p;
            break;
        }
        s = p;
        p = p->next;
    }
    if (p == NULL)
    {
        s->next = NULL;
    }

}

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

这道题我首先想的是,拿链表中的每一个数去往后边遍历,但是突然想到,这是一个有序链表,在蓝哥的指导下,用双指针也可以实现。

通用链表算法:

void DeleteEqualList(LinkList L)
//利用三个指针,一个快指针s,一个跟着快指针指向前驱p1
//一个慢指针p,不断去遍历
//时间复杂度与链表的元素有关,平均复杂度是O((2/n)n)
{

    LinkList p, s, p1;
    p = L->next;
    while (p != NULL)
    {
        p1 = p;
        s = p->next;
        while (s != NULL)
        {
            if (p->data == s->data)
            {
                p1->next = s->next;
                free(s);
                s = p1->next;
                continue;
            }
            p1 = s;
            s = s->next;
        }
        p = p->next;
    }
}

img

有序链表借鉴大佬的思想,算法如下:

void DeleteEqualList(LinkList L)
{

    LinkList p, s, p1;
    p = L->next;
    s = p->next;
    while (s)
    {
        if (p->data == s->data)
        {
            p1 = s;
            s = s->next;
            free(p1);
            p->next = s;
            continue;
        }
        p = s;
        s = s->next;
    }
}

时间复杂度仅仅为O(n),因为只需要快指针s遍历一次链表

本文链接:

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