作业二-函数模板与类模板.doc

《面向对象技术》实验报告 学号：100801305 姓名：高明行

《面向对象技术》
实验报告

专业：计算机科学与技术
学号： 100801305
姓名： 高明行
教师： 周 宇

作业二 函数模板与类模板
一．实验目的
l 学习类模板的定义和使用
l 学习函数模板的定义和使用
l 链表的不同实现方法
l 所有标识符命名方式按照匈牙利命名法。
二．实验内容
第Ⅰ题：基本练习
设计一个数组类的模板，具体要求如下：
l 数组的规模可以任意类型，任意大小。
l 重载构造函数实现不同种的初始化方式（自拟）。
l 数组排序函数。
l 数组查找函数。
l 数组查找最大值/最小值函数。
l 对运算符[]重载，支持对该数组类模板对象的下标运算

第Ⅱ题：基本练习（未必用类模板）
设计一个循环链表，用来表示大整数，具体要求如下：
l 链表的头结点值为-1，其余结点依次存放数据，各结点最多放四位整数，如下图表示233238766：

l 利用上述数据结构解决大整数的表示，以及加法、减法运算（用两个链表表示操作数）。
l 将上述数据结构应用于10位以上求素数问题和阶乘问题。

第Ⅰ题:
一设计分析：
1. 在主函数中可以任意改变数组大小和类型
2. 利用函数模板
二程序清单：
#include "iostream"
#include<stdlib.h>
using namespace std;

template<class T,int s=1>//类模板的首部，声明类模板的参数
class Array //数组类
{ int size;
T *ap;
public:
Array()
{ size=s;
ap=new T[s];
}
void SetData();
void Display();
void sort();
T Max();
T Min();
int search(T x);
T operator [](int i);
~Array()//析构
{
delete []ap;
}
};

template<class T,int s>
void Array<T,s>::SetData()//模板类Carray<T>的构造的输入函数
{ for(int i=0;i<size;i++)
cin>>ap[i];
}

template<class T,int s>
void Array<T,s>::Display()//模板类Carray<T>的构造的输出函数
{ for(int i=0;i<size;i++)
cout<<ap[i]<<" ";
cout<<endl;
}

template<class T,int s>
void Array<T,s>::sort()
{ int i,j,t;
for(i=0;i<size-1;i++)
for(j=0;j<size-i-1;j++)
if(ap[j]>ap[j+1])
{ t=ap[j];
ap[j]=ap[j+1];
ap[j+1]=t;
}
}

template<class T,int s>
T Array<T,s>::Max()
{
int i;
T temp=ap[0];
for(i=1;i<size;i++)
{
temp=(temp>ap[i])?temp:ap[i];
}
return temp;
}

template<class T,int s>
T Array<T,s>::Min()
{
int i;
T temp=ap[0];
for(i=1;i<size;i++)
{
temp=(temp<ap[i])?temp:ap[i];
}
return temp;
}

template<class T,int s>
int Array<T,s>::search(T x)
{ int i;
for(i=0;i<size;i++)
{
if(ap[i]==x)
cout<<"是第"<<i+1<<"个数"<<endl;
}
cout<<"不存在该数";
}

template<class T,int s>
T Array<T,s>::operator[](int i)
{ return ap[i];
}

int main()
{ int x;
Array<int,10> a;
cout<<"请输入整形数组（长度等于10）\n";
a.SetData();
a.sort();
a.Display();
cout<<"Max="<<a.Max()<<endl;
cout<<"Min="<<a.Min()<<endl;
cout<<"输入要查找的"<<endl;
cin>>x;
a.search(x);
system("pause");
return 0;
}

三运行结果：

四思考问题：
1. 对模板类有点理解，但是主要局限于课上的内容拓展一下就不灵活

第Ⅱ题:(百度的，不会写)
一设计分析：
3. 在主函数中可以任意改变数组大小和类型
4. 利用函数模板
二程序清单：
#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<malloc.h>
#define LEN sizeof(longint)
using namespace std;

struct longint //1.每个节点只存储四位十进制数字即不超过 9999 的非负整 数。
//双向链表有头指针，它的 data 值存储长整数的符号，1 为正，-1 为负,0 代表长整数为0,它的over值存储除头节点节点的个数。
//9999 范围的情况，一般 over>0 表示四位数超出 9999，over<0 表示四位数小于 0。
{ int data;
int over;
longint *pro;
longint *next;

};

