浙江自考《计算机软件基础（二）》实验指导书

 
实验一  线性表的插入与删除

【实验目的】

1.      掌握线性表的基本运算.
2.      掌握顺序存储的概念, 学会对顺序存储数据结构进行操作.
3.      加深对顺序存储数据结构的理解, 逐步培养解决实际问题的编程能力.
4.      掌握线性表的在链接存储下的插入和删除运算.
 

【实验内容】

1.      初始化线性表
2.      建立线性表
3.      在线性表中插入指定值的元素
4.      在线性表中删除指定值的元素
5.      在线性表中删除指定位置的元素
6.      在线性表中查找指定元素
7.      输出线性表
 
【参考程序】
1.  建立学生档案链表
 
    #define LEN sizeof(struct student)   /* sizeof()  求字节数运算符 */
struct  student
       { long  num;
         float score;
         struct student *next;
       };
int n;               /* 结点的个数  */
 
struct student *creat ( )
{ struct student *head;           /*  结构体类型  */
 struct student *p1,*p2;     /*p1 指向新结点, p2  指向最后一个结点*/
 n=0;
 p1=p2=(struct student *)malloc(LEN);  /* 分配一个结点的空间 */
scanf (“%ld,%f”, &p1->num, &p1->score);  /* 输入第一个结点的值 */
 head=NULL;           /* 空链表 */
 while(p1->num!=0)      /* 若学号=0,则建表结束 */
   { n=n+1;              /*结点数*/
    if (n==1)
 head=p1;   /* 第一个结点  */
     else
p2->next=p1;    /* 链入下一个结点 */
     p2=p1;
     p1=(struct student *) malloc(LEN);  /* 分配一个新结点的空间 */
     scanf (“%ld,%f”,&p1->num,&p1->score); /* 输入这个结点的值 */
    }
 p2->next=NULL;
 return(head);           /*  返回链表的起始地址   */
}
 
2. 输出链表   
 
void print( struct student  *head )     /* 输入链表的首地址 */
{ struct student *p;
      printf("\n现在,存在 %d 个记录是: \n",n);
      p=head;                    /* p 指向第一个结点  */
      if (head != NULL)            /* 不是空链 */
      do
        { printf ("%ld %5.1lf\n",p->num,p->score);   /* 输出结点的内容 */
          p=p->next;             /*  p 指向下一个结点    */
        } while (p!=NULL);       /* p 为空指针时，循环结束 */
}
 
 
3． 在单链表中插入指定值的结点
struct  student
     { long  num;
       float score;
       struct student *next;
     };
struct student *insert ( struct student *head，struct student *stud ）
     { struct student *p0,*p1,*p2;
p1=head;                    /* p1 指向表头   */
p0=stud;                    /* p0 指向要插入的结点 */
if ( head==NULL )         /* 如果是空表，则接到表头 */
         { head=p0;
p0->next=NULL;
}
else
          { while((p0->num > p1->num) && (p1->next!=NULL ) )
                       /* 找到了插入点或整个链表找完了，则循环结束 */
                { p2=p1;
 p1=p1->next;
              }      /* p2指向刚才p1指向的结点, p1后移一个结点 */
            if (p0->num <= p1-> num)      /* 如果找到了插入点，
              { if (head==p1)
head=p0;  /* 如果插入点是表头,则插到第一个结点之前 */
              else
                  p2->next=p0;      /* 否则插到插入点之后 */
               p0->next=p1;       /* 把插入的结点与链表相连 */
             }     
else
             { p1->next=p0;
  p0->next=NULL;     /* 接到表尾 */
             } 
          }         
     n=n+1;                     /* 结点数加1  */
return head;                 /* 返回新链的首地址  */
   }
 
4.      删除单链表中指定值的结点
struct  student
     { long  num;
       float score;
       struct student *next;
     };
 
