数据结构实验报告.docx

数据结构实习报告指导老师：_姓名：_班级：_学号：_专题一 堆栈应用实验内容：假设：给定一个矩形布线区域，其外围有若干针脚。两个针脚之间通过布设一条金属线路而实现互连。这条线路被称为电线，被限制在矩形区域内。如果两条电线发生交叉，则会发生电流短路。所以，不允许电线间的交叉。每对互连的针脚被称为网组。我们的目标是要确定对于给定的网组，能否合理地布设电线以使其不发生交叉。实现方案：首先创建一空堆栈，从某一针脚按顺时针方向开始把针脚编号读入堆栈。若堆栈为空则把针脚编号压入堆栈；若要读入的针脚编号与目前堆栈的顶部值属于同一网组则弹出堆栈顶部值，继续读取下一个针脚；否则把当前读到的编号值压入堆栈。这样读完所有针脚，此时若堆栈为空则表示布线盒可以成功布线，否则不能成功布线。主要函数及其算法：int checkbox(void) 函数int checkbox(void) int i,temp;for(i=0;i stack_size ;i+)if(is_empty() = 1)push(zhenjiaoi);elsetemp = top();if(findtwo(temp , zhenjiaoi) = 1)pop();elsepush(zhenjiaoi);if(is_empty() = 1)return (1);elsereturn (0);此函数功能：确定布线盒能否成功布线若能返回“1”，若不能返回“0”。算法思路即为“实现方案”。int findtwo(stack_type a , stack_type b)函数int findtwo(stack_type a , stack_type b)int i,haff;haff = stack_size /2;for(i=0;ihaff;i+)if(a = wangzui*2 & b = wangzui*2+1) | (a = wangzui*2+1 & b = wangzui*2)return (1);return (0);算法思路：网组存于一维数组wangzu中，数组中从左往右每两个针脚编号为属于同一网组。把参数a与b分别与每个网组里的值作比较若刚好与网组里的值相等则它们属于同一网组，函数返回“1”；若a与b与所有网组都不能匹配则返回“0”。void inputdata(void)void inputdata(void)int i;printf(请输入针脚个数: n);scanf(%d, & stack_size);create_stack(stack_size);zhenjiao = (stack_type *)malloc(stack_size * sizeof(stack_type);wangzu = (stack_type *)malloc(stack_size * sizeof(stack_type);printf(请按顺时针方向依次输入个针脚编号：n);for(i=0;i stack_size ;i+)scanf(%d ,& zhenjiaoi);printf(请输入所有网组：n);for(i=0;irow = row;new_node -col = col;new_node -next = null;/* 把它插入到队列的尾部*/if(rear = null)front = new_node;elserear -next = new_node;rear = new_node;/* del*/void del(void)queuenode *next_node;/* 从队列的头部删除一个节点，* 如果他是最后一个节点，将rear 也置为null*/assert(! is_empty();next_node = front -next;free(front);front = next_node;if(front = null)rear = null;/* first_row*/queue_type first_row(void)assert(! is_empty();return (front -row);/* first_col*/queue_type first_col(void)assert(! is_empty();return (front -col);/* is_empty*/int is_empty(void)return (front = null);这个头文件主要是实现队列的接口程序，其中最主要的是向队列尾部中添加一新元素及删除头部的元素。主函数main(void)void main(void)int i,j,len,flag = 0;int temp_row, temp_col;printf(请输入起始点所在行列（以空格相隔）:n);scanf(%d %d,&start.row, &start.col);printf(请输入终止点所在行列（以空格相隔）:n);scanf(%d %d,&end.row, &end.col);/* 初始化包围网格的围墙*/for(i=0;i=m+1;i+)grid0i = gridm+1i = 1;gridi0 = gridim+1 = 1;grid13=1;grid23=1;grid24=1;grid35=1;grid44=1;grid45=1;grid51=1;grid55=1;grid61=1;grid62=1;grid63=1;grid71=1;grid72=1;grid73=1;/* 初始化offset*/offset0.row = -1;offset0.col = 0; /*上*/offset1.row = 1;offset1.col = 0; /*下*/offset2.row = 0;offset2.col = -1; /*左*/offset3.row = 0;offset3.col = 1; /*右*/gridstart.rowstart.col = 2; /*首先把起始点编号2*/insert(start.row, start.col);while(! flag) int a, b;for(i=0;i=3;i+)temp_row = first_row() + offseti.row;temp_col = first_col() + offseti.col;if(gridtemp_rowtemp_col = 0)gridtemp_rowtemp_col = gridfirst_row()first_col() + 1;if(temp_row = end.row) & (temp_col = end.col)flag = 1;break;if(gridtemp_rowtemp_col != 1)for(j=0;j=3;j+)a = temp_row + offsetj.row;b = temp_col + offsetj.col;if(gridab = 0)insert(temp_row,temp_col);break;del(); /*把处理完的位置从队列中删除*/len = gridend.rowend.col-2;path = (queue_type *)malloc(2*len* sizeof(queue_type);for(i=0;ilen;i+)int a,b;for(j=0;j=3;j+)a = temp_row + offsetj.row;b = temp_col + offsetj.col;if(gridtemp_rowtemp_col - gridab = 1)pathi*2 = temp_row;pathi*2+1 = temp_col;temp_row = a;temp_col = b;break;printf(以下为最短路径:n);for(i=0;ileft !=null | tree-right !=null)if(tree -left !=null)post_order(tree -left);if(tree -right !=null)post_order(tree -right); visit(tree);此函数算法思路：后续遍历先访问左右子节点然后访问父节点，函数的参数为指向根节点的指针。这里主要用到了递归调用的算法思想，从根节点开始找直到找到叶子节点，然后又从叶子节点开始往回处理。每次访问完左右子节点后就调用visit()函数访问父节点。访问根节点函数：void visit(treenode *tree)void visit(treenode *tree)int d_left,d_right;p+;if(tree-left !=null)d_left = (tree-left)-value;elsed_left = 0;if(tree-right !=null)d_right = (tree-right)-value;elsed_right = 0;if(tree-left = null)d_left = 0;else if(tree-left)-left = null & (tree-left)-right = null)d_left = 0;else if(tree-right = null)d_left = dp-1;else if(tree-right)-left = null & (tree-right)-right = null)d_left = dp-1;else d_left = dp-2;if(tree-right = null)d_right = 0;else if(tree-right)-left = null & (tree-right)-right = null)d_right = 0;elsed_right = dp-1;if(d_left + d_left = d_right + d_right)dp = d_left + d_left;elsedp = d_right + d_right;if(dp+tree-value tolerance)printf(在节点 %d 处放置放大器 ,p);tree-value = 0;printf(%d点的衰减量为：%d n ,p,dp);此函数算法思路：访问每个父节点时计算出它到子节点的衰减量的最大值，然后加上与它相对于父节点的衰减量。如果这个值大于容忍值则需在此节点放置一放大器，此时它相对于父节点的衰减量就为0，并把每个父节点的衰减量存储在一数组中。实验结果与分析：在main()函数开始初始化了一个二叉树如下图所示：容忍值设为3。经过分析要在节点“s”,”r”,”v”处设置放大器，它们是后序遍历访问的父节点中的第1号，第4号，第5号，衰减量分别为2,2,3。第2号，3号，6号(根节点)父节点的衰减量分别为2,2,3。程序运行结果如下所示：程序运行结果与分析结果一致，程序运行正确。专题四 回溯实验内容：在大规模电子系统的设计中存在着电路板排列问题。这个问题的经典形式为将n个电路板放置到一个机箱的许多插槽中，（如图4- 1所示）。n个电路板的每一种排列定义了一种放置方法。令b= b1 , , bn 表示这n个电路板。m个网组集合l= n1, nm 由电路板定义，ni 是b的子集，子集中的元素需要连接起来。实际中用电线将插有这些电路板的插槽连接起来。图4-1电路板及插槽如令n=8, m= 5。集合b和l如下：b= b1, b2, b3, b4, b5, b6, b7, b8 l= n1, n2, n3, n4, n5 n1 = b4, b5, b6 n2 = b2, b3 n3 = b1, b3 n4 = b3, b6 n5 = b7, b8 图4 -2给出了电路板的一个可能的排列。边表示在电路板之间的连线。图4-2 电路板布线令x 为电路板的一个排列。电路板xi 被放置到机箱的插槽i 中。d e n s i t y(x) 为机箱中任意一对相邻插槽间所连电线数目中的最大值。对于图4- 2中的排列，d e n s i t y为2。有两根电线连接了插槽2和3，插槽4和5，插槽5和6。插槽6和7之间无电线，余下的相邻插槽都只有一根电线。板式机箱被设计成具有相同的相邻插槽间距，因此这个间距决定了机箱的大小。该间距必须保证足够大以便容纳相邻插槽间的连线。因此这个距离（继而机箱的大小）由d e n s i t y(x)决定。电路板排列问题的目标是找到一种电路板的排列方式，使其有最小的d e n s i t y。既然该问题是一个n p-复杂问题，故它不可能由一个多项式时间的算法来解决，而象回溯这样的搜索方法则是解决该问题的一种较好方法。实现方案：把电路板在插槽中任意排列，对第一次排列计算任意一对相邻插槽间所连电线数目中的最大值，把它赋给density。以后的排列同样计算任意一对相邻插槽间所连电线数目中的最大值，如果大于density则计算下一个排列的任意一对相邻插槽间所连电线数目中的最大值。如果小于density当前值，则把此值赋给density.如此进行下去直到检测完所有可能排列为止。主要函数及其算法:实现全排列的函数：void perm(int *list,int k,int m)void perm(int *list,int k,int m)int i;if(k m)best_queue(list);elsefor(i=k;i=m;i+)swap(&listk,&listi);perm(list,k+1,m);swap(&listk,&listi);此函数算法思路：这个函数用了递归调用的算法思想，对于一个序列先排列两个数，然后排三个数如此进行下去直到排完序列中所有数，这就完成了全排列。计算density的函数：int cal_den(int *d)int cal_den(int *d)int i, j, k, den = 0;for(i=0;in-1;i+)k = 0;for(j=0;j=density)return (k);else if(kden)den = k;return (den);此函数算法思路：对于任一种排列，把网组及电路板之间的关系表示成一个nm的整型数组。当且仅当nj中包含电路板bi时，bii=1。再建一个（n-1）m的整型数组d。找出数组b每列中的第一个1与最后一个1的位置（例如（i1,j）,(i2,j)）。则在数组d中j列中的i1行到i2行位置处都赋为1，其他位置处赋为0。然后把每行的数字相加，找出最大数即为此种排列的density。实验结果与分析：假设有6个电路板（b1,b2,b3,b4,b5,b6），5个网组n1 = b1,b2,b4, b5 ;n2 = b2, b6 n3 = b3, b5 ;n4 = b1, b2,b3,b5 ; n5 = b3, b4,b6 。程序运行结果如下所示：结果表明b1插到第一个插槽，b2插到第二个插槽，b6插到第三个插槽，b4插到第四个插槽，b5插到第五个插槽，b3插到第六个插槽。此时density最小为3。经过验证最小density 为3。心得体会：因为此前没有学过数据结构，此次实验开始的时候感到有些困难。然后自己看了一下关于c语言的数据结构的资料，对数据结构有了一定的了解，这样就感觉容易上手多了。读了题目后感觉思路很清楚，但写起程序来却不是很顺利。原因是很久没写过程序了，用c语言来描述算法思路不够熟练，这样就只能一点点的写，一点点的试验，效率非常低。专题一是堆栈的应用。开始的时候写了一个用静态数组实现的堆栈程序，如果想改变输入的针脚个数就必须在宏定义中修改堆栈的大小，显得很麻烦。后来又写了一个用动态数组实现的堆栈程序，堆栈的大小由输入的数据决定，可以处理任意多个针脚的布线盒。这个程序虽然可以判断一个布线盒能否布线，但是它不能直观的把布线结果显示出来，还有就是它处理不了网组中含有多余3个针脚的情况，这都是值得改进的地方。专题二是队列的应用。开始的时候准备用数组来实现队列，但写的时候感觉关系不是很清楚，比较乱。就放弃了这个方案，后来改为用链表实现队列，在处理元素的插入和删除时很方便，他能更好的体现队列先进先出的特点。程序中的不足是没有考虑两点之间走不通的情况。专题三是二叉树的应用。程序中最大的不足是把所有的函数都放在一个文件中，没有把程序中相对独立的块儿提出来放到头文件中。还有就是没有考虑如果某一节点相对于父节点的衰减量大于容忍值的情况（此时在此节点设置放大器已经无效了）。就是写程序要有良好的编程风格，考虑要周到。专题四是回溯算法的应用。程序中最大的不足也是把所有函数都写在同一文件中。在这个程序中我学到了很多，例如怎样实现全排列，如何使用指针来动态建立一个二维数组。建议下次实习的时候，每个同学的题目尽量不同，这样每个同学都可以自己做，都有自己的收获。 总之，经过这次实习是我捡起了很多c语言的知识点，并通过实际编程有了很深的了解，而且对一些基本的数据结构有了一定的了解。在遇到困难的时候通过上网查资料，看书又学到了很多新东西，每次的困难中我都学到了很多。附录-源程序专题一：头文件：stack.h ；d_stack.h ; inputdata.h ; findtwo.h ;源文件：switchbox.cppstack.h文件：#define stack_type int /*堆栈所存储的是的类型*/* create_stack*创建堆栈，参数指定堆栈可以保存多少个元素*/void create_stack(int size);/* destroy_stack* 销毁堆栈，它释放堆栈所使用的内存*/void destroy_stack(void);/* push* 把一个新值压入到堆栈中。他的参数是需要被压入的值*/void push(stack_type value);/* pop*从堆栈弹出一个值并将其丢弃；*/void pop(void);/* top*返回堆栈顶部的值，但不对堆栈进行修改*/stack_type top(void);/* is_empty*如果堆栈为空，返回true,否则返回false*/int is_empty(void);/* is_full*如果堆栈已满，返回true,否则返回false*/int is_full(void);d_stack.h文件：/*用一个动态分配数组实现的堆栈*堆栈的长度在创建堆栈的函数被调用是给出，该函数必须在任何其他操作堆栈的函数被点用之前调用*/#include stack.h#include #include #include #include static stack_type *stack;static int stack_size;static int top_element = -1;/* create_stack*/void create_stack(int size)stack_size = size;stack = (stack_type *)malloc(stack_size * sizeof(stack_type);assert(stack != null);/* destroy_stack*/void destroy_stack(void)stack_size = 0;free(stack);stack = null;/* push*/void push(stack_type value)assert(! is_full();top_element += 1;stacktop_element = value;/* pop*/void pop(void)assert(! is_empty();top_element -= 1;/* top*/stack_type top(void)assert(! is_empty();return stacktop_element;/* is_empty*/int is_empty(void)return (top_element = -1);/* is_full*/int is_full(void)return (top_element = stack_size - 1);inpputdata.h文件：#include #include stack.hextern int stack_size ;extern stack_type *zhenjiao;extern stack_type *wangzu;/* inputdata* 输入针脚及网组数据*/void inputdata(void)int i;printf(请输入针脚个数: n);scanf(%d, & stack_size);create_stack(stack_size);zhenjiao = (stack_type *)malloc(stack_size * sizeof(stack_type);wangzu = (stack_type *)malloc(stack_size * sizeof(stack_type);printf(请按顺时针方向依次输入个针脚编号：n);for(i=0;i stack_size ;i+)scanf(%d ,& zhenjiaoi);printf(请输入所有网组：n);for(i=0;i stack_size ;i+)scanf(%d ,& wangzui);findtwo.h文件：extern int stack_size ;extern stack_type *wangzu;/* findtwo* 确定两个针脚编号是否属于同一网组，若是返回“1”，否则返回“0”*/int findtwo(stack_type a , stack_type b)int i,haff;haff = stack_size /2;for(i=0;ihaff;i+)if(a = wangzui*2 & b = wangzui*2+1) | (a = wangzui*2+1 & b = wangzui*2)return (1);return (0);switchbox.cpp文件：#include #include #include inputdata.h#include checkbox.hint stack_size ;stack_type *zhenjiao;stack_type *wangzu;void main(void)inputdata();if(checkbox() = 1)printf(可以布线);elseprintf(不能布线);专题二：头文件：queue.h; l_queue.h源文件：findpath.cppqueue.h文件：/* 一个队列模块的接口*/#include #define queue_type int /*队列元素的类型*/* destroy_queue* 销毁一个队列*/void destroy_queue(void);/* insert* 向队列添加一个新元素，参数就是需要添加的元素*/void insert(queue_type value1,queue_type value2);/* delete* 从队列中移除一个元素并将其丢弃*/void del(void);/* first_row* 返回队列中第一个元素的row值，但不修改队列本身*/queue_type first_row(void);/* first_col* 返回队列中第一个元素的col值，但不修改队列本身*/queue_type first_col(void);/* is_empty* 如果队列为空返回“1”，否则返回“0”*/int is_empty(void);l_queue.h文件：/* 用一个链表实现的堆栈，它没有长度限制*/#include queue.h#include #include #include /*定义一个结构体，用来存储节点值*/typedef struct queue_nodequeue_type row;queue_type col;struct queue_node *next;queuenode;/* 指向队列第一个和最后一个节点的指针*/static queuenode *front;static queuenode *rear;/* destroy_queue*/void destroy_queue(void)while(! is_empty()del();/* insert*/void insert(queue_type row,queue_type col)queuenode *new_node;/* 分配一个新节点，并填充它的值*/new_node = (queuenode *)malloc(sizeof(queuenode);assert(new_node != null);new_node -row = row;new_node -col = col;new_node -next = null;/* 把它插入到队列的尾部*/if(rear = null)front = new_node;elserear -next = new_node;rear = new_node;/* del*/void del(void)queuenode *next_node;/* 从队列的头部删除一个节点，* 如果他是最后一个节点，将rear 也置为null*/assert(! is_empty();next_node = front -next;free(front);front = next_node;if(front = null)rear = null;/* first_row*/queue_type first_row(void)assert(! is_empty();return (front -row);/* first_col*/queue_type first_col(void)assert(! is_empty();return (front -col);/* is_empty*/int is_empty(void)return (front = null);findpath.cpp文件：#include queue.h#include l_queue.h#include #include #include #define m 7 /*布线网格大小（7*7）*/* 定义一个结构体存储位置*/typedef struct positionint row;int col;position;position start ,end;/*定义起始点和终止点结构体*/position offset4; /*用来帮助移动位置*/int gridm+2m+2=0;queue_type *path; /*定义一数组用来存储路径*/void main(void)int i,j,len,flag = 0;int temp_row, temp_col;printf(请输入起始点所在行列（以空格相隔）:n);scanf(%d %d,&start.row, &start.col);printf(请输入终止点所在行列（以空格相隔）:n);scanf(%d %d,&end.row, &end.col);/* 初始化包围网格的围墙*/for(i=0;i=m+1;i+)grid0i = gridm+1i = 1;gridi0 = gridim+1 = 1;grid13=1;grid23=1;grid24=1;grid35=1;grid44=1;grid45=1;grid51=1;grid55=1;grid61=1;grid62=1;grid63=1;grid71=1;grid72=1;grid73=1;/* 初始化offset*/offset0.row = -1;offset0.col = 0; /*上*/offset1.row = 1;offset1.col = 0; /*下*/offset2.row = 0;offset2.col = -1; /*左*/offset3.row = 0;offset3.col = 1; /*右*/gridstart.rowstart.col = 2; /*首先把起始点编号2*/insert(start.row, start.col);while(! flag) /*假设有最短路径*/int a, b;for(i=0;i=3;i+)temp_row = first_row() + offseti.row;temp_col = first_col() + offseti.col;if(gridtemp_rowtemp_col = 0)gridtemp_rowtemp_col = gridfirst_row()first_col() + 1;if(temp_row = end.row) & (temp_col = end.col)flag = 1;break;if(gridtemp_rowtemp_col != 1)for(j=0;j=3;j+)a = temp_row + offsetj.row;b = temp_col + offsetj.col;if(gridab = 0)insert(temp_row,temp_col);break;del(); /*把处理完的位置从队列中删除*/len = gridend.rowend.col-2;path = (