软件技术基础实验规范及大纲（C语言学生版）.doc

《软件技术基础》课程实验教学规范（理工类专业）
第一部分 《软件技术基础》课程实验教学大纲
适用专业：非计算机专业（理工类）
实验类别：基础实验
总实验学时：6学时（分3次上机，每次2学时）

一、 教学总目的和要求
本大纲是针对全校选修课程中《软件技术基础》课程的上机应用训练而编写的。本课程的主要任务是运用在《软件技术基础》课程中学到的理论知识指导实验，使学生们建立起验证常用数据结构的算法，提高熟练解决实际问题的编程能力。本实验课程着重培养学生的逻辑思维能力和动手能力，帮助学生加深对常用数据结构的理解，掌握典型管理信息系统的开发方法，培养良好的实验习惯。
要求学生独立完成每个实验，教师检查实验现象和实验结果。实验中出现的问题，学生应自己解决，如果解决不了，可以在教师指导下加以解决。
二、 实验目的：
1. 掌握数据结构中的一些基本概念。数据、数据项、数据元素、数据类型和数据结构，以及它们之间的关系。
2. 了解数据的逻辑结构和数据的存储结构之间的区别与联系；数据的运算与数据的逻辑结构的关系。
3. 掌握线性表的基本操作：插入、删除、查找以及线性表的合并等运算。
4. 掌握常用的排序方法，并用高级语言实现排序算法。
5. 理解排序的定义和各种排序的特点。
6. 了解排序过程以及依据的原则，并了解各种排序方法的时间复杂度分析。
7. 掌握运用C语言上机调试线性表的基本方法。
三、 实验条件
1. 硬件：每人一台微机
2. 软件：操作系统和C语言系统
四、 实验方法
课前认真准备预习。实验时先确定存储结构后，上机调试实现线性表的基本运算。课后根据教师要求撰写实验报告。
五、 实验内容
1、线性表操作（4学时）
【内容】
1. 试编写在无头结点的单链表上实现线性表基本运算LOCATE（L，X），INSERT（L，X，1）和DELETE（L，1）的算法。
参考算法:
#include <stdio.h>
typedef struct node
{
int data;
struct node *next;
}lklist;

lklist *creat(void)
{
lklist *p,*q,*head;
int i=0;
p=q=(lklist *)malloc(sizeof(lklist));
printf("\ncreate :input data,0--end\n");
scanf("%d", &p->data);
head = NULL;
while (p->data!=0)
{
i++;
if(i==1)
{
head=p;
}
else
{
q->next=p;
}
q=p;
/* 此部分学生填写（此处可能有一条或多条语句） */
}
q->next=NULL;
return(head);
}

void display(lklist *L)
{
lklist *p,*q;
p=L;
printf("\n");
while(p!=NULL)
{
/* 此部分学生填写（此处可能有一条或多条语句） */
}
}

void locate(lklist *L, int x)
{
lklist *p,*q;int i=1;
p=L;
while(p->next!=NULL)
{
if(p->data==x)
{
printf("\nfound!It's position is %d",i);
return;
}
else
{
/* 此部分学生填写（此处可能有一条或多条语句） */
}
}
if(p->data!= x)
{
printf("no this node!");
}
}

lklist *insert(lklist *L,int x,int i)
{
lklist *p,*q;int j;
p=L;
q=(lklist *)malloc(sizeof(lklist));
q->data = x;
if(i<0)
{
printf("error,try again!");
}
if(i==1)
{
q->next=L;
L=q;
return L;
}
j=1;
while((j<i-1) && (p->next!=NULL))
{
j++;
p=p->next;
}
if(j==i-1)
{
/* 此部分学生填写（此处可能有一条或多条语句） */
}
else
{
printf("error!");return L;
}
}

lklist *delete(lklist *L,int i)
{
lklist *p,*q;
int j=1;
p=L;
if(i==1)
{
q=L;
L=L->next;
free(q);
return L;
}
while(p->next&&j<i-1)
{
p=p->next;
++j;
}
if(!(p->next)||j>i)
{
return L;
}
/* 此部分学生填写（此处可能有一条或多条语句） */
return L;
}

main()
{
lklist *L;
int data,loc,i;
printf("\n1--insert 2--delete 3--locate\n");
printf("please input:");
scanf("%d",&i);
switch(i)
{
case 1: L=creat();
printf("insert:input data and postion:");
scanf("%d,%d",&data,&loc);
L=insert(L,data,loc);
display(L);
break;
case 2: L=creat();
printf("delete data:input position:");
scanf("%d",&loc);
L=delete(L,loc);
display(L);
break;
case 3: L=creat();
printf("input the data want to find:");
scanf("%d",&data);
locate(L,data);
}
}
2. 假设有两个按数据元素值递增有序排列的线性表A和B，均以单链表作为存储结构。编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许值相同）排列的线性表C，并要求利用原表（即A表和B表）结点空间存放表C。
参考算法:
#include <stdio.h>
typedef struct node
{
int data;
struct node *next;
}lklist;

