线性表

d1omg

逻辑结构

数据元素之间的逻辑关系(抽象)

集合结构

image-20240705171712254

线性结构

image-20240705171716609

一对一的关系

假如说,2的前面是1,那么就把1称为2的前驱

3在2的后面,那么把3称为后继

树型结构

image-20240705172035523

只能有一个父系

子系可以有多个

图形结构

image-20240705172042422

存储结构

数据结构在计算机中的表示(具体)

顺序、链式、索引、散列

索引、散列可以由顺序、链式实现。

顺序存储

随机访问的意思是:可以到任意某一个元素(计算的时间是一样的)

image-20240705172801888

链式存储

image-20240705222056082

如果C后面没有了就变成NULL

逻辑结构和存储结构

image-20240705222145566

顺序存储和链式存储优势劣势

顺序存储优势:

  1. 实现随机存取
  2. 每个元素占用最少的空间(假如你是int的数组,那么每个就占用4个字节)

顺序存储劣势:

只能使用整块的存储单元,会产出较多的碎片.

链式存储优势:

充分利用所有存储单元,不会出现碎片现象

链式存储劣势:

  1. 需要额外的

算法定义

1.有穷-执行一个算法能结束

2.确定-可以确定结果

3.可行-可以执行

4.输入-输入的内容

5.输出-加工输入的内容

时间复杂度

时间复杂度指的是算法中所有语句的频度(执行次数)之和

记为T(n)=O(f(n))

其中n是问题的规模;f(n)是问题规模n的某个函数

假如 输入n个数要排序. 排序算法就要执行n*n那么f(n)=n^2

O(n^2)

image-20240706131151089

数组O(1) 可以拿到任何一个位置的数

时间复杂度是怎么计算的?

eg.1

int sum=0;
sum=n*(n+1)/2;
printf("%d",sum);

因为这里没有for循环. 并且 程序执行了三次. 算法的执行次数等于3

时间复杂度为T(n)=O(1);

表示不会随着n的增长而增长

eg.2

int x=2;
while(x<n/2)
    x=2*x;

执行频率最高的就是x=2*x;

初始x=2,下一次4,8,16,32

2^t+1<n/2

那就同取log,根据时间复杂度计算忽略高阶项系数和低阶项.

时间复杂度T(n)=O(

image-20240706133110552
)

eg.3

image-20240706133228346

最终是n-1 根据时间复杂度计算忽略高阶项系数和低阶项.

T(n)=O(n);

eg.4

image-20240706133409130

首先外层循环,for(i=0;i<n;i++){}根据n是执行了n次

内层循环while(x<n/2) x=2*x;

1 2 4 8 16 32

2^n+1<n/2

取log 为

image-20240706133737631

再*外层的n就变为了

image-20240706133754010

eg.5

image-20240706133913715

外层循环是n，内层循环是m, n*m=>n^2,根据时间复杂度乘法规则

O(n^2)

eg.6

image-20240706134109260

这里是两个循环没有嵌套,那么就各自执行

T(n)=max(O(n),O(m));

取最大的

eg.7

image-20240706134221555

取最大的,可以忽略5n并且可以忽略3.从而拿到时间复杂度

T(n)=O(n^3);

空间复杂度

S(n)=O(f(n));

空间复杂度O(1)

n个元素数组排序,不开辟额外的空间(随着n的增长而增长的空间叫做额外空间).[有点抽象,没理解]

空间复杂度就是O(1);

线性表

顺序表

什么是线性表

由n个相同类型的元素组成的有序集合.

image-20240706140722646

线性表中元素个数n,称为线性表的长度. 当n=0时,为空表.

ai-1为ai的直接前驱

ai+1为ai的直接后继

特点

  1. 表中元素个数是有限的
  2. 表中元素的数据类型都相同,意味着每一个元素占用相同大小的空间
  3. 表中元素具有逻辑上的顺序性,在序列中各元素排序由其先后顺序

顺序表的代码定义

image-20240706141831375

优点和缺点

image-20240706142016698
image-20240706142210019

