算法学习 之链表

/**********开放定址哈希表的存储结构**********/ 
int hashsize[ ] = { 997, ... }; // 哈希表容量递增表一个合适的素数序列
typedef struct 
{
ElemType *elem; // 数据元素存储基址，
int count; // 当前数据元素个数
int sizeindex;// sizeindex为当前容量
} HashTable;
#define SUCCESS 1
#define UNSUCCESS 0
#define DUPLICATE -1
Status SearchHash (HashTable H, KeyType Key, int &p, int &c) 
{ // 在开放定址哈希表H中查找关键码为K的元素，
// 若查找成功，以p指示待查数据元素在表中位置，
// 并返回SUCCESS；否则，以p指示插入位置，
// 并返回UNSUCCESS, c用以计冲突次数，其初值
// 置零，供建表插入时参考
p = Hash(Key);  //求得哈希地址
while ( H.elem[p].key != NULLKEY &&K != H.elem[p].key) 
// 该位置中填有记录并且关键字不相等
collision(p, ++c); // 求得下一探查地址p
if ((Key== H.elem[p].key) return SUCCESS; 
// 查找成功，p返回待查数据元素位置
else return UNSUCCESS; // 查找不成功，p返回的是插入位置
} // SearchHash

通过调用查找算法实现了开放定址哈希表的插入操作。

Status InsertHash (HashTable &H, Elemtype e) 
{ // 查找不成功时插入数据元素e到开放定址哈希表H
// 中，并返回OK；若冲突次数过大，则重建哈希表
c = 0;
if ( HashSearch ( H, e.key, p, c ) == SUCCESS )
return DUPLICATE;  //表中已有与e有相同关键字的元素
else if ( c < hashsize[H.sizeindex]/2 ) 
{  // 冲突次数c未达到上限，（阀值c可调）
H.elem[p] = e; ++H.count; return OK; // 插入e
} 
else RecreateHashTable(H);     // 重建哈希表
} // InsertHash

 

评论

12 楼 sblig 2012-05-22  

/*************有向图的十字链表*************/
#define MAX_VERTEX_NUM 20
typedef struct ArcBox 
{    int    tailvex, headvex; // 该弧的尾和头顶点的位置
struct ArcBox  *hlink, *tlink; 
// 分别指向下一个弧头相同和弧尾相同的弧的指针域
InfoType  *info;     // 该弧相关信息的指针
} ArcBox;
typedef struct VexNode 
{   VertexType data;
ArcBox *firstin, *firstout; 
// 分别指向该顶点第一条入弧和出弧
} VexNode;
typedef struct 
{   VexNode xlist[MAX_VERTEX_NUM];  // 表头向量
int vexnum, arcnum; // 有向图的当前顶点数和弧数
} OLGraph;

Status CreateDG (OLGraph &G)
{  int i,j,k,w,IncInfo;
   char v1,v2,V;
   ArcBox *p;
   printf ("input the number for vexnum and arcnum");
   scanf ("%d,%d",&G.vexnum , &G.arcnum);
IncInfo=0;IncInfo=IncInfo;
   V=getchar();   //skip the enter ,same as next...
   printf("input %d char for vexs \n",G.vexnum);
   for(i=0; i<G.vexnum; ++i)     //输入顶点
   {  G.xlist[i].data=getchar();  V=getchar();  }
   for(i=0; i<G.vexnum; ++i)     //初始化表头
   {  G.xlist[i].firstin=NULL;  G.xlist[i].firstout=NULL;}
   printf("input %d arc(char,char)  \n",G.arcnum);  //输入边
   for(k=0; k<G.arcnum; ++k)
   {  printf("%d:\n ",k);
      scanf("%c,%c",&v1,&v2);
      V=getchar(); V=V;
      i=LocateVex(G,v1);   j=LocateVex(G,v2);
      if(i !=100 && j !=100)
      {   p= (ArcBox*)malloc(sizeof(ArcBox)); 
 p->tailvex=i;    p->headvex=j;
          p->hlink = G.xlist[j].firstin;
p->tlink = G.xlist[i].firstout;
          G.xlist[j].firstin = G.xlist[i].firstout=p;
      }  //if
   } //for
  return OK;
}

---------∧∧∧∧∧∧∧∧∧----有向图的十字链表---∧∧∧∧∧∧∧∧∧∧∧-----

11 楼 sblig 2012-05-22  

/*******************邻接矩阵**********************/
#define INFINITY INT_MAX  100              // 最大值∞
#define MAX_VERTEX_NUM 20             // 最大顶点个数
typedef enum { DG，DNU，DG，UDN } GraphKind;
                            // { 有向图,有向网,无向图,无向网 }

typedef struct ArcCell
 {   VRType  adj;    // VRType是顶点关系类型，对无权图，用1
                     //或0表示相邻否；对带权图，则为权值类型
   InfoType  *info;  // 该弧相关信息的指针
} ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct MGraph
{   
VertexType vexs[MAX_VERTEX_NUM]; // 顶点向量
    AdjMatrix  arcs;                // 邻接矩阵
    int          vexnum, arcnum;    // 图的当前顶点数和弧(边)数
    GraphKind   kind;               // 图的种类标志
}MGraph;

Status CreateUDN (MGraph &G)     //创建无向网的邻接矩阵
{  
int i, j, k, w, IncInfo;
    char  v1, v2, V;
    printf("input the number for vexnum and arcnum");
    scanf("%d,%d", &G.vexnum, &G.arcnum);  
IncInfo=0;       // IncInfo=0表示各弧不含其他信息
    V=getchar();     //为了滤掉前面输入的空格符，后面亦同此原因
    printf("input %d char for vexs \n",G.vexnum);
    for(i=0; i<G.vexnum; ++i)    //输入网中所有顶点
    {   G.vexs[i]=getchar();   V=getchar();   }
    for(i=0; i<G.vexnum; ++i)       //初始化邻接矩阵
       for(j=0; j<G.vexnum; ++j)
       {  G.arcs[i][j].adj = INFINITY;
 G.arcs[i][j].info = NULL;
}
    printf("input %d arc(char,char,weight)\n", G.arcnum);
    for(k=0; k<G.arcnum; ++k)
{  printf("%d:\n",k);
       scanf("%c,%c,%d", &v1,&v2,&w); //输入一条弧的两个顶点以及权
       V=getchar(); V=V;
       i = LocateVex(G,v1);  //确定v1 v2在G中的位置
j = LocateVex(G,v2);
       if(i!=100 && j!=100)
	    {   G.arcs[i][j].adj = w;
	       if(IncInfo) scanf("%s" , G.arcs[i][j].info);
	       G.arcs[j][i].adj = G.arcs[i][j].adj ;
	    } //if
} //for
    return OK;
}

int LocateVex(Mgraph G, char v);
{
    for(i=0; i<G.vexnum; i++)
        if(G.vexs[i]==v)  return i;
    return ERROR;
}

---------∧∧∧∧∧∧∧∧∧----邻接矩阵---∧∧∧∧∧∧∧∧∧∧∧---------

10 楼 sblig 2012-05-22  

/*************无向图的邻接多重表*************/
#define MAX_VERTEX_NUM 20
typedef emnu {unvisited, visited } VisitIf;
typedef struct Ebox 
{   VisitIf  mark;    // 访问标记
int  ivex, jvex;   // 该边依附的两个顶点的位置
struct EBox  *ilink, *jlink; // 分别指向依附这两个顶点的下一条边
InfoType  *info;    //该边信息指针
} EBox;
typedef struct VexBox 
{   VertexType data;
EBox *firstedge;    //指向第一条依附该顶点的边
} VexBox;
typedef struct
{    VexBox adjmulist[MAX_VERTEX_NUM];
int vexnum, edgenum; // 无向图的当前顶点数和边数
} AMLGraph; 

Status CreateUDG (AMLGraph &G)
{  int i, j, k, w, IncInfo;
   char v1,v2,V;
   EBox *p;
   printf("input the number for vexnum and arcnum");
   scanf("%d,%d",&G.vexnum,&G.edgenum);
IncInfo=0;
   V=getchar();   //skip the enter ,same as next...
   printf("input %d char for vexs \n",G.vexnum);
   for(i=0;i<G.vexnum;++i)
   {   G.adjmulist[i].data=getchar();  V=getchar();  }
   for(i=0; i<G.vexnum; ++i) 
G.adjmulist[i].firstedge=NULL;
   printf("input %d arc(char,char)  \n",G.edgenum);
   for(k=0; k<G.edgenum; ++k)
   {  printf ("%d:\n ",k);
      scanf("%c,%c",&v1,&v2);
      V=getchar();  V=V;
      i=LocateVex(G,v1);   j=LocateVex(G,v2);
      if (i !=100 && j !=100)
      {  p=(Ebox*)malloc(sizeof(Ebox));  
p->ivex=i;   p->jvex=j;
         p->ilink = G.adjmulist[i].firstedge;
p->jlink = G.adjmulist[j].firstedge;
         G.adjmulist[i].firstedge = G.adjmulist[j].firstedge = p;
      }  //if
} //for
   return OK;
}

---------∧∧∧∧∧∧∧∧∧----无向图的邻接多重表---∧∧∧∧∧∧∧∧∧∧∧---------

9 楼 sblig 2012-05-22  

/*******************邻接表**********************/
#define MAX_VERTEX_NUM  20
typedef struct ArcNode       //边结点
{
int adjvex;                 // 该弧所指向的顶点的位置
struct ArcNode *nextarc;  // 指向下一条弧的指针
InfoType *info;            // 该弧相关信息的指针
} ArcNode;
typedef struct VNode          // 表头结点
{
VertexType data;    // 顶点信息
ArcNode *firstarc;  // 指向第一条依附该顶点的弧
} VNode, AdjList[MAX_VERTEX_NUM];
typedef struct ALGraph 
{
AdjList vertices;
int vexnum, arcnum; // 图的当前顶点数和弧数
int kind;            // 图的种类标志
} ALGraph;

Status CreateUDG (ALGraph &G)
{   int i,j,k,w,IncInfo;
    char v1,v2,V;
    ArcNode *p;
    printf("input the number for vexnum and arcnum");
    scanf("%d,%d",&G.vexnum , &G.arcnum); 
IncInfo=0;
    V=getchar();   //skip the enter ,same as next...
    printf("input %d char for vexs \n",G.vexnum);
    for(i=0; i<G.vexnum; ++i)         //初始化邻接表的表头
    {  G.vertices[i].data=getchar();   V=getchar();  }
    for(i=0;i<G.vexnum;++i)  
G.vertices[i].firstarc=NULL;
    printf("input %d arc(char,char)  \n",G.arcnum);
    for (k=0; k<G.arcnum; ++k)
    {   printf("%d:\n ",k);
        scanf("%c,%c",&v1,&v2);      //输入一条弧的两个顶点
        V=getchar(); V=V;
        i=LocateVex(G,v1);   j=LocateVex(G,v2);  //顶点定位
        if(i !=100 && j !=100)
        {  p=(ArcNode*)malloc(sizeof(ArcNode));
   p->adjvex=j;
           p->nextarc = G.vertices[i].firstarc;
G.vertices[i].firstarc = p;
           p=(ArcNode*)malloc(sizeof(ArcNode));
   p->adjvex=i;
           p->nextarc = G.vertices[j].firstarc;
G.vertices[j].firstarc = p;
        } //if
    } //for
    return OK;
}

---------∧∧∧∧∧∧∧∧∧----邻接表---∧∧∧∧∧∧∧∧∧∧∧---------

8 楼 sblig 2012-05-22  

如何建立线索链表？
在中序遍历过程中修改结点的左、右指针域，
以保存当前访问结点的“前驱”和“后继”信息。
遍历过程中，附设指针pre,
并始终保持指针pre指向当前访问的、指针p所指结点的前驱

Status InOrderThreading (BiThrTree &Thrt,  BiThrTree T) 
{  // 中序遍历二叉树T，并将其中序线索化，Thrt指向头结点。
if (!(Thrt = (BiThrTree)malloc(sizeof(BiThrNode)))) exit (OVERFLOW);
Thrt->ltag = 0;      Thrt->rtag =1;   // 建头结点
Thrt->rchild = Thrt;    // 右指针回指
if (!T)  Thrt->lchild = Thrt;   // 若二叉树空，则左指针回指
else 
{   Thrt->lchild = T;   pre = Thrt;
InThreading (T);   // 中序遍历进行中序线索化
pre->rchild = Thrt;     pre->rtag = 1; // 最后一个结点线索化
Thrt->rchild = pre; 
}
return OK;
} // InOrderThreading
void InThreading (BiThrTree p) 
{
if (p)
{ 
InThreading (p->lchild);   // 左子树线索化
if (!p->lchild)  { p->ltag = 1;       p->lchild = pre; } // 建前驱线索
if (!pre->rchild) { pre->rtag = 1;     pre->rchild = p; } // 建后继线索
pre = p;       // 保持pre指向p的前驱
InThreading (p->rchild);   // 右子树线索化
}
} // InThreading

---------∧∧∧∧∧∧∧∧∧----线索链表---∧∧∧∧∧∧∧∧∧∧∧---------

7 楼 sblig 2012-05-22  

/*************************平衡二叉树**********************/
typedef struct BSTNode
{
  ElemType  data;
  int         bf;
  struct  BSTNode  *lchild,*rchild;
} BSTNode, *BSTree

void R_Rotate (BSTree &p)
{  //以*p为根的二叉树右旋处理，旋转后p指向新的树根结点 
lc = p->lchild;
p->lchild = lc->rchild;
lc->rchild = p;  p = lc;
} // R_Rotate

void L_Rotate (BSTree &p)
{  //以*p为根的二叉树左旋处理，旋转后p指向新的树根结点 
rc=p->rchild;
p->rchild=rc->lchild;
rc->lchild=p;  p=rc;
} // R_Rotate


#define LH  1    //左高
#define EH  0   //等高
#define RH  -1   //右高

Status InsertAVL (BSTree &T, ElemType e, int &taller)
{   /*若在平衡的二叉排序树T中不存在和e相同关键字的结点，则插入，并返回1，否则返回0。若因插入而使二叉排序树失去平衡，则做相应的平衡旋转处理*，taller反映T长高与否*/
   if(!T)  //插入新结点，树长高
   {  T = (BSTree) malloc (sizeof(BSTNode));
      T->data=e;
T->lchild=T->rchild=NULL;
T->bf=EH;  taller=TRUE;
}
else
{  if (e==T->data)  {taller=FALSE;  return 0;}  //已存在e，不插入
    if (e<T->data)     //在左子树中搜索
{
   if (!InsertAVL(T->lchild,e,taller))  return 0;//在左子树中找到e不插入
   if(taller)      //已插入到左子树中
switch(T->bf)  //检查原本*T的平衡度
{
   case LH:  LeftBalance(T); taller=FALSE; break;
   case EH:  T->bf=LH; taller=TRUE; break;
   case RH:  T->bf=EH; taller=FALSE; break;
} //switch
} //if
else    
{  //在右子树中搜索
   if( !InsertAVL(T->rchild,e,taller))  return 0; 
   if( taller)
switch(T->bf)
{
    case LH:  T->bf=EH;   taller=FALSE;   break;
    case EH:  T->bf=RH;   taller=TRUE;    break;
    case RH:  RightBalance(T);   taller=FALSE;   break;
} //switch
} //else
} //else
return 1;
} //InsetAVL

6 楼 sblig 2012-05-22  

void LeftBalance (BSTree &T)
{
lc=T->lchild;
switch ( lc->bf )  //检查*T左子树平衡度
{  case LH:    //新结点插在*T的左孩子的左子树上
 T->bf=lc->bf=EH;  R_Rotate(T);   break;
   case RH:   //新结点插在*T的左孩子的右子树上
     rd = lc->rchild;
 swith(rd->bf)
{  case LH: T->bf = RH;  lc->bf = EH;  break；
          case EH: T->bf = lc->bf = EH;       break；
case RH: T->bf = EH;    lc->bf=LH;  break；
} //swith(rd->bf)
rd->bf=EH;
L_Rotate(T->lchild);  //*T的左子树左旋
R_Rotate(T);         //*T的右旋
}// switch(lc->bf)
} //LeftBalance

---------∧∧∧∧∧∧∧∧∧----二叉链表---∧∧∧∧∧∧∧∧∧∧∧---------

5 楼 sblig 2012-05-22  

(1)按给定的先序序列建立二叉链表

Status CreateBiTree(BiTree &T) 
{  // 按先序次序输入二叉树中结点的值（一个字符），
   //空格字符表示空树，构造二叉链表表示的二叉树T。
  scanf(&ch);
  if (ch==' ') T = NULL;
  else 
  {  if ( !(T = (BiTNode *)malloc(sizeof(BiTNode))))
               exit(OVERFLOW);
    T->data = ch; // 生成根结点
    CreateBiTree( T->lchild); // 构造左子树
    CreateBiTree( T->rchild); // 构造右子树
  }
  return OK;
} // CreateBiTree

如果按下列次序顺序输入字符
ABC□□DE□G□□F□□□  
构建的树的形态？？？

4 楼 sblig 2012-05-22  

(2)按二叉树的先序和中序序列建立二叉树

void createbitree (BiTree &T, char a[], int la, int ha, char b[], int lb, int hb)
{
int m;
char c;
if( la>ha ) T = NULL;
else {  if (!(T = (BiTree)malloc(sizeof(BiNode)))) exit (OVERFLOW);
     T->data=a[la];
         m=lb;
         while(b[m]!=a[la])  m++;
         createbitree(T->lchild, a, la+1, la+m-lb, b, lb, m-1);
         createbitree(T->rchild, a, la+m-lb+1, ha, b, m+1, hb);
       }
}
Status CreateBiTree(BiTree &T)
{ char a[10], b[10];
  int i, j, n;
  TElemType ch;
  n=0;
  cout<<"abcd*badc"<<endl;
  scanf("%c", &ch);
  while( ch! ='*' )   { a[n++]=ch;  scanf("%c", &ch);}
  for(i=0; i<n; i++)   scanf("%c", &b[i]);
  createbitree(T, a, 0, n-1, b, 0, n-1);
  return OK;
}

---------∧∧∧∧∧∧∧∧∧----二叉链表---∧∧∧∧∧∧∧∧∧∧∧---------

3 楼 sblig 2012-05-22  

一、构建哈夫曼树

＃define  n   7
＃define  m   2*n-1
typedef  struct
{   int weight;
    int parent, lchild, rchild;
} HTNode, *HuffmanTree; 

Status Huffman (HuffmanTree HT)
{ int   i, j, k, p1, p2;    
float  s1 ,  s2,  f ;
 for ( i =1 ; i < =m ; i + + )            //初始化
 {   HT[ i ].parent = 0 ;   HT[ i ].lchild = 0 ;
     HT[ i ].rchild = 0 ;   HT[ i ].weight = 0 ; 
 }
 for( i = 1 ; i < =n ; i + + )    //读入前n个结点的权值
 {   scanf (“%f”, &f ) ;
     HT[ i ].weight = f ;  
}
for ( i = n+1 ; i < =m ; i + + )  //进行n-1次合并，产生n-1个新结点
 {  p1 = p2 = 0;  
    s1 = s2 = max;   //max是float类型的最大值
    for ( j =1 ;  j < i;  j + + )    //选出两个权值最小的根结点
      if (HT[ j ].parent = = 0 )
      {
			if (s1== max) { p1=j;   continue;}
			if (s1!= max &&s2== max)
			{  if ( HT[j].weight < HT[p1].weight)  {p2=p1;  p1=j;}
		      else p2 = j; 	continue;
			}
			if (HT[j].weight < HT[p1].weight)
			{	p2=p1;	p1=j;	continue;   }
			if (HT[j].weight < HT[p2].weight)
			{	p2=j;   continue;}
		} //if
    HT[ p1 ].parent = i ;  HT[ p2 ].parent = i ; 
    HT[ i ].lchild =p1 ; //最小权根结点是新结点的左孩子，分量号是下标加1
    HT[ i ].rchild =p2 ;    //次小权根结点是新结点的右孩子
    HT[ i ].weight = HT[ p1 ].weight ＋HT[ p2].weight ;
  }//for
} //Huffman

2 楼 sblig 2012-05-22  

二、产生哈夫曼编码，并用得到的哈夫曼编码对电文进行编码译码

typedef  struct
{   int data;
    int parent, lchild, rchild;
} HTNode, *HuffmanTree; 
typedef char**   HuffmanCode;   //指向字符串的指针
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n)
{
  if (n<=1) return;
  m=2*n-1;
  HT= ( HuffmanTree) malloc((m+1)*sizeof(HTNode));
  for (p=HT+1,i=1; i<=n; ++i,++p,++w)  * p={*w,0,0,0};
  for ( ; i<=m; ++i,++p)                *p={0,0,0,0}; //HT初始化:p149图(a)
  for (i=n+1; i<=m; ++i)
{  Select (HT, i-1, p1, p2);  //在HT[0]至HT[i]中选出权最小的2个根节点
     HT[p1].parent = i;  HT[p2].parent = i;
     HT[i].lchild = p1;   HT[i].rchild = p2;
HT[i].weight = HT[p1]. weight + HT[p2]. weight;
}   // 建立哈夫曼树，p149图(b)
HC = ( HuffmanCode)malloc((n+1)sizeof(char *));
// n+1个指向字符串的指针组成的数组
cd = (char*)malloc (n*sizeof(char) );
cd[n-1] = ‘\0’;
for(i=1; i<=n; ++i)
{  start = n-1;
   for (c=i, f=HT[i].parent; f!=0; c=f, f=HT[f].parent)
     if(HT[f].lchild==c)   cd[--start]=’0’;
     else                cd[--start]=’1’;
HC[i] = (char*)malloc((n-start)*sizeof(char));
strcpy(HC[i] , &cd[start]);
}
free(cd);
}

1 楼 sblig 2012-05-22  

Status TexttoCode (HuffmanTree HT, HuffmanCode HC )
{ 
cout<<"please input the text:";
	cin>>c;
	cout<<"The  code   is:";
	for(i=1; i<=strlen(c); i++)
   {
		for(j=1; j<=8; j++)
		if(c[i-1]= =HT[j].zimu)
		{
			cout<< HC[j]; 	break;
		}
   }
   cout<<endl;
}

Status CodetoText(HuffmanTree HT, HuffmanCode HC)
{
cout<<"Enter the code:";
   cin>>c;
   j=strlen(c);
   yu=15;
   i=1;
   while( i<= j)
   {
	  while(HT[yu].lchild != 0)
{
		if(c[i-1]= ='0')
		{
			yu=HT[yu].lchild;
			i++;  continue;
		}
		if(c[i-1]= ='1')
		{
		   yu=HT[yu].rchild;
			i++;  continue;
		}
   }
cout<<HT[yu].zimu;
yu=15;
	}
}

---------∧∧∧∧∧∧∧∧∧----哈夫曼树---∧∧∧∧∧∧∧∧∧∧∧---------