数据结构第二章-线性表(00002)课件.ppt

《数据结构第二章-线性表(00002)课件.ppt》由会员分享，可在线阅读，更多相关《数据结构第二章-线性表(00002)课件.ppt（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章 线性表数据结构本章主要内容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有且仅有一个直接后继；当

2、i=2，3，4，n 时，ai有且仅有一个直接前驱。1、线性表的定义表的长度：线性表中元素的个数n（n0）为线性表的长度；空表：n=0 的时候称该线性表为空表；位序：非空线性表中ai 是第i（1in）个数据元素，称i 为数据元素在线性表中的位序；数据元素：组成线性表的数据元素是一个个的数据项，这种数据项可以是初等项，也可以是组合项；2、线性表的顺序存储 线性表的顺序存储是指用 一组地址连续的存储单元 一组地址连续的存储单元按线性表元素之间的逻辑顺序，依次存储线性表的数据元素。数据元素的 逻辑顺序 逻辑顺序和物理上的存储顺序是完全一致的，物理上存放在位置i 的元素，就是按照逻辑顺序存储时的第i 个

3、元素。顺序存储的线性表是一种 随机存取结构 随机存取结构，只要确定了存储线性表的起始位置，就可以随机存取表中的任何一个数据元素。2、线性表的顺序存储用C语言的一维数组来定义线性表的顺序存储结构：#define MAXSIZE 100/定义一个线性表的最大长度Typedef struct elemtype elemMAXSIZE;/定义一个存放数据元素的一维数组，元素类型elemtype根据实际需要确定 int len;/线性表的当前长度SQLIST2、线性表的顺序存储a1a2 ai anL.Len MAXSIZE设SQLIST L；则L 为如上定义的顺序表，表中含有L.len 个数据元素，依次

4、存储在L.elem0 至L.elemL.len-1 中，如下图所示。其中L.leni-1 的值即为线性表中的第i 个数据元素；该顺序表最多可容纳MAXSIZE 个数据元素；elemtype 为线性表中数据元素所属类型。3、顺序表的基本操作(2).插入操作 插入操作需要注意的问题 顺序表中数据区域分配有MAXSIZE 个存储单元，做插入操作时需要先检查表空间是否已满，表满的情况下不能再做插入操作，否则会产生内存溢出错误。要检查插入位置的有效性，这里i 的有效范围是1in+1，其中n 为原表长度。注意数据移动的方向为向大的下标出移动，如下页图表所示：3、顺序表的基本操作0a1a101a2a21i-

5、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 个元素

6、是，要删除的元素必须真实存在，所以需要检查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相等的数据元素，返回这个数

7、据元素在表中的位置；若查找不到与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个元素”

8、);return-1；elsereturn L-datai-1;4、线性表的链式存储 链式存储结构 不需要逻辑上相邻 不需要逻辑上相邻的两个数据元素（例如ai和ai+1）在物理存储上也相邻，因此不需要划拨一块连续的存储空间来做线性表的物理存储介质。在链表中数据元素之间的逻辑关系通过指针来指示，因此对线性表的插入、删除等操作时 不需要移动数据元素 不需要移动数据元素，而是用修改链指针方式即可实现。链式存储也有其自身的弱点，它 失去了顺序表可随机存取 失去了顺序表可随机存取元素的优势。4、线性表的链式存储链表是由若干个节点构成的，定义节点的代码如下：typedef struct node data

9、type 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;头插法建单链表实例

10、（读入顺序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 向后

11、移动，同时计数器自加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

12、=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).插入操作插入节点的问题首先是一个查找问题，找到之后

13、就是进一步确定是插入到找到的节点前面还是后面的问题了。在节点之后插入插入代码如下：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，然后将其指向后继的指针做修

14、改即可。指针的修改操作代码语句如下：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来选择菜单功能，其他输入则不起作用。