最好的插入情况:在表尾插入,时间复杂度为O(1);

最坏的插入情况:在表头插入,时间复杂度为O(n);

平均情况:在插入概率平均的情况下,平均移动元素的次数为n/2,时间复杂度就为O(n);( 根据省略高次项系数。)

insert code

首先在写代码之前要构建思想。

  1. 判断是否超出数组位置
  2. 寻找要插入的位置
  3. 找到以后,位移后面的元素.
  4. 插入
  5. 结束,长度+1
#include <stdio.h>
#include <string.h>

#define MaxSize 50
typedef struct
{
    int data[MaxSize];
    int len;
}sqllist;


bool insert(sqllist *A,int element,int index)
{

    if(index<1||index>A->len+1) return 0;//插入位置是否合法

    if(A->len>=MaxSize) return 0;//插入的空间是否足够

    for(int i=A->len;i>=index;i--)//index就是要插入的第几个位置
    {
        A->data[i]=A->data[i-1];//往后移动
        //假设i=5,进入这里之后就是A[5]=A[4],也就是A的第四个位置的元素，到第五个去了
    }
    A->data[index-1]=element;//全部移动完了之后,再插入对应元素的位置
    A->len++;//线性表长度加1
    return 1;
}

int main()
{

    sqllist B={{1,2,3,4,5},5};
    if(insert(&B,333,5))
    {
        printf("success\n");
    }else
    {
        printf("fail\n");
    }

    for (int i =0;i<B.len;i++)
    {
        printf("%d,",B.data[i]);
    }
    return 0;
}

delete code

  1. 判断是否超出、插入是否合法.
  2. 找到要删除的数
  3. 把后面的数字往前移
  4. 删除要删除的数
  5. 长度减对应数
  6. 结束
bool del(sqllist *A,int index){
    if(index<1||index>A->len+1) return 0;//插入位置是否合法
    if(A->len>=MaxSize) return 0;//插入的空间是否足够
    int temp=A->data[index-1];

    for(int i=index;i<A->len;i++)
    {
        A->data[i-1]=A->data[i];
    }

    A->len--;
    return 1;
}

#include <stdio.h>
#include <string.h>

#define MaxSize 50
typedef int ElemType;//昂顺序表存储其他类型元素时,可以快速修改
typedef struct
{
    ElemType data[MaxSize];
    int len;
}sqllist;


bool insert(sqllist *A,int element,int index)
{

    if(index<1||index>A->len+1) return 0;//插入位置是否合法

    for(int i=A->len;i>=index;i--)//index就是要插入的第几个位置
    {
        A->data[i]=A->data[i-1];//往后移动
        //假设i=5,进入这里之后就是A[5]=A[4],也就是A的第四个位置的元素，到第五个去了
    }
    A->data[index-1]=element;//全部移动完了之后,再插入对应元素的位置
    A->len++;//线性表长度加1
    return 1;
}

bool del(sqllist *A,int index){
    if(index<1||index>A->len+1) return 0;//插入位置是否合法
    if(A->len>=MaxSize) return 0;//插入的空间是否足够
    int temp=A->data[index-1];

    for(int i=index;i<A->len;i++)
    {
        A->data[i-1]=A->data[i];
    }

    A->len--;
    return 1;
}
int main()
{

    sqllist B={{1,2,3,4,5},5};
    if(insert(&B,333,5))
    {
        printf("success insert\n");
    }else
    {
        printf("fail insert\n");
    }

    if(del(&B,1))
    {
        printf("success del\n");
    }else
    {
        printf("fail del\n");
    }

    for (int i =0;i<B.len;i++)
    {
        printf("%d,",B.data[i]);
    }
    return 0;
}

#include <stdio.h>

#define MaxSize 50
typedef int ElemType;

typedef struct
{
    ElemType data[MaxSize];
    int len;
}SqList;

