《C语言程序设计与数据结构》课件第13章.ppt
《《C语言程序设计与数据结构》课件第13章.ppt》由会员分享,可在线阅读,更多相关《《C语言程序设计与数据结构》课件第13章.ppt(35页珍藏版)》请在三一文库上搜索。
1、C语言程序设计与数据结构,第十三章 线 性 表,C语言程序设计与数据结构,本章学习内容,线性表的定义 线性表的基本运算 线性表的基本操作 线性表的链式存储,C语言程序设计与数据结构,线性表是最基本、最常用的一种数据结构。它在计算机内的存储方法有两种:顺序存储和链式存储,它的主要基本操作是插入、删除和检索等。,C语言程序设计与数据结构,13.1 线性表及其基本运算,13.1.1 线性表的定义 线性表是最常用和最简单的一种数据结构。特点是数据元素之间是一种线性关系,数据元素“一个接一个的排列”。 英文字母表(A,B,Z)是线性表,表中每个字母是一个数据元素(结点)。 扑克牌的点数(2,3,10,J
2、,Q,K,A)也是一个线性表,其中数据元素是每张牌的点数和花色 。,C语言程序设计与数据结构,线性表是具有相同数据类型的n(n=0)个数据元素的有限序列,通常记为: (a1,a2, ai-1,ai,ai+1,an) 其中n为表长, n0 时称为空表。 特点: 表中相邻元素之间存在着顺序关系。将 ai-1 称为 ai 的直接前趋,ai+1 称为 ai 的直接后继。就是说:对于ai,当 i=2,.,n 时,有且仅有一个直接前趋 ai-1.,当i=1,2,.,n-1 时,有且仅有一个直接后继 ai+1,而 a1 是表中第一个元素,它没有前趋,an 是最后一个元素,无后继。,C语言程序设计与数据结构,
3、13.1.2 线性表的基本运算 (1) InitList(L) L是没有初始化的线性表, 为L开辟空间并将L置为空表。 (2) DestroyList(L) 线性表L已存在, 将L的存储空间释放。,C语言程序设计与数据结构,(3) ClearList(L) 线性表L已存在, 将表L置为空表。 (4) emptyList(L) 线性表L已存在, 如果L为空表则返回真,否则返回假。 (5) ListLength(L) 线性表L已存在, 如果L为空表则返回0,否则返回表中的元素个数。,C语言程序设计与数据结构,(6) Locate(L,e) 表L已存在,e为线性表中元素或与之同型元素, 如果L中存在
4、元素e,则返回元素e所在位置,如果L中不存在元素e,则返回0。 (7) Getelem(L,i) 表L存在,i为整数,i值合法,即1iListLength(L)。返回线性表L中第i个元素的值,否则提示出错。,C语言程序设计与数据结构,(8) InsertList(L,i,e) 表L已存在,e的数据类型同线性表中数据元素,且1iListLength(L)+l,在L中第i个位置前插入新的数据元素e,现行表L的长度加1。 (9) DeleteList(L,i,e) 表L已存在且非空,i为整数,如果1iListLength(L),删除线性表中的第i个数据元素,并用e返回其值,函数值返回真,线性表的长度
5、减1;否则函值返回假。,C语言程序设计与数据结构,13.2 线性表的顺序表示及基本操作,13.2.1 线性表的顺序表示 线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素,用这种存储形式存储的线性表称为顺序表 。,C语言程序设计与数据结构,13.2.2 顺序表的基本操作实现 1.初始化 Status InitList_sq(SqList /成功返回OK / InitList_sq,C语言程序设计与数据结构,2.插入运算 在线性表L中第i个数据元素之前插入数据元素e, 插入后使原表长为n的表: (a1,a2,. ,ai-1,ai,ai+1,. ,an) 成为表长为 n+1
6、 表: (a1,a2,.,ai-1,e,ai,ai+1,.,an ) 其中 i 的取值范围为1= i = n+1 。,C语言程序设计与数据结构,用类C语言实现顺序表的插入: Status ListInsert_sq(SqList /ListInsert_sq,C语言程序设计与数据结构,3.删除运算 线性表的删除运算是指将表中第 i 个元素从线性表中去掉,删除后使原表长为 n 的线性表成为表长为 n-1 的线性表:,C语言程序设计与数据结构,用类C语言实现顺序表的删除运算 int ListDelete(SQ_LIST *L,int i,EntryType *e) if (IsEmpty(L) r
7、eturn ERROR; /检测线性表是否为空 if (iL-length) return ERROR; /检查i值是否合理 *e=L-itemi-1; /将欲删除的数据元素内容保留在e所指示的存储单元中 for (j=i;jlength-1;j+) /将线性表第i+1个元素之后的所有元素向前移动 L-itemj-1=L-itemj; L-length-; /线性表长度减1 return OK; / ListDelete,C语言程序设计与数据结构,13.3 线性表的链式存储,线性表的链式存储结构不需要用地址连续的存储单元来实现,因为它不要求逻辑上相邻的两个数据元素物理上也相邻,它是通过“链”建
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- C语言程序设计与数据结构 语言程序设计 数据结构 课件 13
链接地址:https://www.31doc.com/p-2152616.html