数据结构与算法线性表

·线性表的定义及ADT

·线性表的顺序存储结构

·线性表的链接存储结构

·单向循环链表

·双链表、双向循环链表

·一元多项式的加法目录第二章线性表1、线性表的定义及ADT1、线性结构的定义：空或者只有一个结点。或者1、存在唯一的一个被称之为”第一个“的结点。 2、存在唯一的一个被称之为”最后一个“的结点。 3、除第一个结点之外，每个结点均只有一个前驱结点。 4、除最后一个结点之外，每个结点均只有一个后继结点。分为以下几大类：·线性表：进通过它们之间的相对位置，确定它们之间的相互关系的线性结构。 e.g:序列：a1、a2、a3…an-1、an·分类表·时间有序表·频率有序表·序列2、结点或数据元素： 结点（数据元素）：由多个数据项构成，每个数据项表示该结点的某种性质。如：学生登记表中的每个学生结点，由学号、姓名、性别、系别……等构成。 存放在外存中的结点通常称之为记录。1、线性表的定义及ADT3、线形表List的ADTADT2.1:线性表List的ADT Element:{xi|xiElemSet,i=1,2,3,……n,n>0}或

Φ;ElemSet为结点集合。 Relation:{<xi,xi+1>|xi,xi+1ElemSet,i=1,2,3,……n-1},x1为首结点，xn为尾结点。 Operations: Constructor

前提: 无或指定List的规模。

结果: 分配相应空间及初始化。 Clear

前提: 无。

结果：

删除表List中的所有结点并进行初始化。 IsEmpty

前提：

无

结果：

表List为空返回True，否则返回False。 IsFull 前提：

无

结果：

表List为满返回True，否则返回False。1、线性表的定义及ADT3、线形表List的ADT Length

前提：

无

结果：

返回表List中的结点个数。 Get

前提：

表List非空且已知结点序号无

结果：

返回相应结点的数据值。 Prior 前提：

表List非空，已知结点序号且该结点非首结点。

结果：

返回其直接前驱结点的序号。 Next 前提：

表List非空，已知结点序号且该结点非尾结点

结果：

返回其直接后继结点的序号。 Find 前提：

表List非空，已知结点的数据值。 结果：

查找成功，返回相应结点序号，否则返回查找失败标志 Insert 前提：

已知待插入的数据值以及插入位置。 结果：

插入具有该数据值的结点，表List的结点个数增大1。 Delete 前提：

表List非空，已知被删结点的数据值。 结果：

首先查找相应结点，查找成功则删除该结点，表List的结点个数将减少1。否则返回删除失败标志。2、线性表的顺序存储结构1、物理存储位置的计算： ·顺序表示：在物理位置上紧靠在一起。如用数组表示线性表。 ·设第一个结点的存储地址为LOC(a0),余类推。设每个结点占用L个单元。则：an－1ai-1a1a0ai

