河南中医药大学：《数据结构与算法》课程PPT教学课件（C#语言描述）第2章 线性表（定义、顺序存储结构、链式存储结构）

第2章线性表 2.1线性表的定义 211什么是线性表 线性表是具有相同特性的数据元素的一个有限序列。其特 征如下 ●所有数据元素类型相同; ●线性表是有限个数据元素构成的; ●线性表中数据元素是与位置有关的,通常从1开始 编号,每个数据元素有唯一的序号,这一点表明线 性表不同于集合

第2章 线性表 2.1 线性表的定义 2.1.1 什么是线性表 线性表是具有相同特性的数据元素的一个有限序列。其特 征如下： 所有数据元素类型相同； 线性表是有限个数据元素构成的； 线性表中数据元素是与位置有关的，通常从1开始 编号，每个数据元素有唯一的序号，这一点表明线 性表不同于集合

线性表的逻辑结构一般表示为:(a1a2,,n1,.an) 用图形表示的逻辑结构如下图所示 首元素 尾元素 a1)(a2 a)→ 其中,用n(m≥0)表示线性表的长度(即线性表中数据 元素的个数)。当n=0时,表示线性表是一个空表。 在线性表中,每个元素至多只有一个前趋元素并且 至多只有一个后继元素。这是线性表的逻辑特征

线性表的逻辑结构一般表示为：(a1 ,a2 ,…,ai ,ai+1,…an )。 用图形表示的逻辑结构如下图所示。 a1 a2 ai ai+1 an a … … 1 a2 ai ai+1 an … … 首元素 尾元素 其中，用n（n≥0）表示线性表的长度（即线性表中数据 元素的个数）。当n=0时，表示线性表是一个空表。 在线性表中，每个元素至多只有一个前趋元素并且 至多只有一个后继元素。这是线性表的逻辑特征