struct student *delete (struct student *head, long num)
{ struct student *p1, *p2;
           if (head==NULL)
             { printf ( “该链表是空的!" );
goto end;
}
 p1=head;
           while (num!=p1->num && p1->next!=NULL)  
                                  /* p不是要找的结点,且后面还有结点 */                  
              { p2=p1;
                p1=p1->next;        /* 后移一个结点 */
}    
if (num==p1->num)         /* 找到了！ */
               if (p1==head)
                 head=p1->next;     /* 若p是头结点,则head指向第二个结点 */            
               else
                  p2->next=p1->next;   /* 否则连下一个结点，被删结点断开了 */ 
          else
              printf ("%ld 结点没找到!", num);
       end: 
       return (head);                   /* 返回新链的首地址  */
}
 
实验二      二叉排序树

【实验目的】

1.      掌握二叉树的链式存储结构.
2.      掌握二叉树的遍历方法
3.      掌握二叉排序树的查找方法
4.      加深对二叉树的理解, 培养编程能力.

【实验内容】

1.      初始化二叉树
2.      建立二叉树
3.      二叉树的先序, 中序, 后序遍历方法
4.      在二叉树中查找指定的节点
5.      在二叉树中删除指定的节点,并显示结果.
6.      建立二叉排序树
7.      二叉排序树的查找方法
 
【参考算法】
1.      二叉树节点的定义
typedef  struct  node
 { int  data;
   struct  node  *lchild, *rchild;
}  NODE;
      
2.      二叉树遍历的算法
(1)       先序遍历
preorder ( NODE  *root )
      {  if ( ! root ) return  0;
         printf ( “%d”, root -> data );
         preorder ( root -> lchild );
preorder ( root -> rchild );
}
 
(2)       中序遍历
preorder ( NODE  *root )
      {  if ( ! root ) return  0;
         preorder ( root -> lchild );
printf ( “%d”, root -> data );
preorder ( root -> rchild );
}
 
(3)       后序遍历
preorder ( NODE  *root )
      {  if ( ! root ) return  0;
         preorder ( root -> lchild );
preorder ( root -> rchild );
printf ( “%d”, root -> data );
}
 
3.      二叉排序树的查找
      NODE  *bstsrch ( NODE  *root,  int  k )
         { NODE  *p ;
           p = root ;
           while ( p )
             { if ( p -> data = = k ) break ;
               else  if ( k < p -> data ) p = p -> lchild ;
       else  p = p -> rchild ;
}
  return  p;
}
 
 
实验三      排序

【实验目的】

1.      掌握选择排序法
2.      掌握冒泡排序法
3.      掌握快速排序法
 

【实验内容】

1.      编写选择排序函数, 并调用函数进行排序
2.  编写冒泡排序函数, 并调用函数进行排序
3.  编写快速排序函数, 并调用函数进行排序
 
【参考程序】
快速排序法
void quick ( int r[], int l; int h; int i )
      { i = l;
        j = h;
        x = r[i];
        while ( i < j )
          { while ( ( r[j] >= x  &&  ( i < j ) )
              j --;
            if ( i < j )
               { r[i] = r[j];
                 i ++;
}  
while ( ( r[i] <= x  &&  ( i < j ) )
                i ++;
            if ( i < j )
               { r[j] = r[i];
                 j --;
}  
} 
 r[i] = x;
}  
  void quicksort ( int r[], int l, int h )
{ if ( l < h )
    quick ( r, l, h, i );
    quicksort ( r, l, i - 1 );
quicksort ( r, i + 1, h );
}
 
实验四     查找

【实验目的】

1.      掌握线性查找的方法
2.      掌握二分查找的方法

【实验内容】

1.      编写线性查找函数, 并调用函数进行查找
2.  编写二分查找函数, 并调用函数进行查找
 
实验五     数据库的建立

【实验目的】

1.      掌握Visual FoxPro 的数据库的建立方法.
2.      掌握数据库的打开, 关闭, 删除等基本操作.
3.      掌握数据库记录的输入方法.

【实验内容】

1.      设计一个职工情况的数据库”职工.dbf”, 其内容要包含职工的工号, 姓名, 性别, 出生年月, 婚姻状况, 工资, 职称和简历.
2.      输入若干记录.
3.      显示数据库记录
4.      数据库“职工.dbf”保存在”e:\准考证号”文件夹中, 如: ”e:\05123456”

【实验操作】

一. 菜单方式
1.      选择”文件”菜单下的”新建”命令.
2.      在”新建”对话框中, 选择”表”选项,单击”新建文件”按钮.
3.      在”创建”对话框中, 设定表保存的位置, 表名和类型 ( 表/*.dbf ), 单击”保存”按钮.
4.      在”表设计器”对话框中, 输入各字段的字段名, 类型, 宽带和小数位数等属性, 选择”确定”按钮.
5.      在”是否立即输入数据?”对话框中, 选择”是”.
6.      在”记录编辑”窗口中, 输入记录.
7.      关闭”记录编辑”窗口, 使用”显示”菜单下的”浏览”命令, 查看记录.
二. 命令方式
       create 职工
 
  实验六     数据库的索引

【实验目的】

1.      理解索引概念.
2.      掌握索引的建立和使用的方法.

【实验内容】

对职工情况的数据库,分别建立按”工号”,”年龄”,”职称”,”工资”的索引文件.
 
【实验操作】
一. 菜单方式
1.      选择”文件”菜单的”打开”命令, 在”打开”对话框中, 在”e:\ 准考证号”
 (如: ”e:\05123456”) 文件夹中, 选择”职工.dbf”.
2.      选择”显示”菜单下的”表设计器”.
3.      在”表设计器”中, 选择”索引”选项卡, 在索引名列表处输入”工号”索引标识gh, 调出表达式生成器, 选择”工号”字段作为索引表达式.  
4.      根据上述步骤, 分别建立按”年龄”,”职称”,”工资”的索引文件.
二. 命令方式
use  职工
index on 工号 to 职工
list
use
 
附录      实验报告格式
 
            实 验 报 告          
 
实验题目:
 
准考证号:                       姓名:                    计算机号:                         
单位:                           电话:                                                      
1. 实验目的
2. 实验内容
3. 算法与流程图
4. 程序清单
5. 运行结果
     如果需要输入时, 应注明输入的数据.
6. 调试过程和分析
     如果程序未能通过, 则应分析其原因.
8.      本次实验的心得体会和建议
9.     

本资料doc文件下载：

《计算机软件基础（二）》.doc