实验二  栈和队列及应用

一、实验目的

1.掌握用c语言实现队列和栈的方法

2.了解栈和队列的使用

二、实验内容

实验题目一

在许多语言现象中，常见到一种形如abcba的文字，这种文字从左到右读和从右到左读结果是一样的，这种文字就是常说的回文。设计一个程序可以判断给定的一个文字是否是回文。

注意：在本实验中，要求在实现上面的题目时，必须使用如下算法：

考虑到栈的先进后出以及队列的后进先出，可以结合这两种结构来实现需要的功能，即将文字分别入队和入栈，然后依次通过出队和出栈输出判断是否有不相同的字符，一旦发现就证明文字不是一个回文。

实验步骤：

第一步：编写程序，实现栈，该栈可以用数组实现，也可以用链表实现

第二步：编写程序，实现队列，该队列可以为循环队列，也可以用链表实现

第三步：编写主算法，使用自己编写的栈和队列实现回文判断问题（通过键盘输入一个以＃结束的字符串，进行判断）

#include <stdio.h>

#include <malloc.h>

struct Node;

typedef struct Node * PNode;

struct Node

{

       char info;

       PNode link;

};

struct LinkStack                          //定义栈

{

       PNode top;

};

typedef struct LinkStack * PLinkStack;

struct LinkQuene                         //定义队列

{

       PNode f;

       PNode r;

};

typedef struct LinkQuene *PLink;

PLinkStack CreateStackLink ()     //创建空栈

{

       PLinkStack ptop;

       ptop=(PLinkStack)malloc(sizeof(struct LinkStack));

       if (ptop==NULL)

       {

              printf ("申请空间失败！\n");

              exit(-1);

       }

       ptop->top=NULL;

       return ptop;

}

PLink CreateLink ()                            //创建空队列

{

       PLink pl;

       pl=(PLink)malloc(sizeof(struct LinkQuene));

       if (pl==NULL)

       {

              printf ("申请空间失败！\n");

              exit (-1);

       }

       pl->f=NULL;

       pl->r=NULL;

       return pl;

}

void PushLink (PLinkStack pl,char c)//进栈

{

       PNode p;

       p=(PNode)malloc(sizeof(struct Node));

       if (p==NULL)

       {

              printf ("申请空间失败！\n");

              exit(-1);

       }

       p->info=c;

       p->link=pl->top;

       pl->top=p;

}

void PushQuene (PLink pl,char c) //进队列

{

       PNode p;

       p=(PNode)malloc(sizeof(struct Node));

       if (p==NULL)

       {

              printf ("申请空间失败！\n");

              exit (-1);

       }

       p->info=c;

       p->link=NULL;

       if (pl->f==NULL)

              pl->f=p;

       else

              pl->r->link=p;

       pl->r=p;

}

void GetLink (PLinkStack pl)              //出栈

{

       PNode p;

       p=(PNode)malloc(sizeof(struct Node));

       if (pl->top==NULL)

       {

              printf ("空栈！\n");

              exit(-1);

       }

       if (p==NULL)

       {

              printf ("申请空间失败！\n");

              exit(-1);

       }

       p=pl->top;

       pl->top=pl->top->link;

       free (p);

}

void GetQuene (PLink pl)                   //出队列

{

       PNode p;

       p=(PNode)malloc(sizeof(struct Node));

       if (pl->f==NULL)

       {

              printf ("空队列！\n");

              exit(-1);

       }

       if (p==NULL)

       {

              printf ("申请空间失败！\n");

              exit(-1);

       }

       p=pl->f;

       pl->f=p->link;

       free (p);

}

char GetLinkData (PLinkStack pl) //获得栈顶数值

{

       if (pl->top==NULL)

       {

              printf ("空栈！\n");

              exit(-1);

       }

       return pl->top->info;

}

char GetQueneData (PLink pl)             //获得队列头部数值

{

       if (pl->f==NULL)

       {

              printf ("空队列！\n");

              exit(-1);

       }

       return pl->f->info;

}

void PrintLink (PLinkStack pl)            //打印栈

