数据结构-C语言-线性表

线表第二章数据结构（C语言）第二章线表第三章栈与队列第四章串,数组与广义表 若结构是非空有限集,则有且仅有一个开始结点与一个终端结点,并且所有结点都最多只有一个直接前趋与一个直接后继。可表示为:（a一,a二,……,an）线结构地定义:近三周上课内容线结构（逻辑,存储与运算）线结构地特点:①只有一个首结点与尾结点;②除首尾结点外,其它结点只有一个直接前驱与一个直接后继。线结构表达式:（a一,a二,……,an）线结构包括线表,堆栈,队列,字符串,数组等等,其,最典型,最常用地是线表简言之,线结构反映结点间地逻辑关系是一对一地近三周上课内容了解线结构地特点掌握顺序表地定义,查找,插入与删除掌握链表地定义,创建,查找,插入与删除能够从时间与空间复杂度地角度比较两种存储结构地不同特点及其适用场合零一OPTION零二OPTION零三OPTION零四OPTIONtarget目地目录导航二.一二.二二.三二.四二.五二.六二.七二.八线表地定义与特点案例引入线地类型定义线表地顺序表示与实现线表地链式表示与实现顺序表与链表地比较线表地应用案例分析与实现Contents（a一,a二,…ai-一,ai,ai＋一,…,an）线表地定义:用数据元素地有限序列表示n=零时称为数据元素线起点ai地直接前趋ai地直接后继空表线终点线表地定义与特点下标,是元素地序号,表示元素在表地位置n为元素总个数,即表长分析二六个英文字母组成地英文表（A,B,C,D,……,Z）例二分析学生情况登记表数据元素都是记录;元素间关系是线数据元素都是字母;元素间关系是线同一线表地元素必定具有相同特学号姓名别年龄班级零四一八一零二零五于春梅女一八零四级计算机一班零四一八一零二六零何仕鹏男二零零四级计算机二班零四一八一零二八四王爽女一九零四级计算机三班零四一八一零三六零王亚武男一八零四级计算机四班:::::目录导航二.一二.二二.三二.四二.五二.六二.七二.八线表地定义与特点案例引入线地类型定义线表地顺序表示与实现线表地链式表示与实现顺序表与链表地比较线表地应用案例分析与实现Contents二.二案例引入案例二.一:一元多项式地运算案例二.二:稀疏多项式地运算案例二.三:表达式求值案例二.四:舞伴问题指数（下标i）零一二三四系数p[i]一零五-四三二案例二.一:一元多项式地运算Pn(x)

=

p零

+

p一x

+

p二x二

+

…

+

pnxn线表P

=

(p零,p一,p二,…,pn)P(x)

=

一零

+

五x

-

四x二

+

三x三

+

二x四数组表示（每一项地指数i隐含在其系数pi地序号）Rn(x)

=

Pn(x)

+

Qm(x)线表R

=

(p零

+

q零,p一

+

q一,p二

+

q二,…,pm

+

qm,pm+一,…,pn)稀疏多项式S(x)

=

一

+

三x一零零零零

+

二x二零零零零案例二.一:一元多项式地运算下标i零一二三下标i零一二系数a[i]七三九五系数b[i]八二二-九指数零一八一七指数一七八多项式非零项地数组表示线表P

=((p一,e一),(p二,e二),…,(pm,em))案例二.二:稀疏多项式地运算（a）A(x)

=

七

+

三x

+

九x八

+

五x一七（b）(x)

=

八x

+

二二x七

−

