数据结构实验前要.doc

《数据结构》实验（一）
实验目的：复习C语言知识，为后续课程编程环节打下基础。
实验课时：4课时
实验内容：
头文件：

#define DATATYPE1 int
#define DATATYPE2 char
#define KEYTYPE int
#define MAXSIZE 100
#define MAXLEN 40
#define VEXTYPE int
#define ADJTYPE int

typedef struct
{ DATATYPE1 datas[MAXSIZE];
int last;
}SEQUENLIST;

typedef struct node
{
DATATYPE2 data;
struct node *next;
}LINKLIST;

typedef struct dnode
{DATATYPE2 data;
struct dnode *prior, *next;
} DLINKLIST;

typedef struct
{ DATATYPE1 data[MAXSIZE];
int top;
}SEQSTACK;

typedef struct snode
{ DATATYPE2 data;
struct snode *next;
}LINKSTACK;

typedef struct
{ DATATYPE1 data[MAXSIZE];
int front, rear;
}SEQQUEUE;

typedef struct qnode
{ DATATYPE1 data;
struct qnode *next;
}LINKQLIST;

typedef struct
{ LINKQLIST *front, *rear;
}LINKQUEUE;

typedef struct
{ char ch[MAXSIZE];
int len;
}SEQSTRING;

typedef struct
{ char *ch;
int len;
} HSTRING;

typedef struct
{ int i, j;
DATATYPE1 v;
}NODE;

typedef struct
{ int m, n, t;
NODE data[MAXLEN];
}SPMATRIX;

typedef struct
{ DATATYPE2 bt[MAXSIZE];
int btnum;
}BTSEQ;

typedef struct node1
{ DATATYPE2 data;
struct node1 *lchild, *rchild;
}BTCHINALR;

typedef struct node2
{ DATATYPE2 data;
struct node2 *lchild, *rchild, *parent;
}BTCHINALRP;

typedef struct
{ DATATYPE2 data;
int parent;
}PTNODE;

typedef struct
{ PTNODE nodes[MAXSIZE];
int nodenum;
}PTTREE;

typedef struct cnode
{ int child;
struct cnode *next;
}CHILDLINK;

typedef struct
{ DATATYPE2 data;
CHILDLINK *headptr;
}CTNODE;

typedef struct
{CTNODE nodes[MAXSIZE];
int nodenum, rootset;
}CTTREE;

typedef struct csnode
{ DATATYPE2 data;
struct csnode *firstchild, *nextsibling;
}CSNODE;

typedef struct
{ VEXTYPE vexs[MAXLEN];
ADJTYPE arcs[MAXLEN][MAXLEN];
int vexnum, arcnum;
int kind;
}MGRAPH;

typedef struct node3
{ int adjvex;
struct node3 *next;
}EDGENODE;

typedef struct
{ VEXTYPE vertex;
EDGENODE *link;
int id;
} VEXNODE;

typedef struct
{ VEXNODE adjlist[MAXLEN];
int vexnum, arcnum;
int kind;
}ADJGRAPH;

typedef struct
{ KEYTYPE key;
}SSELEMENT;

typedef struct
{ SSELEMENT r[MAXSIZE];
int len;
}SSTABLE;

typedef struct node4
{KEYTYPE key;
struct node4 *lchild, *rchild;
} BSTNODE;

typedef struct node5
{
KEYTYPE key;
struct node5 *next;
}CHAINHASH;

typedef struct
{
KEYTYPE key;
}HASHTABLE;

typedef struct
{ KEYTYPE key;
}RECNODE;

1、编制程序并上机调试：从键盘接收10个整型数据后，找出其中的最大值并输出。
要求：使用函数完成“寻找最大值的功能”。
答： #include "stdio.h"
int max(int a[])
{
int max1=a[0];
int i;
for (i=1;i<10;i++)
{
if (max1<a[i])
max1=a[i];
}
return (max1);
}
void main()
{
int a[10];
int i,max2;
printf("please input 10 integer:\n");
for (i=0;i<10;i++)
scanf("%d",&a[i]);
max2=max(a);
printf("最大的数为:%d\n",max2);
}