bool insert(SqList &A,int element,ElemType index)
{
    if(index<1||index>A.len) return 0;//插入是否合法
    if(A.len>=MaxSize) return 0;//满了，插入不了了

    for(int i=A.len;i>=index;i--)
    {
        A.data[i]=A.data[i-1];
    }
    A.data[index-1]=element;
    A.len++;

return 1;

}
bool del(SqList &A,ElemType index)
{
    if(index<1||index>A.len) return 0;//插入是否合法

    for(int i=index;i<=A.len;i++)
    {
        A.data[i-1]=A.data[i];
    }
    A.len--;
    return 1;
}
void print(SqList &A)
{
    for(int i=0;i<A.len;i++)
    {
        printf("%3d",A.data[i]);
    }
}
int main()
{
    SqList A={{1,2,3,4,5,6},6};


    if(insert(A,333,1))
    {
        printf("success insert\n");
    }else
    {
        printf("fail insert\n");
    };


    print(A);
    return 0;
}

思考

image-20240706152613093

属于

完整的一套操作-顺序表

#include <stdio.h>

#define MaxSize 50
typedef int ElemType;

typedef struct
{
    ElemType data[MaxSize];
    int len;
}SqList;

bool insert(SqList &A,int element,ElemType index)
{
    if(index<1||index>A.len) return 0;//插入是否合法
    if(A.len>=MaxSize) return 0;//满了，插入不了了

    for(int i=A.len;i>=index;i--)
    {
        A.data[i]=A.data[i-1];
    }
    A.data[index-1]=element;
    A.len++;

return 1;

}
bool del(SqList &A,ElemType index)
{
    if(index<1||index>A.len) return 0;//插入是否合法

    for(int i=index;i<=A.len;i++)
    {
        A.data[i-1]=A.data[i];
    }
    A.len--;
    return 1;
}
void print(SqList &A)
{
    for(int i=0;i<A.len;i++)
    {
        printf("%3d",A.data[i]);
    }
}
//查找某个元素的位置
int findelement(SqList &A,ElemType e)
{
    for(int i=0;i<=A.len;i++)
    {
        if(A.data[i]==e)
        {
            printf("you want find element in =%d\n",i+1);
        }
    }
    return 0;
}
//查找某个index中存在那个元素
int getelement(SqList &A,int index)
{
    printf("you want find index in elemtne%d",A.data[index-1]);
  return 0;
}
int main()
{
    SqList A={{1,2,3,4,5,6},6};


    if(insert(A,333,1))
    {
        printf("success insert\n");
    }else
    {
        printf("fail insert\n");
    };

    if(del(A,3))
    {
        printf("success del\n");
    }else
    {
        printf("fail del\n");

    }

    print(A);


findelement(A,4);
getelement(A,1);
    return 0;
}

OJ作业-课时10作业

AC代码:

#include <stdio.h>
#include <iostream>
#define Max 100
typedef  int E;

typedef struct
{
    E data[Max];
    int len;
}SqList;

bool insert(SqList &I,E element,int index)
{
    if(index<1||index>I.len+1) return false;
    if(I.len>=Max) return false;
    for(int i=I.len;index<=i;i--)
    {
        I.data[i]=I.data[i-1];
    }

    I.data[index-1]=element;
    I.len++;

    return true;
}

bool del(SqList &I,E index)
{
    if(index<1||index>I.len) return false;
for(int i=index;i<=I.len;i++)
{
    I.data[i-1]=I.data[i];
}
    I.len--;
    return true;

}


void printList(SqList &I)
{
    for(int i =0;i<I.len;i++)//这里不能是等于,等于的话就会存在数组越界
    {
        printf("%3d",I.data[i]);
    }
printf("\n");
}


int main()
{
    SqList A={{1,2,3},3};
    int element,pos;
    scanf("%d",&element);

    if(insert(A,element,2))
    {
        printList(A);
    }else
    {
        printf("false\n");
    };

    scanf("%d",&pos);
    if(del(A,pos))
    {
        printList(A);
    }else
    {
        printf("false\n");
    };
    return 0;
}

线性表的链式存储

因为顺序表在

  1. 插入和删除操作移动大量元素.
  2. 数组的大小不好确定
  3. 占用一大段连续的存储空间,造成很多碎片

