《数据结构-幻灯片-链表部分》由会员分享，可在线阅读，更多相关《数据结构-幻灯片-链表部分（59页珍藏版）》请在金锄头文库上搜索。
1、回顾上次课内容,数据结构的相关概念 数据的存储结构,逻辑结构 存储结构,集合 线性结构 树形结构 图状结构或网状结构,顺序存储结构 链接存储结构,算法分析方法,第二章 线性表,主要内容： 线性表的类型定义 线性表的顺序表示和实现 线性表的链式表示和实现 线性表的应用举例,线性结构的特点,存在惟一的一个开始结点，称做“第一个”的数据元素 存在惟一的一个终端结点，称做“最后一个”的数据元素 除第一个外，每个数据元素只有一个前驱 除最后一个外，每个数据元素只有一个后继,1.描述: 线性表是由n (n=0)个数据元素(结点)a1,a2,.,ai,.,an组成的有限序列。其中，数据元素的个数n定义为表长
2、。当n=0时称为空表，非空的线性表(n0)记为： (a1,a2,.,ai,an),一、逻辑结构, 注意: 1.数据元素ai是一个抽象的符号 2. ai可取各种数据类型 3. 同一线性表中的元素必定具有相同的特性，属于同一数 据对象 4. 相邻数据元素之间存在序偶关系 5. i是数据元素ai在线性表中的位序 (1i n),2.逻辑特征：仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个前驱和一个后继,线性表是一个线性结构,2.1 线性表的类型定义,二、抽象数据类型线性表的定义 ADT List 数据对象：D=aiai Elemset, i=1,2,n , n0 数据关系：R1= ai-1
3、 , ai D, i=2, ,n 基本操作： 构造、销毁、置空、判空、获取元素、插入、删除、定位等。 ADT List a1是第一个元素，有且仅有一个直接后继元素a2； an是最后一个元素，有且仅有一个直接前趋元素an-1 ； 其余ai(1in)有且仅有一个直接前趋ai-1，有且仅有一个直接后继ai+1,顺序表示（存储）：指在内存中用地址连续的一块存储空间顺序存放线性表的各元素，用这种存储形式存储的线性表称其为顺序表。,线性表顺序存储结构示意图,2.2 线性表的顺序表示和实现,数据元素存储位置表示 设 a的存储地址为Loc(a)，每个数据元素占l个存储地址，则第i个数据元素的地址为： Loc(
4、ai)=Loc(a)+(i-1)* l ，1in 逻辑上相邻的ai和ai+1以相邻的存储位置。 确定起始位置后，顺序表中任一数据元素都可随机存取。 顺序表是一种随机存取的存储结构。,高级语言中一般用数组来描述顺序存储。 #include #define MAXSIZE 100 typedef int ElemType; typedef struct ElemType aMAXSIZE; int length; Sqlist; 因为线性表长度可变，且所需最大空间随问题不同而不同，所以用动态分配的一维数组(P22)。为使得算法简明扼要，暂使用静态数组。,线性表的建立、输出算法,初始化,void i
5、nitlist(Sqlist *L) L-length=0; ,建立顺序表,void creat_sqlist(Sqlist ,void initlist(Sqlist ,Sqlist Sl; initlist(,Sqlist Sl; initlist(Sl);,输出顺序表,void outputl(Sqlist L) int i; cout“List length“ L.lengthendl; for (i=0; iL.length; i+) coutL.ai“ “; if (i+1)%10=0) coutendl; coutendl; ,(a1, , ai-1, ai, , an) 改变为
6、 (a1, , ai-1, e, ai, , an),表的长度加1,插入：在线性表第i （1i n+1）个位置上插入元素e,线性表主要操作的实现,注意：C语言中的数组下标从“0”开始，因此，若L是Sqlist类型的顺序表，则表中第i个元素是L.ai-1。,void insert_sq(Sqlist ,这里的问题规模是表的长度，设它的值为n。该算法的时间主要花费在循环的元素后移语句上，所需移动元素的次数不仅依赖于表的长度，而且还与插入位置有关。 i位置 移动次数 1 n 2 n-1 i n-i+1 n 1 n+1 0,插入操作时间复杂度分析,最好情况下：T(n)=O(1) 最坏情况下：T(n)=
7、O(n) 平均时间复杂度： 长度为n的顺序表中，插入一个结点，令E(n)表示移动结点的期望值(移动平均次数)，在表中第i个位置插入一个结点移动的次数为n-i+1. 其中pi表示在表中第i位置插入结点的概率。Pi1/(n+1) 计算得 E(n)=n/2，所以平均时间复杂度为O(n),(a1, , ai-1, ai, ai+1, , an) 改变为 (a1, , ai-1, ai+1, , an) （1 i n）,ai+1,an,表的长度减1,删除：在线性表中删除第i个元素，使,ElemType delete_sq(Sqlist ,算法的时间复杂度分析与插入算法相似，结点的移动次数也是由表长n和位
8、置i决定。 i位置 移动次数 1 n-1 2 n-2 i n-i n-1 1 n 0,删除操作时间复杂度分析,最好情况下：T(n)=O(1) 最坏情况下：T(n)=O(n-1) 平均时间复杂度：与插入运算相同，其时间主要消耗在了移动表中元素上，删除第i个元素时，其后面的元素 ai+1an 都要向上移动一个位置，共移动了 n-i 个元素，所以平均移动数据元素的次数： 在等概率情况下，pi =1/ n，则： 这说明顺序表上作删除运算时大约需要移动表中一半的元素，显然该算法的时间复杂度为(n)。,顺序表的优点： （1）各结点存储单元物理位置上的邻接关系表示了结点间的逻辑关系，因此，无须增加额外的存储
9、空间表示结点间的逻辑关系。 （2）因其为随机存储结构，故可以随机存取表中任一结点。,顺序表的缺点： （1）插入和删除不方便，通常须移动大量结点，效率较低。 （2）难以进行连续的存储空间的预分配，尤其是当表变化较大时。,重要结论,在顺序存储表示的线性表中插入或删除一个数据元素，平均约需要移动一半的元素,因此，顺序存储表示仅适用于不经常进行插入和删除操作并且表中元素相对稳定的表,查找：在线性表L中查找值为e的元素，如果存在，返回位置(0)，否则返回-1，表示未找到。,int locate_sq(Sqlist L, ElemType e) int i; i=0; while (i=L.length-
10、1 ,合并：两表分别非递减有序(递增或等值)，合并后仍然非递减有序。,void merge_list(Sqlist a, Sqlist b, Sqlist ,单链表 循环链表 双向链表 静态链表 单链表应用举例,2.3 线性表的链式表示与实现,线性表的链式表示和实现,链式分配 线性表数据元素的存储单元可以不连续，存放数据元素的结点至少包括两个域（数据域、指针域），也可以包含若干个数据域、指针域。 单链表：每个结点只有一个指针域 链表链接的顺序和数据元素的逻辑顺序一致，结点的物理位置可任意安排 头指针：存放第一个结点的存储地址 （附加）头结点：在单链表第一个结点之前附设一个结点,head,1 2
11、 3 4 5 6 7 8,5,head,head,头结点,头指针,头指针,空表,head,存储表示 typedef struct LNode ElemType data; / 数据域 struct LNode *next; / 指针域 LNode,*linklist; 其中linklist等价于LNode * 若设 LNode *p,*q; LinkList H; 则p,q,H都是指针变量, p-data 表示数据域 p-next 表示指针域,线性表的单链表,函数malloc,free(p);,访问结点,指针赋值的操作,P=(LNode*) malloc(sizeof(LNode); 产生一个
12、Lnode类型结点，把首地址送给P变量,系统回收P所指向的结点（若干字节），P中无所指向,Lnode *p, s; p-data=20; p-next=null; (s.data=20; s.next=null; 用的少),指针指向结点 p=q,指针指向后继 p=q-next,指针移动 p=p-next,指针赋值的操作,p-next =q,p-next =q-next,创建链表,单链表的基本运算,void creat_list() ElemType x; LNode *ptr,*p; p=head; coutx; while (x!=999) ptr=new LNode; ptr-data=x
13、; ptr-next=NULL; p-next=ptr; p=ptr; coutx; ,调用语句： head=new LNode; head-next=NULL; creat_list();,定义head 为全局变量,void create(LNode *L) int i,n; LNode *s,*p; p=L; coutn; for (i=1; is-data; p-next=s; p=s; p-next=NULL; ,调用语句： head=new LNode; head-next=NULL; create(head);,定义head 为局部变量,LNode *Creat_L(int n)
14、int i; LNode *L,*p; L=new LNode; L-next=NULL; for (i=n; i=1; i-) p=new LNode; coutp-data; p-next=L-next; L-next=p; return(L); ,调用语句： head=Creat_L(5);,定义head 为全局变量,输出链表,void out_list() LNode *q; q=head-next; if (q=NULL) coutdatanext; coutendl; ,取已知的线性链表的第i个元素的值，由函数名返回,ElemType GetElem(LNode *L, int i
15、) int j; LNode *p; p=L-next; j=1; while(p ,调用语句： cout“GetElem is “GetElem(head,4)endl;,语句频度： in，n次 平均为n数量级，故T(n)=O(n),在带头结点的单链表L中第i结点之前插入元素e,void Insert_L(LNode *L, int i, ElemType e) LNode *p,*s; int j; p=L; j=1; while (p!=NULL ,删除带头结点的单链表L中第i个结点，其数据元素由函数名返回,ElemType delete_list(LNode *L, int i) LNode *p,*q; int j; ElemType e; p=L; j=0; while (p-next!=NULL ,void listdelete_L(LNode *L,ElemType x) LNode *p,*q; p=L; while( p-next /删除x结点 ,在带头结点的单链表L中，查找值x的元素，删除之。（假设L中元素不重复）,链表合并La,Lb有序递增，合并为Lc，仍非递减有序,LNode *merge_list(LNode *La, LNode
