数据结构报告【5篇】

数据结构报告【5篇】优秀的报告该怎么去写？在经济飞速发展的今天，一般都会写报告。汇报性是“数据结构报告【5篇】”的一个大特点，栏目网友经过慎选为大家推荐1篇题名为“数据结构报告【5篇】”的文章，这个网页很有用所以请务必加入收藏夹！数据结构报告【第一篇】1.判断链表是否存在环型链表问题：判断一个链表是否存在环，例如下面这个链表就存在一个环：例如N1-N2-N3-N4-N5-N2就是一个有环的链表，环的开始结点是N5这里有一个比较简单的解法，设置两个指针p1，p2。每次循环p1向前走一步，p2向前走两步。直到p2碰到NULL指针或者两个指针相等结束循环。如果两个指针相等则说明存在环。{intdata;link*next;};{link*p1=head,*p2=head;if(head==NULL||head-next==NULL){returnfalse;}do{p1=p1-next;p2=p2-next-next;}while(p2&&p2-next&&p1!=p2);returnfalse;}2,链表反转单向链表的反转是一个经常被问到的一个面试题，也是一个非常基础的问题。比如一个链表是这样的：1-2-3-4-5通过反转后成为5-4-3-2-1。最容易想到的方法遍历一遍链表，利用一个辅助指针，存储遍历过程中当前指针指向的下一个元素，然后将当前节点元素的指针反转后，利用已经存储的指针往后面继续遍历。源代码如下：structlinka{intdata;linka*next;};return;linka*pre,*cur,*ne;pre=head;cur=head-next;{ne=cur-next;cur-next=pre;pre=cur;cur=ne;}head-next=NULL;head=pre;}还有一种利用递归的方法。这种方法的基本思想是在反转当前节点之前先调用递归函数反转后续节点。源代码如下。不过这个方法有一个缺点，就是在反转后的最后一个结点会形成一个环，所以必须将函数的返回的节点的next域置为NULL。因为要改变head指针，所以我用了引用。算法的源代码如下：linka*reverse(linka*p,linka*&head){if(p==NULL||p-next==NULL){head=p;{linka*tmp=reverse(p-next,head);tmp-next=p;returnp;}}3,判断两个数组中是否存在相同的数字给定两个排好序的数组，怎样高效得判断这两个数组中存在相同的数字？这个问题首先想到的是一个O(nlogn)的算法。就是任意挑选一个数组，遍历这个数组的所有元素，遍历过程中，在另一个数组中对第一个数组中的每个元素进行binarysearch。用C++实现代码如下：boolfindcommon(inta[],intsize1,intb[],intsize2){inti;for(i=0;i{intstart=0,end=size2-1,mid;{mid=(start+end)/2;returntrue;elseif(a[i]start=mid+1;}}returnfalse;}后来发现有一个O(n)算法，因为两个数组都是排好序的。所以只要一次遍历就行了。首先设两个下标，分别初始化为两个数组的起始地址，依次向前推进。推进的规则是比较两个数组中的数字，小的那个数组的下标向前推进一步，直到任何一个数组的下标到达数组末尾时，如果这时还没碰到相同的数字，说明数组中没有相同的数字。boolfindcommon2(inta[],intsize1,intb[],intsize2){inti=0,j=0;while(ireturntrue;j++;if(a[i]i++;}returnfalse;}4,最大子序列问题：给定一整数序列A1，A2，...An（可能有负数），求A1~An的一个子序列Ai~Aj，使得Ai到Aj的和最大例如：整数序列-2,11,-4,13,-5,2,-5,-3,12,-9的最大子序列的和为21。对于这个问题，最简单也是最容易想到的那就是穷举所有子序列的方法。利用三重循环，依次求出所有子序列的和然后取最大的那个。当然算法复杂度会达到O(n^3)。显然这种方法不是最优的，下面给出一个算法复杂度为O(n)的线性算法实现，算法的来源于ProgrammingPearls一书。在给出线性算法之前，先来看一个对穷举算法进行优化的算法，它的算法复杂度为O(n^2)。其实这个算法只是对对穷举算法稍微做了一些修改：其实子序列的和我们并不需要每次都重新计算一遍。假设Sum(i,j)是A[i]...A[j]的和，那么Sum(i,j+1)=Sum(i,j)+A[j+1]。利用这一个递推，我们就可以得到下面这个算法：{inti,j,v,max=a[0];for(i=0;i{v=0;for(j=i;j{v=v+a[j];//Sum(i,j+1)=Sum(i,j)+A[j+1]max=v;}}returnmax;}那怎样才能达到线性复杂度呢？这里运用动态规划的思想。先看一下源代码实现：{inti,max=0,temp_sum=0;for(i=0;i{temp_sum+=a[i];max=temp_sum;temp_sum=0;}returnmax;}在这一遍扫描数组当中，从左到右记录当前子序列的和temp_sum，若这个和不断增加，那么最大子序列的和max也不断增加(不断更新max)。如果往前扫描中遇到负数，那么当前子序列的和将会减小。此时temp_sum将会小于max，当然max也就不更新。如果temp_sum降到0时，说明前面已经扫描的那一段就可以抛弃了，这时将temp_sum置为0。然后，temp_sum将从后面开始将这个子段进行分析，若有比当前max大的子段，继续更新max。这样一趟扫描结果也就出来了。5,找出单向链表的中间结点这道题和解判断链表是否存在环，我用的是非常类似的方法，只不过结束循环的条件和函数返回值不一样罢了。设置两个指针p1，p2。每次循环p1向前走一步，p2向前走两步。当p2到达链表的末尾时，p1指向的时链表的中间。{link*p1,*p2;p1=p2=head;if(head==NULL||head-next==NULL)returnhead;do{p1=p1-next;p2=p2-next-next;}while(p2&&p2-next);returnp1;}来自：/163319数据结构报告【第二篇】数据结构报告摘要：数据结构是计算机科学中非常重要的一个领域，我们常常需要在计算机程序中操作大量的数据，但是没有良好的数据结构，就无法快速与方便地运用这些数据。本文将主要介绍数据结构的概念、分类、基本操作、以及常见的数据结构的特点和应用。主题一：数据结构的概念与分类数据结构是指数据元素之间的关系以及这些关系所具有的性质。数据结构可以分为逻辑结构和物理结构两种，逻辑结构是指数据元素之间的逻辑关系，物理结构是指数据在计算机存储器中的表示方法。逻辑结构又分为线性结构和非线性结构两种。线性结构中的数据元素之间只有一个前驱和一个后继，典型的线性结构有数组、链表、队列、栈等；非线性结构中的数据元素之间不存在顺序关系，常见的非线性结构有树和图。主题二：数据结构的基本操作在任何数据结构中，都会有基本操作，包括增加数据元素、删除数据元素、查找数据元素、遍历数据元素等。增加数据元素可以在指定位置插入一个新元素或者在结构末尾添加一个元素；删除数据元素可以通过指定位置删除一个元素或者按照值删除一个元素；查找可以根据元素值、元素位置和其他关键字来查找；遍历可以遍历整个数据结构，以便对每个元素进行操作。主题三：常见的数据结构和应用数组是数据结构中最基本的一种，它是数据元素存储在连续的内存单元上的一种数据结构。数组可以用来保存一段时间内的数据、系统配置文件、文本文件等。链表是另一种常见的数据结构，它不需要连续的内存空间，而是通过指针来关联每个数据元素。链表有单向链表、双向链表、循环链表等多种类型。队列是一种先进先出（FIFO）的数据结构，常用于控制并发、跨进程通信、缓存管理等方面。栈是与队列相反的数据结构，它是一种后进先出（LIFO）的数据结构，常用于表达式求值、函数调用和括号匹配等场合。树是由根结点和若干子树构成的一种数据结构，树的应用非常广泛，包括文件系统、数据库、路由算法等。图是一种由边和顶点组成的数据结构，它可以用于解决网络流、图像识别等诸多问题。结论：数据结构是计算机科学中非常重要的一个领域，本文介绍了数据结构的概念、分类、基本操作以及常见的数据结构的特点和应用。正确地选择和使用数据结构可以有效提高程序的性能，因此对于计算机科学的学生和工作者来说，掌握数据结构是非常必要的。数据结构报告【第三篇】二.实验目的：1、使学生熟练掌握哈夫曼树的生成算法。2、熟练掌握哈夫曼编码的方法。三.问题描述：已知n个字符在原文中出现的频率，求它们的哈夫曼编码。1、读入n个字符，以及字符的权值，试建立一棵Huffman树。2、根据生成的Huffman树，求每个字符的Huffman编码。并对给定的待编码字符序列进行编码，并输出。typedefstruct{unsignedintweight;unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;//动态分配数组存储郝夫曼树typedefchar**HuffmanCode;//动态分配数组存储郝夫曼编码(2)主要的实现思路：1.基本上没有什么太大的问题，在调用select这个函数时，想把权值最小的两个结点的序号带回HuffmanCoding，所以把那2个序号设置成了引用。2.在编程过程中，在什么时候分配内存，什么时候初始化花的时间比较长3.最后基本上实现后，发现结果仍然存在问题，经过分步调试，发现了特别低级的输入错误。把HT[i].weight=HT[s1].weight+HT[s2].weight;中的s2写成了itypedefstruct{intparent,lchild,rchild;}HTNode,*HuffmanTree;typedefchar**HuffmanCode;voidSelect(HuffmanTree&HT,intk,int&s1,int&s2){inti;i=1;while(is1=i;{if(HT[i].parent==0&&HT[i].weight{if(HT[i].parent==0&&i!=s1)break;}s2=i;{if(HT[i].parent==0&&i!=s1&&HT[i].weight}voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn){intm,c,f,s1,s2,i,start;char*cd;if(nHT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号单元未用，预分配m+1个单元HuffmanTreep=HT+1;{p-weight=*w;p-parent=p-rchild=p-lchild=0;{p-weight=p-parent=p-rchild=p-lchild=0;{Select(HT,i-1,s1,s2);//选出当前权值最小的HT[s1].parent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//分配n个字符编码的头指针变量cd=(char*)malloc(n*sizeof(char));//分配求编码的工作空间for(i=1;ifor(c=i,f=H