《线性表的基本操作.ppt》由会员分享，可在线阅读，更多相关《线性表的基本操作.ppt（67页珍藏版）》请在三一办公上搜索。
1、1,第二章 线性表,线性表的定义、逻辑结构特点及基本运算线性表的顺序存储及基本运算线性表的链式存储及基本运算数组的逻辑结构定义及其存储方式线性表的应用,2,线性表的定义及特点,线性表n(n0)个具有相同特性的数据元素的有限序列其中n表示线性表的长度，即数据元素的个数n=0时表为空表n0时记为:（a1,a2，ai-1，ai，ai+1，an）基本特征有且只有一个“第一元素”，有且只有一个“最后元素”除第一元素之外，其它元素都有唯一的直接前趋除最后元素之外，其它元素都有唯一的直接后继,3,元素的含义,数据元素在不同问题中的含义各不相同可以是一个数、一个符号，一个记录，或其它更复杂的信息这里的学生成绩
2、表是一个线性表数据元素是每一个学生的信息，包括：学号、姓名、成绩共三个数据项,数据元素,4,线性表上常用的的运算,基本运算初始化线性表表置空求线性表中第i个元素查找满足给定条件的数据元素在线性表的第i个位置之前插入一个新的数据元素删除线性表中的第i个数据元素查找表中第i个元素的前驱查找表中第i个元素的后继按一个或多个数据项值的递增或递减次序重新排列线性表中的数据元素实际应用中，根据不同的要求选择适当的基本运算解决问题,5,ADT抽象数据类型对数据的定义对关系的定义对运算的定义D,S,PD:数据集合S:关系集合P:操作的集合通过固有数据类型来实现,抽象数据类型,6,ADT triplet数据对象
3、:D=V1,V2,V3数据关系:R=,基本操作:initriplet(&T,n1,n2,n3)操作结果:构造了三元组T,对元素V1,V2,V3分别赋以n1,n2,n3的值max(T,&e)初始条件:三元组T已经存在操作结果:找出数据元素的最大值,用e返回ADT triplet,7,线性表的实现-顺序存储结构,在内存中开辟连续的存储空间，用连续的存储单元依次存放线性表的数据元素顺序存储的线性表，称为顺序表,特点逻辑上相邻的数据元素，其物理位置也相邻利用物理位置上的关系，反映元素的逻辑关系,8,20个学生的线性表，试用顺序表来存储这些信息typedef struct char name9;char
4、 no8;float score STUDENT；STUDENT s20;,在C语言中可借助数组实现若每个元素占m个存储单元第i+1个和第i个元素的存储位置满足如下关系：LOC(ai+1)=LOC(ai)+m第i个和第一个元素的存储位置满足如下关系LOC(ai)=LOC(a1)+(i-1)*mLOC(a1)是线性表的起始地址取a1和ai的时间是相同的是一种随机存取的存储结构,9,顺序表的类型定义,#define MAXSIZE maxlen/maxlen表示线性表可能的最大数据元素数目typedef int elemtype;/elemtype表示数据元素类型，此处定义为inttypedef
5、struct elemtype vMaxsize;/存放线性表元素的数组 int len;/表示线性表的长度sqlist;/sqlist是数据类型的名称/sqlist是一种新的，自定义的数据类型/这种类型就是顺序表类型,10,顺序表的类型定义,两种使用方法sqlist L;L.viL.lensqlist*sq;sq=(sqlist*)malloc(sizeof(sqlist);sq-visq-len,#define MAXSIZE maxlen typedef int elemtype;typedef struct elemtype vMaxsize;int len;sqlist;,11,顺序
6、表的示意图,12,顺序表的基本运算,#define maxsize 1024/顺序表的最大长度typedef int datatype;/定义表元素类型typedef struct/定义顺序表类型datatype datamaxsize;int len;sqlist;void main()sqlist*L;/定义指向顺序表的指针 L=(sqlist*)malloc(sizeof(sqlist);initlist(L);/构造一个空的顺序表;free(L);,初始化:构造空顺序表void initlist(sqlist*L)L-len=0;算法时间复杂度：O(1),13,顺序表上的基本运算,插入
7、算法在线性表的第i个数据元素前，插入一个新数据元素，使线性表的长度从n变成n+1(a1,ai-1,ai,an)(a1,ai-1,x,ai,an),14,x,15,顺序表的插入算法,判断线性表的存储空间是否已满，若已满，则进行“溢出”处理检查i值是否超出允许的范围(1ilen+1)，若超出，则进行“超出”处理如果上述条件都允许,则将最后一个元素到第i个元素依次向后移动一个位置将新的数据元素写到第i个位置上线性表的长度增加1,插入成功,int insert(sqlist*L,int i,elemtype x)；,16,插入算法的时间复杂度,插入算法的主要时间用于移动数据元素，该语句循环执行的次数为
8、n-i+1当i=n+1时，移动次数为0当i=1时,移动次数为n算法的最坏情况时间复杂度：O(n)算法的最好情况时间复杂度：O(1),17,插入算法的时间复杂度,假设在第i个元素之前插入一个元素的概率为Pi，所需移动数据元素的平均次数为：,18,顺序表上的基本运算,删除操作将线性表的第i个数据元素删去，使长为n的线性表变成长为n-1的线性表(a1,.,ai-1,ai,ai+1,.,an)(a1,.,ai-1,ai+1,.,an),19,20,顺序表的删除算法,算法思路判断i值是否超出允许的范围(1ilen），若是，则进行“超出范围”处理；否则，保存第i个元素的值；将第i个元素后的所有元素依次向前
9、移动一个位置；线性表长度减1，删除成功int delete(sqlist*L,int i,elemtype*y)；,21,删除算法的时间复杂度,删除算法的主要时间用于移动数据元素，该循环语句执行的次数为n-i当i=1时，移动n-1 个当i=n时，不需移动算法的最坏情况时间复杂度：O(n)算法的最好情况时间复杂度：O(1),22,删除算法的时间复杂度,设删除第i个元素的概率为qi，所需移动数据元素的平均次数为：,23,顺序表的基本运算,求线性表的长度 int lenth(sqlist*L)int len;len=L-len；return(len);/返回线性表的长度,24,顺序表上的基本运算,查
10、找查找指定数据元素x在表中的位置序号，若vi=x,则算法返回值为i+1，若不存在数据元素x，则返回0,25,顺序存储结构的优缺点,静态操作容易实现根据定位公式容易确定表中元素的存储位置元素随机存取,动态操作实现效率较低插入和删除结点困难由于表中的结点连续存放，在动态操作时，为了保持元素的连续性，所以必须将某些结点向后或向前依次移动扩展不灵活，容易造成空间浪费建表时，若估计不到表的最大长度，就难以确定分配的空间，影响数据扩展分配的空间过大，则会造成预留空间浪费,26,作业,编写完整的源程序实现顺序表的插入,删除算法.P21,综合题5，6，7,27,线性表的链式存储结构,链表以链式结构存储的线性表
11、用一组在物理位置上任意的存储单元来存储线性表的结点存储单元可以是相邻的也可以是不相邻的相邻存储单元中的数据，不一定是相邻的结点物理位置上的关系不能反映结点间的逻辑关系,28,线性表的单链存储示意图,7,15,54,40,NULL,29,链式存储结构的特点,用一组任意位置的存储单元存储线性表的数据元素结点间的逻辑关系借助结点中的指针实现每个数据元素，除存储本身信息外，还需存储其直接后继的信息结点数据域：元素本身信息指针域：指示直接后继的存储位置,30,单链表,链表中，每个结点只包含一个指针域结点类型的C语言描述：typedef char elemtype;typedef struct node
12、elemtype data；struct node*next;Lnode，*linklist;Lnode*L;与 linklist L;等价L可作为单链表的头指针，指向链表的第一个结点若L=NULL，表示单链表为空表，长度为0,31,带头结点的单链表,在单链表的第一个结点前添加一个辅助结点，称为头结点或伪结点头结点的数据域可以不存储任何信息，也可以存储一些附加信息；头结点的指针域存储链表首结点的地址如果头结点的指针域为“空”，即L-next=NULL，表示该链表为空表,32,单链表的使用注意事项,linklist h,p;Lnode*h,*p;p=(Lnode*)malloc(sizeof(L
13、node);此时,P和对象之间的关系:,(*p)表示p所指向的结点(*p).datap-data：P所指向结点的数据域(*p).nextp-next：P所指向结点的指针域,typedef struct node elemtype data;struct node*next;Lnode,*linklist;,33,头插法建立单链表,算法思路1.建立一个头结点，使头结点的指针域为空2.建立一个新结点P,作为待插入的新结点3.给新结点P的数据域赋值4.将新结点插入到头结点的后面，成为第一个数据结点5.是否继续？如果继续，返回2，否则跳到66.结束创建,创建成功,34,typedef char ele
14、mtype;typedef struct node elemtype data；struct node*next;Lnode;#define LEN sizeof(Lnode)/定义结点长度Lnode*creat()Lnode*p,*head;head=(Lnode*)malloc(LEN);/头结点 head-next=NULL;.,35,while(1)/创建新链表 p=(Lnode*)malloc(LEN);/申请一个新结点 scanf(“%c”,36,尾插法创建单链表的算法,算法思路1.申请一个结点的空间，作为头结点2.申请一个结点的空间，作为待插入的新结点3.给新结点的数据域赋值，将
15、新结点插入到链表尾，使其成为新的尾结点,其指针域为NULL4.是否继续？如果继续，返回2，否则跳到55.结束创建,创建成功,37,typedef char elemtype;typedef struct node elemtype data；struct node*next;Lnode;#define LEN sizeof(Lnode)/定义结点长度Lnode*creat()Lnode*p,*tail,*head;tail=head=(Lnode*)malloc(LEN);/头结点 head-next=NULL;.,38,while(1)/创建新链表 p=(Lnode*)malloc(LEN)
16、;/申请一个新结点 scanf(“%c”,39,求单链表的长度的算法,求表中元素的个数算法思想计数器清0令指针p=head-next让指针P沿着链表的指针域向前移动,每移动一步,计数器增1当指针P 为空,表示已经到了链表尾此时,计数器中就是结点个数时间复杂度：O(n),40,单链表的插入算法,插入点,q,p,p-next=q-next;q-next=p;,插入数据不需进行大量数据移动，只需找到插入点即可,41,算法 在单链表的第i个结点后，插入值为item的结点,算法思想寻找第i个结点,即插入点如果找不到插入点,插入位置不合适,无法插入,返回FALSE如果找到插入点,则进行插入操作申请新结点新
17、节点数据域置为item插入新节点操作成功，返回TRUE.int insert(Lnode*h,int i,elemtype x);,42,删除算法,删除数据：删除某个结点算法思想,P,结点i,结点i-1,q,43,删除算法,算法思路：将q指向p结点的直接后继；改变指针链接，把q结点的直接后继作为p结点的直接后继；从单链表中删除q结点；释放q结点空间。,44,删除单链表上的第i个结点算法思想如果是空表,无法删除,返回FALSE 如果不是空表,则找第i-1个结点如果该结点不存在,无法删除,返回FALSE如果第i-1个结点存在,则找第i个结点如果第i个结点不存在,无法删除,返回FALSE如果第i个节
18、点存在,则删除,返回TRUEint delete(Lnode*head，int i);,删除算法,45,int delete(Lnode*head，int i)Lnode*p,*q;int j=1;p=head-next;if(p=NULL)/空表，无法删除 return 0;while(p/q指向第i个结点,p-next=q-next;free(q);return 1;算法的时间复杂度是O(n),46,按值查找算法,查找单链表中是否存在数据域为x的结点。若有该结点，则返回指向该结点的指针，否则返回空算法思路从第一个结点开始扫描整个单链表，逐个比较数据域值和x找到该结点后返回指向该结点的指针,
19、47,读取线性表中指定位置的元素,读取单链表中的第i个元素。如果找到，则返回第i个结点的存储地址，否则返回空 算法思路(1)p从单链表的第一个结点出发，并定义j=1(2)在单链表中移动指针p，同时累计j(3)通过j的累计查找j=i的结点(4)重复(2)、(3)直到p为空或p指向第i个元素Lnode*get(Lnode*h,int i);,48,单链表特点,是一种动态结构，不需预先分配空间指针占用额外存储空间不能随机存取，而是顺序存取适合做动态操作带头结点的单链表很多时候可以使算法简化,49,循环链表,单循环链表单链表中最后一个结点的链域值不是NULL，而是指向头结点，整个表形成一个环 特点从表
20、中任意结点出发均可找到表中其它的结点操作与单链表基本一致,循环条件不同带头结点的单链表：p-next=NULL带头结点的单循环链表：p-next=head,50,创建单循环链表循环链表是对单向链表的一种改善。单链表中尾结点的next=NULL，只需把尾结点的next域设置为头结点的地址，就能够获得一个循环链表。,int initclist(Lnode*head)head=(Lnode*)malloc(sizeof(Lnode);head-next=head;return 1;,单循环链表的操作一,51,判断单循环链表是否为空只需看头结点的next域是否等于头指针int isempty(Lnod
21、e*head)if(head-next=head)return 1;else return 0;本算法时间复杂度为O(1)。,单循环链表的操作二,52,遍历单循环链表从首元节点开始，逐个访问链表结点,直到链表尾void view(Lnode*head)Lnode*p=head-next;while(p!=head)putchar(p-data);p=p-next;算法时间复杂度为O(n),单循环链表的操作三,53,双向链表,每一个结点中有两个指针域一个指向直接后继另一个指向直接前趋这样的链表称为双向链表结点描述如下:typedef struct dulnode elemtype data;st
22、ruct dulnode*next,*prior;dulnode;,54,双向循环链表,将双向链表中的头结点和尾结点链接起来，构成双向循环链表,55,双向循环链表,在双向环形链表中，指针p指向双向链表中的某结点，则有如下关系p-next-prior pp-prior-next p双向链表的对称性,56,在双向循环链表结点p之前插入结点s,改变指针链接的语句有 s-prior=p-prior;p-prior-next=s;s-next=p;p-prior=s;,双向循环链表的插入算法,57,双向循环链表的插入算法,在双向循环链表的第i个结点之前插入值为x的新结点。如果成功，返回1，否则，返回0。
23、算法思路通过p的移动在双向链表中查找第i个元素如果找到，则建立一个新结点s 将s和p以及p的前驱链接起来使s的前驱是p原来的前驱s的后继是p,58,双向循环链表的删除算法,删除双向环形链表的结点p,改变指针链接的语句有p-prior-next=p-next;p-next-prior=p-prior;,59,双向循环链表的删除算法,删除双向环形链表的第i个结点p。如果成功，返回1，否则，返回0。算法思路通过p的移动在双向链表中查找第i个元素如果找到，改变指针链接使p的前驱指向p的后继p的后继结点的前驱指针指向p原来的前驱释放p,60,线性表顺序存储与链式存储的比较,从时间的角度在按位置查找数据，
24、或在查找元素的前趋和后继等方面，顺序存储有着较大的优势。在插入数据、删除数据时，链式存储有较大的优势.因为在链表中只要修改指针即可做到；而在顺序表中则平均要移动将近一半的数据元素从空间的角度顺序表的存储空间是静态分配的，在程序执行之前必须规定其存储规模。动态链表的存储空间是动态分配的，只要内存空间有空闲，就不会产生溢出。,61,线性表的顺序存储和链式存储在操作上的比较,62,线性表的应用,顺序表的原地逆置链表的原地逆置链表合并多项式求和,63,本节学习要点,了解顺序表、链表的概念、含义、区别。熟练掌握这两类存储结构的描述方法。熟练掌握线性表在顺序存储结构上实现基本操作查找、插入和删除的算法。熟
25、练掌握在各种链表结构中实现线性表操作的基本方法能够综合比较线性表两种存储结构的不同特点及其适用场合能在实际应用中选用适当的链表结构,64,作业,学习指导书:2.2.2 综合题1、3、4、6、7、9、13、17、18、20、24、26 实验内容:实验二:3、6、13,65,练习题,线性表若采用链式存储结构时，要求内存中可用存储单元的地址_A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续不连续都可以,D,66,下面程序的时间复杂度是？i=s=0;while(in)i+;s+=i;,练习题,O(n),下面程序的时间复杂度是？for(i=0;in;i+)for(j=0;jm;j+)aij=0;,O(m*n),67,exercise,void main()sqlist*L;int pos=2;L=(sqlist*)malloc(sizeof(sqlist);initlist(L);.;insert(L,pos,87);destroy(L);,#define Maxsize 1024;typedef int elemtype;typedef struct elemtype vMaxsize;int len;sqlist;,int insert(sqlist*L,int i,elemtype x)；,