2、下列程序实现的是判断输入的数是否是素数，请同学们修改程序，把判断素数的过程单独放在一个自定义函数num()中。
#include <stdio.h>
int main()
{ int num,n,x;
printf("请输入一个整数");
scanf("%d",&num);
int i;
for(i=2;i<n;i++)
if(n%i==0) break;
if(i>=n) x=1;
else x=0;
if(x==1) printf("%d is a sushu.\n",num);
else printf("%d is not a sushu.\n",num);
}
答：修改后的程序：
#include <stdio.h>
int num(int n)
{
int i,x;
for(i=2;i<n;i++)
if(n%i==0) break;
if(i>=n) x=1;
else x=0;
if(x==1) printf("%d is a sushu.\n",n);
else printf("%d is not a sushu.\n",n);
}
int main()
{ int n;
printf("请输入一个整数");
scanf("%d",&n);
num(n);
}
3、请先运行程序，根据运行结果回答问题。
#include “stdio.h”
void main()
{
int sum=0;
char s[]="a1d2f3ah45si7d90", *p;
for(p=s+5; *p!='\0'; p++)
if(*p>='0'&&*p<='9')
sum=sum*10+*p-'0';
printf("sum=%d\n",sum);
}
要求： 请说明以上程序的功能，并回答以下问题：
① for(p=s+5; *p!='\0'; p++) 语句的功能是什么？
答：For循环语句：指针指向下标为4的字符串；直到字符串结束；指针移向下一个位置；
② p=s+5;语句执行后 p 的值保存的是哪个变量的地址？
答：p的新数组：f3ah45si7d90
4、阅读下列程序，请指出该程序的功能，并用自然语言或流程图写出 fun 函数的算法流程。
#include “stdio.h”
int fun(char *str,char *t)
{
int num=0;
char * p,*q;
for(int i=0; *(str+i); i++)
{
for(p=str+i,q=t;*p&&(*p==*q);p++,q++) ;
if(*q=='\0') num++;
}
return num;
}
int main()
{
char str[80],t[80];
printf("Input a string：");
gets(str);
printf("Input a string：");
gets(t);
printf("%d\n",fun(str,t));
}
答：第一步， 观察此程序时，利用 watch 窗口观察 num、str+i、*(str+i)、p、*p、q、*q 的取值， 特别是在每次循环后，这些变量的取值变化情况，并判断t字符串是否是str字符串的子串。举一个例子：str字符串为abcde ，t字符串为bc；Num=0；第一个for循环语句为i=0；str字符串出界的时候；i++;第二个for循环语句为p是str字符串的第一个下标加0，即a的地址，q为t字符串的第一个下标，即b的地址；同时要满足*p&&(*p==*q),a!=b,所以中止了；*p=b,*q=b,满足，所以指针全部指向下一个，即*p=c,*q=c,到最后t超界结束，然后num++,最后得出结果1。

额外练习：
1、编写一个比较两个字符串 s 和 t 大小的函数 int strcomp(char *s,char *t)，要求 s 小 于 t 时返回-1，s 等于 t 时返回 0，s 大于 t 时返回 1。
要求：
1）strcomp 函数中不能出现“[”和“]” ，就是不能用数组形式来解决。
2）在主函数中任意输入 4 个字符串，利用该函数求最小字符串。
答：

2、按要求改正程序：
#include “stdio.h”
void main()
{
int j,k,a[5],*p;
for(j=0; j<5; j++,p++)
scanf("%d",&p);
for(j=0; j<5; j++)
printf("%d",p++);
}
要求：
① 调试上述程序，使之具有如下功能：输入 5 个数，然后输出逐个其值。写出调试过程。
答：#include "stdio.h"
void main()
{
int j,a[5];
for(j=0; j<5; j++)
scanf("%d",&a[j]);
for(j=0; j<5; j++)
printf("%d\t",a[j]);
}
② 调试上述程序，使之具有如下功能：输入 5 个数，然后输出所有高于平均数的值。写出调试过程。
答：#include "stdio.h"
void main()
{
int j,a[5],k=0;
for(j=0; j<5; j++)
{
scanf("%d",&a[j]);
k+=a[j];
}
for(j=0; j<5; j++)
{
if((k/5)<=a[j])
printf("%d\t",a[j]);
}
}
③ 语句 int j,k,a[5],*p；不需要改动，而且除了本条语句，其它语句中都不允许出现“[”和“]”。即不能使用数组。
提示：调试此程序时，利用 watch 窗口观察每次 p++后 p 的值，以及*p 对 a 数组内容的影响。为了观察方便，可以将 a 设置为一个 watch 点，数组 a 所有元素的值在一列全部显示出来。调试时注意指针变量指向哪个目标变量。