lklist *creat(void)
{
lklist *p,*q,*head;
int i=0;
p=q=(lklist *)malloc(sizeof(lklist));
printf("\ncreate :input data,0--end\n");
scanf("%d",&p->data);
head=NULL;
while(p->data!=0)
{
i++;
if(i==1)
{
head=p;
}
else
{
q->next=p;
}
q=p;
p=(lklist *)malloc(sizeof(lklist));
scanf("%d",&p->data);
}
q->next=NULL;
return(head);
}

void display(lklist *L)
{
lklist *p,*q;
p=L;
printf("\n");
while(p!=NULL)
{
printf("%d ",p->data);
p=p->next;
}
}

lklist *connectlink(lklist *A,lklist *B,lklist *C)
{
lklist *p,*q,*m;
p=A;
q=B;
C=NULL;
while((p!=NULL)&&(q!=NULL))
{
if(p->data<q->data)
{
m=p;
A=A->next;
p=A;
}
else
{
/* 此部分学生填写（此处可能有一条或多条语句） */
}
m->next=C;
C=m;
}
while(p!=NULL)
{
m=p;
A=A->next;
p=A;
m->next=C;
C=m;
}
while(q!=NULL)
{
/* 此部分学生填写（此处可能有一条或多条语句） */
}
return C;
}

main()
{
lklist *A,*B,*C;
A=creat();
B=creat();
C=NULL;
C=connectlink(A,B,C);
display(C);
}
3. 将一个线性表中的值就地逆置。
main()
{
/* 主程序参数说明部分 */
int a[ ]={1,2,3,4,5,6,7,8},i; /* 将线性表以顺序存储方式存放 */
void Converse(int a[ ]; int n); /* 函数说明 */
/* 程序主体 */
printf(“\n 原数组序列为: “);
for (i=0;i<8;i++)
{
printf(“%d”,a[i]);
}
Converse(a,8); /* 函数调用 */
printf(“\n 逆序数组序列为: “);
for (i=0;i<8;i++)
{
printf(“%d”,a[i]);
}
}

/* 函数 */
void Converse(int a[ ]; int n)
{
/* 参数说明部分*/
int m, x, i ;
/* 程序主体 */
m=n/2;
for (i=0;i<m;i++)
{
/* 此部分学生填写（此处可能有一条或多条语句） */
}
}
4. 在线性表的顺序存储结构的第一个位置上插入一个元素。
#include <stdio.h>
#define MAXSIZE 100
typedef struct
{
int datas[MAXSIZE];
int last;
}SEQUENLIST;

SEQUENLIST insert(SEQUENLIST la,int x);
main()
{
int flag=1,x,i;
SEQUENLIST la;
la.last=0;
printf("\n");
while(flag)
{
scanf("%d",&la.datas[la.last]);
if(la.datas[la.last]==0) flag=0;
la.last++;
}
la.last--;
printf("\ninput the data want to insert:");
scanf("%d",&x);
la=insert(la,x);
printf("\n");
for(i=0;i<la.last;i++)
printf("%d ",la.datas[i]);
}

SEQUENLIST insert(SEQUENLIST la,int x)
{
int k;
for(k=la.last;k>=1;k--)
/* 此部分学生填写（此处可能有一条或多条语句） */
la.datas[0]=x;
la.last=la.last+1;
return la;
}


2、排序基本操作（2学时）
【内容】
1. 设计一待排序的线性表以顺序存储结构存储，试写出冒泡排序算法。
参考程序如下：
#include <stdio.h>
#define N 10
main( )
{
int a[N+1];
int i, j, t;
for(i = 1; i <= N; i++)
{
scanf("%d", &a[i]);
}
printf("\n");
for(j = 1; j < N; j++)
for( i = 1; i < N-j+1; i++)
/* 此部分学生填写（此处可能有一条或多条语句） */
printf("the sorted numbers:\n");
for(i = 1; i <= N; i++)
{
printf("%4d", a[i]);
}
}

2. 给出n个学生的考试成绩表，每条信息由姓名与分数组成，试设计一个算法：
（1）按分数高低次序，打印出每个学生在考试中获得的名次，分数相同的为同一名次。
（2）按名次列出每个学生的姓名与分数。
参考程序如下：
#define N 10
struct student
{
char name[8];
int score;
};
struct student R[N];
main()
{
int num,i,j,max;
struct student temp;
printf("\n 请输入学生成绩:\n");
for(i=0;i<N;i++)
{
printf("name:");
scanf("%s",R[i].name);
scanf("%4d",&R[i].score);
}
num=1;
for(i=0;i<N;i++)
{
/* 此部分学生填写（此处可能有一条或多条语句） */
if(max!=i)
{
temp=R[max];
R[max]=R[i];
R[i]=temp;
}
if((i>0)&&(R[i].score<R[i-1].score))
{
num=num+1;
}
printf("%4d%s%4d",num,R[i].name,R[i].score);
}
}

第10页 共10页