软件技术基础》实验指导书.ppt

软件技术基础实验指导书,太原理工大学信息工程学院 信息与通信工程系 20042005学年第1学期,软件技术基础实验教学大纲,一、实验课程的性质、目的和任务 1培养学生利用所学数据结构、查找排序技术及数据库技术解决问题的能力，掌握对问题分析建模、设计算法、编程调试并实现的方法与技术。 2对教材上所给出的算法，用C语言编程并上机调试，必要时做改进并在计算机上实现。,软件技术基础实验教学大纲,一、实验课程的内容、要求及学时分配 1内容及学时分配 实验一 线性顺序表的插入与删除（2学时） 实验二 顺序栈的入栈与退栈及读栈顶元素（2学时） 实验三 规则矩阵的压缩存储（2学时） 实验四 有序表的对分查找（2学时） 实验五 顺序表的冒泡排序（2学时）,软件技术基础实验教学大纲,基本要求 学生最后提交实验报告和程序源码。实验报告应包含以下内容： (1) 问题描述、分析。 (2) 解决问题的算法描述。 (3) 程序源码，且必须有必要的注释语句。 实验报告可以提交电子版或书面版，程序源码提交电子版（磁盘）。,软件技术基础实验教学大纲,三、考核 以学生的实验报告、程序源码以及上机出勤作为考核依据。 四、参考资料 教材、C语言程序设计、数据结构等参考书。,实验一 线性顺序表的插入与删除,实验目的与要求：理解和掌握线性表的顺序存储结构，使用C语言根据相应算法编写一个程序，实现线性顺序表的插入与删除。要求仔细阅读下面的内容，编写C程序，上机通过，并观察其结果，写出实验报告书。 实验内容：建立一个长度为n的线性表，在第i个元素前面插入一个新元素b，得到一个长度为（n1）的线性表；然后再删除第i个元素，得到长度为n的线性表。,实验一 线性顺序表的插入与删除,具体要求： l根据线性顺序表的插入与删除的算法编写C程序，并上机调试。 l编写的C程序要求建立一个长度不小于10的线性表，输出原始线性表，输出完成插入运算后的线性表，输出删除某个元素后的线性表。 l实验完成后，写出实验报告书。,实验一 线性顺序表的插入与删除,算法： 1建立一个空线性表的顺序存储空间的C语言描述： #include “stdlib.h” void initsl(v,m,n) ET *v; int m, *n; v=malloc(m*sizeof(ET); *n=0; return; ,实验一 线性顺序表的插入与删除,2在长度为n的线性表中的第i个元素前插入新元素b void insl(v,m,n,i,b) int v ; int m,*n, i; int j; if (*n= =m) printf (“overflown”; return; if (i*n) i=*n+1; If (i=i ;j-) vj=vj-1; vi-1=b; *n=*n+1; return;,实验一 线性顺序表的插入与删除,3在长度为n的线性表中删除第i个元素 void desl(v,m,n,i) int v ; int m,*n, i; int j; if (*n=0) printf (“Underflown”; return; if ( i*n) printf (“Not this element in the listn”); return; for(j=i;j=*n-1;j+) vj-1=vj; *n=*n-1; return;,#include “stdio.h“ #include “stdlib.h“ #include “conio.h“ void insl(int v,int m,int *n,int i,int b) /*shang ji 1,xianxing biao cha ru P32 */ int j; if(*n=m) printf(“overflow!n“);return; if(i*n) i=*n+1; if(i=i;j-) vj=vj-1; vi-1=b; *n=*n+1; return; main() int a15=1,2,3,4,5,6,7,8,9,10; int n=6; int i; insl(a,15, ,实验二 顺序栈的入栈与退栈及读栈顶元素,实验目的与要求：通过对栈的编程练习，加强对栈的特点、顺序存储结构及其基本运算的理解和掌握。使用C语言根据相应算法编写一个程序，实现建栈、入栈、退栈及读栈顶元素。要求仔细阅读下面的内容，编写一个C程序，上机调试通过，并观察其结果，写出实验报告书。,实验二 顺序栈的入栈与退栈及读栈顶元素,实验内容：建立一个容量为m的顺序栈，首先在其中压入5个元素，然后作退栈运算和读栈顶元素。,实验二 顺序栈的入栈与退栈及读栈顶元素,具体要求： l根据顺序栈的入栈、退栈、读栈顶元素算法编写一个C程序，并上机调试。 l编写的C程序要求建立一个容量不小于5的顺序栈，首先用入栈算法在其中压入5个元素，然后读栈顶元素，接着作退栈运算，并输出退栈结束后的栈顶元素。 l实验完成后，写出实验报告书。,实验二 顺序栈的入栈与退栈及读栈顶元素,算法： 1建立空栈的顺序存储空间的用C语言描述： #include “stdlib.h” void init_stack(s,m,top) ET *s; int m, * top; / ET为元素的数据类型 s=malloc(m * sizeof(ET); /Create Memory * top=0; return; ,实验二 顺序栈的入栈与退栈及读栈顶元素,2在容量为m的栈S中插入一个元素x： void push(s, m, top, x) int s,x; int m,*top; if (*top=m) printf(“Stack-Overflown”); return *top=*top+1; s*top-1=x; return;,实验二 顺序栈的入栈与退栈及读栈顶元素,3在容量为m的栈S中删除栈顶元素： void pop(s, m, top, y) int s,*y; int m,*top; if (*top=0) printf(“Stack-Underflown”); return *y=s*top-1; *top=*top-1; return; ,实验二 顺序栈的入栈与退栈及读栈顶元素,4读栈顶元素； void read(s, m, top, y) int s,*y; int m,*top; if (*top=0) printf (“Stack emptyn”); return *y=s*top-1; return; ,实验三 规则矩阵的压缩存储,实验目的与要求：通过对三角矩阵的压缩存储编程练习，加强对规则矩阵压缩存储的理解。使用C语言根据压缩存储原理编写一个程序，实现三角矩阵的压缩存储。要求仔细阅读下面的内容，编写一个C程序，上机调试通过，并观察其结果，写出实验报告书。 实验内容：建立一个n阶三角方阵，用一个一维数组以行为主顺序存放下(上)三角矩阵中的所有下(上)三角部分的元素。,实验三 规则矩阵的压缩存储,具体要求： l 对一个阶数不小于5的三角矩阵，编写一个C程序，实现压缩存储。要求先输出原始矩阵，再输出一维数组，最后根据该一维数组得到原始矩阵并输出。 l 实验完成后，写出实验报告书。,实验三 规则矩阵的压缩存储,算法基本思想：对于下三角矩阵，大约有一半的元素为0，不必存储这些零元素，而只需存储下三角部分的元素。 存储的原则是用一个一维数组以行为主顺序存放下三角矩阵中的所有下三角部分的元素。这样，一个n阶的下三角矩阵有n2个元素，但只需存储n(n+1)/2个下三角部分的元素。,实验三 规则矩阵的压缩存储,设n阶下三角矩阵：,实验三 规则矩阵的压缩存储,设一维数组B，长度为n(n+1)/2；按行依次存放A中下三角部分的元素。 下三角矩阵A用一维数组B表示后，二者关系如下：,实验三 规则矩阵的压缩存储,ij (aij下三角部分) Bi(i-1)/2+j ij (aij上三角部分) 0,#include “stdlib.h“ #include “stdio.h“ /*shangji 4,guize juzhen ya suo P69 */ main() /*xia sanjiao juzhen de yasuo cunchu */ int a10=1,2,3,4,5,6,7,8,9,10; int b33; int i,j; printf(“n“); /*mei ci zhixing shi,xian shuchu konghang */ for(i=0;i=3;i+) for(j=0;j=3;j+) if(j=i) printf(“%d “,ai*(i+1)/2+j); else printf(“0 “); printf(“n“); getch(); ,实验四 有序表的对分查找,实验目的与要求：理解和掌握线性表的查找技术，使用C语言根据相应算法编写一个程序，实现顺序存储的有序表的对分查找。要求仔细阅读下面的内容，编写C程序，上机通过，并观察其结果，写出实验报告书。 实验内容：在顺序存储的长度为n的有序线性表中对分查找元素x的序号k,实验四 有序表的对分查找,具体要求： l 根据有序线性表的对分查找的算法编写C程序，并上机调试。 l 编写的C程序要求若表中存在待查找记录，则显示该记录在表中的位置，否则显示该记录不存在。 l 实验完成后，写出实验报告书。,实验四 有序表的对分查找,算法： 1 有序线性表的长度为n，被查元素为x，将x与线性表的中间项进行比较，分三种情况： 若中间项的值等于x，则说明查到，查找结束。 2 若x小于中间项的值，则在线性表的前半部分以相同的方法进行查找。 3 若x大于中间项的值，则在线性表的后半部分以相同的方法进行查找。,实验四 有序表的对分查找,int bserch(v,n,x) int n; ET x,v ; int i,j,k; i=1;j=n; while(ix) j=k-1; else i=k+1; return (-1); ,实验五 顺序表的冒泡排序,实验目的与要求：理解和掌握线性表的排序技术，使用C语言根据相应算法编写一个程序，实现顺序存储的线性表的冒泡排序。要求仔细阅读下面的内容，编写C程序，上机通过，并观察其结果，写出实验报告书。 实验内容：将顺序存储的长度为n的无序线性表进行排序,实验五 顺序表的冒泡排序,具体要求： l 根据线性表的冒泡排序的算法编写C程序，并上机调试。 l 编写的C程序要求将顺序存储的长度为n的无序线性表进行排序 实验完成后，写出实验报告书。,实验五 顺序表的冒泡排序,算法： 1 从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，前面的元素大于后面的元素，则将它们互换，最后将线性表中的最大元素换到了表的最后。,实验五 顺序表的冒泡排序,2从后到前扫描剩下的线性表，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，后面的元素小于前面的元素，则将它们互换，最后将线性表中的最小元素换到了表的最前面。 3 对剩下的线性表重复上述过程，直到剩下的线性表变空为止，此时的线性表已经变为有序。,实验五 顺序表的冒泡排序,Bubsort(p,n) int n; ET p ; int m,k,j,i; ET d; k=0;m=n-1;,while (kpi+1) d=pi;pi=pi+1;pi+1=d;m=i; j=k+1;k=0; for(i=m;i=j;i-) if(pi-1pi) d=pi;pi=pi-1;pi-1=d;k=i; return; ,#include “stdio.h“ #include “stdlib.h“ /*shangji 6,P123 */ bubsort(int p,int n) /*mao pao pai xu */ int m,k,j,i; int d; k=0;m=n-1; while(kpi+1) /*faxian nixu jiaohuan */ d=pi; pi=pi+1; pi+1=d