第三章 数据组织与处理.

Slides:



Advertisements
Similar presentations
数据结构的引入. 通讯录管理 社团机构管理 校园导航管理 通讯录管理 社团机构管理 校园导航管理.
Advertisements

阻塞操作. 在 linux 里,一个等待队列由一个 wait_queue_head_t 类型的结构来描述 等待队列的初始化: static wait_queue_head_t testqueue; init_waitqueue_head(&testqueue);
数据结构概论 第2章 线性表 董黎刚 浙江工商大学信电学院
第二章 线性表 £2.4 线性表的应用 £2.1 线性表的类型定义 £2.2 线性表的顺序存储结构 £2.3 线性表的链式存储结构
第二章 线性表 2.1 线性表的逻辑结构 一. 线性表定义如下:
第二章 线性表 ⒈教学内容:2.1 线性表逻辑结构; 2.2 线性表的顺序存储及运算实现; 2.3 线性表的链式存储和实现。
第二章 线性表 1 线性表的逻辑结构及其基本操作 2 线性表的顺序存储结构 3 线性表的链式存储结构 4 静态链表 5 应用实例.
第二章 线性表.
第2章 线性表 2.1 线性表的概念及运算 2.2 线性表的顺序存储 2.3 线性表的链式存储 2.4 一元多项式的表示及相加.
Linked List Operations
單向鏈結串列 Singly Linked Lists.
第2章 线性表 线性结构 是一个数据元素的有序集合。.
其他类型的链表主要内容 静态链表 循环链表 双向链表.
计算机软件技术基础 数据结构与算法(2).
第三章 栈和队列 Stack and Queue
第二章 线性表 线性表 顺序表 链表 顺序表与链表的比较.
数据结构 第2章 线性表 吴忠华.
数 据 结 构 Ch.2 线性表 计 算 机 学 院 肖明军
第三章 线性表 3.1 线性表的类型定义 3.2 顺序存储的线性表 3.3 链式存储的线性表 3.4 有序表 3.5 顺序表和链表的综合比较.
数据结构 第二章 线性表.
制作:崔广才
数据结构 Data Structure 中南大学 主讲人:王国军,郑瑾 中南大学信息院计科系
教 师:曾晓东 电 话: E_mail: 计算机软件技术基础 教 师:曾晓东 电 话: E_mail:
第2章 线性表 2.1 线性表的基本概念 2.2 线性表的顺序存储 2.3 线性表的链式存储 2.4 线性表的应用 2.5 有序表 本章小结.
本 章 说 明 2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式存储结构 2.4 循环链表和双向链
辅导课程六.
西安交通大学计教中心 ctec.xjtu.edu.cn
第2章 线性表 线性表抽象数据类型 顺序表 主要知识点 单链表 循环单链表 循环双向链表 静态链表 设计举例.
第 1 章 数据结构 1.1 基本数据结构与算法 1.2 线性表 1.3 栈和队列 1.4 树和二叉树 1.5 查找 1.6 内部排序 65
第2章 线性表 2.1 线性表 2.2 顺序表 2.3 单链表 2.4 循环单链表 2.5 双向链表 2.6 仿真链表
第2章 线性表 丽水学院工学院.
第2章 线性表 2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 一元多项式的表示.
线性表是一种最简单的线性结构 线性结构的基本特征为: 线性结构 是 一个数据元素的有序(次序)集 1.集合中必存在唯一的一个“第一元素”;
第 3 讲 线性表(一).
第二章 线性表.
第一章 绪论.
陈海明 副教授 信息学院 计算机系 电子信息类非计算机专业选修课 程序设计实践 陈海明 副教授 信息学院 计算机系
陈海明 副教授 信息学院 计算机系 电子信息类非计算机专业选修课 程序设计实践 陈海明 副教授 信息学院 计算机系
内容回顾 线性表的定义和特点 线性表的顺序存储及查找、插入和删除.
第二章 线性表 2.1 线性表的类型定义 2.2线性表的顺序存储 2.3线性表的链式存储 2.4一元多项式的表示和相加.
(知识点三) 2.3 线性表的链式表示和实现 本节将介绍线性表的另一存储结构—— 链式存储及其对应的操作。
线性表练习.
陈海明 副教授 信息学院 计算机系 电子信息类非计算机专业选修课 程序设计实践 陈海明 副教授 信息学院 计算机系
cn/~dongeliu/dsa.html 刘 东 信息学院6系 中国科学技术大学
顺序表的插入.
王玲 第 2 章 线性表 王玲 2019/2/25.
第2章 线性表 本章主要介绍下列内容 线性表的定义和基本操作 线性表的顺序存储结构 线性表的链式存储结构 线性表的应用举例.
第二章 线性表.
3.1 线性表及逻辑结构 3.2 线性表的顺序存储 3.3 线性表的链式存储 3.4 链式存储结构的应用
严蔚敏、吴伟民编著 清华大学出版社 学习网站:中国网页设计
C++语言程序设计 C++语言程序设计 第七章 类与对象 第十一组 C++语言程序设计.
顺序表的删除.
单链表的基本概念.
顺序查找.
线性结构 线性结构的特点: 线性结构的种类 在数据元素的非空有限集中, (1)存在唯一的一个被称做“第一个”的数据元素;
<编程达人入门课程> 本节内容 内存的使用 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群: ,
第 四 讲 线性表(二).
成绩是怎么算出来的? 16级第一学期半期考试成绩 班级 姓名 语文 数学 英语 政治 历史 地理 物理 化学 生物 总分 1 张三1 115
第二章 线性表.
3.16 枚举算法及其程序实现 ——数组的作用.
1.2 子集、补集、全集习题课.
多层循环 Private Sub Command1_Click() Dim i As Integer, j As Integer
第一章 绪论 1.1 引言 1.2 逻辑结构和存储结构 1.3 算法.
实验目的:掌握数据的顺序存储结构及它们在计算机中的操作。 实验内容:
第三章 线性表 3.1 线性表的类型定义 3.2 顺序存储的线性表 3.3 链式存储的线性表 3.4 有序表 3.5 顺序表和链表的综合比较.
西安交通大学计教中心 ctec.xjtu.edu.cn
算法3.3 void InitList_sq(SqList &L,int msize=LIST_INIT_SIZE)
第二章 线性表 线性表是一种最简单的线性结构 线性结构是一个数据元素的有序(次序)集.
第二部分 数据结构—— 用面向对象方法与C++描述.
第二章 线性表 东南大学计算机学院 方效林 本课件借鉴了清华大学殷人昆老师 和哈尔滨工业大学张岩老师的课件.
Presentation transcript:

