（使用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;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;i for(j=0;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;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;i 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） 九、程序功能分析、运行结果分析：下载本文
