当前位置：首页 > article >正文

数据结构：线性表的链式表示

article 2024/11/17 20:33:51

基本组成

链表的类型

主要操作

初始化：

带头结点

不带头结点

插入操作

删除操作：

查找操作：

求表长：

建立单链表：

头插法：

尾插法：

双链表：

查找操作

插入操作：

删除操作：

详细解释(插入和删除)：

插入操作的时间复杂度为O(1):

删除操作的时间复杂度为O(1):

注意事项:

优缺点

线性表的链式表示，又称为链式存储结构或链式映像，是一种常见且灵活的数据结构表示方式。它使用指针（或链）将一组数据元素按照其逻辑顺序连接起来，而不需要这些元素在物理位置上连续存储。这种表示方式特别适用于需要频繁进行插入和删除操作的场景。

基本组成

线性表的链式表示的基本单位是节点（Node），每个节点通常包含两部分信息：

数据域：用于存放数据元素本身的信息。
指针域：用于存放指向下一个节点的指针（或链），以表示数据元素之间的逻辑关系。

链表的起始节点称为头节点，尾节点的指针域为空（或指向一个特殊的结束标记，这取决于链表的具体实现方式）。

链表的类型

根据节点指针的指向和链表的结构，链表可以分为多种类型，其中最常见的是单链表和循环链表：

单链表：每个节点只有一个指针域，指向下一个节点。单链表的最后一个节点的指针域为空。
循环链表：在单链表的基础上，将最后一个节点的指针域指向头节点，形成一个闭环。循环链表可以是单向的，也可以是双向的（即每个节点有两个指针域，分别指向前一个和后一个节点）。

循环单链表：若设的是头指针，对在表尾插入元素需要O(n),若设的是尾指针r，r->next就是头指针，对在表头插入和表尾插入元素都只要O(1)。
循环双链表

主要操作

线性表的链式表示提供了多种操作，包括但不限于：

初始化：

带头结点

先创建一个头结点，让头指针指向头结点，头结点的next域初始化为null

//initialize
bool initList(LinkList &L){
    L=(LNode*)malloc(sizeof(LNode));//创建头结点,由系统生成一个LNode型的结点，并将该结点的起始位置赋给L（L就是头指针）
    L->next=NULL;//此时表为空 头结点的指针域为空
    return true;

}

不带头结点

只需将头指针初始化为null

bool initList(LinkList &L){
    L=NULL;
    return true;
}

插入操作

在链表的任意位置插入一个新节点，而不需要移动其他节点，时间复杂度通常为O(1)（如果已知插入位置的前驱节点）。

//insert
bool insertList(LinkList &L,int i,ElemType e){
    LNode *p=L;
    int j=0;
    while(p->next!=NULL&&j<i-1){
        p=p->next;
        j++;
    }
    LNode *s=(LNode*)malloc(sizeof(LNode))
    s->data=e;
    s->next=p->next;
    p->next=s;
    return true;
}

删除操作：

从链表中删除一个节点，同样不需要移动其他节点，时间复杂度也为O(1)（如果已知要删除节点的位置或其前驱节点的位置）。

//delete
bool deleteList(LinkList &L,int i,ElemType &e){
    LNode *p=L;
    int j=0;
    while(p->next!=NULL&&j<i-1){
        p=p->next;
        j++;
    }
    if(p==NULL||p->next==NULL)
    return false;
    LNode *q=p->next;
    e=q->data;
    p->next=q->next;
    free(q);
    return true;

}

时间复杂度：O(n)

查找操作：

通过遍历链表来查找指定元素

按序号：

//get
LNode *getelem(LinkList L,int i){
LNode *p=L;
int j=0;
while(p->next&&j<i){
    p=p->next;
    j++
}
return p;
}

按值：

//getbyvalue
LNode *getelem(LinkList L,Elemtype e){
    LNode *p=L;
    while(p->next){
        if(p->data==e)
        return p;
        else
        p=p->next;
    }
    return p;
}

时间复杂度：都为O(n)，其中n是链表中节点的数量。

求表长：

从头节点开始，沿着指针逐个节点遍历，直到遍历完整个链表。

//length
int Length(LinkList L){
    int len=0;
    LNode *p=L;
    while(p->next!=NULL){
        p=p->next;
        len++;
    }
    return len;
}

时间复杂度：O(n)

建立单链表：

头插法：

//create
LinkList List_headInsert(LinkList &L){
    LNode *s;int x;
    L=(LNode*)malloc(sizeof(LNode));
    L->next=NULL;
    scanf("%d",&x);
    while(x!=9999){
        s=(LNode*)malloc(sizeof(LNode));
        s->data=x;
        s->next=L->next;
        L->next=s;
        scanf("%d",&x);
    }
    return L;
}

尾插法：

//create
LinkList List_tailInsert(LinkList &L){
    int x;
    l=(LNode*)malloc(sizeof(LNode));
    LNode *s,*r=L;
    scanf("%d",&x)
    while(x!=9999){
        s=(LNode*)malloc(sizeof(LNode));
        s->data=x;
        r->next=s;
        r=s;
        scanf("%d",&x);
    }
    r->next=NULL;
    return L;

}

时间复杂度：O(n)

双链表：

查找操作

和单链表一样

插入操作：

//doubleline insert
s->next=p->next;
p->next->prior=s;
s->prior=p;
p->next=s;

删除操作：

//doubleline delete
p->next=q->next;
q->next->prior=p;
free(q);

时间复杂度：O(1) 因为可以很方便的查找到节点的前驱

详细解释(插入和删除)：

插入操作的时间复杂度为O(1):

在双链表中插入一个节点，如果已知插入位置的前驱节点或后继节点，则插入操作可以在常数时间内完成。具体步骤如下：

调整指针：首先，将新节点的prev指针指向插入位置的前驱节点，将新节点的next指针指向插入位置的后继节点。
更新前驱和后继节点的指针：然后，如果前驱节点存在，则更新其next指针指向新节点；如果后继节点存在，则更新其prev指针指向新节点。

由于这些操作仅涉及指针的重新赋值，不依赖于链表中元素的数量，因此时间复杂度为O(1)。

删除操作的时间复杂度为O(1):

同样地，在双链表中删除一个节点，如果已知待删除节点的前驱节点或后继节点，则删除操作也可以在常数时间内完成。具体步骤如下：

保存待删除节点的后继节点（如果需要）：首先，如果需要访问被删除节点的数据，可以将其后继节点的数据（如果存在）保存在临时变量中。
调整指针：然后，将待删除节点的前驱节点的next指针指向待删除节点的后继节点，将待删除节点的后继节点的prev指针指向待删除节点的前驱节点（如果前驱和后继节点都存在的话）。
释放内存（在动态分配内存的情况下）：最后，释放待删除节点所占用的内存空间。

这些操作同样只涉及指针的重新赋值和可能的内存释放，不依赖于链表中元素的数量，因此时间复杂度也为O(1)。