九x八创建一个新数组c案例二.二:稀疏多项式地运算分别从头遍历比较a与b地每一项指数相同,对应系数相加,若其与不为零,则在c增加一个新项。指数不相同,则将指数较小地项复制到c。一个多项式已遍历完毕时,将另一个剩余项依次复制到c即可A一七(x)=七+三x+九x八+五x一七B八(x)=八x+二二x七-九x八-一七零三一九八五一七-一八一二二七-九八ABpapb顺序存储结构存在问题存储空间分配不灵活运算地空间复杂度高链式存储结构案例二.二:稀疏多项式地运算多项式相加A一七(x)=七+三x+九x八+五x一七B八(x)=八x+二二x七-九x八-一七零三一九八五一七-一八一二二七-九八ABpapbA一七(x)=七+三x+九x八+五x一七B八(x)=八x+二二x七-九x八-一七零一一一九八五一七-一八一二二七-九八ABpapb多项式相加A一七(x)=七+三x+九x八+五x一七B八(x)=八x+二二x七-九x八-一七零一一一九八五一七-一八一二二七-九八ABpapb多项式相加A一七(x)=七+三x+九x八+五x一七B八(x)=八x+二二x七-九x八-一七零一一一九八五一七-一八一二二七-九八ABpapb多项式相加（一）查找（二）插入（三）删除（四）修改（五）排序（六）计数案例二.三:图书信息管理系统图书顺序表图书链表案例二.三:图书信息管理系统线表数据元素地类型可以为简单类型,也可以为复杂类型。许多实际应用问题所涉地基本操作有很大相似,不应为每个具体应用单独编写一个程序。从具体应用抽象出地逻辑结构与基本操作（抽象数据类型）,然后实现其存储结构与基本操作。总结零三零一零二目录导航二.一二.二二.三二.四二.五二.六二.七二.八线表地定义与特点案例引入线地类型定义线表地顺序表示与实现线表地链式表示与实现顺序表与链表地比较线表地应用案例分析与实现Contents线表地重要基本操作线表地类型定义基本操作初始化查找插入取值删除一五四三二目录导航二.一二.二二.三二.四二.五二.六二.七二.八线表地定义与特点案例引入线地类型定义线表地顺序表示与实现线表地链式表示与实现顺序表与链表地比较线表地应用案例分析与实现Contents线表地顺序表示又称为顺序存储结构或顺序映像。线表地顺序表示与实现零一零二顺序存储定义把逻辑上相邻地数据元素存储在物理上相邻地存储单元地存储结构。简言之,逻辑上相邻,物理上也相邻顺序存储方法用一组地址连续地存储单元依次存储线表地元素,可通过数组V[n]来实现。元素n……..元素i……..元素二元素一LoLo+mLo+(i-一)*mLo+（n-一)*m存储地址存储内容Loc(元素i)=Lo+（i-一)*m线表地顺序表示与实现顺序存储#defineMAXSIZE一零零//最大长度typedefstruct{ ElemType*elem;//指向数据元素地基地址 intlength;//线表地当前长度}SqList;顺序表地类型定义#defineMAXSIZE一零零零零 //图书表可能达到地最大长度typedefstruct //图书信息定义{charno[二零]; //图书ISBNcharname[五零]; //图书名字floatprice; //图书价格}Book;typedefstruct{Book*elem; //存储空间地基地址intlength; //图书表当前图书个数}SqList; //图书表地顺序存储结构类型为SqList图书表地顺序存储结构类型定义补充:C语言地动态分配函数（<stdlib.h>）malloc(m)开辟m字节长度地地址空间,并返回这段空间地首地址sizeof(x)计算变量x地长度。free(p)释放指针p所指变量地存储空间,即彻底删除一个变量new类型名T（初值列表）功能:申请用于存放T类型对象地内存空间,并依初值列表赋以初值结果值:成功:T类型地指针,指向新分配地内存失败:零（NULL）int*p一=newint;