212线性表的抽象数据类型描述 ADT List 数据对象 D={a11≤i≤n,n≥0,a为 Elemtype类型 ElemType是自定义类型,本章中假设 ElemType为 Istring 数据关系: r={<a,a1+1-|aa+1∈D=1,…,n-1 基本运算 void create list( (stringl split):由spli数组中的元素建立存储结构。 string Displisto:将线性表中的所有元素构成一个字符串返回。 int ListLengtho:求线性表的长度 bool getelem(inti, restring e):求线性表中序号为的元素值e int Locate elem( string e):按元素值e查找其序号。 bool ListInsert(int i, stringe):插入数据元素e作为线性表的第个元素。 bool listDelete(int i; ref string e):在线性表中删除第个数据元素e

2.1.2 线性表的抽象数据类型描述 ADT List { 数据对象： D={ai | 1≤i≤n,n≥0,ai为ElemType类型} //ElemType是自定义类型，本章中假设ElemType为string 数据关系： r={ | ai ,ai+1∈D,i=1,…,n-1} 基本运算： void CreateList(string[] split)：由split数组中的元素建立存储结构。 string DispList()：将线性表中的所有元素构成一个字符串返回。 int ListLength()：求线性表的长度。 bool GetElem(int i,ref string e)：求线性表中序号为i的元素值e int LocateElem(string e)：按元素值e查找其序号。 bool ListInsert(int i,string e)：插入数据元素e作为线性表的第i个元素。 bool ListDelete(int i,ref string e)：在线性表中删除第i个数据元素e。 }

2.2线性表的顺序存储结构 221线性表的顺序存储结构一顺序表 class sqlistclass 顺序表类 const int MaxSize=100;/数组的长度 public stringl data; /1放顺序表中元素 public int length /1放顺序表的长度 public sqlistclasso /构造函数,实现data和 ength的初始化 i data=new string MaxSize; length=0 线性表的基本运算算法 数组下标01… i-2 Max Size-I data数组a1a2 arl a+1 空闲

2.2 线性表的顺序存储结构 2.2.1 线性表的顺序存储结构—顺序表 class SqListClass //顺序表类 { const int MaxSize=100; //数组的长度 public string[] data; //存放顺序表中元素 public int length; //存放顺序表的长度 public SqListClass() //构造函数，实现data和length的初始化 { data=new string[MaxSize]; length=0; } //线性表的基本运算算法 } data 数组 a1 数组下标 0 a2 1 …… … ai -1 i-2 ai i-1 ai+1 i …… … an n-1 空闲 MaxSize-1

说明: Sqlistclass类的一个对象L称为顺序表对象L,也 简称为顺序表L,其中主要有data、 length字段和相关的运算 方法,通过 L data或 Llength对字段进行操作,后面的顺序栈 顺序队、顺序串等都采用相似的方式。 SqlistClass l= new sqlistClasso; data length 其他方法等

说明：SqListClass类的一个对象L称为顺序表对象L，也 简称为顺序表L，其中主要有data、length字段和相关的运算 方法，通过L.data或L.length对字段进行操作，后面的顺序栈、 顺序队、顺序串等都采用相似的方式。 data length 其他方法等 L SqListClass L＝new SqListClass();

222顺序表基本运算的实现 建立顺序表 其方法是将给定的含有若干个元素的数组 Split的每个元 素依次放入到顺序表中,并将其长度赋给顺序表的 length字 段。对应的算法如下: public void Createlist( stringl split)/由 split中的元素建立顺序表 i int i; for (i=0; i<split Length; i++) data[i=split[; length=i

2.2.2 顺序表基本运算的实现 1．建立顺序表 其方法是将给定的含有若干个元素的数组split的每个元 素依次放入到顺序表中，并将其长度赋给顺序表的length字 段。对应的算法如下： public void CreateList(string[] split) //由split中的元素建立顺序表 { int i; for (i=0;i<split.Length;i++) data[i]=split[i]; length=i; }

2.顺序表基本运算算法 (1)输出线性表 Displist0 该运算是依次输出顺序表中各数组元素的值,这里是将顺 序表中的所有元素构成一个字符串返回。对应的算法如下: public string Displisto if (length>0) string mystr-data[ 0; for (i=l; i<length; i++) /扫描顺序表中各元素值 mystr+="+data j; return mystr; else return"空串";

2．顺序表基本运算算法 （1）输出线性表DispList() 该运算是依次输出顺序表中各数组元素的值，这里是将顺 序表中的所有元素构成一个字符串返回。对应的算法如下： public string DispList() { int i; if (length>0) { string mystr=data[0]; for (i=1;i<length;i++) //扫描顺序表中各元素值 mystr+=" "+data[i]; return mystr; } else return "空串"; }

(2)求线性表的长度 ListLengthe0 该运算返回顺序表的长度即其中的元素个数。实际上只需 返回 length字段的值即可。对应的算法如下 public int ListLengtho return length;

（2）求线性表的长度ListLength() 该运算返回顺序表的长度即其中的元素个数。实际上只需 返回length字段的值即可。对应的算法如下： public int ListLength() { return length; }

(3)求线性表中某个数据元素值 Getelen(e) 该运算用变量e表示线性表中逻辑序号为)元素,当逻辑 序号正确时取e= datai-1并返回true,否则返回fae对应的 算法如下: public bool GetElem(inti, ref string e) {if(i length) return false /参数错误时返回 false e=datai-1: /取元素值 return true; ∥1功找到元素时返回rue

（3）求线性表中某个数据元素值GetElem(i,e) 该运算用变量e表示线性表中逻辑序号为i的元素，当逻辑 序号i正确时取e=data[i-1]并返回true，否则返回false。对应的 算法如下： public bool GetElem(int i,ref string e) { if (ilength) return false; //参数错误时返回false e=data[i-1]; //取元素值 return true; //成功找到元素时返回true }

(4)按元素值查找 LocateElem(e) 该运算顺序查找第一个值与e相等的元素的逻辑序号。若 顺序表中不存在这样的元素,则返回值为0。对应的算法如下 public int Locate Elem(string e) int i=0 while (iclength & string Compare(datail,e)=0) i++ /查找元素e if (i>=length /未找到时返回0 return 0 else eturn i+1 /找到后返回其逻辑序号

（4）按元素值查找LocateElem(e) 该运算顺序查找第一个值与e相等的元素的逻辑序号。若 顺序表中不存在这样的元素，则返回值为0。对应的算法如下： public int LocateElem(string e) { int i=0; while (i=length) //未找到时返回0 return 0; else return i+1; //找到后返回其逻辑序号 }