第三章 数据组织与处理

任务 3.1 SAGM系统津贴数据插入

3.1.1 案例描述 假设SAGM系统中现有三条职工津贴记录,每条记录包括工号、姓名和津贴,现要求在第2行插入一条新记录,运行结果如下图。

3.1.2 案例分析 解决思路: 将从第2条开始的所有记录依次向后移动1位; 将新记录插入。 数据结构: 本案例中的数据是一组教职工的津贴信息,每条信息有工号、姓名和津贴组成。这些数据具有相同特性,属于同一数据对象,相邻数据元素之间存在序偶关系。所以,该任务中的数据可以用线性表存储。

3.1.3 知识准备 1、数据结构的基本概念 数据是一些可以被计算机接收和处理的描述客观事物的符号。这些符号可以是数字、字符、图形、声音及其他。 数据元素是数据(集合)中的一个“个体”,是数据的基本单位。也可称为节点、记录。 数据对象是具有相同性质的若干个数据元素的集合。

3.1.3 知识准备 1 5 2 4 3 6 etc user dev lib bin bin dev etc lib user 树形结构 3.1.3 知识准备 树形结构 数据元素之间存在着一个对多个的关系 树 二叉树 二叉搜索树 14 13 12 11 2 3 4 5 6 7 8 9 10 1 9· 数据结构是指数据以及数据元素相互之间的联系。可以看作是相互之间存在着某种特定关系的数据元素的集合。 因此,可时把数据结构看成是带结构的数据元素的集合。 四类基本的结构 : 集合结构:数据元素间的关系是“属于同一个集合”。集合是元素关系极为松散的一种结构。 线性结构:数据元素之间存在着一对一的关系。 树型结构:数据元素之间存在着一对多的关系。 图形结构:数据元素之间存在着多对多的关系,图形结构也称作网状结构。 图形(网状)结构 数据元素之间存 在着多对多的关系。 1 5 2 4 3 6 etc user 集合 数据元素之间无特殊关系 dev lib bin 线性结构 数据元素之间存在着一个对一个的关系 bin dev etc lib user

