第一章代码 【例1-1】 队列的抽象数据类型定义 ADT Queue{ 数据对象D.doc

第一章代码【例1-1】 队列的抽象数据类型定义ADT Queue 数据对象：D=ai | aiElemSet，i=1,2,n, n0 数据关系：R1= | ai-1, ai D，i=2,n 基本操作： InitQueue(&Q) 操作结果：构造一个空队列Q。 DestroyQueue(&Q) 初始条件：队列Q已存在。 操作结果：队列Q被撤销，不再存在。 ClearQueue(&Q) 初始条件：队列Q已存在。 操作结果：将Q清为空队列。 QueueEmpty(Q) 初始条件：队列Q已存在。 操作结果：若Q为空队列，则返回TRUE，否则返回FALSE。 GetHead(Q,&e) 初始条件：Q为非空队列。 操作结果：用e返回Q的队头元素。 EnQueue(&Q,e) 初始条件：队列Q已存在。 操作结果：插入元素e为Q的新的队尾元素。 DeQueue(&Q,&e) 初始条件：Q为非空队列。 操作结果：删除Q的队头元素，并用e返回其值。ADT Queue第二章代码1.线性表的初始化操作初始化操作算法描述如下：#define n0 100#define datatype intstruct xxlist datatype wn0+1; /存储线性表中的元素 int n; /线性表的当前表长 ;2插入操作插入算法描述如下：void insert(xxlist &L, int i, datatype x) int j; if(iL.n)|(i0) /在线性表当前长度为n的情况下，将新元素插入到wi+1 wn0 cout位置不合法，出错； 是不允许的 else if(L.n=n0) couti; j-) L. wj+1=L.wj; L.wi+1=x; L.n+; 3删除操作删除算法描述如下：void delete(xxlist &L, int i) int j; if(iL.n)|(i1) cout位置不合法，出错； else for(j=i+1; j=L.n; 页：2将 L.N改成L.nj+) L. wj-1=L.wj; L.n-; 根据上述的算法思想，约瑟夫问题算法描述如下：#define n 9#define m 5int josephus() int yn+1; int i,j,v; for(i=0;i=1;i-) v=(v+m-1)%i; coutyv” ”; for(j=v+1;j=1)&(i=L.n) /查找第i个结点 while(jnext； j+; return(q); 2 单链表的插入 其算法描述如下：void insert(linklist &L,int i,datatype x) node *p,*q; if(iL.n) /线性表的插入位置不合法 coutdata=x; qnext=pnextpnext=q;L.n+; /线性表的长度加13 单链表的删除其算法描述如下：void delete(linklist &L,int i) node *p,*q; if(iL.n) /删除结点的位置不合法 coutnext; pnext= qnext; delete q; L.n-; /释放空间，线性表的长度减1 1双链表的插入其算法步骤如下所示：qprior=p;qnext=pnext;pnext=q;pnextprior=q;同理，在已知结点p之前插入一个新的结点q的算法步骤如下所示。qprior=pprior；qnext=p；ppriornext=q;pprior=q;2. 双链表的删除ppriornext= pnext;pnextprior= pprior;多项式相加的算法描述如下：struct node int coef; /结点的系数 int exp; /结点的指数 node *next; /结点指针域 ;void ploy(int c,int i,node *q) qnext=new node; q=qnext; qcoef=c; qexp=i; void add(node *Ha, node *Hb, node *&Hc) node *qa,*qb,*qc; int x; Hc=new node; qa=Hanext; qb=Hbnext; qc=Hc; while(qa&qb) if(qaexp=qbexp) x=qacoef+qbcoef; if(x) ploy(x,qaexp,qc); qa=qanext; qb=qbnext; else if(qaexpbexp) ploy(qbcoef,qbexp,qc); qb=qbnext; else ploy(qacoef,qaexp,qc); qa=qanext; while(qa) ploy(qacoef,qaexp,qc); qa=qanext; while(qb) ploy(qbcoef,qbexp,qc); qb=qbnext; qcnext=null; 第三章代码3.1.2 栈的存储结构链式栈的C+定义如下： #ifndef Stack_H #define Stack_H template class Stack /栈类定义 /Stack.h头文件 private: int size; int top; T* stackPtr; public: Stack(int s=10); Stack() delete stackPtr; int push(const T&); int pop(T&); int isFull() return top=size-1; int isEmpty() return top=-1; ;#endif /stack.cpp #include #include stack.h using namespace std; template Stack :Stack(int s) size=s0&s1000?s:10; top=-1; stackPtr=new Tsize; template int Stack:push(const T& item) if(!isFull() stackPtr+top=item; return 1 return 0; template int Stack:pop(T& popValue) if(!isEmpty() popValue=stackPtrtop-; return 1; return 0; 1 编程求出菲波那契(Fibonacci)数列的第n项。编写递归函数如下：long fibonacci (int n) if (n=1| n=2) return 1L;else return fibonacci (n-1)+fibonacci (n-2); 2. 文件夹遍历技术void search(LPCTSTR lpPath) if (当前目录为空目录) return; do if (找到的文件是目录) function(找到的目录); else 对文件进行匹配操作;if(匹配成功) return; while (查找下一个目录); 3. 队列的实现#include#includeusing namespace std;templateclass DeQueue;templateclass NodeT info;Node *link;public:Node(T data=0,Node *l=NULL);friend class DeQueue;template Node:Node(T data,Node *l)info=data;link=l;templateclass DeQueueNode *front,*rear;public:DeQueue()rear=front=NULL; /构造一个空链队DeQueue()MakeEmpty();bool IsEmpty() return front=NULL;/队空否？void EnQueFront(const T &data);/进队void EnQueRear(const T &data);/进队T DeQue(); /出队T GetFront(); /查看队头数据void MakeEmpty();/置空队列，与析构逻辑上不同，物理上一样;templatevoid DeQueue:MakeEmpty()Node *temp;while(front!=NULL)temp=front;front=front-link;delete temp;templatevoid DeQueue:EnQueFront(const T &data)if(front=NULL) front=rear=new Node(data,NULL);else front=new Node(data,front);templatevoid DeQueue:EnQueRear(const T &data)if(front=NULL) front=rear=new Node(data,NULL);else rear=rear-link=new Node(data,NULL);templateT DeQueue:DeQue()assert(!IsEmpty();Node *temp=front;T data=temp-info;front=front-link;delete temp;return data;templateT DeQueue:GetFront()assert(!IsEmpty();return front-info;1循环队列的基本操作(1) 常规做法 if(i+1=Size) /i表示队首或队尾 i=0; else i+;(2) “利用模运算”i=(i+1)% Size；3.3.4 队列的应用1. 舞伴问题算法如下(部分伪代码描述)：typedef struct char name20; /姓名 char sex; /性别，F表示女，M表示男 Person;void DancePartner(Person dancer,int num) /结构数组dancer中存放跳舞的男女，num是跳舞的人数。 int i; Person p; 男士队列初始化，生成队列Mdancers; 女士队列初始化，生成队列Fdancers; for(i=0;inum;i+)/依次将跳舞者依其性别入队 p=danceri; if(p.sex=F)此人排入女队; else 此人排入男队; printf(The dancing partners are: n n); while(男队女队均不为空)/以下两人配对成功女士出队并打印出队女士名;男士出队并打印出队男士名; if(女队不为空) 取队头元素，输出将要获得舞伴的女士姓名;/说明她在等待; else if(男队不为空)/输出队头者名字 取队头元素，输出将要获得舞伴的男士姓名;/说明他在等待; /DancerPartners3.5 本 章 实 训3.5.3 实训过程三级标题3.5.31建立一个栈类分析按照类的定义实现类。 实训要求需创建栈类的头文件。实训步骤1) 按实验一所述方法建立一个工程(Stack.dsp)，再在工程内建立头文件(stack.h)，内容如下所示。 # include template class Stack private:int top;Type *elements;int maxSize;public:Stack(int sz=10);Stack()delete elements; void Push(const Type& item);int Pop();Type GetTop();int IsEmpty() const return top=-1;int IsFull() const return top=maxSize-1;void MakeEmpty() top=-1;void transter();2)在工程内建立栈类成员函数和主函数的实现文件stack.cpp，内容如下所示。#include #include stack.htemplate Stack:Stack(int sz):top(-1),maxSize(sz) elements=new TypemaxSize;assert(elements!=NULL);template void Stack:Push(const Type& item) assert(!IsFull();elements+top=item;template int Stack:Pop() if (IsEmpty() return 0;top-;return 1;template Type Stack:GetTop() if (IsEmpty() return NULL;return elementstop;template void Stack:transter( ) for (int i=top; i=0; i-) coutelementsi ;coutendl;void main()Stack teststack(10);int x5=1,2,3,4,5;for (int i=0;i5;i+) teststack.Push (xi);teststack.transter ();teststack.Pop(); teststack.transter ();coutteststack.GetTop ()endl;teststack.Pop (); teststack.Pop ();teststack.Pop (); teststack.transter (); teststack.Push(8); teststack.Push (22); teststack.transter ();运行结果5 4 3 2 14 3 2 14122 8 12. 队列测试分析按照队列的定义实现队列类及其操作方法。实训要求用模板实现队列类的定义。 实训步骤操作步骤如下。1) 按实验一所述方法建立一个工程(Queue.dsp)，再在工程内建立头文件(queue.h)，内容如下所示。 #include template class Queueprivate:int rear,front;Type *elements;int maxSize; public:Queue(int sz=10);Queue() delete elements; void EnQueue(const Type& item);int DeQueue();Type GetFront();void MakeEmpty() front=rear=0;int IsEmpty() const return front=rear;int IsFull() const return (rear+1)%maxSize=front; int Length() const return (rear-front+maxSize)%maxSize; void Transfer();template Queue:Queue(int sz):front(0),rear(0),maxSize(sz)elements=new TypemaxSize;assert(elements!=0);template void Queue:EnQueue(const Type& item) assert(!IsFull();rear=(rear+1)%maxSize;elementsrear=item;template int Queue:DeQueue() if (IsEmpty() return 0; front=(front+1)%maxSize; return 1;template Type Queue:GetFront() if (IsEmpty() return NULL; return elements(front+1)%maxSize;template void Queue:Transfer() if (!IsEmpty()cout输出队列元素：endl;int p;p=(front+1)%maxSize;while (p!=rear) coutelementsp , ; p=(p+1)%maxSize;coutelementsrearendl;2) 在工程内建立文件(queuemain.cpp)，内容如下所示。#include #include queue.h#include void main()Queue queue1(8);/元素5，6，8依次进队列；queue1.EnQueue(5);queue1.EnQueue(6);queue1.EnQueue(8);/输出队列元素cout5，6，8三个元素进队列后的队列元素输出：endl;queue1.Transfer();/元素9，20，16依次进队列； queue1.EnQueue(9);queue1.EnQueue(20);queue1.EnQueue(16); /输出队列元素cout队列中加入元素9，20，16后的队列元素输出：endl;queue1.Transfer();/删除队首元素queue1.DeQueue(); /输出队列元素(元素出队以后)cout删除队首元素后的输出：(istream &,Matrix &); /矩阵输入重载函数friend ostream & operator(istream &,Matrix &); /矩阵输入friend ostream & operator(ostream &,Matrix &); public:private:MatrixNode *headNode; /稀疏距阵的表头 ;1. 按b.data中的三元组的次序在a.data中找到相应的元素进行转置矩阵转置算法1。void transpose(SparMatrix a, SparMatrix b)b.rows=a.cols;/修改行、列、数据数量信息b.cols=a.rows;b.terms=a.terms;if(b.terms)int p=0;for (int col=0;cola.cols;col+) /按行号扫描for (int q=0;anoa.terms;ano+) /对三元组表扫描 if (a.dataq.j=col) /进行转置 b.datap.j=a.dataq.i; b.datap.i=a.dataq.j; b.datap.e=a.dataq.e; p+; 2通过计算直接将a.data中的数据放到b中的指定位置矩阵转置算法2void fastranspose(SparMatrix a. SparMatrix b)b.rows=a.cols;b.cols=a.rows;b.terms=a.terms;if(b.terms)for(col=0;cola.cols;col+)numcol=0;for(int t=0;ta.terms;t+)col=a.datat.j;numcol-1+;pot0=0;for(col=1;cola.cols;col+)potcol=potcol-1+numcol-1;for(p=0;anoa.terms;p+)col=a.datap.j;pt=potcol-1;b.datapt.j=a.datap.i;b.datapt.i=a.datap.j; b.datapt.e=a.datap.e;potcol-1+;4.4 本 章 实 训4.4.3 实训过程1. 实训代码/ Matrix/zhai_pengxiang / 2007-03-15/ #include #include iostream.h#include iomanip.hstruct Triple int row,col ; float v; ;class Matrix;class MatrixNode/矩阵接点定义public:friend class Matrix;friend istream & operator(istream &,Matrix &); /矩阵输入重载函数friend ostream & operator(istream &,Matrix &); /矩阵输入friend ostream & operator(istream & is,Matrix & matrix) Triple s;int p;cout创建矩阵endl;couts.row;couts.col;couts.v; /输入矩阵的行数，列数和if(s.rows.col) /非零元素个数p=s.row;elsep=s.col; /取行、列数大者matrix.headNode=new MatrixNode(false,&s);/整个矩阵表头结点if(!p) /零矩阵时matrix.headNode-right=matrix.headNode;return is;MatrixNode *H=new MatrixNode *p;/建立表头指针数组，指向各链表的表头for(int i=0;ip;i+)Hi=new MatrixNode(true,NULL);int currentRow=0;MatrixNode *last=H0;/当前行最后结点for(i=0;is.v;i+) /建立矩阵Triple t;coutt.row;coutt.col;coutt.v; /输入非零元素的三元组if(t.rowcurrentRow)/如果 行号大于当前行，闭合当前行last-right=HcurrentRow;currentRow=t.row;last=HcurrentRow;last=last-right=new MatrixNode(false,&t);/链入当前行Ht.col-gy.next=Ht.col-gy.next-down=last; /链入列链表last-right=HcurrentRow;/闭合最后一行/闭合各列链表for(i=0;igy.next-down=Hi;for(i=0;igy.next=Hi+1; Hp-1-gy.next=matrix.headNode;matrix.headNode-right=H0;delete H;return is;ostream & operatorright;cout输出结果endl;