数据结构03线性表.ppt

第三讲线性表提纲1线性表及其基本运算2线性表的顺序存储结构3线性表的链式存储结构1.1线性表基本概念线性表（Linearlist）是最简单且最常用的一种数据结构。线性表是具有相同类型的n（n≥0）个数据元素（结点）a1,a2,…,an组成的有限序列。其中数据元素的个数n定义为表的长度。当n=0时称为空表，常常将非空的线性表（n0）记作：（a1,a2,…,an)这里的数据元素ai(1≤i≤n)只是一个抽象符号，具体含义视情况而不同。这种结构具有下列特点：存在一个唯一的没有前驱的（头）数据元素；存在一个唯一的没有后继的（尾）数据元素；此外，每一个数据元素均有一个直接前驱和一个直接后继数据元素。1.2线性表逻辑结构例如：英文字母表（A，B，C，…，Z）是一个长度为26的线性表，其中的每一个字母就是一个数据元素；某公司2003年每月产值表（400，420，500，…，600，650）(单位：万元)是一个长度为12的线性表，其中的每一个数值就是一个数据元素。上述两例中的每一个数据元素都是不可分割的，在一些复杂的线性表中，每一个数据元素又可以由若干个数据项组成，在这种情况下，通常将数据元素称为记录(record)含用大量记录的线性表又称为文件例如，图2.1学生成绩表就是一个线性表，表中每一个学生的成绩就是一个记录，每个记录包含六个数据项：学号、姓名、高等代数……。1.2线性表逻辑结构1.2线性表逻辑结构矩阵也是一个线性表，但它是一个比较复杂的线性表。在矩阵中，我们可以把每行看成是一个数据元素，也可以把每列看成是一个数据元素，而其中的每一个数据元素又是一个线性表。因此，线性表或者是一个空表（n=0），或者可以写成：（a1，a2，a3，…，ai-1，ai，ai+1，…，an）。1.3线性表的基本操作数据的运算(线性表的基本操作）是定义在逻辑结构上的，而运算的具体实现则是在存储结构上。线性表的基本运算：（1）置空表InitList(L):将线性表L置成空表（2）求长度ListLength(L):求线性表L中结点个数（3）取结点GetNode(L,i):取出线性表L中第i个结点（4）定位Locate(L,x):在线性表L中查找x的位置（5）插入Insert(L,x,i):在线性表L的第i个位置插入一值为x的新结点（6）删除Delete(L,i):删除线性表L的第i个结点2顺序线性表在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素，称作线性表的顺序存储结构，线性表称为顺序表。2.1顺序表存储结构在线性表的顺序存储结构中，其前后两个元素在存储空间中是紧邻的，且前驱元素一定存储在后继元素的前面。由于线性表的所有数据元素属于同一数据类型，所以每个元素在存储器中占用的空间大小相同，因此，要在该线性表中查找某一个元素是很方便的。假设线性表中的第一个数据元素的存储地址为Loc(a1)，每一个数据元素占d字节，则线性表中第i个元素ai在计算机存储空间中的存储地址为：Loc(ai)=Loc(a1)+(i-1)*d2.1顺序表存储结构只要确定了存储线性表的起始位置，线性表中任一元素都可随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。在程序设计语言中，通常利用数组来表示线性表的顺序存储结构。这是因为数组具有如下特点:(1)数据中的元素间的地址是连续的；(2)数组中所有元素的数据类型相同。这两特点与线性表的顺序存储结构类似。2.2顺序表的基本操作1.顺序表的插入操作线性表的插入运算是指在表的第i（1≤i≤n)个位置上，插入新结点x,使长度为n的线性表：（a1，…，ai-1，ai，…，an）变成长度为n+1的线性表：（a1，…，ai-1，x，ai，…，an）2.2顺序表的基本操作2.2顺序表的基本操作插入算法（C语言版）intInsert_Item(SeqList*L,DataTypex,inti){intj;if(i1||iL-length+1)return0;for(j=L-length;j=i-1;j--)L-data[j+1]=L-data[j];L-data[i-1]=x;L-Length++;retur