965- 线性表的逻辑结构.pptVIP

存储特点 顺序表 1.每个数据元素占用相同数量的存储空间 2.逻辑上相邻的数据元素物理次序上也相邻 3.相邻两个数据元素Ki与ki+1存储位置关系： Loc(ki+1)= Loc(ki) +c 4.第i个元素ki的存储位置为 Loc(ki)= Loc(k0) +i×c 用C语言描述存储结构 定义顺序表 1.＃define MAXNUM 100 DataType element[MAXNUM]; int n;/顺序表长度/ 用C语言描述存储结构 定义顺序表 基本运算的实现 基本运算的实现 顺序表 1.创建空表 PSeqList CreateNullList_Seq( void) 算法2.10 在单链表中求某元素的存储位置 PNode locate_link(LinkList llist, DataType x ) /* 在llist带有头结点的单链表中找第一个值为x的结点存储位置 */ { PNode p; if (llist==NULL) return(NULL); p = llist-link; while( p != NULL p-info != x ) p = p-link; return (p); } ? 算法2.11 求单链表中下标为i的(第i+1个)元素的存储位置 PNode find_link( LinkList llist, int i ) /* 在带有头结点的单链表llist中求下标为i的(第i+1个)结点的存储位置 */ /* 当表中无下标为i的(第i+1个)元素时，返回值为NULL */ { PNode p; int j; if (i0) /* 检查i的值 */ { printf(The value of i=%d is not reasonable.\n,i); return (NULL); } p=llist; for ( j=0;j=i;j++ ) { p = p-link; if ( p == NULL ) return (NULL); } return (p); } （1）顺序表表示 A.创建空顺序表，插入元素（n1,n2,…..nm）; B.从第s个结点开始寻找，输出和删除顺序表中的第m个结点。 （2）循环链表表示 A.创建循环单链表，插入元素（n1,n2,…..nm）; B.从第s个结点开始寻找，输出和删除顺序表中的第m个结点。 3.试设计一个民航公司的自动订票和退票系统的算法 。设某时刻的乘客之间的关系如下： 序号 data llink rlink 1 Li 6 5 2 Chang 4 9 3 Wang 5 7 4 Bai 0 2 5 Ma 1 3 6 Du 8 1 7 Xiu 3 0 8 Ding 9 6 9 Chen 2 8 分析： 初始的序列为 n1，n2，n3，……，nm （1）寻找：确定出列人的存储位置 （2）输出：输出第m个结点 （3）删除：删除该结点 （4）重复上述操作 对象的存储：顺序表和循环链表 问题的对象： 操作： （1）寻找：确定出列人的存储位置（从第s个人数到第m个人的存储位置S1） 初始：s1＝s-1, s1＝（s1＋m-1）％n （2）输出：输出第m个结点 （3）删除：删除该结点 （4）重复上述操作 （1）寻找：确定出列人的存储位置 找第s个元素，P指向第s个结点， 从p所指结点开始计数寻找第m个结点； （2）输出：输出第m个结点 p-info （3）删除：删除该结点 pre-link=p-link;free(p) （4）重复上述操作，直到所有结点被删除为止 顺