课程设计报告 房屋建筑学课程设计报告

      试验一 约瑟夫问题　

      一、实验目的

      1、 熟悉Ｃ或VC++语言上机环境。

      2、 熟悉单循环链表的一些基本操作和应用。

      3、 加深单循环链表的理解，逐步培养解决实际问题的编程能力。

      二、实验要求

      利用单向循环链表存储结构模拟此过程，按照出列的顺序输出个人的编号。

      三，设计思路

      采用单循环链表，先构造一个有n个节点的单循环

      链表，再给出一个报数的上限值m(假设m>1)，在链表的首节点开始从1计数，计到m是时，对应的节点从链表中删除，然后再被删除节点的下一个节点又从1开始计数，直到最后一个节点从链表中删除算法结束。

          单循环链表中节点的结构如下：

          typedef  struct

      { int num;

      Int sipher;

      Struct node *next;

      }linklist;

          该问题有两部分组成，分别由一下算法完成：

      算法一：建立一个由头指针head指示的有n个节点的约瑟夫单循环链表creat.

      算法二：寻找、输出和删除head所指的单循环链表的第m个节点select。该算法有以下具体步骤组成：

      1、 在head中的第一个节点起循环计数找第m个节点；

      2、 输出该节点的num值，把该节点的cipher(密码)值赋给m；

      3、 删除该节点；

      4、 转去1，知道所有节点被删除为止。

      四、程序代码#include<stdio.h>

      #include<stdio.h>

      #define size 100                    /* 输入人数的上限 */

      void main()

      {

       int person[size];

       int i, j;                        /* 循环修正变量 */

       int arrayLen;                    /* 数组长度 */

       int start, overNum;              /* 开始位置各跨过位置 */

       int deleNum;                    /* 出列人所在数组中的下标 */

       int name, total;                /* 输入时,人的信息以及人的总数 */

       printf( "请输入圆桌的总人数 " );

       scanf( "%d", &arrayLen );

       printf( "\n" );

       if( ( arrayLen > size ) || ( arrayLen < 0 ) )

       {

        printf( "超出范围，请重新输入：" );

        scanf( "%d", &arrayLen );

        printf( "\n" );

       };

       printf( "请输入各个人的信息(整数): \n" );

       for( i = 0; i < arrayLen; i++ )

       {

        scanf( "%d", &name );

        person[i] = name;

       }

       printf( "你输入的数据的顺序为: \n" );

       for( i = 0; i < arrayLen - 1; i++ )

        printf( " %d ==>", person[i] );

       printf( "%d \n", person[arrayLen - 1] );

      printf( "你打算从第几个人开始? 请输入开始号: " );

       scanf( "%d", &start );

       printf( "\n" );

       start = start - 1;

       printf( "请输入相邻两出列人之间的间隔: " );

       scanf( "%d", &overNum );

       printf( "\n" );

       total = arrayLen;

       printf( "程序运行后,出列人的顺序为:\n" );

       for( i = 0; i < total; i++ )                    /* 要打印tota

      l个人的情况,故做total次 */

       {

        if ( arrayLen == 1 )

        printf( "%d", person[0] );                    /* 如果是数组只剩一个元素,直接出列 */

        else

        {

        deleNum = ( start + overNum - 1 ) % arrayLen; /* 此取模保证循环 */

        printf( "%d ==> ", person[deleNum] );

        for ( j = deleNum; j < arrayLen; j++ )        /* 将出列元素后面的各元素前移 */

          person[j] = person[j+1];

        start = deleNum;

        arrayLen = arrayLen - 1;                      /* 移动完毕后,数组长度减1 */

        }

       }

       printf( "\n\n" );

      }

      五、运行结果 

      实验二分布计数排序算法的设计

      一、实验目的

      1熟悉Ｃ或VC++语言上机环境。

      2熟悉分布计数排序算法的一些基本操作和应用

      3加深分布计数排序算法的理解，逐步培养解决实际问题的编程能力。

      二、实验要求

      （1）用C语言实现，要求运行时间尽可能少。

      （2）分析该算法的比较次数和使用的辅助空间数。

      三，设计思路

      1 计数排序：(采用非递减排序)设有n个关键字不同的记录，对每个记录R[i]，求出在其它n-1个记录中，小于该记录关键字的记录个数c，则c+1就是排序后该记录的位置。 

      2 分布计数排序：这是当关键字的取值范围比较小，并且重复的关键字较多时的一种排序方法。

      3（1）计数排序分析：设在R[0...n-1]中有n个关

      键字不同的记录。数组count[i]存放小于R[i]的记录个数。 对于0 ≤ j < i ≤ n-1 , 比较R[j].key 和R[i].key,  若R[j].key < R[i].key, 则count[i] +1, 否则count[j] +1； 算法结束时,  count[i] 就是R[i]应处的位置。

      （2）算法： ①[清count]  把count[0]至count[n-1]都置0 。

          ②[对i进行循环]  对i = n-1，n-2，……，1，执行第3步。

          ③[对j进行循环]  对j = i-1, i-2，……，0，执行第4步。

          ④ [比较R[j].key和R[i].key]  若 R[j].key < R[i].key,  则count[i] +1, 否则count[j] +1。

          ⑤ [复制] 对i=0, ……，n-1, 把R[i]写到S[ count[i] ] 中。

      4（1）分布计数排序法分析：设关键字的取值范围u≤R[i]≤v，并且（v-u）很小。这些假定看起来十分苛刻，但事实上这一思想有不少应用。例如，若把这个算法应用于关键字的头几位数字，而不是整个关键字，则这个文件被部分的排序，完成这项任务是相当简单的。

      （2）算法: ①.[清count] 把count[u]到count[v]清为0。

        ②.[求关键字的重复数] 对i=1,2,…,n, 执行: count[R[i]]+ 1。

        ③.[累加] (此时count[i]的值是关键字i的个数) 对i=u+1,u+2,……,v,

              执行 count[i] = count[i] + count[i-1]。

                    ④.[输出](此时的count[i]是小于或等于i的关键字的个数,特别地count[v]=n)

              对j=n,n-1,…,1, 执行: S[count[R[j]]]=R[j]和count[R[j]]-1。

      四 算法的C语言描述如下：

      1计数排序

      Typedef struct rectype

      { Keytype key;

      datatype otherinfo;

      }rectype;

      void countsort1(rectype R[], int n)

       {  int count[n];

       for ( i =0;  i<=n-1;  i++)  count[i] =0;

          for ( i = n-1;  i>=1;  i--)

            for ( j = i-1;  j>=0;  j--)

              if  R[j].key < R [i].key  count[i] ++；

      else    count[j] ++；

       for ( i =0;  i<=n-1;  i++) 

      S[count[i]]=R[i];

      }

       说明：

      由算法可以看出, 对于n个元素, 比较次数为： (n-1)+(n-2)+…..+1= n(n-1)/2, 另外，还需要2n个辅助单元, 当n很大时, 这不是一个有效的算法。

      在上述讨论中, 我们假设关键字互不相同， 若允许存在相同关键字的记录时,该算法也能正确工作，并且是稳定的。若允许存在相同关键字的记录，且在第4步中，把“R[j].key < R [i].key”改成“R[j].key <= R [i].key”，仍能正确工作，但是不稳定了。

      2分布计数排序

      程序为了符合程序设计的习惯, 把count[]定义成

      从count[1]到count[v-u+1].

       程序如下:

      void countsort2(int R[],n,u,v)

      {    int m=v-u+1;

      For(i=1; i<=m; i++)          /*置初值*/

      count[i]=0;

      For(i=1; i<=n; i++)          /*求各键的重复次数*/

      count[R[i]-u+1]++;

      For(i=2; i<=m; i++)          /*累加*/

      count[i]= count[i]+count[i-1]; 

      For(j=n; j>=1; j--)          /*输出*/

       {

      i=R[j]-u+1;

      S[count[i]]=R[j];

      count[i]--;

       }；

      }

      说明：

      可以看出，该算法的运算是比较快的，执行语句的次数约为4n+2m，因为n>>m，故近似为4n，即时间复杂度为O（n）；另外需两个数组count[m]和输出区S[n]，所以其空间复杂度为O（n）。

      该算法是稳定的

      在算法的第4步中,若把“j=n,n-1,…,1”改成“j=1,2,…

      ,n”,算法能正常工作，但是是不稳定的。