数据结构2第2章.pptVIP

线性表的逻辑结构及其基本操作 线性表的顺序存储结构 线性表的链式存储结构 静态链表 应用实例 2.1. 线性表的逻辑结构及其基本操作 线性表是n(n=0)个相同类型数据元素a0, a1, …，an-1构成的有限序列。 形式化定义： Linearlist = (D, R) 换句话说，就是线性表中有第一个元素，第二个元素等等。每一个元素也都有一种数据类型。虽然概念上并不排除可以有不同数据类型元素的线性表，但在本章讨论的简单线性表实现中，表中的所有元素都具有相同的数据类型。 概念：线形表的长度，结点，表头，表尾，前驱元素，后继元素 　线性表中不包含任何元素时，我们称之为空（empty）表。当前存储的元素数目叫做线性表的长度（length）。线性表中的数据元素也称为结点。线性表的开始结点叫做表头，最后一个结点叫做表尾。当n≥1时，k0是最前面的一个元素，kn－1是最后一个元素，线性表中数据元素的相对位置是确定的。线性表的数据元素构成一个序列，在序列中，kj排在kj+1的前面，我们称kj为kj+1的前驱元素；kj+1排在kj后面，我们称kj+1是kj的后继元素。k0没有前驱元素，kn－1没有后继元素。当n≥2时，k0有后继元素k1，kn－1有前驱元素kn－2；当n≥3时，ki（i=1, 2,…, n－2）既有前驱元素ki－1，也有后继元素ki+1。表中元素的值与它的位置之间可以有联系，也可以没有联系。 2.2 线性表的顺序存储结构--顺序表 在计算机内，可以利用不同的存储方式表示线性表，其中最常用、最简单的方式是顺序存储。所谓线性表的顺序存储，就是用一组连续的存储单元依次存储线性表中的结点。 顺序表一般用数组实现，这就意味着将要分配固定长度的数组，因此当线性表生成时数组的长度必须是已知的。每个线性表可以表示为一个不等长的数组，而这个长度必须由线性表对象来记录。在任何给定时刻，线性表中都具有一定数目的元素，这个数目应该小于数组允许的最大值，线性表中当前的实际元素数目也必须在线性表中记录。 线性表的插入 下面用一个C语言函数sq_insert( )实现上述的插入算法。此函数在具有n个结点的线性表list中，把值为x的结点插在第i（0≤i≤n）个位置上。越界以后：若插入位置i不在可以插入的位置上（即i0或in），则返回1；表满之后：若n＝MAXSIZE（即线性表已满），此时list数组没有存储单元存放新结点，则返回2；若插入成功，则返回0。在函数的参数中，有一个指针变量p_n，在调用时，把存放线性表的当前结点个数的变量n的地址赋给指针变量p_n，以此来实现插入后线性表长度n增加1（关于指针的概念和有关性质等，请大家查阅C语言中相关的内容）。 线形链表的结构 　　由于线性链表中的每个结点都有一个链接指针，所以不要求链表中的结点必须按结点的先后次序存放在一个连续存储区中。也就是说，对于结点k，并不要求它的后继结点k’一定存放在结点k后面的连续存储单元中，只要把存放结点k’的地址存放在结点k的链接指针中就行。这样，根据结点k的链接指针，我们就很容易找到k的后继结点k’。由于存储结点时放松了要求，所以存储结点比较灵活自由。因此，在线性链表中插入或删除结点比在顺序存储的线性表中容易。但是，这是以花费一些存储空间为代价换来的：每个结点都需要有一个链接指针，而指针需要占用一定的存储空间。 linklist *CREATELISTR() { char ch; linklist *head,*s,*r; head＝NULL; r＝NULL; ch＝getchar(); while(ch!=‘$’) { s＝malloc(sizeof(linklist)); s-data＝ch; if (head==NULL) head＝s; else r-next＝s; r＝s; ch＝getchar(); } 尾插法建立单链表 if (r!=NULL) r-next＝NULL; return head; } 算法验证 按序号查找 linklist *GET(linklist *head,int i) { int j; linklist *p; p＝head;j＝0; while((p-next!=NULL)(ji)) { p＝p-next; j++; } if (i==j) return p; else return NULL; } 查找运算 按值查找 linklist *LOCATE(linklist *head,datatype key) { linklist *p; p＝head-ne