我们用某种线性表需要再特定的场景下使用。

假如说你要读取很多数据的,就可以考虑使用顺序表。

单链表

​ [data]+[next]

image-20240706165419894

在定义的时候，和顺序表不大一样。

因为在定义结构体的时候,会用到结构体指针。

当我们存储数据的时候,就是需要用到,这么一个结构体来保存数据.

typedef int ElemType;
typedef struct Lnode
{
    ElemType data;//数据域
    struct Lnode *next;//指针域指向下一个数据
}Lnode,*LinkList;

每一个节点都有next指针. 当出现NULL的时候,就知道到结尾了.

image-20240706170411086

在a1之前还放了一个,叫做头节点(不放值).L叫做头指针

image-20240706170506079

为什么在a1前加一个头结点？因为带头结点的链表是操作简单的。

若链表有头节点,则头指针永远指向头节点,不论链表是否为空(a1/a2/a3都是没有数据的),头指针均不为空,头指针是链表的必须元素,他表示一个链表.

头节点是为了操作的方便而设立的,其数据域一般为空,或者存放链表的长度.有头结点后,对在第一节点前插入和删除第一节点的操作就统一了,不需要频繁重置头指针.但头节点不是必须的.

优点

image-20240706173759189

缺点

image-20240706173804223

指针域不是存数据的。是存指针的。

插入思路

在表头插入时:

image-20240707114132054

q->next=p->next;(指针域)

p->next=q(指针域指向q的数据域)

在表中插入时:

image-20240707114240909

q->next=p->next;

p->next=q;

表尾插入时

image-20240707114820609

p->next=q;(p的指针域指向q的数据域)

q->next=NULL;(q的指针域指向NULL)

删除

在表头/表中/表尾删除时:

image-20240707115331156

q=p->next;(拿到要删除的元素)

p->next=q->next;(p的指针域[表头L]指向q指向的指针域a2)

free(q);

查找

按index查找

image-20240707120742473

按元素查找

image-20240707120759933

代码实战

头插法+中间法

插入

开始->定义链表指针->申请空间->scanf读取第一个元素->while循环建立链表->print->结束

#include <iostream>
#include <stdio.h>
#include <stdlib.h>

typedef int E;

// 头插法+中间插
typedef struct Lnode {
    E data;
    struct Lnode *next; // 指向下一个节点
} Lnode, *posLnode;

bool insert(posLnode &A) {
    A = (posLnode)malloc(sizeof(Lnode)); // 申请头节点的空间
    A->next = NULL;
    E x; // 定义存放数据

    // 先读取一次数据，初始化 x
    scanf("%d", &x);

    while (x != 9999) {
        Lnode *s = (posLnode)malloc(sizeof(Lnode));
        s->data = x;
        s->next = A->next; // 让新节点 s，指向原来那个节点
        A->next = s;
        scanf("%d", &x); // 读取下一个数据
    }

    return true;
}

void print(posLnode A) {
    A = A->next; // 跳过头节点
    while (A != NULL) {
        printf("%3d", A->data);
        A = A->next;
    }
    printf("\n");
}

int main() {
    posLnode A; // 链表头指针
    insert(A);
    print(A);
    return 0;
}

尾插法

开始->定义链表头指针L->头节点申请空间,定义尾指针r,指向头结点L->scanf读取第一个元素->开启while循环建链表->结束

image-20240707152605292
#include <iostream>

typedef int E;
typedef struct Lnode
{
    E data;
    struct Lnode *next;
}Lnode,*p;

void insert_tail(Lnode *&L)
{
    //头指针
    L=(p)malloc(sizeof(Lnode));//申请节点空间
    L->next=NULL;
    //尾指针指向L(始终指向链表尾部),存储a(1-n)的s
    Lnode *r=L,*s;
    //输入
    E x;
    scanf("%d",&x);
    //定义
    while (x!=9999)
    {
        s=(p)malloc(sizeof(Lnode));//为新节点申请空间
        s->data=x;
        r->next=s;//新节点给尾节点的next指针
        r=s;
        scanf("%d",&x);

    }
    r->next=NULL;
}

