02-线性表

1数据结构DataStructure2第二章线性表第二章线性表2.1线性表的定义和运算2.2顺序表2.3链表2.4其它结构形式的链表2.5串32.1线性表的定义和运算定义：线性表L是由n个元素a1，a2，……，an组成的有限序列。记作L=（a1，a2，……，an）其中n=0为表长；n=0时为L空表，记作L=（）特性：A、只有一个第一个元素和一个最后一个元素；B、除第一个元素外其他元素有且仅有一个直接前趋（前驱）；C、除最后一个元素外其他元素有且仅有一个直接后继元素ai的含义：同一表中，元素类型相同。在不同的场合有不同的含义例：字母表（A，B，C，D，……，Z）；数字表（0，1，2，3，4，……，9）；每月天数（31,29,31,30,31,30,31,31,30,31,30,31）;42.1线性表的定义和运算运算：(1)初始化initial_List(L)建立线性表的初始结构，即建空表(2)求长度List_length(L)即求表中的元素个数(3)按序号取元素get_element(L,i)取出表中序号为i的元素(4)按值查找元素List_locate(L,x)取出指定值为x的元素，若存在则返回其地址；否则返回特殊值(5)插入List_insert(L,i,x)在表L的第i个位置上插入值为x的元素(1=i=n+1)(6)删除List_delete（L,i）删除表L中序号为i的元素1=i=n52.2顺序表存储结构：顺序表类型描述#definemaxlen100//假设元素个数最大为100typedefstruct{elementtypedata[maxlen];//存储表中元素的数组intlistlen;//表长度}seqlist;顺序表的特点：逻辑上相邻的元素，其存储地址也相邻。62.2顺序表运算实现：voidinitial_List（seqlist*L）{L-listlen=0;}intList_length（seqlistL）{returnL.listlen;}voidget_element（seqlistL，inti,elementtype&x）{if（i1||iL.listlen）error(“超出范围”);elsex=L.data[i-1];}intList_locate（seqlistL，elementtypex）{inti;for(i=0;iL.listlen;i++)if(L.data[i]==x)return(i+1);return(0);}72.2顺序表voidList_insert（seqlist*L，elementtypex，inti）{intj;if（L-listlen==maxlen）error（“overflow”）;elseif（i1||iL-listlen+1）error(“positionerror”）;else{for（j=L-listlen-1;j=i-1;j--）L-data[j+1]=L-data[j];L-data[i-1]=x;L-listlen++;}}a1a2a3aian012i-1n-1maxlen-1x条件：顺序表不满；序号正确，在[1,n+1]中操作：ai~an后移;填入x;listlen++82.2顺序表voidList_delete(seqlist*L,inti){intj;if(L-listlen=0)error(“下溢出错”);if(iL-listlen||i=0)error(“删除位置出错”);else{for(j=i;j=L-listlen-1;j++)L-data[j-1]=L-data[j];L-listlen--;}}92.2顺序表算法分析：插入时在i=1,2,…,n+1，元素移动的次数分别为n,n-1,…,0。在等概率的情况下，平均移动(n+1)n/2(n+1)=n/2次删除时在i=1,2,…,n，元素移动的次数分别为n,n-1,…,0。在等概率的情况下，平均移动(n-1)n/2n=(n-1)/2次结论：n较大时，大量移动元素，耗时解决：考虑不移动元素102.3链表——基本结构以链接形式连接元素次序。a1a2a3a4^L=(a1,a2,a3,a4)结点包括元素和地址。datanext112.3链表——存储实现（静态链表）1、静态链表——用数组C3A2B0D5F-1E4datanext012345L=(A,B,C,D,E,F)head122.3链表——存储实现（动态链表）2、动态链表——用指针和动态变量实现（1）结点结构datanext（2）类型定义typedefstruct{elementtypedata;node*next;}node;引用：node*head；132.3链表－图例a1a2a3a4^Head*HeadHead-next首元素142.3链表——讨论(插入操作)插入（一般位置）：假设被插入位置的前一个结点的指针P已找到，插入由S指向的结点：Pa1a2a3a4^headxS×①②①S-next=P-next②P-next=S注意：两个操作不能交换如果是作为第一个结点插入，过程如下：×①②①S-next=head-next②head=Sa1a2a3a4^headxS152.3链表——讨论(引入头结点)为保持插入操作一致，引入头结点。注意：头结点与首元素的区别。a1a2a3^xheadSP①S-next=P-next②P-next=S162.3链表——讨论(删除操作)删除（一般位置）：假设被删除的前一个结点的指针P已找到，插入由S指向的结点：Pa1a2a3a5^heada4×P-next=P-next-next如果是删除第一个结点，过程如下：head=head-nexta1a2a3a5^heada4×讨论结果：引入头结点P-next=P-next-next×a1a2a4^heada3P172.3链表——运算的实现（有头结点）1、初始化单链表（建空表）L^voidinitial_List(node&*L){L=newnode;L-next=NULL;}182.3链表——求表长（1）2、求单链表表长a1a2a3^LPlen=0P=L-next;len=0;P!=NULLreturn(len);P=P-next;len++;YNintList_length(node*L){P=L-next;len=0;while(P!=NULL){P=P-next;len++;}return(len);}192.3链表——求表长（2）2、求单链表表长a1a2a3^LintList_length(node*L){P=L;len=0;while(P-next!=NULL){P=P-next;len++;}return(len);}Plen=0P=L;len=0;P-next!=NULLreturn(len);P=P-next;len++;YN202.3链表——按序号取值3、按序号取值—返回指向结点的指针,否则返回NULLa1a2a3^LPj=0node*get(node*L,inti){P=L;j=0;while(P-next!=NULL&&j!=i){P=P-next;j++;}return(P);}P=L;j=0;P-next!=NULLreturn(P);P=P-next;j++;YNj==iYNreturn(P);212.3链表——按值查询4、按值查询——返回元素结点指针，否则返回NULL；a1a2a3^LPP=L-next;P-data!=xreturn(P);P=P-next;YNP!=NULLNYreturn(P);node*locate(node*L,elementtypex){P=L-next;while(P!=NULL&&P-data!=x)P=P-next;return(P);}222.3链表——插入5、插入ai-1aixSP×分析：A、搜索位置；B、装入x；C、插入x；P=get(L,i-1);if(P==NULL)error(“序号错”);else{S=newnode;S-data=x;S-next=P-next;P-next=S;}voidinsert(node&*L,elementtypex,inti){}232.3链表——删除6、删除Pai-1aiai+1×分析：A、搜索位置；B、删除结点；C、释放结点；P=get(L,i-1);if(P==NULL)error(“序号错”);else{u=P-next;P-next=P-next-next;deleteu;}voiddelete(node&*L,inti){}242.3链表——单链表的应用(头结点)链表的遍历：访问链表每个结点一次且仅一次。基本算法如下：voidprint(node*L){P=L-next;while(P!=NULL){visit(P-data);P=P-next;}}a1a2a3^LP252.3链表——单链表的应用(头结点)设计算法，判断带头结点单链表L是否递增？若递增，则返回true，否则返回false。分析：（1）链表空，返回true；（2）只有一个结点，返回true；（3）每个元素都小于其直接后继，返回true；否则，返回false；例262.3链表——单链表的应用(头结点)由分析得如下流程图：P=L-next;P=P-next;P!=NULLP-next!=NULLP-dataP-next-dataYYY返回true返回trueNN返回fasleNboolJudge(node*L){P=L-next;if(P==NULL)return(true);while(P-next!=NULL){if(P-dataP-next-data)P=P-next;elsereturn(false);}return(true);}272.3链表——构造链表构造链表基本方法：从键盘输入数据，每读入一个元素，产生结点装入，插入链表中，重复上述操作X是结束0非0cinxs=newnode;s-data=x;s-next=head-next;head-next=s;讨论：产生结点：s=newnode;s-data=x;插入链表：插入位置如何确定，有表头/表尾两个位置可选头插法尾插法重复上述操作：何时结束?282.3链表——头插法头插法运算实现：voidcreate_List(node*&L){L=newnode;L-next=NULL;cinx;while(x!=End_of_Num){u=newnode;u-data=x;u-next=L-next;L-next=u;cinx;}}a1a2an^……UxL292.3链表——尾插法尾插法运算实现：voidcreate_List(node*&L){L=newnode;R=L;//尾指针cinx;while(x!=End_of_Numo){u=newnode;u-data=x;R-next=u;R=u;cinx;}R-next=NULL;}a1a2an^……x^sLR302.3链表——练习题1）链表A，B，设计算法求C＝A∩B，并分析其时间复杂度2）递增链表A，B，设计算法求C＝A∩B，并分析其时间复杂度312.4其他结构形式的链表单循环链表（优点：可在表中反复搜索）初始化操作为：head=newnode;head-next=head;求长度：p=head-next;n=0;while(p!=head){p=p-next;n++;}应用：m人开m把锁问题（每人一把钥匙，要求所有锁都能开）约瑟夫环问题（利用循环队列，不带头结点的循环链表都可）a1a2an……headhead322.4其他结构形式的链表带尾指针的单循环链表（优点：表尾操作方便）应用：将A、B两链表