新软件基础实验指导

《新软件基础实验指导》由会员分享，可在线阅读，更多相关《新软件基础实验指导（38页珍藏版）》请在金锄头文库上搜索。

1、计算机软件基础实验指导书计算机软件基础实验指导书C 语言实现语言实现冷朝霞冷朝霞 杨媛杨媛 杨文宇杨文宇 白华煜白华煜 孙旭霞孙旭霞西安理工大学自动化与信息工程学院二 00 八年六月计算机软件基础实验指导书目目 录录实验报告要求 . . 1实验一 顺序表的基本操作.2实验二 单链表的基本操作.5实验三 堆栈的基本操作.10实验四 循环队列的基本操作 .14实验五 稀疏矩阵的转置.18实验六 二叉排序树的建立与遍历.22实验七 直接插入排序.24实验八 直接选择排序.26实验九 顺序查找和折半查找.28实验十 二叉排序树查找.32计算机软件基础实验指导书1实验报告要求实验报告要求一、实验目的 二

2、、实验内容 三、程序流程图 四、实验结果（要求检测所有情况的正确性，写出测试条件及相应的 测试结果） 五、完成思考题计算机软件基础实验指导书2实验一实验一 顺序表的基本操作顺序表的基本操作(2 学时学时)一、实验目的一、实验目的 了解顺序表的逻辑特征，掌握顺序表的描述方法、特点及有关的 概念，掌握顺序表上的插入和删除等基本操作算法。 二、实验内容二、实验内容 在顺序表List 中，实现顺序表的基本操作，包括：初始化顺序 表，在表中插入元素、删除元素。 基本要求： （1） 顺序表的元素个数可随意设定； （2） 可连续测试任意多个元素的插入、删除， （插 入、删除位置及要插入元素数值均从键盘输入）

3、 ；（3） 任一操作结束后将顺序表中的内容输出； （4） 可由用户选择退出程序。 三、实验要点及说明三、实验要点及说明 顺序表又称为线性表的顺序存储结构，它是用一组地址连续的存 储单元依次存放线性表的各个元素。可按如下格式定义顺序表：#define MAXLEN 50 /* 定义顺序表最大元素个数 50 */ typedef int datatype;typedef structdatatype ListMAXLEN; /* 定义顺序表 List */int Num; /* 定义顺序表表长（1MAXLEN）*/ Seqlist; 模块划分：（1）initiq(Seqlist *la )函数：初

4、始化顺序表（2）insertq( )函数：实现插入功能（3）deleteq( )函数：实现删除功能（4）print( )函数：实现输出功能 四、参考源程序四、参考源程序 #include #define MAXLEN 50 typedef int datatype; typedef structdatatype ListMAXLEN;int Num; Seqlist; void initiq(Seqlist *la );计算机软件基础实验指导书3int insertq(Seqlist *la,int n); int deleteq(Seqlist *la,int n); int print(S