3.1.3 知识准备 数据结构的形式定义用一个二元组表示,记为: Data_Structure = (D, S) 3.1.3 知识准备 数据结构的形式定义用一个二元组表示,记为: Data_Structure = (D, S) 其中,D 是数据元素的有限集(即一个数据对象), S 是该对象中所有数据成员之间的关系的有限集合。 在计算机科学中,对复数的定义:复数是一种数据结构 Complex=(C,R) 其中:C是包含两个实数的集合 {C1, C2 }, R={P},P是定义在C上的一种关系{ <C1,C2> }。

3.1.3 知识准备 数据结构包括如下3个方面: (1)数据元素之间的逻辑关系,即数据的逻辑结构。 3.1.3 知识准备 数据结构包括如下3个方面: (1)数据元素之间的逻辑关系,即数据的逻辑结构。 (2)数据元素及其关系在计算机存储器中的存储方式, 即数据的存储结构,也称为数据的物理结构。 (3)施加在该数据上的操作,即数据的运算。

3.1.3 知识准备 数据的逻辑结构从逻辑关系上描述数据,可以看作是从具体问题抽象出来的数据模型,与数据的存储无关,也与数据元素本身的形式、内容、相对位置无关; 数据的逻辑结构分类: 线性结构 线性表、栈、队列 、串 非线性结构 树 、图(或网络)

3.1.3 知识准备 数据的物理结构是数据的逻辑结构在计算机中的表示,也称存储结构,研究的是数据结构在计算机中的实现方法。 3.1.3 知识准备 数据的物理结构是数据的逻辑结构在计算机中的表示,也称存储结构,研究的是数据结构在计算机中的实现方法。 它包括数据元素的表示和关系的表示: (1)数据元素的表示:位、字长、元素、结点、数据域 (2)关系的表示分为两种基本的存储方法: ①顺序映像(顺序存储结构) ②非顺序映像(链式存储结构)

3.1.3 知识准备 顺序存储结构借助数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。所有元素存放在一片连续的存贮单元中,逻辑上相邻的元素存放到计算机内仍然相邻。比如: 地址 元素 L:(a1,a2,a3,…,an) 2000 2002 2004 … 2008 2010 a1 a2 a3 … an-1 an

3.1.3 知识准备 链式存储结构 在链接存储结构中,每个节点即数据元素由数据域Data和指针域Next两部分组成。数据域存放元素本身的数据,指针域存放与其相邻的元素地址。 一个节点 data next Head data next data next data null 单链表表示的线性表

3.1.3 知识准备 数据的运算主要有以下几种: 插入: 在数据结构中的指定位置插入新的元素。 3.1.3 知识准备 数据的运算主要有以下几种: 插入: 在数据结构中的指定位置插入新的元素。 删除: 根据一定的条件,将某个节点从数据结构中删除。 更新: 更新数据结构中某个指定节点的值。 检索: 在给定的数据结构中,找出满足一定条件的节点,条 件可以是一个或多个数据项的值。 排序: 根据某一给定的条件,将数据结构中所有的节点重新 排列顺序。

3.1.3 知识准备 2、线性表 线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列,通常记为: 3.1.3 知识准备 2、线性表 线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列,通常记为: L:(a1,a2,… ai-1,ai,ai+1,…an) 其中n为表长, n=0 时称为空表。相邻元素之间存在着顺序关系。将ai-1 称为 ai 的直接前趋,ai+1 称为 ai 的直接后继。除了第一个元素没有直接前驱和最后一个元素没有直接后继之外,其余的每个数据元素只有一个直接前驱和一个直接后继。

3.1.3 知识准备 假设有线性表:L:(a1,a2, . . . ,ai,. . . ,an ) 其基本操作主要有: 3.1.3 知识准备 假设有线性表:L:(a1,a2, . . . ,ai,. . . ,an ) 其基本操作主要有: (1)InitList(L) 操作结果:将L初始化为空表。 (2)DestroyList(L) 操作前提:线性表L已存在。 操作结果:将L销毁。 (3)ClearList(L) 操作结果:将表L置为空表。

