《数据结构》
课程设计报告
题 目： 实现两个链表的合并
班 级： 08计管（2）班
姓 名： 袁文珠
学 号： 0803011229
指导教师： 肖丽娜
2010 年 6 月 17 日
目录
一、································ 课程设计的性质、目的及要求·· 3
一、··················································· 课程设计性质·· 3
二、························································· 设计目的·· 3
三、························································· 设计要求·· 3
二、··························································· 任务描述·· 4
三、··························································· 软件环境·· 4
四、········································· 算法设计思想及流程图·· 4
一、··················································· 算法设计思想·· 4
二、···························································· 流程图·· 6
五、······························································ 源代码·· 6
六、··························································· 运行结果·· 9
七、························································ 收获及体会·· 10
一、 课程设计的性质、目的及要求
一、 课程设计性质
性质：数据结构设计是《数据结构》课程的实践环节，也是我院各专业必修的计算机技术基础课程之一。
二、 设计目的
目的：课程设计为学生提供了一个既动手又动脑，独立实践的机会，学生将课本上的理论知识和实际有机的结合起来，锻炼学生分析、解决较复杂问题的能力，本次课程设计，也是为了锻炼我们应用编程语言的语法规则和已经掌握的一些较为简单的算法，自己解决一个较简单的课题，初步积累编程经验。提高学生独立编写大编程的能力。
三、 设计要求
计算机科学是一门研究数据表示和数据处理的科学。数据是计算机化的信息，是计算机可以直接处理的最基本和最重要的对象。无论是进行科学计算，数据处理，过程控制，还是对文件的存储和检索及数据库技术的应用，都是对数据进行加工处理的过程。
希望通过学习掌握程序设计的方法与编程技术，我们能学会良好的程序设计风格，为在计算机不同领域的应用打下坚实的基础。希望通过本次的学习，我们能利用计算机解决实际题。与此同时，希望能通过此次的实训来提高我们的思维能力，促进我们的综合应用能力和我们的专业素质。
二、 任务描述
实现两个链表的合并
基本功能要求：
1、建立两个链表A和B，链表元素的个数没别为m和n个。
2、假设元素分别为（x1,x2,···xm），和（y1,y2,···yn）。把他们合并成一个线性表C，使得：
当m>=n时，C=x1,y1,x2,y2,···xn,yn,···xm
当n>m时，C=y1,x1,y2,x2,···ym,xm,···,yn
输出线性表C
3、用直接插入排序法对C进行升序排序，生成表D，并输出表A ,B ,C ,D。
三、 软件环境
编辑工具：
Turbo C2.0
功能介绍：
Turbo C2.0是一个快捷、高效的编译程序，同时还有一个易学、易用的集成开发环境。使用Turbo C2.0无需独立地编辑、编译和连接程序，就能建立并运行C语言程序。因为这些功能都组合在Turbo 2.0的集成开发环境内，并且可以通过一个简单的主屏幕使用这些功能。
四、 算法设计思想及流程图
一、 算法设计思想
1、 定义链表的结构
typedef struct
{
int data[maxsize];
int top;
}list;
2、 创建链表A，B，C，D,由于这链表是自己创立的，我们首先要对他们进行申请存储空间，首先我们就定义头文件#include<alloc.h>，用malloc(sizeof())函数来现实，这是申请链表存储空间的标志.
3、 用指针top的移动来实现对链表A，和B进行数据的输入输出，再进行链表长度的比较，在用直接插入法对A和B中的数据查到C中，当m>=n的时候，先插A的元素，再插入B的元素
C->data[C->top]=A->data[j];
j=j+1;
C->top=C->top+1;
C->data[C->top]=B->data[k];
k=k+1;
C->top=C->top+1;
当n>m的时候，先插B的元素，在插入A的元素
C->data[C->top]=B->data[j];
j=j+1;
C->top=C->top+1;
C->data[C->top]=A->data[k];
k=k+1;
C->top=C->top+1;
4、 用冒泡排序法对C中元素进行排序生成表D，由于要进行升序排序，所以只需比较D->data[j]<D->data[j-1]，再输出D->data[j]，移动指针D->top，每进行一次输出，指针就移动一次D->top+1，直到C中元素都排序完，最后输出D。
5、 打印链表A，B，C，D。
二、 流程图
五、 源代码
#include<stdio.h>
#include<stdlib.h>
#include<alloc.h>
#define maxsize 100
typedef struct
{
int data[maxsize];
int top;
}list; /*创建单链表*/
main()
{
list *A,*B,*C,*D;
int i,j,k,m,n;
/*创建A 链表*/
A=malloc(sizeof(list)); /*给表A申请一个存储空间*/
A->top=0;
printf("input A->data:");
scanf("%d",&A->data[A->top]);
while(A->data[A->top]!=0)
{
A->top++;
printf("input A->data:");
scanf("%d",&A->data[A->top]);
}i=0;
/*创建B 链表*/
B=malloc(sizeof(list)); /*给表B申请一个存储空间*/
B->top=0;
printf("\ninput B->data:");
scanf("%d",&B->data[B->top]);
while(B->data[B->top]!=0)
{
B->top++;
printf("input B->data:");
scanf("%d",&B->data[B->top]);
}i=0;
printf("---------------------------\n");
printf("A:");
for(i=0;i<A->top;i++)
printf("%3d",A->data[i]);
printf("\n---------------------------\n");
printf("---------------------------\n");
printf("B:");
for(i=0;i<B->top;i++)
printf("%3d",B->data[i]);
printf("\n---------------------------\n");
/*C 链表*/
C=malloc(sizeof(list));
C->top=0;
if(A->top>=B->top) /*m>=n时，C=x1,y1,x2,y2,…xn,yn,…,xm*/
{
m=A->top-B->top; /*表A与表B的长度差*/
j=0;
k=0;
for(i=0;i<B->top;i++) /*以B表的长度为循环基准*/
{
C->data[C->top]=A->data[j]; /*C表的第一个插入A中的X1*/
j=j+1;
C->top=C->top+1;
C->data[C->top]=B->data[k]; /*C表的第二个插入B中的Y1*/
k=k+1;
C->top=C->top+1;
}
for(i=0;i<m;i++)
{
C->data[C->top]=A->data[j]; /* 插入完之后A中的多出的元素直接插入C中*/
j=j+1;
C->top=C->top+1;
}
}
else /*n>m时，C=y1,x1,y2,x2,…ym,xm,…,yn*/
{
m=B->top-A->top;
j=0;
k=0;
for(i=0;i<A->top;i++)
{
C->data[C->top]=B->data[j];
j=j+1;
C->top=C->top+1;
C->data[C->top]=A->data[k];
k=k+1;
C->top=C->top+1;
}
for(i=0;i<m;i++)
{
C->data[C->top]=B->data[j];
j=j+1;
C->top=C->top+1;
}
}
printf("-------------------------------\n");
printf("C:");
for(i=0;i<C->top;i++)
printf("%3d",C->data[i]);
printf("\n-------------------------------\n");
/*D 链表*/
D=malloc(sizeof(list));/*给表D申请一个存储空间*/
D->top=0;
for(i=0;i<C->top;i++)
{
D->data[D->top]=C->data[i];
D->top=D->top+1;
}
for(i=0;i<D->top;i++)
{
for(j=1;j<D->top-i;j++)
{
if(D->data[j]<D->data[j-1]) /*D中元素大小进行比较*/
{
n=D->data[j];
D->data[j]=D->data[j-1];
D->data[j-1]=n;
}
}
}
printf("-------------------------------\n");
printf("D:");
for(i=0;i<D->top;i++)
printf("%3d",D->data[i]);
printf("\n-------------------------------\n");
}
六、 运行结果
1 m>=n时运行结果
2 n<m时运行结果
七、 收获及体会
本学期我们学习了数据结构课程，虽说这门学科是今年才开的，在此之前我们还进行过C语言的实训，应该说是一定的基础的，其实通过这次实训也是对我们所学知识的巩固，而且在对数据结构算法进行初步了解同时也提高了语言设计的能力。
我一直觉得编程是一门熟练科学， 多编程，水平肯定会提高， 最重要的是能够养成一种感觉，就是对程序对算法的敏感， 为什么那些牛人看一个算法一下子就看懂了？而自己要看很久才能弄懂， 而且弄懂了过了一阵子又忘记了？其实这个是因为牛人们以前看的程序很多， 编得也很多， 所以他们有了那种感觉，所以我觉得大家应该多看程序， 多写程序， 培养自己的感觉
就我们计算机专业看来，编程能力是很重要的，一个计算机专业的学生首先需要了解和运用的知识就是编程语言，而要学习编程，必须要有明确的学习目的。一般来说在学习程序设计方法和语言时，掌握基本理论是比较容易的，但我们在实际应用和算法估量时却无从下手。比如本次的程序设计，刚开始看到这题目的时候觉得好写，因为在这之前我们做过相关的练习，但真的开始着手写的时候，真的不知道怎么下手，不过在通过认真的思考和结合以前所做的，分析其要实现的功能，和需要的算法。还有在语言编程过程中，有时无法恰当的运用存储数据的方法，这就是知识在实际中的运用问题。如何编写高质量的程序更是我们所面临的难题，这要求我们仔细体会，在反复实践的过程中掌握编程的技巧。
在这次的编程遇到了蛮多的问题，记得在刚开始编写的时候，在做那个指针移动的时候出现了问题，不知道怎么去移动它，但通过自己查阅书籍和问同学，和一步一步的实验，最后终于弄出来了，在这次的编程过程中发现了自己一个很不足的一点，那就是不细心，编程本来要的是程序员要很细心，不细心是要忌讳的，在这次的链表编程中，要熟悉和了解链表的基本功能和链表里面的指针移动，要了解数据的数据域和指针域，如果不是很了解的话，很有可能把里面的数据什么的搞错，还有实现不了自己所需的东西。
通过本次课程设计，还体会到编程能力的高低主要由以下几点决定：1、编程的习惯；2、对数据结构的认知能力；3、语言的掌握能力。