Timmy's Blog

Sort.h

struct ElemType{
char name[10];
int mark;
};

void InsertSort(ElemType A[],int n) //straight insertion sorting
{
ElemType x;
int i,j;
for(i=1;i x=A[i];
for(j=i-1;j>=0;j–)
if(x.mark>A[j].mark)
A[j+1]=A[j];
else
break;
A[j+1]=x;
}
}

void ShellSort(ElemType A[],int n)
{
ElemType x;
int i,j,d;
for(d=n/2;d>=1;d/=2){
for(i=d;i x=A[i];
for(j=i-d;j>=0;j-=d){
if(x.mark>A[j].mark)
A[j+d]=A[j];
else
break;
}
A[j+d]=x;
}
}
}

void SelectSort(ElemType A[],int n)
{
ElemType x;
int i,j,k;
for(i=1;i< =n-1;i++){
k=i-1;
for(j=i;j< =n-1;j++)
if(A[j].mark>A[k].mark)
k=j;
if(k!=i-1){
x=A[i-1];
A[i-1]=A[k];
A[k]=x;
}
}
}

void PrintSortResultByMark(ElemType A[],int n)
{
int i,rank;
cout< <"Name Mark Rank"< for(i=0;i rank=i+1;
if(i>0&&A[i].mark==A[i-1].mark)
rank–;
cout< }
}

void PrintSortResultByOrder(ElemType A[],int n)
{
int i,rank;
cout< <"Rank Name Mark"< for(i=0;i rank=i+1;
if(i>0&&A[i].mark==A[i-1].mark)
rank–;
cout< }
}
阅读全文…

Index.h

typedef struct{
int key; //职工号，作为关键字域
char depart[13]; //部门名称，作为索引值域
int next; //链接同一部门的职工记录
}ElemType;
typedef char IndexKeyType[13];
struct IndexItem{
IndexKeyType index;
int start;
int length;
};
typedef IndexItem indexlist[ILMaxSize];
typedef ElemType mainlist[MaxSize];

