数据结构实验

（使用C语言）

物理与电子技术系

张   青

实验1：顺序表的基本操作

一、实验目的：

1. 会定义线性表的顺序存储类型；

2. 熟悉C程序的基本结构，掌握程序中的用户头文件、实现文件和主文件之间的相互关系及各自的作用；

3. 熟悉对线性表的一些基本操作和具体的函数定义；

4. 熟悉C操作环境的使用以及多文件程序的输入、编辑、调试和运行的全过程。

二、实验要求：

1. 理解实验内容中所给出程序的含义；

2. 用此程序上机运行、调试；

3. 屏幕显示结果，能结合程序进行分析；

4. 能按照你对顺序表操作的需要，重新改写主函数并运行。

实验内容：训练对顺序表的插入和取数据元素操作，顺序插入、取打印1-10这几个数字。

三、实验程序：

#include

#define maxsize 100

typedef int datatype;

typedef struct

{

   datatype list[maxsize];

   int size;

}seqlist;

  slinitiate(seqlist*L1);

  slinsert(seqlist*L2,int i,datatype x);

  slget(seqlist L3,int i,datatype*x);

  main(void)

{

    seqlist mylist;

    int i,x;

    slinitiate(&mylist);

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

    {

    if(slinsert(&mylist,i,i+1)==0)

    {

    printf("wrong!\\n");

    return;

    }

    }

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

    {

    if(slget(mylist,i,&x)==0)

    {

    printf("wrong!\\n");

    return;

    }

    else printf("%d",x);

    }

    }

    slinitiate(seqlist*L1)

    {

L1->size=0;

    }

    int slinsert(seqlist*L2,int i,datatype x)

    {

    int j;

if(L2->size>=maxsize)

    {

    printf("the list is full,can't be inserted!\\n");

    return 0;

    }

else if(i<0||i>L2->size)

    {

    printf("the parameter is illegal!\\n");

    return 0;

    }

    else

    {

for(j=L2->size;j>i;j--)L2->list[j]=L2->list[i];

L2->list[i]=x;

L2->size++;

    return 1;

    }

}

    int slget(seqlist L3,int i,datatype*x)

    {

if(i<0||i>L3.size-1)

    {

    printf("the parameter i is illegal!\\n");

    return 0;

    }

    else

    {

    *x=L3.list[i];

    return 1;

    }

    }

_

四、实验结果： 

1 2 3 4 5 6 7 8 9 10

五、程序各部分功能及实验结果分析：

实验2： 不带头结点单链表的基本操作

一、实验目的：

1.    会定义单链表的结点类型；

2.    熟悉对单链表的一些基本操作和具体的函数定义；

3.    了解和掌握单链表的调用格式。

二、实验要求：

1.认真阅读和掌握实验内容所给的程序，并上机运行；

2.保存程序运行结果，并结合程序 进行分析；

3. 尝试自己调试修改程序并试运行。

三、实验内容：

编写算法实现不带头结点单链表的初始化操作、插入操作和删除操作。

四、实验程序：

#include

#include

#include

typedef int datatype;

typedef struct node

{

datatype data;

struct node*next;

}nslnode;

void nsllinitiate(nslnode**head);

int nsllinsert(nslnode**head,int i,datatype x);

int nslldelete(nslnode**head,int i,datatype*x);

void main(void)

{

   datatype test[6]={,6,7,,12,24};

   nslnode*head,*p;

int n=6,i,*x;

nsllinitiate(&head);

for(i=1;i<=n;i++)

nsllinsert(&head,i,test[i-1]);

for(i=n;i>=1;i--)

{

    nslldelete(&head,i,x);

    printf(“%d”,*x);

}

}

void nsllinitiate(nslnode**head)

{

*head=NULL;

}

int nsllinsert(nslnode**head,int i,datatype x)