3.1.3 知识准备 (4)EMPETY(L) (5)LENGTH(L) (6)GET (L,i, e) 3.1.3 知识准备 (4)EMPETY(L) 操作前提:线性表L已存在。 操作结果:如果L为空表则返回真,否则返回假。 (5)LENGTH(L) 操作结果:如果L为空表则返回0,否则返回表中的元素个数。 (6)GET (L,i, e) 操作前提: 表L已存在,1<=i<=listlen(L)。 操作结果: 用e返回L中第i个元素的值。

3.1.3 知识准备 (7)LocateElem(L,e) (8)ListInsert(L,i,e) 3.1.3 知识准备 (7)LocateElem(L,e) 操作前提: 表L已存在,e为合法元素值。 操作结果: 如果L中存在元素e,则将元素e所在位置返回,否则返回0。 (8)ListInsert(L,i,e) 操作前提:表L已存在,e为合法元素值且1≤i≤Listlen(L)+1。 操作结果:在L中第i个位置之前插入新的数据元素e,L的长度加1。 (9)ListDelete(L,i, e) 操作前提:表L已存在且非空 ,1≤i≤Listlen(L)。 操作结果:删除L的第i个数据元素,并用e返回其值,L的长度减1。

3.1.3 知识准备 3、线性表的顺序存储—顺序表 具有顺序存储结构的线性表称为顺序表。 特点: 3.1.3 知识准备 3、线性表的顺序存储—顺序表 具有顺序存储结构的线性表称为顺序表。 特点: 线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素。 因为内存中的地址空间是线性的,用物理上的相邻实现数据元素之间的逻辑相邻关系是简单。 顺序表具有按数据元素的序号随机存取的特点。

3.1.3 知识准备 线性表的顺序存储表示如下: #define DATATYPE1 int #define MAXSIZE 100 3.1.3 知识准备 线性表的顺序存储表示如下: #define    DATATYPE1 int #define MAXSIZE 100 typedef  struct { DATATYPE1 data[MAXSIZE]; /* 线性表占用的数组空间。*/   int        len;    /*线性表的长度*/  } SEOUENLIST ;