void CreateIndexList(mainlist A, int n, indexlist B, int m)
{
int i,j;
for(j=0;j B[j].start=-1;
B[j].length=0;
}
for(i=0;i for(j=0;j if(strcmp(A[i].depart,B[j].index)==0){
if(B[j].start==-1)
B[j].start=i;
B[j].length++;
}
int t;
for(j=0;j t=B[j].start;
for(i=0;i if(i==B[j].start)
continue;
if(strcmp(A[i].depart,B[j].index)==0){
A[t].next=i;
t=i;
}
}
}
cout< <"now print the mainlist after sort :"< for(j=0;j i=B[j].start;
while(i!=-1){
cout< “;
i=A[i].next;
}
cout< }
}

void SearchIndexList(mainlist A, int n, indexlist B, int m, ElemType worker)
{
int i,j;
for(i=0;i if(strcmp(worker.depart,B[i].index)==0)
break;
if(i==m)
exit(1);
j=B[i].start;
while(j!=-1)
if(worker.key==A[j].key){
cout< <"found the record matched in "< break;
}
else
j=A[j].next;
if(j==-1)
cout< <"Not found."<}

void InsertIndexList(mainlist A, int n, indexlist B, int m, ElemType worker)
{
int i,j;
for(i=0;i j=i;
if(strcmp(worker.depart,A[j].depart)==0){
while(A[j].next!=-1)
j=A[j].next;
A[j].next=n;
strcpy(A[n].depart,worker.depart);
A[n].key=worker.key;
A[n].next=-1;
}
}
for(j=0;j if(strcmp(worker.depart,B[j].index)==0){
B[j].length++;
break;
}
}
阅读全文…

Graph3.h

void InitAdjoin(adjlist G)
{
for(int i=0;i G[i]=NULL;
}

void CreateAdjoin(adjlist G, int n)
{
char *s=new char[100];
cerr< <"please input the adjmatrix :"< cin>>s;
istrstream sin(s);
char c1,c2,c3;
int i,j;
Edgenode *p;
sin>>c1;
do{
sin>>c1>>i>>c2>>j>>c3;
p=new Edgenode;
p->adjvex=j;
p->next=G[i];
G[i]=p;
sin>>c1;
if(c1=='}')
break;
}while(1);
}

void PrintAdjoin (adjlist G, int n)
{
int i,j;
Edgenode *p;
cout< <"V={";
for(i=0;i cout< cout< cout< <"E={";
for(i=0;i p=G[i];
while(p){
j=p->adjvex;
cout< <'<'<'< <',';
p=p->next;
}
}
cout< <'}'<}
阅读全文…

Test9.cpp
[codes=c]
#include<iostream.h>
#include<stdlib.h>
#include<strstrea.h>
typedef int VertexType;
typedef int WeightType;
const int MaxVertexNum=10;
const WeightType MaxValue=20000;
typedef int adjmatrix[MaxVertexNum][MaxVertexNum];
struct edgenode
{
    int adjvex;
    edgenode *next;
};
typedef edgenode *adjlist[MaxVertexNum];
#include"Graph2.h"

void PATH(adjlist path,int m,int j)
{
  edgenode *p,*q,*s;
  p=path[j];
  while(p!=NULL)
  {
    path[j]=p->next;
    delete p;
    p=path[j];
  }
  p=path[m];
  while(p!=NULL)
  {
    q=new edgenode;
    q->adjvex=p->adjvex ;
    if(path[j]==NULL)
    {
      path[j]=q;
    }
    else    
      s->next=q;
    s=q;
    p=p->next;
  }
  q=new edgenode;
  q->adjvex=j;
  q->next=NULL;
  s->next=q;
}

void Dijkstra(adjmatrix GA,int dist[],adjlist path,int i,int n)
{
  int *s=new int[MaxVertexNum];
  for(int j=0;j<n;j++)
  {
    if(j==i)
      s[j]=1;
    else
      s[j]=0;
    dist[j]=GA[j];
    if((dist[j]<MaxValue)&&(j!=i))
    {
      edgenode *p1=new edgenode;
      edgenode *p2=new edgenode;
      p1->adjvex=i;
      p2->adjvex =j;
      p2->next =NULL;
      p1->next=p2;
      path[j]=p1;
    }
    else
      path[j]=NULL;
  }
  int w;
  int m;
  for(int k=1;k<=n-2;k++){
    w=MaxValue;
    m=i;
    for(j=1;j<n;j++)
      if(s[j]==0&&dist[j]<w){
        w=dist[j];
        m=j;
      }
      if(m!=i)
        s[m]=1;
      else
        break;
      for(j=0;j<n;j++)
        if(s[j]==0&&dist[m]+GA[m][j]<dist[j]){
          dist[j]=dist[m]+GA[m][j];
          PATH(path,m,j);
        }
  }
}

void PrintPath(int dist[], edgenode *path[], int n)
{
  int i,t;
  for(i=1;i<n;i++){
    edgenode *p=path;
    cout<<"V={";
    while(p!=NULL){
      cout<<p->adjvex<<',';
      p=p->next;
    }
    cout<<"}"<<"    length: "<<dist<<endl;
  }
}

void main()
{
    adjmatrix GA;
  int n;
  cout<<"input the points of the graph: ";
  cin>>n;
  InitMatrix(GA);
  CreateMatrix(GA,n);
  PrintMatrix(GA,n);
  cout<<endl;
  cout<<"now print the path and length from v0 to others :"<<endl;
    adjlist path;
    int *dist=new int[MaxVertexNum];
    Dijkstra(GA,dist,path,0,n);
  PrintPath(dist,path,n);
}
[/codes] 阅读全文…

Graph1.h

void InitMatrix(adjmatrix G)
{
int i,j;
for(i=0;i for(j=0;j if(i==j)
G[i][j]=0;
else
G[i][j]=MaxValue;
}

void CreateMatrix(adjmatrix G,int n)
{
char *s=new char[100];
cerr< <"please input the matrix: ";
cin>>s;
istrstream sin(s);
char c1,c2,c3;
int i,j;
WeightType w;
sin>>c1;
do{
sin>>c1>>i>>c2>>j>>c3>>w;
if(i*j<0||i>n-1||j>n-1)
exit(1);
G[i][j]=G[j][i]=w;
sin>>c1;
if(c1=='}')
break;
}while(1);
}

void PrintMatrix(adjmatrix G,int n)
{
int i,j;
cout< <"V={";
for(i=0;i cout< cout< cout< <"E={";
for(i=0;i for(j=0;j if(G[i][j]!=0&&G[i][j]!=MaxValue)
if(i cout< <'('< cout< <'}'<}

void InitArray(edgeset GE)
{
for(int i=0;i GE[i].fromvex=GE[i].endvex=-1;
GE[i].weight=MaxValue;
}
}

阅读全文…

Haffman.h

struct BTreeNode{
ElemType data;
BTreeNode* left;
BTreeNode* right;
};

BTreeNode* CreateHuffman(ElemType a[],int n)
{
BTreeNode **b,*q;
b=new BTreeNode*[n];
int i,j;
for(i=0;i b[i]=new BTreeNode;
b[i]->data=a[i];
b[i]->left=b[i]->right=NULL;
}
for(i=1;i int k1=-1,k2;
for(j=0;j if(b[j]!=NULL&&k1==-1){
k1=j;
continue;
}
if(b[j]!=NULL){
k2=j;
break;
}
}
for(j=k2;j if(b[j]!=NULL){
if(b[j]->datadata){
k2=k1;
k1=j;
}
else if(b[j]->datadata)
k2=j;
}
}
q=new BTreeNode;
q->data=b[k1]->data+b[k2]->data;
q->left=b[k1];
q->right=b[k2];
b[k1]=q;
b[k2]=NULL;
}
delete []b;
return q;
}

void HuffManCoding(BTreeNode *BT, int len)
{
static int a[10];
if(BT!=NULL){
if(BT->left==NULL&&BT->right==NULL){
cout< <"结点权值为"<data< <"的编码：";
for(int i=0;i cout< cout< }
else{
a[len]=0;
HuffManCoding(BT->left,len+1);
a[len]=1;
HuffManCoding(BT->right,len+1);
}
}
}

阅读全文…