[原创]《数据结构》课程设计

主题：[原创]《数据结构》课程设计

weylen [专家分：30] 发布于 2006-06-20 17:32:00

课题1．运动会分数统计
任务：参加运动会有n个学校，学校编号为1……n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1……m，女子m+1……m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m<=20,n<=20）
功能要求：
1)可以输入各个项目的前三名或前五名的成绩；
2)能统计各学校总分，
3)可以按学校编号、学校总分、男女团体总分排序输出；
4)可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。
规定：输入数据形式和范围：20以内的整数（如果做得更好可以输入学校的名称，运动项目的名称）
输出形式：有中文提示，各学校分数为整形
界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。
存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。请在最后的上交资料中指明你用到的存储结构。
测试数据：要求使用（1）全部合法数据；（2）整体非法数据；（3）局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在实验报告中详细报告。
课题2．一元多项式计算
任务：能够按照指数降序排列建立并输出多项式；
能够完成两个多项式的相加、相减，并将结果输入；
在设计报告中报告：存储结构、多项式相加的基本过程的算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法。
课题3．订票系统
任务：通过此系统可以实现如下功能：
录入：
可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）
查询：
可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；
可以输入起飞抵达城市，查询飞机航班情况；
订票：（订票情况可以存在一个数据文件中，结构自己设定）
可以订票，如果该航班已经无票，可以提供相关可选择航班；
退票：可退票，退票后修改相关数据文件；
客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。
修改航班信息：
当航班信息改变可以修改航班数据文件
要求：
根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能；
课题4．文章编辑
功能：输入一页文字，程序可以统计出文字、数字、空格的个数。
静态存储一页文章，每行最多不超过80个字符，共N行；要求（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。
存储结构使用线性表，分别用几个子函数实现相应的功能；
输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。
输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出"全部字母数"、"数字个数"、"空格个数"、"文章总字数"（3）输出删除某一字符串后的文章。
课题5．joseph环
任务：编号是1，2，……,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。
要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。
测试数据：
m的初值为20，n=7 ,7个人的密码依次为3，1，7，2，4，7，4，首先m=6,则正确的输出是什么？
要求：
输入数据：建立输入处理输入数据，输入m的初值，n ，输入每个人的密码，建立单循环链表。
输出形式：建立一个输出函数，将正确的输出序列
课题6．猴子选大王
任务：一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。
要求：
输入数据：输入m,n m,n 为整数，n<m
输出形式：中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号，建立一个函数来实现此功能
课题7．建立二叉树，层序、先序遍历（用递归或非递归的方法都可以）
任务：
要求能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列；分别建立建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数。
课题8．哈夫曼树的建立
任务：建立最优二叉树函数
要求：可以建立函数输入二叉树，并输出其哈夫曼树
在课程设计报告中：存储结构、基本算法（可以使用程序流程图）、输入输出、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法。
课题9．图的建立及输出
任务：建立图的存储结构（图的类型可以是有向图、无向图、有向网、无向网，学生可以任选两种类型），能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。
课题10．各种排序比较
任务：
（1）用程序实现插入法排序、起泡法改进算法排序；
（2）利用插入排序和冒泡法的改进算法,将用户随机输入的一列数按递增的顺序排好。
（3）输入的数据形式为任何一个正整数，大小不限。
（4）输出的形式：数字大小逐个递增的数列?
（5）不同排序算法的比较。

本帖地址： http://bbs.pfan.cn/post/176499.html

回复列表（共4个回复）

沙发

weylen [专家分：30] 发布于 2006-06-23 10:18:00

怎么没人来回复哦

板凳

中国台湾 [专家分：2140] 发布于 2006-06-25 00:55:00

typedef struct bitnode//定义一个2叉数
{
char data;
struct bitnode *lchild ,*rchild;
}bitnode ,*bitree;

int CreatBitree(bitree *T)//建立一个2叉树
{
char ch;

printf("请输入字符:");
scanf("%c",&ch);
    getchar();//吃掉残留的数据
if ( ch ==' ')
{
  (*T)=NULL;
         return 0;
}
else
{
  (*T) = (bitree)malloc(sizeof(bitnode));
        if((*T) == NULL)
  {
   printf("memory allocation failed,goodbye");
   exit(1);
  }
  (*T)->data=ch;
  CreatBitree(&(*T)->lchild);
  CreatBitree(&(*T)->rchild);
}

    return OK;
}

