结构体及运用

数据结构课程所研究的问题均运用到“结构体”。在C语言中结构体的定义、输入/输出是数据结构程序设计的重要语法基础。定义结构体的一般格式:
struct   结构体类型名
     {  类型名1       变量名1;  //数据子域
类型名2       变量名2;……
类型名n       变量名n;
};
其中struct是保留字。结构体类型名由用户自己命名。在使用时必须声明一个具体的结构体类型的变量,声明创建一个结构体变量的方法是:
struct 结构体类型名    结构体变量名;
例如:  struct  ElemType     /* 定义结构体  */
       { int  num;  char  name[10];
        } ;
struct  ElemType  x; /*  声明结构体变量x  */
另外有一种方法使用typedef 语句定义结构体,在声明结构体变量时可以不写struct,使得书写更加简便。例如:
 typedef  struct
       { int  num;
        char  name[10];
       } ElemType;
ElemType就是一个新的类型名,并且是结构体类型名。声明变量x的语句是:
      ElemType  x;
一个结构体中可以包含多个数据子域。数据子域的类型名一般指基本数据类型(int  char 等),也可是已经定义的另一结构体名。数据子域变量名可以是简单变量,也可以是数组。它们也可以称为结构体的数据成员。
通过“结构体变量名.数据子域” 可以访问数据子域。
例1.6   设计Student结构体,在主程序中运用。
#include  <stdio.h>
#include <string.h>
typedef  struct           /*  定义结构体Student  */
{ long  num;         /*  学号  */
   int   x;           /*  成绩  */
   char  name[10];    /*  姓名  */
} Student;
void  main( ) 
 {  Student   s1;                 /*  声明创建一个结构体变量s1  */
s1.num=1001 ;                /*  为s1的数据子域提供数据    */
s1. x=83;                                  
strcpy( s1.name, “ 李  明”);  
printf( “\n  姓名: %s”, s1.name);  /*  输出结构体变量s1 的内容 */
printf( “\n  学号: %d”, s1.num);
printf( “\n  成绩: %d”, s1.x);    
}
或者使用键盘输入:
  {     scanf(“%d”, s1.num);
scanf(“%d”, s1.x);
scanf(“%s”, s1.name);
     }
还可以通过“结构体指针->数据子域” 来访问数据域。在实际问题中还会使用到指向结构体的指针,通过以下语句段可以说明结构体指针的一般用法。
{  Student  *p;                            /*  声明指针变量p */
p=( Student *)malloc(sizeof( Student));  /* 分配存储单元,首地址赋给p指针 */
   p->num=101;    p->x=83;    strcpy( p->name, “李  明 ”);   
printf(“\n  %10s%6d%6d”,p->name,p->num,p->x);
}
设计一个一维数组,每个数组元素是Student结构体类型,通过以下语句段可以说明结构体数组的一般用法。可以通过“结构体数组名[下标].数据子域”访问数据域。
 {  Student  a[5];                      /*  声明创建一个结构体数组a  */
    int i ;
for( i=0, i<5, i++){   
printf(“\n  学号:%d”,a[i].num) ; 
printf(“\n  姓名:%s”,a[i].name) ;
printf(“\n  成绩:%d”,a[i].x) ;    
                        }  
       } 
以上是关于结构体的基本概念和简单运用。



第二部分   上机实验习题
上机实验要求及规范
数据结构课程具有比较强的理论性,同时也具有较强的可应用性和实践性。在上机实验是一个重要的教学环节。一般情况下学生能够重视实验环节,对于编写程序上机练习具有一定的积极性。但是容易忽略实验的总结,忽略实验报告的撰写。对于一名大学生必须严格训练分析总结能力、书面表达能力。需要逐步培养书写科学实验报告以及科技论文的能力。拿到一个题目,一般不要急于编程。按照面向过程的程序设计思路(关于面向对象的训练将在其它后继课程中进行),正确的方法是:首先理解问题,明确给定的条件和要求解决的问题,然后按照自顶向下,逐步求精,分而治之的策略,逐一地解决子问题。具体实习步骤如下:
1.问题分析与系统结构设计
充分地分析和理解问题本身,弄清要求做什么(而不是怎么做),限制条件是什么。按照以数据结构为中心的原则划分模块,搞清数据的逻辑结构(是线性表还是树、图?),确定数据的存储结构(是顺序结构还是链表结构?)。然后设计有关操作的函数。在每个函数模块中,要综合考虑系统功能,使系统结构清晰、合理、简单和易于调试。最后写出每个模块的算法头和规格说明,列出模块之间的调用关系(可以用图表示),便完成了系统结构设计。
2.详细设计和编码
详细设计是对函数(模块)的进一步求精,用伪高级语言(如类C语言)或自然语言写出算法框架,这时不必确定很多结构和变量。
编码,即程序设计,是对详细设计结果的进一步求精,即用某种高级语言(如C/C++语言)表达出来。尽量多设一些注释语句,清晰易懂。尽量临时增加一些输出语句,便于差错矫正,在程序成功后再删去它们。
3.上机准备
熟悉高级语言用法,如C语言。熟悉机器(即操作系统),基本的常用命令。静态检查主要有两条路径,一是用一组测试数据手工执行程序(或分模块进行);二是通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑,在这个过程中再加入一些注释和断言。如果程序中逻辑概念清楚,后者将比前者有效。
4.上机调试程序
调试最好分块进行,自底向上,即先调试底层函数,必要时可以另写一个调用驱动程序,表面上的麻烦工作可以大大降低调试时所面临的复杂性,提高工作效率。
5.整理实习报告
    在上机实开始之前要充分准备实验数据,在上机实践过程中要及时记录实验数据,在上机实践完成之后必须及时总结分析。写出实验报告。
