c教案整编线性表.ppt

1,第二章 线性表（linear list),线性表的定义及运算 线性表的顺序存储结构（顺序表） 线性表的链式存储结构（链表）,2,2.1 线性表的定义及运算 2.1.1. 线性表的定义： 是由n(n=0)个数据元素（结点）a1,a2,a3, an组成 的有限序列。其中： n为数据元素的个数，也称为表的长度。 当n=0 时，称为空表。 非空的线性表(n0) 记作：（ a1,a2,a3, an） 线性表的特性： （1）线性表中的所有数据元素的数据类型是一致的。 （2）数据元素在线性表中的位置只取决于它的序号。 （3）结点间的逻辑关系是线性的。,3,（1）有且仅有一个开始结点a1(无直接前趋）； （2）有且仅有一个终端结点an(无直接后继）； （3）其余的结点ai 都有且仅有一个直接前趋ai-1和一个直接后继ai+1。 （4）ai是属于某个数据对象的元素，它可以是一个数字、一个字母或一个记录。,例126个英文字母组成的字母表 （A，B，C、Z） 例2某校从1978年到1983年各种型号的计算机拥有量的变化情况。 （6，17，28，50，92，188）,2.1.2 线性表（a1,a2,a3, an）的逻辑特征：,4,例3、学生健康情况登记表如下：,5,数据的运算是定义在逻辑结构上的，而具体的实现则在存储结构上进行。 （1）存取 （2）插入 （3）删除 （4）查找 （5）合并 （6）分解 （7）排序 （8）求线性表的长度,基本运算,2.1.3. 线性表的运算,6, 2.2 线性表的顺序存储结构（顺序表） 2.2.1. 顺序表的定义： 用一组连续的存储单元（地址连续）依次存放线性表的各个数据元素。 即：在顺序表中逻辑结构上相邻的数据元素，其物理位置也是相邻的。,7,2.2.2 顺序表中数据元素的存储地址 若一个数据元素仅占一个存储单元，则其存储方式如下图。,从图中可见，第i个数据元素的地址为： LOC（a i）=loc(a 1)+(i-1),8,若每个数据元素占用m个存储单元，则 第i个数据元素的存储位置为： LOC（a i）=loc(a 1)+(i-1)*m 其中： loc(a 1)称为基地址（第一个数据元素的存储位置）。 显然，数据元素在顺序表中位置取决于数据元素在线性表中的位置。 顺序表的特点是：逻辑位置相邻，其物理位置也相邻。 例： 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第五个元素的存储地址是 _,108,9,2.2.3 顺序表的描述： 可用C语言的一维数组实现： #define M 100 int vM; 其中：M 是大于线性表长度的一个整数，它可根据实际需要而修改。线性表的各个元素a1,a2,a3, an可依次存入在向量v的各个分量v1,v2,.,vn中。,10,Sqlist类型定义,#define len 100 /线性表存储空间的初始分配量 #define skip 10 /线性表存储空间的分配增量 Typedef struct ElemType *elem; /存储空间基址 int length; /当前长度 int listsize; / 当前分配的存储容量（以 sizeof(ElemType)为单位） SqList;,2.2.4 顺序表的几种基本运算,11,顺序表的初始化,Status InitList_Sq (SqList / InitList_Sq,12,（1）删除算法 将线性表的第i（1<=i<=n)个结点删除，使： 长度为n的线性表变为长度为n-1的线性表。 （a1,a2,ai-1,ai,ai+1,an）,（a1,a2,ai-1,ai+1,an）,2.2.4 顺序表的几种基本运算,13,删除算法的思想： 1. 若i=n,只需删除终端结点，不用移动结点； 2. 若表长度n<=0或删除位置不适当，则输出错误信息，并返回-1； 3. 当1<=i<n时，则将表中结点ai+1,ai+2,an依次向前移动一个位置（共需移动n-i个数据元素）。 4. 最后将表长n减1，删除成功，函数返回值为0。,14,删除算法实现,Void deleteList(Sqlist 注： Sqlist类型定义见教材22页,15,删除算法分析： 上述算法for循环语句的执行次数为n-i; 若i=1,最坏：O(n) 若i=n,无需用移动结点，直接删除即可。（最好O(1)） 移动结点的平均次数：,16,按等概率考虑： 可能的删除位置为i=1,2,n共n个，则pi=1/n 所以,顺序表删除算法平均约需移动一半结点。,17,2.2.4 顺序表的几种基本运算 （2）插入运算 在第i（1<=i<=n)个元素之前插入一个新的数据元素x。使： 长度为n的线性表变为长度为n+1的线性表 （a1,a2,ai-1,ai,an）,（a1,a2,ai-1,x,ai,an）,18,插入算法的思想： 1. 若i=n+1,则将x插入到表尾； 2. 若表长度n<0或插入位置不适当，则输出错误信息，并返回-1； 3. 当1<=i<=n时，则从表尾开始到第i个元素，依次向后移动一个位置（共需移动n-i+1个数据元素）。 4. 最后将x存入vi中，表长n增加1，插入成功，函数返回值为0。,19,插入算法实现,int insertlist(v,pn,i,x) int v,x,*pn,i; /*-pn指向表长n的地址。-*/ int j; if (*pn*pn+1) printf(“插入位置i不适当n); return(-1); ,for (j=*pn;j=i;j-) vj+1=vj; vi=x; (*pn)+; printf(successn); return(0); 算法调用： k=insertlist(v,若i=1,需移动全部n个结点（最坏：O(n)）,若i=n+1（在表尾插入）,无需用移动结点，直接插入即可。（最好O(1)）,21,按等概率考虑： 可能的插入位置为i=1,2,n,n+1共n+1个，则pi=1/(n+1) 所以,顺序表插入算法平均约需移动一半结点。 小结： 顺序表插入、删除算法平均约需移动一半结点，当n很大时，算法的效率较低。,22,优点： （1）无须为表示结点间的逻辑关系而增加额外的存储空间。 （2）可以随机地访问表元素。 缺点： （1）插入和删除平均须移动一半结点。 （2）存储分配只能预先进行（静态） 过大- 浪费 过小- 溢出,顺序表的优、缺点,23, 2.3 线性表的链式存储结构（链表）,2.3.1 基本知识 链表： 用一组任意的存储单元（可以是无序的，即可零散地分布在内存中的任何位置上）存放线性表的数据元素。 链表的特点： 链表中结点的逻辑次序和物理次序不一定相同。即：逻辑上相邻未必在物理上相邻。 结点之间的相对位置由链表中的指针域指示，而结点在存储器中的存储位置是随意的。,24,线性表（ a1,a2,a3, a4）,25,结点的组成：,数据域 指针域,数据域-表示数据元素自身值。 指针域（链域）-存储其后继结点（或其它结点）的存储位置信息。 通过链域，可将n个结点按其逻辑顺序链接在一起（不论其物理次序如何）。,26,单链表：-每个结点只有一个链域。,头指针-指示链表中第一个结点的存储位置； 整个链表的存取必须从头指针开始 附: 单链表由头指针唯一确定，因此单链表可以用头指针的名字来命名。例如：若头指针为head，则可把链表称为“表head”。,2.3.2 单链表,27, 空表-头指针为空。 开始结点-（无前趋）用头指针指向之。 尾结点-（无后继），最后一个结点，其指针域为空，用或null表示。 表中其它结点-由其前趋的指针域指向之。 头结点-在链表的第一个结点之前附设一个结点，称为头结点。头结点的数据域可以不存任何信息，也可存储如长度等附加信息。,28,typedef int datatype; typedef struct node /结点类型定义 datatype data; /数据域 struct node *next; /next为指针域，指向后继 JD，*LinkList; /JD是结点的类型； LinkList 是指向JD类型结点的指针类型 JD *head,*p; LinkList H；,单链表的描述：,29,指针p与所指向的结点关系示意图： p 结点 (*p) 说明： p-指向链表中某一结点的指针。 *p-表示由指针p所指向的结点。 (*p).data或p-data-表示由p所指向结点的数据域。 (*p).next或p-next-表示由p所指向结点的指针域。,30,P=(JD*)malloc(n*sizeof(JD) -对指针p赋值使其指向某一结点（按需生成一个JD结点类型的新结点）。 其中： Sizeof(JD)-求结点需要占用的字节数。 n -需要结点的个数 Malloc(size)-在内存中分配size个连续可用字节的空间。(size= n*sizeof(JD) (JD*)-进行类型转换。 Free(p)-系统回收p结点。（动态）,31, 单链表的基本运算 （1）建立单链表之-头插法建表： 思想：从一个空表开始，重复读入数据，生成新结点，将读入数据存放在新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。,B,A ,C,D ,Head,S,注：头插法生成的链表中结点的次序和输入的顺序相反。,32,JD *CREATELISTF() Char ch; /*逐个插入字符，以“$“为结束 符，返回单链表头指针*/ JD *head,*s; head=NULL; /*链表开始为空*/ ch=getchar(); /*读入第一个结点的值*/ while(ch!=$) s=（JD *）malloc(sizeof(JD); /生成新结点s*/,s-data=ch; s-next=head; head=s; ch=getchar(); return head; /*CREATLISTF*/, 头插法建表:,33,算法思想：将新结点插入到当前链表的表尾上，可增加一个尾指针r，使其始终指向链表的尾结点。,A,C,B,（1）建立单链表之-尾插建表法：,head,r,尾插建表可使生成的结点次序和输入的顺序相同,34,JD *CREATLISTR() Char ch; /*逐个插入字符，以“$“为结 束符，返回单链表头指针*/ JD *head,*s,*r; head=NULL; /*链表开始为空*/ r=NULL; /*尾指针初值为空*/ ch=getchar(); /*读入首结点的值*/ while(ch!=$) /*“$“为输入结束符*/ s=（JD *）malloc(sizeof(JD); /生成新结点*/,s-data=ch; If (head=NULL) head=s; else r-next=s; r=s ch=getchar(); If (r!=NULL) r-next=NULL; return head; /*CREATLISTR*/, 尾插法建表:,35,头、尾插法建表分析： 上述头、尾插法建表由于没有生成（附 加）头结点，因此开始结点和其它结点 的插入处理并不一样，原因是开始结点 的位置存放在头指针中，而其余结点的 位置是在其前趋结点的指针域 。 尾插法建表的改进算法 思想：设头结点，使第一个结点和其余结点的插入操作一致。,36,（表）头结点： - 在第一个结点之前附设，其指 针域 存贮指向第一个结点的指针 （即第一个结点的存贮位置）。 头结点的数据域：可有可无 头结点的指针域：指向第一个结点的指针。,（1）建立单链表之-改进的尾插建表法：,37,带头结点的单链表,空表,非空表,说明： 无论链表是否为空，其头指针是指向头结点的非空指针，所以表的第一个结点和其它结点的操作一致。,head,头结点,38,JD *CREATLISTR1() /*带头结点的尾插法建立单链表，返回表头指针*/ Char ch; JD *head,*s,*r; head=malloc(sizeof(JD); /*生成头结点*/ r=head; /*尾指针初值指向头结点*/ ch=getchar(); while(ch!=$) /*“$“为输入结束符*/, s=（JD *）malloc(sizeof(JD); /生成新结点*/ s-data=ch; r-next=s; /*新结点插入表尾*/ r=s; /*尾指针r指向新的表尾*/ ch=getchar(); /*读下一结点*/ r-next=NULL; return head; /*CREATLISTR1*/,改进的尾插建表算法:,39,（2）单链表的查找运算之- 按序号查找 设单链表的长度为n,要查找表中第i个结点 算法思想如下： 从头结点开始顺链扫描，用指针p指向当前扫描到的结点，用j作统计已扫描结点数的计数器，当p扫描下一个结点时，j自动加1。 P的初值指向头结点，j的初值为0。 当j=i时，指针p所指的结点就是第i个结点。,单链表的基本运算,40,按序号查找算法描述 JD *GET(head,i) JD *head; int i; int j; JD *p; p=head;j=0; while(p-next!=null) /*找不到，收返回null*/ /*end*/,41,（2）单链表的查找运算之- 按值查找 在链表中，查找是否有结点等于给定值key的结点，若有的话，则返回首次找到的值为key的结点的存储位置；否则返回null. 算法思想： 从开始结点出发，顺链逐个结点的值和给定值key作比较。 算法描述（略）,42,（3）插入运算： 设指针p指向单链表的某一结点，指针s指向等待插入的、其值为x的新结点。 实现方法（两种）： 后插-将新结点*s插入结点*p之后。 前插-将新结点*s插入结点*p之前。,单链表的基本运算,43,算法思想： 取一新结点，将其数据域置为要插入的值，再修改有关结点的链域： 把原p结点的直接后继结点作为s结点的直接后继，s结点作为p结点的直接后继。,S,（3）单链表的插入运算之- 后插算法,P,X,44,INSERTAFTER（P，X） /*将值为X的新结点插入*P之后*/ JD *p; datatype x; JD *s; s=（JD *）malloc(sizeof(JD); /生成新结点*/ s-data=x; s-next=p-next; p-next=s; /*将*s插入*p之后*/ /*INSERTAFTER */,后插算法实现：,后插算法的时间复杂度： O（1）,45,例1-6：在单链表中实现线性表的插入运算INSERT（L,x,i)，即在链表L的第i个位置插入数据x。 算法思想： (1)先求出第i-1个结点 (2)然后在第i-1个结点之后插入结点x。,46,例1-6的实现： INSERT（L,x,i) JD *L; datatype x; int i; JD *p; int j; j=i-1; p=GET(L，j）； /*找到第i-1个结点*p*/ if (p=null) printf(“找不到插入点n“） else INSERA(p,x) /*end*/,47,q,p,算法思想： 先找到p结点的前趋结点q（单链表无前趋指针），将s结点指向p结点，然后修改q的链域，使其指向待插入的s结点。,（3）单链表的插入运算之- 前插操作：,48,INSERTBEFORE（head,p,x）/*在带头结点的单链表head中, 将值为X的新结点插入*P之前*/ JD *head,*p; datatype x; JD *q,*s; s=（JD *）malloc(sizeof(JD); /*生成新结点*/ s-data=x; q=head; /*从头指针开始*/ While(q-next!=p) q=q-next; /*找*p的前趋结点*/ s-next=p；q-next=s; /*将*s插入*p之 前*/ /*INSERTBEFORE */,前插算法实现：,前插算法的平均时间复杂度为：O（n）,49,后插法插入结点S后，交换*S和*p： 交换值： t=p-data; p-data=s-data; s-data=t; 后移指针： p=p-next ,（3）单链表的基本运算之- 改进的前插算法,算法思想： 后插算法为O(1)，而前插算法为O(n)，改进后可在p之后先插入新结点s，然后交换*s和*p的值。 算法描述： （思考）,50,插入前 p s 插入后 p s,A,X,x,A,51,(4) 删除运算,删除单链表中*p的后继 算法描述： DeleteA(JD * p) /*删除p的后继结点r，设r存在*/ JD *r; If (p-next!=null) r=p-next; p-next=r-next; free(r); /*enddelete*/,单链表的基本运算,52,思考： （1）如何删除单链表中p结点本身？ （2）如何删除单链表中p结点的前趋结点？ 例1-7：在单链表上实现线性表的删除运算Delete(L,i)，即删除链表L的第i个结点。 思想：先找到被删结点（第i个）的前趋结点，即第i-1个结点p；然后删除p的后继（ 需引用函数GET（L,i) )。,53,例1-7的实现： DELETE( L, i ) JD *L; int i; JD *p; int j; j=i-1; p=GET(L，j)； /*找到第i-1个结点*p*/ if (p!=null) else printf(“errorn”) /*end*/ 思考：如何实现删除线性表head中数据域为a的结点。,54,例: 1、线性表的顺序存储结构是一种随机存取的存储结构；则线性表的链式存储结构是一种（ ）的存储结构。 A、 随机存取 B、 顺序存取 C、 索引存取 D、 线性存取,B,55,例: 2、线性表若采用顺序存储结构时，要求内存可用存储单元的地址 ( ) A、必须是连续的 B、 部分地址必须是连续的 C、一定是不连续的 D、 连续不连续都可以,A,56,例: 3、下列语句中正确的是（ ） A. 顺序存储方式只能用于线性结构，不能用于非线性结构 B. 基于某种逻辑结构之上的运算，其实现是唯一的 C. 算法可以用不同的语言描述，则算法实际上就是程序了 D. 数据结构的三大组成部分是逻辑结构、存储结构和运算,D,57,例: 4、带头结点的单链表为空的判定条件是 （ ） A、head=NULL B、head-next=NULL C、hed-next=head D、head!=NULL,B,58,例: 5、不带头结点的单链表为空的判定条件是 （ ） A、head=NULL B、head-next=NULL C、hed-next=head D、head!=NULL,A,59,例6： 在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行( ) A. p-next=s-next; s-next=p B. p-next=s-next; s-next=q C. q-next=s; s-next=q-next D. q-next=s; s-next=p; E. 以上都不对,D,60,2.3.3 循环链表,循环链表：整个链表形成一个环，从表中任一结点出发均可找到表中其它结点。 非空表： Head 空表： head,a1,an,61,（2）循环链表的运算与单链表基本一致。但两者判断是否到表尾的条件不同： 单链表：判断某结点的链域是否为空。 循环链表：判断某结点的链域是否等于头指针。,特点： （1）表中最后一个结点的指针指向第一个结点或表头结点（如果有表头结点）。,62,（3）用头指针表示的单循环链表查找结点： 找a1(开始结点) O(1) 找an 需要遍历表 O(n) 由于在实际问题中，对表的操作常在表的首尾位置进行，因此可增加一个尾指针(rear)，则： 找a1(开始结点) ：rear-next-next O(1) 找an rear O(1) 实用中多用尾指针表示单循环链表。,63,循环链表,head,head,非空表,空表,rear,rear,64,例: 表的合并：在链表上实现将两个线性表(a1,a2,.,an)和(b1,b2bm)链接成一个线性表(a1,a2,.,an,b1,b2,.,bm)的运算。 分析：若在单链表或头指针表示的单循环链表上做这种链接运算，都要遍历第一个链表找到结点an，然后将结点b1链接到an的后面，其执行时间为O（n）。 算法思想： 在尾指针表示的单循环链表上实现，则只需修改指针，无需遍历，其执行时间为O（1）。,65,两个单循环链表（用尾指针表示）的链接示意图,p,66,JD *CONNECT(ra,rb) JD *ra,*rb; JD *p; p=ra-next; /*保存链表ra的头结点地址*/ ra-next=rb-next-next; /*将表rb的开始结点链接到表ra的终结点之后*/ free(rb-next); /*释放链表rb的头结点*/ rb-next=p； /*链表ra的头结点链到链表rb的终端结点之后*/ return rb ; /*返回新循环链表的尾指针*/ /*ENDCONNECT*/,67,2.3.4 双向链表（Double linked list),单链表查找特点的回顾： 只能顺链向后（顺着直接后继指针）查找。若要找某一结点的前趋，则： 单链表：从头顺链找。O(n) 单循环链表：可从任一已知结点出发查。 O(n),68,双向链表（Double linked list)- 单链表的每个结点再增加一个指向其前趋的指针域 prior，这样形成的链表有两条不同方向的链，称之为双（向）链表。 特点： 双链表一般也由头指针head唯一确定。 每一结点均有： 数据域（data) 左链域 （prior) 指向前趋结点. 右链域 （next) 指向后继结点。 是一种对称结构（既有前趋，又有后继）。,69,（1）双向链表的分类： 非循环双向链表 循环双向链表 此外，为了定义运算方便起见，还可添加一表头结点。 （2）双链表的结点类型描述 typedef struct dnode datatype data; struct dnode *prior,*next; dlinklist; dlinklist *head;,70,(3)结点结构示意图,71,(4)双链表结构对称性描述： p-prior-next=p-next-prior=p 即：结点*p的存储位置 既存放在其前趋结点（*p-prior)的后继指针域中； 也存放在其后继结点（*p-next)的前趋指针域中。,72,(5)双链表的基本运算： 插入、删除、查找 在单链表中，前插不如后插方便；删除某结点自身不如删除该结点的后继方便。 而在双向链表中，上述的运算均十分方便。,73,(前)插入操作（将结点x插入*p之前） /*在带头结点的双链表中，将值为x的新结点插入到*p 之前。*/ Dinsert (p,x) dlinklist *p; datatype x; dlinklist *s; s=malloc(sizeof(dlinklist); s-data=x; s-prior=p-prior; s-next=p; p-prior-next=s; p-prior=s; /*enddinsert*/,74,75,删除操作（在双向链表中删除p结点） Ddelete(p) dlinklist *p; p-prior-next=p-next; p-next-prior=p-prior; free(p); /*endDdelete*/,76,77,查找（在带头结点双向循环链表中查找结点x） 算法思想： 从第一个结点开始（头结点的后继）依次比较每个结点的数据域的值，若找到结点x则返回指向该结点的指针；否则： 若又回到头结点，说明表中不存在头结点x，则返回空指针。 算法描述： 参见教材描述的算法。,78,例: 7、若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省时间。 A、单链表 B、仅有头指针的单循环链表 C、双链表 D、仅有尾指针的单循环链表,D,79,例： 8、在单链表、双链表和单循环链表中，若仅知道指针P指向某结点，不知道头指针，能否将结点*P从相应的链表中删除？请选出下面三种链表中能删除结点*P且其时间复杂度为O(n)的一项( ) A. 单链表 B. 双链表 C. 单循环链表,C,80,关于顺序表和链表的小结： （1）顺序表是用数组实现的，而链表是用指针或“游标”来实现的。 （2）当线性表的长度变化较大，难以估计其存储规模时， 益采用动态链表作为存储结构为佳；当线性表的长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表作为存储结构。（基于空间的考虑）,81,（3）顺序表是一种随机存取结构，对表中任一结点都可在O(1)时间内直接存取。而链表中的结点则需用从头指针开始顺链扫描。 因此： 若线性表的操作主要是查找，很少涉及到插入、删除操作时，可采用顺序表结构。 若要频繁地进行插入和删除操作，宜采用链表作为存储结构。 若表的插入、删除操作主要发生在表的两端，则宜采用有尾指针的单循环链表。,82,2.4 线性表的应用举例 一元多项式的表示及相加 一元多项式的表示：,可用线性表P表示,但对S(x)这样的多项式浪费空间,用数据域含两个数据项的线性表表示,其存储结构可以用顺序存储结构，也可以用单链表,83,单链表的结点定义,typedef struct node int coef,exp; struct node *next; JD;,一元多项式相加,84,设p,q分别指向A,B中某一结点，p,q初值是第一结点,运算规则,85,Ch2_7.c,算法描述,