数据结构学习――第二章线性表

1第二章线性表（linearlist)2.1线性表的定义及运算1.线性表的定义：是由n(n=0)个数据元素（结点）a1,a2,a3,……an组成的有限序列。其中：n为数据元素的个数，也称为表的长度。当n=0时，称为空表。非空的线性表(n0)记作：（a1,a2,a3,……an）22.线性表（a1,a2,a3,……an）的逻辑特征：（1）有且仅有一个开始结点a1(无直接前趋）；（2）有且仅有一个终端结点an(无直接后继）；（3）其余的结点ai都有且仅有一个直接前趋ai-1和一个直接后继ai+1。（4）ai是属于某个数据对象的元素，它可以是一个数字、一个字母或一个记录。33.线性表的特性（1）线性表中的所有数据元素的数据类型是一致的。（2）数据元素在线性表中的位置只取决于它的序号。（3）结点间的逻辑关系是线性的。4例1、26个英文字母组成的字母表（A，B，C、…、Z）例2、某校从1978年到1983年各种型号的计算机拥有量的变化情况。（6，17，28，50，92，188）5例3、学生健康情况登记表如下：姓名学号性别年龄健康情况王小林790631男18健康陈红790632女20一般刘建平790633男21健康张立立790634男17神经衰弱……..……..…….…….…….64.线性表的运算数据的运算是定义在逻辑结构上的，而具体的实现则在存储结构上进行。（1）存取（2）插入（3）删除（4）查找（5）合并（6）分解（7）排序（8）求线性表的长度基本运算7线性表的顺序存储结构（顺序表）1.顺序表的定义：------用一组连续的存储单元（地址连续）依次存放线性表的各个数据元素。即：在顺序表中逻辑结构上相邻的数据元素，其物理位置也是相邻的。82.顺序表中数据元素的存储地址若一个数据元素仅占一个存储单元，则其存储方式参见下图。从图中可见，第i个数据元素的地址为：LOC（ai）=loc(a1)+(i-1)9若每个数据元素占用m个存储单元，则第i个数据元素的存储位置为：LOC（ai）=loc(a1)+(i-1)*mloc(a1)称为基地址（第一个数据元素的存储位置）。显然，数据元素在顺序表中位置取决于数据元素在线性表中的位置。顺序表的特点是：逻辑位置相邻，其物理位置也相邻。103.顺序表的描述：可用C语言的一维数组实现：#defineM100intv[M];其中：M是大于线性表长度的一个整数，它可根据实际需要而修改。线性表的各个元素a1,a2,a3,……an可依次存入在向量v的各个分量v[1],v[2],…...,v[n]中。115.顺序表的几种基本运算（1）插入运算---在第i（1=i=n)个元素之前插入一个新的数据元素x。使：长度为n的线性表变为长度为n+1的线性表（a1,a2,…,ai-1,ai,…,an）（a1,a2,…,ai-1,x,ai,…,an）12插入算法的思想：若i=n+1,则将x插入到表尾；若表长度n0或插入位置不适当，则输出错误信息，并返回-1；当1=i=n时，则从表尾开始到i个依次向后移动一个位置（共需移动n-i+1个数据元素。最后将x存入v[i]中，表长n增1插入成功，函数返回值为0。13插入算法描述intsxbcr(v,pn,i,x)intv[],x,*pn,i;/*--pn指向表长n的地址。--*/{intj;if(*pn0){printf(“表长错误\n);return(-1);}if(i1||i*pn+1){printf(“插入位置i不适当\n);return(-1);}for(j=*pn;j=i;j--)v[j+1]=v[j];v[j]=x;(*pn)++;printf(success\n);return(0);}算法调用：k=sxbcr(&v,&n,i,x)14插入算法分析：上述算法for循环语句的执行次数为n-i+1;若i=1,需移动全部n个结点（最坏：O(n)）若i=n+1（在表尾插入）,无需用移动结点，直接插入即可。（最好O(1)）移动结点的平均次数：15按等概率考虑：可能的插入位置为i=1,2,……n,n+1共n+1个，则pi=1/(n+1)所以顺序表插入算法平均约需移动一半结点。16（2）删除算法---将线性表的第i（1=i=n)个结点删除，使：长度为n的线性表变为长度为n-1的线性表。（a1,a2,…,ai-1,ai,ai+1,…,an）（a1,a2,…,ai-1,ai+1,…,an）17删除算法的思想：若i=n,只需删除终端结点，不用移动结点；若表长度n=0或删除位置不适当，则输出错误信息，并返回-1；当1=in时，则将表中结点ai+1,ai+2,…,an依次向前移动一个位置（共需移动n-i个数据元素。最后将表长n减1，删除成功，函数返回值为0。18删除算法描述VoiddeleteList(Sqlist*L，inti){intj;if(i1||iL.length){printf(“Positionerror”);returnERROR;}for(j=i+1;j=L.length-1;j++)L.data[j-1]=L.data[j];L.length--;}19删除算法分析：上述算法for循环语句的执行次数为n-i;若i=1,最坏：O(n)若i=n,无需用移动结点，直接删除即可。（最好O(1)）移动结点的平均次数：20按等概率考虑：可能的删除位置为i=1,2,……n共n个，则pi=1/n所以顺序表插入算法平均约需移动一半结点。小结：顺序表插入、删除算法平均约需移动一半结点，当n很大时，算法的效率较低。21优点：（1）无须为表示结点间的逻辑关系而增加额外的存储空间。（2）可以方便地随机存储表中的任一结点。缺点：（1）插入和删除平均须移动一半结点。（2）存储分配只能预先进行（静态）过大浪费过小溢出顺序表的优、缺点：22-----线性表的链式存储结构第二章线性表线性表的链式存储结构：（链表linkedlist）链表：用一组任意的存储单元（可以是无序的）存放线性表的数据元素。*无序---可零散地分布在内存中的任何位置上。链表的特点：链表中结点的逻辑次序和物理次序不一定相同。即：逻辑上相邻未必在物理上相邻。结点之间的相对位置由链表中的指针域指示，而结点在存储器中的存储位置是随意的。23-----线性表的链式存储结构第二章线性表线性表的链式存储结构：（链表linkedlist）结点的组成：数据域指针域数据域----表示数据元素自身值。指针域（链域）----表示与其它结点关系。通过链域，可将n个结点按其逻辑顺序链接在一起（不论其物理次序如何）。24-----线性表的链式存储结构第二章线性表线性表的链式存储结构：（链表linkedlist）单链表：----每个结点只有一个链域。开始结点---（无前趋）用头指针指向之。最后一个结点(尾结点)---指针为空（无后继），用^或null表示。表中其它结点---由其前趋的指针域指向之。a1an^Head25-----线性表的链式存储结构第二章线性表单链表：空表---头指针为空。头结点---其指针域指向表中第一个结点的指针。单链表的描述单链表由头指针唯一确定，因此单链表可以用头指针的名字来命名。例如：若头指针为head,则可把链表称为“表head”。a1an^Head26Typedefintdatatype;typedefstructnode/*结点类型定义*/{datatypedata;/*数据域*/structnode*next;}JD;/*next为指针域，指向该结点的后继*/JD*head,*p;/*指针类型说明*/指针p与指向的结点关系示意图Datanextp结点(*p)单链表的描述：27指针p与指向的结点关系示意图：p结点(*p)说明：p---指向链表中某一结点的指针。*p---表示由指针p所指向的结点。(*p).data或p-data----表示由p所指向结点的数据域。(*p).next或p-next----表示由p所指向结点的指针域。Datanext单链表的描述：28P=(JD*)malloc(sizeof(JD))----对指针p赋值使其指向某一结点（按需生成一个JD结点类型的新结点）。其中：(JD*)----进行类型转换。Sizeof(JD)---求结点需用占用的字节数。Malloc(size)--在内存中分配size个连续可用字节的空间。Free(p)--系统回收p结点。（动态）单链表的描述：-----线性表的链式存储结构第二章线性表29单链表的基本运算（1）建立单链表之-------①头插法建表：思想：从一个空表开始，重复读入数据，生成新结点，将读入数据存放在新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。BA^CD②Head-----线性表的链式存储结构第二章线性表①③④S注：头插法生成的链表中结点的次序和输入的顺序相反。30JD*CREATELISTF(){Charch;/*逐个插入字符，以“$“为结束符，返回单链表头指针*/JD*head,*s;head=NULL;/*链表开始为空*/ch=getchar();/*读入第一个结点的值*/while(ch!=‘$’){s=（JD*）malloc(sizeof(JD));/生成新结点*/s-data=ch;s-next=head;head=s;ch=getchar();}returnhead;}/*CREATLISTF*/头插法建表:31算法思想：将新结点插入到当前链表的表尾上，可增加一个尾指针r，使其始终指向链表的尾结点。pAD^CB-----线性表的链式存储结构第二章线性表单链表的基本运算（1）建立单链表之-------②尾插建表法：headrS①②③④尾插建表可使生成的结点次序和输入的顺序相同32JD*CREATLISTR(){Charch;/*逐个插入字符，以“$“为结束符，返回单链表头指针*/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;elser-next=s;r=s;ch=getchar();}If(r!=NULL)r-next=NULL;returnhead;}/*CREATLISTR*/尾插法建表:33头、尾插法建表分析：上述头、尾插法建表由于没有生成（附加）头结点，因此开始结点和其它结点的插入处理并不一样，原因是开始结点的位置存放在头指针中，而其余结点的位置是在其前趋结点的指针域。③尾插法建表的改进算法思想：设头结点，使第一个结点和其余结点的插入操作一致。单链表的基本运算-----线性表的链式存储结构第二章线性表34（表）头结点（在第一个结点之前附设）---其指针域存贮指向第一个结点的指针（即第一个结点的存贮位置）。头结点的数据域：可有可无头结点的指针域：指向第一个结点的指针。-----线性表的链式存储结构第二章线性表单链表的基本运算之---改进的尾插法建表算法35-----线性表的链式存储结构第二章线性表带头结点的单链表^空表heada1an^头结点开始结点非空表无论链表是否为空，其头指针是指向头结点的非空指针，所以表的第一个结点和其它结点的操作一致。36JD*CREATLISTR1()/*带头结点的尾插法建立单链表，返回表头指针*/{Charch;JD*head,*s,*r;head=malloc(sizeof(JD));/*生成头结点*/r=head;/*尾指针初值指向头结点*/ch=getchar();while(ch!=‘$’)/*“$“为输入结束符*/{s=（JD*）malloc(sizeof(JD)