{

   nslnode*p,*q;

   int j;

   p=*head;j=1;

while(p!=NULL&&j{

p=p->next;j++;

}

if(j!=i-1&&i!=1)

{

printf(“插入位置参数错！”);

return 0;

}

if((q=(nslnode*)malloc(sizeof(nslnode)))==NULL)exit(1);

q->data=x;

if(I==1)

{

q->next=*head;

   *head=q;

}

else

{

q->next=p->next;

p->next=q;

}

return 1;

}

int nslldelete(nslnode**head,int i,datatype*x)

{

nslnode*p,*q;

int j;

p=*head;j=1;

while(p!=NULL&&p->next!=NULL&&j{

p=p->next;j++

}

if(j!=i-1&&i!=1)

{

   printf(“删除位置参数错！”);

   return 0;

}

if(i==1)

{

    q=p;

    head=(*head)->next;

}

else

{

q=p->next;

p->next=p->next->next;

}

*x=q->data;free(q);

return 1;

}

五、运行结果：

24 12  7 6 

六、程序各部分功能及实验结果分析：

实验3 ：带头结点单链表中数据就地逆置

一、实验目的：

1.    会定义单链表的结点类型；

2.    熟悉对单链表的一些基本操作和具体的函数定义；

3.    了解和掌握单链表的调用格式。

二、实验要求：

1.    认真阅读和掌握实验内容所给的程序，并上机运行；

2.    保存程序运行结果，并结合程序 进行分析；

3.    尝试自己调试修改程序并试运行。

三、实验内容：

编写算法实现带头结点单链表的就地逆置，即利用原带头结点单链表的结点空间把数据元素序列逆置。

四、实验程序：

#include

#include

#include

typedef int datatype;

typedef struct snode

{

   datatype data;

   struct snode*next;

}slnode;

sllinitiate(slnode**head);

int sllinsert(slnode*head,int i,datatype x);

int slldelete(slnode*head,int i,datatype x);

int sllget(slnode*head,int i,datatype*x);

int sllnotempty(slnode*head);

linlistsurt(slnode*head);

linlistinsert(slnode*head,datatype x);

converse(slnode*head);

main(void)

{

   datatype test[6]={,6,7,,12,24};

   slnode*head,*p;

   int n=6,i;

   sllinitiate(&head);

for(i=1;i<=n;i++)

     sllinsert(head,i,test[i-1]);

     linlistsort(head);

     linlistinsert(head,25);

     converse(head);

p=head->next;

     while(p!=NULL)

     {

printf("%d",p->data);

p=p->next;

     }

}

sllinitiate(slnode**head)

{

if((*head=(slnode*)malloc(sizeof(slnode)))==NULL)exit(1);

(*head)->next=NULL;

}

int sllinsert(slnode*head,int i,datatype x)

{

slnode*p,*q;

int j;

p=head;j=0;

while(p!=NULL&&j{

p=p->next;j++;

}

if(j!=i-1)

{

printf("the insert-position parameter is wrong!\\n");

return 0;

}

if((q=(slnode*)malloc(sizeof(slnode)))==NULL)exit(1);

q->data=x;

q->next=p->next;p->next=q;

return 1;

}

int slldelete(slnode*head,int i,datatype x)

{

slnode*p,*q;

int j;

p=head;j=0;

while(p->next!=NULL&&j{

p=p->next;j++;

}

if(j!=i-1)

{

printf("the delete-position parameter is wrong!\\n");

return 0;

}

q=p->next;p->next=p->next->next;

x=q->data;

free(q);

return 1;

}

int sllget(slnode*head,int i,datatype*x)

{

slnode*p;

int j;

p=head;j=0;

while(p->next!=NULL&&j{

p=p->next;j++;

}

if(j!=i)

{

printf("the get-position parameter is wrong!\\n");

return 0;

}

*x=p->data;

return 1;

}

int sllnotempty(slnode*head)

{

if(head->next==NULL)return 0;

else return 1;

}

linlistsort(slnode*head)

{

slnode*curr,*pre,*p,*q;

p=head->next;

head->next=NULL;

while(p!=NULL)

{

curr=head->next;

  pre=head;

while(curr!=NULL&&curr->data<=p->data)

  {

  pre=curr;

curr=curr->next;

  }

  q=p;

p=p->next;

q->next=pre->next;

pre->next=q;

}

}

linlistinsert(slnode*head,datatype x)

{

   slnode*curr,*pre,*q;

curr=head->next;

   pre=head;

while(curr!=NULL&&curr->data<=x)

   {

   pre=curr;

curr=curr->next;

   }

   if((q=(slnode*)malloc(sizeof(slnode)))==NULL)exit(1);

q->data=x;

q->next=pre->next;

pre->next=q;

}

converse(slnode*head)

{

slnode*p,*q;

p=head->next;

head->next=NULL;

while(p!=NULL)

{

    q=p;

p=p->next;

q->next=head->next;

head->next=q;

}

}

五、实验结果：

  25 24 12 7 6

六、程序各部分功能及实验结果分析：

实验4：顺序堆栈的基本操作

一、实验目的：

1. 会定义顺序堆栈抽象数据类型；

2. 熟悉顺序堆栈的基本结构；

3. 熟悉对顺序堆栈的一些基本操作和具体的函数定义；

二、实验要求：

1. 理解实验内容中所给出程序的含义；

2. 用此程序上机运行、调试；

3. 屏幕显示结果，能结合程序进行分析；

4. 能按照你对顺序堆栈操作的需要，重新改写主函数并运行。

三、实验内容：

打印依次出栈的数据元素序列

四、实验程序：

#include

#include

#define maxstacksize 100

typedef int datatype;

typedef struct

{

datatype stack[maxstacksize];

int top;

}seqstack;

void stackinitiate(seqstack*s);

int stacknotempty(seqstack s);

int stackpush(seqstack*s,datatype x);

int stackpop(seqstack*s,datatype*d);

int stacktop(seqstack s,datatype*d);

void main(void)

{

   seqstack mystack;

   int i,x;

   stackinitiate(&mystack);

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

   {

      if(stackpush(&mystack,i+1)==0)

      {

      printf("wrong!\\n");

      return;

      }

   }

   if(stacktop(mystack,&x)==0)

   {

       printf("wrong!\\n");

       return;

   }

   else

       printf("today the data of the stacktop is:%d\\n",x);

       printf("the pop data one by one is:\\n");

   while(stacknotempty(mystack))

   {

    stackpop(&mystack,&x);

    printf("%d  ",x);

   }

}

void stackinitiate(seqstack*s)

{

s->top=0;

}

int stacknotempty(seqstack s)

{

if(s.top<=0) return 0;

    else return 1;

}

int stackpush(seqstack*s,datatype x)

{

if(s->top>=maxstacksize)

    {

    printf("stack is full,can't insert!\\n");

    return 0;

    }

    else

    {

s->stack[s->top]=x;

s->top++;

    return 1;

    }

}

int stackpop(seqstack*s,datatype*d)

{

if(s->top<=0)

    {

    printf("stack is empty!\\n");

    return 0;

    }

    else

    {

s->top--;

*d=s->stack[s->top];

     return 1;

    }

}

int stacktop(seqstack s,datatype*d)

{

if(s.top<=0)

    {

       printf("stack is empty!\\n");

       return 0;

    }

    else

    {

    *d=s.stack[s.top-1];

    return 1;

    }

}

五、程序运行结果：

10 9 8 7 6 5 4 3 2 1

六、程序各部分功能及实验结果分析：

实验5：判断一个字符序列是否是回文

一、实验目的：

1. 会定义顺序堆栈和顺序循环队列的抽象数据类型；

2. 熟悉顺序堆栈和顺序循环队列的基本结构，掌握程序中的用户头文件、实现文件和主文件之间的相互关系及各自的作用；

3. 熟悉对顺序堆栈和顺序循环队列的一些基本操作和具体的函数定义；

二、实验要求：

1. 理解实验内容中所给出程序的含义；

2. 用此程序上机运行、调试；

3. 屏幕显示结果，能结合程序进行分析；

4. 能按照你对顺序堆栈和顺序循环队列操作的需要，重新改写主函数并运行。

实验内容：编程序判断一个字符序列是否是回文。要求程序从键盘输入一个字符串，字符串长度小于等于80，用于判断回文的字符串中不包括字符串的结束标记符。

三、实验内容：

     利用顺序堆栈和顺序循环队列，判断一个输入的字符序列是否是回文

四、实验程序：

#include

#include

#define maxsize 80

typedef char datatype;

typedef struct

{

   datatype list[maxsize];

   int top;

}seqstack;

typedef struct

{

   datatype list[maxsize];

   int front;

   int count;

}seqcqueue;

void scqinitiate(seqcqueue*q);

int scqappend(seqcqueue*q,datatype x);

int scqdelete(seqcqueue*q,datatype*d);

int scqgettop(seqcqueue q,datatype*d);

int scqnotempty(seqcqueue q);

void ssinitiate(seqstack*s);

int sspush(seqstack*s,datatype x);

int sspop(seqstack*s,datatype*d);

int ssgettop(seqstack s,datatype*d);

int ssnotempty(seqstack s);

void palindrome(char str[],int n)

{

   seqstack mystack;

   seqcqueue myqueue;

   char x,y;

   int i;

   ssinitiate(&mystack);

   scqinitiate(&myqueue);

for(i=0;i   {

    scqappend(&myqueue,str[i]);

    sspush(&mystack,str[i]);

   }

   while(scqnotempty(myqueue)==1&&ssnotempty(mystack)==1)

   {

    scqdelete(&myqueue,&x);

    sspop(&mystack,&y);

    if(x!=y)

    {

        printf("bu shi hui wen!");

        return;

    }

   }

   printf("shi hui wen!");

}

void enterstr(char str[],int*n)

{

    printf("qing cha ru zi fu chuan(bu chao guo 80 zi fu):");

    scanf("%s",str);

    *n=strlen(str);

}

void main(void)

{

    char ch,str[80];

    int n;

    while(1)

    {

    enterstr(str,&n);

    palindrome(str,n);

    printf("\\n go on?(y/n):");

    scanf("%s",&ch);

    if(ch=='Y'||ch=='y')continue;

    else return;

    }

}

void scqinitiate(seqcqueue*q)

{

q->front=0;

q->count=0;

}

int scqappend(seqcqueue*q,datatype x)

{

    int rear;

if(q->count==maxsize)

    {

       printf("队列已满无?!\\n");

       return 0;

    }

    else

    {

rear=q->front+q->count;

q->list[rear]=x;

q->count++;

    return 1;

    }

}

int scqdelete(seqcqueue*q,datatype *d)

{

if(q->count==0)

    {

       printf("循环队列已空!\\n");

       return 0;

    }

    else

    {

*d=q->list[q->front];

q->front=(q->front+1)%maxsize;

q->count--;

     return 1;

    }

}

int scqgettop(seqcqueue q,datatype*d)

{

    if(q.count==0)

    {

    printf("循环队列已空!\\n");

    return 0;

    }

    else

    {

       *d=q.list[q.front];

       return 1;

    }

}

int scqnotempty(seqcqueue q)

{

   if(q.count==0)return 0;

   else return 1;

}

void ssinitiate(seqstack *s)

{

s->top=0;

}

int sspush(seqstack*s,datatype x)

{

if(s->top>=maxsize)

    {

    printf("堆栈已满无法插入!\\n");

    return 0;

    }

    else

    {

s->list[s->top]=x;

s->top++;

    return 1;

    }

}

int sspop(seqstack*s,datatype*d)

{

if(s->top<=0)

   {

       printf("堆栈已空!\\n");

       return 0;

   }

   else

   {

s->top--;

*d=s->list[s->top];

       return 1;

   }

}

int ssgettop(seqstack s,datatype*d)

{

if(s.top<=0)

    {

       printf("堆栈已空!\\n");

       return 0;

    }

    else

    {

       *d=s.list[s.top-1];

       return 1;

    }

}

int ssnotempty(seqstack s)

{

if(s.top<=0)return 0;

    else return 1;

}

五、程序测试情况：

输入字符串（不能超过80个字符）：abcdcba

是回文！

要继续吗？(y/n):y

输入字符串（不能超过80个字符）：abcdefghi

不是回文！

要继续吗？(y/n):y

输入字符串（不能超过80个字符）：1234321

是回文！

要继续吗？(y/n):n

六、程序功能分析、运行结果分析：

实验6：农夫、狼、羊和菜问题

一、实验目的：

1. 会定义图的抽象数据类型；

2. 熟悉图的基本结构，掌握程序中的用户头文件、实现文件和主文件之间的相互关系及各自的作用；

3. 熟悉对图的一些基本操作和具体的函数定义；

4.掌握在实际问题中运用所学知识解决实际问题的方法和步骤。                      

二、实验内容描述：

有一农夫带着一条狼、一只羊和一筐菜，想从河的左岸乘船到右岸。但由于船太小，农夫每次只能带一样东西过河，而且，如果没有农夫看管，则狼会吃羊，羊会吃菜。问农夫怎样过河才能把每样东西安全地送过河。

三、实验要求：

1. 将上述问题用图表示出来；

2. 选择图的一种存储结构，编写一个自动生成该图的算法；

3.在上述基础上编写求解该问题的算法程序，并用此程序上机运行、调试，

4.屏幕显示结果，能结合程序进行分析。

四、问题分析：

    该问题从表面上看，并不是一个图的问题，但可以把它用图表示出来，从而转换为一个图的问题。在这个问题的解决过程中，农夫需要多次架船往返于两岸之间，每次可以带一样东西或者自己单独过河，每一次过河都会使农夫、狼、羊和菜所处的位置发生变化。如果用一个四元组（Farmer,Wolf,Sheep,Veget）表示当前农夫、狼、羊和菜所处的位置，其中每个元素可以是0或1，0表示在左岸，1表示在右岸。这样，对这四个元素的不同取值可以构成16种不同的状态，初始时的状态则为（0，0，0，0），最终要达到的目标为（1，1，1，1）。状态之间的转换可以有下面四种情况：

（1）农夫不带任何东西过河，可表示为：

(Farmer,Wolf,Sheep,Veget)  (!Farmer,Wolf,Sheep,Veget)

（2）当农夫和狼在相同位置时，表示农夫带狼过河，即当Farmer=Wolf时：

(Farmer,Wolf,Sheep,Veget)  (!Farmer,!Wolf,Sheep,Veget)

（3）当农夫和羊在相同位置时，表示农夫带羊过河，即当Farmer=Sheep时：

(Farmer,Wolf,Sheep,Veget)  (!Farmer,Wolf,!Sheep,Veget)

（4）当农夫和菜在相同位置时，表示农夫带菜过河，即当Farmer=Veget时：

(Farmer,Wolf,Sheep,Veget)  (!Farmer,Wolf,Sheep,!Veget)

在这16种状态中，有些状态是不安全的，是不允许出现的，如（1，1，0，0）表示农夫和狼在右岸，而羊和菜在左岸，这样羊会吃掉菜。如果从16种状态中删去这些不安全状态，将剩余的安全状态之间根据上面的转换关系连接起来，就得到如下图所示的图。

图1 农夫、狼、羊和菜问题的状态图

这样，原始问题就转换为在这个图中寻找一条从顶点（0，0，0，0）到顶点（1，1，1，1）的路径的问题。

五、存储结构：

采用邻接矩阵和邻接表都可以完成求图中两顶点间的路径问题，这里，我们不妨采用邻接矩阵存储结构。其中图的每个顶点结点包括四个域，类型定义为：

typedef struct                                   /*定义图的顶点类型*/

{

     int Farmer,Wolf,Sheep,Veget;

}VexType;

图的邻接矩阵存储结构定义为：

#define VEX-NUM 10                                   /*最大顶点个数*/

typedef struct

{

    int vexnum,e;                            /*图的当前顶点数和边数*/

    VexType vex[VEX-NUM];                          /*顶点向量*/

    int adj[VEX-NUM][VEX-NUM];                      /*邻接矩阵*/

}AdjGraph;

六、算法思想：

在这个问题中，首先需要自动生成图的邻接矩阵存储，具体方法是先生成各种安全状态结点，存放在顶点向量中；再根据状态之间的转换关系形成顶点之间的所有边，保存在邻接矩阵中。在建立了图的邻接矩阵存储结构后，利用深度优先搜索思想求出从顶点（0，0，0，0）到顶点（1，1，1，1）的一条简单路径。

七、实验程序：

 #include

#define VEX_NUM 10

typedef enum{FALSE,TRUE}Boolean;

typedef struct

{

int Farmer,Wolf,Sheep,Veget;

}VexType;

typedef struct

{

int vexnum,e;

VexType vexs[VEX_NUM];

int adj[VEX_NUM][VEX_NUM];

}AdjGraph;

Boolean visited[VEX_NUM];

int path[VEX_NUM];

int locate(AdjGraph*G,int F,int W,int S,int V)

{

int i;

for(i=0;ivexnum;i++)

if(G->vexs[i].Farmer==F&&G->vexs[i].Wolf==W&&G->vexs[i].Sheep==S&&G->vexs[i].Veget==V)

return(i);

return(-1);

}

int is_safe(int F,int W,int S,int V)

{

if(F!=S&&(W==S||S==V))

return(0);

else

return(1);

}

int is_connected(AdjGraph*G,int i,int j)

{

int k;

k=0;

if(G->vexs[i].Wolf!=G->vexs[j].Wolf)

   k++;

if(G->vexs[i].Sheep!=G->vexs[j].Sheep)

   k++;

if(G->vexs[i].Veget!=G->vexs[j].Veget)

   k++;

if(G->vexs[i].Farmer!=G->vexs[j].Farmer&&k<=1)

   return(1);

else

   return(0);

}

void CreateG(AdjGraph*G)

{

int i,j,F,W,S,V;

i=0;

for(F=0;F<=1;F++)

for(W=0;W<=1;W++)

for(S=0;S<=1;S++)

for(V=0;V<=1;V++)

if(is_safe(F,W,S,V))

{

G->vexs[i].Farmer=F;

G->vexs[i].Wolf=W;

G->vexs[i].Sheep=S;

G->vexs[i].Veget=V;

i++;

}

G->vexnum=i;

for(i=0;ivexnum;j++)

for(j=0;jvexnum;j++)

  if(is_connected(G,i,j))

G->adj[i][j]=G->adj[i][j]=1;

  else

G->adj[i][j]=G->adj[j][i]=0;

  return;

}

void print_path(AdjGraph*G,int u,int v)

{

int k;

k=u;

while(k!=v){

printf("(%d,%d,%d,%d)\\n",G->vexs[k].Farmer,G->vexs[k].Wolf,G->vexs[k].Sheep,G->vexs[k].Veget);

k=path[k];

}

printf("(%d,%d,%d,%d）\\n",G->vexs[k].Farmer,G->vexs[k].Wolf,G->vexs[k].Sheep,G->vexs[k].Veget);

}

void DFS_path(AdjGraph*G,int u,int v)

{

int j;

visited[u]=TRUE;

for(j=0;jvexnum;j++)

if(G->adj[u][j]&&!visited[j]&&!visited[v]){

   path[u]=j;

   DFS_path(G,j,v);

   }

}

void main()

{

int i,j;

AdjGraph graph;

CreateG(&graph);

for(i=0;ivisited[i]=FALSE;

i=locate(&graph,0,0,0,0);

j=locate(&graph,1,1,1,1);

DFS_path(&graph,i,j);

if(visited[j]

print_path(&graph,i,j);

if(visited[j])

print_path(&graph,i,j);

return;

}

八、实验测试结果：

（0，0，0，0）

（1，0，1，0）

（0，0，1，0）

（1，0，1，1）

（0，0，0，1）

（1，1，0，1）

（0，1，0，1）

（1，1，1，1）

九、程序功能分析、运行结果分析：