ch2线性表解答.ppt

第二章 线性表; 例1、26个英文字母组成的字母表 （A，B，C、…、Z） 例2 一副扑克牌的点数 （1,2,3,4,5,6,7,8,9,10，J，Q，K）;例3、学生健康情况登记表如下：;线性表;线性表的运算;4）LOCATE(L,x) 按值查找，若表中存在一个或多个值为x的结点，返回第一个找到的数据元素的位序，否则返回一个特殊值。 5）INSERT(L,x,i) 在L中第i个位置插入新的数据元素x，表长加1。 6）DELETE(L,i) 删除表中第i个数据元素，e返回其值，表长减1。;例2.1利用线性表的基本算法实现清除表L中的重复节点。;2.2线性表的存储1、顺序表;顺序表的存储方式：;顺序表（Sequenlist）的类型定义 #define maxsize 1024 //最大允许长度 typedef int datatype; typedef struct {datatype data[maxsize]; //存储空间基址 int last; //当前元素个数 } sequenlist; sequenlist *L;; 顺序表基本运算 求表长 LENGTH(L) 查找：GET(L,i) 、 定位 ：LOCATE(L,x) 插入： INSERT(L,x,i) 删除： DELETE(L,i) ; 求表的长度 int Length ( sequenlist *L ) { return (*L).last+1; } 提取函数：在表中提取第 i 个元素的值 datatype Get ( sequenlist *L, int i ) { if ( i = 0 i (*L).last) return (*L).data[i]; else printf ( “参数 i 不合理！\n” ); } ;按值查找：找x在表中的位置，若查找成功，返回表项的位置，否则返回-1 ;插入;顺序表的插入 int Insert ( sequenlist *L, datatype x, int i ) { int j; //在表中第 i 个位置插入新元素 x if (i 1 || i (*L).last+1|| (*L).last = maxsize-1) return 0; //插入不成功 else { for ( j = (*L).last; j =i-1; j-- ) (*L).data[j+1] =(*L ).data[j ]; (*L).data[i-1] = x; (*L).last++; return 1; //插入成功 } };顺序表插入时，平均数据移动次数AMN在各表项 插入概率相等时平均时间复杂度 ：T(n)=O(n);删除;顺序表的删除（删除指定位置上的元素） int DELETE ( sequenlist *L, int i ) {int j; if ((i1) || (i(*L).last+1)) {printf (“error”); return null; //非法位置 else { for ( j = i; j = (*L).last; j++ ) //第i个结点的下标是i-1 (*L).data[j-1] = (*L).data[j]; //结点前移 (*L).last - -; } return (1); //成功删除 };顺序表的删除（删除指定值为x的元素）;顺序表的应用:集合的“并”运算;集合的“交”运算 ;4. 顺序表的分析;顺序表之整体概念：;2.3线性表的链式存储; 链表是指用一组任意的存储单元来依次存放线性表的结点，这组存储单元即可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。因此，链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储