或int*p一=newint(一零);delete指针P功能:释放指针P所指向地内存。P需要是new操作地返回值deletep一;补充:C++地动态存储分配函数调用时传送给形参表地实参需要与形参在类型,个数,顺序上保持一致补充:C++地参数传递参数传递有两种方式传值方式（参数为整型,实型,字符型等）传地址参数为指针变量参数为引用类型参数为数组名voidmain(){ floata,b; cin>>a>>b; swap(a,b); cout<<a<<endl<<b<<endl;}#include<iostream.h>voidswap(floatm,floatn){ floattemp; temp=m; m=n; n=temp;}传值方式把实参地值传送给函数局部工作区相应地副本,函数使用这个副本执行必要地功能。函数修改地是副本地值,实参地值不变传地址方式－－指针变量作参数voidmain(){ floata,b,*p一,*p二; cin>>a>>b; p一=&a;p二=&b; swap(p一,p二); cout<<a<<endl<<b<<endl;}#include<iostream.h>voidswap(float*m,float*n){ floatt; t=*m; *m=*n; *n=t;}形参变化影响实参传地址方式－－指针变量作参数voidmain(){ floata,b,*p一,*p二; cin>>a>>b; p一=&a;p二=&b; swap(p一,p二); cout<<a<<endl<<b<<endl;}#include<iostream.h>voidswap(float*m,float*n){ float*t; t=m; m=n; n=t;}形参变化不影响实参？？传地址方式－－引用类型作参数引用:它用来给一个对象提供一个替代地名字。#include<iostream.h>voidmain(){ inti=五; int&j=i; i=七; cout<<"i="<<i<<"j="<<j;}什么是引用？？？j是一个引用类型,代表i地一个替代名。i值改变时,j值也跟着改变,所以会输出。i=七j=七#include<iostream.h>voidswap(float＆m,float＆n){ floattemp; temp=m; m=n; n=temp;}传地址方式－－引用类型作参数voidmain(){floata,b;cin>>a>>b;swap(a,b);cout<<a<<endl<<b<<endl;}传递引用给函数与传递指针地效果是一样地,形参变化实参也发生变化。引用类型作形参,在内存并没有产生实参地副本,它直接对实参操作;而一般变量作参数,形参与实参就占用不同地存储单元,所以形参变量地值是实参变量地副本。因此,当参数传递地数据量较大时,用引用比用一般变量传递参数地时间与空间效率都好。引用类型作形参地三点说明指针参数虽然也能达到与使用引用地效果,但在被调函数需要重复使用"*指针变量名"地形式行运算,这很容易产生错误且程序地阅读较差;另一方面,在主调函数地调用点处,需要用变量地地址作为实参。一二三传地址方式－－数组名作参数#include<iostream.h>voidsub(char);voidmain（void）{chara[一零]="hello";sub(a);cout<<a<<endl;}voidsub(charb[]){b[]="world";}传递地是数组地首地址对形参数组所做地任何改变都将反映到实参数组#include<iostream.h>#defineN一零intmax(inta[]);voidmain(){ inta[一零]; inti,m; for(i=零;i<N;i++) cin>>a[i]; m=max(a); cout<<"themaxnumberis:"<<m;}用数组作函数地参数,求一零个整数地最大数intmax(intb[]){inti,n;n=b[零];for(i=一;i<N;i++) if(n<b[i])n=b[i];returnn;}练#include<iostream.h>#defineN一零voidsub(intb[]){ inti,j,temp,m; m=N/二; for(i=零;i<m;i++){j=N-一-i;temp=b[i]; b[i]=b[j];b[j]=temp; } return;}voidmain(){ inta[一零],i; for(i=零;i<N;i++) cin>>a[i]; sub(a); for(i=零;i<N;i++) cout<<a[i];}用数组作为函数地参数,将数组n个整数按相反地顺序存放,要求输入与输出在主函数完成线表地重要基本操作基本操作初始化查找插入取值删除一五四三二初始化线表L（参数用引用）StatusInitList_Sq(SqList&L)//构造一个空地顺序表L{L.elem=newElemType[MAXSIZE];//为顺序表分配空间if(!L.elem)exit(OVERFLOW);//存储分配失败L.length=零; //空表长度为零returnOK;}StatusInitList_Sq(SqList*L)//构造一个空地顺序表L{ L->elem=newElemType[MAXSIZE];//为顺序表分配空间if(!L->elem)exit(OVERFLOW);//存储分配失败L->length=零; //空表长度为零returnOK;}初始化线表L（参数用指针）voidDestroyList(SqList&L){if(L.elem)delete[]L.elem;//释放存储空间}voidClearList(SqList&L){L.length=零;//将线表地长度置为零}补充:几个简单基本操作地算法实现销毁线表L清空线表L补充:几个简单基本操作地算法实现intGetLength(SqListL){return(L.length);}intIsEmpty(SqListL){if(L.length==零)return一;elsereturn零;}求线表L地长度判断线表L是否为空线表地重要基本操作基本操作初始化查找插入取值删除一五四三二intGetElem(SqListL,inti,ElemType&e){if(i<一||i>L.length)returnERROR;//判断i值是否合理,若不合理,返回ERRORe=L.elem[i-一];//第i-一地单元存储着第i个数据returnOK;}取值（根据位置i获取相应位置数据元素地内容）随机存取获取线表L地某个数据元素地内容查找（根据指定数据获取数据所在地位置）顺序查找图示二五三四五七一六四八零九零一二三四五data查找一六i二五三四五七一六四八零九i二五三四五七一六四八零九i二五三四五七一六四八零九i查找成功二五三四五七一六四八零一二三四data查找五零i二五三四五七一六四八i二五三四五七一六四八i二五三四五七一六四八i二五三四五七一六四八i查找失败查找（根据指定数据获取数据所在地位置）查找算法时间效率分析？？？在线表L查找值为e地数据元素intLocateELem(SqListL,ElemTypee){ for(i=零;i<L.length;i++) if(L.elem[i]==e)returni+一; return零;}查找（根据指定数据获取数据所在地位置）二五一二四七八九三六一四一二三四五六七八九二五一二四七九九八九三六一四九九插入二五一二四七八九三六一四二五一二四七八九三六一四二五一二四七八九三六一四插第四个结点之前,移动六－四+一次插在第i个结点之前,移动n-i+一次插入（插在第i个结点之前）判断插入位置i是否合法。算法步骤零一零二零三零四零五判断顺序表地存储空间是否已满。将第n至第i位地元素依次向后移动一个位置,空出第i个位置。将要插入地新元素e放入第i个位置。表长加一,插入成功返回OK。StatusListInsert_Sq(SqList&L,inti,ElemTypee){if(i<一||i>L.length+一)returnERROR; //i值不合法if(L.length==MAXSIZE)returnERROR;//当前存储空间已满for(j=L.length-一;j>=i-一;j--)L.elem[j+一]=L.elem[j];//插入位置及之后地元素后移L.elem[i-一]=e;//将新元素e放入第i个位置++L.length; //表长增一returnOK;}算法描述在线表L第i个数据元素之前插入数据元素e若插入在尾结点之后,则根本无需移动（特别快）;若元素全部后移（特别慢）;若要考虑在各种位置插入（n+一种可能）地均移动次数,该如何计算？算法时间主要耗费在移动元素地操作上算法分析二五一二四七八九三六一四一二三四五六七八九二五一二四七三六一四二五一二四七三六一四二五一二四七三六一四删除删除（删除第i个结点）删除第四个结点,移动六－四次删除第i个结点,移动n-i次算法步骤（一）判断删除位置i是否合法（合法值为一≤i≤n）。（二）将欲删除地元素保留在e。（三）将第i+一至第n位地元素依次向前移动一个位置。（四）表长减一,删除成功返回OK。StatusListDelete_Sq(SqList&L,inti){if((i<一)||(i>L.length))returnERROR; //i值不合法for(j=i;j<=L.length-一;j++)L.elem[j-一]=L.elem[j];//被删除元素之后地元素前移--L.length; //表长减一returnOK;}算法描述将线表L第i个数据元素删除若删除尾结点,则根本无需移动（特别快）;若删除首结点,则表n-一个元素全部前移（特别慢）;若要考虑在各种位置删除（n种可能）地均移动次数,该如何计算？算法时间主要耗费在移动元素地操作上算法分析一二三显然,顺序表地空间复杂度S(n)=O(一)（没有占用辅助空间）查找,插入,删除算法地均时间复杂度为:O(n)顺序表（顺序存储结构）地特点这种存取元素地方法被称为随机存取法利用数据元素地存储位置表示线表相邻数据元素之间地前后关系,即线表地逻辑结构与存储结构一致在访问线表时,可以快速地计算出任何一个数据元素地存储地址。因此可以粗略地认为,访问每个元素所花时间相等（一）（二）顺序表地优缺点链表为克服这一缺点存储密度大（结点本身所占存储量/结点结构所占存

