陕西高等教育自学考试.doc

《陕西高等教育自学考试.doc》由会员分享，可在线阅读，更多相关《陕西高等教育自学考试.doc（19页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、陕西省高等教育自学考试计算机软件基础课程实践环节考核报告准考证号：010407220039考生姓名：张小飞所在专业：通信工程专业层次：本科考核地点：西安电子科技大学考核时间：2010 年 5 月 16 日考核桌（机）号：同组考核者姓名：实践考核评语及成绩评定（由教师填写）教师签名：年月日主考院校：西安电子科技大学一、实验名称：链表的插入和删除二、目的与要求：线性表是最简单、最常用的一种数据结构。其逻辑结构是数据元素的有序序列：（aa.a）。三、具体题目：#include#includemalloc.h#include#define M 5#define CHA0/插入位置#define del

2、 1/删除位置#define NULL 0void main()/printf(hello word!);typedef struct nodechar data;struct node*link;NODE;NODE*FR5;/数据结构 的定义for(int j=0;jdata=A;FR1-data=B;FR2-data=C;FR3-data=D;FR4-data=E;/向数据区写入字符printf(/n);printf(这是单链表简单实验an);printf(/n);for(int i=0;idata);printf(这是第%d 个元素：%cn,i+1,FRi-data);/显示链表 的元素

3、/NODE*head,*P;P=(NODE*)malloc(sizeof(NODE);head=FR0;for(int s=0;slink=FRs+1;FRM-link=NULL;/建立连接 的 过程/test/printf(this isa test%can,FR0-link-link-data);/插入char X;X=m;if(CHA=0)P-data=X;P-link=head;head=P;printf(第一个插入元素为：%can,head-data);head-link=FRdel+1;free(FRdel);printf(删除 B 显示 下一个元素：%can,head-link-

4、data);for(int f=0;f5;f+)delete(FRi);#include#include#define MAXSIZE 50/*typedef struct/定义排序表的结构int elemwordMAXSIZE;/数据元素关键字int length;/表中当前元素的个数SqList;void InitialSqList(SqList&L,int R,int n)/表初始化int i;L.length=n;for(i=1;i=L.length;i+)L.elemwordi=Ri-1;*/void SelectSort(int R,int n)/选择排序,升序/对记录序列 R0.

5、n-1作简单选择排序int min;int j;for(int i=0;i n;i+)/选择第 i 小的记录，并交换j=i;min=Ri;for(int k=i;k n;k+)/在 Ri.n-1中选择最小的记录if(Rk min)min=Rk;j=k;if(i!=j)/与第 i 个记录交换int temp=Ri;Ri=Rj;Rj=temp;/SelectSortvoid BubbleSort(int R,int n)/冒泡排序,升序/设待排记录放在 R0到 Rn-1中for(int i=0;i n;i+)for(int j=0;j Rj+1)/交换元素,每次寻找最大的让其沉底int temp=

6、Rj+1;Rj+1=Rj;Rj=temp;/BubbleSortvoid BiInsertionSort(int R,int n)/折半插入排序,升序int low,high,temp,m;for(int i=1;i n;i+)temp=Ri;/将 Ri暂存到 templow=0;high=i-1;while(low=high)/在 R0.i-1中折半查找插入位置m=(low+high)/2;/折半if(temp high;j-)Rj+1=Rj;/记录后移Rhigh+1=temp;/插入/for/BInsertSortint SeqSearch(int R,int n,int m)/顺序从前往

7、后查找for(int i=0;i n;i+)if(Ri=m)return i+1;return-1;/找不到则返回-1int BiSearch(int R,int n,int m)/折半查找int low,high,mid;low=0;high=n-1;while(low Rmid)low=mid+1;elsehigh=mid-1;return-1;/找不到则返回-1int Partition(int R,int low,int high)int pivotkey=Rlow;/枢轴while(low high)while(low=pivotkey)/从右向左搜索high-;Rlow=Rhigh

8、;while(low high)&(Rlow=pivotkey)/从左向右搜索low+;Rhigh=Rlow;Rlow=pivotkey;return low;/返回枢轴所在位置/Partitionvoid QSort(int R,int s,int t)/对记录序列 Rs.t进行快速排序if(s t)/长度大于 1int pivotloc=Partition(R,s,t);/对 Rs.t 进行一次划分QSort(R,s,pivotloc-1);/对低子序列递归排序，pivotloc 是枢轴位置QSort(R,pivotloc+1,t);/对高子序列递归排序/QSortvoid HeapAdj

9、ust(int R,int s,int m)/已知 Rs.m中除 Rs之外均满足堆的定义,本函数调整 Rs/使 Rs.m成为一个大顶堆int j,rc;rc=Rs;for(j=2*s;j=m;j*=2)/沿关键字叫大的结点向下筛选if(jm&Rj=Rj)break;/rc 应插入在位置 s 上Rs=Rj;s=j;Rs=rc;/插入void HeapSort(int R,int n)/对顺序表 R 做堆排序int i,t;for(i=n/2;i0;-i)/把 R1.n建成大顶堆HeapAdjust(R,i,n);for(i=n;i1;-i)/大顶堆t=R1;/将堆顶记录和当前未经排序子序列 R1

10、.iR1=Ri;/中的最后一个记录相互交换Ri=t;/此交换将最大元素放在末尾,即取出堆顶元素HeapAdjust(R,1,i-1);/将 R1.i-1重新调整为大顶堆void main()char next=y;int n,i,m2;int*num;int*num2;int*num3;cout请输入元素个数:n;num=new intn;num2=new intn;num3=new intn+1;cout请依次输入每个元素:endl;for(i=0;i numi;cout您输入的元素为:endl;for(i=0;i n;i+)coutnumi;coutendl;for(i=0;i n;i+)

11、num2i=numi;cout选择排序:endl;SelectSort(num2,n);for(i=0;i n;i+)coutnum2i;coutendl;for(i=0;in;i+)num2i=numi;cout冒泡排序:endl;BubbleSort(num2,n);for(i=0;i n;i+)coutnum2i;coutendl;for(i=0;i n;i+)num2i=numi;cout折半插入排序:endl;BiInsertionSort(num2,n);for(i=0;i n;i+)coutnum2i;coutendl;for(i=0;i n;i+)num2i=numi;cout

12、快速排序:endl;QSort(num2,0,n-1);for(i=0;i n;i+)coutnum2i;coutendl;for(i=0;i n;i+)num3i+1=numi;cout堆排序:endl;HeapSort(num3,n);for(i=0;i n;i+)coutnum3i+1;coutendl;cout您输入的元素为:endl;for(i=0;i n;i+)coutnumi;coutendl;while(next!=n)cout请输入要查找的元素:m2;cout 顺 序 查 找(原 始 序 列):endlSeqSearch(num,n,m2)endl;cout顺序查找(排序序列):endlSeqSearch(num2,n,m2)endl;cout 折 半 查 找(排 序 序 列):endlBiSearch(num2,n,m2)endl;cout继续?(y/n):next;cout任意键退出endl;getch();