void print(p A) {
    A = A->next; // 跳过头节点
    while (A != NULL) {
        printf("%3d", A->data);
        A = A->next;
    }
    printf("\n");
}
int main()
{
    p L;
    insert_tail(L);
    print(L);
    return 0;
}

按值查找与按位置查找

按值查找

开始->定义链表头指针->尾插法新建链表->查找某个位置的元素值,需要判断是否合法,L是从0开始的->遍历查找index对应的元素值->结束输出

p GetElem(p A,int index)
{
    //A起头是0开始的.
    int i = 0;
    if(index<1) return NULL;

    while (i<index)
    {
        A=A->next;//L指向第一个有数据的
        i++;
    }
    return A;

}

按位置查找

p LocateElem(p A,E element)
{
    while (A)
    {
        if(A->data==element)
        {
            return A;//如果找到对应的值就返回节点index
        }
        A=A->next;
    }
    return  NULL;
}

小完整-差删除

#include <iostream>

typedef int E;
typedef struct Lnode
{
    E data;
    struct Lnode *next;
}Lnode,*p;

void insert_tail(Lnode *&L)
{
    //头指针
    L=(p)malloc(sizeof(Lnode));//申请节点空间
    L->next=NULL;
    //尾指针指向L(始终指向链表尾部),存储a(1-n)的s
    Lnode *r=L,*s;
    //输入
    E x;
    scanf("%d",&x);
    //定义
    while (x!=9999)
    {
        s=(p)malloc(sizeof(Lnode));//为新节点申请空间
        s->data=x;
        r->next=s;//新节点给尾节点的next指针
        r=s;
        scanf("%d",&x);

    }
    r->next=NULL;
}
void insert_head(Lnode *&L)
{
    //首先给L开辟一个空间,用来存放头指针
    L=(p)malloc(sizeof(Lnode));//申请节点空间
    L->next=NULL;
    //输入数据
    Lnode *s;//定义存放数据的 数据指针/数据域
    E x;
    scanf("%d",&x);
    while (x!=9999)
    {
        //给s开辟一条存放数据的空间
        s=(p)malloc(sizeof(Lnode));
        s->data=x;
        s->next=L->next;
        L->next=s;
        scanf("%d",&x);
    }
}
void print(p A) {
    A = A->next; // 跳过头节点
    while (A != NULL) {
        printf("%3d", A->data);
        A = A->next;
    }
    printf("\n");
}

p GetElem(p A,int index)
{
    //A起头是0开始的.
    int i = 0;
    if(index<1) return NULL;

    while (i<index)
    {
        A=A->next;//L指向第一个有数据的
        i++;
    }
    return A;

}

p LocateElem(p A,E element)
{
    while (A)
    {
        if(A->data==element)
        {
            return A;//如果找到对应的值就返回节点index
        }
        A=A->next;
    }
    return  NULL;
}

int main()
{
    p L,GetE,LocE;
    // insert_tail(L);
    insert_head(L);
    print(L);
    GetE=GetElem(L,2);
    if(GetE)
    {
        printf("success getelem\n");
        printf("%d\n",GetE->data);
    }else
    {
        printf("faild getelem\n");
    };

    LocE=LocateElem(L,7);
    if(LocE)
    {
        printf("success LocE\n");
        printf("%d\n",LocE->data);
    }else
    {
        printf("faild LocE\n");
    };
    
    return 0;
}

往第i个位置插入元素

bool insert_i_pos(Lnode  *&A,int index,E element)
{
    p AAA = GetElem(A, index - 1);
    if (AAA == NULL) return false;
    p q = (p)malloc(sizeof(Lnode)); //给新节点申请空间
    q->data = element;
    q->next = AAA->next;
    AAA->next = q;
    return true;
}

单链表完整代码:

#include <iostream>

typedef int E;
typedef struct Lnode
{
    E data;
    struct Lnode *next;
}Lnode,*p;


