第2章线性表辅导.doc

第2章 线性表辅导 本章通过实例给出线性表的定义，介绍线性表的逻辑结构、顺序存储结构和链式存储结构，讨论线性表在两种不同存储结构下对应的顺序表和链表的相关操作，介绍线性表的简单应用。 通过本章学习，要求同学们： 1.掌握线性表的定义和逻辑结构。 2.掌握线性表的顺序存储结构的有关概念，能利用C语言的数组和指针实现对顺序表的相关操作。 3.掌握线性表的链式存储结构的有关概念，并重点掌握单向链表的特点和访问方式，能利用C语言的结构变量和指向结构体的指针实现对链表的相关操作。 4.正确理解线性表两种存储结构各自的特点和应用场合，能利用所学知识和按照相关要求设计算法、编制程序，利用线性表解决简单的应用问题。 一、本章知识点 1. 线性表的定义及特点 线性表是一种最简单、最常用的一种数据结构。线性表中的元素存在着一对一的相互关系。 线性表是n（n≥0)个数据元素的有限序列。其中n为数据元素的个数，定义为数据表的长度。当n为零时的表称为空表。当n0时，一般将线性表记为：（a1,a2,…ai-1,ai,…an），其中ai（i=1,2,3,…,n)a1，存在称作“最后一个”的数据元素，例如上表中的an。 2.表中第一个元素a1前面没有元素和它相邻，称它没有直接前驱，它后面有且只有一个元素a2与它相邻，称它有且只有一个直接后继。而表中“最后一个”元素an有且只有一个直接前驱an-1，没有直接后继。 3．除“第一个”元素和“最后一个”元素外，其它每个元素均有且只有一个直接前驱和一个直接后继。 2.线性表的顺序存储结构 用一组地址连续的存储单元依次存放线性表的数据元素，该结构的特点是逻辑上相邻的数据元素在物理上也相邻，可以随机访问，一对一的关系。 用顺序存储结构存储的线性表称为顺序表 3.顺序表的操作 （1）插入操作 插入操作的算法步骤为：从an开始逐次将an，an-1.，…, ai向后平移一个存储位置，然后将x存入到a[i]中。 若有n个元素的顺序表，在第i个元素之前插入，也即插入元素作为第i个元素。有下列四种情况： 当i=1时移动元素次数为n； 当i=n+1时，移动元素次数为0； 一般情况下，移动元素的次数为n-i+1； 等概率情况下平均为n/2。 （2）删除操作 在线性表A=（a1,a2,…ai-1,ai,ai+1,…an）中删除第i个元素ai（1i≤n),删除后线性表长度为n-1，删除后的线性表为A=（a1,a2,…ai-1,ai+1,…an）。 上述操作的算法步骤为：逐次将ai+1,ai+2,…an个元素向前平移一个存储位置，使后面的数据元素逐次覆盖它的直接前驱。有下列四种情况： 当i=1时，移动元素次数为n-1； i=n时，移动元素次数为0； 一般情况下，移动次数n-i； 等概率平均情况（n+1）/2。 插入、删除的基本操作为元素移动，时间复杂度为O（n)。 4．线性表的链式存储结构 （1）链表的概念 用链式存储结构存储的线性表称为链表。链表就是把线性表中的每个元素的值和该表中下一个元素的地址放在一起，这两部分信息组成一个结点，若干个这种结点构成了线性链表。 链表的特点是：用于存储线性表数据元素的存储单元不一定是连续的，线性表的逻辑关系则是利用指针来体现。链表不能随机访问。 （2）单向链表 单向链表中每个由数据域和指针域两部分组成，结点形式如下： data next 其中，data部分称为数据域，用于存储线性表的一个数据元素，next部分成为指针域，或链域，用于存放一个指针该指针指向本结点所含数据元素的直接后继所在的结点。 在单向链表中，第一个结点的存储位置称为头指针，程序中通常用一个指针变量存储头指针。本章命名该指针变量为head。最后一个数据元素an没有直接后继，所以链表中最后一个结点的指针域存放的是空指针（NULL）。单向链表的逻辑结构如下图所示。 设置头结点的好处是：（1）便于处理首结点（指头结点后面的第1个结点，即头结点的后继结点）使得在创建链表和删除结点时，可以将首结点与其他结点同等对待。对于不带头结点的链表，在进行插入删除操作时，需要每次对首结点进行判断，这样十分繁琐。（2）可利用头结点的数据域存储链表的相关信息，如链表的长度，这样可以不需要通过遍历整个链表获得信息，提高算法的效率。 在C语言中，可以用“结构变量”存储结点的信息，用“结构指针变量”存储头指针。本课程的文字教材中设线性表的数据元素为整数，则结构体类型定义如下： struct node { int data; struct node *next; } typedef struct node NODE; 5．建立单链表 （1）尾插法 尾插法建立链表是逐次生成的新结点总是作为当前链表的尾结点插入。 用尾插法建立带头结点且