数据结构-线性表(3)
时间: 2020-07-22来源:OSCHINA
线性表的链式存储结构
线性表的链式存储结构的特点是 用一组任意的存储单元存储线性表的数据元素,这组存储单元可以是连续的,也可以是不连续的。
意味着数据元素可以存在内存未被占用的任意位置。
链式结构中,除了要存数据元素信息外,还要存储它的后继元素的存储地址。
为了表示每个数据元素ai与其直接后继数据元素ai+1之间的逻辑关系,对数据元素ai来说,除了存储其本身的信息之外,还需要存储一个指示其直接后继的信息(即直接后继的存储位置)。
我们把存储数据元素信息的域称为数据域,把存储直接后继位置的域称为指针域。
指针域中存储的信息称做指针或链。
这两部分信息组成数据元素ai的存储映像,称为 结点 Node。
n个节点(ai的存储映像)链结成一个链表,即为线性表(a1,a2,...,an)的链式存储结构。
此链表的每个结点中只包含一个指针域,所以叫做 单链表。
单链表正是通过每个结点的指针域将线性表的数据元素按其逻辑次序链接在一起。
我们把链表中的第一个结点的存储位置叫做头指针,整个链表的存取必须是从头指针开始进行,之后的每一个结点,就是上一个的后继指针指向的位置。
最后一个节点的指针没有直接后继,因此指针是 空 (NULL 或者 ^ 表示)
一般会在单链表的第一个结点前附设一个节点,称为头结点。可以不存储任何信息,也可以存储链表长度等附加信息。
头结点的指针域存储指向第一个结点的指针。
头指针与头结点的异同
头指针:
头指针是指链表指向第一个结点的指针,若链表有头结点,则是指向头结点的指针
头指针具有标识作用,所有常用头指针冠以链表的名字
无论链表是否为空,头指针均不为空。头指针是链表的必要元素
头结点:
头结点是为了操作的统一和方便而设立的,放在第一元素的节点之前,其数据域一般无意义(可以存放链表的长度)
有了头结点,对在第一元素节点前插入节点和删除第一节点,其操作与其它节点的操作就统一了
头结点不一定是链表必须要素
线性表链式存储结构代码描述
若线性表是空表,头结点的指针域为空。
结点由存放数据元素的数据域,存放后继结点地址的指针域组成。
假设p是指向线性表第i个元素的指针,
节点ai的数据域,可以用p->data表示,p->data的值是一个数据元素,
节点ai的指针域,可以用p->next表示,p->next的值是一个指针。
p->next指向第i+1个元素,即指向ai+1的指针。
如果p->data = ai 那么 p->next->data = ai+1
单链表的读取
单链表获取第i个元素的数据操作GetElem的算法思路:
1. 声明一个节点p指向链表的第一个结点,初始化j从1开始;
2. 当j<i时,就遍历链表,让p的指针向后移动,不断指向下一个节点,j累加1;
3. 若到链表末尾p为空,则说明第i个元素不存在;
4. 否则查找成功,返回节点p的数据。
//初始条件: 顺序线性表L已经存在, 1<=i<=ListLength(L) //操作结果: 用e返回L中第i个数据元素的值 Status GetElem(LinkList L, int i, ElemType *e){ int j; //声明一个节点p LinkList p; //让p指向链表L的第一个结点 p = L->next; //j为计数器 j = 1; //p不为空且j不等于 while(p && j < i){ //让p指向下一个节点 p = p->next ++j; } if(!p || j > i){ return ERROR; } //赋值第i个元素给e *e = p->data; return OK; }
查找算法的时间复杂度取决于i的位置,当i=n的时候遍历n-1次才行,最坏的时间复杂度是O(n)。
主要核心思想是 “工作指针后移”。
单链表的插入与删除
单链表的插入
将结点s插入到结点p和p->next之间,
s->next = p>next; p->next = s;
先把p的后继结点改成s的后继结点,再把结点s变成p的后继结点。
如果更换顺序,就会导致p->next节点没有上级。
单链表第i个数据插入结点的算法思路:
1. 声明一结点p指向链表第一个结点,初始化j从1开始; 当j<i时,就遍历链表,让p的指针向后移动,不断指向下一结点,j累计1; 若到链表末尾p为空,则说明第i个元素不存在; 否则查找成功,在系统中生成一个空结点s; 将数据元素e赋值给s->data; 单链表的插入标准语句s->next=p->next; p->next = s; 返回成功。
//初始条件:顺序线性表L 已经存在, 1 <=i<=ListLength(L) //操作结果: 在L中第i个位置之前插入新的数据元素e,L的长度加1 Status ListInsert(LinkList *L, int i, ElemType e){ int j; LinkList p,s; p = *L; j = 1; //寻找第i个节点 while(p && j < i){ p = p>nextl ++j; } //第i个元素不存在 if(!p || j > i){ return ERROR; } //生成新结点 s = (LinkList)malloc(Sizeof(Node)) s->data = e; s->next = p->next; p->next = s; return OK; }
malloc是C的标准函数用来生成一个新的结点,其类型与Node是一样的,其实质就是在内存中找一块空地,用来存放e数据s结点。

单链表的删除
将节点q删除单链表的操作,其实就是讲它的前继结点的指针绕过,指向它的后继结点即可。
p->next=p->next->next。
用q替换p->next 即是
q = p->next; p->next=q->next;
就是让p的后继的后继结点改成p的后继结点。
单链表第i个数据删除结点的算法思路: 声明一结点p指向链表第一个结点,初始化j从1开始; 当j<i时,就遍历链表,让p的指针向后移动,不断指向下一个结点,j累加1; 若到链表末尾p为空,则说明第i个元素不存在; 否则查找成功,将欲删除的节点p->next赋值给q; 单链表的删除标准语句p->next = q->next; 将q结点中的数据赋值给e,作为返回; 释放q节点; 返回成功。

//初始条件:顺序线性表L 已经存在, 1 <=i<=ListLength(L) //操作结果: 删除L的第i个数据元素,并用e返回其值, L的长度减1 Status ListDelete(LinkList L, int i, ElemType e){ int j; LinkList p,q; p = *L; j = 1; //寻找第i个节点 while(p->next && j < i){ p = p>nextl ++j; } //第i个元素不存在 if(!(p->next) || j > i){ return ERROR; } //将q的后继赋值给p的后继 q = p->next; p-next = q->next; //将q结点中的数据给e *e = q->data; //让系统回收此结点,释放内存 free(q); return OK; }
free是c的标准函数,主要作用是让系统回收一个Node结点,释放内存。
单链表插入和删除算法,都是由两部分组成: 第一部分就是遍历查找第i个元素;第二部分就是插入和删除元素。时间复杂度都是O(n)。
如果在第i个位置,插入10个元素,对于顺序存储结构来说, 每一次插入都需要移动n-i个元素,每次都是O(n)。
而单链表,只需要在第一次时,找到第i个位置的指针,此时为O(n),接下来只是简单地通过赋值移动指针,时间复杂度都是O(1)。
对于插入或删除数据越频繁的操作,单链表的效率优势就越是明显。
热门排行