[工学]数据结构导论2142第二章.ppt

第2章 线性表 第2章 线性表 2.1 线性表的基本概念 2.2 线性表的顺序实现 2.3 线性表的连接实现 2.4 其它运算在单链表上的实现 2.5 其它链表 2.6 顺序实现与连接实现的比较 2.7 串 2.1 线性表的基本概念 线性表是由n（n≥0）个数据元素（结点） a1，a2，…，an组成的有限序列。 ① 数据元素的个数n定义为表的长度, n=0时称为空表，记作（）② 将非空的线性表（n＞0）记作： L=（a1，a2，…，an）③ 数据元素ai（1≤i≤n）只是个抽象符号，其具体含义在不同情况下可以不同。 线性表的基本术语： 起始结点、终端结点、直接前驱、直接后继线性表长度，空表 线性表的逻辑结构特征 对于非空的线性表:① 有且仅有一个开始结点a1，没有直接前趋，有且仅有一个直接后继a2； ② 有且仅有一个终结结点an，没有直接后继，有且仅有一个直接前趋an-1； ③ 其余的内部结点ai（2≤i≤n-1）都有且仅有一个直接前趋ai-1和一个直接后继ai+1。 线性表的基本运算 1，初始化 InitList(L) 2，求表长度 ListLength(L) 3，取表元 GetNode(L,i) 4，定位 LocateNode(L,x) 5，插入 InsertList(L,x,i) 6，删除 DeleteList(L,i) 区分引用型和加工型操作 2.2 线性表的顺序实现 定义 顺序表是线性表的顺序存储存储结构，即以一段连续内存存放的线性表 此时， 内存的顺序性体现了数据间的逻辑关系 线性表中相邻的结点在存储结构中仍相邻 设线性表中所有结点的类型相同，则每个结点所占用存储空间大小亦相同。 假设表中每个结点占用L个存储单元，其中第一个单元的存储地址则是该结点的存储地址， 并设表中开始结点a1的存储地址是b，那么结点ai的存储地址LOC（ai） 基本运算在顺序表上的实现 插入、删除、定位 插入 线性表的插入运算是指在表的第i（1≤i≤n+1）个位置上，插入一个新结点x，使长度为n的线性表：（a1，…，ai-1，ai，…an）变成长度为n+1的线性表：?????? （a1，…，ai-1，x，ai，…an） 顺序表插入操作过程 void InsertList ( Seqlist *L，x，i ){ int j; if ( i 1 || i L-last + 1 ) Error(“位置错误”); if ( L-last = MaxSize ) Error(“溢出); for( j=L-last-1; j=i-1; j--) ?????? ? L-data[ ] = L-data[ ]; L-data[ ] = x;???? L-last++;?? } 假设线性表中含有n个数据元素， 在进行插入操作时，有 位置可插入 在每个位置插入数据的概率是： 在i位置插入时，要移动 个数据 假定在n+1个位置上插入元素的可能性均等， 则平均移动元素的个数为： 2. 删除 线性表的删除运算是指将表的第i个结点删去，使长度为n的线性表???????????? （a1，…，ai-1，ai，ai+1，…，an）变成长度为n-1的线性表???????????? （a1，…，ai-1，ai+1，…，an） 顺序表删除操作过程 1，若i=n，则只要删除终端结点，无须移动结点； 2，若1≤i≤n-1，则必须将表中位置 i+1，i+2，…，n的结点，依次前移到位置i，i+1，…，n-1上，以填补删除操作造成的空缺。 3，该表长度减1 顺序表删除操作过程 具体算法描述 void DeleteList(SeqList *L,int i) {?int j; ? if( i 1 || i L.last )????? Error(“位置错误”);  for( j = i ;j L.last ; j++ ) ??????? L.data[ j-1 ] =L.data[ j ]; L.length - - ;????????????? } 假设线性表中含有n个数据元素， 在进行删除操作时，有 位置可删除 在每个位置删除数据的概率是： 在i位置删除时，要移动 个数据 假定在n个位置上删除元素的可能性均等， 则平均移动元素的个数为： 在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为： 3. 定位(查找) 定位运