数据结构导论讲义-第二章　线性表

VIP免费

2024-11-16 1 0 959.5KB 16 页 5.9玖币

侵权投诉

第二章　线性表

　　一、学习目的与要求

　　顺序表和单链表分别是简单、基本的顺序存储结构和链式存储结构。顺序表和单链表上实现基本运算

的算法是数据结构中简单和基本的算法。这些内容构成以下各章的重要基础，因此本章是本课程的重点之

一。

　　本章要求：理解线性表的概念；熟练掌握顺序表和链表的组织方法及实现基本运算的算法；掌握在

顺序表和链表上进行算法设计的基本技能；了解顺序表与链表的优缺点。

　　二、课程内容

　　2.1 　线性表的基本概念

　　线性表中结点具有一对一的关系，如果结点数不为零，则除起始结点没有直接前驱外，其他每个结

点有且仅有一个直接前驱；除终端结点没有直接后继外，其他每个结点有且仅有一个直接后继。

　　线性表基本运算有：初始化、求表长、读表元素、定位、插入、删除。

　　2.2 　线性表的顺序存储

　　2.2.1　线性表的顺序存储

　　线性表的顺序存储：逻辑结构相邻的结点其存储位置也相邻。用顺序存储实现的线性表称为顺序表，

一般用数组来表示顺序表，如图 2-1 所示

　　【例 2-1】学生档案信息表的顺序存储实现。

　　【分析】根据学生档案信息，给出顺序表具体的类型定义。

　　2.2.2 　线性表的基本运算在顺序表上的实现

　　插入

　　顺序表的插入运算 InsertSeqlist（SeqList L,DataType x,int i）是指在顺序表的第

i（1<=i<=n+1）个元素之前，插入一个新元素 x。使长度为 n 的线性表（a1，a2，...，ai-1，a

i，...，an）变为长度为 n+1 的线性表（a1，a2，...，ai-1，x，a i，...，an）。

　　具体算法描述如下：

　　2）删除

　　删除运算 DeleteSeqlist（SeqList L，int i ）是指将线性表的第 i（1<=i<=n）个数据元素删去，

使长度为 n 的线性表（a1，a2，... ，ai-1， ai，ai+1，...，an）变为长度为 n-1 的线性表（a1，a2，...

，ai-1， ai+1，...，an）。

　　具体算法描述如下：

　　3）定位

　　定位运算 LocateSeqlist（SeqList L,DataType x）的功能是查找出线性表 L 中值等于 x 的结点序号

的最小值，当找不到值为 x 的结点时，返回结果 0。下列算法从左往右扫描顺序表中的元素，考察元素的

值是否等于 X，描述算法如下：

　　2.2.3　顺序表实现算法的分析

　　插入：O（n）

　　删除：O（n）

　　定位：O（n）

　　2.3　线性表的链接存储

　　2.3.1 　单链表的类型定义

　　线性表的链接存储是指它的存储结构是链式的。线性表常见的链式存储结构有单链表、循环链表和双

向循环链表，其中最简单的是单链表。

　　下面举个例子说明单链表的结构：

　　单链表的一个结点由两部分组成：数据元素和指针，相当于火车的车厢和车钩。各个结点在内存中的

存储位置并不一定连续。链表的结点可以重新连接，相当于火车的编组。

　　如图所示，data 部分称为数据域，用于存储线性表的一个数据元素，next 部分称为指针域或链域，

用于存放一个指针，该指针指向本结点所含数据元素的直接后继结点。

　　非空的单链表和空单链表，如图所示

　　a）非空的单链表 b）空单链表

　　我们通常用结构体类型来定义单链表的结点数据类型：

　　单链表的类型定义如下：

　　Typedef　struct node

　　{

　　Data Type data； //数据域

　　struct node * next； //指针域

　　}Node,*LinkList；

　　【例 2-2】学生档案信息链表的类型完整描述

　　则学生档案信息链式存储实现，如图 2-7所示

　　为了便于运算实现，在单链表的第一个结点之前增设一个类型相同的结点，称之为头结点，其他结

点称为表结点。

　　a）带头结点的非空单链表 b）带头结点的空单链表

　　2.3.2 　线性表的基本运算在单链表上的实现

　　我们首先来讨论单链表的一些基本运算，这是使用单链表的开始。

　　初始化

　　初始化的工作是建立一个空表，空表由一个头指针和一个头结点组成。

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

5.9 玖币 0人已下载

立即下载 VIP免费下载

摘要：

第二章　线性表　　一、学习目的与要求　　顺序表和单链表分别是简单、基本的顺序存储结构和链式存储结构。顺序表和单链表上实现基本运算的算法是数据结构中简单和基本的算法。这些内容构成以下各章的重要基础，因此...

展开>> 收起<<

数据结构导论讲义-第二章　线性表.doc

共16页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

数据结构导论讲义-第二章　线性表

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择:

数据结构导论讲义-第二章 线性表

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择:

数据结构导论讲义-第二章　线性表