计算机算法设计与分析专业课程设计常规题目的C及C代码集.doc

合并排序1：
#include<iostream>
using namespace std;
const int N=100;
class list
{
public:
int array[N];
void input(int a);
void merge(int arrayc[],int arrayd[],int l,int m,int r);
void mergepass(int arrayx[],int arrayy[],int s);
void mergesort(int array1[]);
void diaplay(int a);
};
void list::input(int a)
{
cout<<"Please input shorted array:"<<endl;
for(int i=0;i<a;i++)
cin>>array[i];
}
void list::merge(int arrayc[],int arrayd[],int l,int m,int r)
{
int i=l;
int j=m+1;
int k=l;
while((i<=m)&&(j<=r))
if(arrayc[i]<=arrayc[j])
arrayd[k++]=arrayc[i++];
else arrayd[k++]=arrayc[j++];
if(i>m)
for(int q=j;q<=r;q++)
arrayd[k++]=arrayc[q];
else
for(int q=i;q<=m;q++)
arrayd[k++]=arrayc[q];
}
void list::mergepass(int arrayx[],int arrayy[],int s)
{
int i=0;
while(i<=N-2*s)
{
merge(arrayx,arrayy,i,i+s-1,i+2*s-1);
i=i+2*s;
}
if((i+s)<N)
merge(arrayx,arrayy,i,i+s-1,N-1);
else
for(int j=i;j<N;j++)
arrayy[j]=arrayx[j];
}
void list::mergesort(int array1[])
{
int array2[N];
int s=1;
while(s<N)
{
mergepass(array1,array2,s);
s+=s;
mergepass(array2,array1,s);
s+=s;
}
}
void list::diaplay(int a)
{
for(int i=N-a;i<N;i++)
cout<<array[i];
}
void main()
{
list f;
int a;
cout<<"请输入要合并排序数组大小：(数组最大上限 100)"<<endl;
cin>>a;
f.input(a);
f.mergesort (f.array);
f.diaplay (a);
}

合并排序：2
#include <iostream>
usingnamespace std;
void MERGES(int *A,int p,int q,int r) //下标 P<=q<r
{
int n1=q-p+1; //n1:p,q之间数个数
int n2=r-q; //n2：q以后到r数个数
int *L=newint [n1+1], //动态申请两个子数组
*R=newint [n2+1];
int i,j,k;
for (i=0;i<n1;i++)
{
L[i]=A[p+i-1];
}
for (j=0;j<n2;j++)
{
R[j]=A[q+j];
}
L[n1]=10000; //设置哨兵
R[n2]=10000;
i=0;
j=0;
for (k=p-1;k<r;k++)
{
if (L[i]<=R[j])
{
A[k]=L[i];
i=i+1;
}
else
{
A[k]=R[j];
j=j+1;
}
}
}
void MERGESORT(int *A,int p,int r)
{
if (p<r)
{
int q=(p+r)/2;
MERGESORT(A,p,q);
MERGESORT(A,q+1,r);
MERGES(A,p,q,r);
}
}
void main()
{
int x,z,p,r;
cout<<"请输入数组长度"<<endl;
cin>>x;
int *A= newint[x];
cout<<"请输入数组元素"<<endl;
for(int y=0;y<x;y++)
{
cin>>z;
A[y]=z;
}
cout<<"请输入上下限p，r"<<endl;
cin>>p>>r;
MERGESORT(A,p,r);
cout<<"合并排序后为："<<endl;
for (int m=p;m<=r;m++)
{
cout<<A[m];
}
delete []A;
}

