结点ai内存不足

2014/4/71数据结构Ch.
2线性表计算机学院肖明军Email:xiaomj@ustc.
edu.
cnhttp://staff.
ustc.
edu.
cn/~xiaomj§2.
1线性表的逻辑结构线性表:由n(n≥0)个结点a1,…,an组成的有限序列记作:L=(a1,a2,…,an),属性:长度----结点数目n,n=0时为空表a般是同类型2ai----一般是同一类型§2.
1线性表的逻辑结构逻辑特征当L≠Ф时,①有且仅有1个开始结点a1和1个终端结点an,a1仅有一直接后继,an仅有一直接前驱②内部结点(2≤i≤1)均有直接前驱和直接3②内部结点ai(2≤i≤n-1)均有一直接前驱ai-1和一直接后继ai+1结点之间的逻辑关系是由位置次序决定的,ai出在表的第i个位置.
该关系是线性的(全序的),故称L为线性表.
§2.
1线性表的逻辑结构举例:英文字母表(A,B,…,Z)扑克牌点数(2,3,…,10,J,Q,K,A)学生成绩表等ai----抽象符号.
具体应用可能是一个结构类型的对象4ai抽象符号.
具体应用可能是个结构类型的对象线性表是一种相当灵活的数据结构,其长度可根据需要增长或缩短基本运算:InitList(L),ListLength(L),GetNode(L,i)…等复杂运算可通过基本运算去构造§Ch.
2线性表线性表的抽象数据类型定义ADTList{数据对象:D={ai|ai∈ElemSet,i=1,2,…,n,n≧0}数据关系:R={|ai-1ai∈Di=23n}数据关系:R={|ai-1,ai∈D,i=2,3,…,n}基本操作:InitList(&L)操作结果:构造一个空的线性表L;ListLength(L)初始条件:线性表L已存在;操作结果:若L为空表,则返回TRUE,否则返回FALSE;§Ch.
2线性表….
GetElem(L,i,&e)初始条件:线性表L已存在,1≦i≦ListLength(L);操作结果:用e返回L中第i个数据元素的值;ListInsert(L,i,&e)初始条件:线性表L已存在,1≦i≦ListLength(L);操作结果:在线性表L中的第i个位置插入元素e;…}ADTList2014/4/72§2.
2线性表的顺序存储结构§2.
2.
1顺序表定义:将线性表中结点按逻辑次序依次存储在一组地址连续的存储单元里.
由此存储的L称为顺序表.
地址计算7地址计算:设结点大小为l个单元,其中第i个单元为该结点地址Loc(ai)=Loc(a1)+(i-1)*lL的基地址§2.
2.
1顺序表特征:①随机存储②只需存储结点.
无需用辅助空间存储逻辑关系.
但空闲大小不易确定,易浪费空间③静态分配(当用向量实施时)亦可动态申请空间,但copy成本大(扩充表时).
8§2.
2.
1顺序表实现:用向量实现#defineListSize100;//假定typedefintDataType;//依具体使用定typedefstruct{DataTypedata[ListSize];//存放结点9DataTypedata[ListSize];//存放结点intlength;//当前表长n}Seglist;§2.
2.
2顺序表上实现的基本运算1.
插入基本思想:在L的第i个位置上插入一新结点x(1≤i≤n+1).
x10(a1,…,ai-1,ai,ai+1,…,an)→(a1,…,ai-1,x,ai,…,an+1)为保持结点的物理顺序和逻辑顺序一致,须:①将an,…,ai依次后移1位,空出ith位置②插入x③表长加1§2.
2.
2顺序表上实现的基本运算算法:voidInsertList(SegList*L,DataTypex,inti){intj;//注意c数组1st位置的下标为0.
ai的位置是data[i-1].
if(iL->length+1)//1≤i≤n+1是合法插入位置Error("Positionerror!
");11Error(Positionerror!
);if(L->length>=ListSize)Error("Overflow");//溢出for(j=L->length-1;j>=i-1;j--)L->data[j+1]=L->data[j];//结点后移L->data[i-1]=x;//插入xL->length++;//长度加1};§2.
2.
2顺序表上实现的基本运算分析:循环后移,移动节点数为n-i+1,时间与相关①最好情况:当i=n+1,不移动O(1)常数时间解释O(n0)与n无关②最坏情况:当i=1,全部后移O(n)12②最坏情况:当i1,全部后移O(n)③平均性能:设任何合法位置上插入的概率相等:(位置i插入的概率)当位置i确定是,后移次数亦确定:n-i+1.
故表中平均移动结点为:即插入式,平均移动表中一半结点2014/4/73§2.
2.
2顺序表上实现的基本运算2.
删除基本思想:在L中删除ith结点(1≤i≤n).
(a1,…,ai-1,ai,ai+1,…,an)→(a1,…,ai-1,ai+1,…,an-1)13为保持物理与逻辑顺序一致,须:①前移:将ai+1,…,an依次前移1位,填补删除ai留下的空间②表长减1§2.
2.
2顺序表上实现的基本运算算法:voidDeleteList(SegList*L,inti){intj,n=L->length;if(in)Error("Positionerror!
");//非法位置for(j=i;jdata[j-1]=L->data[j];//结点后移L->length--;//长度减1};§2.
2.
2顺序表上实现的基本运算分析:前移次数与n和i相关,移动节点数n-i.
①最好情况:当i=n,不移动O(1)②最坏情况:当i=1,前移n-1次O(n)15③平均性能:§2.
3线性表的链式存储结构顺序表缺点:移动节点,不利于动态插入和删除优点:随机存取,得到第i个结点的时间为O(1)与表长和位置无关§231单链表(线性链表)16§2.
3.
1单链表(线性链表)存储方法:用一组任意存储单元来存放结点(可连续,亦可不连续);为表示逻辑关系,须存储后继或前驱信息§2.
3.
1单链表(线性链表)结点结构数据域指针域(链域)next指向该结点的后继(的地址)表示17①开始结点无前驱,用头指针表示②终端结点无后继,next域为空(NULL)§2.
3.
1单链表(线性链表)逻辑状态头指针唯一确定一个单链表存储状态见图2518存储状态见图2.
5特征①非顺序存取②用指针表示结点间逻辑关系③动态分配2014/4/74§2.
3.
1单链表(线性链表)实现:typedefstructnode{//结点类型定义DataTypedata;//数据域structnode*next;//指针域}ListNode;19}ListNode;typedefListNode*LinkList;//链表类型定义ListNode*p;//结点定义LinkListhead;//链表头指针定义§2.
3.
1单链表(线性链表)结点变量和指针变量20指针变量p:值为结点地址结点变量*p:值为结点内容动态申请,垃圾收集§2.
3.
1单链表(线性链表)1.
建立单链表(1)头插法:从空表开始,重复读入数据:申请新结点、插入表头,直至输入结束.
表次序与输入次序相反.
21表次序与输入次序相反.
处理自然简单§2.
3.
1单链表(线性链表)(2)尾插法:设为指针r指向当前链尾(初值为NULL)22①申请新结点s②将读入数据写入③新结点链到表尾(应注意边界条件)④修改尾指针r§2.
3.
1单链表(线性链表)为简便起见,设结点数据类型DataType为char,输入字符,换行符结束LinkListCreateList(void){//ch,head,r为局部量head=r=NULL;//开始为空表23while((ch=getchar(n'){s=(ListNode*)malloc(sizeof(ListNode));//①s->data=ch;//②if(head==NULL)//插入空表head=s;//新结点插入空表(边界),r为空§2.
3.
1单链表(线性链表)elser->next=s;//③r=s;//④}if(r!
=NULL)r->next=NULL;//非空表,终端结点指针为空无后继returnhead;24returnhead;}边界条件处理:空表和非空表处理不一致简化方法:引入头结点(哨兵),其中data域可做它用(如表长度)2014/4/75§2.
3.
1单链表(线性链表)LinkListCreateList(void){//用尾插法建立带头结点的单链表25charch;LinkListhead=(Linklist)malloc(sizeof(ListNode));//生成头结点ListNode*s,*r;r=head;//为指针初始指向头结点while(){s=(ListNode*)malloc(sizeof(ListNode));s->data=ch;§2.
3.
1单链表(线性链表)r->next=s;r=s;}r->next=NULL;//终端结点指针置空,或空表时头结点指针置空returnhead;}26}Note:为简化起见,,申请结点时不判是否申请到时间:O(n)§2.
3.
1单链表(线性链表)2.
查找①按值查找找链表中关键字为k的结点②按序号查找合法位置1≤i≤n头结点可看作第0个结点27合法位置1≤i≤n.
头结点可看作第0个结点返回第i个结点的地址,即找到第i-1个结点,返回其next域思想:顺链扫描:p----当前扫描到的结点,初始指向头结点j----计算器.
累加扫描到的结点,初始值为0每次加1,直至j=i为止,p指向ith结点算法§2.
3.
1单链表(线性链表)ListNode*GetNode(LinkListhead,inti){//在链表(有头结点)中查找ith结点找到(0≤i≤n)则返回该结点的存储//位置,否则返回NULLintj;ListNode*p;p=head;j=0;//头结点开始扫描while(p->next&&jnext为空或j=i为止p=p->next;j++;}28}if(i==j)returnp;//找到elsereturnNULL;//当in时未找到}时间分析循环终止条件是搜索到表尾或j=i.
复杂度最多为i,与查找位置相关.
//i=0,找头结点§2.
3.
1单链表(线性链表)3.
插入问题:将值为x的结点插到表的第i个结点位置上.
即在ai-1和ai之间插入.
故须找到第ai-1个结点的地址p,然后生成新结点*s,将其链到ai-1之后,ai之前.
29§2.
3.
1单链表(线性链表)voidInsertList(LinkListhead,DataTypex,inti){//带头结点1≤i≤n+1ListNode*p;p=GetNode(head,i-1);//寻找第i-1个结点①if(p==NULL)//in+1时插入位置i有错Error("positionerror");s=(ListNode*)malloc(sizeof(ListNode));//②s>data=x;//③30s->data=x;//③s->next=p->next;//④p->next=s;//⑤}思考:若无头结点,边界如何处理时间:主要是GetNodeO(n)合法位置1≤i≤n+1GetNode:0≤i≤n2014/4/76§2.
3.
1单链表(线性链表)4.
删除删ith结点.
首先找ai-1.
31§2.
3.
1单链表(线性链表)voidDeleteList(LinkListhead,inti){//合法位置是1≤i≤np=GetNode(head,i-1);//①if(!
p||!
(p->next))//in时删除位置有错Error("positionerror");32(p);r=p->next;//②令r指向被删结点aip->next=r->next;//③将ai从链上摘下free(r);//④释放ai}§2.
3.
1单链表(线性链表)正确性分析①inext为空③i>n+1时GetNode返回p为空33③i>n+1时,GetNode返回p为空时间O(n)结论:链表上插、删无须移动结点,仅需修改指针§2.
3.
2循环链表(单)首尾相接:不增加存储量,只修改连接方式34优点:从任一结点出发可访问到表中任一其它结点,如找前驱(O(n))遍历表的终止方式:p为空或p->next为空p=head或p->next=head§2.
3.
2循环链表(单)仅设尾指针更方便:访问开始结点和终端结点的时间均为O(1).
例如:合并两个单循环链表的时间为O(1),但用头指针表示时:T(mn)=O(max(mn))或O(min(mn))35T(m,n)=O(max(m,n))或O(min(m,n))§2.
3.
3双链表(循环)单链表只有后向链,找一结点的后继时间为O(1),但找前驱费时,若经常涉及找前驱和后继,则可选双链表.
362014/4/77§2.
3.
3双链表(循环)结构特征对称结构:若p不空,则p->prior->next=p=p->next->prior优点:37①找一结点前驱和找一结点后继同样方便②删*p本身和删*p的后继同样方便§2.
3.
3双链表(循环)例1:前插s->data=x;//②s->prior=p->prior;//③s->next=p;//④p->prior->next=s;//⑤p->prior=s;//⑥38例2:删*pp->prior->next=p->next;p->next->prior=p->prior;free(p);§2.
3.
4静态链表上述链表是由指针实现的,其中结点分配和回收是由系统实现的,系统提供了malloc和free动态执行,故称为动态链表.
动态----程序执行时系统动态分配和回收静态链表39静态链表----先分配大空间作为备用结点空间(即存储池)用下标(亦称游标cursor)模拟指针,自定义分配和释放结点函数§2.
3.
4静态链表1.
定义#definenil0//空指针#defineMaxSize1000//可容纳的结点数typedefstruct{40DataTypedata;intnext;}node,NodePool[MaxSize];typedefintStaticList;§2.
3.
4静态链表2.
基本操作(模拟动态链表)①初始化将整个表空间链成一个备用链表,只做一次.
voidInitiate(NodePoolspace){//备用链表的头结点位置为space[0]41//备用链表的头结点位置为space[0]for(i=0;inext结点后继位置space[ptr].
next§2.
4顺序表和链表之比较作业1.
为什么在单循环链表中设置尾指针比设置头指针更好2.
写一个算法将单链表中值重复的结点删除使得的结表中各结点值均相,使所得的结果表中各结点值均不相同.