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

合并排序1：
#include
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:"<>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)nt s=1;
while(s
cin>>a;
f.input(a);
f.mergesort (f.array);
f.diaplay (a);
}

合并排序：2
#include
usingnamespace std;
void MERGES(int *A,int p,int q,int r) //下标 P<=q
*R=newint [n2+1];
int i,j,k;
for (i=0;i
i=i+1;
}
else
{
A[k]=R[j];
j=j+1;
}
}
}
void MERGESORT(int *A,int p,int r)
{
if (pin()
{
int x,z,p,r;
cout<<"请输入数组长度"<>x;
int *A= newint[x];
cout<<"请输入数组元素"<>z;
A[y]=z;
}
cout<<"请输入上下限p，r"<>p>>r;
MERGESORT(A,p,r);
cout<<"合并排序后为："<or (int m=p;m<=r;m++)
{
cout<
#include //这个函数将b[0]至b[right-left+1]拷贝到a[left]至a[right]
template
void Copy(T a[],T b[],int left,int right)
{
int size=right-left+1;
for(int i=0i
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;ja1end)
{
b[bcout++]=a[a2cout++];
continue;
}//假如第一个数组结束，拷贝第二个数组元素到b
if(a2cout>a2end)
{
b[bcout++]=a[a1cout++];
continue;
}//假如第二个数组结束，拷贝第一个数组元素到b
if(a[a1cout]
void MergeSort(T a[],int left,int right)
{
T *b=new int[right-left+1];
if(lefthow many numbers to sort:";
cin>>n;
int *a=new int[n];
cout<<"input "<>a[i];
}
MergeSort( a, 0, n-1);
for(int j=0;j
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
{
int a[100];
int n,i;
cout<<"输入元素个数n:";
cin>>n;
cout<<"输入一维数组a["<>a[i];
MergeSort(a,0,n-1);
cout<<"输出排序为:";
for ( i=0;i
#include 　
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输入二维数组a:"<>a[i][j];
}
}
b=new int*[y];
for(i=0;i>b[i][j];
}
}
c=new int*[x];
for(i=0;i {
c[i]=new int [z];
}
cout<<"输入二维数组c:"<{
cout<clude
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;ifor(k=0;k
#include
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
}
return 0; //显示数组 c
}

矩阵相乘4：
#include
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=i;j--)
{
cout<
}
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"<t i=0;i<=n;i++)
{
cin>>p[i]>>endl;
}
chain(p,n,m,s);
Traceback(1,6,s);
}
return 0;
}

Haffman编码1：
#include
#include
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 {
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
cd.bit[cd.start]=1;
cd.start--;
c=p;
p=huffnode[c].parent;
}
cout<uffnode;
}
void main()
{
string str;
int i=0,j,n,m[100],h,k=0;
char cha[100];
cout<<"请输入一个字符串"<>str;
n=str.length();
cout<<"字符串总共有字符"<cout<<"字符"<
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)
{
if(TT[i].NewWeight/
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>HT[i].weight;
}
for(i=n;i HT[min2].parent=i;
HT[i].lchild=min1;
HT[i].rchild=min2;
HT[i].weight=HT[min1].weight+HT[min2].weight;
cout<odeNode;
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>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}
void main()
{
int i;
cout<<"输入字符个数：";
cin>>i;
HuffmanTree HT;
HuffmanCode HC;
CreateHaffmanTree(HT,i);
CreateHuffmanCode(HT,HC,i);
OutputHuffmanCode(HC,i);
}

图形着色1：
#include
#include //回溯法
using namespace std;//judge the coloration isValid or not.
bool isValid(bool b[5][5], int k, int x[])
{
for(int i=0; itrue,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