合并排序3：
#include <iomanip.h>
#include <iostream.h> //这个函数将b[0]至b[right-left+1]拷贝到a[left]至a[right]
template <class T>
void Copy(T a[],T b[],int left,int right)
{
int size=right-left+1;
for(int i=0;i<size;i++)
{
a[left++]=b[i];
}
} //这个函数合并有序数组a[left:i],a[i+1:right]到b,得到新有序数组b
template <class T>
void Merge(T a[],T b[],int left,int i,int right)
{
int a1cout=left,//指向第一个数组开头
a1end=i,//指向第一个数组结尾
a2cout=i+1,//指向第二个数组开头
a2end=right,//指向第二个数组结尾
bcout=0;//指向b中元素
for(int j=0;j<right-left+1;j++)//实施right-left+1次循环
{
if(a1cout>a1end)
{
b[bcout++]=a[a2cout++];
continue;
}//假如第一个数组结束，拷贝第二个数组元素到b
if(a2cout>a2end)
{
b[bcout++]=a[a1cout++];
continue;
}//假如第二个数组结束，拷贝第一个数组元素到b
if(a[a1cout]<a[a2cout])
{
b[bcout++]=a[a1cout++];
continue;
}//假如两个数组全部没结束，比较元素大小，把较小放入b
else
{
b[bcout++]=a[a2cout++];
continue;
}
}
} //对数组a[left:right]进行合并排序
template <class T>
void MergeSort(T a[],int left,int right)
{
T *b=new int[right-left+1];
if(left<right)
{
int i=(left+right)/2;//取中点
MergeSort(a,left,i);//左半边进行合并排序
MergeSort(a,i+1,right);//右半边进行合并排序
Merge(a,b,left,i,right);//左右合并到b中
Copy(a,b,left,right);//从b拷贝回来
}
} //from
int main()
{
int n;
cout<<"how many numbers to sort:";
cin>>n;
int *a=new int[n];
cout<<"input "<<n<<" numbers:";
for(int i=0;i<n;i++)
{
cin>>a[i];
}
MergeSort( a, 0, n-1);
for(int j=0;j<n;j++)
{
cout<<setw(5)<<a[j];
}
return 1;
}

合并排序4：
#include <iostream>
using namespace std;
void Merge(int a[],int b[],int l,int m,int r)
{
int i=l,j=m+1,k=l;
while ((i<=m)&&(j<=r))
if (a[i]<=a[j])b[k++]=a[i++];
else b[k++]=a[j++];
if (i>m)
for(int q=j;q<=r;q++)
b[k++]=a[q];
else
for(int q=i;q<=m;q++)
b[k++]=a[q];
}
void Copy(int a[],int b[],int s,int n)
{
for(int i=s;i<=n;i++)
a[i]=b[i];
}
void MergeSort(int a[],int left,int right)
{
int i;
if(left<right)
{
i=(left+right)/2;
int b[100];
MergeSort(a,left,i);
MergeSort(a,i+1,right);
Merge(a,b,left,i,right);
Copy(a,b,left,right);
}
}
int main()
{
int a[100];
int n,i;
cout<<"输入元素个数n:";
cin>>n;
cout<<"输入一维数组a["<<n<<"]:";
for( i=0;i<n;i++)
cin>>a[i];
MergeSort(a,0,n-1);
cout<<"输出排序为:";
for ( i=0;i<n;i++)
cout<<a[i]<<' ';
cout<<endl;
return 0;
}

矩阵相乘1:
#include <iostream>
#include <stdio.h> 　
using namespace std;
int main()
{
int i, j, k;
cout<<"输入二维数组a行数和二维数组c行数x:";
int x;
cin>>x;
cout<<"输入二维数组a列数和二维数组b行数y:";
int y;
cin>>y;
cout<<"输入二维数组b列数和二维数组c行数z:";
int z;
cin>>z;
int **a, **b, **c;
a=new int*[x];
for(i=0;i<x;i++)
{
a[i]=new int[y];
}
cout<<"输入二维数组a:"<<endl;
for(i=0;i<x;i++)
{
for(j=0;j<y;j++)
{
cin>>a[i][j];
}
}
b=new int*[y];
for(i=0;i<y;i++)
{
b[i]=new int [z];
}
cout<<"输入二维数组b:"<<endl;
for(i=0;i<y;i++)
{
for(j=0;j<z;j++)
{
cin>>b[i][j];
}
}
c=new int*[x];
for(i=0;i<x;i++)
{
c[i]=new int [z];
}
cout<<"输入二维数组c:"<<endl;
for(i=0;i<x;i++)
{
for(j=0;j<z;j++)
{
c[i][j]=0;
}
}
for(i=0;i<x;i++)
{
for(j=0;j<z;j++)
{
for(k=0;k<y;k++)
{
c[i][j]+=a[i][k]*b[k][j];
}
}
}
for(i=0;i<x;i++)
{
for(j=0;j<z;j++)
{
cout<<c[i][j]<<' ';
}
cout<<endl;
}
for(i=0;i<x;i++)
{
delete [] a[i];
}
delete [] a;
for(i=0;i<x;i++)
{
delete [] c[i];
}
delete [] c;
for(i=0;i<y;i++)
{
delete [] b[i];
}
delete [] b;
return 0;
}

