数据结构报告收藏15篇。
通常来讲，有付出就会有收获，随着社会一步步向前发展。书写报告对我们来说是很普遍的，报告的内容必须切实可靠，撰写报告时我们可以从哪些角度着手？根据您所查询的“数据结构报告”工作总结之家编辑为您整理了相关资料供您参考，如需更多信息请继续关注我们的网站！
数据结构报告 篇1
概述
本次实验是针对数据结构课程的一项重要实践活动。通过完成这个实验，我们将深入了解和掌握各类数据结构的运作原理和实际应用。在实验过程中，我们通过编写代码、构建数据结构和进行算法分析等方式，对数据的存储、检索和处理等操作进行了全面的探索和研究。
实验内容
本次实验主要涉及以下几个方面的内容：
1. 数组
数组是最简单和最常用的一种数据结构。我们实现了基本的数组初始化、赋值和读取操作，还研究了各种不同类型的数组和多维数组的使用情况。通过这一部分的实验，我们深入理解了数组在内存中的存储和访问机制。
2. 链表
链表是一种动态数据结构，它的灵活性和高效性使得它在很多场景下比数组更加适用。我们实现了单链表和双链表，并比较了它们在插入和删除操作上的效率差异。通过这部分实验，我们深入了解了链表的结构和运作原理，以及如何通过指针来操作链表。
3. 栈和队列
栈和队列是两种非常常见的数据结构，它们在很多算法和应用中都起到了关键作用。我们实现了基本的栈和队列，并比较了它们在插入和删除操作上的效率差异。通过这部分实验，我们深入理解了栈和队列的特性以及它们的应用场景。
4. 树
树是一种非常重要和复杂的数据结构，它在很多高级算法和数据处理中都起到了关键作用。我们实现了二叉树和二叉搜索树，并研究了它们的遍历和搜索算法。通过这部分实验，我们深入了解了树的结构和运作原理，以及如何通过递归和迭代等方式来解决树相关的问题。
实验过程
在实验过程中，我们首先通过理论学习来了解各种数据结构的概念和特性。然后，我们使用编程语言来实现这些数据结构，并编写测试用例来验证它们的正确性和性能。在编码和调试过程中，我们遇到了很多问题，但通过团队合作和老师的指导，最终成功解决了这些问题。
实验结果
经过实验，我们成功实现了各种数据结构，并通过多次测试验证了它们的正确性和性能。我们还分别对数组、链表、栈和队列、树的各种操作进行了算法分析和性能测试。从实验结果可以看出，不同的数据结构在不同的场景中具有不同的优势和劣势，我们可以根据实际需求选择最适合的数据结构来提高程序的效率和性能。
实验总结
通过本次实验，我们对数据结构的概念和原理有了更加深入的理解，并学会了如何使用编程语言来实现和应用各种数据结构。实验过程中，我们也锻炼了问题分析和解决的能力，以及团队合作和沟通的能力。这些都对我们今后的学习和工作具有重要意义。
通过本次数据结构实验，我们不仅掌握了各种数据结构的运作原理和实际应用，还提高了我们的编程和算法设计能力。这将对我们今后的学习和工作产生积极影响。我们将继续学习和深入研究数据结构，为未来的科学研究和技术创新做出贡献。
数据结构报告 篇2
数据结构(C语言版)实验报告;专业：计算机科学与技术、软件工程;学号:____201240703061_____;班级:_________软件二班________;姓名:________朱海霞__________;指导教师:___刘遵仁_____________;青岛大学信息工程学院;2013年10月;实验1;实验题目：顺序存储结构线性表的插入和删除;实验目
数据结构(C语言版) 实验报告
专业：计算机科学与技术、软件工程
学号:____201240703061___________________
班级:_________软件二班______________
姓名:________朱海霞______________
指导教师:___刘遵仁________________
青岛大学信息工程学院
2013年10月
实验1
实验题目：顺序存储结构线性表的插入和删除
实验目的：
了解和掌握线性表的逻辑结构和顺序存储结构，掌握线性表的基本算法及相关的时间性能分析。
实验要求：
建立一个数据域定义为整数类型的线性表，在表中允许有重复的数据;根据输入的数据，先找到相应的存储单元，后删除之。
实验主要步骤：
理解给出的示例程序。
2、调试程序，并设计输入一组数据(3，-5，6，8，2，-5，4，7，-9)，测试程序的如下功能：根据输入的数据，找到相应的存储单元并删除，显示表中所有的数据。
程序代码:
#include
#include
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef struct{
int* elem;
int length;
int listsize;
}Sqlist;
int InitList_Sq(Sqlist &L){
L.elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int));
if(!L.elem) return -1;
L.length=0;
L.listsize=LIST_INIT_SIZE;
return OK;
}
int ListInsert_Sq(Sqlist&L,int i,int e){
if(iL.length+1) return ERROR;
if(L.length==L.listsize){
int *newbase;
newbase=(int*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(int));
if(!newbase) return -1;
L.elem=newbase;
L.listsize+=LISTINCREMENT;
}
int *p,*q;
q=&(L.elem[i-1]);
for(p=&(L.elem[L.length-1]);p>=q;--p)
*(p+1)=*p;
*q=e;
++L.length;
return OK;
}
int ListDelete_Sq(Sqlist &L,int i,int e){
int *p,*q;
if(iL.length)return ERROR;
p=&(L.elem[i-1]);
e=*p;
q=L.elem+L.length-1;
for(++p;p
*(p-1)=*p;
--L.length;
return OK;
}
int main(){
Sqlist L;
InitList_Sq(L);//初始化
int i,a[]={3,-5,6,8,2,-5,4,7,-9};
for(i=1;i
ListInsert_Sq(L,i,a[i-1]);
for(i=0;i
printf(" %d",L.elem[i]);
printf(" ");//插入9个数
ListInsert_Sq(L,3,24);
for(i=0;i
printf(" %d",L.elem[i]);
printf(" ");//插入一个数
int e;
ListDelete_Sq(L,2, e);
for(i=0;i
printf(" %d",L.elem[i]);//删除一个数
printf(" ");
return 0;
}
实验结果：
3，-5,6,8,2，-5,4,7，-9
3，-5,24,6,8,2，-5,4,7，-9
3,24,6,8,2，-5,4,7，-9
心得体会：
顺序存储结构是一种随机存取结构，存取任何元素的时间是一个常数，速度快;结构简单，逻辑上相邻的元素在物理上也相邻;不使用指针，节省存储空间;但是插入和删除元素需要移动大量元素，消耗大量时间;需要一个连续的存储空间;插入元素可能发生溢出;自由区中的存储空间不能被其他数据共享 实验2
实验题目：单链表的插入和删除
实验目的：
了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。
实验要求：
建立一个数据域定义为字符类型的单链表，在链表中不允许有重复的字符;根据输入的字符，先找到相应的结点，后删除之。
实验主要步骤：
理解给出的示例程序。
4、调试程序，并设计输入数据(如：A，C，E，F，H，J，Q，M)，测试程序的如下功能：不允许重复字符的插入;根据输入的字符，找到相应的结点并删除。
5、修改程序：
(1) 增加插入结点的功能。
(“后插”法。
程序代码:
#include
#include
#define NULL 0
#define OK 1
#define ERROR 0
typedef struct LNode{
int data;
struct LNode *next;
}LNode,*LinkList;
int InitList_L(LinkList &L){
L=(LinkList)malloc(sizeof(LNode)); L->next=NULL;
return OK;
}
int ListInsert_L(LinkList &L,int i,int e){ LinkList p,s;
int j;
p=L;j=0;
while(p&&j
p=p->next;++j;
}
if(!p||j>i-1)
return ERROR;
s=(LinkList)malloc(sizeof(LNode)); s->data=e;
s->next=p->next;
p->next=s;
return OK;
}
int ListDelete_L(LinkList&L,int i,int &e){ LinkList p,q;
int j;
p=L;j=0;
while(p->next&&j
p=p->next;++j;
}
if(!(p->next)||j
return ERROR;
q=p->next;p->next=q->next; e=q->data;free(q);
return OK;
}
int main(){
LinkList L,p;
char a[8]={'A','C','E','F','H','J','Q','U'}; int i,j;
InitList_L(L);
for(i=1,j=0;i
p=L->next;
while(p!=NULL){
printf("%c ",p->data); p=p->next;
}//插入八个字符printf(" ;实验结果：;ACEFHJQU;ABCEFHJQU;ABEFHJQU;心得体会：;单链表是通过扫描指针P进行单链表的`操作;头指针唯;实验掌握栈的顺序存储结构和链式存储结构，以便在实;掌握栈的基本运算，如：入栈与出栈
}
}//插入八个字符 printf(" "); i=2; int e; ListInsert_L(L,i,'B'); p=L->next; while(p!=NULL){ printf("%c ",p->data); p=p->next; }//插入一个字符 printf(" "); i=3; ListDelete_L(L,i,e); p=L->next; while(p!=NULL){ printf("%c ",p->data); p=p->next; } printf(" "); return 0;
实验结果：
A C E F H J Q U
A B C E F H J Q U
A B E F H J Q U
心得体会：
单链表是通过扫描指针P进行单链表的操作;头指针唯一标识点链表的存在;插入和删除元素快捷，方便。
实验3
实验题目：栈操作设计和实现
实验目的：
1、掌握栈的顺序存储结构和链式存储结构，以便在实际中灵活应用。
2、掌握栈的特点，即后进先出和先进先出的原则。
3、掌握栈的基本运算，如：入栈与出栈等运算在顺序存储结构和链式存储结构上的实现。
实验要求：
回文判断：对于一个从键盘输入的字符串，判断其是否为回文。回文即正反序相同。如
“abba”是回文，而“abab”不是回文。
实验主要步骤
(1)数据从键盘读入;
(2)输出要判断的字符串;
(3)利用栈的基本操作对给定的字符串判断其是否是回文，若是则输出“Yes”，否则输出“No”。
程序代码:
#include
#include
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define N 100
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef struct{
int *base; // 在栈构造之前和销毁之后，base的值为NULL int *top; // 栈顶指针
int stacksize; // 当前已分配的存储空间，以元素为单位
} SqStack;
int InitStack(SqStack &S)
{ // 构造一个空栈S
if(!(S.base=(int *)malloc(STACK_INIT_SIZE*sizeof(int))))
exit(OVERFLOW); // 存储分配失败
=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}
int StackEmpty(SqStack S)
{ // 若栈S为空栈，则返回TRUE，否则返回FALSE
if(==S.base)
return TRUE;
else
return FALSE;
}
int Push(SqStack &S, int e)
{ // 插入元素e为新的栈顶元素
if(-S.base>=S.stacksize) // 栈满，追加存储空间
{
S.base=(int *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int)); if(!S.base)
exit(OVERFLOW); // 存储分配失败
=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*()++=e;
return OK;
}
int Pop(SqStack &S,int &e)
{ // 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK;否则返回ERROR if(==S.base)
return ERROR;
e=*--;
return OK;
}
int main(){
SqStack s;
int i,e,j,k=1;
char ch[N] = {0},*p,b[N] = {0};
if(InitStack(s)) // 初始化栈成功
{
printf("请输入表达式: ");
gets(ch);
p=ch;
while(*p) // 没到串尾
Push(s,*p++);
for(i=0;i
if(!StackEmpty(s)) {// 栈不空
Pop(s,e); // 弹出栈顶元素
b[i]=e;
}
}
for(i=0;i
if(ch[i]!=b[i])
k=0;
}
if(k==0)
printf("NO!");
else
printf("输出:")
printf("YES!");
}
return 0;
}
实验结果：
请输入表达式：
abcba
输出：YES!
心得体会：栈是仅能在表尾惊醒插入和删除操作的线性表，具有先进后出的性质，这个固有性质使栈成为程序设计中的有用工具。
实验4
实验题目：二叉树操作设计和实现
实验目的：
掌握二叉树的定义、性质及存储方式，各种遍历算法。
实验要求：
采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。
实验主要步骤：
理解程序。
中序和后序以及按层次遍历序列，求所有叶子及结点总数。
程序代码:
实验结果：
心得体会：
实验5
实验题目：图的遍历操作
实验目的：
掌握有向图和无向图的概念;掌握邻接矩阵和邻接链表建立图的存储结构;掌握DFS及BFS对图的遍历操作;了解图结构在人工智能、工程等领域的广泛应用。
实验要求：
采用邻接矩阵和邻接链表作为图的存储结构，完成有向图和无向图的DFS和BFS操作。
实验主要步骤：
设计一个有向图和一个无向图，任选一种存储结构，完成有向图和无向图的DFS(深度优先遍历)和BFS(广度优先遍历)的操作。
1. 邻接矩阵作为存储结构
#include"stdio.h"
#include"stdlib.h"
#define MaxVertexNum 100 //定义最大顶点数
typedef struct{
char vexs[MaxVertexNum]; //顶点表
int edges[MaxVertexNum][MaxVertexNum]; //邻接矩阵，可看作边表 int n,e; //图中的顶点数n和边数e
}MGraph; //用邻接矩阵表示的图的类型
//=========建立邻接矩阵=======
void CreatMGraph(MGraph *G)
{
int i,j,k;
char a;
printf("Input VertexNum(n) and EdgesNum(e): ");
scanf("%d,%d",&G->n,&G->e); //输入顶点数和边数
scanf("%c",&a);
printf("Input Vertex string:");
for(i=0;in;i++)
{
scanf("%c",&a);
G->vexs[i]=a; //读入顶点信息，建立顶点表
}
for(i=0;in;i++)
for(j=0;jn;j++)
G->edges[i][j]=0; //初始化邻接矩阵
printf("Input edges,Creat Adjacency Matrix ");
for(k=0;ke;k++) { //读入e条边，建立邻接矩阵
scanf("%d%d",&i,&j); //输入边(Vi，Vj)的顶点序号
G->edges[i][j]=1;;G->edges[j][i]=1;//若为;//=========定义标志向量，为全局变量=;typedefenum{FALSE,TRUE}B;Booleanvisited[MaxVertex;//========DFS：深度优先遍历的递归算;voidDFSM(MGraph*G,inti);{//以Vi为出发点
G->edges[i][j]=1;
G->edges[j][i]=1; //若为无向图，矩阵为对称矩阵;若建立有向图，去掉该条语句 }
}
//=========定义标志向量，为全局变量=======
typedef enum{FALSE,TRUE} Boolean;
Boolean visited[MaxVertexNum];
//========DFS：深度优先遍历的递归算法======
void DFSM(MGraph *G,int i)
{ //以Vi为出发点对邻接矩阵表示的图G进行DFS搜索，邻接矩阵是0，1矩阵
给出你的编码
//===========BFS：广度优先遍历=======
void BFS(MGraph *G,int k)
{ //以Vk为源点对用邻接矩阵表示的图G进行广度优先搜索
给出你的编码
//==========主程序main =====
void main()
{
int i;
MGraph *G;
G=(MGraph *)malloc(sizeof(MGraph)); //为图G申请内存空间
CreatMGraph(G); //建立邻接矩阵
printf("Print Graph DFS: ");
DFS(G); //深度优先遍历
printf(" ");
printf("Print Graph BFS: ");
BFS(G,3); //以序号为3的顶点开始广度优先遍历
printf(" ");
}
2. 邻接链表作为存储结构
#include"stdio.h"
#include"stdlib.h"
#define MaxVertexNum 50 //定义最大顶点数
typedef struct node{ //边表结点
int adjvex; //邻接点域
struct node *next; //链域
}EdgeNode;
typedef struct vnode{ //顶点表结点
char vertex; //顶点域
EdgeNode *firstedge; //边表头指针
}VertexNode;
typedef VertexNode AdjList[MaxVertexNum]; //AdjList是邻接表类型 typedef struct {
AdjList adjlist; //邻接表
int n,e; //图中当前顶点数和边数
} ALGraph; //图类型
//=========建立图的邻接表=======
void CreatALGraph(ALGraph *G)
{
int i,j,k;
char a;
EdgeNode *s; //定义边表结点
printf("Input VertexNum(n) and EdgesNum(e): ");
scanf("%d,%d",&G->n,&G->e); //读入顶点数和边数
scanf("%c",&a);
printf("Input Vertex string:");
for(i=0;in;i++) //建立边表
{
scanf("%c",&a);
G->adjlist[i].vertex=a; //读入顶点信息
G->adjlist[i].firstedge=NULL; //边表置为空表
}
printf("Input edges,Creat Adjacency List ");
for(k=0;ke;k++) { //建立边表
scanf("%d%d",&i,&j); //读入边(Vi，Vj)的顶点对序号
s=(EdgeNode *)malloc(sizeof(EdgeNode)); //生成边表结点
s->adjvex=j; //邻接点序号为j
s->next=G->adjlist[i].firstedge;
G->adjlist[i].firstedge=s; //将新结点*S插入顶点Vi的边表头部
s=(EdgeNode *)malloc(sizeof(EdgeNode));
s->adjvex=i; //邻接点序号为i
s->next=G->adjlist[j].firstedge;
G->adjlist[j].firstedge=s; //将新结点*S插入顶点Vj的边表头部
}
}
//=========定义标志向量，为全局变量=======
typedef enum{FALSE,TRUE} Boolean;
Boolean visited[MaxVertexNum];
//========DFS：深度优先遍历的递归算法======
void DFSM(ALGraph *G,int i)
{ //以Vi为出发点对邻接链表表示的图G进行DFS搜索
给出你的编码
//==========BFS：广度优先遍历=========
void BFS(ALGraph *G,int k)
{ //以Vk为源点对用邻接链表表示的图G进行广度优先搜索
给出你的编码
//==========主函数===========
void main()
{
int i;
ALGraph *G;
G=(ALGraph *)malloc(sizeof(ALGraph));
CreatALGraph(G);
printf("Print Graph DFS: ");
DFS(G);
printf(" ");
printf("Print Graph BFS: ");
BFS(G,3);
printf(" ");
}
实验结果：
1. 邻接矩阵作为存储结构
2. 邻接链表作为存储结构
心得体会：
实验6
实验题目：二分查找算法的实现
实验目的：
掌握二分查找法的工作原理及应用过程，利用其工作原理完成实验题目中的内容。。
实验要求：
编写程序构造一个有序表L，从键盘接收一个关键字key，用二分查找法在L中查找key，若找到则提示查找成功并输出key所在的位置，否则提示没有找到信息。。
实验主要步骤：
1. 建立的初始查找表可以是无序的，如测试的数据为{3，7，11，15，17，21，35，42，50｝或者{11，21，7，3，15，50，42，35，17｝。
2. 给出算法的递归和非递归代码;
3. 如何利用二分查找算法在一个有序表中插入一个元素x，并保持表的有序性?
程序代码
实验结果：
心得体会：
实验7
实验题目：排序
实验目的：
掌握各种排序方法的基本思想、排序过程、算法实现，能进行时间和空间性能的分析，根据实际问题的特点和要求选择合适的排序方法。
实验要求：
实现直接排序、冒泡、直接选择、快速、堆、归并排序算法。比较各种算法的运行速度。
实验主要步骤：
程序代码
数据结构报告 篇3
首先你要知道什么是数据结构，学习数据结构的意义。这将是你学习的动力所在。计算机软件都用到了数据结构。所以，学好数据结构对于你将来从事计算机编程类的工作有十分重要的作用。
数据结构中的基本概念，你要一定清楚。平时要多看书，要在计算机上去调试程序，在调试的过程中，你才能发现自己的问题，然后及时解决。在上机调试的过程中，更要大胆尝试，注重运用。拿到一个题时，更要深入分析，尝试用不同的算法去设计。当然编程的时候，要注意格式。比如：变量一定要先定义后使用。变量的定义不要定义在中间。
算法与数据结构是紧密联系，所以你算法一定要会。如果你是学生，只需把课本上出现的搞懂就好了，比如线性表的插入，删除，查找算法，它都是固定的。你就要理解，当然你要学会画图。对于书中的内容要熟悉。
数据结构的大纲如下：线性表、栈和队列，串、数组和广义表、树与森林、图、还有就是查找和排序。简单的总结一下也就是它的逻辑结构：线性结构和非线性结构。这些基本的内容你如果搞懂了，你的数据结构也就学好了。
要严格要求自己。在学习算法的过程中，你要想它为什么要这样设计?它的优点在哪里?想着去改进算法，慢慢的的你的逻辑思维能力也就提高了。你会发现其实数据结构也就那么回事，不是很难。
有不懂得地方要及时请教老师，不要不懂装懂。不要放过任何一个细节，因为我的专业就是计算机，所以有很多都是深有体会。
首先你要清楚一周内所要做的事情，然后制定一张作息时间表。在表上填上那些非花不可的时间，如吃饭、睡觉、上课、娱乐等。安排这些时间之后，选定合适的、固定的时间用于学习，必须留出足够的时间来完成正常的阅读和课后作业。当然，学习不应该占据作息时间表上全部的空闲时间，总得给休息、业余爱好、娱乐留出一些时间，这一点对学习很重要。一张作息时间表也许不能解决你所有的问题，但是它能让你了解如何支配你这一周的时间，从而使你有充足的时间学习和娱乐。
这就意味着在你认真投入学习之前，先把要学习的内容快速浏览一遍，了解学习的大致内容及结构，以便能及时理解和消化学习内容。当然，你要注意轻重详略，在不太重要的地方你可以花少点时间，在重要的地方，你可以稍微放慢学习进程。
学习成绩好的学生很大程度上得益于在课堂上充分利用时间，这也意味着在课后少花些功夫。课堂上要及时配合老师，做好笔记来帮助自己记住老师讲授的内容，尤其重要的是要积极地独立思考，跟得上老师的思维。
课堂上做的笔记你要在课后及时复习，不仅要复习老师在课堂上讲授的重要内容，还要复习那些你仍感模糊的认识。如果你坚持定期复习笔记和课本，并做一些相关的习题，你定能更深刻地理解这些内容，你的记忆也会保持更久。定期复习能有效地提高你的考试成绩。
选择某个地方作你的学习之处，这一点很重要。它可以是你的单间书房或教室或图书馆，但是它必须是舒适的，安静而没有干扰。当你开始学习时，你应该全神贯注于你的功课，切忌“身在曹营心在汉”。
平时测验的目的主要看你掌握功课程度如何，所以你不要弄虚作假，而应心平气和地对待它。或许，你有一两次考试成绩不尽如人意，但是这不要紧，只要学习扎实，认真对待，下一次一定会考出好成绩来。通过测验，可让你了解下一步学习更需要用功夫的地方，更有助于你把新学的知识记得牢固。
数据结构报告 篇4
北京邮电大学信息与通信工程学院
2009级数据结构实验报告
实验名称： 实验三哈夫曼编/解码器的实现
学生姓名：陈聪捷
日 期： 2010年11月28日
1.实验要求
一、实验目的：
了解哈夫曼树的思想和相关概念;
二、实验内容：
利用二叉树结构实现哈夫曼编/解码器
1.初始化：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立哈夫曼树。
2.建立编码表：利用已经建好的哈夫曼树进行编码，并将每个字符的编码输出。
3.编码：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。
4.译码：利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果。
5.打印：以直观的方式打印哈夫曼树。
6.计算输入的字符串编码前和编码后的长度，并进行分析，讨论哈夫曼编码的压缩效果。
7.用户界面可以设计成“菜单”方式，能进行交互，根据输入的字符串中每个字符出现的次数统计频度，对没有出现的字符一律不用编码。
2. 程序分析
2.1 存储结构
二叉树
template
class BiTree
{
public:
BiTree(); //构造函数，其前序序列由键盘输入
~BiTree(void); //析构函数
BiNode* Getroot(); //获得指向根结点的指针
protected:
BiNode *root; //指向根结点的头指针
};
//声明类BiTree及定义结构BiNode
Data：
二叉树是由一个根结点和两棵互不相交的左右子树构成
data:
HCode* HCodeTable;//编码表
int tSize; //编码表中的总字符数
二叉树的节点结构
template
struct BiNode //二叉树的结点结构 {
T data; //记录数据
T lchild; //左孩子
T rchild; //右孩子
T parent; //双亲
};
编码表的节点结构
struct HCode
{
char data; //编码表中的字符
char code[100]; //该字符对应的编码
};
待编码字符串由键盘输入，输入时用链表存储，链表节点为 struct Node
{
char character; //输入的字符
unsigned int count;//该字符的权值
bool used; //建立树的时候该字符是否使用过
Node* next; //保存下一个节点的地址
};
示意图：
2.2 关键算法分析
1.初始化函数(void HuffmanTree::Init(string Input))
算法伪代码：
1.初始化链表的头结点
2.获得输入字符串的第一个字符，并将其插入到链表尾部,n=1(n记录的是链表
中字符的个数)
3.从字符串第2个字符开始，逐个取出字符串中的字符
3.1 将当前取出的字符与链表中已经存在的字符逐个比较，如果当前取出
的字符与链表中已经存在的某个字符相同，则链表中该字符的权值加1。
3.2 如果当前取出的字符与链表中已经存在的字符都不相同，则将其加入
到链表尾部，同时n++
4.tSize=n(tSize记录链表中字符总数，即哈夫曼树中叶子节点总数)
5.创建哈夫曼树
6.销毁链表
源代码：
void HuffmanTree::Init(string Input)
{
Node *front=new Node; //初始化链表的头结点
if(!front)
throw exception("堆空间用尽");
front->next=NULL;
front->character=NULL;
front->count=0;
Node *pfront=front;
char ch=Input[0]; //获得第一个字符
Node* New1=new Node;
if(!New1)
throw exception("堆空间用尽");
New1->character=ch; //将第一个字符插入链表
New1->count=1;
New1->next=pfront->next;
pfront->next=New1;
bool replace=0; //判断在已经写入链表的字符中是否有与当前读出的字符相同的字符 int n=1; //统计链表中字符个数
for(int i=1;i
{
ch=Input[i]; //获得第i个字符
do
{
pfront=pfront->next;
if((int)pfront->character == (int)ch) //如果在链表中有与当前字符相同的字符，
该字符权值加1
{
pfront->count++;
replace=1;
break;
}
}while(pfront->next);
if(!replace) //如果在链表中没找到与当前字符相同的字符，则将该字符作为新成 员插入链表
{
Node* New=new Node;
if(!New)
throw exception("堆空间用尽");
New->character=ch;
New->count=1;
New->next=pfront->next;
pfront->next=New;
n++;
}
pfront=front; //重置pfront和replace变量为默认值 replace=0;
}
tSize=n; //tSize记录的是编码表中字符个数
CreateHTree(front,n); //创建哈夫曼树
pfront=front;
while(pfront) //销毁整个链表
{
front=pfront;
pfront=pfront->next;
front;
}
时间复杂度：
若输入的字符串长度为n，则时间复杂度为O(n)
2.创建哈夫曼树(void HuffmanTree::CreateCodeTable(Node *p))
算法伪代码：
1. 创建一个长度为2*tSize-1的三叉链表
2. 将存储字符及其权值的链表中的字符逐个写入三叉链表的前tSize个结点
的data域，并将对应结点的孩子域和双亲域赋为空
3. 从三叉链表的第tSize个结点开始，i=tSize
3.1 从存储字符及其权值的.链表中取出两个权值最小的结点x,y，记录其
下标x,y。
3.2 将下标为x和y的哈夫曼树的结点的双亲设置为第i个结点
3.3 将下标为x的结点设置为i结点的左孩子，将下标为y的结点设置为
i结点的右孩子，i结点的权值为x结点的权值加上y结点的权值，i
结点的双亲设置为空
4. 根据哈夫曼树创建编码表
源代码：
void HuffmanTree::CreateHTree(Node *p,int n)
{
root= new BiNode[2*n-1]; //初始化哈夫曼树
Node *front=p->next;
if(n==0)
throw exception("没有输入字符");
for(int i=0;i
root[i].data=front->count;
root[i].lchild=-1;
root[i].rchild=-1;
root[i].parent=-1;
front=front->next;
}
front=p;
int New1,New2;
for(i=n;i
{
SelectMin(New1,New2,0,i); //从0~i中选出两个权值最小的结点
root[New1].parent=root[New2].parent=i; //用两个权值最小的结点生成新结点，
新节点为其双亲
root[i].data=root[New1].data+root[New2].data;//新结点的权值为其孩子的权值的和 root[i].lchild=New1;
root[i].rchild=New2;
root[i].parent=-1;
}
CreateCodeTable(p); //创建编码表
}
时间复杂度：
在选取两个权值最小的结点的函数中要遍历链表，时间复杂度为O(n),故该函数
的时间复杂度为O(n^2)
3.创建编码表(void HuffmanTree::CreateCodeTable(Node *p))
算法伪代码：
1.初始化编码表
2.初始化一个指针，从链表的头结点开始，遍历整个链表
2.1 将链表中指针当前所指的结点包含的字符写入编码表中
2.2 得到该结点对应的哈夫曼树的叶子结点及其双亲
2.3 如果哈夫曼树只有一个叶子结点，将其字符对应编码设置为0
2.4 如果不止一个叶子结点，从当前叶子结点开始判断
2.4.1 如果当前叶子结点是其双亲的左孩子，则其对应的编码为0，否
则为1
2.4.2 child指针指向叶子结点的双亲，parent指针指向child指针的双亲，
重复2.4.1的操作
2.5 将已完成的编码倒序
2.6 取得链表中的下一个字符
3.输出编码表
源代码：
void HuffmanTree::CreateCodeTable(Node *p)
{
HCodeTable=new HCode[tSize]; //初始化编码表
Node *front=p->next;
for(int i=0;i
{
HCodeTable[i].data=front->character; //将第i个字符写入编码表
int child=i; //得到第i个字符对应的叶子节点
int parent=root[i].parent; //得到第i个字符对应的叶子节点的双亲
int k=0;
if(tSize==1) //如果文本中只有一种字符，它的编码为0
{
HCodeTable[i].code[k]='0';
k++;
}
while(parent!=-1) //从第i个字符对应的叶子节点开始，寻找它到根结点的路径
{
if(child==root[parent].lchild) //如果当前结点为双亲的左孩子，则编码为0，
否则编码为1
HCodeTable[i].code[k]='0';
else
HCodeTable[i].code[k]='1';
k++;
child=parent;
parent=root[child].parent;
}
HCodeTable[i].code[k]='';
Reverse(HCodeTable[i].code); //将编码逆置
front=front->next; //得到下一个字符
}
cout
for(i=0;i
{
cout
parent=root[parent].lchild;
else //编码为1则寻找右孩子
parent=root[parent].rchild;
i++;
}
if(tSize==1) //如果编码表只有一个字符，则根结点即为叶子结点 i++;
d.append(1,HCodeTable[parent].data);//将叶子节点对应的字符追加到解码串中 }
cout
}
时间复杂度：
设待解码串长度为n，则复杂度为O(n)
8. 计算哈夫曼编码的压缩比(void HuffmanTree::Calculate(string s1,string s2)) 算法伪代码：
1. 获得编码前字符串的长度，即其占用的字节数
2. 获得编码后的字符串的长度，将其除以8然后向上取整，得到其占用的字
节数
3. 压缩比将两个相除
源代码：
void HuffmanTree::Calculate(string s1,string s2)
{
int cal1=s1.length();
int cal2=s2.length();
cal2=ceill((float)cal2/8); //将编码串的比特数转化为字节数 cout
cout
cout
}
时间复杂度：
O(1)
9. 打印哈夫曼树(void HuffmanTree::PrintTree(int TreeNode,int layer) ) 算法伪代码：
1. 如果待打印结点为空，则返回
2. 递归调用函数打印当前结点的右子树
3. 根据当前结点所在的层次确定其前面要输出多少空格，先输出空格，在打
印当前结点的权值
4. 递归调用函数打印当前结点的左子树
源代码：
void HuffmanTree::PrintTree(int TreeNode,int layer)
{
if(TreeNode==-1) //如果待打印结点为空，则返回 return;
else
{
PrintTree(root[TreeNode].rchild,layer+1); //先打印该结点的右子树，layer记录
的是该结点所在的层次
for(int i=0;i
空格
cout
cout
PrintTree(root[TreeNode].lchild,layer+1); //打印该结点的左子树
}
}
时间复杂度：
中序遍历哈夫曼树，复杂度为O(n)
10. 菜单函数(void HuffmanTree::Menu())
算法伪代码：
1. 逐一读取键盘缓存区中的字符，并将它们逐一追加到记录输入字符串的
string变量中，直到读到回车输入符为止
2. 删除string变量末尾的回车输入符
3.利用string变量创建哈夫曼树，初始化编码表。
4. 直观打印哈夫曼树
5. 对输入的字符串进行编码
6. 对编码后的字符串进行解码
7. 计算编码前后的压缩比并输出
源代码：
void HuffmanTree::Menu()
{
cout
string Input;
char letter;
do //将字符逐个读入Input变量中
{
letter=cin.get();
Input.append(1,letter);
}while(letter!=' ');
Input.erase(Input.length()-1,1); //去掉Input末尾的回车符
Init(Input); //根据输入的字符串创建哈夫曼树及其编码表 cout
PrintTree(2*tSize-1-1,1); //打印哈夫曼树
cout
string d1,d2;
cout
Encode(Input,d1); //编码并打印编码串
cout
Decode(d1,d2); //解码并打印解码串
cout
Calculate(Input,d1); //计算编码前后的压缩比
}
2.3 其他
1.由于题目要求能输入任意长的字符串，所以本程序采用了string变量来记录输入
的字符串，并采用string类的类成员函数来完成各项任务
2.打印哈夫曼树时采用了递归函数，且采用了凹凸表的形式打印哈夫曼树。
3.为了输入空格，输入时采取逐个字符输入的方式
3. 程序运行结果
主函数流程图：
运行结果：
各函数运行正常，没有出现bug
4. 总结
经过这次实验，我了解了哈夫曼树的创建过程，了解了一种不等长编码的方法，用设断点调试的方法更加熟练，同时熟悉了STL中string类型的用法，对C++更加熟悉
数据结构报告 篇5
一、需求分析
1、 程序所实现的功能;
2、 程序的输入，包含输入的数据格式和说明;
3、 程序的输出，程序输出的形式;
4、 测试数据，如果程序输入的数据量比较大，需要给出测试数据;
5、 合作人及其分工
二、设计说明
1、 主要的数据结构设计说明;
2、 程序的主要流程图;
3、 程序的主要模块，要求对主要流程图中出现的模块进行说明
4、 程序的'主要函数及其伪代码说明 (不需要完整的代码) ;
5、 合作人设计分工
三、上机结果及体会
1、 合作人编码分工
2、 实际完成的情况说明(完成的功能，支持的数据类型等);
3、 程序的性能分析，包括时空分析;
4、 上机过程中出现的问题及其解决方案;
5、 程序中可以改进的地方说明;
6、 程序中可以扩充的功能及设计实现假想;
说明：
模块、抽象数据类型设计;详细设计负责程序的数据类型定义和主要函数的说明。
2、 设计说明中，不需要写出代码或者模块的详细代码，只需要写出主要函数的伪代码说明。
数据结构报告 篇6
一、实验报告规范
实习报告的开头应给出题目、班级、姓名、学号和完成日期，并包括以下七个内容：
1.需求分析
以无歧义的陈述说明程序设计的任务，强调的是程序要做什么?明确规定：
(1)输入的形式和输入值的范围;
(2)输出的形式;
(3)程序所能达到的功能;
(4)测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。
2.概要设计
说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次(调用)关系。
3.详细设计
实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法;对主程序和其他模块也都需要写出伪码算法(伪码算法达到的详细程度建议为：按照伪码算法可以在计算机键盘直接输入高级程序设计语言程序);画出函数的调用关系图。
4.调试分析
内容包括：
(1)调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析;
(2)算法的时空分析(包括基本操作和其他算法的时间复杂度和空间复杂度的分析)和改进设想;
(3)经验和体会等。
5.用户使用说明
说明如何使用你编写的程序，详细列出每一步的操作步骤。
6.测试结果
列出你的测试结果，包括输入和输出。这里的测试数据应该完整和严格，最好多于需求分析中所列。
7.附录
带注释的源程序。如果提交源程序软盘，可以只列出程序文件名的清单。
值得注意的是，实习报告的各种文档资料，如：上述中的前三部分要在程序开发的过程中逐渐充实形成，而不是最后补写(当然也可以应该最后用实验报告纸誊清或打印)。
数据结构实验报告;实验名称：实验一线性表实现一个多项式;学生姓名：黄锦雨;班级：模板类、异常处理的使用;3.掌握线性表的操作的实现方法;4.学习使用线性表解决实际问题的能力;实验内容：;
数据结构实验报告
实验名称： 实验一线性表实现一个多项式
学生姓名： 黄锦雨
班 级：2011211109
班内序号： 20
学 号： 2011210263
日 期： 2012年10月31日
实验目的：
1.熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法
模板类、异常处理的使用
3.掌握线性表的操作的实现方法
4.学习使用线性表解决实际问题的能力
实验内容：
利用线性表实现一个一元多项式Polynomial
f(x) = a0 + a1x + a2x2 + a3x3 + … + anxn
要求：
1. 能够实现一元多项式的输入和输出
2. 能够进行一元多项式相加
3. 能够进行一元多项式相减
4. 能够计算一元多项式在x处的值
5. 能够计算一元多项式的导数(选作)
6. 能够进行一元多项式相乘(选作) 7. 编写测试main()函数测试线性表的正确性
2. 程序分析
由于多项式是线性结构，故选择线性表来实现，在这个程序中我采用的是单链表结构，每个结点代表一个项，多项式的每一项可以用其系数和指数唯一的表示。如果采用顺序存储，那么对于结点的插入和删除的操作会比较麻烦，而且顺序表的结点个数固定，对于可能发生的情况无法很好的处理，而采用链表就会简单许多，还能自由控制链表的长度。
两个多项式要进行多次的计算，为了保护原始的数据，方便进行以后的计算，故选择把结果存储在一个新建的链表里。
2.1本程序完成的主要功能：
1. 输入和输出：需要输入的.信息有多项式的项数，用来向系统动态申请内存;多项式
各项的系数和指数，用来构造每个结点，形成链表。输出即是将多项式的内容
向屏幕输出。
2. 多项式相加与相减：多项式的加减要指数相同即是同类项才能实现，所以在运算时
要注意判断指数出现的各种不同的情况，分别写出计算方法。将每项运算得到
的结果都插入到新的链表中，形成结果多项式。
3. 多项式的求导运算：多项式的求导根据数学知识，就是将每项的系数乘以指数，将
指数减1即可，将每项得到的结果插入到结果多项式的链表中。
4. 多项式在某点的值：由用户输入x的值，然后求出每项的值相加即可。
2.2存储结构
单链表: 其定义的结点包括三部分：系数、指数以及下一个结点的地址
2.3关键算法分析
[内容要求]
关键算法：
1.一元多项式求和算法:
[1]初始化工作指针p和q,以及p节点前驱节点指针p_prior
[2]若p和q都不为空,则循环以下操作:
[2.1]若p->data.expdata.exp,则p_prior=p;p=p->nenx;
[2.2]否则,若p->data.exp>q->data.exp,则:
[2.2.1]将q结点加入到A链表p结点之前
[2.2.2]q指向B链表的下一个结点
[2.3]否则:p->ef=p->ef+q->ef;
[2.3.1]若p->ef为0,则删除结点p
[2.3.2]p指向下一个结点
[2.3.3]删除q结点
[2.3.4]q指向下一个结点
[3]若p为空并且q不为空,则将q结点及其后所有结点追加到A链表的最后端
[4]将B链表 制成空链表
2.一元多项式求导
[1]初始化工作指针p及p_prior
[2]若p不为空,循环以操作
[2.1]若p->data.exp=0;p_prior->next=p->next; p; p=p_prior;
[2.2]否则 p->ef*=p->data.exp; p->data.exp--;
3.一元多项式求在X处的值
[1]初始化工作指针p,定义会参数a
[2]若p不为空,循环以下操作
a+=p->ef*pow(x,p->data.exp);
p=p->next;
4.输出多项式
[1]获取头结点;
[2]循环n-1次(n为多项式的项数)
[2.1]将指针的指向后移;
[2.2]依照多项式的各种情况，设置输出方式
[2.2.1] 系数为1且指数不为1和0，输出x^expn+;
[2.2.2] 系数不为0且指数为0，输出(coef)+;
[2.2.3] 系数不为0且指数为1，输出(coef)x+;
代码详细分析：
求和算法详细分析:
1.若p->data.expdata.exp
(1)q结点不变
(2)p结点向下移
(1)p_prior=p;
(2)p=p->next;
2.若p->data.exp>q->data.exp执行一下主要操作步骤
(1) p_prior->next=q;
(2)p_prior=q;
(3)q=q->next;
(4)p_prior->next=p;
示意图
:
3.若p->data.exp==q->data.exp执行以下操作步骤:
(a)若合并系数为零,则删除p结点,主要步骤:
(1)p_prior->next=p->next;
(2) p;
(3)p=p_prior->next;
(4)Node*temp=q;
(5)q=q->next;
(6) temp;
示意图
:
(b)合并系数不为零,将其从新赋予p结点,主要步骤:
(1)p_prior=p;
(2)p=p_prior->next;
(3)Node*temp=q;
(4)q=q->next;
(5) temp;
示意图:
5. 若p为空且q不为空的情况
p_prior->next=q;
示意图:
3、计算关键算法的时间,空间复杂度
时间复杂度(1)一元多项式的构建(2)求和(3)减法(4)求导 时间复杂度都为O(n)
空间复杂度为:S(1)
2.3 其他
[内容要求]说明:为了防止word版本不一样而可能带来的图形错乱,示意图,流程图都用截图
3. 程序运行结果
测试主函数流程：流程图如图所示
4.总结;[正文格式要求]见1实验要求中的格式要求;1.这次实现一元多项式的运算运用了模版类,单链表;版类的的继承,在掌握模版类及链表的同时又复习了上;2.这次试验另一比较大的工程是一元多项式加法的算;点打出来又截图完成的,真的是一个比较大工程!;3.这次一元多项式实验问题让我的收获很大,对链表;的更加准确,在调试代码,检验的时候,曾遇到很大的;4.通过本次
4. 总结
[正文格式要求] 见1实验要求中的格式要求
1. 这次实现一元多项式的运算运用了模版类,单链表模版类,一元多项式模版类是单链表模
版类的的继承,在掌握模版类及链表的同时又复习了上学期的相应内容.
2. 这次试验另一比较大的工程是一元多项式加法的算法示意图,以上截图全是我自己一点
点打出来又截图完成的,真的是一个比较大工程!
3.这次一元多项式实验问题让我的收获很大,对链表的构建更加熟练,对链表的向前推进把握
的更加准确,在调试代码,检验的时候,曾遇到很大的阻碍,主要是内存问题,通过自己一步步调试,解决了问题,自己也收获了很多。
4.通过本次实验，我发现自己分析问题不是很全面，容易忽略一些细节，以后分析问题时要仔细考虑认真分析，避免细节上的错误。
数据结构报告 篇7
数据结构是计算机科学中非常重要的一门基础课程，它研究的是数据的存储、组织和管理方式。本文将针对数据结构这一主题展开一系列讨论，介绍数据结构的基本概念、常用算法以及实际应用场景。
一、数据结构的基本概念
1.1 数据类型
数据类型是数据结构中最基本的概念之一，它指的是数据存储的格式和类型。常见的数据类型包括整型、浮点型、字符型等。
1.2 数据结构
数据结构指的是一种数据的组织方式，它可以简单地理解为按一定规律组织数据的方法。常见的数据结构包括数组、链表、树、图等。
1.3 算法
算法是一种用于解决特定问题的过程或方法，它可以用某种语言来描述。不同的算法适用于不同的问题，比如排序、查找、计算等。
二、常用数据结构算法
2.1 排序算法
排序算法是数据结构中最基本和常见的算法之一，它可以对一系列数据进行排序，以便于后续的查找和管理。常见的排序算法有冒泡排序、快速排序、插入排序等。
2.2 查找算法
查找算法是在一组数据中搜索指定数据的过程，常见的查找算法有顺序查找、二分查找等。
2.3 哈希算法
哈希算法是一种常见的数据加密和解密算法，它通过对数据进行一定方式的计算，将其变成一个固定长度的字符串，用于保障数据的安全性。
三、数据结构在实际应用中的应用场景
3.1 图像处理
图像处理是一项对图片进行操作和优化的技术，它需要使用到很多数据结构，比如数组、链表等，用于存储和处理图片的颜色、像素等信息。
3.2 网络通信
网络通信是一个重要的应用场景，它需要使用到很多数据结构，比如树、图等用于存储和处理网络的拓扑结构、路由算法等。
3.3 数据库管理
数据库是一个存储、管理和检索数据的系统，它需要使用到很多数据结构，比如哈希表、B-Tree等，用于快速地检索数据、管理索引等。
综上所述，数据结构是计算机科学中一个非常重要的基础课程，它研究的是数据的存储、组织和管理方式。在实际应用中，数据结构有着广泛的应用场景，包括图像处理、网络通信、数据库管理等。掌握数据结构的基本概念和常用算法，对于提高算法设计和编程能力有着巨大的帮助。
数据结构报告 篇8
数据结构报告
引言：
数据结构是计算机科学中的一门重要课程，它研究如何组织和存储数据，以便在计算机中高效地操作和处理。数据结构对于计算机科学的发展和应用起着至关重要的作用。本报告将详细介绍数据结构的相关主题，包括数组、链表、栈、队列和树等。
一、数组
数组是一种线性数据结构，它由相同类型的元素组成，并按照一定的顺序存储在内存中。数组提供了按下标随机访问元素的能力，具有快速读取和修改元素的特点。本节将介绍数组的定义、基本操作及其在实际应用中的使用。
二、链表
链表是另一种常见的线性数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。与数组相比，链表的插入和删除操作更加灵活，但访问元素时需要遍历整个链表。本节将介绍链表的分类、基本操作以及它在实际应用中的应用场景。
三、栈
栈是一种具有特殊操作规则的线性数据结构，它遵循先进后出（Last In First Out，LIFO）的原则。栈主要包含入栈和出栈两个基本操作，可以用于实现简单的计算器、函数调用等。本节将介绍栈的定义、基本操作以及它在计算机系统中的应用。
四、队列
队列是一种具有特殊操作规则的线性数据结构，它遵循先进先出（First In First Out，FIFO）的原则。队列主要包含入队和出队两个基本操作，可以用于实现线程池、消息队列等。本节将介绍队列的定义、基本操作以及它在实际应用中的使用。
五、树
树是一种非线性的数据结构，由节点和边组成，节点之间存在层次关系。树具有层次性、唯一根节点和子树的递归结构等特点。树的应用非常广泛，比如文件系统、数据库索引和图像压缩等。本节将介绍树的定义、基本概念以及常见的树结构和它们的应用场景。
六、总结
数据结构是计算机科学的基础，它为我们提供了有效存储和操作数据的方法。通过本报告的详细介绍，我们了解了数组、链表、栈、队列和树等常见的数据结构，以及它们在实际应用中的使用场景。在实际开发中，根据不同的问题需求选择合适的数据结构非常重要，只有熟练掌握数据结构的原理和应用，才能更高效地解决实际问题。
参考文献：
1.《数据结构与算法分析- C语言描述》
2.《数据结构与算法分析- Java语言描述》
3.《Introduction to Algorithms》
附录：数据结构相关算法代码实现及其测试用例
数据结构报告 篇9
一、实验目的及要求
1)掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们。
本实验训练的要点是“栈”和“队列”的观点;
二、实验内容
1) 利用栈，实现数制转换。
2) 利用栈，实现任一个表达式中的语法检查(选做)。
判队列空、入队列、出队列);
三、实验流程、操作步骤或核心代码、算法片段
顺序栈：
Status InitStack(SqStack &S)
{
S.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));
if(!S.base)
return ERROR;
=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}
Status DestoryStack(SqStack &S)
{
free(S.base);
return OK;
}
Status ClearStack(SqStack &S)
{
=S.base;
return OK;
}
Status StackEmpty(SqStack S)
{
if(S.base==)
return OK;
return ERROR;
}
int StackLength(SqStack S)
{
return -S.base;
}
Status GetTop(SqStack S,ElemType &e)
{
if(-S.base>=S.stacksize)
{
S.base=(ElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));
if(!S.base) return ERROR;
=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*++=e;
return OK;
}
Status Push(SqStack &S,ElemType e)
{
if(-S.base>=S.stacksize)
{
S.base=(ElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));
if(!S.base)
return ERROR;
=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*++=e;
return OK;
}
Status Pop(SqStack &S,ElemType &e)
{
if(==S.base)
return ERROR;
e=*--;
return OK;
}
Status StackTraverse(SqStack S)
{
ElemType *p;
p=(ElemType *)malloc(sizeof(ElemType));
if(!p) return ERROR;
p=;
while(p!=S.base)//上面一个...
{
p--;
printf("%d ",*p);
}
return OK;
}
Status Compare(SqStack &S)
{
int flag,TURE=OK,FALSE=ERROR;
ElemType e,x;
InitStack(S);
flag=OK;
printf("请输入要进栈或出栈的元素：");
while((x= getchar)!='#'&&flag)
{
switch (x)
{
case '(':
case '[':
case '{':
if(Push(S,x)==OK)
printf("括号匹配成功! ");
break;
case ')':
if(Pop(S,e)==ERROR || e!='(')
{
printf("没有满足条件 ");
flag=FALSE;
}
break;
case ']':
if ( Pop(S,e)==ERROR || e!='[')
flag=FALSE;
break;
case '}':
if ( Pop(S,e)==ERROR || e!='{')
flag=FALSE;
break;
}
}
if (flag && x=='#' && StackEmpty(S))
return OK;
else
return ERROR;
}
链队列：
Status InitQueue(LinkQueue &Q)
{
Q.front =Q.rear=
(QueuePtr)malloc(sizeof(QNode));
if (!Q.front) return ERROR;
Q.front->next = NULL;
return OK;
}
Status DestoryQueue(LinkQueue &Q)
{
while(Q.front)
{
Q.rear=Q.front->next;
free(Q.front);
Q.front=Q.rear;
}
return OK;
}
Status QueueEmpty(LinkQueue &Q)
{
if(Q.front->next==NULL)
return OK;
return ERROR;
}
Status QueueLength(LinkQueue Q)
{
int i=0;
QueuePtr p,q;
p=Q.front;
while(p->next)
{
i++;
p=Q.front;
q=p->next;
p=q;
}
return i;
}
Status GetHead(LinkQueue Q,ElemType &e)
{
QueuePtr p;
p=Q.front->next;
if(!p)
return ERROR;
e=p->data;
return e;
}
Status ClearQueue(LinkQueue &Q)
{
QueuePtr p;
while(Q.front->next )
{
p=Q.front->next;
free(Q.front);
Q.front=p;
}
Q.front->next=NULL;
Q.rear->next=NULL;
return OK;
}
Status EnQueue(LinkQueue &Q,ElemType e)
{
QueuePtr p;
p=(QueuePtr)malloc(sizeof (QNode));
if(!p)
return ERROR;
p->data=e;
p->next=NULL;
Q.rear->next = p;
Q.rear=p; //p->next 为空
return OK;
}
Status DeQueue(LinkQueue &Q,ElemType &e)
{
QueuePtr p;
if (Q.front == Q.rear)
return ERROR;
p = Q.front->next;
e = p->data;
Q.front->next = p->next;
if (Q.rear == p)
Q.rear = Q.front; //只有一个元素时(不存在指向尾指针)
free (p);
return OK;
}
Status QueueTraverse(LinkQueue Q)
{
QueuePtr p,q;
if( QueueEmpty(Q)==OK)
{
printf("这是一个空队列! ");
return ERROR;
}
p=Q.front->next;
while(p)
{
q=p;
printf("%ddata);
q=p->next;
p=q;
}
return OK;
}
循环队列：
Status InitQueue(SqQueue &Q)
{
Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));
if(!Q.base)
exit(OWERFLOW);
Q.front=Q.rear=0;
return OK;
}
Status EnQueue(SqQueue &Q,QElemType e)
{
if((Q.rear+1)%MAXQSIZE==Q.front)
return ERROR;
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1)%MAXQSIZE;
return OK;
}
Status DeQueue(SqQueue &Q,QElemType &e)
{
if(Q.front==Q.rear)
return ERROR;
e=Q.base[Q.front];
Q.front=(Q.front+1)%MAXQSIZE;
return OK;
}
int QueueLength(SqQueue Q)
{
return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
}
Status DestoryQueue(SqQueue &Q)
{
free(Q.base);
return OK;
}
Status QueueEmpty(SqQueue Q) //判空
{
if(Q.front ==Q.rear)
return OK;
return ERROR;
}
Status QueueTraverse(SqQueue Q)
{
if(Q.front==Q.rear)
printf("这是一个空队列!");
while(Q.front%MAXQSIZE!=Q.rear)
{
printf("%d
Q.front++;
}
return OK;
}
数据结构报告 篇10
问题描述：;四则运算表达式求值，将四则运算表达式用中缀表达式;一、需求分析：;输入输出格式：;输入格式：在字符界面上输入一个中缀表达式，回车表;请输入表达式：;输入一个中缀表达式;输出格式：如果该中缀表达式正确，那么在字符界面上;式，其中后缀表达式中两相邻操作数之间利用空格隔开;果不正确，在字符界面上输出
问题描述：
四则运算表达式求值，将四则运算表达式用中缀表达式，然后转换为后缀表达式，并计算结果。
一、 需求分析：
1、本程序是利用二叉树后序遍历来实现表达式的转换，同时可以使用实验三的结果来求解后缀表达式的值。
2、输入输出格式：
输入格式：在字符界面上输入一个中缀表达式，回车表示结束。
请输入表达式：
输入一个中缀表达式
输出格式：如果该中缀表达式正确，那么在字符界面上输出其后缀表达
式，其中后缀表达式中两相邻操作数之间利用空格隔开;如
果不正确，在字符界面上输出表达式错误提示。
逆波兰表达式为：
3、测试用例
输入：21+23*(12-6)
输出：21 23 12 6 -*+ 输出逆波兰表达式 运算结果为：输出运算后的结果
二、概要设计 ：
抽象数据类型
二叉树类BiTree
算法的基本思想
根据题目要求，利用栈计算，和二叉树存储，来计算表达式
该算法的基本思想是：
先利用栈进行计算，然后用二叉树进行存储，和实验三算法一样来计算逆波兰表达式的值
程序的流程
程序由三个模块组成：
(1) 输入模块：输入一个运算式
(2) 计算模块：利用栈进行表达式的计算，二叉树来存储。 (3 ) 输出模块：屏幕上显示出后缀表达式和运算结果。
三、详细设计
物理数据类型
程序含有两个类，其中栈不再赘述，另一个类为二叉树class BiTree包含私有成员struct BiTreeNode，根节点BiTreeNode *T;索引index; int number_of_point 优先级比较函数 compare(char a,char b);生成树的函数void InorderCreate(BiTreeNode *&T,char str[30][10],int start,int end);判断数字函数bool IsNumber(char a);求值函数double Operate(BiTreeNode *T);还有显示后缀表达式的函数void display(BiTreeNode *T) ;而公有成员函数则是对私有函数的重载，为方便使用，因为函数中普遍使用了递归的算法。
算法的时空分析
此算法利用栈和二叉树来实现，故次算法的的时间复杂度为(N)。
输入和输出的格式
输入格式：请输入表达式：
输入一个中缀表达式 //回车
输出格式：逆波兰表达式为：
输出逆波兰表达式
运算结果为：输出运算后的结果
四、调试分析
略。
五、测试结果
本实验的测试结果截图如下：
六、用户使用说明(可选)
运行程序时
提示输入表达式
本程序可以将中缀表达式转换为后缀表达式后在计算出运算式的结果。 提示：请输入表达式：
输出
提示：逆波兰表达式为：
运算结果：
七、实验心得(可选)
本次实验过程比较复杂，由于书上的`知识掌握的还不是很牢靠，所以现在实验做起来有点儿吃力。本实验主要是通过与同学的讨论和课后查阅资料来完成的，虽然有些地方还不是很懂，但基本上能完成此次实验的内容。而且通过本次实验，加深了对二叉树算法的了解。
附录(实验代码)：
#include
#include
#include
#include
#include
#include
#define STACK_INIT_SIZE 100
#define DATA_SIZE 10
#define STACKINCREMENT 10
#define OK 1
#define TRUE 1
#define FALSE 0
#define ERROR 0
#define OVERFLOW -2
using namespace std;
typedef float SElemtype;
typedef int Status;
typedef char * TElemType;
typedef struct BiTNode {
TElemType data;
int len; //data字符串中字符的个数
struct BiTNode * lchild, * rchild;
}BiTNode, *BiTree;
typedef struct
{
SElemtype *base;
SElemtype *top;
int stacksize;
} SqStack;
Status IsDigital(char ch)
{ if(ch>='0'&&ch
{return 1; //是数字字母
}
return 0; //不是数字字母
}
int CrtNode(stack &PTR, char *c)
{
BiTNode * T;
int i=0;
T = (BiTNode *)malloc(sizeof(BiTNode));
T->data = (char *)malloc(DATA_SIZE*sizeof(char));
while(IsDigital(c[i]))
{T->data [i] = c[i];
i++; }
T->len = i;
T->lchild = T->rchild = NULL;
PTR.push (T);
return i;
}
void CrtSubTree(stack &PTR, char c)
{BiTNode * T;
T = (BiTNode *)malloc(sizeof(BiTNode));
T->data = (char *)malloc(DATA_SIZE*sizeof(char));
T->data [0] = c;
T->len = 1;
T->rchild = (); //先右子树，否则运算次序反了
PTR.pop ();
T->lchild = ();
PTR.pop ();
PTR.push (T);
}
char symbol[5][5]={{'>', '>', ''}, //符号优先级
{'>', '>', ''},
{'>', '>', '>', '>', '>'},
{'>', '>', '>', '>', '>'},
{'
int sym2num(char s) //返回符号对应优先级矩阵位置 { switch(s)
{
case '+': return 0; break;
case '-': return 1; break;
case '*': return 2; break;
case '/': return 3; break;
case '#': return 4; break;
}
}
char Precede(char a, char b) //返回符号优先级
{return(symbol[sym2num(a)][sym2num(b)]);}
void CrtExptree(BiTree &T, char exp[])
{ //根据字符串exp的内容构建表达式树T
stack PTR;//存放表达式树中的节点指针
stack OPTR;//存放操作符
char op;
int i=0;
OPTR.push ('#');
op = ();
while( !((exp[i]=='#') && (()=='#')) ) //与
{
if (IsDigital(exp[i]))
{//建立叶子节点并入栈 PTR
i+=CrtNode(PTR, &exp[i]);
}
else if (exp[i] == ' ')
i++;
else{
switch (exp[i])
{
case '(': {
OPTR.push (exp[i]);
i++;
break;}
case ')': {
op = (); OPTR.pop ();
while(op!='('){
CrtSubTree(PTR, op);
op = (); OPTR.pop ();
数据结构报告 篇11
数据结构报告
一、引言
数据结构是计算机科学中非常重要的一门课程，它研究了数据的组织方式、存储结构及其在计算机算法中的应用。数据结构的设计和实现对于软件开发和算法设计具有深远的影响。本报告将讨论数据结构的相关主题，包括线性数据结构、树形数据结构和图形数据结构，并从实际应用的角度探讨它们的优缺点以及适用场景。
二、线性数据结构
1. 数组（Array）
数组是一种最基础的线性数据结构，它将相同数据类型的元素按照一定的顺序存储在内存中。数组的优点是随机访问速度快，但插入和删除操作较为低效。它适用于需要频繁访问元素，并且元素的数量相对稳定的场景，比如存储一组学生成绩。
2. 链表（Linked List）
链表是一种动态数据结构，它使用指针将元素按照某种逻辑关系连接起来。链表的优点是插入和删除操作高效，但查找元素需要遍历链表，速度较慢。它适用于频繁进行插入和删除操作的场景，比如实现一个简单的消息队列。
三、树形数据结构
1. 二叉树（Binary Tree）
二叉树是一种每个节点最多有两个子节点的树结构。二叉树的优点是查找操作高效，且可以利用二叉搜索树的性质进行排序。然而，如果树的平衡性不好，可能会导致树的高度较高，影响操作效率。二叉树适用于需要进行高效查找和排序操作的场景，比如实现字典。
2. 堆（Heap）
堆是一种用于实现优先队列的树结构，堆中的每个节点的值都必须满足一定的顺序关系。堆的优点是能够在常数时间内找到最大或最小的元素，但插入和删除操作较为复杂。堆适用于需要高效查找最大或最小元素的场景，比如任务调度算法。
四、图形数据结构
1. 邻接矩阵（Adjacency Matrix）
邻接矩阵是一种使用二维数组来表示图中节点之间的关系的方法。邻接矩阵的优点是可以快速判断两个节点之间是否存在边，但是如果图的边很稀疏，邻接矩阵会浪费大量的空间。邻接矩阵适用于节点之间关系紧密且边比较密集的场景，比如社交网络分析。
2. 邻接表（Adjacency List）
邻接表是一种使用链表或数组来表示图中节点之间关系的方法。邻接表的优点是节省空间，但查找两个节点之间是否存在边的时间复杂度较高。邻接表适用于节点之间关系稀疏的场景，比如地图导航中的路径查找。
五、结论
数据结构在计算机科学中扮演了至关重要的角色，不同的数据结构适用于不同的场景。了解各种数据结构的优缺点以及适用场景，可以帮助我们选择合适的数据结构来解决实际问题，并优化算法的性能。本报告从线性数据结构、树形数据结构和图形数据结构三个方面介绍了常见的数据结构，希望对读者有所帮助。
数据结构报告 篇12
实验报告;课程名称：数据结构班级：软件工程实验成绩：;1206;实验名称：打印机队列模拟学号：4848批;程序的设计;实验编号：实验一姓名：实验日期：5月2;一、实验目的;对队列的理解;对STL中的queue的使用;实验仿真一个网络打印过程;二、实验内容与实验步骤流程图;这个任务队列的测试使用STL队列适配器;具体地说,每一行中包含的信息是
这个任务队列的测试使用STL队列适配器。程序要求完成模拟的实现共享打印机。这个打印机使用先进先出队列。仿真是通过读取和处理事件数据文件的列表。一个有效的数据文件中的每一行包含信息打印作业和提交这份工作的时间。
具体地说,每一行中包含的信息是提交工作的时间(以秒为单位),和在页面的工作长及工作的计算机的名称。在模拟的开始,每个这些事件的每一个应该被程序所读，存储在继承工作负载队列。程序应该通过循环递增计数器或while-loop模拟时间的流逝。程序应该将计数器初始化为零,然后依次增加1秒。当模拟等于当前时间的打印作业的提交时间在工作队列的前面，一个打印作业完成。当这一切发生的时候,从工作队列取出这个事件,然后把它放在另一个队列对象。这个队列对象存储已完成的打印作业。当程序仿真其他的打印工作的时候，这些工作在队列等待。
#include “simulator.h”
protected:
queue waiting;
priority_queue priority_waiting;
public:
fifo(int seconds_per_page);
void simulate(string file);
};
bool operator
using namespace std;
fifo::fifo(int seconds_per_page):simulator(seconds_per_page){ }
void fifo::simulate(string file){
int finish_time = 0;
float agg_latency = 0;
int totaljob =0;
event evt;
if(file.find(“arbitrary”)!= string::npos){
string outfile =“arbitrary.out”;
ofstream osf(outfile.c_str());
loadworkload(file);
osf
for(int time =1;!waiting.empty()||!workload.empty();time++){ while(!workload.empty() && time ==
workload.front().arrival_time()){
evt= workload.front();
osf
workload.pop();
}
if(!waiting.empty() && time >= finish_time){
totaljob ++;
evt = waiting.front();
agg_latency += time - evt.arrival_time();
osf
finish_time = time + evt.getjob().getnumpages() * seconds_per_page;
}
}
osf
osf
osf
return;
}
if(file.find(“bigfirst”) != string::npos){
string outfile = “bigfirst.out”;
ofstream osf(outfile.c_str());
loadworkload(file);
=1;!priority_waiting.empty()||!workload.empty();time++){
while(!workload.empty() && time ==
workload.front().arrival_time()){
evt= workload.front();
osf
workload.pop();
}
if(!priority_waiting.empty() && time >= finish_time){
totaljob ++;
evt = priority_();
agg_latency += time - evt.arrival_time();
osf
finish_time = time + evt.getjob().getnumpages() * seconds_per_page; }
}
osf
osf
osf
return;
}
cerr
cerr
bool operator
return evtleft.getjob().getnumpages()
evtright.getjob().getnumpages();
经测试，功能较为完整。代码流程简图如下：
通过这次实验，我了解了有关队列方面的知识。掌握了队列的逻辑结构，抽象数据类型，队列的存储方式等。运用先进先出表，仿真了网络打印队列。这都使我对数据结构的学习有了新的认识与帮助。在实验过程中，我也遇到了许多困难，从开始时对队列运算的不熟悉，到逐渐查找资料，从而完成了实验;六、附录;-《数据结构与算法分析》以及网上资料;
逐渐查找资料，从而完成了实验。在今后的学习中，我将继续努力，加强对堆栈，队列等知识的学习，以达到精益求精。
数据结构报告 篇13
数据结构报告
引言
数据结构是计算机科学中的一个重要概念，它是指数据元素之间的关系以及这些关系在计算机中的存储方式。数据结构的选择和设计直接影响到程序的运行效率和空间利用率。本报告将详细介绍数据结构的相关知识、应用及优化方法。
一、数据结构的概念和分类
数据结构是对计算机中数据的组织、存储和管理的方法的研究。它按照数据元素之间的关系可分为线性结构、非线性结构和文件结构。线性结构中的数据元素是一对一的关系，如数组、链表；非线性结构中的数据元素是一对多的关系，如树、图；文件结构是对数据进行存储和访问的方法，如顺序文件、索引文件。
二、常见数据结构的应用
1. 数组(Array)：数组是一种线性结构，它可以存储多个相同类型的元素。在计算机科学中，数组被广泛应用于存储和访问数据，如矩阵运算、图像处理等。
2. 链表(Linked List)：链表是一种线性结构，它通过指针将数据元素连接在一起。链表可以动态地调整大小，因此在需要频繁插入和删除元素的情况下，链表是一种常用的数据结构。
3. 栈(Stack)：栈是一种具有特定操作限制的线性结构，它遵循先进后出（LIFO）的原则。栈常用于程序的内存分配、表达式求值等场景。
4. 队列(Queue)：队列是一种具有特定操作限制的线性结构，它遵循先进先出（FIFO）的原则。队列常用于实现任务调度、消息传递等场景。
5. 树(Tree)：树是一种非线性结构，它由节点和边组成。树状结构的应用非常广泛，如文件系统、数据库索引等。
6. 图(Graph)：图是一种非线性结构，它由节点和边组成。图的应用涉及到网络、社交关系分析等领域。
三、数据结构的优化方法
1. 算法优化：选择合适的算法可以明显提高程序的执行效率。比如，在查找一个有序数组中的元素时，使用二分查找算法可以将时间复杂度降低为O(logN)，而不是简单的线性查找算法的O(N)。
2. 空间优化：合理利用存储空间是数据结构优化的一个重要方面。比如，对于稀疏矩阵，可以采用压缩存储的方式，只保存非零元素，从而减少内存消耗。
3. 缓存优化：利用计算机中的缓存机制可以提高程序的访问速度。比如，将最常用的数据放在缓存中，减少从内存读取数据的时间。
4. 并行优化：利用并行计算的特性可以加快程序的执行速度。比如，将大规模的计算任务分解为多个子任务，分配给多个处理器同时执行。
结论
数据结构是计算机科学中非常重要的一门学科，它对程序的性能和空间利用率有着直接影响。在实际的软件开发中，根据具体的需求选择合适的数据结构和优化方法可以提高程序的效率和用户体验。因此，深入理解数据结构的概念和分类，并学会应用优化方法，对于开发高效的软件应用至关重要。
数据结构报告 篇14
一、需求分析1、程序所实现的功能；2、程序的输入，包含输入的数据格式和说明；3、程序的输出，程序输出的形式；4、测试数据，如果程序输入的数据量比较大，需要给出测试数据；5、合作人及其分工二、设计说明1、主要的数据结构设计说明；2、程序的主要流程图；3、程序的主要模块，要求对主要流程图中出现的模块进行说明4、程序的主要函数及其伪代码说明(不需要完整的代码)；5、合作人设计分工三、上机结果及体会1、合作人编码分工2、实际完成的情况说明（完成的功能，支持的数据类型等）；3、程序的性能分析，包括时空分析；4、上机过程中出现的问题及其解决方案；5、程序中可以改进的地方说明；6、程序中可以扩充的功能及设计实现假想；说明：1、如果程序比较大，可以将设计说明分为概要设计和详细设计两部分。概要设计主要负责程序的流程、模块、抽象数据类型设计；详细设计负责程序的数据类型定义和主要函数的说明。2、设计说明中，不需要写出代码或者模块的详细代码，只需要写出主要函数的伪代码说明。
数据结构报告 篇15
1.判断链表是否存在环型链表问题：判断一个链表是否存在环，例如下面这个链表就存在一个环：
例如N1->N2->N3->N4->N5->N2就是一个有环的链表，环的开始结点是N5这里有一个比较简单的解法，设置两个指针p1，p2。每次循环p1向前走一步，p2向前走两步。直到p2碰到NULL指针或者两个指针相等结束循环。如果两个指针相等则说明存在环。
{
int data;
link* next;
};
{
link* p1=head, *p2 = head;
if (head ==NULL || head->next ==NULL)
{
return false;
}
do{
p1= p1->next;
p2 = p2->next->next;
} while(p2 && p2->next && p1!=p2);
return false;
}
2,链表反转 单向链表的反转是一个经常被问到的一个面试题，也是一个非常基础的问题。比如一个链表是这样的： 1->2->3->4->5 通过反转后成为5->4->3->2->1。最容易想到的方法遍历一遍链表，利用一个辅助指针，存储遍历过程中当前指针指向的下一个元素，然后将当前节点元素的指针反转后，利用已经存储的指针往后面继续遍历。源代码如下：
struct linka {
int data;
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;
return p;
}
}
3,判断两个数组中是否存在相同的数字 给定两个排好序的数组，怎样高效得判断这两个数组中存在相同的数字？
这个问题首先想到的是一个O(nlogn)的算法。就是任意挑选一个数组，遍历这个数组的所有元素，遍历过程中，在另一个数组中对第一个数组中的每个元素进行binary search。用C++实现代码如下：
bool findcommon(int a[],int size1,int b[],int size2)
{
int i;
for(i=0;i
{
int start=0,end=size2-1,mid;
{
mid=(start+end)/2;
return true;
else if (a[i]
start=mid+1;
}
}
return false;
}
后来发现有一个 O(n)算法，
因为两个数组都是排好序的。所以只要一次遍历就行了。首先设两个下标，分别初始化为两个数组的起始地址，依次向前推进。推进的规则是比较两个数组中的数字，小的那个数组的下标向前推进一步，直到任何一个数组的下标到达数组末尾时，如果这时还没碰到相同的数字，说明数组中没有相同的数字。
bool findcommon2(int a[], int size1, int b[], int size2)
{
int i=0,j=0;
while(ireturn true;j++;if(a[i]i++;}return false;}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)的线性算法实现，算法的来源于Programming Pearls一书。 在给出线性算法之前，先来看一个对穷举算法进行优化的算法，它的算法复杂度为O(n^2)。其实这个算法只是对对穷举算法稍微做了一些修改：其实子序列的和我们并不需要每次都重新计算一遍。假设Sum(i, j)是A[i] ... A[j]的和，那么Sum(i, j+1) = Sum(i, j) + A[j+1]。利用这一个递推，我们就可以得到下面这个算法：{int i,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;}}return max;}那怎样才能达到线性复杂度呢？这里运用动态规划的思想。先看一下源代码实现：{int i,max=0,temp_sum=0;for(i=0;i{temp_sum+=a[i];max=temp_sum;temp_sum=0;}return max;}在这一遍扫描数组当中，从左到右记录当前子序列的和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)return head;do {p1=p1->next;p2=p2->next->next;} while(p2 && p2->next);return p1;}来自：akalius.blog/163319