线性链表 — 单链表

墨蓝 2022-04-16 03:40 289阅读 0赞

线性链表存储结构的特点：用一组**任意**的存储单元存储线性表的数据元素（存储单元可以是连续的，也可以是不连续的）

数据元素a与其直接后继a+1之间的逻辑关系，对数据元素a来说，除了存储其本身信息外，还需要存储一个指示其直接后继的信息（即直接后继的存储位置）。这两部分信息组成数据元素a的存储映像，称为**结点（ node）**

它包括两个域：存储数据元素信息的域称为**数据域**；存储直接后继存储位置的域称为**指针域**。指针域中存储的信息称为**指针**或**链**。

n个结点(ai(1i≤n)的存储映像)链结成一个**链表**，即为线性表的**链**式存储结构。又因为此链表的每一个结点中只包含一个指针域，故又称**线性链表**或**单链表**。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FuZ2VsaWE2MjA_size_16_color_FFFFFF_t_70][]

链表是从头指针开始，**头指针**的信息就是第一个结点（即第一个数据元素的存储映像）存储地址。最后一个数据元素没有直接后继，故线性链表的最后一个结点的指针为“**空**”**（NULL）**

指针是数据元素之间的逻辑关系的映像。

逻辑上相邻的两个数据元素其存储的物理位置不要求相邻，这种存储结构为**非顺序映像**或**链式映像**。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FuZ2VsaWE2MjA_size_16_color_FFFFFF_t_70 1][]

头结点：在单链表的第一个结点之前设一个结点。头结点的数据域可以不存储任何信息，也可以存储如线性表的长度等类的附加信息，头结点的指针域存储指向第一个结点的指针（即第一个元素结点的存储位置）

Status GetElem_L(LinkList L,int i,ElemType &e){
    	//L为带头结点的单链表的头指针
    	//当第i个元素存在时，其赋值给e并返回OK值，否则返回ERROR
    	p = L -> next;j=1;//初始化L，p指向第一个结点，j为计数器
    	while(P && j < i){//顺指针向后查找，知道p指向第i个元素或p为空
    		p = p -> next;
    		++j;
    	}
    	if(!p || j>i) return ERROR;//第i个元素不存在
    	e = p -> data;//取第i个元素
    	return OK;
    }GetElem_L

时间复杂度：O(n)

单链表的插入与删除：

插入算法：

![2018111618041960.png][]

Status ListInsert_L(LinkList &L, int i,ElemType e){
    //在带头结点的单链线性表L中第i个位置插入元素e
    	p = L; j = 0;
    	while(p && j<i-1){//寻找第i-1个结点
    		p=p->next;
    		++j;
    	}
    	if(!p || j>i-1) return ERROR;
    
    	s=(LinkList)malloc(sizeof(LNode));//生成新的结点
    
    	s->data=e;s->next=p->next;//插入到L中
    	p->next=s;
    	return OK;
    }//ListInsert_L

s=(LinkList)malloc(sizeof(LNode));作用是游戏厅生成一个LNode型的结点，同时将该结点的起始位置赋值给指针变量s

时间复杂度：O(n)

删除算法：

![20181116180436356.png][]

Status ListDelete_L(LinkList &L, int i,ElemType e){
    //在带头结点的单链线性表L中删除第i个位置的元素，并由e返回其值
    	p = L; j = 0;
    	while(p && j<i){//寻找第i个结点，并令p指向其前驱
    		p=p->next;
    		++j;
    	}
    	if(!p || j>i-1) return ERROR;
    
    	q=p->next; p->next=q->next;//删除并释放结点
    	e=q->data;
    	free(q);//粒子还给系统
    	return OK;
    }//ListDelete_L

free(q);作用是由系统回收一个LNode型的结点，回收后的空间可以备做再次生成结点时用

时间复杂度：O(n)

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FuZ2VsaWE2MjA_size_16_color_FFFFFF_t_70]: /images/20220416/da7e7dd34c204c1db198f7f1a78f6e58.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FuZ2VsaWE2MjA_size_16_color_FFFFFF_t_70 1]: /images/20220416/48ba24c560bc499a9d69979f49f1ca54.png
[2018111618041960.png]: /images/20220416/e87dc33c9881413c86123929c2083cd0.png
[20181116180436356.png]: /images/20220416/334d91830f2944068e78965874a5e073.png