转载

线性表的链式存储结构

一、线性表的链式存储结构

特点:线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素,这组存储单元可以存在内存中未被占用的任意位置。

链式存储结构中,除了要存储数据元素信息外,还要存储它的后继元素的地址(指针)。也就是说除了==存储本身信息外==,还要存储==一个指示其直接后继的存储位置的信息==。

  • 数据域:把存储数据元素信息的域称为数据域
  • 指针域:把存储直接后继位置的域称为指针域(指针域中存储的信息称为指针或链)
  • 这两个部分加起来,也就是数据域以及指针域加起来称为存储映像,也叫结点(Node)
  • n个结点连接成一个链表,即为线性表(a1,a2,a3...,an)的链式存储结构
  • 其中一条链表当中,如果==每个结点只包含一个指针域==的链表叫做==单链表==。

二、单链表

  • 一条链表中每个结点只包含一个指针域的链表就叫做单链表
  • 我们把第一个结点的存储位置叫做头指针,最后一个结点指针为空(NULL或^)

如图:

在这里插入图片描述

三、头指针与头结点的异同

==头指针==

  • 指的是链表指向第一个结点的指针,若链表有头结点,头指针就是表示指向头结点的指针
  • 头指针具有标识作用。
  • 头指针是链表的必要元素。
  • 不论链表是否为空,头指针均不为空。

==头结点==

  • 头结点是为了操作的同一和方便而设立,放在第一个元素的结点之前,其数据域一般无意义。
  • 头结点对在第一元素结点前插入结点和删除第一结点起操作与其他系欸但的操作就统一了。
  • 头结点不一定是链表的必要元素。

==如图==:

单链表图: 在这里插入图片描述 ==空链表==: 在这里插入图片描述 ==用C语言中可以用结构指针来描述单链表==

typedef struct Node{
	ElemType data;			//数据域
	struct Node* Next;  	//指针域
}Node;
typedef struct Node* LinkList;//Node* = LinkList
  • 该结构表示结点是由存放数据元素的数据域和存放后继结点地址的指针域组成。

==例题:== 假设p是指向线性表第i个元素的指针,则该结点ai的数据域,我们可以用p->data的值是一个数据元素,结点ai的指针可以用p->next表示,p->next的值是一个指针。

==问:p->next指向谁? 答:指向第i+1一个元素。也就是指向ai+1的指针== ==问:如果p->data =ai,那么p->next->data是什么? 答:p->next->data =ai+1(表示数据域)==

四、单链表的读取

  • 单链表中,因为他是链状的。我们无法通过索引的形式。去寻找元素。我们只能从第一个元素顺着链子往下寻找。
  • ==算法思路==:
    • 声明一个结点p指向链表第一个结点,初始化j从1开始
    • 当j<i时,就遍历链表,让p的指针向后移动,不断指向下一个结点,j+1
    • 若链表末尾p为空,则说明第i个元素不存在
    • 否则查找成功,返回结点p的数据
  • ==用c语言代码实践==
Status GetElem(LinkList L,int i,ElemType *e){
		int j;
		LinkList p;
		p=L->next;
		j =1;
	while(p && j<i)
	{
		p=p->next;
		++j;
	}
	if(!p || j>i){
		return ERROR;
	}
	*e=p->data;
	return OK;
}
  • 该算法时间复杂度取决于i的位置,当i=1,则不需要遍历,而i=n时则遍历n-1此才可以。因为最坏情况的时间复杂度为O(n)
  • 由于单链表的结构中没有定义表长,所以不能实现知道要循环多少次,因为不方便使用for来控制循环。

五、单链表的插入

  • 假设存储元素e的结点为s,要实现结点p,p->next和s之间的逻辑关系的变化。

  • 示例图: 在这里插入图片描述

  • 算法思路

    • s->next =p->next;
    • p->next =s; 在这里插入图片描述
  • ==注意两句代码不能反过来==

    • p->next =s;
    • s->next = p->next;
    • 也就是p->next先被覆盖为s的地址,则s->next =p->next就等于s->next = s,陷入死循环
  • 首先声明一结点p指向链表头结点,初始化j从1开始;

  • 当j<1时,就遍历链表,让p的指针向后移动,不断指向下一个结点,j累加1。

  • 若到链表末尾p为空,则说明第i个元素不存在,否则查找成功,在系统中生成一空结点s;

  • 将数据元素e赋值给s->data;

  • 伪代码实现

Status ListInsert(LinkList *L,int i,ElemType e){
	int j;
	LinkList p,s;

	P = *L;
	j = 1;
	while( p && j < 1){  //用户寻找第i个结点
		p = p->next;
		j++;
	}
	if(!p || j > i){
		return ERROR;
	}
	s =(LinkList)malloc(sizeof(Node));//生成新结点
	s->data = e;
	
	s->next =p->next;
	p->next =s;
	
	return OK;
}

六、单链表的删除

  • 假设元素a2的结点为q,要实现结点q删除单链表的操作

  • 示例图 在这里插入图片描述

  • 算法思路

    • 其实就是将它的前继结点的指针绕过指向后继结点
    • 表示为:p->next = p->next->next
    • 也可以表示为:q=p->next;p->next =q->next;
  • 声明结点p指向链表第一个结点,初始化j=1

  • 当j<1时,就遍历链表,让P的指针向后移动,不断指向下一个结点,j累加1

  • 若链表末尾p为空,则说明第i个元素不存在

  • 否则查找成功,将欲删除结点p->next赋值给q

  • 将q结点中的数据域赋值给e,作为返回

  • 释放q结点

  • 伪代码实现

Status listDelete(linkList *L,int i,ElemType *e){
	int j;
	LinkList p,q;
	p = *L;
	j = 1;

	while(p->next && j < i){
		p = p->next;
		++j;
	}
	if( !(p->next) || j > i){
		return ERROR;
	}
	q = p->next;
	p->next =q->next;
	*e = q->data;
	free(q);
	return OK;
}

七、效率问题

不论是单链表的插入还是删除,都由两个部分组成,

  • 第一部分:遍历查找第i个元素
  • 第二部分:实现插入或者删除操作
  • 则时间复杂度为:O(n)
  • 如果我们不知道第i个元素指针位置,单链表数据结构在插入和删除操作上与线性表的顺序存储结构是没有太大优势的
  • 如果我们希望从第i个位置开始,插入连续10个元素,对于顺序存储结构,则每次插入都需要移动(n-i)个位置,所以每次都是O(n)
  • 而单链表,我们只需要在第一次是,找到第i个位置的指针,此时为O(n),接下来只是简单的通过赋值移动指针即可。时间复杂度都是O(1)
Linux

评论