LOC(ai) =LOC(ai-1)+L =LOC(ai-2)+2L =LOC(ai-i)+i*L =LOC(a0)+i*L ·随机存取：访问任何一个数据元素或结点花费同样多时间。2、线性表的顺序存储结构template<classElemType>classSeqList{private:ElemType*elem;//顺序表存储数组，存放实际的数据结点。

intlength;//顺序表中的结点个数，亦称表的长度。intMaxSize; //顺序表的的最大可能的长度。

public:SeqList(intInitSize); //构造函数~SeqList(); //析构函数

voidClear(); //清空顺序表boolIsEmpty()const{return(length==0);} //表为空返回TRUE,否则返回FALSE。boolIsFull()const{return(length==MaxSize)};//表是否已经满，满则返回TRUE，否则FALSE。intLength()const;//表的长度ElemTypeGet(inti)const; //返回第i个结点的值intNext(inti)const;//若第i个结点的直接后继结点存在，返回其下标，//否则返回0intPrior(inti)const;//若第i个结点的直接前驱结点存在，返回其下标， //否则返回0

intFind(ElemTypee);//返回值等于e的结点的序号，无则返回02、线性表的顺序存储结构template<classElemType>classSeqList{

….

intFind(ElemTypee);//返回值等于e的结点的序号，无则返回0intInsert(inti,constElemType&e);//在第i个位置上插入新的结点（值为e），并//使原来的第i个结点至最后一个结点的序号依次加1。//插入成功返回1，否则为0intDelete(ElemType&e,inti);//若第i个结点存在，删除并将其值放入e, //若i非法，则删除失败，返回0。};

注意：本处惯例，0号单元不用。Length既是顺序表的当前结点个数，同时又是尾结点的指针。2、线性表的顺序存储结构2、主要函数的实现 ·顺序表的创建：template<classElemType>SeqList<ElemType>::SeqList(intInitSize){ //构造函数if(InitSize>0){elem=newElemType[InitSize];//申请连续空间，返回空间首地址。Exception(!elem,”thereisnospaceinmemory”)//若申请空间失败，则程序中断。length=0;MaxSize=InitSize-1; }}251247998936length2、线性表的顺序存储结构 ·查找及其分析：成功查找的情况template<classElemType>intSeqList<ElemType>::Find(ElemTypee){//按照下标从大到小顺序查找值为e的数组结点的下标并将其返回。//elem[0]做哨兵用,保证即使查找失败，也可以在哨兵位上能找到值e。elem[0]=e;inti=length;//初始位置为尾结点所在下标while(elem[i]!=e)i--;//不等时继续向前比较，找到返回结点下标，否则返回0。returni; }成功查找时的平均比较次数：等概率情况,n为表中结点数

∑(n-i+1)/n=(n+1)/2时间复杂性为O(n)。i=n12、主要函数的实现251247998936length2、线性表的顺序存储结构3、插入和删除的时间复杂性分析： ·插入（插如之后成为第i个结点，注意从第1个结点开始）：124789361401234567899插入 ·如图99插入之后成为第3个结点，移动5－（3－1）次。 在一般情况下，插入之后成为第i个结点，移动n-(i-1)=n-i+1次。template<classElemType>intSeqList<ElemType>::Insert(inti,constElemType&e){ //在位置i上插入一个值为e的结点，原来的第i个结点变为第//i+1个结点，其余后继结点序号同样加1，插入成功返回1。Exception((i<1)||(i>length+1),”iisnotcorrect.”);//插入位置i不合法Exception(MaxSize==length,”nospacefornewitem.”);//存储空间已经满了，无法插入。//从尾结点起到第i个结点逐个向后移动一个位置for(intj=length;j>=i;j--)elem[j+1]=elem[j];elem[i]=e; //将要插入的结点值放入第i个结点的位置length++; //顺序表结点个数加1return1; //插入成功返回1}lengtht2、线性表的顺序存储结构3、插入和删除的时间复杂性分析：124789361401234567812479989361499插入124789361412478936141247893614 ·插入（插如之后成为第i个结点，注意从第1个结点开始）： ·如图99插入之后成为第3个结点，移动5－（3－1）次。 在一般情况下，插入之后成为第i个结点，移动n-(i-1)=n-i+1次。2、线性表的顺序存储结构3、插入和删除的时间复杂性分析： ·插入后成为第3个结点，移动5－（3－1）次。

在一般情况下，插入后成为第i个结点，移动n-i+1)次 插入后成为第1个结点，移动n次 插入后成为第i个结点，移动n-i+1次 插入后成为第n个结点，移动1次。 插入后成为第n＋1个结点，移动0次。总共n+1种情况 ·在长度为n的线性表中插入一个结点的平均次数为：

∑(n-i+1)/(n+1)=n/2时间复杂性为O(n)。i=1n+12、线性表的顺序存储结构3、插入和删除的时间复杂性分析： ·删除：1247893614012345678 ·如图结点的数据值为89的结点删除将移动5－3次。 在一般情况下，删除第i个结点，移动n-1次。template<classElemType>intSeqList<ElemType>::Delete(ElemType&e,inti){//若第i个结点存在，删除并将其值放入e,若i非法，删除失败。Exception((i<1)||(i>length),”iisillgeal.”);e=elem[i];//将第i个结点值首先读出，用于返回。for(intj=i;j<length;j++)elem[j]=elem[j+1];//第i+1个结点到尾结点逐个前移。length--; //表长度减1。returni; //返回成功标志i。}length删除892、线性表的顺序存储结构3、插入和删除的时间复杂性分析： ·删除（删除线性表的第i个结点）：1247893614012345678124736141247361412473614删除2、线性表的顺序存储结构3、插入和删除的时间复杂性分析： ·删除第3个结点，移动5-3次。

在一般情况下，删除第i个结点，移动n-i次

删除第1个结点，移动n-1次 删除第i个结点，移动n-i次 删除第n个结点，移动0次。总共n种情况 ·在长度为n的线性表中删除一个结点的平均次数为：

∑(n-i)/n=(n-1)/2时间复杂性为O(n)。i=1n ·另外，通过数据场之值x查找结点，代价O(n)。

查找第i个结点，代价O(1)。3、线形表的链接存储结构1、单链接表：通常用于表示线性结构，如：线性表·结点的表示：参照下图所示的情况：ElementNext·单链接表的表示：参照下图所示的情况：其中head是表首指针。∧ElementNextheadABZ∧headABZ头结点：不是线性表之中的结点。但增加此结点后，操作容易。Element:数据场－通常用于保存结点的数据元素或数据值Next:指针场－给出直接后继结点的地址3、线形表的链接存储结构1、单链接表、双链表和双向循环链表及其初始化。3、线形表的链接存储结构链表的ADT（抽象数据类型）链表类AbsList的定义ADT2.2链表类

AbsList的定义。template<classElemType>classAbsList{public:AbsList(){}; //构造函数 virtual~AbsList(){} //析构函数 virtualIsEmpty()const=0;//判表空吗？ virtualIsFull()const=0;//判表满吗？ virtualvoidMakeEmpty()=0;//将表清空。 firiendclassAbsListItr<ElemType>;private: AbsList(constAbsList&){}//冻结复制另一链表的构造函数。}；3、线形表的链接存储结构链表类迭代器类AbsList的定义ADT2.3链表迭代器类

AbsListItr的定义。template<classElemType>classAbsListItr{public: AbsListItr(constAbsList<ElemType>&L){}//构造函数。 AbsListItr(constAbsListItr&);

//通过复制构造当前迭代器。 virtual~AbsListItr(){} //析构函数 //以下函数是基本数据操纵类成员函数。 virtualvoidInsert(constElemType&x)=0;//插入在当前结点(值为x)之后。 virtualintRemove(constElemType&x)=0;//删除值为x的结点。 virtualintFind(constElemType&x)=0;//查找值为x的结点。 virtualintIsFound(constElemType&x)const=0;//查找值为x的结点成功否。 //访问当前结点运算符。 virtualintoperator+()const=0;//判当前结点存在吗？ virtualconstElemType&operator()()const=0;//取当前结点内容。 //定位运算符及函数。 virtualvoidZeroth()=0;//定位于链表的首结点之前。 virtualvoidFirst()=0;//定位于链表的首结点。 virtualvoidoperator++()=0;//定位于链表的下一个结点。 virtualvoidoperator++(int)=0;//定位于链表的下一个结点。protected: AbsListItr(){}//冻结无参的构造函数。}；请改正书上这行！3、线形表的链接存储结构单链接表、基本操作及迭代器的实现。·结点类的定义：ElementNextElement:数据场－通常用于保存结点的数据元素或数据值。Next:指针场－给出直接后继结点的地址。程序2.5单链表结点类。template<classElemType>classList; //单链表类的向前说明。template<classElemType>classListItr; //单链表迭代器类的向前说明。template<classElemType>classListNode{ friendclassList<ElemType>; //单链表类为其友元类,便于访问结点类中的私有成员。friendclassListItr<ElemType>;//单链表迭代器类为其友元类,便于访问结点类中的私有成员。private: ListNode<ElemType>*Next;//指向下一个结点的指针。 ElemTypeElement; //结点数据。public: ListNode(constElemType&E,ListNode<ElemType>*N=NULL) :Element(E),Next(N){} //构造函数 ListNode():Next(NULL){} //构造函数 ~ListNode(){}; //析构函数};3、线形表的链接存储结构单链接表、基本操作及迭代器的实现。·单链接表类：ElementNext程序2.6:单链表类。template<classElemType>classListItr; //单链表迭代器类的向前说明。template<classElemType>classList:publicAbsList<ElemType>{ friendclassListItr<ElemType>;//单链表迭代器类为其友元类。private:ListNode<ElemType>*head;//指向头结点的指针。public:List(){head=newListNode<ElemType>();}~List(){MakeEmpty();deletehead;} //析构函数constList&operator=(constList&R);//完成复制功能。intIsEmpty()const{returnhead->Next==NULL;}intIsFull()const{return0;}voidMakeEmpty();};3、线形表的链接存储结构单链接表、基本操作及迭代器的实现。迭代器类：ElementNext程序2.7:迭代器类。template<classElemType>classListItr:publicAbsListItr<ElemType>{ private: ListNode<ElemType>*consthead; //指向头结点的常指针。 ListNode<ElemType>*Current; //指向当前结点的指针。public: ListItr(constList<ElemType>&L):head(L.head) {Current=L.IsEmpty()?head:head->Next;} ~ListItr(){} //析构函数 intFind(constElemType&x); //查找值为x的结点，查找成功则使其成为当前结点，并返回True。 intIsFound(constElemType&x)const;//查找值为x的结点，查找成功返回//True，否则返回False;不改变指针Current的值。 voidInsert(constElemType&x);//插入成功，新结点成为当前结点。 intRemove(constElemType&x);//删除值为x的结点的操作。

3、线形表的链接存储结构单链接表、基本操作及迭代器的实现。迭代器类：ElementNext程序2.7:迭代器类（续）。 ………… intoperator+()const{returnCurrent&&Current!=head;} //当前结点非空则返回True。 constElemType&operator()()const; //取当前结点的数据值。 voidoperator++(); //使当前结点的直接后继结点成为当前结点。 voidoperator++(int){operator++();}//定义为前缀++运算符。 voidZeroth(){Current=head;}//当前指针指向头结点。 voidFirst(); //当前指针指向首结点。 constListItr&operator=(constListItr&);//赋值运算符。};3、线形表的链接存储结构CurrentBATmpx单链接表结点类、基本操作及迭代器的实现。·插入操作的实现：将新结点插入到当前结点（指针Current指向的结点）之后。Tmp=newListNode();Tmp->Element=x;3、线形表的链接存储结构CurrentBATmpx2.

Current->Next=Tmp注意：1、2不可颠倒，否则链表将脱链。时间代价：O(1)可用一个语句取代上述操作，即：Current->Next=newListNode(x,Current->Next);

·插入操作的实现：将新结点插入到当前结点（指针Current指向的结点）之后。1.Tmp->Next=Current->Next·指针p和指向的对象的关系：·程序语句：p->next->next->next->pbacElementNext·指针pp->指针p指向的对象(结点)p->nextp->next->p->next->nextp->next->next->3、线形表的链接存储结构·删除：删除Current所指向的结点之后继结点。要知被删结点的前驱结点的地址CurrentCurrentbacpp=Current->Next3、线形表的链接存储结构·删除：删除Current所指向的结点之后继结点。要知被删结点的前驱结点的地址CurrentCurrentbacpCurrent->Next=p->Next;3、线形表的链接存储结构·删除：删除Current所指向的结点之后继结点。要知被删结点的前驱结点的地址CurrentCurrentacdeletep;注意：必须释放p->。时间O(1)。养成良好的程序设计习惯。3、线形表的链接存储结构·和顺序存储的线性表的操作的比较：插入：O(1)删除：O(1)FINDith:O(i)平均O(n)FINDkey:平均O(n)插入：O(n)删除：O(n)FINDith:O(1)FINDkey:平均O(n)单链表顺序存储的线性表3、线形表的链接存储结构·在迭代器中，基本操作的实现template<classElemType>classListItr:publicAbsListItr<ElemType>{private:

ListNode<ElemType>*consthead;//指向头结点的常指针。 ListNode<ElemType>*Current;//指向当前结点的指针。public: ListItr(constList<ElemType>&L):head(L.head) {Current=L.IsEmpty()?head:head->Next;} ~ListItr(){}//析构函数 intFind(constElemType&x); //查找值为x的结点，查找成功则使其成为当前结点，并返回True。

intIsFound(constElemType&x)const; //查找值为x的结点，查找成功返回True，否则返回False;不改变指 //针Current的值。

voidInsert(constElemType&x);//插入成功，新结点成为当前结点。

intRemove(constElemType&x);//删除值为x的结点的操作。

……………….};3、线形表的链接存储结构·在迭代器中，基本操作Find和IsFound的实现template<classElemType>intListItr<ElemType>::Find(constElemType&x){ListNode<ElemType>*Ptr=head->Next;while(Ptr!=NULL&&!(Ptr->Element==x))Ptr=Ptr->Next;if(

Ptr==NULL)return0;Current=Ptr;return1;}template<classElemType>intListItr<ElemType>::IsFound(constElemType&x)const{ListNode<ElemType>*Ptr=head->Next;while(Ptr!=NULL&&!(Ptr->Element==x))Ptr=Ptr->Next;returnPtr!=NULL;}3、线形表的链接存储结构·在迭代器中，基本操作Inser和Delete的实现template<classElemType>voidListItr<ElemType>::Insert(constElemType&x){//插入操作。Exception(Current==NULL,“Thelocationisillegal!”);ListNode<ElemType>*p;p=newListNode<ElemType>(x,Current->Next);Current=Current->Next=p;}template<classElemType>intListItr<ElemType>::Remove(constElemType&x){ListNode<ElemType>*Ptr=head;while(Ptr->Next!=NULL&&!(Ptr->Next->Element==x))Ptr=Ptr->Next;if(

Ptr->Next==NULL)return0;//未找到数据值为x的结点，删除失败。ListNode<ElemType>*P=Ptr->Next;Ptr->Next=Ptr->Next->Next;deleteP;Current=head;return1;}

3、线形表的链接存储结构·在迭代器中，基本操作Inser和Delete的实现程序2.8:类List的赋值运算符=的实现。template<classElemType>constList<ElemType>&List<ElemType>::

operator=(constList<ElemType>&R){if(this==&R)return*this; //同一单链表，不必赋值。MakeEmpty(); //清空单链表。ListItr<ElemType>Itr(*this);for(ListItr<ElemType>Ritr(R);+Ritr;Ritr++)Itr.Insert(Ritr()); //根据单链表R的结点数据值，创建新结点，并插入到当前链表。return*this;}4、单向循环链表head

……

head

2、带头结点的单向循环链表的初态1、带头结点的单向循环链表带头结点的单向循环链表head

……

head＝NULL2、不带头结点的单向循环链表的初态1、不带头结点的单向循环链表不带头结点的单向循环链表4、单向循环链表

tail

……

tail＝NULL2、不带头结点的单向循环链表的初态1、不带头结点的单向循环链表不带头结点的单向循环链表（使用尾指针）5、双链表、双向循环链表

tailhead

A

B

C

tailhead

(1).带头结点和最后一个结点的双链表初始化headBCDA(2).双向循环链表的一种实现方案head=NULL;初始化PriorElementNextPriorElementNext5、双链表、双向循环链表·删除：给出待删结点的地址就可以把它删除。如；删除数据场之值为a的结点，地址由 current给出。headabCurrentctailheadabCurrentctailheadabCurrentctail执行：Current->Prior->Next=current->Next;后执行：Current->Next->Prior=Current->Prior;后

最后执行：deleteCurrent;将结点删除。5、双链表、双向循环链表·插入：注意插入次序。如：将数据场为x的结点，插在当前结点之后。headabctailxheadabCurrentctailxheadabctailx·p->prior=Current;·p->Next=Current->Next;CurrentCurrentppp·Current->Next->prior=p;·Current->Next=p;6、一元多项式的加法一元多项式的表示及相加；StructTerm{floatcoef;intexp;Term(intc,inte){coef=c;exp=e;}

…………}; ·如：多项式：AH=7+3x+9x8+5x17 BH=8x+22x7-9x8AH703198517BH81227-98∧∧coefexplinkCH70111227517∧6、一元多项式的加法一元多项式的表示及相加； ·如：多项式：AH=7+3x+9x8+5x17 BH=8x+22x7-9x8；结果保留在CH的单链表之中。 ·算法：指数等：若系数之和为零，则两结点都删除。pa、pb后移。 否则将相加后的系数、及相应指数送入单链表C,pa、pb后移。 pa->指数小：将系数、及相应指数送入单链表C,pa后移。 pa->指数大：将链表B系数、及相应指数送入单链表C,pb后移。 注意：将任何一个多项式的多余部分，插入在单链表C之后。AH703198517BH81227-98∧∧CH70∧coefexpnNext6、一元多项式的加法一元多项式的表示及相加； ·如：多项式：AH=7+3x+9x8+5x17 BH=8x+22x7-9x8；结果保留在CH的单链表之中。 ·算法：指数等：若系数之和为零，则两结点都删除。pa、pb后移。 否则将相加后的系数、及相应指数送入单链表C,pa、pb后移。 pa->指数小：将系数、及相应指数送入单链表C,pa后移。 pa->指数大：将链表B系数、及相应指数送入单链表C,pb后移。 注意：将任何一个多项式的多余部分，插入在单链表C之后。AH703198517BH81227-98∧∧CH70111coefexpnNext∧6、一元多项式的加法一元多项式的表示及相加； ·如：多项式：AH=7+3x+9x8+5x17 BH=8x+22x7-9x8；结果保留在CH的单链表之中。 ·算法：指数等：若系数之和为零，则两结点都删除。pa、pb后移。 否则将相加后的系数、及相应指数送入单链表C,pa、pb后移。 pa->指数小：将系数、及相应指数送入单链表C,pa后移。 pa->指数大：将链表B系数、及相应指数送入单链表C,pb后移。 注意：将任何一个多项式的多余部分，插入在单链表C之后。AH703198517BH81227-98∧∧CH70111227coefexpnNext∧6、一元多项式的加法一元多项式的表示及相加； ·如：多项式：AH=7+3x+9x8+5x17 BH=8x+22x7-9x8；结果保留在CH的单链表之中。 ·算法：指数等：若系数之和为零，则两结点都删除。pa、pb后移。 否则将相加后的系数、及相应指数送入单链表C,pa、pb后移。 pa->指数小：将系数、及相应指数送入单链表C,pa后移。 pa->指数大：将链表B系数、及相应指数送入单链表C,pb后移。 注意：将任何一个多项式的多余部分，插入在单链表C之后。AH703198517BH81227-98∧∧CH70111227∧coefexpnNext6、一元多项式的加法一元多项式的表示及相加； ·如：多项式：AH=7+3x+9x8+5x17 BH=8x+22x7-9x8；结果保留在CH的单链表之中。 ·算法：指数等：若系数之和为零，则两结点都删除。pa、pb后移。 否则将相加后的系数、及相应指数送入单链表C,pa、pb后移。 pa->指数小：将系数、及相应指数送入单链表C,pa后移。 pa->指数大：将链表B系数、及相应指数送入单链表C,pb后移。 注意：将任何一个多项式的多余部分，插入在单链表C之后。AH703198517BH81227-98∧∧CH70111227517∧coefexpnNext ·注意：本书的程序实现时，对单链表使用了带有表头的表示方法。另外，使用了 迭代器(本书称之为游标类)。迭代器是一种“指针”抽象。6、一元多项式的加法一元多项式的表示及相加；程序的实现 ·如：多项式：AH=7+3x+9x8+5x17 BH=8x+22x7-9x8AH703198517BH81227-98∧∧coefexplinkCH70111227517∧coefexplinkmain(){TermR(-1,-1);//多项式输入的结束标志。Polynomial<Term>a(R),b(R),c;cin>>a>>b;// 读入2个多项式，通过对>>重载实现。c=a; //多项式a并不破坏，将其值送入c。c+b; //完成多项式c、b相加，结果保存在多项式c之中。cout<<c;//将多项式c输出。return0;}template<classElemType>classPolynomial{public:Polynomial(constElemType&P){Stop_flag=P;}Polynomial(){}~Polynomial(){}Polynomial&operator=(constPolynomial&T);Polynomial&operator+(constPolynomial&T);friendistream&operator>>(istream&is,Polynomial<ElemType>&T);friendostream&operator<<(ostream&os,constPolynomial<ElemType>&T);private:List<ElemType>poly;

ElemTypeStop_flag;//用于判断多项式输入结束。};StructTerm{floatcoef;intexp;Term(intc,inte){coef=c;exp=e;}…………};6、一元多项式的加法template<classElemType>Polynomial<ElemType>&Polynomial<ElemType>::operator+(constPolynomial<ElemType> &T) { ElemTypeelemA,elemB; Polynomial<ElemType>C; ListItr<ElemType>ItrA(poly); ListItr<ElemType>ItrB(T.poly); ListItr<ElemType>ItrC(C.poly);

for(;+ItrA&&+ItrB;){ elemA=ItrA();elemB=ItrB();

switch(compare(elemA,elemB)){

case‘=’: elemA+=elemB;

if(!Is_Empty(elemA))ItrC.Insert(elemA); ++ItrA;++ItrB;

break;

case‘>’: ItrC.Insert(elemB);++ItrB;break;

case‘<’: ItrC.Insert(elemA);++ItrA;break; } }

if(+ItrA)for(;+ItrA;++ItrA){elemA=ItrA();ItrC.Insert(elemA);}

else

for(;+ItrB;++ItrB){elemB=ItrB();ItrC.Insert(elemB);} *this=C;return*this;}papc

3198517∧pbp

1312527∧7、应用：静态链表和稀疏矩阵·静态链表的实现： 用于没有动态存储分配功能的语言，如FORTRAN、COBOL等；当然也可用于C/c++ 等高级语言。缺点：必须预估存区的大小，造成浪费。优点：插、删操作省时。·e.g:设集合A=(c,b,e,g,f,d)和B=(a,b,n,f)。求集合运算(A－B)∪(B－A)的结 果。解：A－B=(c,e,g,d);B－A=(a,n)。(A－B)∪(B－A)=(c,e,g,d,a,n)。程序执行步骤： 1、将用作存储空间的数组的所有单元分配至可利用空间表(也称：空闲栈或备 用链(保存未被使用的结点的单链表)。 2、建立集合A的静态链表。 3、逐个输入集合B的元素，同时查找A的静态链表有无该元素。有则删 除，无则插入该结点。 4、集合B的元素输入完毕，则在原集合A的静态链表中得到了集合运算 (A－B)∪(B－A)的结果。7、应用：静态链表和稀疏矩阵 1、将用作存储空间的数组的所有单元分配至空闲栈或备用链。datacurspace[0]space[1]space[2]space[3]space[4]space[5]space[6]space[7]space[8]space[9]space[10]space[11]datacur1234567891011-17、应用：静态链表和稀疏矩阵 1、将用作存储空间的数组的所有单元分配至空闲栈或备用链。 ·备用链经初始化之后的情况：注意此处的地址是下标地址。10234567891011datacurvoidInitSpace_SL(SLinkList&Space){for(i=0;i<MAXSIZE-1;++i)space[i].cur=i+1;space[MAXSIZE-1]=-1;}intMalloc_SL(SLinkList&Space){i=space[0].cur;if(space[0].cur!=-1);space[0].cur=space[i].cur;returni;}intfree_SL(SLinkList&Space,intk){space[k].cur=space[0].cur;space[0].cur=k;}10234567891011datacur1234567891011 ·为了形象起见，和动态分配的单链表表示相似，备用链初 始化之后通常表示成以下形式。-1-17、应用：静态链表和稀疏矩阵 1、将用作存储空间的数组的所有单元分配至空闲栈或备用链。 ·备用链通常画成以下图形：注意此处的地址是下标地址。10234567891011datacur 2、建立集合A的静态链表: ·集合A的静态链表的初始化。0234567891011datacur10s工作链：备用链：-1-17、应用：静态链表和稀疏矩阵 1、将用作存储空间的数组的所有单元分配至空闲栈或备用链。 ·备用链通常画成以下图形：注意此处的地址是下标地址。10234567891011datacur 2、建立集合A的静态链表: ·集合A的静态链表：在输入元素c之后。0234567891011-1datacur10-1s工作链：备用链：rc7、应用：静态链表和稀疏矩阵 1、将用作存储空间的数组的所有单元分配至空闲栈或备用链。 ·备用链通常画成以下图形：注意此处的地址是下标地址。10234567891011datacur 2、建立集合A的静态链表: ·集合A的静态链表：在输入元素b之后。0234567891011-1datacur10-1s工作链：备用链：rcb7、应用：静态链表和稀疏矩阵 1、将用作存储空间的数组的所有单元分配至空闲栈或备用链。 ·备用链通常画成以下图形：注意此处的地址是下标地址。10234567891011datacur 2、建立集合A的静态链表: ·集合A的静态链表：在输入元素e之后。0234567891011-1datacur10-1s工作链：备用链：rcbe7、应用：静态链表和稀疏矩阵 1、将用作存储空间的数组的所有单元分配至空闲栈或备用链。 ·备用链通常画成以下图形：注意此处的地址是下标地址。10234567891011datacur 2、建立集合A的静态链表: ·集合A的静态链表：在输入元素g之后。0234567891011-1datacur10-1s工作链：备用链：rcbeg7、应用：静态链表和稀疏矩阵 1、将用作存储空间的数组的所有单元分配至空闲栈或备用链。 ·备用链通常画成以下图形：注意此处的地址是下标地址。10234567891011datacur 2、建立集合A的静态链表: ·集合A的静态链表：在输入元素f之后。0234567891011-1datacur10-1s工作链：备用链：rcbegf7、应用：静态链表和稀疏矩阵 1、将用作存储空间的数组的所有单元分配至空闲栈或备用链。 ·备用链通常画成以下图形：注意此处的地址是下标地址。10234567891011datacur 2、建立集合A的静态链表: ·集合A的静态链表：在输入元素d之后。0234567891011-1datacur10-1s工作链：备用链：rcbegfd7、应用：静态链表和稀疏矩阵 1、将用作存储空间的数组的所有单元分配至空闲栈或备用链。 ·备用链通常画成以下图形：注意此处的地址是下标地址。10234567891011datacur 3、逐个输入集合B的元素。 ·输入a,查找A的静态链表。a不在，插入。0234567891011datacur10s工作链：备用链：rcbegfda-1-17、应用：静态链表和稀疏矩阵 1、将用作存储空间的数组的所有单元分配至空闲栈或备用链。 ·备用链通常画成以下图形：注意此处的地址