程序：第02章：线性表

《程序：第02章：线性表》由会员分享，可在线阅读，更多相关《程序：第02章：线性表（12页珍藏版）》请在金锄头文库上搜索。

1、第第 2 2 章章 线性表线性表程序程序 2.12.1 线性表类#include template class LinearList public: virtual bool IsEmpty() const=0; virtual int Length() const=0; virtual bool Find(int i,T virtual int Search(T x) const=0; virtual bool Insert(int i,T x)=0;virtual bool Delete(int i)=0; virtual bool Update(int i,T x)=0;virtual

2、void Output(ostream protected:int n; /线性表的长度;程序程序 2.22.2 顺序表类 #include “linearlist.h“template class SeqList:public LinearList public:SeqList(int mSize);SeqList() Delete elements;bool IsEmpty() const;int Length() const;bool Find(int i,T int Search(T x) const; bool Insert(int i,T x);bool Delete(int i)

3、;bool Update(int i,T x);void Output(ostream private:int maxLength; /顺序表的最大长度T *elements; /动态一维数组的指针;template SeqList:SeqList(int mSize) maxLength=mSize;elements=new TmaxLength; /动态分配顺序表的存储空间n=0;template bool SeqList:IsEmpty() const return n=0;template int SeqList:Length() const return n;templatebool

4、 SeqList:Find(int i,Tjbool SeqList:Insert(int i,T x) if (in-1) couti;j-) elementsj+1=elementsj; /从后往前逐个后移元素elementsi+1=x; /将 x 插入下标为 i 的元素后面n+; return true;template bool SeqList:Delete(int i) if (!n) /下溢出检查coutn-1) coutbool SeqList:Update(int i,T x) if (in-1) coutvoid SeqList:Output(ostream i class

5、SingleList; /超前声明 SingleListtemplate class Node private:T element;Node *link;friend class SingleList;template class SingleList:public LinearList public:SingleList() first=NULL; n=0; SingleList();bool IsEmpty() const;int Length() const;bool Find(int i,Tint Search(T x) const;bool Insert(int i,T x);boo

6、l Delete(int i);bool Update(int i,T x);void Clear();void Output(ostreamprivate:Node* first;template SingleList: SingleList() Node *p;while (first) p=first-link;delete first;first=p;template int SingleList:Length() const return n;template bool SingleList:IsEmpty() const return n=0;templatebool Single

7、List:Find(int i,Tfor (int j=0; jlink;x=p-element; return true;templateint SingleList:Search(T x)const Node *p=first;for (int j=0; p j+) p=p-link;if(p) return j;return -1;templatebool SingleList:Insert(int i,T x) if (in-1) cout * q=new Node; q-element=x; /生成新结点 q1Node *p=first; /从头结点开始找 ai元素所在的结点pfor

8、 (int j=0; jlink;if(i-1) q-link=p-link; /新结点 q 插在 p 之后p-link=q;else q-link=first; /新结点 q 插在头结点之前，成为新的头结点 first=q;n+; return true;templatebool SingleList:Delete(int i) if (!n) /若 n=0，则再删除就会下溢出coutn-1) cout *p=first, *q=first;for (int j=0; jlink; /q 指向要删除的结点的前一结点if (i=0) first=first-link; /若 i=0,则删除的是

9、头结点else /否则删除的是非头结点p=q-link; /p 指向要删除的结点，q 是 p 的前驱q-link=p-link; /从单链表中删除 p 结点delete p; /释放 p 占据的存储单元n-; return true;template1本书中，在不引起混淆的情况下，常以指针变量名代表由该指针所指示的结点。例如，删除结点 p是指删除指针变量 p 所指示的结点*p。bool SingleList:Update(int i,T x) if (in-1)cout *p=first;for(int j=0; jlink;p-element=x; return true;templatev

10、oid SingleList:Output(ostreamwhile(p) outelementlink; outHeaderList: HeaderList() Node *first=new Node; /空的带表头结点的单链表仍然有一个表头结点first-link=NULL;n=0;templatebool HeaderList:Insert(int i, T x) if (in-1) cout *p=first; /从表头结点开始沿链查找 i 结点 pfor (int j=0; jlink;Node * q=new Node; q-element=x; /生成新结点 qq-link=p

11、-link; /p 插入 q 之后，无需区分头结点和一般结点p-link=q;n+;return true;templatebool HeaderList:Delete(int i) if ( !n ) coutn-1 ) cout *q=first, *p; /从表头结点开始沿链查找 i 结点的前驱结点 qfor (int j=0; jlink;p=q-link; /p 指向要删除的结点q-link=p-link; /从链表中删除 p，无需区分头结点和一般结点delete p; /释放 p 占据的存储单元n-; return true;程序程序 2.52.5 双向链表的结点类template

12、 class DoubleList; /超前声明 DoubleList 类template /声明 DNode 类class DNode private:T element;DNode *lLink, *rLink;friend DoubleList;程序程序 2.62.6 多项式项结点的 C+类class Term public:Term(int c,int e);Term(int c,int e,Term* nxt);Term* InsertAfter(int c,int e); /在 this 指针指示的结点后插入新结点private:int coef;int exp;Term *link;friend ostream ostream friend Polynominal;程序程序 2.82.8 多项式类的构造和析构函数Polynominal:Polynominal() /创建多项式的空的单循环链表 theList=new Term(0,-1); /分配表头结点的存储单元theList-link=theList; /构成循环链表Polynominal:Polynominal() /撤消多项式的单循环链表Term* p=theList-link;while(p!=theList)theList-link=p-link; /