矩阵相乘2：
#include<iostream>
using namespace std;
#define M 2
#define N 3
#define P 4
int main()
{
int a[M][N]={{1,2,3},{4,5,6}};
int b[N][P]={{7,8,9,1},{2,3,4,5},{6,7,8,9}};
int c[M][P];
int i,j,k;
for(i=0;i<M;i++)
for(j=0;j<P;j++)
c[i][j]=0;
for(i=0;i<M;i++)
for(j=0;j<P;j++)
for(k=0;k<N;k++)
c[i][j]+=a[i][k]*b[k][j];
cout<<"矩阵相乘结果是："<<endl;
for(i=0;i<M;i++){for(j=0;j<P;j++)
cout<<c[i][j]<<" ";
cout<<endl;
}//system("pause");
return 0;
}

矩阵相乘3：
#include <iostream>
#include <iomanip>
using namespace std;
int main()
{
const int m=3;
const int n=3;
int a[m][n],i,j; //初始化数组 a,b
for(i=0;i<m;i++) //对数组 a 赋值并显示
{
for( j=0;j<n;j++)
{
cout<<"a["<<i<<"]"<<"["<<j<<"]=";
cin>>a[i][j];
}
}
for( i=0;i<m;i++)
{
for( j=0;j<n;j++)
cout<<setw(4)<<a[i][j];
cout<<endl;
}
const int k=3;
const int h=2;
int b[k][h],x,y;
for( x=0;x<k;x++)
{
for( y=0;y<h;y++)
{
cout<<"b["<<x<<"]"<<"["<<y<<"]=";
cin>>b[x][y];
}
}
for( x=0;x<k;x++)
{
for( y=0;y<h;y++)
cout<<setw(4)<<b[x][y];
cout<<endl;
}
int c[m][h]; //乘赋值给数组 c
for(int r=0;r<m;r++)
{
for(int t=0;t<h;t++) //数组 a 和 b 相//对数组 b 赋值并显示
{
c[r][t]=0;
for(int s=0;s<k;s++)
{
c[r][t]+=a[r][s]*b[s][t];
}
}
}
cout<<"c["<<m<<"]"<<"["<<h<<"]"<<endl;
for(int z=0;z<m;z++)
{
for(int w=0;w<h;w++)
cout<<setw(4)<<c[z][w];
cout<<endl;
}
return 0; //显示数组 c
}

矩阵相乘4：
#include<iostream>
using namespace std;
void chain(int*p,int n,int m[][7],int s[][7])//p维数数组，m最优乘次数组，s统计划分方案
{
int j;
for(int i=1;i<=n;i++)
m[i][i]=0;
for(int r=2;r<=n;r++)
{
for(i=1;i<=n-r+1;i++)
{
j=i+r-1;
m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];
s[i][j]=i;
for(int k=i+1;k<j;k++)
{
int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
if(t<m[i][j])
{
m[i][j]=t;
s[i][j]=k;
}
}
}
}
for(i=1;i<=n;i++)//我把它翻过来输出。。。
{
for(j=n;j>=i;j--)
{
cout<<m[i][j]<<'';
}
cout<<endl;
}
}
void Traceback(int i,int j,int s[][7])//输出相乘方案
{
if(i==j)
return;
Traceback(i,s[i][j],s);
Traceback(s[i][j]+1,j,s);
cout<<"Multiply A"<<i<<","<<s[i][j];
cout<<"and B"<<(s[i][j]+1)<<","<<j<<endl;
return;
}
int main()
{
int p[7],m[7][7],s[7][7],n;
while(n!=EOF)
{
for(int i=0;i<=n;i++)
{
cin>>p[i]>>endl;
}
chain(p,n,m,s);
Traceback(1,6,s);
}
return 0;
}