void PreOrderTraverse1(bitree T)// 前序遍历递归形式
{
if(T)
{
        printf("%c",T->data);
        PreOrderTraverse1((*T).lchild);
        PreOrderTraverse1((*T).rchild);
}

}

void PreOrderTraverse2(bitree T)// 前序遍历非递归形式
{
int top = 0;
bitree a[M];


while (T!=NULL||top!=0)
{
  while ( T!=NULL)
  {
      printf("%c",T->data);
   a[++top] = T;
   T = T->lchild;
  }

  if(top > 0)
  {
   T = a[top--];
   T = T->rchild;
  }
}
}

void InOrderTraverse1(bitree T)//中序递归形式访问
{
if(T)

{
        InOrderTraverse1(T->lchild);
  printf("%c",T->data);
  InOrderTraverse1(T->rchild);
}
}

void InOrderTraverse2(bitree T)//中序非递归形式
{
int top = 0;
bitree s[M];

while(T!=NULL||top!=0)
{
  while(T!=NULL)
  {
   s[++top] = T;
   T = T->lchild;
  }

  if (top>0)
  {
   T = s[top--];
   printf("%c",T->data);
   T = T->rchild;
  }
}
}

void BerforOrderTraverse1(bitree T)//后序递归形式
{

    if(T)
{
  BerforOrderTraverse1((*T).lchild);
  BerforOrderTraverse1((*T).rchild);
  printf("%c",T->data);
}
}

void BerforOrderTraverse2(bitree t) //后序非递归形式
{
    typedef struct node
       {
    bitree  t;
       int tag;
       } stack;
      stack s[100] ;
       int top=0;
      while (t!=NULL|| top!=0)
      {
    while (t!=NULL)
          {
     s[++top].t=t;
     s[top].tag=0;
     t=t->lchild;
    }
         while (top!=0 && s[top].tag==1)
   {
    printf("%c" ,s[top--].t->data);
   }
      if (top)
   {
      s[top].tag=1;
         t = s[top].t->rchild ;
   }
  }
}

3 楼

中国台湾 [专家分：2140] 发布于 2006-06-25 00:57:00

#include<stdio.h>
#include<stdlib.h>
#define MAX_VERTEX_NUM 10
#define ERROR 0
typedef char VertexType;
typedef int VPType;
typedef int Graphkind;
typedef int status;
typedef enum {FALSE, TRUE} boolean;
boolean visit[MAX_VERTEX_NUM];
typedef struct Arcell
{
VPType adj;
}Arcell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct
{
VertexType vex[MAX_VERTEX_NUM];//顶点标志或者叫代号
int vexnum, arcnum;//点的个数和边的条数
AdjMatrix arcs;
Graphkind kind;//图的类型
}MGraph;

status  CreatGraph(MGraph *G)       //建立图
{
int i, j, select;

printf("1:建立有向图!\n");
printf("2:建立无向图!\n");
printf("3:请选者种类!\n");
scanf("%d",&select);
    if (select == 1)
{
  G->kind = 0;
}
else if (select == 2)
{
  G->kind = 1;
}
else
{
  return ERROR;
}

printf("\n请输入顶点的个数:");
scanf("%d",&G->vexnum);
    getchar();// 吃掉内存中的残留数据
printf("\n 请输入顶点的信息(代号)");
for ( i = 0; i < G->vexnum; i++)
{
  scanf("%c",&G->vex[i]);//注意一下

}

getchar();
printf("\n 请输入2个顶点之间的相互关系(0表示相邻 1表示不相邻):\n");
for ( i = 0 ; i < G->vexnum; i++)
  for ( j = 0; j < G->vexnum; j++)
  {
   scanf("%d",&G->arcs[i][j].adj);
  }

   printf("建立成功\n");
   return 0;
}

4 楼

中国台湾 [专家分：2140] 发布于 2006-06-25 00:57:00

