数据结构实践周部分题目答案

《数据结构程序设计》

报告

      学        号    1132107107          

姓        名      郁家琪            

班        级       1121             

         日        期    2012年7月 5号     

实践报告1

学号 ___1132107107__ 

                  姓名 _  郁家琪__ 

 班级____1121_________  

一、实验目的：熟悉数据结构，培养良好的程序设计能力

二、实验内容：（粘贴你所选择的题目）

管道铺设施工的最佳方案选择

需要在某个城市的n各居民区之间都可以架设管道，则在这n各居民区之间只需架设n-1条管道即可。假设任意两个居民区之间均可以架设管道，但由于地理环境的不同，所需经费不同，选择最优的施工方案能使总投资尽可能少，这个问题即为求网络的“最小生成树”。

要求：在所有可能架设的管道中选取n-1条，即能连通n各居民区又能使总投资最小。连通网络可采用邻接矩阵存储，以顶点对（i，j）的形式输出最小生成树的边。测试数据如教材p2图1.2（a）所示。（难度系数为4）

三、设计说明：写出数据结构的定义

    ①图文件的结构

　　②图在内存中的存储结构

　　　邻接矩阵、邻接表、三元组

　　③最小生成树的存储结构

　　④图形的显示结构 

四、功能说明：说明本程序中的每一个函数及其功能。

①准备代价文件

　　　自动随机生成、用户可以自定义

　　②读图文件，得到图的存储结构

　　③计算最小生成树

　　　何种算法效率更好？Prim、Kruskal

　　④显示最小生成树

　　　文本方式：各边、总权值

　　  图形函数：屏幕初始化、端点位置的初始化、绘边函数、代价显示函数、绘无边图函数...... 

五、调试分析

内容包括：

（1）调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析

（2）算法的时空分析和改进设想

（3）经验与体会等

通过数据结构的课程设计使我们对所学知识有了更好的理解，也增强了动手能力，同时也发现了自己的很多不足之处，对所学知识的应用能力不足，编程水平与课程要求有很大差距。

由于对课本知识了解不够，在实验过程中遇到了一些问题，经过查阅资料思考和探究，最终将问题得到了解决。

通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，才能达到学以致用的目的。设计的过程中发现了自己的不足之处，就是对所学的知识理解得不够深刻，掌握得不够牢固。在此次的课程设计过程中，也让我学到了很多课堂以外的东西，比如思考解决问题的能力，出现差错的随机应变的能力，以及与人合作共同完成任务的能力。总之，此次课程设计让我受益匪浅。

六、测试结果

   包括输入和输出 (粘贴输入输出界面，即用户屏幕)

七、带注释的源程序

#include

#define INFINIFY 9999

void main()

