陕西高等教育自学考试

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

2、#define M 5#define CHA 0 /插入位置#define del 1/删除位置 #define NULL 0void main()/printf("hello word!");typedef struct nodechar data;struct node *link;NODE;NODE *FR5;/数据结构 的定义for(int j=0;j<5;j+)FRj=(NODE *)malloc(sizeof(NODE);/*NODE *FR1;NODE *FR2;NODE *FR3;NODE *FR4;*/初始化链表 的定义FR0->data=&#

3、39;A'FR1->data='B'FR2->data='C'FR3->data='D'FR4->data='E'/向数据区写入字符printf("/n");printf(" 这是单链表 简单实验an");printf("/n");for(int i=0;i<5;i+)/printf("%s",FRi->data);printf("这是第 %d 个元素： %cn",i+1,FRi->

4、data);/显示链表 的元素/NODE *head,*P;P=(NODE *)malloc(sizeof(NODE);head=FR0;for(int s=0;s<M-1;s+)FRs->link=FRs+1;FRM->link=NULL;/建立连接 的 过程 /test/printf("this is a test %can",FR0->link->link->data);/插入char X;X='m'if(CHA=0)P->data=X;P->link=head;head=P;printf("第

5、一个插入元素为： %can",head->data);head->link=FRdel+1;free(FRdel);printf("删除B 显示 下一个元素 ： %can",head->link->data);for(int f=0;f<5;f+)delete(FRi);#include <iostream.h>#include <conio.h>#define MAXSIZE 50/*typedef struct /定义排序表的结构int elemwordMAXSIZE; /数据元素关键字int length

6、; /表中当前元素的个数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.n-1作简单选择排序int min;int j;for (int i = 0; i < n; i+) / 选择第i小的记录，并交换j = i;min = Ri;for (int k = i; k < n;

7、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 < n - i - 1; j+) if(Rj > Rj+1)/ 交换元素,每次寻找最大的让其沉底int temp = Rj+1;Rj+1 = Rj;

8、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 < Rm) high = m - 1; / 插入点在低半区else low = m + 1; / 插入点在高半

9、区for (int j = i - 1; j > high; j-)Rj + 1 = Rj; / 记录后移Rhigh + 1 = temp; / 插入/ for/ BInsertSortint SeqSearch (int R, int n, int m)/顺序从前往后查找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

10、<= high)mid = (low + high) / 2;if (Rmid = m)return mid+1;if (m > 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 < high) && (Rhigh >= pivotkey)/ 从右向左搜索high-;Rlow = Rhigh;wh

11、ile (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是枢轴位置QS

12、ort(R, pivotloc + 1, t);/ 对高子序列递归排序/ QSortvoid HeapAdjust(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(j<m&&Rj<Rj+1)+j; /j为关键字较大的记录的下标if(rc>=Rj)break; /rc应插入在位置s上Rs=Rj;s=j;Rs=rc; /插入void HeapSort(int R, int n)/对

13、顺序表R做堆排序int i,t;for(i=n/2;i>0;-i) /把R1.n建成大顶堆HeapAdjust(R,i,n);for(i=n;i>1;-i)/大顶堆t=R1; /将堆顶记录和当前未经排序子序列R1.i R1=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<<"请输入元素个数:

14、"<<endl;cin>>n;num = new intn;num2 = new intn;num3 = new intn + 1;cout<<"请依次输入每个元素:"<<endl;for(i = 0; i < n; i+)cin>>numi;cout<<"您输入的元素为:"<<endl;for(i = 0; i < n; i+)cout<<numi<<" "cout<<endl;for(i =

15、 0; i < n; i+)num2i=numi;cout<<"选择排序:"<<endl;SelectSort(num2, n);for(i = 0; i < n; i+)cout<<num2i<<" "cout<<endl;for(i=0; i<n; i+)num2i=numi;cout<<"冒泡排序:"<<endl;BubbleSort(num2, n);for(i = 0; i < n; i+)cout<<nu

16、m2i<<" "cout<<endl;for(i = 0; i < n; i+)num2i=numi;cout<<"折半插入排序:"<<endl;BiInsertionSort(num2, n);for(i = 0; i < n; i+)cout<<num2i<<" "cout<<endl;for(i = 0; i < n; i+)num2i=numi;cout<<"快速排序:"<<endl

17、;QSort(num2, 0, n-1);for(i = 0; i < n; i+)cout<<num2i<<" "cout<<endl;for(i = 0; i < n; i+)num3i + 1=numi;cout<<"堆排序:"<<endl;HeapSort(num3, n);for(i = 0; i < n; i+)cout<<num3i+1<<" "cout<<endl;cout<<"您输入的元素为:"<<endl;for(i = 0; i < n; i+)cout<<numi<<" "cout<<endl;while(next != 'n')cout<<"请输入要查找的元素:"<<endl;cin>>m2;cout<<"顺序查找(原始序列):"<<endl<<SeqSearch(num, n, m2)<<endl;cout<