软件技术基础实验指导及报告.doc

太原理工大学现代科技学院软件技术基础课程 实验报告 专业班级 通信14-1 学 号 2014101596 姓 名 王晓振 指导教师 范俊杰 软件技术基础实验指导及报告实验说明：1、 共5次实验，每次实验完成1个内容。2、 实验报告命名统一为：软件_专业班级_学号_姓名3、自备U盘，在实验前认真阅读实验要求，在实验中及时记录保存实验结果和调试过程，并填写到实验报告对应位置，实验结束后将该实验报告电子版在指定时间内提交给各班学习委员。实验一 顺序线性表的插入与删除1、实验目的：理解和掌握线性表的顺序存储结构，使用C语言根据相应算法编写程序，实现线性表的创建、插入和删除。2、 实验内容：编写C程序实现先建立一个长度不小于n = 8的线性表，输出原始线性表；然后进行插入运算，在第3个元素前面插入一个新元素b（值为学号后3位），得到一个长度为（n+1）的线性表，输出插入后的线性表；最后进行删除运算，删除第5个元素，得到长度为n的线性表，输出删除后的线性表。3、参考程序：#include #define MAXSIZE 20typedef structint dataMAXSIZE;int last;List;void Init(List *pt)int i = 0;for(i=1;idatai = i;pt-last = i;void Output(List *pt)int i,max=pt-last;printf(List have %d: n,pt-last);for(i=1;idatai);printf(n);void InsertL(List *pt, int i, int x)int k;if(iMAXSIZE-1)printf(插入位置不合适！n);else if(pt-last=MAXSIZE-1) printf(线性表已满！n);elsefor (k=pt-last;k=i;k-) pt-datak+1=pt-datak;pt-datai=x;pt-last+;void Insert(List *pt) int position,x;printf(please input insert position and value:);scanf(%d,%d,&position,&x);InsertL(pt, position, x);void DeleteL(List *pt, int i) int k;if(ipt-last)printf(删除位置不合适！n);elsefor(k=i+1;klast;k+)pt-datak-1=pt-datak;pt-last-;void Delete(List *pt) int position;printf(please input delete position:);scanf(%d,&position);DeleteL(pt, position);int main()int int_Insert,int_Delete;List L,*pt;pt = &L;Init(pt);Output(pt); Insert(pt); Output(pt);Delete(pt);Output(pt);return 0;4、实验结果：将程序运行结果截屏粘贴至此处。5、实验总结：（自行改进程序请粘贴至此处）elsefor (k=pt-last;k=3;k-) pt-datak+1=pt-datak;pt-data3=596;pt-last+;void Insert(List *pt) int position,x;printf(please input insert position and value:);scanf(%d,%d,&position,&x);InsertL(pt, position, x);void DeleteL(List *pt, int i) int k;i=6;if(ipt-last)printf(删除位置不合适！n);6、其他（自行设计程序请粘贴至此处）实验二 顺序栈及其操作1、实验目的：理解和掌握栈数据结构及其顺序存储结构，使用C语言实现栈的相关操作：建立、入栈、退栈和读栈顶元素。2、实验内容：编写C程序实现先建立一个容量不小于5的栈；然后将序列L（L长度为5，起始数为学号后3位，之后每个数加1）中元素依次入栈；最后进行退栈操作，同时读出栈顶元素并输出，直到栈为空。3、参考程序：#include #define maxlen 5int elementmaxlen;int top;int push( int element, int max, int *top, int x ) if ( *top = max ) printf(Stack-overflown); return -1; *top = *top + 1; element*top-1 = x; /元素x入栈，只影响top指针 return 0;int pop( int element, int *top, int *x ) if (*top = 0) printf(Stack-underflown); return -1; *x = element*top-1;/x为退栈元素的值 *top = *top - 1; return 0;int Readtop(int element, int top, int *x) if ( top = 0 ) printf(Stack-underflown); return -1; *x = elementtop-1; return 0;void CreateStack() top = 0;int main()int r,b,x; /CreateStack(); /while(1)printf(Push:please input push element value:);scanf(%d,&b);r = push(element,maxlen,&top,b);if(r = 0)printf(push Successn);elseprintf(push Failn);break;/while(1)printf(Read and Pop:n);r = Readtop(element, top, &x);if(r = 0)printf(%dn,x);elsebreak;r = pop(element,&top,&x);return 0;4、实验结果：将程序运行结果截屏粘贴至此处。5、实验总结：（自行改进程序请粘贴至此处） 由于栈中元素的插入和删除只能在表的同一端即栈顶进行，所以总是后进栈的元素先出来，即栈的后进先出特性，其运算效率相对较高。6、其他（自行设计程序请粘贴至此处）实验三 线性链表的插入与删除1、 实验目的：理解和掌握线性表的链式存储结构，使用C语言根据相应算法编写程序，实现线性链表的创建、插入和删除。2、 实验内容：编写C程序实现先建立一个长度不小于n = 6的线性表，输出原始线性表；然后进行插入运算，在第3个元素前面插入一个新元素b（值为学号后3位），得到一个长度为（n+1）的线性表，输出插入后的线性表；最后进行删除运算，删除第5个元素，得到长度为n的线性表，输出删除后的线性表。3、参考程序：#include #include typedef struct nodeint data;struct node *next; LinkList;LinkList* create() LinkList *head,*p,*q=NULL;int x; head=(LinkList *)malloc(sizeof(LinkList);head-next=NULL;printf(请输入结点值，结束输入-1 n结点值为:n);q=head;scanf(%d,&x);if(x=-1)return head;while(x!=-1) p=(LinkList *)malloc(sizeof(LinkList);p-data=x;q-next=p; q=p;scanf(%d,&x); q-next=NULL;return head;void output(LinkList *head) int i = 0; LinkList *p = head-next;printf(链表元素为：n);while(p != NULL)printf(%d ,p-data);p = p-next;printf(n);void Insert(LinkList *head, int i, int x)LinkList *p,*s; int j=0;p = head;while(p!=NULL) & (jnext;j+;if(p=NULL) | (ji-1)printf(i值不合法 n);elses = (LinkList*)malloc(sizeof(LinkList);s-data = x;s-next = p-next;p-next = s;void Delete(LinkList *head, int i)LinkList *p, *s;int j = 0;p = head;while(p-next!=NULL) & (jnext;j+;if(p-next=NULL) | (ji-1)printf(i值不合法 n);elses = p-next;p-next = s-next; printf(删除元素 %d n,s-data); free(s);/*主函数*/void main()int x=0,i=0;LinkList *head;printf(建立链表n);head=create();output(head);printf(n输入在链表中插入数据的值x:n);scanf(%d,&x);printf(n输入要插入数据的位置i:n);scanf(%d,&i);Insert(head,i,x);output(head);printf(n输入在链表中删除数据的位置i：n);scanf(%d,&i);Delete(head,i);output(head);4、实验结果：将程序运行结果截屏粘贴至此处。5、实验总结：（自行改进程序请粘贴至此处）在线性链表中插入或删除元素时，不需要移动元素，只要找到制定删除节点的钱趋结点，然后改变链接，即只要将待插入或删除结点的指针域内容赋予前趋结点的指针域即可，但为了找到表中第i-1个元素，仍需从表头开始顺链查找。6、其他（自行设计程序请粘贴至此处）实验四 有序表的对分查找1、 实验目的：理解和掌握对分查找的算法及适用条件，并使用C语言实现对分查找。2、实验内容：编写C程序实现有序表的对分查找算法，要求在顺序存储的长度为n=10的有序线性表中实现对分查找，即查找元素值为x的位置序号k，并能正确输出查找结果，若查找的元素存在，则输出其在线性表中的位置，若不存在，在输出不存在的提示信息。 3、参考程序：#include #define N 10void arrayprint(int array, int n)int i;for(i=0;in;i+)printf(%d ,arrayi);printf(n);int Search (int v, int n, int x ) int i, j, k; i = 1; j = n; while (ix ) j = k - 1; /取前半部分 else i = k + 1; /取后半部分return (-1); /找不到返回int main()int searcharrayN;int i,x,position;for(i=0;i=0 & position=N-1)printf(position of value %d is %dn,x,position+1);elseprintf(value %d is not heren,x);return 0;4、实验结果：将程序运行结果截屏粘贴至此处。（查找成功和查找失败两种情况都要求有）5、实验总结：（自行改进程序请粘贴至此处）6、其他（自行设计程序请粘贴至此处）实验五 顺序线性表简单选择排序1、 实验目的：理解和掌握简单选择排序的算法，并使用C语言实现简单选择排序。2、 实验内容：编写C程序实现简单选择排序算法，要求将顺序存储的长度为n=10的无序线性表用简单选择排序法进行排序，先输出原始的线性表，再输出排序后的有序线性表。3、参考程序：#include #define N 5void arrayprint(int array, int n)int i;for(i=0;in;i+)printf(%d ,arrayi);void sort(int array, int n)int i,j,k,min,temp;for(i=0;in-1;i+)min=arrayi;k=i;for(j=i+1;jn;j+)if(arrayjmin)min = arrayj;k=j;if(i!=k)temp = arrayi;arrayi = arrayk;arrayk = temp;arrayprin