{

       PNode p;

       p=(PNode)malloc(sizeof(struct Node));

       if (p==NULL)

       {

              printf ("申请空间失败！\n");

              exit(-1);

       }

       p=pl->top;

       while (p->link!=NULL)

       {

              printf ("%c=>",p->info);

              p=p->link;

       }

       printf ("%c\n",p->info);

}

void PrintQuene (PLink pl)                 //打印队列

{

       PNode p;

       p=(PNode)malloc(sizeof(struct Node));

       if (p==NULL)

       {

              printf ("申请空间失败！\n");

              exit (-1);

       }

       p=pl->f;

       while (p->link!=pl->r->link)

       {

              printf ("%c=>",p->info);

              p=p->link;

       }

       printf ("%c\n",p->info);

}

int main ()

{

       //char ch[]="abcdcba";

       int i;

       char s1,s2,x;

       PLinkStack pl1;

       PLink pl2;

       pl1=CreateStackLink ();

       pl2=CreateLink ();

       printf ("请输入（以#结束）：\n");

       for (i=0;i<50;i++)

       {

              scanf ("%c",&x);

              if (x=='#')

                     break;

              PushLink (pl1,x);

              PushQuene (pl2,x);

       }

       printf ("栈输出为：");

       PrintLink (pl1);

       //s=GetLinkData (pl1);

       //printf ("%c\n",s);

       printf ("队列输出为：");

       PrintQuene (pl2);

       //s=GetQueneData (pl2);

       //printf ("%c\n",s);

       while (pl1->top!=NULL && pl2->f!=NULL)

       {

              s1=GetLinkData (pl1);

              s2=GetQueneData (pl2);

              if (s1==s2)

              {

                     GetLink (pl1);

                     GetQuene (pl2);

              }

              else

              {

                     printf ("不是回文数！\n");

                     break;

              }

       }

       if (pl2->f==NULL)

       {

              printf ("这是回文数！\n");

       }

       return 0;

}

实验三   树及应用

一、实验目的

1、掌握简单的二叉树编程，掌握二叉树构造的一些方法

2、掌握二叉树的中序，前序，后序遍历方法

二、实验内容

实验题目一：

（1）从键盘输入任意二叉树的前根排序序列，用＃结束，当某节点的左子树或右子树为空时，用“@”代替，

例如对于如下图的二叉树，输入内容为：abd@@eh@@@cf@i@@g@@#

（2）分别用三种遍历方法输出遍历结果。

（3）键盘输入一个值x，要求在生成好的二叉排序树中查找这个值x，如果找到，则输出“找到了”，没有找到，则输出“没有找到”

#include<stdio.h>

#include<malloc.h>

#include<stdlib.h>

#include<iostream.h>

typedef char DataType;

struct BinNode

{

       DataType info;

       BinNode* lchild;

       BinNode* rchild;

};

typedef BinNode* BinTree;

void InitBinTree(BinTree &T);

void CreateBinTree(BinTree &T);

void DisplayBinTree_DLR(BinTree &T);

void DisplayBinTree_LRD(BinTree &T);

void DisplayBinTree_LDR(BinTree &T);

int ServechBinTree(DataType x,BinTree &T);

int main()

{

       BinTree T;

       printf("1 :初始化树\n2 :先根序列创建树\n3 :后根序列输出\n4 :中根序列输出\n5 :先根序列输出\n6: 查找\n");

       for(;;)

       {

             //printf("1 :初始化树\n2 :先根序列创建树\n3 :后根序列输出\n4 :中根序列输出\n5 :先根序列输出\n6: 查找\n");

              int i;

              printf("请输入你的选择：\n");

              cin>>i;

              if(i==1)

                     InitBinTree(T);

              else if(i==2)

                     CreateBinTree(T);

              else if(i==3)

              {

                     printf("后根序列输出:");

                     DisplayBinTree_LRD(T);

                     printf("\n");

              }

              else if(i==4)

              {

                     printf("中根序列输出:");

                     DisplayBinTree_LDR(T);

                     printf("\n");

              }

              else if(i==5)

              {

                     printf("先根序列输出:");

                     DisplayBinTree_DLR(T);

                     printf("\n");

              }

              else if(i==6)

              {

                     DataType x;

                     printf("请输入要查找的元素： \n");

                     cin>>x;

                     if(ServechBinTree(x,T)==1)

                            printf("%c have find!!!\n",x);

                     else

                            printf("no find!!!\n");

              }

       }

       return 0;

}