void insert_tail(Lnode *&L)
{
    //头指针
    L=(p)malloc(sizeof(Lnode));//申请节点空间
    L->next=NULL;
    //尾指针指向L(始终指向链表尾部),存储a(1-n)的s
    Lnode *r=L,*s;
    //输入
    E x;
    scanf("%d",&x);
    //定义
    while (x!=9999)
    {
        s=(p)malloc(sizeof(Lnode));//为新节点申请空间
        s->data=x;
        r->next=s;//新节点给尾节点的next指针
        r=s;
        scanf("%d",&x);

    }
    r->next=NULL;
}
void insert_head(Lnode *&L)
{
    //首先给L开辟一个空间,用来存放头指针
    L=(p)malloc(sizeof(Lnode));//申请节点空间
    L->next=NULL;
    //输入数据
    Lnode *s;//定义存放数据的 数据指针/数据域
    E x;
    scanf("%d",&x);
    while (x!=9999)
    {
        //给s开辟一条存放数据的空间
        s=(p)malloc(sizeof(Lnode));
        s->data=x;
        s->next=L->next;
        L->next=s;
        scanf("%d",&x);
    }
}


void print(p A) {
    A = A->next; // 跳过头节点
    while (A != NULL) {
        printf("%3d", A->data);
        A = A->next;
    }
    printf("\n");
}

p GetElem(p A,int index)
{
    //A起头是0开始的.
    int i = 0;
    if(index<0) return NULL;
    while (i<index)
    {
        A=A->next;//L指向第一个有数据的
        i++;
    }
    return A;

}
p LocateElem(p A,E element)
{
    while (A)
    {
        if(A->data==element)
        {
            return A;//如果找到对应的值就返回节点index
        }
        A=A->next;
    }
    return  NULL;
}
//index代表插入索引
bool insert_i_pos(Lnode  *&A,int index,E element)
{
    p AAA = GetElem(A, index - 1);
    if (AAA == NULL) return false;
    p q = (p)malloc(sizeof(Lnode)); //给新节点申请空间
    q->data = element;
    q->next = AAA->next;
    AAA->next = q;
    return true;
}

//要删除第几个元素
bool del(Lnode *&A,int index)
{

    p q;
    p AAA=GetElem(A,index-1);//拿到要删除的元素前一个指针
    if(AAA==NULL) return  false;
    q=AAA->next;//拿到要删除的指针
    if(q==NULL) return  false;//当链表只有5个节点,删除第6个节点时返回false
    AAA->next=q->next;//断链
    free(q);
    return  true;
}
int main()
{
    p L,GetE,LocE;
    // insert_tail(L);
    insert_head(L);
    print(L);
    /*
    GetE=GetElem(L,2);
    if(GetE)
    {
        printf("success getelem\n");
        printf("%d\n",GetE->data);
    }else
    {
        printf("faild getelem\n");
    };

    LocE=LocateElem(L,7);
    if(LocE)
    {
        printf("success LocE\n");
        printf("%d\n",LocE->data);
    }else
    {
        printf("faild LocE\n");
    };
*/
    insert_i_pos(L,2,99);
    print(L);
    del(L,3);
    print(L);
    return 0;
}

OJ作业-课时11作业

image-20240708123527112
image-20240708123535934
#include <iostream>
typedef int E;
typedef struct Lnode
{
    E data;
    struct Lnode *next;

}Lnode,*p;// struct Lnode *p;


