《数据结构数组与顺序表.ppt》由会员分享，可在线阅读，更多相关《数据结构数组与顺序表.ppt（30页珍藏版）》请在三一办公上搜索。
1、第2章 顺序表与数组,数据结构,一维数组,数组的定义：存储于一个连续存储空间的 相同类型的数据元素的集合。一维数组：长度（大小）为n的有限序列下标，起始下标，元素占用空间，数组占用空间，访问数组元素，.,35 27 49 18 60 54 77 83 41 02,下标 0 1 2 3 4 5 6 7 8 9,多维数组及其顺序存储,多维数组是一维数组的推广,i,i,j,i,k,一维数组a5,二维数组b35,三维数组c354,ai bij cijk,复合线性结构,j,一维数组连续存储方式,35 27 49 18 60 54 77 83 41 02,0 1 2 3 4 5 6 7 8 9,l l l
2、 l l l l l l l,LOC(i)=LOC(i-1)+l=LOC(i-1)+i*l,LOC(i)=,LOC(0)+i*l,i 0,LOC(0),i=0,a+i*l,a,二维数组连续存储方式,行优先存放：LOC(j,k)=LOC(0,0)+(j*m+k)*l,每个元素占用的存储单元,第一个元素的存储地址,三维数组连续存储方式,各维元素个数为 m1,m2,m3。下标为 i1,i2,i3的数组元素的存储地址：（按页/行/列存放）,LOC(i1,i2,i3)=LOC(0,0,0)+(i1*m2*m3+i2*m3+i3)*l,前i1页总元素个数,第i1页的前i2行总元素个数,第i2行前i3列元素
3、个数,线性表(Linear List),定义：n个数据元素的有限序列；n为线性 表的长度，当n0时为空表。特点：除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。原则上讲，线性表中表元素的数据类型可以不相同。但采用的存储表示可能会对其有限制。,顺序表(Sequential List),定义：将线性表中的元素相继存放在一 个连续的存储空间中。可利用一 维数组或链表作为其存储结构。特点：顺序存取 限制：所有元素有相同数据类型 顺序表的遍历：,顺序表结构,listarray,0,1,size-1,MaxSize,size,数组下标,数组
4、,变量,操作算法,MaxSize-1,.,.,.,初始化操作插入操作删除操作查找操作排序操作.,顺序表(SeqList)类的定义,public class SeqList final int defaultSize=10;int maxSize;int size;Object listArray;private void initiate(int sz)maxSize=sz;size=0;listArray=new Objectsz;public SeqList(int size)initiate(size);public SeqList()initiate(defaultSize);publ
5、ic int size()return size;public boolean isEmpty()return size=0;public int Find(Object x)public void insert(int i,Object obj)public Object delete(int i)public Object getData(int i)public int MoreDataDelete(SeqList L,Object x),顺序表的查找（搜索）,public int Find(Object x)int i=0;while(i=size)return-1;else retu
6、rn i;,搜索函数 int Find(Object x)在顺序表中从头向尾查找结点值等于给定值x的结点,顺序搜索图示,25 34 57 16 48 09,0 1 2 3 4 5,搜索 16,i,25 34 57 16 48 09,i,25 34 57 16 48 09,i,25 34 57 16 48 09,i,搜索成功,listarray,25 34 57 16 48,0 1 2 3 4,搜索 50,i,25 34 57 16 48,i,25 34 57 16 48,i,25 34 57 16 48,i,25 34 57 16 48,i,搜索失败,listarray,搜索成功的平均比较次数
7、,若搜索概率相等，则,最好情况，查找目标为第一个元素，比较1次；最坏情况：搜索不成功 数据比较 n 次。,情况i时的比较次数,情况i发生的概率,顺序表的插入操作,25 34 57 16 48 09 63,0 1 2 3 4 5 6 7,50,插入 x=,25 34 57 50 16 48 09 63,0 1 2 3 4 5 6 7,50,i,listarray,listarray,顺序表的插入操作成员函数,public void insert(int i,Object obj)throws Exceptionif(size=maxSize)throw new Exception(顺序表已满无法
8、插入！);if(i size)throw new Exception(参数错误！);for(int j=size;j i;j-)listArrayj=listArrayj-1;listArrayi=obj;size+;,顺序表的删除操作,25 34 57 50 16 48 09 63,0 1 2 3 4 5 6 7,listarray,16,删除 x,25 34 57 50 48 09 63,0 1 2 3 4 5 6 7,listarray,顺序表的删除操作成员函数（1）,public Object delete(int i)throws Exceptionif(size=0)throw n
9、ew Exception(顺序表已空无法删除！);if(i size-1)throw new Exception(参数错误！);Object it=listArrayi;for(int j=i;j size-1;j+)listArrayj=listArrayj+1;size-;return it;,顺序表的删除操作成员函数（2）,public int MoreDataDelete(SeqList L,Object x)int i,j;int tag=0;for(i=0;i L.size;i+)if(x.equals(L.getData(i)L.delete(i);i-;tag=1;return
10、 tag;,顺序表示例（1）,public class SeqListTest1public static void main(String args)SeqList seqList=new SeqList(100);int n=10;tryfor(int i=0;i n;i+)seqList.insert(i,new Integer(i+1);System.out.println(size1=+seqList.size);seqList.delete(4);System.out.println(size2=+seqList.size);seqList.insert(2,new Integer
11、(22);System.out.println(size3=+seqList.size);System.out.println(seqList.Find(new Integer(8);for(int i=0;i seqList.size;i+)System.out.print(seqList.getData(i)+);catch(Exception e)System.out.println(e.getMessage();,顺序表示例（2）,class Studentlong number;String name;String sex;int age;Student(long number,St
12、ring name,String sex,int age)this.number=number;this.name=name;this.sex=sex;this.age=age;public long getNumber()return number;public String getName()return name;public String getSex()return sex;public int getAge()return age;,顺序表示例（2）,public class SeqListTest2public static void main(String args)SeqLi
13、st seqList=new SeqList(100);Student student;student=new Student3;student0=new Student(2000001,张三,男,20);student1=new Student(2000002,李四,男,21);student2=new Student(2000003,王五,女,22);int n=3;tryfor(int i=0;i n;i+)seqList.insert(i,studenti);for(int i=0;iseqList.size;i+)Student st=(Student)seqList.getData
14、(i);System.out.println(st.getNumber()+st.getName()+st.getSex()+st.getAge();catch(Exception e)System.out.println(e.getMessage();,顺序存储结构的优缺点,优点：（1）算法简单、可读性好、开发代价低缺点：（1）插入、删除操作时需要移动大量元素，效率较低；（2）最大表长（MaxSize）难以估计，太大了浪费空间，太小了容易溢出。,稀疏矩阵(Sparse Matrix),非零元素个数远远少于矩阵元素个数,稀疏矩阵(Sparse Matrix),定义：设矩阵 Amn 中有 t 个
15、非零元素，若 t 远远小于矩阵元素的总数 mn，则称矩阵A 为稀疏矩阵。为节省存储空间，应只存储非零元素。非零元素的分布一般没有规律，应在存储非零元素时，同时存储该非零元素的行下标 row、列下标 col、值 value。每一个非零元素由一个三元组表示，并用一顺序表（一维数组）来存放上述三元组.,class Trituple/三元组int row,col;/非零元素行号/列号 double value;/非零元素的值,矩阵的三元组表示(压缩),稀疏矩阵的抽象数据类型,class Trituple/三元组private int row,col;/非零元素行号/列号private double v
16、alue;/非零元素的值 class SparseMatrix/稀疏矩阵类定义 int Rows,Cols,Terms;/行，列，非零元素数 final int MaxTerms=20;Trituple smArray=new TritupleMaxTerms;/三元组表 public SparseMatrix(int MaxRow,int Maxcol);/构造函数/转置、相加、相乘 public SparseMatrix Transpose(SparseMatrix a);public SparseMatrix Add(SparseMatrix a,SparseMatrix b);public SparseMatrix Multiply(SparseMatrix a,SparseMatrix b);,特殊矩阵的表示(压缩),对称矩阵,特殊矩阵的表示(压缩),三角矩阵,带状矩阵和对角矩阵,特殊矩阵的表示(压缩),