void InitBinTree(BinTree &T)

{

       T=(BinTree)malloc(sizeof(struct BinNode));

       if(T!=NULL)

              printf("Init a tree successful!!\n");

       else

              printf("Init a tree failt!!!\n");

}

void CreateBinTree(BinTree &T)

{

    DataType ch;

       scanf("%c",&ch);

       if(ch=='@')

              T=NULL;

       else

       {

              T=(BinTree)malloc(sizeof(struct BinNode));

              if(T==NULL)

                     exit(0);

              T->info=ch;

              CreateBinTree(T->lchild);

              CreateBinTree(T->rchild);

       }

}

void DisplayBinTree_DLR(BinTree &T)//先根

{

       if(T!=NULL)

       {

              printf("%c",T->info);

              DisplayBinTree_DLR(T->lchild);

              DisplayBinTree_DLR(T->rchild);

       }

}

void DisplayBinTree_LRD(BinTree &T)//后根

{

       if(T!=NULL)

       {

             

              DisplayBinTree_LRD(T->lchild);

              DisplayBinTree_LRD(T->rchild);

              printf("%c",T->info);

       }

}

void DisplayBinTree_LDR(BinTree &T)//中根

{

       if(T!=NULL)

       {

      

              DisplayBinTree_LDR(T->lchild);

              printf("%c",T->info);

              DisplayBinTree_LDR(T->rchild);

       }

}

int ServechBinTree(DataType x,BinTree &T)

{

       if(T!=NULL)

       {

              if(T->info==x)

                     return 1;

              else

              {

                     if(ServechBinTree(x,T->lchild)==1)

                            return 1;

                     else

                            return ServechBinTree(x,T->rchild);

              }

       }

}

实验四 查找

一、实验目的

掌握折半查找法

二、实验内容

设一数组，存放有10个排好顺序的整数，要求键盘输入一个值，然后使用折半查找的方法在此排好顺序的数组中查找出该值，并输入该值的所在的数组下标。

要求：

（1）自己编写函数实现折半查找算法

（2）要实现完整的程序，包括输入输出

输入要查找的值，假如该值在数组中不存在，输出“没有找到”，否则输出该值在数组中的位置

#include <stdio.h>

int HalfSearch (int s,int *sum,int first,int last)

{

       int mid;

       mid=(first+last)/2;

       if (first>last)

              return -1;

       else

       {

              if (sum[mid]==s)

                     return mid;

              else if (s<sum[mid])

                     return HalfSearch (s,sum,first,mid-1);

              else if (s>sum[mid])

                     return HalfSearch (s,sum,mid+1,last);

       }

}

int main()

{

       int sum[]={1,2,3,4,5,6,7,8,9,10,11,12};

       int s,r;

       printf ("请输入一个数字进行查询：");

       scanf ("%d",&s);

       r=HalfSearch (s,sum,0,11);

       if (r==-1)

              printf ("没有查找到%d！",s);

       else

              printf ("%d在第%d个位置！",s,r);

       return 0;

}

实验五 排序

一、实验目的

掌握快速排序

二、实验要求

复习排序方法，掌握快速排序算法，并自己编写代码实现

三、实验内容

编写程序，实现快速排序。从键盘上输入10个整数，存放在数组中，然后用快速排序法对其从小到大进行排序，并输出排序结果。

思考：书上已经有的部分快速排序程序，实际上对数据进行的是从小到大的排序，假如，需要将数据从大到小进行排序，该如何做？

#include<stdlib.h>

#include<stdio.h>

#include<malloc.h>

typedef int KeyType;

typedef int DataType;

typedef struct {

       KeyType key;

//     DataType info;

}RecordNode;

typedef struct {

       int n;

       RecordNode *record;

}SortObject;

void Inser(SortObject *sj);

void QuickSort(SortObject *pvector,int l,int r);

