数据结构第二章-线性表(00002)课件.ppt
第二章 线性表数据结构本章主要内容l 线性表的定义和基本操作l 线性表的顺序存储和相关操作l 线性表的链式存储和相关操作1、线性表的定义 线性表（Linear_List）简称为表，是n（n0）个数据元素（也叫结点或表元素）组成的有限序列，其特点是各数据元素之间存在着线性关系，即都是一个接一个的按一定顺序排列的,并且线性表要求同一个表中的各数据元素的结构类型必须完全一致。例如：（a1,a2,a3,ai-1,ai,ai+1,an-1,an）即为一个线性表，表中ai-1领先于ai，称ai-1是ai的直接前驱元素，ai+1是ai的直接后续元素。当i=1，2，3，n-1 时，ai有且仅有一个直接后继；当i=2，3，4，n 时，ai有且仅有一个直接前驱。1、线性表的定义表的长度：线性表中元素的个数n（n0）为线性表的长度；空表：n=0 的时候称该线性表为空表；位序：非空线性表中ai 是第i（1in）个数据元素，称i 为数据元素在线性表中的位序；数据元素：组成线性表的数据元素是一个个的数据项，这种数据项可以是初等项，也可以是组合项；2、线性表的顺序存储 线性表的顺序存储是指用 一组地址连续的存储单元 一组地址连续的存储单元按线性表元素之间的逻辑顺序，依次存储线性表的数据元素。数据元素的 逻辑顺序 逻辑顺序和物理上的存储顺序是完全一致的，物理上存放在位置i 的元素，就是按照逻辑顺序存储时的第i 个元素。顺序存储的线性表是一种 随机存取结构 随机存取结构，只要确定了存储线性表的起始位置，就可以随机存取表中的任何一个数据元素。2、线性表的顺序存储用C语言的一维数组来定义线性表的顺序存储结构：#define MAXSIZE 100/定义一个线性表的最大长度Typedef struct elemtype elemMAXSIZE;/定义一个存放数据元素的一维数组，元素类型elemtype根据实际需要确定 int len;/线性表的当前长度SQLIST2、线性表的顺序存储a1a2 ai anL.Len MAXSIZE设SQLIST L；则L 为如上定义的顺序表，表中含有L.len 个数据元素，依次存储在L.elem0 至L.elemL.len-1 中，如下图所示。其中L.leni-1 的值即为线性表中的第i 个数据元素；该顺序表最多可容纳MAXSIZE 个数据元素；elemtype 为线性表中数据元素所属类型。3、顺序表的基本操作(2).插入操作 插入操作需要注意的问题 顺序表中数据区域分配有MAXSIZE 个存储单元，做插入操作时需要先检查表空间是否已满，表满的情况下不能再做插入操作，否则会产生内存溢出错误。要检查插入位置的有效性，这里i 的有效范围是1in+1，其中n 为原表长度。注意数据移动的方向为向大的下标出移动，如下页图表所示：3、顺序表的基本操作0a1a101a2a21i-2ai-1ai-1i-2i-1aiei-1iai+1aiiai+1i+1n-1anannMAXSIZE-1 MAXSIZE-1(a)插入前(b)插入后3、顺序表的基本操作(2).插入操作 算法实现int Insert_SeqList(SeqList*L,int I,datatype e)int j;if(L-len=MAXSIZE-1)printf(“表满将溢出”);/表空间已满的情况，不允许插入return-1;if(iL-len+2)/检查插入位置i 是否有效 printf(“插入位置出错”);return 0;3、顺序表的基本操作(3).删除操作 删除操作需要注意的问题 删除第i 个元素是，要删除的元素必须真实存在，所以需要检查i 的取值是否有效，i 的有效取值范围为1in，否则操作失败。表为空表的时候不能执行删除操作。注意数据移动的方向为向小的下标出移动，如下页图所示：3、顺序表的基本操作0a1a101a2a21i-2ai-1ai-1i-2i-1aiai+1i-1iai+1 ann-2n-1anMAXSIZE-1 MAXSIZE-1(a)删除前(b)删除后3、顺序表的基本操作L-len-;return 1;/删除成功 算法时间复杂度3、顺序表的基本操作(4).按值查找算法思路：从第一个元素a1开始依次将顺序表中的元素ai与e相比较，直到找到一个与e相等的数据元素，返回这个数据元素在表中的位置；若查找不到与e相等的数据元素，则返回-1，表示查找失败。int Locate_SeqList(SeqList*L,datatype e)int i=0;while(idatai!=e)i+if(iL-len)return-1;/没有查找到目标元素elsereturn i;/查找到目标元素，返回其位置下标3、顺序表的基本操作(5).取顺序表中元素算法思路：首先确认所查找数据元素序号是否合法，若合法则直接返回对应元素值，否则操作失败。int Get_SeqList(SeqList*L,int i)if(iL-len+1)/检验查找位置i是否有效 printf(“没有第i个元素”);return-1；elsereturn L-datai-1;4、线性表的链式存储 链式存储结构 不需要逻辑上相邻 不需要逻辑上相邻的两个数据元素（例如ai和ai+1）在物理存储上也相邻，因此不需要划拨一块连续的存储空间来做线性表的物理存储介质。在链表中数据元素之间的逻辑关系通过指针来指示，因此对线性表的插入、删除等操作时 不需要移动数据元素 不需要移动数据元素，而是用修改链指针方式即可实现。链式存储也有其自身的弱点，它 失去了顺序表可随机存取 失去了顺序表可随机存取元素的优势。4、线性表的链式存储链表是由若干个节点构成的，定义节点的代码如下：typedef struct node datatype data;Struct node*next;LNode,*LinkList;定义头指针变量为LinkList H;4、链式表的基本操作(1).建立单链表 头插法建立单链表LinkList Creath_LinkList()LinkList L=NULL;/建立空链表LLnode*s;int e;/设数据元素的类型为intscanf(“%d”,&e);whil(e!=flag)/flag 为结束标志，可以为#等 s=malloc(sizeof(LNode);s-data=e;s-next=L;L=s;4、链式表的基本操作scanf(“%d”,&e);return L;头插法建单链表实例（读入顺序35，48，28，67，59）4、链式表的基本操作 尾插法建立单链表LinkList CreatLinkList()LinkList L=NULL;/定义一个空表LNode*s,*r=NULL;/定义新节点指针和尾指针int e;/定义数据元素类型为intscanf(“%d”,&e);while(e!=flag)/flag 为设定的录入结束符 s=malloc(sizeof(LNode);s-data=e;if(L=NULL)L=s;/插入的节点是第一个节点else4、链式表的基本操作(2).求单链表长算法思路：设指针变量p 和计数器变量i，当p 所指向的节点还有后继节点时，p 向后移动，同时计数器自加1，一直到p 指向链表的最后一个节点。带头结点的表长求解int Length_LinkList1(LinkList L)/当链表带头节点时 LNode*p=L;/p 指向头节点int i=0;/设计数器iwhile(p-next)p=p-next;/p 指针依次后移i+;return i;4、链式表的基本操作 不带头结点的表长求解int Length_LinkList2(LinkList L)/当链表不带头节点时 LNode*p=L;int i;/设计数器iif(p=NULL)return 0;/为空表，返回0i=1;/非空表，p 指向第一个节点while(p-next)p=p-next;i+;return I;注意：为了处理方便，在后面编写的算法中若不加额外说明则认为单链表都是带头节点的。4、链式表的基本操作 按值查找从链表的第一个节点起，如果当前节点的数据域的值与给定参数e 相等，则返回该节点的地址指针，否则沿着指针域依次向下寻找，直到表结束为止。若表中没有符合要求的节点，则返回空。LNode*Locate_LinkList(LinkList L,datatype e)LNode*p=L-next;while(p!=NULL&p-data!=e)p=p-next;return p;4、链式表的基本操作(4).插入操作插入节点的问题首先是一个查找问题，找到之后就是进一步确定是插入到找到的节点前面还是后面的问题了。在节点之后插入插入代码如下：s-next=p-next;p-next=s;注意：这两条指令的先后顺序不能互换，否则会是链表断开，从而无法准确的完成新节点插入操作。4、链式表的基本操作 在节点之前插入插入代码如下：q=L;while(q-next!=p)q=q-next;/查找*p 的直接前驱节点s-next=q-next;q-next=s;要完成此操作，首先需要找到*p 的直接前驱*q，然后再在*q之后插入*s即可4、链式表的基本操作(5).删除操作要实现对节点*p 的删除操作，首先要找到*p 的直接前驱节点*q，然后将其指向后继的指针做修改即可。指针的修改操作代码语句如下：q-next=p-next;free(p);如果想要删除的是*p 的直接后继节点（假设存在），则可以通过下列代码语句来完成：s=p-next;p-next=s-next;free(s);5、实战练习请编程实现通讯录管理功能，包括通讯的建立、新增通讯者、删除通讯者、通讯者的查询以及通讯录的输出等。为了实现通讯录管理的集中操作功能，首先设计一个含有多个菜单项的主控菜单程序，然后再为这些菜单项配上相应的功能。要求程序运行后，给出6个菜单项的内容和输入提示：1.通讯录链表的建立2.通讯者节点的插入3.通讯者节点的查询4.通讯者节点的删除5.通讯录链表的输出0.退出管理系统使用数字0-5来选择菜单功能，其他输入则不起作用。