{

int date[20][20];

int areanum;

int edgenum;

int price;

printf("请输入单位长度的价格:\\n");

scanf("%d",&price);

printf("请输入: 顶点数,边数:\\n");

scanf("%d,%d",&areanum,&edgenum);//初始化矩阵各元素值

int i,j;

for(i=0;ifor(j=0;jdate[i][j]=INFINIFY;//读入边

int from,to,m;

printf("输入边,格式为 i,j,k,表示 i 到 j 的权值是 m:\\n");

for(i=0;i{

 scanf("%d,%d,%d",&from,&to,&m);

date[from][to]=m;

date[to][from]=m;

}//输出邻接矩阵

printf("输出邻接矩阵为 :\\n");

for(i=0;i{

for(j=0;j{

printf("%d\",date[i][j]);

}

printf("\\n");

}//prim();

//辅助数组short_way,near_area

//short_way[i]表示居民区i到目前生成树中所有点集u中某个居民区（点）的路程最小值

//near_area[i]表示u中能使其最小的居民区（点）

int short_way[20];

int near_area[20];

int min;

int k,s;

//0已经放入u中

//初始化short_way 和near_area

for(i=1;i{

  short_way[i]=date[0][i];

  near_area[i]=0;

}

short_way[i]=0;

near_area[i]=0;

s=0;

printf("从居民区 0 出发 ，\\n");

for(i=1;i{

min=INFINIFY;//求生成树外顶点到生成树内顶点具有最小权值的边

j=1;k=1;

while(j{

if(short_way[j]!=0 && short_way[j]{

min=short_way[j];

k=j;

} j++;

}

printf("从居民区%d到居民区%d,居民区路程(边的权值)为%d\\n",near_area[k],k,min);

short_way[k]=0;

s+=min;

for(j=0;j{

if(date[k][j]{

short_way[j]=date[k][j];

near_area[j]=k;

}

}

}

printf("%d个居民区之间铺设煤气管道最小生成树的总长度s 为:%d\\n",areanum,s);

printf("所以%d个居民区之间铺设煤气管道所需最小代价 price 为:%d\\n",areanum,s*price);

}

实践报告2

               学号 __1132107107_____  

               姓名 __郁家琪_____

               班级____1121_________    

一、  目的：熟悉数据结构，培养良好的程序设计能力

二、实验内容：（粘贴你所选择的题目）

  实现单链表基础上的选择排序。（难度系数为2）

3、设计说明：写出数据结构的定义

1.选择排序结构

2.单链表结构

4、功能说明：说明本程序中的每一个函数及其功能。

1.选择排序可以使数组中的数按顺序排列

2.单链表结构更方便排序的运行快速，便捷

3.输入输出，储存功能

五、调试分析

内容包括：

（1）调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析

（2）算法的时空分析和改进设想

（3）经验与体会等

通过数据结构的课程设计使我们对所学知识有了更好的理解，也增强了动手能力，同时也发现了自己的很多不足之处，对所学知识的应用能力不足，编程水平与课程要求有很大差距。

由于对课本知识了解不够，在实验过程中遇到了一些问题，经过查阅资料思考和探究，最终将问题得到了解决。

通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，才能达到学以致用的目的。设计的过程中发现了自己的不足之处，就是对所学的知识理解得不够深刻，掌握得不够牢固。在此次的课程设计过程中，也让我学到了很多课堂以外的东西，比如思考解决问题的能力，出现差错的随机应变的能力，以及与人合作共同完成任务的能力。总之，此次课程设计让我受益匪浅。

六．测试结果

   包括输入和输出 (粘贴输入输出界面，即用户屏幕)

七．带注释的源程序

#include "stdio.h"

#include

typedef struct node

{

    int data;

    struct node *next;      

}*Linklist,Node;

Linklist creat(int n)

{

    Linklist head,r,p;

    int x,i;

    head=(Node*)malloc(sizeof(Node));

    r=head;

    printf("输入数字:\\n");

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

{

    scanf("%d",&x);

    p=(Node*)malloc(sizeof(Node));

p->data=x;

r->next=p;

    r=p;

}

r->next=NULL;

    return head;

}

 void output(Linklist head)//将你输入的一组数重新输出，方便下面的结果的比较

{

     Linklist p;

p=head->next;

do

{

printf("%8d",p->data);

p=p->next;

}while(p);

    printf("\\n");

} 

void paixu(Linklist head)

{

    Linklist p,q,small;

    int temp;

for(p=head->next;p->next!=NULL;p=p->next)

{

    small=p;                                                                                                           

for(q=p->next;q;q=q->next)

if(q->datadata)

    small=q;

    if(small!=p)

{

temp=p->data;

p->data=small->data;

small->data=temp;

}

} 

    printf("输出排序后的数字:\\n");

    output(head);

} //用选择排序法把小的数逐一排序，通过n-1次的得到结果

void main()

{

    Linklist head;

    int n;

    printf("输入数字的个数n:\\n");

    scanf("%d",&n);

    head=creat(n);

    printf("输出数字:\\n");

    output(head);

    paixu(head);

}

实践报告3

               学号 __1132107107_____  

               姓名 __郁家琪__ _   __

               班级____1121_________    

一、  目的：熟悉数据结构，培养良好的程序设计能力

二、实验内容：（粘贴你所选择的题目）

快速排序。任务：用程序实现线性表基础上的冒泡和快速排序，并输出排序结果，数据可通过随机函数随机生成。（难度系数为2）

3、设计说明：写出数据结构的定义

1.快速排序结构

2.随机函数结构

4、功能说明：说明本程序中的每一个函数及其功能。

1.一趟快速排序的过程，

2.利用堆排序将一次快速排序联系起来变成多次的一次排序，最终得出结果。

3.利用随机函数rand（）对一定范围的数进行随机抽取调用，避免了偶然性

五、调试分析

内容包括：

（1）调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析

   （2）算法的时空分析和改进设想

（3） 经验与体会等

通过数据结构的课程设计使我们对所学知识有了更好的理解，也增强了动手能力，同时也发现了自己的很多不足之处，对所学知识的应用能力不足，编程水平与课程要求有很大差距。

由于对课本知识了解不够，在实验过程中遇到了一些问题，经过查阅资料思考和探究，最终将问题得到了解决。

通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，才能达到学以致用的目的。设计的过程中发现了自己的不足之处，就是对所学的知识理解得不够深刻，掌握得不够牢固。在此次的课程设计过程中，也让我学到了很多课堂以外的东西，比如思考解决问题的能力，出现差错的随机应变的能力，以及与人合作共同完成任务的能力。总之，此次课程设计让我受益匪浅。

6．测试结果

   包括输入和输出 (粘贴输入输出界面，即用户屏幕)

7．带注释的源程序

#include

#include

#include

#define ElemType int

#define Status int

typedef struct

{

    ElemType *elem;

    int length;

    int listsize;

}sqlist;

void initlist_sq(sqlist &L)

{

    L.elem=new ElemType[100];

    L.length=0;

    L.listsize=100;

}

void QuickSort(sqlist l, int first, int end)

{

    int i=first,j=end,temp=l.elem[first];

while(i  {

     while(i=temp)

            j--;

        l.elem[i]=l.elem[j];

     while(i            i++;        

        l.elem[j]=l.elem[i];            //从表的两端交替的向中间扫描

  }

    l.elem[i]=temp;

if(first      QuickSort(l,first,i-1);

if(end>i+1)        

        QuickSort(l,i+1,end);

}

void main()

{  int n,a,i,m;

    sqlist L;

initlist_sq(L);

printf("请输入需要排序的个数n=  ");

cin>>n;

printf("请输入需要随机排序的范围m=  ");    

cin>>m;

for(i=0;i{

     L.elem[i]=1+(int)(m*rand()/(RAND_MAX+1.0));            

     L.length++;

}//利用随机函数rand()在一定范围中随机出一些数

QuickSort(L,0,L.length-1);

printf("after quicksorted\\n");

for(i=0; i        printf("%d  ", L.elem[i]);

    printf("\\n");

}

实践报告4

               学号 __1132107107_____  

               姓名 __郁家琪__ _   __

               班级____1121_________    

一、  目的：熟悉数据结构，培养良好的程序设计能力

二、实验内容：（粘贴你所选择的题目）

单链表的逆置

 要求：逆置后的单链表是一个新的单链表，但表中的结点不是新生成的，而是从原链表中得到。（难度系数为1）

3．设计说明：写出数据结构的定义

1.单链表结构

2.交换体系及

4．功能说明：说明本程序中的每一个函数及其功能。

1.嵌入函数可以把更多的函数有效的运用

2.释放函数可以避免死循环，使程序正常运行

3.逆置函数可以更好的完成题目的要求

5、调试分析

内容包括：

（1）调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析

   （2）算法的时空分析和改进设想

（3） 经验与体会等

通过数据结构的课程设计使我们对所学知识有了更好的理解，也增强了动手能力，同时也发现了自己的很多不足之处，对所学知识的应用能力不足，编程水平与课程要求有很大差距。

由于对课本知识了解不够，在实验过程中遇到了一些问题，经过查阅资料思考和探究，最终将问题得到了解决。

通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，才能达到学以致用的目的。设计的过程中发现了自己的不足之处，就是对所学的知识理解得不够深刻，掌握得不够牢固。在此次的课程设计过程中，也让我学到了很多课堂以外的东西，比如思考解决问题的能力，出现差错的随机应变的能力，以及与人合作共同完成任务的能力。总之，此次课程设计让我受益匪浅。

六．测试结果

七．带注释的源程序

#include

using namespace std;

struct Number 

{

char data; 

struct Number *next; 

}*number;

void CreateList(Number *&L) //创造一个列表

{

Number *s,*r; 

char x; 

L=(Number *)malloc(sizeof(Number)); //用malloc() 函数求出表的长度

L->next=NULL;

r=L; 

x=getchar(); 

while(x!='\\n') 

{

s=(Number *)malloc(sizeof(Number)); //输出列表

s->data=x;

r->next=s;

r=s; 

x=getchar(); 

}

r->next=NULL;

}

void PrintList(Number *L) //

{

Number *p=L->next;

while(p!=NULL) 

{

cout<data;

p=p->next;

}

cout<}

void InverseList(Number *L)//将列表内的元素逆置

{

Number *p=L->next,*q=L->next;

q=q->next;

p->next=NULL;

p=q;

while(p!=NULL)

{

q=q->next;

p->next=L->next;

L->next=p;

p=q;

}

}

void DestroyList(Number *&L) 

{

Number *p=L,*q=p->next;

while(q!=NULL)

{

free(p);

p=q;

q=p->next;

}

cout<<"释放链表"<}

int main()

{

cout<<"请输入一个链表:";

CreateList(number); 

cout<<"输入的链表为："<PrintList(number); 

InverseList(number); 

cout<<"此链表的逆置为："<PrintList(number); 

DestroyList(number); 

return 0;

}