3.1.3 知识准备 顺序表的初始化操作 void InitList (SQOUENLIST *L) { //构造一个空的线性表 3.1.3 知识准备 顺序表的初始化操作 void InitList (SQOUENLIST *L) { //构造一个空的线性表 L->len=0; //空表长度为0 } 求表长度的操作 Int LENGTH( SQOUENLIST *L ) { return L->len; }

3.1.3 知识准备 顺序表的取元素操作 DATATYPE1 GET(SQOUENLIST *L,int i) {//取线性表中第i个元素 3.1.3 知识准备 顺序表的取元素操作 DATATYPE1 GET(SQOUENLIST *L,int i) {//取线性表中第i个元素 if(i<1||i>L->len) return 0; else return L->data[i-1]; }

3.1.3 知识准备 p p p p p p i 8 1 1 4 2 3 e = 38 50 L->len = 7 顺序表的查找操作 3.1.3 知识准备 顺序表的查找操作 23 75 41 38 54 62 17 L->data p p p p p L->len = 7 p i 8 1 1 4 2 3 可见,基本操作是, 将顺序表中的元素 逐个和给定值 e 相比较。 e = 38 50

3.1.3 知识准备 int LocateElem (SQOUENLIST *L, DATATYPE1 e) 3.1.3 知识准备 int LocateElem (SQOUENLIST *L, DATATYPE1 e) { // 在顺序表中查询第一个满足判定条件的数据元素, // 若存在,则返回它的位序,否则返回 0 int i ; // i 的初值为第 1 元素的位序 i= 1; while (i <= L->len && L->data[i-1]!=e) ++i; if (i <= L->len) return i; else return 0; }

3.1.3 知识准备 a1 a2 … ai-1 ai … an … a1 a2 … ai-1 ai an e 顺序表的插入操作 3.1.3 知识准备 顺序表的插入操作 分析:假设在线性表的第i个元素之前插入一个元素e。 插入元素时,线性表的逻辑结构由 (a1,…,ai-1, ai,…,an) (a1, …, ai-1, e, ai, …, an) <ai-1, ai> <ai-1, e>, <e, ai> a1 a2 … ai-1 ai … an … a1 a2 … ai-1 ai an e

3.1.3 知识准备 顺序表插入操作算法的基本思想: 检查i值是否超出所允许的范围(1≤i≤n+1),若超出,则进行“超出范围”错误处理; 3.1.3 知识准备 顺序表插入操作算法的基本思想: 检查i值是否超出所允许的范围(1≤i≤n+1),若超出,则进行“超出范围”错误处理; 将线性表的第i个元素和它后面的所有元素均向后移动一个位置; 将新元素写入到空出的第i个位置上; 使线性表的长度增1。

3.1.3 知识准备 Status ListInsert (SQOUENLIST *L, int i, DATATYPE1 e) { 3.1.3 知识准备 Status ListInsert (SQOUENLIST *L, int i, DATATYPE1 e) { // 在顺序表L的第 i 个元素之前插入新的元素e, // i 的合法范围为 1≤i≤L.len+1 int k; if (i < 1 || i > L->len+1) printf(“ ERROR”); // 插入位置不合法 else { for (k=L->len;k>=i;k--) L->data[k]= L->data[k-1]; // 插入位置及之后的元素右移 L->data[i-1]= e; // 插入e ++ L-> len; // 表长增1 }

3.1.3 知识准备 a1 a2 … ai-1 ai ai+1 … an a1 a2 … ai-1 ai+1 an … e 顺序表的删除操作 3.1.3 知识准备 顺序表的删除操作 分析: 假设删除线性表的第i个元素保存在变量e中。 删除元素时,线性表的逻辑结构由 (a1,…,ai-1, ai, ai+1, …,an) (a1, …, ai-1, ai+1, …, an) <ai-1, ai> <ai, ai+1> <ai-1, ai+1> a1 a2 … ai-1 ai ai+1 … an a1 a2 … ai-1 ai+1 an ai … e

3.1.3 知识准备 顺序表的删除算法的基本思想: 检查i值是否超出所允许的范围(1≤i≤n),若超出,则进行“超出范围”错误处理; 3.1.3 知识准备 顺序表的删除算法的基本思想: 检查i值是否超出所允许的范围(1≤i≤n),若超出,则进行“超出范围”错误处理; 线性表的第i个元素赋值给e。 将线性表的第i个元素后面的所有元素均向前移动一个位置; 使线性表的长度减1。

3.1.3 知识准备 void ListDelete (SQOUENLIST *L, int i, DATATYPE1 &e) 3.1.3 知识准备 void ListDelete (SQOUENLIST *L, int i, DATATYPE1 &e) {// 在顺序线性表L中删除第i个元素,并用e返回其值 // i的合法值为1≤i≤Listlen (L) if ((i < 1) || (i > L->len)) printf(“error”); // 删除位置不合法 e = L->data [i-1]); // 被删除元素的值赋给e for (k=i+1; k<=L->len; k ++) L->data[k-2]= L->data[k-1]; // 被删除元素之后的元素左移 L->len - -; }

3.1.3 知识准备 判断表是否为空的操作 int EMPTY( SQOUENLIST *L) { if(L->len==0) 3.1.3 知识准备 判断表是否为空的操作 int EMPTY( SQOUENLIST *L) { if(L->len==0) return 1; else return 0; }

3.1.4 案例实现 main() { SEQUENLIST list,*L; int i; DATATYPE1 x; 3.1.4 案例实现 main() { SEQUENLIST list,*L; int i; DATATYPE1 x; DATATYPE1 s[3]={{1,"张凡",980},{2,"李丽",850},{3,"王海",1000}}; L=&list; INITIATE(L); for(i=1;i<=3;i++) INSERT(L,i,s[i-1]); printf("现有职工津贴表为:\n"); printf("工号 姓名 津贴\n"); for(i=1;i<=LENGTH(L);i++) printf("%-10d%-10s%-10d\n",GET(L,i).no ,GET(L,i).name ,GET(L,i).money ); printf("请在第二行插入一条新纪录: 姓名:肖云 , 津贴:880元\n"); x.no =002; strcpy(x.name,"肖云"); x.money =880; INSERT(L,2,x); printf("添加新纪录后的职工津贴表为:\n"); }

3.1.5 拓展训练 线性表的链式存储—单链表 用一组任意的存储单元存储线性表的数据元素 3.1.5 拓展训练 线性表的链式存储—单链表 用一组任意的存储单元存储线性表的数据元素 利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素 每个数据元素ai,除存储本身信息外,还需存储其直接后继的信息 对线性表的插入、删除不需要移动数据元素 结点:数据元素ai 的存储映像 数据域:元素本身信息 指针域:指示直接后继的存储位置 数据域 指针域 结点

3.1.5 拓展训练 LNode LNode next data p 1、单链表的表示: #define DATATYPE2 cahr 3.1.5 拓展训练 1、单链表的表示: #define DATATYPE2 cahr typedef struct LNode { DATATYPE2 data; struct LNode *next; } LinkList; LNode LNode next data p (*p) 表示p所指向的结点 p->data 表示p指向结点的数据域 p->next 表示p指向结点的指针域 2、生成一个LNode型新结点: p=(LinkList *)malloc(sizeof(LinkList)); 3、系统回收p结点: free(p);

3.1.5 拓展训练 单链表的建立—头插入法(HCreateList ()) 算法思路: (1)建立头结点,头指针L=NULL; 3.1.5 拓展训练 单链表的建立—头插入法(HCreateList ()) 算法思路: (1)建立头结点,头指针L=NULL; (2)按线性表中元素的顺序依次读入数据元素,不是结束标志时,申请节点p。 (3)将新节点插入到已建好的单链表的头结点与第一个结点之间。

3.1.5 拓展训练 已知线性表(20,17,40,60,34),用头插法创建带有头结点的单链表。 L ∧ 34 60 40 17 20 p 3.1.5 拓展训练 已知线性表(20,17,40,60,34),用头插法创建带有头结点的单链表。 L ∧ 34 60 40 17 20 p p p p p

3.1.5 拓展训练 void HCreateList ( ) { // 输入 n 个数据元素的值,建立带头结点的单链表 L 3.1.5 拓展训练 void HCreateList ( ) { // 输入 n 个数据元素的值,建立带头结点的单链表 L LinkList *p,*L; int i; L = ( LinkList *) malloc ( sizeof (LinkList ) ); L->next = NULL; // 先建立一个带头结点的空链表 for ( i = n; i > 0; --i ) { p = ( LinkList ) malloc ( sizeof (LinkList ) ); scanf ("%d" ,&p->data ); p->next = L->next; L->next = p; }

3.1.5 拓展训练 初始化操作 LinkList *INIT( ) { LinkList *L; 3.1.5 拓展训练 初始化操作 LinkList *INIT( ) { LinkList *L; L= (LinkList *)malloc(sizeof(LinkList)); L->next=NULL; return L; }

3.1.5 拓展训练 int LENGTH(LinkList *L) { int i; LinkList *p; p=L; i=0; 3.1.5 拓展训练 求表长度操作 int LENGTH(LinkList *L) { int i; LinkList *p; p=L; i=0; While(p->next!=NULL) { p=p->next; i++; } return i;

3.1.5 拓展训练 单链表查找操作 -- GetElem(L, i, &e) 算法思路: 3.1.5 拓展训练 单链表查找操作 -- GetElem(L, i, &e) 算法思路: (1)令p为指针变量,首先指向第一个结点,变量j为计数器; (2)依次向后查找,循环结束的条件,p为空或者j=i。 (3)如果p为空并且j>i,出错;否则就找到了,用e返回第i个元素的值。

3.1.5 拓展训练 已知线性表(20,17,40,60,34),分别查找第3个和第6个元素。 L 20 17 40 60 34 ∧ p 5 3.1.5 拓展训练 已知线性表(20,17,40,60,34),分别查找第3个和第6个元素。 L 20 17 40 60 34 ∧ p 5 2 4 3 1 j

3.1.5 拓展训练 Status GetElem_L(LinkList L, int i, DATATYPE1 &e) 3.1.5 拓展训练 Status GetElem_L(LinkList L, int i, DATATYPE1 &e) { // L是带头结点的链表的头指针,以 e 返回第 i 个元素 p = L->next; // p指向第一个结点 j = 1; // j为计数器 while (p && j<i) { p = p->next; ++j; } if ( !p) return ERROR; e = p->data; // 取得第 i 个元素 return OK; }

3.1.5 拓展训练 定位操作 LinkList *LOCATE(LinkList *L,datatype1 x) 3.1.5 拓展训练 定位操作 LinkList *LOCATE(LinkList *L,datatype1 x) {LinkList *p; p=L->next; while(p!=NULL&&p->data!=x) p=p->next; return p; }

3.1.5 拓展训练 单链表的插入操作 -- ListInsert(&L, i, e) 3.1.5 拓展训练 单链表的插入操作 -- ListInsert(&L, i, e) 分析:“插入元素”使线性表的逻辑结构和物理结构发生什么变化?假设在线性表的第i个元素之前插入一个元素e。 (a1,…,ai-1, ai,…,an) (a1, …, ai-1, e, ai, …, an) <ai-1, ai> <ai-1, e>, <e, ai> L a1 ai-1 ai an …… …… ∧ e

3.1.5 拓展训练 s 第i个元素之前插入元素e e p p ai-1 ai ai-1 ai (插入前) (插入后) 3.1.5 拓展训练 第i个元素之前插入元素e s e p p ai-1 ai ai-1 ai (插入前) (插入后) s = (LinkList *)malloc(sizeof(LinkList)); s->data = e; s->next = p->next; p->next = s;

3.1.5 拓展训练 已知线性表(20,17,40,60,34),在第3个元素前插入元素10. p j s L 20 17 40 60 34 3.1.5 拓展训练 已知线性表(20,17,40,60,34),在第3个元素前插入元素10. L 20 17 40 60 34 ∧ p 2 1 j s 10

3.1.5 拓展训练 int ListInsert_L ( LinkList L, int i, int e ) 3.1.5 拓展训练 int ListInsert_L ( LinkList L, int i, int e ) {// 带头结点的单链表L中第 i 个位置之前插入元素 e LNode *p,*s; int j; p = L->next; j = 1; while ( p && j<i-1 ) { p = p->next; ++j; } if ( ! p) return ERROR; s = ( LinkList *) malloc ( sizeof (LinkList ) ); // 生成新结点 s->data = e; // 使新结点数据域的值为 e s->next = p->next; // 将新结点插入到单链表 L 中 p->next = s; // 修改第 i-1 个结点指针 return OK; }

单链表的删除操作 -- ListDelete(&L, i, &e) 3.1.5 拓展训练 单链表的删除操作 -- ListDelete(&L, i, &e) 分析:删除第i个元素使线性表的物理结构发生什么变化? L an a1 ai-1 ai ai+1 ∧ ……

3.1.5 拓展训练 p p q 删除第i个元素,并保存数据到元素e中 ai-1 ai ai+1 3.1.5 拓展训练 删除第i个元素,并保存数据到元素e中 p e ai p q ai-1 ai ai+1 q = p->next; // 用指针 q 指向被删除结点 p->next = q->next; // 删除第 i 个结点 *e=ai; free(q);

3.1.5 拓展训练 LinkList *L, int i, int *e ) {// 删除第 i 个元素,并由 e 返回其值 3.1.5 拓展训练 LinkList *L, int i, int *e ) {// 删除第 i 个元素,并由 e 返回其值 LinkList *p,*q;int j; p = L->next; j = 1; while ( p && j<i-1 ) { p = p->next; ++j; } if ( ! p) return ERROR; // 删除位置不合理 q = p->next; // 用指针 q 指向被删除结点 p->next = q->next; // 删除第 i 个结点 *e = q->data; // 取出第 i 个结点数据域值 free (q); // 释放第 i 个结点 return OK; }

3.1.5 拓展训练 判断表空的操作 int EMPTY(LinkList *L) { if(L->next==NULL) 3.1.5 拓展训练 判断表空的操作 int EMPTY(LinkList *L) { if(L->next==NULL) return 1; else return 0; }

3.1.5 拓展训练 思考: 假设SAGM系统中现有三条职工津贴记录,每条记录包括工号、姓名和津贴,现要求在第2行插入一条新记录,试运用单链表实现。

课程学习资源 实践教学管理平台: http://http://59.76.156.25/sxglxt/ 课程在线学习平台 http://bb.lzpcc.edu.cn 精品课程建设网 http://jpkc.lzpcc.com.cn/rjkfjs

任务结束 www.lzpcc.edu.cn