Haffman编码1：
#include<iostream>
#include<string>
using namespace std;
typedef struct
{
int weight;
int flag;
int parent;
int lchild;
int rchild;
}
hnodetype;
typedef struct
{
int bit[10];
int start;
char leaf;
}
hcodetype;
void huf(char cha[],int m[],int n)
{
int i,j,m1,m2,x1,x2,c,p;
hnodetype *huffnode=new hnodetype[2*n-1];
hcodetype *huffcode=new hcodetype[n],cd;
for(i=0;i<2*n-1;i++)
{
huffnode[i].weight=0;
huffnode[i].parent=0;
huffnode[i].flag=0;
huffnode[i].lchild=-1;
huffnode[i].rchild=-1;
}
for(i=0;i<n;i++)
{
huffnode[i].weight=m[i];
huffcode[i].leaf=cha[i];
}
for(i=0;i<n-1;i++)
{
m1=m2=10000000;
x1=x2=0;
for(j=0;j<n+i;j++)
{
if (huffnode[j].weight<=m1&&huffnode[j].flag==0)
{
m2=m1;
x2=x1;
m1=huffnode[j].weight;
x1=j;
}
else if(huffnode[j].weight<=m2&&huffnode[j].flag==0)
{
m2=huffnode[j].weight;
x2=j;
}
}
huffnode[x1].parent=n+i;
huffnode[x2].parent=n+i;
huffnode[x1].flag=1;
huffnode[x2].flag=1;
huffnode[n+i].weight=huffnode[x1].weight+huffnode[x2].weight;
huffnode[n+i].lchild=x1;
huffnode[n+i].rchild=x2;
}
for(i=0;i<n;i++)
{
cd.start=n-1;
c=i;
p=huffnode[c].parent;
while(p!=0)
{
if(huffnode[p].lchild==c)
cd.bit[cd.start]=0;
else
cd.bit[cd.start]=1;
cd.start--;
c=p;
p=huffnode[c].parent;
}
cout<<huffcode[i].leaf<<":";
for(j=cd.start+1;j<n;j++)
{
huffcode[i].bit[j]=cd.bit[j];
cout<<cd.bit[j];
}
cout<<endl;
huffcode[i].start=cd.start;
}
delete[] huffcode;
delete[] huffnode;
}
void main()
{
string str;
int i=0,j,n,m[100],h,k=0;
char cha[100];
cout<<"请输入一个字符串"<<endl;
cin>>str;
n=str.length();
cout<<"字符串总共有字符"<<n<<"个"<<endl;
for(i=0;i<n;i++)
{
j=0;
h=0;
while(str[i]!=str[j])
j++;
if(j==i)
{
cha[k]=str[i];
cout<<"字符"<<cha[k]<<"出现";
}
else continue;
for(j=i;j<n;j++)
{
if(str[i]==str[j])h++;
}
cout<<h<<"次"<<endl;
m[k]=h;
k++;
}
cout<<"每个字符哈夫曼编码是："<<endl;
huf(cha,m,k);
cin.get();
cin.get();
}

