新软件基础实验指导.doc

计算机软件基础实验指导书计算机软件基础实验指导书 C语言实现冷朝霞 杨媛 杨文宇 白华煜 孙旭霞西安理工大学自动化与信息工程学院二00八年六月目 录实验报告要求 . . 1实验一 顺序表的基本操作.2实验二 单链表的基本操作.5实验三 堆栈的基本操作.10实验四 循环队列的基本操作 .14实验五 稀疏矩阵的转置.18实验六 二叉排序树的建立与遍历.22实验七 直接插入排序.24实验八 直接选择排序.26实验九 顺序查找和折半查找.28实验十 二叉排序树查找.32实验报告要求一、 实验目的二、 实验内容三、 程序流程图四、 实验结果（要求检测所有情况的正确性，写出测试条件及相应的测试结果）五、 完成思考题实验一 顺序表的基本操作(2学时)一、实验目的了解顺序表的逻辑特征，掌握顺序表的描述方法、特点及有关的概念，掌握顺序表上的插入和删除等基本操作算法。二、实验内容在顺序表List 中，实现顺序表的基本操作，包括：初始化顺序表，在表中插入元素、删除元素。基本要求：（1） 顺序表的元素个数可随意设定；（2） 可连续测试任意多个元素的插入、删除，（插入、删除位置及要插入元素数值均从键盘输入）；（3） 任一操作结束后将顺序表中的内容输出；（4） 可由用户选择退出程序。三、实验要点及说明顺序表又称为线性表的顺序存储结构，它是用一组地址连续的存储单元依次存放线性表的各个元素。 可按如下格式定义顺序表： #define MAXLEN 50 /* 定义顺序表最大元素个数50 */typedef int datatype; typedef structdatatype ListMAXLEN; /* 定义顺序表List */ int Num; /* 定义顺序表表长（1MAXLEN）*/Seqlist;模块划分：（1）initiq(Seqlist *la )函数：初始化顺序表 （2）insertq( )函数：实现插入功能 （3）deleteq( )函数：实现删除功能 （4）print( )函数：实现输出功能四、参考源程序#include #define MAXLEN 50typedef int datatype;typedef struct datatype ListMAXLEN; int Num; Seqlist;void initiq(Seqlist *la );int insertq(Seqlist *la,int n);int deleteq(Seqlist *la,int n);int print(Seqlist *la);void main() Seqlist la;int s,n; /* s 选择输入， n 插入或删除数据的个数*/printf(请输入你的选择: 1-initiate 2-insert 3-delete 4-print 5-exitnyour choice =);scanf(%d,&s);while(s!=5) if(s=1) initiq( &la );printf(完成初始化 !n); else if(s=2) printf(请输入待插入的数据个数:);scanf(%d,&n); insertq(&la,n);print(&la); else if(s=3) printf(请输入待删除的数据个数:);scanf(%d,&n);deleteq(&la,n);print(&la); else if(s=4) print(&la); else printf(你的选择是错误的!n );printf(请输入你的选择: 1-initiate 2-insert 3-delete 4-print 5-exitnyour choice =);scanf(%d,&s); /*初始化*/void initiq(Seqlist *la ) la- Num=0; /*插入*/int insertq(Seqlist *la,int n) int i,j; /* i 插入位置， j 顺序表下标 */datatype x; /* x 插入数据 */while(n) if (la-Num=MAXLEN-1) printf (n 表满，不能插入！插入未完成，还有%d个数据未插入n,n);return 0; printf(请输入插入的位置和数据:);scanf(%d%d,&i,&x);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-; printf(插入完成n);return 1; /*删除*/int deleteq(Seqlist *la,int n) int i,j; /* i 删除位置， j 顺序表下标 */while(n) if (la-Num=0) printf (n 表空，不能删除！n);return 0; printf(请输入删除的位置:);scanf(%d,&i);if (i=la-Num) printf (n 删除位置错误!n); else for ( j=i+1; jNum; j+)la-Listj-1=la-Listj;la-Num-;n-; printf(删除完成！n);return 1; /*显示输出*/int print (Seqlist *la) int m;if (la-Num=0) printf(顺序表为空!n);return 0; else printf(当前的顺序表为:n);for(m=0;mNum;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如何用程序实现将两个不同的顺序表复制到一个顺序表中？实验二 单链表的基本操作（2学时）一、实验目的了解链表的逻辑结构特征，掌握链表的描述方法、特点及有关概念，掌握链表的建立、插入、删除以及查找的基本操作算法。二、实验内容实现单链表的基本操作，包括：建立单链表，插入结点，删除结点，查找结点，打印输出单链表中的所有结点。基本要求：（1）单链表的结点个数可随意设定；（2）可连续测试任意多个结点的插入、删除，（插入位置、插入结点的数据及被删除结点的数据要从键盘输入）； （3）根据键盘输入的数据在单链表中查找结点；（4）任一操作结束后将单链表中的内容输出；（5）可由用户选择退出程序。三、实验要点及说明线性表的链式存储结构是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接的次序实现的。线性表的链式存储结构中只有一个指针域的链表称为单链表。 可按如下格式定义单链表的结点结构： typedef struct node datatype data; /*结点数据域*/ struct node *next; /*结点指针域*/ 模块划分：（1）initiate( )函数：初始化单链表 （2）append( )函数：建立单链表 （3）insert( )函数：插入结点 （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 deletet(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 要查找的结点数据*/ initiate ( &h );printf(请输入你的选择: 1-initiate 2-append 3-insert 4-delete 5- search 6-print 7-exitnyour choice =);scanf(%d,&sel);while(sel!=7) if(sel=1) initiate ( &h ); else if(sel=2) append(h); print(h); else if(sel=3) printf(请输入待插入的结点个数:); scanf(%d,&n); insert(h,n); print(h); else if(sel=4) printf(请输入待删除的结点个数:);scanf(%d,&n);deletet(h,n);print(h); else if(sel=5) printf(请输入要查找的结点数据:);scanf(%d,&x);s=search(h,x);if(s!=NULL)printf(查找成功，结点位置为：%dn,l); else if(sel=6) print(h); elseprintf(你的选择是错误的!n );printf(请输入你的选择: 1-initiate 2-append 3-insert 4-delete 5- search 6-print 7-exit nyour choice =);scanf(%d,&sel); /*初始化*/int initiate (slnode *h) *h=( slnode * )malloc(sizeof(slnode);if (*h=NULL) printf(初始化失败！n);return 0; (*h)-next=NULL;printf(完成初始化 !n);return 1; /*建立单链表*/int append (slnode *h) slnode *p,*q;int n,i; /* n 单链表中最初的结点数*/datatype a10; /* a 单链表中最初的数据*/if(h=NULL) printf(单链表未初始化！n);return 0; printf(请输入单链表最初的结点数n=);scanf(%d,&n);printf(请输入各个结点数据域的值:);for(i=0;in;i+) scanf(%d,&ai); p=h;for(i=0;idata=ai;q-next=NULL;p-next=q;p=q; return 1; /*插入*/int insert (slnode *h, int n) slnode *p, *q;int i, j; /* i 插入结点的位置*/datatype x; /* x 插入结点的数据*/p=h; j=0;while(n) printf(请输入插入结点的位置及结点数据：);scanf(%d%d,&i,&x);while(p-next!=NULL)&(jnext;j+; if(j!=i-1) printf(n插入位置不合理！n); else if (q=( slnode * )malloc(sizeof(slnode)=NULL) printf(新结点空间申请失败！n);return 0; q-data=x;q-next=p-next;p-next=q;n-; printf(插入完成!n);return 1; /*删除*/int deletet (slnode *h, int n) slnode *p,*s;int m; /*m 保存被删除结点的个数 */datatype x; /* x 被删除结点的数据*/p=h;m=n;while(n) printf(请输入第%d个被删除结点的数据：,m-n+1);scanf(%d,&x);s=search(h,x);if(s=NULL)continue;p=s-next;s-next=p-next;free(p);n-; return 1; /*查找*/slnode * search(slnode *h, datatype x) slnode *p;p=h;l=0;while(p-next!=NULL) l+;if(p-next-data=x)return p;p=p-next; printf(没有要删除的结点数据！n);return NULL; /*显示输出*/void print(slnode *h) slnode *p;int i;p=h-next;i=0;printf(n当前的单链表数据内容为:n);while(p!=NULL) i+;printf(第%d个数据： %d n,i,p-data);p=p-next; printf(n线性表的表长为%dn,i); 五、思考题1. 编写一个算法，删除单链表中值相同的多余结点。2实现单链表的就地逆序，设其头结点指针为head，编写一个算法将单链表逆置，即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。3假设现有一个带头结点的单链表head，试写出将单链表中结点数据值为偶数的结点，复制并放入另一个带头结点的单链表head1的头部的算法。4设现有一个带头结点的单链表（头指针为head），试写出一算法，删除该单链表中数据为奇数的所有结点。5.双向链表的基本操作实验三 堆栈的基本操作（2学时）一、实验目的了解堆栈的顺序逻辑结构特征，掌握堆栈的描述方法、特点及有关概念，掌握堆栈的建立、插入、删除等基本操作算法。二、实验内容实现顺序堆栈的基本操作，包括：初始化堆栈，进栈，出栈，取栈顶元素。基本要求：（1）顺序堆栈的元素个数可随意设定；（2）可连续测试任意多个元素的进栈、出栈操作； （3）可实现取栈顶元素；（4）任一操作结束后将顺序堆栈中的内容输出；（5）可由用户选择退出程序。三、实验要点及说明栈的逻辑结构和线性表相同，但运算规则与线性表相比有了更多的限制，故又称操作受限的线性表。栈是一种只允许在表的一端进行插入或删除操作的线性表。只允许插入，删除操作的一端称为栈顶，另一端称为栈底，栈顶当前位置是由一个栈顶指示器指示；插入操作称为进栈或入栈，删除操作称为出栈或退栈；当栈中没有任何元素时称为空栈。 可按如下格式定义堆栈的顺序存储结构： #define MAX 50 /* 定义顺序堆栈最大元素个数50 */ typedef struct datatype stackMAX; /* 定义顺序堆栈stack */ int top ; /* 定义栈顶指示器*/seqstack;模块划分：（1）initiate( )函数：初始化顺序堆栈 （2）push( )函数：进栈操作 （3）pop( )函数：出栈操作 （4）stacktop( )函数：取栈顶元素 （5）print( )函数：显示输出四、参考源程序#include #include #define MAX 50typedef int datatype;typedef struct datatype stackMAX; int top;seqstack; void initiate(seqstack *s );int push(seqstack *s, int n );int pop(seqstack *s, int n );int stacktop(seqstack *s );void print(seqstack *s );int main() seqstack *s;int sel,n; /* sel 选择输入， n 进栈或出栈数据的个数*/if (s=(seqstack *)malloc(sizeof(seqstack)=NULL) printf(申请空间错误！n);return 0; initiate (s );printf(完成初始化 !n);printf(请输入你的选择: 1-initiate 2- push 3- pop 4- stacktop 5- print 6-exitnyour choice =);scanf(%d,&sel);while(sel!=6) if(sel=1) initiate (s );printf(完成初始化 !n); else if(sel=2) printf(请输入待进栈的数据个数:);scanf(%d,&n); push (s,n);print(s); else if(sel=3) printf(请输入待出栈的数据个数:);scanf(%d,&n);pop (s,n);print(s); else if(sel=4) stacktop (s); print(s); else if(sel=5) print(s); elseprintf(你的选择是错误的!n );printf(请输入你的选择: 1-initiate 2- push 3- pop 4- stacktop 5- print 6-exit nyour choice =);scanf(%d,&sel); return 1; /*初始化*/void initiate (seqstack *s) s-top=-1; /*进栈*/int push(seqstack *s,int n) int i=1;datatype x;while(n) if (s-top=MAX-1) printf(栈满！n还有%d个数据未完成进栈！n,n);return 0; printf(输入第%d个进栈的数据：,i);scanf(%d,&x);s-top+;s-stacks-top=x;i+;n-; return 1; /*出栈*/int pop(seqstack *s,int n) int i=1;datatype x;while(n) if(s-top=-1) printf( 栈空!n要求的出栈数据过多！n);return 0; x=(s-stack(s-top)-);printf(第%d个出栈数据是：%dn,i,x);n-;i+; return 1; /*取栈顶元素*/int stacktop(seqstack *s ) datatype x;if (s-top=-1) printf(栈空！n);return 0; x=(s-stack(s-top);printf(栈顶数据为：%dn,x);return 1; /*显示输出*/void print(seqstack *s ) int i;if (s-top=-1)printf(栈空！n);elsefor(i=0;itop;i+)printf(stack%d为：%dn,i,s-stacki); 五、思考题1. 如果初始化栈指针s-top=0 则进栈的push()函数应如何修改？2如何实现两个顺序栈的共用？3设两个栈（stack1，stack2）共享一个一维数组空间sm，它们的栈底分别设在数组的两端，试编写一算法，从键盘输入一个整数x，该数大于100时放入stack2，否则放入stack1。stack1stack2top1top201m-1sm#define m 10typedef struct stack int sm; int top1; int top2; STACK; STACK *p;实验四 循环队列的基本操作（2学时）一、实验目的了解循环队列的顺序逻辑结构的定义及基本操作，掌握队列的描述方法、特点及有关概念。二、实验内容实现顺序循环队列的基本操作，包括：建立循环队列，元素入对，元素出对等。基本要求：（1）正确判断循环队列对满、对空的情况；（2）可连续测试任意多个元素的入对、出对操作； （3）可实现取对头元素；（4）任一操作结束后将队列中的内容输出；（5）可由用户选择退出程序。三、实验要点及说明队列是一种只允许在表的一端进行插入操作而在另一端进行删除操作的线性表。队列的插入操作通常称为进队或入队，队列的删除操作通常称为退队或出队。表中允许进行插入操作的一端称为队尾，允许进行删除操作的一端称为队头，队头和队尾分别由队头指针q-front和队尾指针q-rear指示。 当队列中没有数据元素时称为空队。解决顺序队列假溢出的方法是采用循环队列，即将队列的首尾相接。当q-rear=q-front时，队列为空；当(q-rear+1)%maxnum=q-front时，队列为满，即牺牲一个数据元素空间作为队满标志。 可按如下格式定义顺序循环队列结构： #define MAX 50 /* 定义顺序循环队列最大元素个数50 */ typedef struct datatype queueMAX; /* 定义顺序循环队列queue */ int front ; /* 定义对头指示器*/ int rear; /*定义对尾指示器*/ sequeue;模块划分：（1）initiate( )函数：初始化顺序循环队列 （2）addqueue ( )函数：入对操作 （3）delqueue ( )函数：出对操作 （4）gettop( )函数：取对头元素 （5）print( )函数：显示输出四、参考源程序#include #include #include #define MAX 50typedef int datatype;typedef struct datatype queueMAX;int front;int rear; sequeue;void initiate(sequeue *s );int addqueue (sequeue *s, int n);int delqueue (sequeue *s, int n );int gettop(sequeue *s );void print(sequeue *s );int main() sequeue *s;int sel,n; /* sel 选择输入， n 进栈或出栈数据的个数*/if (s=( sequeue *)malloc(sizeof(sequeue)=NULL) printf(申请空间错误！n);return 0; initiate(s );printf(完成初始化 !n);printf(n请输入你的选择: 1-initiate 2- addqueue 3- delqueue 4- gettop 5- print 6-exitnyour choice =);scanf(%d,&sel);while(sel!=6) if(sel=1) initiate(s );printf(完成初始化 !n); else if(sel=2) printf(n请输入待入对的数据个数:);scanf(%d,&n); addqueue(s,n);print(s); else if(sel=3) printf(n请输入待出对的数据个数:);scanf(%d,&n);delqueue(s,n);print(s); else if(sel=4) gettop(s);print(s); else if(sel=5) print(s); elseprintf(你的选择是错误的!n );printf(n请输入你的选择: 1-initiate 2- addqueue 3- delqueue 4- gettop 5- print 6-exit nyour choice =);scanf(%d,&sel); return 1; /*初始化*/void initiate (sequeue *s) s-front=0;s-rear=0; /*入对*/int addqueue(sequeue *s,int n) int i=1; /*显示是第几个数据入对*/datatype x; /*待入对的数据*/while(n) if (s-front=(s-rear+1)%MAX) /*判对满条件*/ printf(堆满！n还有%d个元素未完成入对！n,n);return 0; printf(请输入第%d个入对的数据：,i);scanf(%d,&x);s-rear=(s-rear+1)%MAX;s-queues-rear=x;i+;n-; return 1; /*出对*/int delqueue(sequeue *s,int n) int i=1; /*显示是第几个数据出对*/datatype x; /*出对的数据*/while(n) if(s-front=s-rear) /*判对空条件*/ printf(对空!n);return 0; s-front=(s-front+1)%MAX;x= (s-queues-front);printf(第%d个出对的数据为：%dn,i,x);i+;n-; return 1; /*取对头元素*/int gettop(sequeue *s ) datatype x; /*对头元素*/int m;if(s-front=s-rear) /*判对空条件*/ printf(对空!n);return 0; m=(s-front+1)%MAX; /*保证对头指针不变*/x= (s-queuem);printf(对头数据为：%dn,x);return 1; /*显示输出*/void print(sequeue *s) int m;m=s-front; /*下标*/if(s-front=s-rear) /*判对空条件*/ printf(对空!无显示输出!n); else while(m!=s-rear) m=(m+1)%MAX;printf(queue%d数据为： %dn,m,s-queuem); 五、思考题 1除了循环队列，还有哪些方法可以解决顺序队列“假溢出”的问题？2如果循环队列的下标不是从0到n-1，而是从1到n，那么入对、出对操作应如何修改？判断队满的条件又应如何修改？实验五 稀疏矩阵的转置一、实验目的熟悉数组的有关概念，能熟练掌握稀疏矩阵的三元组存储结构的转置方法。二、实验内容用三元组顺序表存储结构存储稀疏矩阵，实现稀疏矩阵的转置运算。基本要求： （1）稀疏矩阵通过键盘输入； （2）建立稀疏矩阵的三元组顺序表； （3）实现稀疏矩阵三元组顺序表的转置； （4）输出转置前后的稀疏矩阵； （5）可由用户选择退出程序。三、实验要点及说明以二维数组的形式从键盘输入稀疏矩阵，由程序完成三元组顺序表、顺序表的转置。原稀疏矩阵三元组顺序表按先行序后列序的次序存放，转置后的稀疏矩阵三元组顺序表仍然按先行序后列序的次序存放。 可按如下格式定义三元组顺序表结构： typedef struct int pi; /*行号*/ int q; /* 列号*/ datatype x; /*元素值*/ List; 三元组顺序表的控制数据结构： typedef struct int md; /*行数*/ int nd; /* 列数*/ int td; /*非零元素个数*/ tabletype;模块划分：（1）input( )函数：输入稀疏矩阵 （2）setup ( )函数：建立三元组顺序表 （3）transition ( )函数：转置 （4）print1( )函数：矩阵输出（5）print2( )函数：三元组顺序表输出四、参考源程序#include #include #define maxsize 50typedef int datatype;typedef struct int p,q; datatype x; List;typedef struct int md,nd,td; tabletype;int n,m; /*稀疏矩阵的行数、列数*/ void input(datatype amaxsizemaxsize );void setup (datatype amaxsizemaxsize, List ta,tabletype *ta1 );void transition (tabletype *ta1, tabletype *tb1, List ta,List tb);void print1(datatype amaxsizemaxsize);void print2(List a,int nn);int main( ) datatype amaxsizemaxsize; /*稀疏矩阵*/List tamaxsize,tbmaxsize; /*三元组顺序表*/tabletype *ta1,*tb1;int sel; /*选择输入*/if (ta1=(tabletype *)malloc(sizeof(tabletype)=NULL) printf(申请空间错误！n);return 0; if (tb1=(tabletype *)malloc(sizeof(tabletype)=NULL) printf(申请空间错误！n);return 0; printf(请输入你的选择：1-开始 其它选择为退出 nyour choice =);scanf(%d,&sel);while(sel=1) input(a);setup(a,ta,ta1);transition(ta1, tb1, ta,tb);printf(n原稀疏矩阵：n);print1(a );printf(n原三元组顺序表：n);print2(ta,ta1-td);printf(n转置后的三元组顺序表：n);print2(tb, tb1-td);printf(请输入你的选择：1-开始 其它选择为退出 nyour choice =);scanf(%d,&sel); return 1; /*输入*/void input(datatype amaxsizemaxsize ) int i,j;printf(n预输入的稀疏矩阵的行数);scanf(%d,&n); printf(n预输入的稀疏矩阵的列数);scanf(%d,&m);for(i=0;in;i+)for(j=0;jtd=0; /*初始化非零元素个数*/for(i=0; in;i+)for(j=0;jtd.p=i;tata1-td.q=j;tata1-td.x=aij;ta1-td+; ta1-md=n;ta1-nd=m; /*转置*/void transition (tabletype *ta1, tablety