算法与数据结构课件.ppt

算法与数据结构课件.ppt第一章线性表本章是学****后续章节(串,树,图,排序):“第一元素”;“最后元素”;,均有唯一的后继;,均有唯一的前驱。线性结构是一个数据元素的有序(次序)集线性表是一种最简单的线性结构线性表是n个数据元素k0,k1,…,kn的有限序列,记为(k0,k1,…ai,…,an)其中,ki可以是一个数、一个字母、一串字符、一页书,甚至更复杂的信息例如:英文字母表(A,B,C,…,Z)在校生人数变化情况表(800,1500,2400,4100,…,20000)一、线性表的逻辑结构在稍复杂的线性表中,一个数据元素可以由若干个数据项组成,如职工工资表职工姓名性别年龄工资1王小林男5122002陈红女4718003孙丽丽女3517604赵京男271650…………………………在这种情况下,通常把数据元素称为记录,把含有大量记录的线性表称为文件。综上所述:线性表中的数据元素可以是各种各样的,但同一线性表中的元素必定具有相同的特性,即属同一数据对象,相邻数据元素之间存在着序偶关系。线性表的基本运算查找查找线性表的第i(0<=i<n-1)个结点在线性表中查找值为x的结点插入把新结点插在线性表第i(0<=i<n-1)个位置上把新结点插在值为x的结点的前面(后面)删除在线性表中删除第i(0<=i<n-1)个结点在线性表中删除值为x的结点线性表的基本运算统计线性表中结点的个数打印线性表中所有结点复制一份线性表把一个线性表拆成几个线性表把几个线性表合并成一个线性表根据结点的某个字段值按升序(降序)重新排列线性表顺序存贮的线性表顺序存贮地址线性表的插入线性表的删除用顺序存贮的线性表表示多项式一、线性表的顺序存储结构——顺序映象最简单的一种顺序映象方法是:令y的存储位置和x的存储位置相邻。以x的存储位置和y的存储位置之间某种关系表示逻辑关系<x,y>。顺序存储结构:用一组地址连续的存储单元依次存放线性表中的数据元素。a1a2…ai-1ai…an线性表的起始地址称作线性表的基地址