longint *creat()//构造一个空的只有头指针的双向循环链表
{ longint *head;
head=(longint *)malloc(LEN);
if(head==NULL)
cout<<"malloc error!"<<endl;
else
{ head->data=0;
head->over=0;
head->pro=head;
head->next=head;
}
return(head);
}
void print(longint *head)
//输出以 head 为头结点的长整数
//先判断长整数的正负，为负时先输出"-"号，然后按节点顺序依次输出
//返回到头节点为止，输出前要判断各个节点 data 值的位数来判断先输出几个 0
{ longint *p;
p=head;
if(head->next==head)
cout<<"longint error!"<<endl;
else
{ if(head->data==-1)
cout<<"-"; //判断长整数是否为正
p=head->next;
cout<<p->data;
p=p->next;
while(p!=head) //判断各个节点 data 值的位数来判断先输出几个 0
{ if(p->data>=0 && p->data<10)
cout<<"000"<<p->data;
if(p->data>=10 && p->data<100)
cout<<"00"<<p->data;
if(p->data>=100 && p->data<1000)
cout<<"0"<<p->data;
if(p->data>=1000)
cout<<p->data;
p=p->next;
}
cout<<endl;
}
}

void insert(longint *head,longint *p)
//head 存在且 p 指向一个 longint 型节点。
//将节点 p 插到头节点后并返回头指针
{ p->next=head->next;
head->next->pro=p;
head->next=p;
p->pro=head;
head->over=head->over+1;
} //head 存在且 p 指向的节点在头节点后
//将头节点后的那个节点从链表里删除、释放 p 的空间并返回头指针

void del(longint *head,longint *p)
{ head->next=p->next;
p->next->pro=head;
free(p);
head->over=head->over-1;
}

longint *get(char s[]) //字符串存有字符格式的长整数。
//将以字符串形式存储的长整数转化到双向循环链表中存储并返回头指针。

//将长整数的字符形式转化成数字形式，存放到双向循环链表中，先判断长整数 若为负，减去字符串的第一位，将数字部分存到双向循环链表中

{ longint *head,*q;
//将长整数存到双向循环链表
int i,j,l=0;
head=creat(); //判断长整数的符号，并将信息存到头节点中
if(s[0]>'0')
head->data=1;
if(s[0]=='0')
head->data=0;
if(s[0]=='-')
{ l=1;
head->data=-1;
}
j=strlen(s)-1;
for(i=l;i<=j;i++)
s[i]=s[i]-'0';
while(j-l>=3)
{ q=(longint *)malloc (LEN);
q->data=s[j]+s[j-1]*10+s[j-2]*100+s[j-3]*1000;
insert(head,q);
j=j-4;
}
if(j>=l)
//当最后几位数的位数不足四位时
{ q=(longint *)malloc(LEN);
q->data=0;
while(l<=j)
{ q->data=q->data*10+s[l];
l++;
}
insert(head,q);
}
return(head);
}

void plus(longint *a,longint *b) //两个循环链表分别存有两个长整数
//将两个长整数做和并输出结果
//先将各位做加减，然后根据所得长整数正负和各结点 data 值进位或退位计算所得长整数的值并输出。
{ longint *m,*n,*p,*chead,*q;
if(a->over==0||b->over==0)
cout<<"long int error!"<<endl;
else
{ m=a->pro;
n=b->pro;
chead=creat();
while(m!=a&&n!=b)
{ p=(longint *)malloc(LEN);
p->data=a->data*m->data+b->data*n->data;
insert(chead,p);
m=m->pro;
n=n->pro;
}
while(m!=a||n!=b)
{ if(m==a)
{ p=(longint *)malloc(LEN);
p->data=b->data*n->data;
n=n->pro;
insert(chead,p);
}
else if(n==b)
{ p=(longint *)malloc(LEN);
p->data=a->data*m->data;
m=m->pro;
insert(chead,p);
}
}
p=chead->next;
chead->data=0;
while(p!=chead)
{ if(p->data>0)
{ chead->data=1;
break;
}
if(p->data<0)
{ chead->data=-1;
break;
}
p=p->next;
}
p=chead->pro;
while(p!=chead)
{ if(p->next!=chead)
p->data=p->data*chead->data+p->next->over;
if(p->next==chead)
p->data=p->data*chead->data;
p->over=0;
if(p->data>=10000)
p->over=1;
if(p->data<0)
p->over=-1;
p->data=p->data-p->over*10000;
p=p->pro;
}
p=chead->next;
while(p->data==0 && p->over==0 && p->next!=chead)
{ q=p;
p=p->next;
del(chead,q);
}
if(p->over>0)
{ q=(longint*)malloc(LEN);
q->data=p->over;
insert(chead,q); }
}
if(chead->next->data==0)
chead->data=0;
print(chead);
}

void minus(longint *a, longint *b) //两个循环链表分别存有两个长整数。
//用第一个长整数减第二个长整数并输出结果
{ b->data=(-1)*b->data; //将被减数的符号改变
plus(a,b); }

int main()
{ longint *a,*b;
char s1[100],s2[100];
int n;
cout<<"please input longint a:"<<endl;
gets(s1);
cout<<"please input longint b:"<<endl;
gets(s2);
a=get(s1);
b=get(s2);
cout<<"calulate: 1.a+b 2.a-b 3.b-a"<<endl;
cin>>n;
print(a);
print(b);
if(n==1)
plus(a,b);
if(n==2)
minus(a,b);
if(n==3)
minus(b,a);
system("pause");
return 0;
}

Page12