void insert_head(p &L)
{
    //定义头指针L
    L=(p)malloc(sizeof(Lnode));
    L->next=NULL;
    //定义存数据的节点
    Lnode *s;
    //定义输入数据的变量
    E x;
    scanf("%d",&x);
    while (x!=9999)
    {
        s=(p)malloc(sizeof(Lnode));
        s->data=x;
        s->next=L->next;
        L->next=s;
        scanf("%d",&x);
    }
}//insert head
void print_insert_head(p A)
{
    int i=0;
    A=A->next;
    while (A!=NULL)
    {
        printf("%3d",A->data);
        ++i;
        A=A->next;
    }
    printf("\n");
};//my print way
void insert_tail(p &L)
{
    //初始化头
    L=(p)malloc(sizeof(Lnode));
    L->next=NULL;
    //初始化数据域
    p s,r=L;
    E x;
    scanf("%d",&x);
    while (x!=9999)
    {
        s=(p)malloc(sizeof(Lnode));
        s->data=x;
        r->next=s;//r的下一个就是s的数据域
        r=s;//r直接变成了s,新的插入之后又是一个新的s
        scanf("%d",&x);
    }
    r->next=NULL;
    //在尾插法中，没有正确地设置最后一个节点的 next 指针为 NULL。导致在打印链表时，链表的最后一个节点的 next 指针不是 NULL，可能指向了一些未初始化的内存区域，从而导致无限循环。
}
void PrintList(p L)
{
    L = L->next;
    while (L != NULL)
    {
        printf("%d", L->data); //打印当前结点数据
        L = L->next; //指向下一个结点
        if (L != NULL)
        {
            printf(" ");
        }
    }
    printf("\n");
}//oj print way
//根据index找元素
p GetEle(p L,int index)
{
    int i=0;
    if(index<0) return NULL;
    while (i<index)
    {
        L=L->next;
        i++;
    }
    return L;
}
//根据元素找index
p FindEle(p L,E element)
{
    while (L)
    {
        if(L->data==element)
        {
            return L;
        }
        L=L->next;
    }
    return NULL;//如果没有找到就返回NULL;
}
bool del(p L,int index)
{
    p A;//定义找到删除前一个
    p d;//定义要删除的元素
    A=GetEle(L,index-1);//找到要删除的元素的前一个
    if (A==NULL) return false;
    d=A->next;
    if(d==NULL) return false;
    A->next=d->next;//断链
    free(d);
    return true;
}
int main()
{

     p A,GetE,FindE;
    // insert_head(A);
    // PrintList(A);
    insert_tail(A);
    PrintList(A);

    GetE=GetEle(A,2);
    if(GetE){printf("success find e:%d\n",GetE->data);}else{printf("fail find e");};
    FindE=FindEle(A,7);
    if(FindE){printf("success find i:%d\n",FindE->data);}else{printf("fail find i");};

    del(A,3);
    PrintList(A);
    return 0;
}

2019年考研真题分析41题-很懵

image-20240708123614467

问题:

空间复杂度在什么情况下不是O(1)?

比如你在原有基础[]n个元素中,又让其中某一个元素开辟了n个空间，就不是空间复杂度为O(1)的了。

设计思想:

空间复杂度为O(1),不能额外申请空间.

找到链表中间节点.

前一半节点为L,后半部分节点为L2.将链表后半部分的创立一个新节点给予L2,再进行原地逆置.

最后交叉合并.

image-20240708151645495

解题设计

  1. 找到中间节点,并赋予新节点为L2.
  2. 原地逆置L2
  3. 合并

代码

//找中间
void find_middle(p L,p &L2)
{
    //第二条链表的头节点
    L2=(p)malloc(sizeof(NODE));
    //构造两个指针,双指针法遍历
    p pcur,ppre;
    //开始遍历
    pcur=ppre=L->next;//首先指到a1
    while (pcur!=NULL)
    {
        pcur=pcur->next;//先走一步，判断后面是否为空
        if(pcur==NULL) break;//判断pcur后面是否为空了
        pcur=pcur->next;//在走一部
        if(pcur==NULL) break;//为了使得偶数个ppre依然指向中间两个节点的前一个
        ppre=ppre->next;
    }

    //这里没怎么理解,还得画个图
    L2->next=ppre->next;//由L2头节点指向后面一半链表
    ppre->next=NULL;//前一半链表的最后一个节点,next要为null
}
//逆置
//逆转不需要头指针变的
void reverse(p L2)
{
    p r,s,t;
    r=L2->next;
    if(r==NULL) return;//链表为空,第一个节点a1没数据
    s=r->next;
    if(s==NULL) return;
    t=s->next;
    while (t)
    {
        s->next=r;
        r=s;//以下三句是三个指针同时向后
        s=t;
        t=t->next;
    }

//这里也不大懂,可以画图
s->next=r;//最后一步了。
L2->next->next=NULL;//逆置后的链表尾部next要为空 L2原本第一个节点要为NULL
L2->next=s;

}
//合并L，L2
void merge(p L,p L2)
{
    p pcur,pp,qq;
    pcur=L->next;
    pp=pcur->next;
    qq=L2->next;
    while (qq!=NULL&&pp!=NULL)
    {
        pcur->next=qq;
        qq=qq->next;//指向下一个节点 用来遍历l2链表
        pcur=pcur->next;

        pcur->next=pp;
        pp=pp->next;
        pcur=pcur->next;
    }
    if(pp!=NULL){pcur->next=pp;}
    if(qq!=NULL){pcur->next=qq;}
}

