[其它考试]算法与数据结构_C语言版_第二版_陈守孔_第2章.ppt

[其它考试]算法与数据结构_C语言版_第二版_陈守孔_第2章.ppt

  1. 1、本文档共69页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
[其它考试]算法与数据结构_C语言版_第二版_陈守孔_第2章

第二章 线性表 线性结构 在数据元素的非空的有限集合中: 存在唯一的一个被称为“第一个”的数据元素; 存在唯一的一个被称为“最后一个”的数据元素; 除第一个元素外,集合中每个元素都有且仅有一个前驱; 除最后一个元素外,集合中每个元素都有且仅有一个后继; 线性表(Linear List)定义 定义: n个具有相同特性的数据元素组成的有限序列; 表示:{a1,…,ai-1,ai,ai+1,…,an} ai必须具有相同特性,即属于同一数据对象 ai-1是ai的直接前驱元素,ai+1是ai的直接后继元素 数据元素ai在线性表中有确定的位置i,i称为位序 线性表中数据元素的个数n称为线性表的长度,n=0时,线性表称为空表 抽象数据类型定义 ADT List{ 数据对象:D={ai|ai∈ElemSet,i=1,2,…,n,n≥0} 数据关系:R={ai-1,ai|ai,ai-1∈D,i=2,…,n} 基本操作: ListInit (L) ; ListLength (L) ; ListGet(L,i) ; ListLocate (L,x) ; ListClear (L) ; 6. ListEmpty (L) ; ListPrior (L,e) ; ListNext(L,e) ; ListInsert(L,i,e) ; ListDelete(L,i); }ADT List 线性表举例1(遍历线性表) ListTraverse(List L,visit()) {//遍历线性表 if(ListEmpty(L)) printf(“空表”); else for(i=1;i=ListLength(L);i++) visit(ListGet(L,i)); } 线性表举例2(合并线性表) List ListMerge(List La,List Lb) {//La和Lb是两个非递减有序的线性表,将线性表La和Lb合并成一个新的线性表Lc,Lc也非递减有序。 ListInit(Lc); i=j=1;k=0; La_len=ListLength(La);Lb_len=ListLength(Lb); while((i=La_len)(jLb_len))//La和Lb均非空 {ai=ListGet(La,i); bj=ListGet(Lb,j); if(ai=bj) {ListInsert(Lc,++k,ai);++i;} else {ListInsert(Lc,++k,bj);++j;} } 线性表举例2(合并线性表) 逻辑结构是本质 通过上面两个例子可以看出: 逻辑结构是数据组织的某种“本质性”的东西: (1)逻辑结构与数据元素本身的形式、内容无关。 (2)逻辑结构与数据元素的相对位置无关。 (3)逻辑结构与所含数据元素的个数无关。 算法的设计取决于选定的逻辑结构,而算法的实现依赖于采用的存储结构 线性表的顺序表示和实现 线性表的顺序表示 :线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素,用这种存储形式存储的线性表称为顺序表。 设 a1的存储地址为Loc(a1),每个数据元素占L个存储单元,则第i个数据元素的地址为: Loc(ai)=Loc(a1)+(i-1)*L 1≤i≤n 顺序表上基本运算的实现(1) SeqList SeqListInit( ) {//构造一个空的顺序表 SeqList L; //定义L为顺序表 L.length=0; //初始化顺序表为空表 return L; } 顺序表上基本运算的实现(2) 插入运算:在第 i 个位置,插入元素e 思想:把从第i个位置开始的元素,依次后移 步骤: 1.当前表是否已经满? 2.输入是否有效? 3.插入元素。 顺序表上基本运算的实现(2) void SeqListInsert(SeqList L,int i,ElemType x) {//在顺序表中的第 i 个位置插入元素 x if (L.length==MAXSIZE) {printf("表满"); exit(0); } //表满,退出 if(i1 || iL.length+1)   {printf("位置错"); exit(0);}//插入位置错,退出 for(j=L.length-1;j=i-1;j--) L.data[j+1]=L.data[j]; //逐一后移 L.data[i-1]=x;  //新元素插入到第i个位置 L.length++; //顺序表长度增1 } 顺序表上基本运

文档评论(0)

qiwqpu54 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档