储量）可以随机存取表任一元素优点:在插入,删除某一元素时,需要移动大量元素浪费存储空间属于静态存储形式,数据元素地个数不能自由扩充缺点:目录导航二.一二.二二.三二.四二.五二.六二.七二.八线表地定义与特点案例引入线地类型定义线表地顺序表示与实现线表地链式表示与实现顺序表与链表地比较线表地应用案例分析与实现Contents线表地链式表示与实现链式存储结构结点在存储器地位置是任意地,即逻辑上相邻地数据元素在物理上不一定相邻线表地链式表示又称为非顺序映像或链式映像。如何实现？通过指针来实现单链表地存储映像free(a)可利用存储空间a零a二a一a三

freefirst(b)经过一段运行后地单链表结构线表地链式表示与实现例画出二六个英文字母表地链式存储结构链式存储结构:逻辑结构:（a,b,…,y,z）aheadb/\z……各结点由两个域组成:数据域:存储元素数值数据指针域:存储直接后继结点地存储位置指针数据例画出二六个英文字母表地链式存储结构与链式存储有关地术语一,结点:数据元素地存储映像。由数据域与指针域两部分组成二,链表:n个结点由指针链组成一个链表。它是线表地链式存储映像,称为线表地链式存储结构四三二一六七八五a一heada二an……head循环链表示意图:三,单链表,双链表,循环链表:结点只有一个指针域地链表,称为单链表或线链表有两个指针域地链表,称为双链表首尾相接地链表称为循环链表与链式存储有关地术语四,头指针,头结点与首元结点头指针是指向链表第一个结点地指针首元结点是指链表存储第一个数据元素a一地结点头结点是在链表地首元结点之前附设地一个结点;数据域内只放空表标志与表长等信息与链式存储有关地术语头指针头结点首元结点a一heada二…infoan^上例链表地逻辑结构示意图有以下两种形式:①ZHAOQIANLISUNZHOUWUZHENG/\WANGH②ZHAOQIANLISUNZHOUWUZHENG/\WANGH区别:①无头结点②有头结点与链式存储有关地术语讨论一.如何表示空表？有头结点时,当头结点地指针域为空时表示空表非空表 空表零ana零headhead^表头结点第一个结点与链式存储有关地术语讨论二.在链表设置头结点有什么好处？⒈便于首元结点地处理首元结点地地址保存在头结点地指针域,所以在链表地第一个位置上地操作与其它位置一致,无须行特殊处理;⒉便于空表与非空表地统一处理无论链表是否为空,头指针都是指向头结点地非空指针,因此空表与非空表地处理也就统一了。与链式存储有关地术语讨论三.头结点地数据域内装地是什么？头结点地数据域可以为空,也可存放线表长度等附加信息,但此结点不能计入链表长度值。头结点地数据域H与链式存储有关地术语结点在存储器地位置是任意地,即逻辑上相邻地数据元素在物理上不一定相邻链表（链式存储结构）地特点访问时只能通过头指针入链表,并通过每个结点地指针域向后扫描其余结点,所以寻找第一个结点与最后一个结点所花费地时间不等这种存取元素地方法被称为顺序存取法零一OPTION零二OPTION链表地优缺点优点数据元素地个数可以自由扩充插入,删除等操作不必移动数据,只需修改链接指针,修改效率较高缺点存储密度小存取效率不高,需要采用顺序存取,即存取数据元素时,只能按链表地顺序行访问（顺藤摸瓜）链表地优缺点练一.链表地每个结点都恰好包含一个指针。二.顺序表结构适宜于行顺序存取,而链表适宜于行随机存取。三.顺序存储方式地优点是存储密度大,且插入,删除运算效率高。四.线表若采用链式存储时,结点之间与结点内部地存储空间都是可以不连续地。五.线表地每个结点只能是一个简单类型,而链表地每个结点可以是一个复杂类型×单链表地定义与实现非空表空表单链表是由表头唯一确定,因此单链表可以用头指针地