分析时间复杂度

void find_middle

image-20240708172201809

因为pcur总共走两次,所以是O(n/2)=O(n)

void reverse

因为他遍历的就是L2的长度,所以时间复杂度就是O(n)

void merge

遍历次数O(n/2)=O(n)

三个函数 实际遍历之后就是1.5n -> O(n)

双链表

https://blog.csdn.net/weixin_44162361/article/details/115819742 参考博客

插入

image-20240709111313438

尾插

image-20240709130845988
bool insert_tail(k &p)
{
    init(p);
    //定义
    k s,tail=p;//尾插法.和单链表差不多
    E x;
    scanf("%d",&x);
    while (x!=9999)
    {
        s=(k)malloc(sizeof(Lnode));
        if(s==NULL) return false;
        s->data=x;//给予数据
        s->next=NULL;//
        s->prev=tail;
        tail->next=s;
        tail=s;
        scanf("%d",&x);
    };
    return  true;
}

头插

image-20240709135836015
bool insert_head(k &p)
{
    //初始化
    init(p);
    k s;
    E x;
    scanf("%d",&x);
    while (x!=9999)
    {
        s=(k)malloc(sizeof(Lnode));
        if(s==NULL) return false;
        s->data=x;
        if(p->next==NULL)
        {
            s->next=NULL;
            s->prev=p;
            p->next=s;
        }else
        {
           s->next=p->next;
           p->next->prev=s;
            s->prev=p;
            p->next=s;
        }
        scanf("%d",&x);
    };
    return  true;
}

删除

k GetEle(k p,int index)
{
    p=p->next;
    int i = 1;
    if(index<1) return NULL;
    while (p&&i<index)
    {
        p=p->next;
        i++;
    }
    return p;
}

bool delete_pos(k &p,int index)
{
    if(index<1||len(p)<index) return false;
    k q;//要删除的元素
    p=GetEle(p,index-1);//拿到前驱节点
    if(p==NULL) return false;
    q=p->next;//要删除的元素
    p->next=q->next;//q的下一个指向上一个元素
    q->next->prev=p;//要删除元素的下一个元素的前驱节点被p赋予
    free(q);
    return true;
}

求表的长度

int len(k p)
{
    p=p->next;
    int i = 0;
    while(p)
    {
        p=p->next;
        i++;
    }
    return i;
}

循环 单、双链表

//循环单-插入

//循环双-插入
bool insert_tail(k &p)
{
    init(p);
    //定义
    k s, tail = p; // 尾插法，和单链表差不多
    E x;
    scanf("%d", &x);
    while (x != 9999)
    {
        s = (k)malloc(sizeof(Lnode));
        if (s == NULL) return false;
        s->data = x; // 赋予数据

        if (tail == p) { // 如果链表为空（插入第一个节点）
            s->next = p;
            s->prev = p;
            p->next = s;
            p->prev = s;
        } else { // 插入后续节点
            s->next = p;
            s->prev = tail;
            tail->next = s;
            p->prev = s;
        }

        tail = s; // 更新尾节点
        scanf("%d", &x);
    }
    return true;
}

This article was updated on July 9, 2024

You should also read: