bbs.txt

几种数据结构算法的C程序实现

各位，新来乍到，小生有礼了，献拙作几篇，还望多多指教。
QQ：289185927
算法参考教材为严蔚敏C语言版的数据结构。
以下全部程序均在VC++6.0中调试通过。

排序：
将代码中的129到132行加上或去掉注释标记可实现不同的排序算法。
Record中的info域存储元素编号以测试算法稳定性。

#include "stdio.h"
#define MAX 40

typedef struct Record
{
 int key;
 int info;
}Record;

typedef struct SqList
{
 Record r[MAX+1];
 int length;
}SqList;

int Partition(SqList *L, int low, int high)
{
 int pivotkey=(*L).r[low].key;
 (*L).r[0]=(*L).r[low];
 while(low<high)
 {
  while(low<high&&(*L).r[high].key>=pivotkey)--high;
  (*L).r[low]=(*L).r[high];
  while(low<high&&(*L).r[low].key<=pivotkey)++low;
  (*L).r[high]=(*L).r[low];
 }
 (*L).r[low]=(*L).r[0];
 return low;
}

void QuickSort(SqList *L, int low, int high)
{
 int pivot;
 if(low<high)
 {
  pivot=Partition(L,low,high);
  QuickSort(L,low,pivot-1);
  QuickSort(L,pivot+1,high);
 }
}


void BubbleSort(SqList *L)
{
 int i,j,change;
 for(i=(*L).length,change=1;i>1&&change;--i)
 {
 change=0;
 for(j=1;j<i;++j)
 {
  if((*L).r[j].key>(*L).r[j+1].key)
  {
   (*L).r[0]=(*L).r[j];
   (*L).r[j]=(*L).r[j+1];
   (*L).r[j+1]=(*L).r[0];
   change=1;
  } 
 }
 }
}


void SelectSort(SqList *L)
{
 int i,j,k;
 for(i=1;i<(*L).length;i++)
 {
 k=i;
 for(j=i+1;j<=(*L).length;j++)
  if((*L).r[j].key<(*L).r[k].key) k=j;
 if(k!=i){(*L).r[0]=(*L).r[k];(*L).r[k]=(*L).r[i];(*L).r[i]=(*L).r[0];}
 }
}


void InsertSort(SqList *L)      /*教材P265算法10.1*/
{
 int i,j;
 for(i=2;i<=(*L).length;i++)
 {
 if((*L).r[i].key<(*L).r[i-1].key)
 {
  (*L).r[0]=(*L).r[i];(*L).r[i]=(*L).r[i-1];
  for(j=i-2;j>0&&(*L).r[j].key>(*L).r[0].key;j--)
   (*L).r[j+1]=(*L).r[j];
  (*L).r[j+1]=(*L).r[0];
 }
 }
}


void Print(SqList L)
{
 int i;
 printf("Number:");
 for(i=1;i<=L.length;i++)
  printf("%4d",L.r[i].info);
 printf("\n");
 printf("  Elem:");
 for(i=1;i<=L.length;i++)
  printf("%4d",L.r[i].key);
}


void create(SqList *L)
{
 int i;
 while((*L).length<MAX)
 {
  scanf("%d",&i);
  if(i==-1) break;
  (*L).r[++(*L).length].key=i;
 }
}

main()
{
 int i,low,high;
 SqList L;
 L.length=0;
 printf("Input the elem data of SqList:\n");
 create(&L);
 for(i=1;i<=L.length;i++)
  L.r[i].info=i;
 Print(L);
 printf("\n");
 printf("Now, the SqList will be sorted\n");
 low=1;  high=L.length;
 InsertSort(&L);
 /*SelectSort(&L);*/
 /*BubbleSort(&L);*/
 /*QuickSort(&L,low,high);*/
 Print(L);
 printf("\n");
}


堆排序：教材P282算法10.10，10.11

#include "stdio.h"
#define MAX 20

typedef struct Record
{
 int key;
 int info;
}Record;

typedef struct SqList
{
 Record r[MAX+1];
 int length;
}SqList;

void create(SqList *L)
{
 int i;
 while((*L).length<MAX)
 {
  scanf("%d",&i);
  if(i==-1) break;
  (*L).r[++(*L).length].key=i;
 }
}


void HeapAdjust(SqList *L, int s, int m)
{
 int j; Record rc;
 rc=(*L).r[s];
 for(j=2*s;j<=m;j*=2)
 {
 if(j<m&&(*L).r[j].key<(*L).r[j+1].key) ++j;
 if(rc.key>=(*L).r[j].key) break;
 (*L).r[s]=(*L).r[j]; s=j;
 }
 (*L).r[s]=rc;
}


void HeapSort(SqList *L)
{
 int i;Record temp;
 for(i=(*L).length/2;i>=1;--i)
 HeapAdjust(L,i,(*L).length);
 for(i=(*L).length;i>1;--i)
 {
 temp=(*L).r[1];(*L).r[1]=(*L).r[i];(*L).r[i]=temp;
 HeapAdjust(L,1,i-1);
 }
}


void Print(SqList L)
{
 int i;
 printf("Number:");
 for(i=1;i<=L.length;i++)
  printf("%4d",L.r[i].info);
 printf("\n");
 printf("  Elem:");
 for(i=1;i<=L.length;i++)
  printf("%4d",L.r[i].key);
}


main()
{
 int i;
 SqList L;
 L.length=0;
 printf("Input the data of the list ending with -1:\n");
 create(&L);
 for(i=1;i<=L.length;i++)
  L.r[i].info=i;
 Print(L);
 printf("\nNow the list will be heap sorted:\n");
 HeapSort(&L);
 Print(L);
 printf("\n");
}


图的建立及深广度优先遍历：（用邻接表）

#include "stdio.h"
#include "stdlib.h"
#include "malloc.h"
#define Null 0
#define MAX 20

typedef struct ArcNode
{
 int adjvex;
 int weight;
 struct ArcNode *nextarc;
}ArcNode,*AdjList;

typedef struct Graph
{
 AdjList elem[MAX+1];
 int vexnum;
 int arcnum;
 int GraphKind;
}Graph;

/*对列定义及相关操作*/

typedef struct Queue
{
 int elem[MAX];
 int front,rear;
}Queue;

int visited[MAX+1];

void initQueue(Queue *Q)
{
 (*Q).front=(*Q).rear=0;
}

int QueueEmpty(Queue Q)
{
 if(Q.front==Q.rear) return 1;
 else return 0;
}

int EnQueue(Queue *Q, int v)
{
 (*Q).elem[(*Q).rear]=v;
 (*Q).rear=((*Q).rear+1)%MAX;
 return v;
}

int DeQueue(Queue *Q, int *v)
{
 *v=(*Q).elem[(*Q).front];
 (*Q).front=((*Q).front+1)%MAX;
 return (*v);
}


void create(Graph *G)
{
 int i, start, end;     AdjList p;
 for(i=0;i<=MAX;i++)
  (*G).elem[i]=Null;
 for(i=1;i<=(*G).arcnum;i++)
 {
 /*输入弧的起止顶点*/
  scanf("%d,%d",&start,&end);
  p=(AdjList)malloc(sizeof(ArcNode));
  p->adjvex=end;
  p->nextarc=(*G).elem[start];
  (*G).elem[start]=p;
  if((*G).GraphKind==0)
  {
   p=(AdjList)malloc(sizeof(ArcNode));
   p->adjvex=start;
   p->nextarc=(*G).elem[end];
   (*G).elem[end]=p;
  }
 }
}

int NextAdjVex(Graph G, int v, int w)
{
 AdjList p;
 for(p=G.elem[v];p->adjvex!=w;p=p->nextarc);
 if(p->nextarc==Null) return 0;
 else return (p->nextarc->adjvex);
}

int FirstAdjVex(Graph G, int v)
{
 if(!G.elem[v]) return 0;
 else return G.elem[v]->adjvex;
}

void DFS(Graph G, int v)
{
 int w;
 printf("v%d ",v);   visited[v]=1;
 for(w=FirstAdjVex(G,v);w;w=NextAdjVex(G,v,w))
  if(!visited[w]) DFS(G,w);
}

void DFSTraverse(Graph G)
{
 int v;
 for(v=1;v<=G.vexnum;v++)
  visited[v]=0;
 for(v=1;v<=G.vexnum;v++)
  if(!visited[v]) DFS(G,v);
}

void BFS(Graph G)
{
 int v,w;
 Queue Q;
 initQueue(&Q);
 for(v=1;v<=G.vexnum;v++)
  visited[v]=0;
 for(v=1;v<=G.vexnum;v++)
 {
  printf("v%d ",v);   visited[v]=1;
  EnQueue(&Q,v);
  while(!QueueEmpty(Q))
  {
   DeQueue(&Q,&v);
   for(w=FirstAdjVex(G,v);w;w=NextAdjVex(G,v,w))
    if(!visited[w]){printf("v%d ",w);visited[w]=1;EnQueue(&Q,w);}
  }
 }
}

void printAdjList(Graph G)
{
 int i;     AdjList p;
 for(i=1;i<=G.vexnum;i++)
 {
  printf("v%d: ",i);
  if(!(G.elem[i])) {printf("\n\n"); continue;}
  else{
       for(p=G.elem[i];p;p=p->nextarc)
  printf("%d ",p->adjvex);
       printf("\n\n");
      }
 }
}

main()
{
 Graph G;
 printf("Please input the number of vex, arc and GraphKind:");   
 /*输入图的顶点数，弧数及图的类型0：无向，1：有向。*/
 scanf("%d,%d,%d",&G.vexnum,&G.arcnum,&G.GraphKind);
 printf("Input the arc of the Graph:\n");
 create(&G);
 printf("\n\n");
 printAdjList(G);
 printf("\n\n");
 printf("DFS Traverse:\n");
 DFSTraverse(G);
 printf("\n");
 printf("BFSTraverse:\n");
 BFS(G);
 printf("\n");
}

/*教材P182算法7.12拓扑排序*/

#include "stdio.h"
#include "stdlib.h"
#include "malloc.h"
#define Null 0
#define MAX 20

typedef struct ArcNode
{
 int adjvex;
 int weight;
 struct ArcNode *nextarc;
}ArcNode,*AdjList;

typedef struct Graph
{
 AdjList elem[MAX+1];
 int vexnum;
 int arcnum;
 int GraphKind;
}Graph;


typedef struct Stack
{
 int s[MAX];
 int top;
}Stack;

void initStack(Stack *s)
{
 (*s).top=0;
}

int Push(Stack *s, int e)
{
 if((*s).top>=MAX) return 0;
 else (*s).s[(*s).top++]=e;
}

int Pop(Stack *s, int *e)
{
 if((*s).top<=0) return 0;
 else *e=(*s).s[--(*s).top];
}

int StackEmpty(Stack s)
{
 if(s.top==0)return 1;
 else return 0;
}


void create(Graph *G)
{
 int i, start, end;     AdjList p;
 for(i=0;i<=MAX;i++)
  (*G).elem[i]=Null;
 for(i=1;i<=(*G).arcnum;i++)
 {
  scanf("%d,%d",&start,&end);
  p=(AdjList)malloc(sizeof(ArcNode));
  p->adjvex=end;
  p->nextarc=(*G).elem[start];
  (*G).elem[start]=p;
  if((*G).GraphKind==0)
  {
   p=(AdjList)malloc(sizeof(ArcNode));
   p->adjvex=start;
   p->nextarc=(*G).elem[end];
   (*G).elem[end]=p;
  }
 }
}


int TopoSort(Graph G)
{
 int i, count, indegree[MAX+1];
 AdjList p; Stack S;
 for(i=1;i<=G.vexnum;i++)
  indegree[i]=0;
 initStack(&S);
 for(i=1;i<=G.vexnum;i++)
  for(p=G.elem[i];p;p=p->nextarc)
   ++indegree[p->adjvex];
 for(i=1;i<=G.vexnum;i++)
  if(!indegree[i]) Push(&S,i);
 count=0;
 while(!StackEmpty(S))
 {
 Pop(&S,&i);
 printf("v%d ",i);++count;
 for(p=G.elem[i];p;p=p->nextarc)
  if(!(--indegree[p->adjvex])) Push(&S,p->adjvex);
 }
 if(count<G.vexnum) return 0;
 else return 1;
}


main()
{
 Graph G;
 printf("Please input the number of vex, arc and GraphKind:");
 scanf("%d,%d,%d",&G.vexnum,&G.arcnum,&G.GraphKind);
 create(&G);
 printf("The outcome of TopoSort is:\n");
 TopoSort(G);
}


汉诺塔程序：程序执行后会生成hannoi.txt文件其中记录了移动n个盘子的步骤

#include "stdio.h"


move(char a,char c,FILE **fp,int *count)
{
 (*count)++;
 printf("%6d:%c-->%c\n",*count,a,c);
 fprintf(*fp,"%6d:%c-->%c\n",*count,a,c);
}


hanoi(int n, char a, char b, char c, FILE **fp, int *count)
{
 if(n==1) move(a,c,fp,count);
 else
 {
  hanoi(n-1,a,c,b,fp,count);
  move(a,c,fp,count);
  hanoi(n-1,b,a,c,fp,count);
 }
}


main()
{
 int n,count=0;   /*count用来记录移动次数*/
 FILE *fp;
 fp=fopen("hanoi.txt","w");
 printf("Input the number of disk:");
 scanf("%d",&n);
 fprintf(fp,"%d disks hanoi tower:\n",n);
 hanoi(n,'A','B','C',&fp,&count);
 fclose(fp);
}


链表：

/*带头结点单链表逆置*/

#include "stdio.h"
#include "stdlib.h"
#define Null 0

typedef struct LNode
{
 int data;
 struct LNode *next;
}LNode,*Linklist;

void Creat(Linklist *L)
{
 int i;
 Linklist p,q;
 (*L)=(Linklist)malloc(sizeof(LNode));
 (*L)->data=-1;(*L)->next=Null;
 p=*L;
 scanf("%d",&i);
 while(i!=-1)
 {
 q=(Linklist)malloc(sizeof(LNode));
 q->data=i;q->next=Null;
 p->next=q;
 p=q;
 scanf("%d",&i);
 }
}


void Reverse(Linklist *L)
{
 Linklist p=(*L)->next,q;
 (*L)->next=Null;
 while(p)
 {
 q=p->next;
 p->next=(*L)->next;
 (*L)->next=p;
 p=q;
 }
}


void Print(Linklist L)
{
 Linklist p=L->next;
 while(p)
 {
 printf("%d ",p->data);
 p=p->next;
 }
}


main()
{
 Linklist L;
 printf("Input the data of L ending with -1:\n");
 Creat(&L);
 printf("\nThe original list is:\n");
 Print(L);
 printf("\nNow the list will be reversed:\n");
 Reverse(&L);
 Print(L);
}

有序链表的合并：
La，Lb为两个元素按递增有序排列的链表，将其合并到Lc元素仍递增有序。

#include "stdio.h"
#include "stdlib.h"
#define Null 0

typedef struct LNode
{
 int data;
 struct LNode *next;
}LNode,*Linklist;

void Creat(Linklist *L)
{
 int i;
 Linklist p,q;
 (*L)=(Linklist)malloc(sizeof(LNode));
 (*L)->data=-1;(*L)->next=Null;
 p=*L;
 scanf("%d",&i);
 while(i!=-1)
 {
 q=(Linklist)malloc(sizeof(LNode));
 q->data=i;q->next=Null;
 p->next=q;
 p=q;
 scanf("%d",&i);
 }
}


void Merge(Linklist La, Linklist Lb, Linklist *Lc)
{
 Linklist pa=La->next,pb=Lb->next,pc;
 *Lc=(Linklist)malloc(sizeof(LNode));
 (*Lc)->data=-1;(*Lc)->next=Null;
 pc=*Lc;
 while(pa&&pb)
 {
 if(pa->data<pb->data)
 {
  pc->next=pa;
  pc=pa;
  pa=pa->next;
 }
 else
 {
  pc->next=pb;
  pc=pb;
  pb=pb->next;
 }
 }
 if(pa) pc->next=pa;
 else pc->next=pb;
}


void Print(Linklist L)
{
 Linklist p=L->next;
 while(p)
 {
 printf("%d ",p->data);
 p=p->next;
 }
}


main()
{
 Linklist La,Lb,Lc;
 /*输入La，Lb的元素，注意应按递增有序*/
 printf("Input the data of La:\n");
 Creat(&La);
 printf("Input the data of Lb:\n");
 Creat(&Lb);
 printf("\nLa:");
 Print(La);
 printf("\nLb:");
 Print(Lb);
 printf("\nMerge La and Lb to Lc:\n");
 Merge(La,Lb,&Lc);
 Print(Lc);
 printf("\n");
}


La，Lb为两个元素按递增有序排列的链表，将其合并到Lc元素递减有序。

#include "stdio.h"
#include "stdlib.h"
#include "malloc.h"
#define Null 0

typedef struct LNode
{
 int data;
 struct LNode *next;
}LNode,*Linklist;

void Creat(Linklist *L)
{
 int i;
 Linklist p,q;
 (*L)=(Linklist)malloc(sizeof(LNode));
 (*L)->data=-1;(*L)->next=Null;
 p=*L;
 scanf("%d",&i);
 while(i!=-1)
 {
 q=(Linklist)malloc(sizeof(LNode));
 q->data=i;q->next=Null;
 p->next=q;
 p=q;
 scanf("%d",&i);
 }
}


void Merge(Linklist La, Linklist Lb, Linklist *Lc)
{
 Linklist pa=La->next,pb=Lb->next,p;
 *Lc=(Linklist)malloc(sizeof(LNode));
 (*Lc)->data=-1;(*Lc)->next=Null;
 while(pa&&pb)
 {
 if(pa->data<pb->data)
 {
  p=pa->next;
  pa->next=(*Lc)->next;
  (*Lc)->next=pa;
  pa=p;
 }
 else
 {
  p=pb->next;
  pb->next=(*Lc)->next;
  (*Lc)->next=pb;
  pb=p;
 }
 }
 while(pa)
 {
 p=pa->next;
 pa->next=(*Lc)->next;
 (*Lc)->next=pa;
 pa=p;
 }
 while(pb)
 {
 p=pb->next;
 pb->next=(*Lc)->next;
 (*Lc)->next=pb;
 pb=p;
 }
}


void Print(Linklist L)
{
 Linklist p=L->next;
 while(p)
 {
 printf("%d ",p->data);
 p=p->next;
 }
}


main()
{
 Linklist La,Lb,Lc;
 printf("Input the data of La:\n");
 Creat(&La);
 printf("Input the data of Lb:\n");
 Creat(&Lb);
 printf("\nLa:");
 Print(La);
 printf("\nLb:");
 Print(Lb);
 printf("\nMerge La and Lb to Lc:\n");
 Merge(La,Lb,&Lc);
 Print(Lc);
 printf("\n");
}