SortObject* Init(int n);

void display(SortObject* pvector);

int main()

{

       //int k;

       //int i;

       SortObject *sj=Init(10);

       Inser(sj);

       printf("befor sort :\n");

       display(sj);

       QuickSort(sj,0,9);

       printf("\nafter sort :\n");

       display(sj);

       return 0;

      

}

void display(SortObject* pvector)

{

       for(int i=0;i<10;i++)

       {

              printf("%d ",pvector->record[i].key);

       }

}

SortObject* Init(int n)

{

       SortObject* sj=(SortObject*)malloc(sizeof(SortObject));

       sj->record=(RecordNode*)malloc(sizeof(RecordNode)*n);

       sj->n=n;

       return sj;

}

void Inser(SortObject *sj)

{

       int i;

       KeyType k;

       //sj->record=(RecordNode*)malloc(sizeof(int)*sj->n);

       //fflush(stdin);

       for(i=0;i<sj->n;i++)

       {

              scanf("%d",&k);

              sj->record[i].key=k;

       }

}

void QuickSort(SortObject *pvector,int l,int r)

{

       int i,j;

       RecordNode temp;

       if(l>=r)

              return ;

       i=l;

       j=r;

       temp=pvector->record[i];

       while(i!=j)

       {

              while((i<j)&&pvector->record[j].key>temp.key)

                     j--;

              if(i<j)

                     pvector->record[i++]=pvector->record[j];

      

              while((i<j)&&pvector->record[i].key<temp.key)

                     i++;

              if(i<j)

                     pvector->record[j--]=pvector->record[i];

             

       }

       pvector->record[i]=temp;

       QuickSort(pvector,l,i-1);

       QuickSort(pvector,i+1,r);

}

实验六   图

一、实验目的

熟悉图的遍历操作

二、实验内容

采用邻接矩阵作为存储结构，完成无向图的深度优先遍历和广度优先遍历

具体的实验代码包括

1)   读入图，保存为邻接矩阵的形式，为了方便，可以直接读入一个矩阵，也可以让用户输入两条相连的边，或者读入相邻的两个结点

2)   实现深度优先遍历的算法

3)   输出深度优先遍历的结果

4)        实现广度优先遍历的算法

5)        输出广度优先遍历的结果

如上图：

从点1开始的深度遍历输出为：

1→2→ 4 →8 →5 →3→ 6 →7

从点1开始的广度遍历输出为：1→2→ 3 →4 →5 →6→ 7→8

//图的遍历算法程序

//图的遍历是指按某条搜索路径访问图中每个结点，使得每个结点均被访问一次，而且仅被访问一次。图的遍历有深度遍历算法和广度遍历算法，程序如下： 

#include <iostream>

//#include <malloc.h>

#define INFINITY 32767

#define MAX_VEX 20 //最大顶点个数

#define QUEUE_SIZE (MAX_VEX+1) //队列长度

using namespace std;

bool *visited;  //访问标志数组

//图的邻接矩阵存储结构

typedef struct{

  char *vexs; //顶点向量

  int arcs[MAX_VEX][MAX_VEX]; //邻接矩阵

  int vexnum,arcnum; //图的当前顶点数和弧数

}Graph;

//队列类

class Queue{

  public:

  void InitQueue(){

    base=(int *)malloc(QUEUE_SIZE*sizeof(int));

    front=rear=0;

  }

  void EnQueue(int e){

    base[rear]=e;

    rear=(rear+1)%QUEUE_SIZE;

  }

  void DeQueue(int &e){

    e=base[front];

    front=(front+1)%QUEUE_SIZE;

  }

  public:

  int *base;

  int front;

  int rear;

};

//图G中查找元素c的位置

int Locate(Graph G,char c){

  for(int i=0;i<G.vexnum;i++)

  if(G.vexs[i]==c) return i;

  return -1;

}

//创建无向网