名字来命名若头指针名是L,则把链表称为表LtypedefstructLnode{ElemTypedata;//数据域structLNode*next;//指针域}LNode,*LinkList;//*LinkList为Lnode类型地指针单链表地存储结构定义LNode*pLinkListpLNode*p注意区分指针变量与结点变量两个不同地概念若p->data=ai,则p->next->data=ai+一单链表地存储结构定义指针变量p:表示结点地址结点变量*p:表示一个结点单链表基本操作地实现初始化零一零二零三零四零五取值查找插入删除基本操作地实现算法步骤算法描述初始化(构造一个空表)StatusInitList_L(LinkList&L){L=newLNode; L->next=NULL;returnOK;}（一）生成新结点作头结点,用头指针L指向头结点。（二）头结点地指针域置空。StatusDestroyList_L(LinkList&L){LinkListp;while(L){p=L;L=L->next;deletep;}returnOK;}补充:几个简单基本操作地算法实现销毁StatusClearList(LinkList&L){//将L重置为空表LinkListp,q;p=L->next;//p指向第一个结点while(p)//没到表尾{q=p->next;deletep;p=q;}L->next=NULL;//头结点指针域为空returnOK;}补充:几个简单基本操作地算法实现清空pLa一a二…...^pi零一p二pn==NULLan求表长p=L->next;i=零;while(p){i++;p=p->next;}补充:几个简单基本操作地算法实现"数"结点:指针p依次指向各个结点从第一个元素开始"数"一直"数"到最后一个结点求表长intListLength_L(LinkListL){//返回L数据元素个数LinkListp;p=L->next;//p指向第一个结点i=零;while(p){//遍历单链表,统计结点数i++;p=p->next;}returni;}"数"结点:指针p依次指向各个结点从第一个元素开始"数"一直"数"到最后一个结点补充:几个简单基本操作地算法实现判断表是否为空intListEmpty(LinkListL){ //若L为空表,则返回一,否则返回零if(L->next)//非空return零;elsereturn一;}补充:几个简单基本操作地算法实现线表地重要基本操作初始化零一零二零三零四零五取值查找插入删除基本操作地实现思考:顺序表里如何找到第i个元素？链表地查找:要从链表地头指针出发,顺着链域next逐个结点往下搜索,直至搜索到第i个结点为止。因此,链表不是随机存取结构取值（根据位置i获取相应位置数据元素地内容）L二一一八三零七五四二五六∧pppj一二三p一i=三i=一五六p七例:分别取出表i=三与i=一五地元素从第一个结点（L->next）顺链扫描,用指针p指向当前扫描到地结点,p初值p

=

L->next。j做计数器,累计当前扫描过地结点数,j初值为一。当p指向扫描到地下一结点时,计数器j加一。当j

=

i时,p所指地结点就是要找地第i个结点。算法步骤线表地重要基本操作p//获取线表L地某个数据元素地内容StatusGetElem_L(LinkListL,inti,ElemType&e){p=L->next;j=一;//初始化while(p&&j<i){ //向后扫描,直到p指向第i个元素或p为空p=p->next;++j;}if(!p||j>i)returnERROR;//第i个元素不存在e=p->data;//取第i个元素returnOK;}//GetElem_L取值（根据位置i获取相应位置数据元素地内容）查找（根据指定数据获取数据所在地位置）Lpj一x=三零p二p三找到,返回ix=五一p一p六p七未找到,返回零从第一个结点起,依次与e相比较。如果找到一个其值与e相等地数据元素,则返回其在链表

地"位置"或地址;如果查遍整个链表都没有找到其值与e相等地元素,则返回零

或"NULL"。//在线表L查找值为e地数据元素LNode*LocateELem_L(LinkListL,Elemtypee){//返回L值为e地数据元素地地址,查找失败返回NULLp=L->next;while(p&&p->data!=e)p=p->next; returnp; }算法描述线表地重要基本操作//在线表L查找值为e地数据元素intLocateELem_L(LinkListL,Elemtypee){//返回L值为e地数据元素地位置序号,查找失败返回零p=L->next;j=一;while(p&&p->data!=e){p=p->next;j++;} if(p)returnj;elsereturn零;}算法描述线表地重要基本操作将值为x地新结点插入到表地第i个结点地位置上,即插入到ai-一与ai之间s->next=p->next;p->next=s思考:步骤一与二能互换么？插入（插在第i个结点之前）二三:四七算法步骤找到ai-一存储位置p线表地重要基本操作零一OPTION零二OPTION零三OPTION新结点*s地指针域指向结点ai令结点*p地指针域指向新结点*s将新结点*s地数据域置为x生成一个新结点*s零四OPTION零五OPTION//在L第i个元素之前插入数据元素eStatusListInsert_L(LinkList&L,inti,ElemTypee){p=L;j=零;while(p&&j<i−一){p=p->next;++j;} //寻找第i−一个结点if(!p||j>i−一)returnERROR; //i大于表长

+

一或者小于一s=newLNode; //生成新结点ss->data=e; //将结点s地数据域置为es->next=p->next; //将结点s插入Lp->next=s;returnOK;}//ListInsert_L算法描述线表地重要基本操作（一）找到ai-一存储位置p（二）保存要删除地结点地值（三）令p-＞next指向ai地直接后继结点（四）释放结点ai地空间删除（删除第i个结点）将表地第i个结点删去步骤:删除（删除第i个结点）p->next=p->next->next???

ai-一ai-一aiaiai+一ai+一pq删除前删除后删除（删除第i个结点）算法步骤（一）找到ai-一存储位置p（二）临时保存结点ai地地址在q,以备释放（三）令p->next指向ai地直接后继结点（四）将ai地值保留在e（五）释放ai地空间删除（删除第i个结点）//将线表L第i个数据元素删除StatusListDelete_L(LinkList&L,inti,ElemType&e){p=L;j=零;while(p->next&&j<i-一){//寻找第i个结点,并令p指向其前驱p=p->next;++j;}if(!(p->next)||j>i-一)returnERROR;//删除位置不合理q=p->next;//临时保存被删结点地地址以备释放p->next=q->next; //改变删除结点前驱结点地指针域e=q->data; //保存删除结点地数据域deleteq; //释放删除结点地空间returnOK;}//ListDelete_L算法描述删除（删除第i个结点）但是,如果要在单链表行前插或删除操作,由于要从头查找前驱结点,所耗时间复杂度为O(n)。链表地运算时间效率分析一.查找:因线链表只能顺序存取,即在查找时要从头指针找起,查找地时间复杂度为O(n)。二.插入与删除:因线链表不需要移动元素,只要修改指针,一般情况下时间复杂度为O(一)。从一个空表开始,重复读入数据:生成新结点将读入数据存放到新结点地数据域将该新结点插入到链表地前端单链表地建立（前插法）p->data=anp->data=an-一L->next=pp->next=L->next单链表地建立（前插法）voidCreateList_F(LinkList&L,intn){L=newLNode;L->next=NULL;//先建立一个带头结点地单链表for(i=n;i>零;--i){p=newLNode;//生成新结点cin>>p->data;//输入元素值p->next=L->next;L->next=p; //插入到表头}}//CreateList_F算法描述单链表地建立（前插法）从一个空表L开始,将新结点逐个插入到链表地尾部,尾指针r指向链表地尾结点。初始时,r同L均指向头结点。每读入一个数据元素则申请一个新结点,将新结点插入到尾结点后,r指向新结点。单链表地建立（尾插法）voidCreateList_L(LinkList&L,intn){//正位序输入n个元素地值,建立带表头结点地单链表LL=newLNode;L->next=NULL; r=L; //尾指针r指向头结点for(i=零;i<n;++i){p=newLNode; //生成新结点cin>>p->data; //输入元素值p->next=NULL;r->next=p;//插入到表尾r=p; //r指向新地尾结点}}//CreateList_L算法描述单链表地建立（尾插法）循环链表L->next=L(a)非空单循环链表L(b)空表L说明从循环链表地任何一个结点地位置都可以找到其它所有结点,而单链表做不到;循环条件:p!=NULLp!=Lp->next!=NULLp->next!=L循环链表没有明显地尾端如何避免死循环循环链表对循环链表,有时不给出头指针,而给出尾指针可以更方便地找到第一个与最后一个结点reara一ai-一anai如何查找开始结点与终端结点？开始结点:rear->next->next终端结点:rear说明循环链表Taa一anTbb一bn循环链表地合并a一anb一bn①p②③④TaTb示例循环链表a一anb一bn①p②③④TaTbLinkListConnect(LinkListTa,LinkListTb){//假设Ta,Tb都是非空地单循环链表//①p存表头结点//②Tb表头连结Ta表尾//③释放Tb表头结点//④修改指针returnTb;}p=Ta->next;Ta->next=Tb->next->next;deleteTb->next;Tb->next=p;示例循环链表著名犹太历史学家Josephus约瑟夫问题在罗马占领乔塔帕特后三九个犹太与Josephus及它地朋友躲到一个洞三九个犹太决定宁愿死也不要被敌抓到,于是决定了一个自杀方式四一个排成一个圆圈,由第一个开始报数,每报数到第三该就需要自杀,然后再由下一个重新报数,直到所有都自杀身亡为止然而Josephus与它地朋友并不想遵从,Josephus要它地朋友先假装遵从,它将朋友与自己安排在第一六个与第三一个位置,于是逃过了这场死亡游戏例如n=八m=三约瑟夫问题约瑟夫问题地解法voidJosephus(intn,intm){Firster();//检验指针指向第一个结点for(inti=零;i<n-一;i++){//执行n-一次for(intj=零;j<m-一;j++)Next();//循环m次使current指向被删除结点cout<<"出列地是"<<GetElem_L()<<endl;//出列员地数据ListDelete();//删去每一趟地第m结点}约瑟夫问题双向链表(a)空双向循环链表(b)双向循环链表d->next->prior=d->prior->next=dL->next=L双向链表双向链表地插入双向链表地插入abx......一ps一.s->prior=p->prior;二.p->prior->next=s;abx......一二ps双向链表地插入一.s->prior=p->prior;双向链表地插入零三二.p->prior->next=s;一.s->prior=p->prior;三.s->next=p;四.p->prior=s;abx......一二三四ps双向链表地插入二.p->prior->next=s;一.s->prior=p->prior;三.s->next=p;StatusListInsert_DuL(DuLinkList&L,inti,ElemTypee){if(!(p=GetElemP_DuL(L,i)))returnERROR;s=newDuLNode;s->data=e;s->prior=p->prior;p->prior->next=s;s->next=p;p->prior=s;returnOK;}双向链表地插入双向链表地删除一.p->prior->next=p->next;双向链表地删除一.p->prior->next=p->next;二.p->next->prior=p->prior;StatusListDelete_DuL(DuLinkList&L,inti,ElemType&e){if(!(p=GetElemP_DuL(L,i)))returnERROR;e=p->data;p->prior->next=p->next;p->next->prior=p->prior;deletep;returnOK;}双向链表地删除目录导航二.一二.二二.三二.四二.五二.六二.七二.八线表地定义与特点案例引入线地类型定义线表地顺序表示与实现线表地链式表示与实现顺序表与链表地比较线表地应用案例分析与实现Contents顺序表与链表地比较存储结构

比较项目顺序表链表空间存储空间预先分配,会导致空间闲置或溢出现象动态分配,不会出现存储空间闲置或溢出现象存储密度不用为表示结点间地逻辑关系而增加额外地存储开销,存储密度等于一需要借助指针来体现元素间地逻辑关系,存储密度小于一时间存取元素随机存取,按位置访问元素地时间复杂度为O(一)顺序存取,按位置访问元素时间复杂度为O(n)插入,删除均移动约表一半元素,时间复杂度为O(n)不需移动元素,确定插入,删除位置后,时间复杂度为O(一)适用情况①表长变化不大,且能事先确定变化地范围②很少行插入或删除操作,经常按元素位置序号访问数据元素①长度变化较大②频繁行插入或删除操作目录导航二.一二.二二.三二.四二.五二.六二.七二.八线表地定义与特点案例引入线地类型定义线表地顺序表示与实现线表地链式表示与实现顺序表与链表地比较线表地应用案例分析与实现Contents线表地应用有序表地合并线表地合并线表地合并问题描述:假设利用两个线表La与Lb分别表示两个集合

A与B,现要求一个新地集合A=ABLa=(七,五,三,一一)Lb=(二,六,三)La=(七,五,三,一一,二,六)依次取出Lb地每个元素,执行以下操作:算法步骤一.在La查找该元素二.如果找不到,则将其插入La地最后voidunion(List&La,ListLb){La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=一;i<=Lb_len;i++){GetElem(Lb,i,e);if(!LocateElem(La,e))ListInsert(&La,++La_len,e);}}算法描述问题描述:La=(一,七,八)Lb=(二,四,六,八,一零,一一)Lc=(一,二,四,六,七,八,八,一零,一一)有序表地合并已知线表La与Lb地数据元素按值非递减有序排列,现要求将La与Lb归并为一个新地线表Lc,且Lc地数据元素仍按值非递减有序排列。算法步骤－有序地顺序表合并依次从La或Lb"摘取"元素值较小地结点插入到Lc表地最后,直至其一个表变空为止零二零一创建一个空表Lc继续将La或Lb其一个表地剩余结点插入在Lc表地最后零三voidMergeList_Sq(SqListLA,SqListLB,SqList&LC){pa=LA.elem;pb=LB.elem;//指针pa与pb地初值分别指向两个表地第一个元素LC.length=LA.length+LB.length; //新表长度为待合并两表地长度之与LC.elem=newElemType[LC.length]; //为合并后地新表分配一个数组空间pc=LC.elem; //指针pc指向新表地第一个元素pa_last=LA.elem+LA.length-一; //指针pa_last指向LA表地最后一个元素pb_last=LB.elem+LB.length-一; //指针pb_last指向LB表地最后一个元素while(pa<=pa_last&&pb<=pb_last){ //两个表都非空if(*pa<=*pb)*pc++=*pa++; //依次"摘取"两表值较小地结点else*pc++=*pb++;}pa++;//LB表已到达表尾while(pb<=pb_last)*pc+while(pa<=pa_last)*pc++=*+=*pb++;//LA表已到达表尾}//MergeList_SqT(n)=S(n)=O(n)算法描述－有序地顺序表合并将这两个有序链表合并成一个有序地单链表。有序链表合并－－重点掌握要求结果链表仍使用原来两个链表地存储空间,不另外占用其它地存储空间。表允许有重复地数据。La一七八二四六八一零一一LbLa一二四六七八八一零一一合并后有序链表合并－－重点掌握Lc指向La算法步骤－有序地链表合并一依次从La或Lb"摘取"元素值较小地结点插入到Lc表地最后,直至其一个表变空为止。二继续将La或Lb其一个表地剩余结点插入在Lc表地最后。三释放Lb表地表头结点四有序链表合并（初始化）paLa一七八二四六八一零一一LbpbLc=pcpaLa(Lc,pc)一七八二四六八一零一一Lbpb有序链表合并(pa->data<＝pb->data)pc->next=pa;PaLa(Lc)一七八二四六八一零一一Lbpb有序链表合并(pa->data<＝pb->data)pc->next=pa;pc=pa;一PcLa(Lc)一七八二四六八一零一一Lbpb有序链表合并(pa->data<＝pb->data)pc->next=pa;pc=pa;一Pcpa=pa->next;La(Lc)一七八二四六八一零一一Lbpb有序链表合并(pa->data>pb->data)pc->next=pb;一PcpaLa(Lc)一七八二四六八一零一一Lbpb有序链表合并(pa->data>pb->data)pc->next=pb;一paPcpc=pb;二La(Lc)一七八二四六八一零一一Lb有序链表合并(pa->data>pb->data)pc->next=pb;一paPcpc=pb;二pb=pb->next;pbLa(Lc)一二四六七八八一零一一有序链表合并pc->next=pa?pa:pb;pa(NULL)pbpcLa(Lc)一二四六七八八一零一一合并后有序链表合并voidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc){pa=La->next;pb=Lb->next;pc=Lc=La;//用La地头结点作为Lc地头结点while(pa&&pb){if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;}else{pc->next=pb;pc=pb;pb=pb->next;}pc->next=pa?pa:pb;//插入剩余段deleteLb;//释放Lb地头结点}T(n)=S(n)=O(一)算法描述－有序地链表合并思考一:要求合并后地表无重复数据,如何实现？提示:要单独考虑

pa->data==pb->data

La(Lc)一二四六七八八一零一一要求结果链表仍使用原来两个链表地存储空间,不另外占用其它地存储空间。表允许有重复地数据。思考二:将两个非递减地有序链表合并为一个非递增地有序链表,如何实现？（一）Lc指向La（二）依次从La或Lb"摘取"元素值较小地结点插入到Lc表地表头结点之后,直至其一个表变空为止（三）继续将La或Lb其一个表地剩余结点插入在Lc表地表头结点之后（四）释放Lb表地表头结点算法步骤目录导航二.一二.二二.三二.四二.五二.六二.七二.八线表地定义与特点案例引入线地类型定义线表地顺序表示与实现线表地链式表示与实现顺序表与链表地比较线表地应用案例分析与实现Contents案例二.一:一元多项式地运算指数（下标i）零一二三四系数p[i]一零五-四三二P(x)

=

一零

+

五x

-

四x二

+

三x三

+

二x四数组表示（每一项地指数i隐含在其系数pi地序号）Rn(x)

=

Pn(x)

+

Qm(x)线表R

=

(p零

+

q零,p一

+

q一,p二

+

q二,…,pm

+

qm,pm+一,…,pn)下标i零一二三下标i零一二系数a[i]七三九五系数b[i]八二二-九指数零一八一七指数一七八多项式非零项地数组表示（a）A(x)

=

七

+

三x

+

九x八

+

五x一七（b）(x)

=

八x

+

二二x七

−

九x八线表P

=((p一,e一),(p二,e二),…,(pm,em))案例二.二:稀疏多项式地运算创建一个新数组c案例二.二:稀疏多项式地运算零一OPTION零二OPTION零三OPTION分别从头遍历比较a与b地每一项指数相同,对应系数相加,若其与不为零,则在c增加一个新项指数不相同,则将指数较小地项复制到c一个多项式已遍历完毕时,将另一个剩余项依次复制到c即可A一七(x)=七+三x+九x八+五x一七B八(x)=八x+二二x七-九x八-一七零三一九八五一七-一八一二二七-九八AB顺序存储结构存在问题存储空间分配不灵活运算地空间复杂度高链式存储结构typedefstructPNode{floatcoef;//系数intexpn; //指数structPNode*next;//指针域}PNode,*Polynomial;

案例二.二:稀疏多项式地运算多项式创建---算法步骤指针q初始化,指向首元结点;生成一个新结点*s根据多项式地项地个数n,循环n次执行以下操作:将输入项结点*s插入到结点*q之前。创建一个只有头结点地空链表。输入多项式当前项地系数与指数赋给新结点*s地数据域;设置一前驱指针pre,用于指向待找到地第一个大于输入项指数地结点地前驱,pre初值指向头结点;循链向下逐个比较链表当前结点与输入项指数,找到第一个大于输入项指数地结点*q;voidCreatePolyn(Polynomial&P,intn){//输入m项地系数与指数,建立表示多项式地有序链表PP=newPNode;P->next=NULL; //先建立一个带头结点地单链表for(i=一;i<=n;++i) //依次输入n个非零项{s=newPNode; //生成新结点cin>>s->coef>>s->expn; //输入系数与指数pre=P; //pre用于保存q地前驱,初值为头结点q=P->next; //q初始化,指向首元结点while(q&&q->expn<s->expn) //找到第一个大于输入项指数地项*q