5、eqlist *la); void main() Seqlist la; int s,n; /* s 选择输入， n 插入或删除数据的个数*/ printf(“请输入你的选择: 1-initiate 2-insert 3-delete 4-print 5- exitnyour choice =“); scanf(“%d“, while(s!=5) if(s=1) initiq( printf(“完成初始化 !n“); else if(s=2) printf(“请输入待插入的数据个数:“); scanf(“%d“, insertq( print( else if(s=3) printf(“请输入

6、待删除的数据个数:“); scanf(“%d“, deleteq( print( else if(s=4) print( elseprintf(“你的选择是错误的!n “); printf(“请输入你的选择: 1-initiate 2-insert 3-delete 4-print 5- exitnyour choice =“); scanf(“%d“, /*初始化*/ void initiq(Seqlist *la ) la- Num=0; /*插入*/ int insertq(Seqlist *la,int n) int i,j; /* i 插入位置， j 顺序表下标 */ datatyp

7、e x; /* x 插入数据 */ while(n)计算机软件基础实验指导书4 if (la-Num=MAXLEN-1) printf (“n 表满，不能插入！插入未完成，还有%d 个数据未 插入n“,n); return 0; printf(“请输入插入的位置和数据:“); scanf(“%d%d“, if (ila-Num) printf (“n 插入位置不合理！n“); else if (i= la-Num) la-Listi=x; else for ( j=la-Num; ji; j-) la-Listj=la-Listj-1; la-Listi=x; la-Num+; n-; pri

8、ntf(“插入完成n“); return 1; /*删除*/ int deleteq(Seqlist *la,int n) int i,j; /* i 删除位置， j 顺序表下标 */ while(n) if (la-Num=la-Num) printf (“n 删除位置错误!n“); else for ( j=i+1; jNum; j+) la-Listj-1=la-Listj; la-Num-; n-; printf(“删除完成！n“); return 1; /*显示输出*/计算机软件基础实验指导书5int print (Seqlist *la) int m; if (la-NumNum;

9、m+) printf(“List%d=%d “,m,la-Listm); printf(“n 表长为%dn“,la-Num); return 1; 五、思考题五、思考题 1设顺序表 L 中的数据元素按递增排列，编写一个算法，将数据元 素 x 插入到顺序表 L 的适当位置上，以保持顺序表的有序性。 2设计一算法实现删除顺序表 a 中第 i 个元素起的 k 个元素。typedef struct int datatype100;int length; /*顺序表的长度*/SqList; 3设已有线性表 la 的数据结构定义同上，编写一个算法，删除顺序 表 la 中所有值为 x 的数据元素。 4如何用

10、程序实现将两个不同的顺序表复制到一个顺序表中？实验二实验二 单链表的基本操作（单链表的基本操作（2 学时）学时）一、实验目的一、实验目的 了解链表的逻辑结构特征，掌握链表的描述方法、特点及有关概 念，掌握链表的建立、插入、删除以及查找的基本操作算法。 二、实验内容二、实验内容 实现单链表的基本操作，包括：建立单链表，插入结点，删除结 点，查找结点，打印输出单链表中的所有结点。 基本要求： （1）单链表的结点个数可随意设定； （2）可连续测试任意多个结点的插入、删除， （插 入位置、插入结点的数据及被删除结点的数据要计算机软件基础实验指导书6从键盘输入） ；（3）根据键盘输入的数据在单链表中查找

11、结点； （4）任一操作结束后将单链表中的内容输出； （5）可由用户选择退出程序。 三、实验要点及说明三、实验要点及说明 线性表的链式存储结构是一种物理存储单元上非连续、非顺序的 存储结构，数据元素的逻辑顺序是通过链表中的指针链接的次序实现 的。线性表的链式存储结构中只有一个指针域的链表称为单链表。可按如下格式定义单链表的结点结构：typedef struct node datatype data; /*结点数据域*/struct node *next; /*结点指针域*/ 模块划分：（1）initiate( )函数：初始化单链表（2）append( )函数：建立单链表（3）insert( )函

12、数：插入结点（4）delete( )函数：删除结点（5）search( )函数：查找结点（6）print( )函数：显示输出 四、参考源程序四、参考源程序 #include #include #include typedef int datatype; typedef struct node datatype data; struct node *next; slnode; int l; /*保存查找到的结点位置*/ int initiate (slnode *h ); int append(slnode *h); int insert(slnode *h, int n); int delet

13、et(slnode *h, int n); slnode * search(slnode *h, datatype x); void print(slnode *h); void main() slnode *h,*s; int sel,n,x; /* sel 选择输入， n 插入或删除结点的个数，x 要查找计算机软件基础实验指导书7的结点数据*/initiate ( printf(“请输入你的选择: 1-initiate 2-append 3-insert 4-delete 5- search 6-print 7-exitnyour choice =“); scanf(“%d“, while

14、(sel!=7) if(sel=1) initiate ( else if(sel=2) append(h);print(h); else if(sel=3) printf(“请输入待插入的结点个数:“);scanf(“%d“, insert(h,n);print(h); else if(sel=4) printf(“请输入待删除的结点个数:“); scanf(“%d“, deletet(h,n); print(h); else if(sel=5) printf(“请输入要查找的结点数据:“); scanf(“%d“, s=search(h,x); if(s!=NULL) printf(“查找成功，结点位置为：%dn“,l); else if(sel=6) print(h); else printf(“你的选择是错误的!n “); printf(“请输入你的选择: 1-initiate 2-append 3-insert 4-delete 5- search 6-print 7-exit nyour choice =“