status qiudu(const MGraph *G)//求度操作
{
int sum1 , sum2 = 0;
    int i, j;

if (G->kind == 1)
{
  for ( i = 0; i < G->vexnum; i++)
  {
   sum1=0;
   for ( j = 0; j < G->vexnum; j++)
   {
    if ( G->arcs[i][j].adj == 1)
    {
     sum1++;
    }
   }
   printf("编号为%c的第%d的点的度为%d\n",G->vex[i], i+1, sum1);
  }
}
else
{
  for ( i = 0 ; i < G->vexnum; i++)
  {
    sum1=0, sum2=0;
   for ( j = 0 ; j < G->vexnum; j++)
   {
    if ( G->arcs[i][j].adj == 1)
    {
     sum1++;
                }
    if ( G->arcs[j][i].adj == 1)
    {
     sum2++;
    }
   }
   printf("编号为%d的第%d的点的出度为%d入度为%d\n",G->vex[i], i+1, sum1,sum2);

  }
}

return 0;
}

void DFS(MGraph G) //深搜索
{
int i, j;
    void DFS1( MGraph G, int i);//函数声明

for (i = 0 ; i < G.vexnum; i++)
{
  visit[i] = FALSE;
}
for (j = 0; j <G.vexnum; j++)
{
  if (!visit[j])
   DFS1(G,j);//不要用&G 因为G已经是地址了
}

// return 0;
}

void DFS1(MGraph G, int i)
{
int j;

visit[i]=TRUE;
printf("%c",G.vex[i]);

for (j = 0; j < G.vexnum; j++)
{
  if ((i != j) && (G.arcs[i][j].adj == 1) && !visit[j])
  {
   DFS1(G,j);
  }
}

// return 0;
}

status BFS( const MGraph *G,int k)//广度搜索
{
   int s = 0, g = 0;
   int i, j;
   char a[MAX_VERTEX_NUM];

   for (i = 0; i < G->vexnum; i++)
   {
    visit[i] = FALSE;
   }

   printf("%c ",G->vex[k]);
   visit[k]=TRUE;

   for ( j = 0; j < G->vexnum; j++)
   {
    a[j] = -1;
   }
   a[s] = k;

   while(a[s]!=-1)
   {
    int j;

    i = a[g];
    g++;
       for ( j = 0; j < G->vexnum; j++)
    {
     if (G->arcs[i][j].adj == 1 && !visit[j])
     {
      printf("%c ",G->vex[j]);
      visit[j] = TRUE;
      s++;
      a[s] = j;
     }

    }
   if ( s == G->vexnum-1)
   {
   break;
   }
   }
   return 0;
}

int main(void)
{
    MGraph G;
    int flag, select;
int flag1 = 0;
int k;
while(1)
{
  do
  {
   printf("1:构建图\n");
   printf("2:求度\n");
   printf("3:深度搜索\n");
   printf("4:广度搜索\n");
   printf("5:退出\n");
   printf("6:请选择\n");
   scanf("%d",&select);
   if (select == 5)
   {
    flag = 0;
   }
         else
   {
    flag = 1;
   }
  }while(select < 1 || select > 6);

        if (flag == 0)
  {
   break;
  }
  switch(select)
  {
   case 1:
               flag1 = 1;
               CreatGraph(&G);
      break;
        case 2:
               if(flag1 == 1)
      {
                  qiudu(&G);
      }
      else
      {
      printf(" 请先建立图\n");
      }
      break;
        case 3:
      if(flag1 == 1)
      {
                   printf("进行深度搜索:\n");
       DFS(G);
          printf("进行深度搜索:\n");
       printf("\n");
      }
      else
      {
                    printf(" 请先建立图\n");
      }
      break;

        case 4:
      if(flag1 == 1)
      {
       printf("请哪个点开始搜索");
          scanf("%d",&k);
       getchar();
       printf("进行广度搜索\n");
       BFS(&G,k);
       printf("\n");
      }
               else
      {
                    printf(" 请先建立图\n");
      }
      break;

  default: continue;
  }
}

}

我来回复

您尚未登录，请登录后再回复。点此登录或注册

主题：[原创]《数据结构》课程设计

回复列表（共4个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：[原创]《数据结构》课程设计

回复列表 （共4个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共4个回复）