[课件资料]线性表(链接存储)

线性表的链接存储,一、顺序存储的缺点：1、它要求系统分配一块连续存贮空间。但是当顺序表很大时，系统可能无法分配给你这么大的一块连续存贮空间，只有多个分散的空间可以提供，而这些分散空间合起来可以足够存放你的数据，那么如何利用这些分散空间呢？打个比方：有一群七人做公交车，上车后发现车上有十个空位，当然通常空位是不连一起的，假如这七人一定要全部坐一起，那么可能无法找到一片连续空位的，于是他们都没有座。但假如他们可以分散坐，那肯定每人都有位子了。,2、在进行插入、删除操作时，将移动大量元素。这会耗费主机时间，效率比较低。,链接存储可以克服以上不足：1）可以充分利用分散的存贮空间。2）在插入、删除操作时，不需要移动元素。,二、线性表的链接存储如何实现,线性表在逻辑上是一个有序排列的元素集合，而链接存储中，元素的存放位置是分散的，那么如何从表头元素开始，依次找到下一个元素，直到最后的表尾元素呢？所以，链接存储的每个结点中，除了存贮各元素的数据外，还必须要保存指向下一个结点的指针。即下一个结点的地址信息，通过这个指针，就可以找到下一个元素。分散存储的各元素就是通过指针一个接一个连成一体，好比是一个环环相扣的链条。这就是链接表。,三、单链表,1、结构：单链表中，每个结点的存贮单元分为两部分：一部分存放结点的数据，也就是线性表中元素的值，称为值域；另一部分存放指向后继结点的指针，称为指针域。最后一个结点没有后继，所以它的指针域为空，即NULL值。另外，对于每个单链表而言，还需要一个表头指针来存放第一个结点的地址。这样，只要从表头指针出发，我们就可以依次找到单链表中的每个元素，直到表尾。所以，通常用表头指针名来命名一个单链表。,2、结点结构的C/C+语言描述structLNode,3、如何在单链表中插入和删除结点1）插入结点有a、b、c三个结点，假设ap，bp，cp都是LNode类型的指针变量，即LNode*ap,*bp,*cp;它们分别指向a，b，c结点，要把b结点插入到a、c之间。则：初始状态：apnext=cp;插入：bpnext=cp;apnext=bp;,2）删除结点同样a、b、c三个结点，以及三个指针ap，bp，cp，要删除a、c之间的b结点。删除前：apnext=bp;bpnext=cp;删除后：apnext=cp;,四、双向链表,1、结构：每个结点包含有两个指针域，分别存放指向前驱结点的指针和指向后继结点的指针。表头结点的左指针域，即前驱指针域为空；表尾结点的右指针域，即后继指针域为空。同样地，双向链表也需要一个表头指针来存放第一个结点的地址。通常，表头指针名作为双向链表名。2、结点结构和C语言描述structDNodeElemTypedata;DNode*left;DNode*right;3、插入和删除操作,线性表操作在单链表上的实现,一、单链表的定义1、单链表上每个结点的结构表示：2、单链表可以用它的表头指针来定义：因为每个单链表都有一个表头指针，表头指针是指向单链表表头结点的指针。从这个表头指针出发，可以顺序找到单链表中的每个元素，所以单链表可以用它的表头指针来表示。,GO,假定我们给表头指针取名为HL，则HL也表示一个单链表。所以我们后面学到在单链表上的各项操作，这些函数的参数中都有HL，表示对单链表进行操作。HL的数据类型：因为它是指向表头结点的指针，而表头结点为LNode类型，所以显然HL的类型为LNode*。在函数定义中，形参用了引用符号，表示：在函数调用时，直接修改实参。所以书上所有的函数定义中，凡是要修改表头指针HL的操作，例如初始化表、插入、删除等，这些函数中形参HL必须用引用，引用符号2）插入时，分两种情况：i)插入在表头，即新结点作为表头结点：newptrnext=HL；HL=newptr；ii)插入在非表头位置：newptrnext=cp；apnext=newptr；,9、函数名：InsertList时间复杂度分析：(1)当pos=0时：此操作与顺序表相比，只需比较元素，而不必移动元素。首先要查找新元素插入的合适位置i，所以需要比较元素i次（从第1到第i个元素与item比较），但第i到第n个元素不用后移位置，只需修改指针即可插入。时间复杂度分析与FindList函数相同：最好情况1次，最坏n次，平均情况(n+1)/2次。所以时间复杂度量级O(n)。(2)当插入到指定位置时：不需要象顺序表那样后移元素，但插入非表头时，需要从表头依次往下找到指定位置。最好情况：插入到表头O(1)最坏情况：插入到表尾O(n)平均情况：比较(n+1)/2次O(n),10、函数名：DeleteList形参：单链表HL，元素item，删除位置pos返回值：true（删除成功）或false（删除失败）功能：根据pos的值，删除单链表HL中符合条件的第一个元素。(1)当pos=0时：在表中查找data=item的第一个结点并删除之。(2)当pos=-1时：删除表尾元素。(3)当1posn时：删除第pos个结点。说明：1）此项操作与顺序表相比，也是只需比较元素，而不必移动元素。比较元素的时间复杂度分析与InsertList类似，故时间复杂度量级为O(n)。当删除表头元素时，时间复杂度量级O(1)。2）在单链表中删除某结点要求释放其空间，用delete语句。3）删除时分两种情况：i）删除表头结点，则HL=HLnext；ii）删除非表头结点，则apnext=cpnext；,11、函数名：SortList形参：单链表HL返回值：无功能：调用InsertList算法，对单链表HL中的n个结点按值进行排序。说明：1）具体方法是：先建立一个空的单链表，然后向空链表中逐个插入原单链表HL中的结点，得到一个有序的单链表。最后由HL带回新单链表的表头指针。2）由于每插入一个结点，平均操作次数为(n+1)/2，因此插入n个结点，平均操作次数为n*(n+1)/2，故该算法的时间复杂度量级为O(n2)。,顺序表与单链表之比较,顺序表单链表存贮空间要求分配一块不要求存贮要求连续存贮空间空间连续结点结构无结点结构，只由每个结点包括：数组存储元素的值值域和指针域表的结构顺序表L为List结构单链表HL实际上类型，包括两个成员：是一个表头指针，数组list和表长size类型为LNode*特点适于访问一个元素，适于插入、删除不适宜插入、删除,顺序表单链表GetListO(1)O(n)InsertListO(n)O(n)要向后移动元素不需移动元素，故可节约时间。DeleteListO(n)O(n)要向前移动元素不需移动元素，故可节约时间。,线性表、顺序表和单链表是何种关系,线性表是一种逻辑结构。表中各元素之间是线性关系，即只有一个前驱，一个后继。线性表在计算机中的存储方式线性表的物理结构。线性表常见的两种物理结构：1)各元素存储位置连续，并保持逻辑顺序顺序存储结构顺序存储的线性表叫做顺序表2)各元素存储位置可以分散，通过指针来连接链接存储结构链接存储的线性表叫做单链表,测试题：,在一个表头指针为ph的单链表中，若要向表头插入一个由指针p指向的新结点，应执行p-next=ph;ph=p;操作。在一个表头指针为ph的单链表中，若要在指针q所指结点的后面插入一个由指针p所指向的新结点，应执行p-next=q-next;q-next=p;操作。在一个单链表中删除指针p所指向结点的后继结点时，需要把p-next-next的值赋给p-next指针域。若经常需要对线性表进行插入和删除运算，则最好采用链接存储结构，若经常需要对线性表进行查找运算，则最好采用顺序存储结构。访问一个顺序表和一个单链表中第i个元素的时间复杂度的量级分别为O(1)和O(n)。对于一个单链接存储的线性表，在表头插入结点的时间复杂度为O(1)，在表尾插入结点的时间复杂度为O(n)。,火车售票系统的简单设计方案,基本要求：假设所有出售的车票均为同一车次；假设每张车票的信息只有：车次号、座位号退票时，只有本车站售出的车票才能退，否则视为无效票，不能退。,火车售票系统的简单设计方案,算法设计：为每张车票建立一个结点，则所有待出售车票建立起一个单链表。structLNodechartrain_num4;/车次号elemtypedata;/座位号LNode*next;,火车售票系统的简单设计方案,算法设计：售票从单链表中删除一个结点，为提高效率，删除表头结点。退票先判断是否有效票，有效则插入一个结点，插入到表头。查询依次将单链表中所有结点的信息输出，并统计结点数，即余票量。,火车售票系统的复杂方案,算法设计：设计一个struct结构，包含上述信息。其中，座位号是单链表或数组类型。整个售票系统可设计为顺序表，表中每个元素即如上一条记录信息。售票用户输入车次号和购票数n，程序按车次号查找到相应的记录，若余票量=购票数n，则从座位号中删除n个结点，修改余票量。,火车售票系统的复杂方案,算法设计：退票用