Haffman编码2：
#include <iostream>
using namespace std;
//********************************//结构哈夫曼树//********************************/*哈夫曼树次序表定义*/
typedef struct
{
int weight;
int parent,lchild,rchild;
}
HTNode;
typedef HTNode * HuffmanTree;/*初始化一个哈夫曼树*/
void InitHuffmanTree(HuffmanTree &HT,int m)
{
int i;
HT=new HTNode[m];
for(i=0;i<m;i++)
{
HT[i].weight=0;
HT[i].parent=-1;
HT[i].lchild=-1;
HT[i].rchild=-1;
}
}
//****************************************//从n个结点中选择最小两个结点//****************************************
void SelectMin(HuffmanTree &HT,int n,int &min1,int &min2)
{
typedef struct
{
int NewWeight;//存放权
int p;//存放该结点所在位置
}
TempNode,*TempTree;
TempTree TT=new TempNode[n];
int i,j;
j=0;
for(i=0;i<n;i++)
{
if(HT[i].parent==-1 && HT[i].weight!=0)
{
TT[j].NewWeight=HT[i].weight;
TT[j].p=i;
j++;
}
}//将HT中没有双亲结点存放到TT中
int m1,m2;
m1=m2=0;
for(i=0;i<j;i++)
{
if(TT[i].NewWeight<TT[m1].NewWeight)//此处不让取到相等，是因为结点中有相同权值时候，m1取最前那个。
m1=i;
}
for(i=0;i<j;i++)
{
if(m1==m2)
m2++;//当m1在第一个位置时候，m2向后移一位
if(TT[i].NewWeight<=TT[m2].NewWeight && i!=m1)//此处取到相等，是让在结点中有相同权值时候，//m2取最终那个。
m2=i;
}
min1=TT[m1].p;min2=TT[m2].p;
}/*创建哈夫曼树*/
void CreateHaffmanTree(HuffmanTree &HT,int n)
{
int i;
int m;
int min1,min2;
if(n<=1)
cout<<"Parameter Error!";
m=2*n-1;//哈夫曼树中结点个数
InitHuffmanTree(HT,m);
for(i=0;i<n;i++)
{
cin>>HT[i].weight;
}
for(i=n;i<m;i++)
{
SelectMin(HT,i,min1,min2);
HT[min1].parent=i;
HT[min2].parent=i;
HT[i].lchild=min1;
HT[i].rchild=min2;
HT[i].weight=HT[min1].weight+HT[min2].weight;
cout<<min1<<" "<<min2<<endl;
}
}
//***********************************//结构哈夫曼编码//***********************************/*哈夫曼编码定义*/
typedef struct
{
char ch;
char bits[10];
}
CodeNode;
typedef CodeNode * HuffmanCode;/*哈夫曼编码结构*/
void CreateHuffmanCode(HuffmanTree &HT,HuffmanCode &HC,int n)
{
int i;
int start;
int c;
int p;
char *cd;
char q;
HC=new CodeNode[n];
cd=new char[n];
cd[n-1]='/0';
for(i=0;i<n;i++)
{
cin>>q;
HC[i].ch=q;
start=n-1;
c=i;
while((p=HT[c].parent)>=0)
{
--start;
cd[start]=(HT[p].lchild==c)?'0':'1';c=p;
}
strcpy(HC[i].bits,&cd[start]);
}
delete cd;
}/*哈夫曼编码输出*/
void OutputHuffmanCode(HuffmanCode &HC,int n)
{
int i;
for(i=0;i<n;i++)
{
cout<<HC[i].ch<<" "<<HC[i].bits<<endl;
}
}
void main()
{
int i;
cout<<"输入字符个数：";
cin>>i;
HuffmanTree HT;
HuffmanCode HC;
CreateHaffmanTree(HT,i);
CreateHuffmanCode(HT,HC,i);
OutputHuffmanCode(HC,i);
}

图形着色1：
#include <cstdlib>
#include <iostream>//回溯法
using namespace std;//judge the coloration isValid or not.
bool isValid(bool b[5][5], int k, int x[])
{
for(int i=0; i<k; ++i)
if(!b[k][i])
continue;
else if(b[k][i] && x[k]== x[i])
return false;
return true;
}//by : 潘乔木
int main(int argc, char *argv[])
{
int n = 5;
int m = 3;//第i个顶点着色号码( 解向量 )
int x[5];
bool b[5][5]={ true,true,true,false,false,true, true,true,true,true,true, true,true,false,true,false,true,false,true,true,false,true,true,true,true };
for(int i=0; i<5; i++)
x[i] = 0;
int k=0;//whiles
while(k>=0)
{
x[k] = x[k] + 1;//着色无效继续再目前层搜索有效颜色
while(x[k]<=m && !isValid(b, k, x))
x[k] = x[k] + 1;
if(x[k]<=m)
{
if(k==n-1)
break; //successelse
//为下一个结点着色
k = k+1;
}
else
{ //返回至上一层
x[k] = 0;
k = k-1;
}
}//print
cout << "Five vertexes' coloration scheme is: " << endl;
for(int j=0; j<5; j++)
cout << x[j] << " ";
co