数据结构之线性表（链式表示之单链表）

Bertha 。 2023-07-16 03:49 96阅读 0赞

**定义：** 线性表的链式存储又称单链表

typedef struct LNode{ 
    ElemType data;
    struct LNode *next;
    }LNode,*LinkList;

**基本操作：**  
头插法建立单链表：

LinkList List_HeadInsert(LinkList &L){ 
    LNode *s;int x;
    L=(LinkList)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;
    }

> 最坏时间复杂度：O(n)

尾插法建立单链表：

LinkList List_TailInsert(LinkList &L){ 
    int x;
    L=(LinkList)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)

按序号查找操作：

LNode *GetElem(LinkList L,int i){ 
    int j=1;
    LNode *p=L->next;
    if(i==0)
    return L;
    if(i<1)
    return NULL;
    while(p&&j<i){ 
    p=p->next;
    j++;
    }
    return p;
    }

> 最坏时间复杂度：O(n)

按值查找操作：

LNode *LocateElem(LinkList L,ElemType e){ 
    LNode *p=L->next;
    while(p!=NULL&&p->data!=e)
    p=p->next;
    return p;
    }

> 最坏时间复杂度：O(n)

插入节点操作：

p=GetElem(L,i-1);
    s->next=p->next;
    p->next=s;

删除节点操作：

p=GetElem(L,i-1);
    q=p->next;
    p->next=q->next;
    free(q);

(优化)删除给定节点 \*p：

q=p->next;
    p->data=p->next->data;
    p->next=q->next;
    free(q);

求表长：

int k=0;
    p=head;
    while(p->next!=NULL){ 
    k++;
    p=p->next;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，96人围观）

还没有评论，来说两句吧...

相关阅读

相关【数据结构】线性表之单链表

目录一、链表的概念 1、概念 2、分类 3、重点二、单链表模拟实现 1、准备 2、头插法 3、尾插法 4、指定下标插入 5、遍历 6、删除第一次出现

ゝ一纸荒年。/ 2023年09月27日 13:24/ 0 赞/ 58 阅读

相关数据结构之线性表（链式表示之循环链表和静态链表（数组表示））

循环链表的空表判断： > 循环单链表： L->next==L; > 循环双链表： L->next==L; L->prior==L; 静态链表：

以你之姓@/ 2023年07月16日 11:58/ 0 赞/ 33 阅读

相关数据结构之线性表（链式表示之双链表）

结构体定义： typedef struct DNode{ ElemType data; struct DNOde prior,next;

ゝ一纸荒年。/ 2023年07月16日 11:56/ 0 赞/ 107 阅读

相关数据结构之线性表（链式表示之单链表）

定义：线性表的链式存储又称单链表 typedef struct LNode{ ElemType data; struct LNode next;

Bertha 。/ 2023年07月16日 03:49/ 0 赞/ 97 阅读

相关线性表链式表示和实现

1、我们把存储数据元素信息的域称为数据域，把存储直接后继的域称为指针域。指针域中存储的信息称为指针或链。元素（数据元素映像）+指针（指示后继元素存储位置）=结点（表示数据元素）

男娘i/ 2022年06月17日 13:12/ 0 赞/ 284 阅读

相关数据结构——线性表之链式存储

数据结构——线性表之链式存储 1、单链表由于链式存储的物理存储单元不一定是连续的，所以除了需要存储元素本身的信息外，还需要存储其后继元素的地址信息，以此保证线

刺骨的言语ヽ痛彻心扉/ 2022年06月16日 22:19/ 0 赞/ 316 阅读

相关数据结构之线性表链表

\include <stdio.h> \include <stdlib.h> typedef int ElemType; typedef struc

水深无声/ 2022年05月10日 10:42/ 0 赞/ 328 阅读

相关数据结构---------------线性表（下篇）之单链表

![70][] 单链表特点：储存空间不连续结点（数据元素组成）：数据域（储存数据）和指针域（指针）A1 ![70 1][] 若用p来指向则数据域为p-

朴灿烈づ我的快乐病毒、/ 2022年05月10日 08:04/ 0 赞/ 449 阅读

相关数据结构之线性表（链式表示）

在上篇博文中，我们介绍了线性表的顺序存储，本文将介绍其链式表示方式。由于顺序表的插入、删除操作都需要移动大量的元素，这极大的影响了运行效率，所以引进了线性表的链式表示。链

￡神魔★判官ぃ/ 2022年04月23日 15:10/ 0 赞/ 472 阅读

相关线性表—链式存储之单链表

线性表—链式存储之单链表 1、定义 2、表示方式 3、时间效率 4、相关概念 5、头指针与头结点的异同 6、带头节点的单链表与不带头结

落日映苍穹つ/ 2021年11月15日 12:52/ 0 赞/ 558 阅读