一、实验报告的基本要求:
      一般性、较小规模的上机实验题,必须遵循下列要求。养成良好的习惯。
(1)    姓名 班级 学号 日期
(2)    题目:内容叙述
(3)    程序清单(带有必要的注释)
(4)    调试报告:
实验者必须重视这一环节,否则等同于没有完成实验任务。这里可以体现个人特色、或创造性思维。具体内容包括:测试数据与运行记录;调试中遇到的主要问题,自己是如何解决的;经验和体会等。
二、实验习报告的提高要求:
阶段性、较大规模的上机实验题,应该遵循下列要求。养成科学的习惯。
(1)    需求和规格说明
描述问题,简述题目要解决的问题是什么。规定软件做什么。原题条件不足时补全。
(2)    设计
a.    设计思想:存储结构(题目中限定的要描述);主要算法基本思想。
b.    设计表示:每个函数的头和规格说明;列出每个函数所调用和被调用的函数,也可以通过调用关系图表达。
c.    实现注释:各项功能的实现程度、在完成基本要求的基础上还有什么功能。
(3)    用户手册:即使用说明。
(4)    调试报告:调试过程中遇到的主要问题是如何解决的;设计的回顾、讨论和分析;时间复杂度、空间复杂度分析;改进设想;经验和体会等。



实习一  复数ADT及其实现
一、实验目的
1. 了解抽象数据类型(ADT)的基本概念,及描述方法。
 2. 通过对复数抽象数据类型ADT的实现,熟悉C语言语法及程序设计。为以后章节的学习打下基础。
二、实例
   复数抽象数据类型ADT的描述及实现。
   [复数ADT的描述]
   ADT complex{ 
       数据对象:D={ c1,c2   c1,c2∈FloatSet }
       数据关系:R={ <c1,c2>  c1   c2    }
       基本操作:创建一个复数        creat(a);
                 输出一个复数        outputc(a);
                 求两个复数相加之和  add(a,b);
                 求两个复数相减之差  sub(a,b);
                 求两个复数相乘之积  chengji(a,b);
                 等等;
              } ADT complex;
   [复数ADT实现的源程序]
#include <stdio.h>
#include <stdlib.h>
/* 存储表示,结构体类型的定义   */
typedef  struct
   { float x;                   /* 实部子域 */
     float y;           /* 虚部的实系数子域 */ 
    }comp;
/* 全局变量的说明 */
comp a,b,a1,b1;
int z;
/* 子函数的原型声明  */
void creat(comp *c);
void outputc(comp a);
comp add(comp k,comp h);
/* 主函数 */
main()
{ creat(&a);   outputc(a);
  creat(&b);   outputc(b);
  a1=add(a,b); outputc(a1);
}  /* maijn  */
/*  创建一个复数   */
void creat(comp *c)
{ float c1,c2;
  printf("输入实部real x=?");scanf("%f",&c1);
  printf("输入虚部xvpu y=?");scanf("%f",&c2);
  (*c).x=c1;  c ->y=c2;
}   /* creat */
/*  输出一个复数 */
void outputc(comp a)
  { printf("\n  %f+%f i \n\n",a.x,a.y); 
   }
/*  求两个复数相加之和 */
comp add(comp k,comp h)
{ comp l;
  l.x=k.x+h.x;  l.y=k.y+h.y;
  return(l);
  }  /* add */
三、实习题
首先将上面源程序输入计算机,进行调试。运行程序,输入下列两个复数的实部域虚部,记录两个复数相加的输出结果。  原始数据:2.0 + 3.5i    ,3.0 – 6.3i 
然后在上面程序的基础上,增加自行设计的复数减、复数乘的两个子函数,适当补充必需的语句(例如函数原型声明、主函数中的调用等)。提示:
// 求两个复数相减之差的函数 
comp sub(comp k,comp h) { ……}  
// 求两个复数相乘之积的函数 
comp chengji(comp k,comp h){ …… } 
再次调试运行程序。输入数据,记录结果,最后完成实验报告。