文档介绍：计算机软件技术基础
长春理工大学计算机科学技术学院基础部孙爽滋
顺序表优点和缺点
优点:
逻辑上相邻元素存储位置也相邻,无需增加额外存储空间可方便随机存取表中任一元素。
缺点:
插入和删除运算不方便,必须移动大量结点,效率较低不适合元素经常变动的大的线性表。
对于长度变化较大的线性表,要一次性地分配足够的存储空间,但这些空间常常又得不到充分的利用;容易造成存储空间的“碎片”
思路(链式存储):
元素可以散落在任何位置,不必相邻
让每个元素知道它的下一个元素在哪里
我们只需要知道第一个元素的位置
插入删除不再需要移动元素而是需要修改元素间的关系
1
2
3
4
5
6
2
3
4
5
6
1
顺序存储结构不足的解决办法
链式存储结构特点:
线性表的链式存储结构
线性表的链式存储结构是指用一组任意的存储单元(可以连续,也可以不连续)存储线性表中的数据元素。为了反映数据元素之间的逻辑关系,对于每个数据元素不仅要表示它的具体内容,还要附加一个表示它的直接后继元素存储位置的信息。
假设有一个线性表(a,b,c,d),可用下图所示的形式存储:
线性表中的数据元素在存储单元中的存放顺序与逻辑顺序不一定一致;
在对线性表操作时,只能通过头指针进入链表,并通过每个结点的指针域向后扫描其余结点,这样就会造成寻找第一个结点和寻找最后一个结点所花费的时间不等,具有这种特点的存取方式被称为顺序存取方式。
线性表的链式存储结构
:
定义:线性表的链式存储结构称为线性链表
数据域: 一部分存放数据元素值
指针域: 存放指针,用于指向该结点的
前一个结点或后一个结点
线性链表中
结点组成:
线性表的链式存储结构
结合C语言:
链表就是一组组的数据用链将它连起来,如下图所示。
数据1
数据2
数据5
数据3
数据4
数据
链
问题是用什么来存放数据,用什么来作为链。
解决办法?
数据1
指
针
◎
数据2
指
针
◎
数据3
指
针
◎
数据域
指针域
从上图知,可以定义一个结构,其中一部分存放数据,另一部分存放指向下一数据的指针。这就构成了单链表。
…
节点
每组数据和指针称为链表的一个节点。
10
: malloc() ——
1)调用方式
void *malloc(unsigned size)
2)功能
在内存中分配size个字节的存储空间,并返回指向分配存储区起始地址的指针;如果不能获得需要的存储空间,将返回空指针。
注:在把返回值赋给具有一定数据类型的指针变量时,应对返回值作强制类型转换。
结合C语言:
跟链表相关的函数