void CreateUDN(Graph &G){

  int i,j,w,s1,s2;

  char a,b,temp;

  printf("输入顶点数和弧数:");

  scanf("%d%d",&G.vexnum,&G.arcnum);

  temp=getchar(); //接收回车

  G.vexs=(char *)malloc(G.vexnum*sizeof(char)); //分配顶点数目

  printf("输入%d个顶点.\n",G.vexnum);

  for(i=0;i<G.vexnum;i++){ //初始化顶点

    printf("输入顶点%d:",i);

    scanf("%c",&G.vexs[i]);

    temp=getchar(); //接收回车

  }

  for(i=0;i<G.vexnum;i++) //初始化邻接矩阵

    for(j=0;j<G.vexnum;j++)

      G.arcs[i][j]=INFINITY;

  printf("输入%d条弧.\n",G.arcnum);

  for(i=0;i<G.arcnum;i++){ //初始化弧

    printf("输入弧%d:",i);

    scanf("%c %c %d",&a,&b,&w); //输入一条边依附的顶点和权值

    temp=getchar(); //接收回车

    s1=Locate(G,a);

    s2=Locate(G,b);

    G.arcs[s1][s2]=G.arcs[s2][s1]=w;

  }

}

//图G中顶点k的第一个邻接顶点

int FirstVex(Graph G,int k){

  if(k>=0 && k<G.vexnum){ //k合理

    for(int i=0;i<G.vexnum;i++)

      if(G.arcs[k][i]!=INFINITY) return i;

  }

  return -1;

}

//图G中顶点i的第j个邻接顶点的下一个邻接顶点

int NextVex(Graph G,int i,int j){

  if(i>=0 && i<G.vexnum && j>=0 && j<G.vexnum){ //i,j合理

    for(int k=j+1;k<G.vexnum;k++)

      if(G.arcs[i][k]!=INFINITY) return k;

  }

  return -1;

}

//深度优先遍历

void DFS(Graph G,int k){

  int i;

  if(k==-1){ //第一次执行DFS时,k为-1

    for(i=0;i<G.vexnum;i++)

      if(!visited[i]) DFS(G,i); //对尚未访问的顶点调用DFS

  }

  else{

    visited[k]=true;

    printf("%c ",G.vexs[k]); //访问第k个顶点

    for(i=FirstVex(G,k);i>=0;i=NextVex(G,k,i))

      if(!visited[i]) DFS(G,i); //对k的尚未访问的邻接顶点i递归调用DFS

  }

}

//广度优先遍历

void BFS(Graph G){

  int k;

  Queue Q; //辅助队列Q

  Q.InitQueue();

  for(int i=0;i<G.vexnum;i++)

    if(!visited[i]){ //i尚未访问

      visited[i]=true;

      printf("%c ",G.vexs[i]);

      Q.EnQueue(i); //i入列

      while(Q.front!=Q.rear){

        Q.DeQueue(k); //队头元素出列并置为k

        for(int w=FirstVex(G,k);w>=0;w=NextVex(G,k,w))

          if(!visited[w]){ //w为k的尚未访问的邻接顶点

            visited[w]=true;

            printf("%c ",G.vexs[w]);

            Q.EnQueue(w);

          }

      }

    }

}

//主函数

void main(){

  int i;

  Graph G;

  CreateUDN(G);

  visited=(bool *)malloc(G.vexnum*sizeof(bool));

  printf("\n广度优先遍历: ");

  for(i=0;i<G.vexnum;i++)

  visited[i]=false;

  DFS(G,-1);

  printf("\n深度优先遍历: ");

  for(i=0;i<G.vexnum;i++)

  visited[i]=false;

  BFS(G);

  printf("\n程序结束.\n");

}

输出结果为（红色为键盘输入的数据，权值都置为1）：

输入顶点数和弧数:8 9

输入8个顶点.

输入顶点0:a

输入顶点1:b

输入顶点2:c

输入顶点3:d

输入顶点4:e

输入顶点5:f

输入顶点6:g

输入顶点7:h

输入9条弧.

输入弧0:a b 1

输入弧1:b d 1

输入弧2:b e 1

输入弧3:d h 1

输入弧4:e h 1

输入弧5:a c 1

输入弧6:c f 1

输入弧7:c g 1

输入弧8:f g 1

广度优先遍历: a b d h e c f g

深度优先遍历: a b c d e f g h

程序结束.