有人看免费的视频吗_市场监督管理局是干什么的_网站推广的方式_外链代发

目录

基本组成

链表的类型

主要操作

初始化：

带头结点

不带头结点

插入操作

删除操作：

查找操作：

求表长：

建立单链表：

头插法：

尾插法：

双链表：

查找操作

插入操作：

删除操作：

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

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

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

注意事项:

优缺点

---

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

基本组成

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

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

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

链表的类型

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

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

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

主要操作

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

初始化：

带头结点

先创建一个头结点，让头指针指向头结点，头结点的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;elsep=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):

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

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

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

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

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

1. 保存待删除节点的后继节点（如果需要）：首先，如果需要访问被删除节点的数据，可以将其后继节点的数据（如果存在）保存在临时变量中。

2. 调整指针：然后，将待删除节点的前驱节点的next指针指向待删除节点的后继节点，将待删除节点的后继节点的prev指针指向待删除节点的前驱节点（如果前驱和后继节点都存在的话）。

3. 释放内存（在动态分配内存的情况下）：最后，释放待删除节点所占用的内存空间。

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

注意事项:

需要注意的是，上述O(1)的时间复杂度是基于已知插入或删除位置的前驱节点或后继节点的前提下的。如果只知道待插入或删除节点的值或序号，则需要先遍历链表找到该节点及其前驱节点或后继节点，此时时间复杂度将变为O(n)，其中n是链表的长度。

综上所述，双链表插入和删除的时间复杂度为O(1)，这主要得益于其双向链接的结构特性和操作方式。

综上所述，线性表的链式表示是一种灵活且高效的数据结构表示方式，特别适用于需要频繁进行插入和删除操作的场景。然而，在选择使用链表时，也需要根据具体的应用场景和需求来权衡其优缺点。

优缺点

优点：

• 插入和删除操作效率高，因为只需要修改指针，而不需要移动数据元素。
• 不需要预先分配固定大小的存储空间，可以根据需要动态地申请和释放存储空间。

缺点：

• 访问链表中的元素需要从头节点开始遍历，因此随机访问的效率较低。
• 每个节点都需要额外的指针域来存储指针信息，这会增加一定的存储开销。