福州大学至诚学院算法与数据结构实验报告

至诚学院实验报告题目�2009-1010学年下学期算法与数据结构上机试验报告姓名�***学号�******系别�计算机工程系专业�计算机科学与技术年级�09级2010年12月29日实验报告�1�题目�顺序表的逆置【问题描述】将顺序表中的元素逆置�即将线性表�a1,a2,„,am�改变成�am,am-1,„,a1�。【编程任务】试设计一个算法�要求使用尽可能少的辅助空间将顺序表的元素逆置。【数据输入】由文件input.txt给出输入数据。第一行有一个数n�n0�,表示存储于线性表中的元素总个数�后续的n行中�每行只有一个整数�依次表示顺序表中的元素。【结果输出】将逆置后的线性表输出到output.txt中�输出文件的第一行为数n,表示线性表的元素总个数�后续的n行依次是逆置后的顺序表元素。输入文件示例输出文件示例5527812-4-412872【算法描述】1、设计思路�本逆置算法主要是通过循环将顺序表中的元素进行首尾互换�从而达到逆置的需要。并且满足利用尽可能少的辅助空间这一条件。2、数据结构�为实现上述算法�利用了顺序表这一数据结构。C语言描述如下�#defineLIST_INIT_SIZE100//线性表存储空间的初始分配量#defineLISTINCREMENT10//线性表存储空间的分配增量typedefstruct//定义顺序表{int*elem;//存储空间基地址intlength;//当前长度intlistsize;//当前分配的存储容量�以sizeof(int)为单位�}SqList;【核心代码】voidInitList_Sq(SqList*L)//初始化顺序表{L-elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int));L-length=0;L-listsize=LIST_INIT_SIZE;}voidListli_sq(SqList*L)//逆置函数{inti,temp;for(i=0;iL-length/2;i++){temp=L-elem[i];L-elem[i]=L-elem[L-length-i-1];L-elem[L-length-i-1]=temp;}}实验报告�2�题目�杨辉三角【问题描述】杨辉三角是一个有数字排列成的三角形数表�一般形式如下�111121133114641„„„„„„„„„„„„„„„„„„„杨辉三角最本质的特征是�它的两条斜边都是由数字1组成的�而其余的数则是等于它肩上的两个数之和。【编程任务】(1)编写一个打印输出杨辉三角�又称二项式系数表�前n(n0)行的程序。(2)要求借鉴第三章课件中给出的编程思路�采用循环队列完成。【数据输入】由文件input.txt给出输入数据给出打印的行数n。【结果输出】文件output.txt中输出如“问题描述”部分给出的三角形数表。输入文件示例输出文件示例5111121133114641【算法描述】1、设计思路�由于杨辉三角的形状特征�它的两条斜边都是由数字1组成的�而其余的数则是等于它肩上的两个数之和。本算法主要是运用循环队列来输出三角形的杨辉三角。在循环队列中依次存放第i-1行上的元素�然后逐个出队打印�同时生成第i行元素并入队。2、数据结构�本算法运用的数据结构是队列。C语言描述如下�#defineMAXSIZE20//最大队列长度typedefstruct{int*base;//初始化的动态分配存储空间intfront;//头指针�若队列不空�指向队列头元素intrear;//尾指针�若队列不空�指向队列尾元素的下一个位置}SqQueue;//定义队列【核心代码】boolInitQueue(SqQueue&Q)//初始化队{Q.base=(int*)malloc(MAXSIZE*sizeof(int));if(!Q.base){printf(OVERFLOW\n);//存储分配失败returnfalse;}Q.front=0;Q.rear=0;returntrue;}boolQueueEmpty(SqQueueQ)//判断队是否空{if(Q.front==Q.rear)returntrue;elsereturnfalse;}intGetHead(SqQueueQ,int&e)//取队头元素{if(QueueEmpty(Q))return-1;else{e=Q.base[Q.front];return0;}}intQueueLength(SqQueueQ)//求队列长度{return(Q.rear-Q.front+MAXSIZE)%MAXSIZE;}boolEnQueue(SqQueue&Q,inte)//入队{if(Q.front==(Q.rear+1)%MAXSIZE){printf(Queuefull\n);returnfalse;}Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXSIZE;returntrue;}boolDeQueue(SqQueue&Q,int&e)//出队{if(Q.front==Q.rear){printf(Queueempty\n);returnfalse;}e=Q.base[Q.front];Q.front=(Q.front+1)%MAXSIZE;returntrue;}实验报告�3�题目�Josephus排列问题【问题描述】Josephus排列问题定义如下�假设n个竞赛者排列成一个环形。给定一个正整数m,从某个指定的第一个人开始�沿环计数�每遇到第m个人就让其出列�且计数继续进行下去。这个过程一直进行下去直到所有人都出列为止。最后出列者为优胜者。每个人出列的次序定义了整数1、2、„,n的一个排列。这个排列称为一个�n,m�Josephus排列。例如��7,3�Josephus排列为3,6,2,7,5,1,4。【编程任务】设计一个求�n,m�Josephus排列的算法。【数据输入】由文件input.txt给出输入数据。第一行有2个正整数n和m�分别表示有n个人�沿环计数每遇到第m个人出列。接下来的n行是按照顺序1,2�„,n排列的n个人的名字。【结果输出】将计算出的编程任务的结果输出到文件output.txt。文件的第1行是计算得到的编程任务中的优胜者名字。输入文件示例输出文件示例73JohnZhengqiangWangwuWangjinglingJohnFangweiZhangkaiSunping【算法描述】1、设计思路�根据Josephus排列的特征�本算法主要运用环形的单向链表处理。2、数据结构�根据本算法的需要�采用了环形单向链表这一数据结构。C语言描述如下�typedefstructJosephus//定义环形单向链表{char*date;//节点的数据域structJosephus*next;//指向下一个几点的指针}Josephus;【核心代码】Josephus*Josephus_create(inttotal)//构造环形单向链表{//先构造构造单向链表FILE*fp;intm;Josephus*head,*tail,*p;if((fp=fopen(input.txt,r))==NULL)//打开输入文件{printf(erroronopen!\n);exit(1);}fscanf(fp,%d,&total);fscanf(fp,%d,&m);head=tail=NULL;charck=fgetc(fp);//除去回车换行符for(inti=1;i=total;i++){p=(Josephus*)malloc(sizeof(Josephus));//为P创建空间p-date=(char*)malloc(MAX*sizeof(char));//为date创建一个含有MAX大的空间p-next=NULL;charch=fgetc(fp);intn=0;while(!feof(fp)&&ch!='\n'&&nMAX-1){p-date[n]=ch;ch=fgetc(fp);n++;}if(n==MAX-1){printf(名字的第%d个的长度超过了MAX,退出\n,i);free(head);exit(0);}p-date[n]='\0';//一个名字输入结束if(head==NULL)tail=head=p;else{tail-next=p;tail=p;}}tail-next=head;//tail接到head去fclose(fp);returnhead;}//Josephus循环取数q=p;m=m%total;printf(先后淘汰的顺序如下:\n);while(q!=q-next)//只要链表不只一个数就一直循环{for(inti=1;im-1;i++)//取到第m-1个节点q=q-next;p=q-next;//临时节点printf(%s\n,q-next-date);//输出第m个节点的值q-next=q-next-next;q=q-next;//从链表中删除第m个节点free(p);//释放临时空间}实验报告�4�题目�排序【问题描述】对给定的无序线性表�采用非递归的归并算法�将其元素按照从大到小的顺序进行排序�斌输出排序后的元素序列。【编程任务】对给定的无序线性表�采用自底向上的非递归归并排序算法进行排序�输出排序后的正序序列。【数据输入】由文件input.txt给出输入数据。第一行有1个正整数n�表示给定的线性表有n个元素。接下来的n行中�每行有一个正整数�分别表示待排序的数据元素。【结果输出】将排序结果输出到文件output.txt。共n行�每行都是一个正整数�按行扫描�正好构成排序后的正序序列。输入文件示例输出文件示例5-10034224734-10047227878【算法描述】1、设计思路�本算法采用自底向上的合并排序算法来消除递归�提高效率。第i趟排序将序列的n/2i-1取下界个长度为2i-1的有序子序列�依次两两合并为n/2i取下界个长度为2i的有序子序列。2、数据结构�本算法主要运用了数组这一数据结构。C语言描述如下�#defineMAX-ARRAY-DIM8//假设数组维数的最大值为8typedefstruct{int*base;//数组元素基址intdim;//数组维数int*bounds;//数组维界基址int*constants;//数组映象函数常量基址}Array�【核心代码】voidMerge(int*data,inta,intb,intlength,intn)//把a从b到length个数组进行从小到//大排序{intlen;if(b+length-1=n-1)len=n-b;//数组是最后一组的情况elselen=length;int*temp=newint[length+len];//创建新的数组temp保存合并后的数组inti=0;intj=0;while(i=length-1&&j=len-1){if(data[a+i]=data[b+j])//对相邻的两对数组进行合并{temp[i+j]=data[a+i];i++;}else{temp[i+j]=data[b+j];j++;}}if(j==len){//B可能是最后一组�则a[i]还有未比较memcpy(data+a+i+j,data+a+i,(length-i)*sizeof(int));}//void*memcpy(void*dest,constvoid*src,size_tn)字符串拷贝src源字符串�n//拷贝的最大长度dest目的字符串memcpy(data+a,temp,(i+j)*sizeof(int));}voidSort(int*data,intn)//划分个数然后调用Merge排序{intstep=1;while(stepn){for(inti=0;in-step;i+=2*step)Merge(data,i,i+s