当前位置：首页 > 实用文档 > 其他范文> 数据结构实验报告

数据结构实验报告

时间：2022-11-11 11:19:16 其他范文收藏本文下载本文

数据结构实验报告（精选16篇）由网友“coco2008”投稿提供，下面是小编为大家推荐的数据结构实验报告，欢迎大家分享。

数据结构实验报告

篇1：数据结构实验报告

一、实验目的及要求

1)掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们。

本实验训练的要点是“栈”和“队列”的观点;

二、实验内容

1) 利用栈，实现数制转换。

2) 利用栈，实现任一个表达式中的语法检查(选做)。

3) 编程实现队列在两种存储结构中的基本操作(队列的初始化、判队列空、入队列、出队列);

三、实验流程、操作步骤或核心代码、算法片段

顺序栈：

Status InitStack(SqStack &S)

{

S.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));

if(!S.base)

return ERROR;

S.top=S.base;

S.stacksize=STACK_INIT_SIZE;

return OK;

}

Status DestoryStack(SqStack &S)

{

free(S.base);

return OK;

}

Status ClearStack(SqStack &S)

{

S.top=S.base;

return OK;

}

Status StackEmpty(SqStack S)

{

if(S.base==S.top)

return OK;

return ERROR;

}

int StackLength(SqStack S)

{

return S.top-S.base;

}

Status GetTop(SqStack S,ElemType &e)

{

if(S.top-S.base>=S.stacksize)

{

S.base=(ElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));

if(!S.base) return ERROR;

S.top=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT;

}

*S.top++=e;

return OK;

}

Status Push(SqStack &S,ElemType e)

{

if(S.top-S.base>=S.stacksize)

{

S.base=(ElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));

if(!S.base)

return ERROR;

S.top=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT;

}

*S.top++=e;

return OK;

}

Status Pop(SqStack &S,ElemType &e)

{

if(S.top==S.base)

return ERROR;

e=*--S.top;

return OK;

}

Status StackTraverse(SqStack S)

{

ElemType *p;

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

if(!p) return ERROR;

p=S.top;

while(p!=S.base)//S.top上面一个...

{

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(“括号匹配成功!\n\n”);

break;

case ')':

if(Pop(S,e)==ERROR || e!='(')

{

printf(“没有满足条件\n”);

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(“这是一个空队列!\n”);

return ERROR;

}

p=Q.front->next;

while(p)

{

q=p;

printf(“%d<-\n”,q->data);

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.base[Q.front]);

Q.front++;

}

return OK;

}

篇2：数据结构实验报告

一.实验内容：

实现哈夫曼编码的生成算法。

二.实验目的：

1、使学生熟练掌握哈夫曼树的生成算法。

2、熟练掌握哈夫曼编码的方法。

三.问题描述：

已知n个字符在原文中出现的频率，求它们的哈夫曼编码。

1、读入n个字符，以及字符的权值，试建立一棵Huffman树。

2、根据生成的Huffman树，求每个字符的Huffman编码。并对给定的待编码字符序列进行编码，并输出。

四.问题的实现

(1)郝夫曼树的存储表示

typedef struct{

unsigned int weight;

unsigned int parent,lchild,rchild;

}HTNode,*HuffmanTree; //动态分配数组存储郝夫曼树

郝夫曼编码的存储表示

typedef char* *HuffmanCode;//动态分配数组存储郝夫曼编码

(2)主要的实现思路：

a.首先定义郝夫曼树的存储形式，这里使用了数组

b.用select遍历n个字符，找出权值最小的两个

c.构造郝夫曼树HT，并求出n个字符的郝夫曼编码HC

总结

1.基本上没有什么太大的问题，在调用select这个函数时，想把权值最小的两个结点的序号带回HuffmanCoding，所以把那2个序号设置成了引用。

2.在编程过程中，在什么时候分配内存，什么时候初始化花的时间比较长

3.最后基本上实现后，发现结果仍然存在问题，经过分步调试，发现了特别低级的输入错误。把HT[i].weight=HT[s1].weight+HT[s2].weight;中的s2写成了i

附：

//动态分配数组存储郝夫曼树

typedef struct{

int weight; //字符的权值

int parent,lchild,rchild;

}HTNode,*HuffmanTree;

//动态分配数组存储郝夫曼编码

typedef char* *HuffmanCode;

//选择n个(这里是k=n)节点中权值最小的两个结点

void Select(HuffmanTree &HT,int k,int &s1,int &s2)

{ int i;

i=1;

while(i<=k && HT[i].parent!=0)i++;

//下面选出权值最小的结点，用s1指向其序号

s1=i;

for(i=1;i<=k;i++)

{

if(HT[i].parent==0&&HT[i].weight

}

//下面选出权值次小的结点，用s2指向其序号

for(i=1;i<=k;i++)

{

if(HT[i].parent==0&&i!=s1)break;

}

s2=i;

for(i=1;i<=k;i++)

{

if(HT[i].parent==0&&i!=s1&&HT[i].weight

}

//构造Huffman树，求出n个字符的编码

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)

{

int m,c,f,s1,s2,i,start;

char *cd;

if(n<=1)return;

m=2*n-1; //n个叶子n-1个结点

HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //0号单元未用，预分配m+1个单元

HuffmanTree p=HT+1;

w++; //w的号单元也没有值，所以从号单元开始

for(i=1;i<=n;i++,p++,w++)

{

p->weight=*w;

p->parent=p->rchild=p->lchild=0;

}

for(;i<=m;++i,++p)

{

p->weight=p->parent=p->rchild=p->lchild=0;

}

for(i=n+1;i<=m;i++)

{

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)); //分配求编码的工作空间

cd[n-1]='\0';//编码结束符

for(i=1;i<=n;i++) //逐个字符求郝夫曼编码

{

start=n-1; //编码结束符位置

for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) //从叶子到根逆向求编码

{

if(HT[f].lchild==c)cd[--start]='0';

else

cd[--start]='1';

}

HC[i]=(char*)malloc((n-start)*sizeof(char)); //为第i个字符编码分配空间

strcpy(HC[i],&cd[start]);//从cd复制编码到HC

}

free(cd); //释放工作空间

}

void main

{ int n,i;

int* w; //记录权值

char* ch; //记录字符

HuffmanTree HT;

HuffmanCode HC;

cout<<“请输入待编码的字符个数n=”;

cin>>n;

w=(int*)malloc((n+1)*sizeof(int)); //记录权值，号单元未用

ch=(char*)malloc((n+1)*sizeof(char));//记录字符，号单元未用

cout<<“依次输入待编码的字符data及其权值weight”<

for(i=1;i<=n;i++)

{

cout<<“data[”<

}

篇3：数据结构实验报告

数据结构实验报告

数据结构实验报告1

一、实验目的及要求

1)掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们。

本实验训练的要点是“栈”和“队列”的观点;

二、实验内容

1) 利用栈，实现数制转换。

2) 利用栈，实现任一个表达式中的语法检查(选做)。

3) 编程实现队列在两种存储结构中的基本操作(队列的初始化、判队列空、入队列、出队列);

三、实验流程、操作步骤或核心代码、算法片段

顺序栈：

Status InitStack(SqStack &S)

{

S.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));

if(!S.base)

return ERROR;

S.top=S.base;

S.stacksize=STACK_INIT_SIZE;

return OK;

}

Status DestoryStack(SqStack &S)

{

free(S.base);

return OK;

}

Status ClearStack(SqStack &S)

{

S.top=S.base;

return OK;

}

Status StackEmpty(SqStack S)

{

if(S.base==S.top)

return OK;

return ERROR;

}

int StackLength(SqStack S)

{

return S.top-S.base;

}

Status GetTop(SqStack S,ElemType &e)

{

if(S.top-S.base>=S.stacksize)

{

S.base=(ElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));

if(!S.base) return ERROR;

S.top=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT;

}

*S.top++=e;

return OK;

}

Status Push(SqStack &S,ElemType e)

{

if(S.top-S.base>=S.stacksize)

{

S.base=(ElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));

if(!S.base)

return ERROR;

S.top=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT;

}

*S.top++=e;

return OK;

}

Status Pop(SqStack &S,ElemType &e)

{

if(S.top==S.base)

return ERROR;

e=*--S.top;

return OK;

}

Status StackTraverse(SqStack S)

{

ElemType *p;

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

if(!p) return ERROR;

p=S.top;

while(p!=S.base)//S.top上面一个...

{

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(“括号匹配成功!\n\n”);

break;

case ')':

if(Pop(S,e)==ERROR || e!='(')

{

printf(“没有满足条件\n”);

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)

篇4：数据结构实验报告

数据结构实验报告范例

篇一：数据结构实验报告范例

《数据结构与算法》实验报告

专业班级姓名学号

实验项目

实验一二叉树的应用

实验目的

1、进一步掌握指针变量的含义及应用。

2、掌握二叉树的结构特征，以及各种存储结构的`特点及使用范围。

3、掌握用指针类型描述、访问和处理二叉树的运算。

实验内容

题目1:编写一个程序，采用一棵二叉树表示一个家谱关系。要求程序具有如下功能：

（1）用括号表示法输出家谱二叉树，

（2）查找某人的所有儿子，

（3）查找某人的所有祖先。

算法设计分析

（一）数据结构的定义

为了能够用二叉树表示配偶、子女、兄弟三种关系，特采用以下存储关系，则能在二叉树上实现家谱的各项运算。

二叉树型存储结构定义为：

typedef struct SNODE

{char name[MAX]; //人名

struct SNODE *left;//指向配偶结点

struct SNODE *right; //指向兄弟或子女结点

}FNODE;

（二）总体设计

实验由主函数、家谱建立函数、家谱输出函数、儿子查找函数、祖先查找函数、结点定位函数、选择界面函数七个函数共同组成。其功能描述如下：

（1）主函数：统筹调用各个函数以实现相应功能

void main()

（2）家谱建立函数：与用户交互建立家族成员对应关系

void InitialFamily(FNODE *&head) //家谱建立函数

（3）家谱输出函数：用括号表示法输出家谱

输出形式为：父和母（子1和子妻1（孙1），子2和子妻2（孙2））

void PrintFamily(FNODE *head) //家谱输出函数

（4）儿子查找函数：在家谱中查找到某人所有的子女并输出，同时也能辨别出其是否为家族成员与是否有子女

void FindSon(FNODE *b,char p[]) //儿子查找函数

（5）祖先查找函数：在家谱中查找到某人所有的祖先并输出，同时也能辨别出其是否为家族中成员。

int FindAncestor(FNODE *head,char son[ ]) //祖先查找函数

（6）结点定位函数：在家谱中找到用户输入人名所对应的结点。

FNODE *findnode(FNODE *b,char p[]) //结点定位函数

（7）选择界面函数：为便于编写程序，将用户选择部分独立为此函数。

void PRINT(int &n)

（三）各函数的详细设计：

void InitialFamily(FNODE *&head) //家谱建立函数

1：首先建立当前人的信息，将其左右结点置为空，

2：然后让用户确定其是否有配偶，如果没有配偶，则当前程序结束，

3：如果有则建立其配偶信息，并将配偶结点赋给当前人的左结点；

4：再让用户确定其是否有子女，如果有则递归调用家谱建立函数建立子女结点，并将其赋给配偶结点的下一个右结点。

5：如无，则程序结束

void PrintFamily(FNODE *head) //家谱输出函数

1：首先判断当前结点是否为空，如果为空则结束程序；

2：如果不为空，则输出当前结点信息，

3：然后判断其左结点（配偶结点）是否为空，如不为空则输出“和配偶信息。

4：再判断配偶结点的右结点是否为空，如不为空则递归调用输出其子女信息，最后输出“）”；

5：当配偶结点为空时，则判断其右结点（兄弟结点）是否为空

6：如果不为空，则输出“，”，并递归调用输出兄弟信息

7程序结束

FNODE *findnode(FNODE *b,char p[]) //结点定位函数

1：当前结点是否为空，为空则返回空；

2：如果和查找信息相同，则返回当前结点；

3：如不然，则先后递归访问其左结点，再不是则递归访问右结点

void FindSon(FNODE *b,char p[]) //儿子查找函数

1：在家谱中定位到要查找的结点，如无则输出“查找不到此人”

2：判断其配偶结点与子女结点是否为空，为空则输出“无子女”

3：不为空则输出其配偶结点的所有右结点（子女结点）。

int FindAncestor(FNODE *head,char son[ ]) //祖先查找函数

1：先在家谱中定位到要查找的结点，如为空输出“不存在此人”，程序结束

2：先将父母结点入栈，当栈为空时程序结束，

3：栈不为空时，判断栈顶元素是否已访问过，

4：访问过，再判断是否为查找结点，如是则输出栈中保存的其祖先结点，并滤过其兄弟结点不输出；不是查找结点，则退栈一个元素

5：未访问过，则取当前栈顶元素，置访问标志——1，同时取其右结点

6：栈不为空或当前所取结点不为空时，转到2；

实验测试结果及结果分析

（一）测试结果

（二）结果分析

（略）

实验总结

（略）

篇5：北邮数据结构实验报告

北京邮电大学信息与通信工程学院

级数据结构实验报告

实验名称：实验三哈夫曼编/解码器的实现

学生姓名：陈聪捷

日期： 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：

二叉树是由一个根结点和两棵互不相交的左右子树构成

哈夫曼树类的数据域，继承节点类型为int的二叉树 class HuffmanTree:public BiTree

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个字符

{

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<2*n-1;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<<“压缩比为：”<<((double)cal2/(double)cal1)*100<<“%”<

}

时间复杂度：

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<<“ASCII码编码与HUFFMAN编码的比较”<

Calculate(Input,d1); //计算编码前后的压缩比

}

2.3 其他

1.由于题目要求能输入任意长的字符串，所以本程序采用了string变量来记录输入

的字符串，并采用string类的类成员函数来完成各项任务

2.打印哈夫曼树时采用了递归函数，且采用了凹凸表的形式打印哈夫曼树。

3.为了输入空格，输入时采取逐个字符输入的方式

3. 程序运行结果

主函数流程图：

运行结果：

各函数运行正常，没有出现bug

4. 总结

经过这次实验，我了解了哈夫曼树的创建过程，了解了一种不等长编码的方法，用设断点调试的方法更加熟练，同时熟悉了STL中string类型的用法，对C++更加熟悉

篇6：北邮数据结构实验报告线性表

实验报告;课程名称：数据结构班级：软件工程实验成绩：;1206;实验名称：打印机队列模拟学号：4848批;程序的设计;实验编号：实验一姓名：实验日期：5月2;一、实验目的;对队列的理解;对STL中的queue的使用;实验仿真一个网络打印过程;二、实验内容与实验步骤流程图;这个任务队列的测试使用STL队列适配器;具体地说,每一行中包含的信息是

实验报告

课程名称：数据结构班级：软件工程实验成绩：

1206

实验名称：打印机队列模拟学号：20124848 批阅教师签字：

程序的设计

实验编号：实验一姓名：实验日期：205 月 24 日

一、实验目的

对队列的理解

对STL中的queue的使用

实验仿真一个网络打印过程

二、实验内容与实验步骤流程图

这个任务队列的测试使用STL队列适配器。程序要求完成模拟的实现共享打印机。这个打印机使用先进先出队列。仿真是通过读取和处理事件数据文件的列表。一个有效的数据文件中的每一行包含信息打印作业和提交这份工作的时间。

具体地说,每一行中包含的信息是提交工作的时间(以秒为单位),和在页面的工作长及工作的计算机的名称。在模拟的开始,每个这些事件的每一个应该被程序所读，存储在继承工作负载队列。程序应该通过循环递增计数器或while-loop模拟时间的流逝。程序应该将计数器初始化为零,然后依次增加1秒。当模拟等于当前时间的打印作业的提交时间在工作队列的前面，一个打印作业完成。当这一切发生的时候,从工作队列取出这个事件,然后把它放在另一个队列对象。这个队列对象存储已完成的打印作业。当程序仿真其他的打印工作的时候，这些工作在队列等待。

Win8，Visual C++ 6.0

四、实验过程与分析

(1)实验主要函数及存储结构

main.cpp 包括主函数和主要的功能

simulator.h 仿真类的声明

simulator.cpp 仿真类的定义

event.h 事件类的声明

event.cpp - 事件类的定义

job.h 作业类的声明

job.cpp 作业类的定义

arbitrary.run 包括任意打印作业数的数据文件

arbitrary.out 输出 arbitrary.run

bigfirst.run 包括打印较大作业的数据文件

bigfirst.out 输出 bigfirst.run

(2)实验代码

#ifndef FIFO_H //fifo.h

#define FIFO_H

#include “simulator.h”

class fifo:public simulator{

protected:

queue waiting;

priority_queue priority_waiting;

public:

fifo(int seconds_per_page);

void simulate(string file);

};

bool operator < (event evtleft,event evtright);

#endif

#include “fifo.h” //fifo.cpp

#include

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<<“FIFO Simulation ”<

for(int time =1;!waiting.empty()||!workload.empty();time++){ while(!workload.empty() && time ==

workload.front().arrival_time()){

evt= workload.front();

osf<<“ Arriving: ”<

workload.pop();

}

if(!waiting.empty() && time >= finish_time){

totaljob ++;

evt = waiting.front();

agg_latency += time - evt.arrival_time();

osf<<“ Servicing: ”<

finish_time = time + evt.getjob().getnumpages() * seconds_per_page;

}

osf<<“ total job ”<

osf<<“ aggregate latency: ”<

osf<<“ mean latency : ”<

return;

}

if(file.find(“bigfirst”) != string::npos){

string outfile = “bigfirst.out”;

ofstream osf(outfile.c_str());

loadworkload(file);

osf<<“FIFO Simulation ”<

for(int time

=1;!priority_waiting.empty()||!workload.empty();time++){

while(!workload.empty() && time ==

workload.front().arrival_time()){

evt= workload.front();

osf<<“ Arriving: ”<

workload.pop();

}

if(!priority_waiting.empty() && time >= finish_time){

totaljob ++;

evt = priority_waiting.top();

agg_latency += time - evt.arrival_time();

osf<<“ Servicing: ”<

finish_time = time + evt.getjob().getnumpages() * seconds_per_page; }

}

osf<<“ total job ”<

osf<<“ aggregate latency: ”<

osf<<“ mean latency : ”<

return;

}

cerr<<“The program don't know what algorithm to use”<

cerr<<“You should specify the file name with arbitrary or bigfirst”<

bool operator < (event evtleft,event evtright){

return evtleft.getjob().getnumpages() <

evtright.getjob().getnumpages();

}

五、实验结果总结

经测试，功能较为完整。代码流程简图如下：

通过这次实验，我了解了有关队列方面的知识。掌握了队列的逻辑结构，抽象数据类型，队列的存储方式等。运用先进先出表，仿真了网络打印队列。这都使我对数据结构的学习有了新的认识与帮助。在实验过程中，我也遇到了许多困难，从开始时对队列运算的不熟悉，到逐渐查找资料，从而完成了实验;六、附录;-《数据结构与算法分析》以及网上资料;

逐渐查找资料，从而完成了实验。在今后的学习中，我将继续努力，加强对堆栈，队列等知识的学习，以达到精益求精。

六、附录

-《数据结构与算法分析》以及网上资料

篇7：数据结构试题答案

数据结构试题答案

一、单项选择题（每题2分，共30分）

1.若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（）存储方式最节省时间。

A) 单链表 B) 双链表 C) 单向循环链表 D) 顺序表

2.串是任意有限个（）。

A) 符号构成的序列 B) 符号构成的集合

C) 字符构成的序列 D) 字符构成的集合

3.设矩阵A的任一元素aij(1≤i,j≤10)满足：

aij≠0；(i≥j,1≤i,j≤10)

aij=0； (i

现将A的所有非0元素以行序为主序存放在首地址为的存储区域中，每个元素占有4个单元，则元素A[9,5]的首地址为（）。

A) 2340 B) 2336 C) 2164 D) 2160

4.如果以链表作为栈的存储结果，则出栈操作时（）。

A) 必须判别栈是否为满 B) 对栈不作任何判别

C) 必须判别栈是否为空 D) 判别栈元素的类型

5.设数组Data[0..m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针,则执行出队操作的语句为（）。

A) front = front+1 B) front = (front+1) % m

C) rear = (rear+1) % m D) front = (front+1) % (m+1)

6.深度为6(根的层次为1)的二叉树至多有（）结点。

A) 64 B) 32 C) 31 D) 63

7.将含100个结点的完全二叉树从根这一层开始，每层上从左到右依次堆结点编号，根结点的编号为1。编号为49的结点X的双亲的编号为（）。

A) 24 B) 25 C) 23 D) 无法确定

8.设有一个无向图和，如果为的生成树，则下面不正确的说法是（）。

A) 为的子图 B) 为的连通分量

C) 为的极小连通子图且 D) 为的一个无环子图

9.用线性探测法查找闭散列表，可能要探测多个散列地址，这些位置上的键值（）。

A) 一定都是同义词 B) 一定都不是同义词

C) 多相同 D) 不一定都是同义词

10.二分查找要求被查找的表是（）。

A) 键值有序的链接表 B) 链接表但键值不一定有序

C) 键值有序的顺序表 D) 顺序表但键值不一定有序

11.当初始序列已经按键值有序，用直接插入算法对其进行排序，需要循环的次数为（）。

A) B) C) D) n－1

12.堆是一个键值序列 ,对，满足（）。

A) B)

C) 且 ( ) D) 或 ( )

13.使用双向链表存储数据，其优点是可以（）。

A) 提高检索速度 B) 很方便地插入和删除数据

C) 节约存储空间 D) 很快回收存储空间

14.设计一个判别表达式中左右括号是否配对出现地算法，采用（）数据结构最佳。

A) 线性表地顺序存储结构 B) 栈

C) 队列 D) 线性表达的链式存储结构

15.设深度为k的二叉树上只有度为0和2的结点，则此类二叉树中所含的结点数至少为（）。

A) k + 1 B) 2k C) 2k - 1 D) 2k + 1

二、填空题（每空2分，共28分）

1.设r指向单链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的三条语句是_____________________________________________r=s;r->next=NULL。

2.在单链表中，指针p所指结点为最后一个结点的条件是___________________。

3.设一个链栈的栈顶指针是ls，栈中结点格式为，栈空的条件为_____________。如果栈不为空，则出栈操作为p=ls;______________;free(p)。

4.已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的'结点，则该树有________个叶子结点。

5.树有三种常用的存储结构，即孩子链表法，孩子兄弟链表法和____________。

6.n个顶点的连通图的生成树有__________条边。

7.一个有向图G中若有弧、和，则在图G的拓扑序列中，顶点的相对位置为___________。

8.设表中元素的初始状态是按键值递增的，分别用堆排序、快速排序、冒泡排序和归并排序方法对其进行排序(按递增顺序)，________最省时间，__________最费时间。

9.下面是将键值为x的结点插入到二叉排序树中的算法，请在划线处填上适当的内容。

Typedef struct pnode

{ int key;

struct node * left, * right;

}

Void search (int x; pnode t )

{ if (_____________)

{p = malloc (size);

p->key=x;p->left=NULL;

p->right=NULL;

t=p;

}

else

if (xkey) search (x,t->left)

else _________________

}

10.线性表的____________的主要优点是从表中任意结点出发都能访问到所有结点。而使用____________，可根据需要在前后两个方向上方便地进行查找。

三、应用题（每题10分，共30分）

1.在双链表中，要在指针变量P所指结点之后插入一个新结点，请按顺序写出必要的算法步骤。(设：P所指结点不是链表的首尾结点，q是与p同类型的指针变量)

2.已知待排序文件各记录的排序码顺序如下：

72 73 71 23 94 16 05 68

请列出快速排序过程中每一趟的排序结果。

四、算法题(共12分)

编写算法，实现单链表上的逆置运算(说明：即将单链表中的元素次序反转)

参考答案：

一、单项选择题（每题2分，共30分）

1.D 2.C 3.D 4.C 5.D 6.D 7.A 8.B 9.D 10.C 11.D 12.C 13.A 14.B 15.C

二、填空题（每空2分，共28分）

1. r->next=s; 2. p->next=NULL;

3. ls = = NULL; ls=ls->link。 4. 12

5. 双亲表示法 6. n-1

7. i,j,k 8. 冒泡排序，快速排序

9. t= =NULL，search（x,t->right）； 10.循环链表，双向链表

三、应用题（每题10分，共30分）

1．new(q)；

q↑.llink ← p；

q↑.rlink ← p↑.rlink；

p↑.rlink↑.llink ← q；

p↑.rlink ← q。

评分细则：按顺序每对一个给2分，全对计10分。

2．各趟结果如下：

[68 05 71 23 16] 72 [94 73]

[16 05 23] 68 [71] 72 [94 73]

[05] 16 [23] 68 [71] 72 [94 73]

05 16 [23] 68 [71] 72 [94 73]

05 16 23 68 71 72 [94 73]

05 16 23 68 71 72 [73] 94

05 16 23 68 71 72 73 94

四．算法题(共12分)

void invert（ pointer head）

{p=NULL;

while ( headNULL)

{u=head;

head=head->next;

u->next=p;

p=u;

}

head=p;

}

篇8：数据结构简历

目前所在：天河区年龄： 20

户口所在：汕头国籍：中国

婚姻状况：未婚民族：汉族

诚信徽章：未申请身高： 157 cm

人才测评：未测评体重：

人才类型：在校学生

应聘职位：幼教/保育员，家教，销售主管/销售代表/客户代表

工作年限： 1 职称：

求职类型：兼职可到职日期：随时

月薪要求：面议希望工作地区：天河区,越秀区,广州

工作经历

无起止年月：-10 ～ -05

公司性质：所属行业：

担任职位：作业指导

工作描述：辅导小学生作业，照顾小学生

广州地铁起止年月：2012-04 ～ 2012-05

担任职位：地铁志愿者

工作描述：

毕业院校：广东交通职业技术学院

最高学历：大专获得学位: 毕业日期： -06

专业一：软件技术专业二：

起始年月终止年月学校（机构）所学专业获得证书证书编号

语言能力

外语：英语良好粤语水平：一般

其它外语能力：

国语水平：优秀

工作能力及其他专长

熟悉计算机办公软件操作、C语言，数据结构，数据库原理，汇编语言，软件工程等Windows编程、网页制作

个人自传

性格开朗，成绩优良,乐于助人；善于与人交流、适应能力强、具有团体协作精神；喜欢运动

篇9：数据结构面试

1.判断链表是否存在环型链表问题：判断一个链表是否存在环，例如下面这个链表就存在一个环：

例如N1->N2->N3->N4->N5->N2就是一个有环的链表，环的开始结点是N5这里有一个比较简单的解法，设置两个指针p1，p2。每次循环p1向前走一步，p2向前走两步。直到p2碰到NULL指针或者两个指针相等结束循环。如果两个指针相等则说明存在环。

struct link

{

int data;

link* next;

};

bool IsLoop(link* head)

{

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);

if(p1 == p2)

return true;

else

return false;

}

2,链表反转单向链表的反转是一个经常被问到的一个面试题，也是一个非常基础的问题。比如一个链表是这样的： 1->2->3->4->5 通过反转后成为5->4->3->2->1。最容易想到的方法遍历一遍链表，利用一个辅助指针，存储遍历过程中当前指针指向的下一个元素，然后将当前节点元素的指针反转后，利用已经存储的指针往后面继续遍历。源代码如下：

struct linka {

int data;

linka* next;

};

void reverse(linka*& head)

{

if(head ==NULL)

return;

linka*pre, *cur, *ne;

pre=head;

cur=head->next;

while(cur)

{

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;

return p;

}

else

{

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;

while(start<=end)

{

mid=(start+end)/2;

if(a[i]==b[mid])

return true;

else if (a[i]

end=mid-1;

else

start=mid+1;

}

return false;

}

后来发现有一个 O(n)算法，

因为两个数组都是排好序的。所以只要一次遍历就行了。首先设两个下标，分别初始化为两个数组的起始地址，依次向前推进。推进的规则是比较两个数组中的数字，小的那个数组的下标向前推进一步，直到任何一个数组的下标到达数组末尾时，如果这时还没碰到相同的数字，说明数组中没有相同的数字。

bool findcommon2(int a[], int size1, int b[], int size2)

{

int i=0,j=0;

while(i

{

if(a[i]==b[j])

return true;

if(a[i]>b[j])

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 max_sub(int a[],int size)

{

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]

if(v>max)

max=v;

}

return max;

}

那怎样才能达到线性复杂度呢？这里运用动态规划的思想。先看一下源代码实现：

int max_sub2(int a[], int size)

{

int i,max=0,temp_sum=0;

for(i=0;i

{

temp_sum+=a[i];

if(temp_sum>max)

max=temp_sum;

else if(temp_sum<0)

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* mid(link* head)

{

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.javaeye.com/blog/163319

篇10：浅谈《数据结构》教学

浅谈《数据结构》教学

<数据结构>是高等院校计算机专业的一门重要专业基础课程,要求会分析和理解加工的数据对象特性,选择适当的.数据结构和存储结构及算法.要讲好这门课,可以从学生的听课率、课程的基础、重点和难点方面考虑,另外,师生之间的互动非常重要,最后要加强实践环节.

作者：毛养红作者单位：广州大学华软软件学院刊名：中国科技信息英文刊名：CHINA SCIENCE AND TECHNOLOGY INFORMATION 年，卷(期)： “”(5) 分类号：G64 关键词：数据结构教学模式教学方法

篇11：怎么学好数据结构

怎么学好数据结构

首先你要知道什么是数据结构，学习数据结构的意义。这将是你学习的动力所在。计算机软件都用到了数据结构。所以，学好数据结构对于你将来从事计算机编程类的工作有十分重要的作用。

数据结构中的基本概念，你要一定清楚。平时要多看书，要在计算机上去调试程序，在调试的过程中，你才能发现自己的问题，然后及时解决。在上机调试的过程中，更要大胆尝试，注重运用。拿到一个题时，更要深入分析，尝试用不同的算法去设计。当然编程的时候，要注意格式。比如：变量一定要先定义后使用。变量的定义不要定义在中间。

算法与数据结构是紧密联系，所以你算法一定要会。如果你是学生，只需把课本上出现的搞懂就好了，比如线性表的插入，删除，查找算法，它都是固定的。你就要理解，当然你要学会画图。对于书中的内容要熟悉。

数据结构的大纲如下：线性表、栈和队列，串、数组和广义表、树与森林、图、还有就是查找和排序。简单的总结一下也就是它的逻辑结构：线性结构和非线性结构。这些基本的内容你如果搞懂了，你的数据结构也就学好了。

要严格要求自己。在学习算法的过程中，你要想它为什么要这样设计?它的优点在哪里?想着去改进算法，慢慢的的你的逻辑思维能力也就提高了。你会发现其实数据结构也就那么回事，不是很难。

有不懂得地方要及时请教老师，不要不懂装懂。不要放过任何一个细节，因为我的专业就是计算机，所以有很多都是深有体会。

注意：

一、认真安排好你的时间

首先你要清楚一周内所要做的事情，然后制定一张作息时间表。在表上填上那些非花不可的时间，如吃饭、睡觉、上课、娱乐等。安排这些时间之后，选定合适的、固定的时间用于学习，必须留出足够的时间来完成正常的阅读和课后作业。当然，学习不应该占据作息时间表上全部的空闲时间，总得给休息、业余爱好、娱乐留出一些时间，这一点对学习很重要。一张作息时间表也许不能解决你所有的问题，但是它能让你了解如何支配你这一周的时间，从而使你有充足的时间学习和娱乐。

二、学习前先预习

这就意味着在你认真投入学习之前，先把要学习的内容快速浏览一遍，了解学习的大致内容及结构，以便能及时理解和消化学习内容。当然，你要注意轻重详略，在不太重要的地方你可以花少点时间，在重要的地方，你可以稍微放慢学习进程。

三、充分利用课堂时间

学习成绩好的学生很大程度上得益于在课堂上充分利用时间，这也意味着在课后少花些功夫。课堂上要及时配合老师，做好笔记来帮助自己记住老师讲授的内容，尤其重要的是要积极地独立思考，跟得上老师的思维。

四、学习要有合理的规律

课堂上做的笔记你要在课后及时复习，不仅要复习老师在课堂上讲授的重要内容，还要复习那些你仍感模糊的认识。如果你坚持定期复习笔记和课本，并做一些相关的习题，你定能更深刻地理解这些内容，你的记忆也会保持更久。定期复习能有效地提高你的考试成绩。

五、一个安静的、舒适的学习环境

选择某个地方作你的学习之处，这一点很重要。它可以是你的单间书房或教室或图书馆，但是它必须是舒适的，安静而没有干扰。当你开始学习时，你应该全神贯注于你的功课，切忌“身在曹营心在汉”。

六、树立正确的考试观

平时测验的目的主要看你掌握功课程度如何，所以你不要弄虚作假，而应心平气和地对待它。或许，你有一两次考试成绩不尽如人意，但是这不要紧，只要学习扎实，认真对待，下一次一定会考出好成绩来。通过测验，可让你了解下一步学习更需要用功夫的地方，更有助于你把新学的知识记得牢固。

篇12：数据结构试题

数据结构试题

一、选择题(30分)

1.下列程序段的时间复杂度为( )。

(A) O(m*n*t) (B) O(m+n+t) (C) O(m+n*t) (D) O(m*t+n)

2.设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动( )个元素。

(A) n-i (B) n+l -i (C) n-1-i (D) i

3.设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，T1、T2和T3的结点数分别为N1、N2和N3，则二叉树B的根结点的左子树的结点数为( )。

(A) N1-1 (B) N2-1 (C) N2+N3 (D) N1+N3

4.利用直接插入排序法的思想建立一个有序线性表的时间复杂度为( )。

(A) O(n) (B) O(nlog2n) (C) O(n2) (D) O(1og2n)

5.设指针变量p指向双向链表中结点A，指针变量s指向插入的结点X，则在结点A的后面插入结点X的操作序列为( )。

(A) p->right=s; s->left=p; p->right->left=s; s->right=p->right;

(B) s->left=p;s->right=p->right;p->right=s; p->right->left=s;

(D) s->left=p;s->right=p->right;p->right->left=s; p->right=s;

6.下列各种排序算法中平均时间复杂度为O(n2)是( )。

(A) 快速排序 (B) 堆排序 (C) 归并排序 (D) 冒泡排序

7.设输入序列1、2、3、…、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是( )。

(A) n-i (B) n-1-i (C) n+l -i (D) 不能确定

8.设散列表中有m个存储单元，散列函数H(key)= key % p，则p最好选择( )。

(A) 小于等于m的最大奇数 (B) 小于等于m的最大素数

9.设在一棵度数为3的树中，度数为3的结点数有2个，度数为2的结点数有1个，度数为1的结点数有2个，那么度数为0的结点数有( )个。

(A) 4 (B) 5 (C) 6 (D) 7

10.设完全无向图中有n个顶点，则该完全无向图中有( )条边。

(A) n(n-1)/2 (B) n(n-1) (C) n(n+1)/2 (D) (n-1)/2

11.设顺序表的长度为n，则顺序查找的平均比较次数为( )。

(A) n (B) n/2 (C) (n+1)/2 (D) (n-1)/2

12.设有序表中的元素为(13，18，24，35，47，50，62)，则在其中利用二分法查找值为24的元素需要经过( )次比较。

(A) 1 (B) 2 (C) 3 (D) 4

13.设顺序线性表的长度为30，分成5块，每块6个元素，如果采用分块查找，则其平均查找长度为( )。

(A) 6 (B) 11 (C) 5 (D) 6.5

14.设有向无环图G中的有向边集合E={<1，2>，<2，3>，<3，4>，<1，4>}，则下列属于该有向图G的一种拓扑排序序列的是( )。

(A) 1，2，3，4 (B) 2，3，4，1 (C) 1，4，2，3 (D) 1，2，4，3

15.设有一组初始记录关键字序列为(34，76，45，18，26，54，92)，则由这组记录关键字生成的二叉排序树的深度为( )。

(A) 4 (B) 5 (C) 6 (D) 7

二、填空题(30分)

1.设指针p指向单链表中结点A，指针s指向插入的结点X，则在结点A的前面插入结点X时的操作序列为：

1) s->next=___________;2) p->next=s;3) t=p->data;

4) p->data=___________;5) s->data=t;

2.设某棵完全二叉树中有100个结点，则该二叉树中有______________个叶子结点。

3.设某顺序循环队列中有m个元素，且规定队头指针F指向队头元素的前一个位置，队尾指针R指向队尾元素的当前位置，则该循环队列中最多存储_______队列元素。

4.对一组初始关键字序列(40，50，95，20，15，70，60，45，10)进行冒泡排序，则第一趟需要进行相邻记录的比较的次数为__________，在整个排序过程中最多需要进行__________趟排序才可以完成。

5.在堆排序和快速排序中，如果从平均情况下排序的速度最快的角度来考虑应最好选择_________排序，如果从节省存储空间的.角度来考虑则最好选择________排序。

6.设一组初始记录关键字序列为(20，12，42，31，18，14，28)，则根据这些记录关键字构造的二叉排序树的平均查找长度是_______________________________。

7.设一棵二叉树的中序遍历序列为BDCA，后序遍历序列为DBAC，则这棵二叉树的前序序列为____________________。

8.设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为7、19、2、6、32、3、21、10，根据这些频率作为权值构造哈夫曼树，则这棵哈夫曼树的高度为________________。

9.设一组记录关键字序列为(80，70，33，65，24，56，48)，则用筛选法建成的初始堆为_______________________。

10. 10. 设无向图G(如右图所示)，则其最小生成树上所有边的权值之和为_________________。

三、判断题(20分)

1.有向图的邻接表和逆邻接表中表结点的个数不一定相等。( )

2.对链表进行插入和删除操作时不必移动链表中结点。( )

3.子串“ABC”在主串“AABCABCD”中的位置为2。( )

4.若一个叶子结点是某二叉树的中序遍历序列的最后一个结点，则它必是该二叉树的先序遍历序列中的最后一个结点。( )

5.希尔排序算法的时间复杂度为O(n2)。( )

6.用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数无关而与图中边数有关。( )

7.中序遍历一棵二叉排序树可以得到一个有序的序列。( )

8.入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。( )

9.顺序表查找指的是在顺序存储结构上进行查找。( )

10.堆是完全二叉树，完全二叉树不一定是堆。( )

四、算法设计题(20分)

1.设计计算二叉树中所有结点值之和的算法。

2.设计将所有奇数移到所有偶数之前的算法。

3.设计判断单链表中元素是否是递增的算法。

篇13：精选实验报告

一、实验目的

熟悉应用PHOTOSHOP 在图形处理中的操作，

二、实验内容

按照样张的样子把两张素材文件合并为一个图像文件。保存文件为.psd (不得合并图层)

三、实验环境

实验应用系统及软件：WINDOWNS XP和PHOTOSHOP

四、实验步骤

1、从桌面上启动PHOTOSHOP

2、应用菜单栏中的“文件”菜单“打开”命令分别打开两个图形文件“城市风.JPG”和“云天.jpg”

3、应用“图象”—>“旋转画布”—>“水平反转画布”对文件“云天.jpg”进行转换。

4、使用方框工具选中中间图片，使用CTRL+j新建图层.

5、选择新建图层，并选择“魔术棒工具”大致选出“城市风光.jpg”文件中的建筑轮廓，并配合使用SHIFT、ALT键完成精细的选择。

6、使用“选择”菜单中的“反选”命令选中建筑图片拖动到云天图片中。

7、使用CTRL+T对图片进行自由变换使其符合云天图片大小。

8、保存文件名为xin.psd

五、实验结果

在实验中着重应用了PHOTOSHOP中的图片反转、图层的建立、图片中的扣图、图片的自由变换，基本达到了实验目标。

六、总结

实验过程中，开始我不知道如何去除图片中的背景、经过请教摸索终于掌握了其应用方法。个人方面我觉得初次接触PHOTOSHOP很有收获。

篇14：实验报告格式

学生实验报告书

实验课程名称开课学院指导教师姓名学生姓名学生专业班级

200

-- 200 学年第学期

实验教学管理基本规范

实验是培养学生动手能力、分析解决问题能力的重要环节;实验报告是反映实验教学水平与质量的重要依据。为加强实验过程管理，改革实验成绩考核方法，改善实验教学效果，提高学生质量，特制定实验教学管理基本规范。

1、本规范适用于理工科类专业实验课程，文、经、管、计算机类实验课程可根据具体情况参

照执行或暂不执行。

2、每门实验课程一般会包括许多实验项目，除非常简单的验证演示性实验项目可以不写实验

报告外，其他实验项目均应按本格式完成实验报告。

3、实验报告应由实验预习、实验过程、结果分析三大部分组成。每部分均在实验成绩中占一

定比例。各部分成绩的观测点、考核目标、所占比例可参考附表执行。各专业也可以根据具体情况，调整考核内容和评分标准。

4、学生必须在完成实验预习内容的前提下进行实验。教师要在实验过程中抽查学生预习情况，

在学生离开实验室前，检查学生实验操作和记录情况，并在实验报告第二部分教师签字栏签名，以确保实验记录的真实性。

5、教师应及时评阅学生的实验报告并给出各实验项目成绩，完整保存实验报告。在完成所有

实验项目后，教师应按学生姓名将批改好的各实验项目实验报告装订成册，构成该实验课程总报告，按班级交课程承担单位(实验中心或实验室)保管存档。 6、实验课程成绩按其类型采取百分制或优、良、中、及格和不及格五级评定。

实验课程名称：__通信原理_____________

更多相关热门文章推荐阅读：

篇15：实验报告格式

实验名称

要用最简练的语言反映实验的内容。如验证某程序、定律、算法，可写成“验证---”;分析---。

学生姓名、学号、及合作者

实验日期和地点(年、月、日)

实验目的

目的要明确，在理论上验证定理、公式、算法，并使实验者获得深刻和系统的理解，在实践上，掌握使用实验设备的技能技巧和程序的调试方法。一般需说明是验证型实验还是设计型实验，是创新型实验还是综合型实验。

实验原理

在此阐述实验相关的主要原理。

实验内容

这是实验报告极其重要的内容。要抓住重点，可以从理论和实践两个方面考虑。这部分要写明依据何种原理、定律算法、或操作方法进行实验。详细理论计算过程。

篇16：实验报告格式

只写主要操作步骤，不要照抄实习指导，要简明扼要。还应该画出实验流程图(实验装置的结构示意图)，再配以相应的文字说明，这样既可以节省许多文字说明，又能使实验报告简明扼要，清楚明白。

实验结果

实验现象的描述，实验数据的处理等。原始资料应附在本次实验主要操作者的实验报告上，同组的合作者要复制原始资料。

对于实验结果的表述，一般有三种方法:

1. 文字叙述: 根据实验目的将原始资料系统化、条理化，用准确的专业术语客观地描述实验现象和结果，要有时间顺序以及各项指标在时间上的关系。

2. 图表: 用表格或坐标图的方式使实验结果突出、清晰，便于相互比较，尤其适合于分组较多，且各组观察指标一致的实验，使组间异同一目了然。每一图表应有表目和计量单位，应说明一定的中心问题。

3. 曲线图

应用记录仪器描记出的曲线图，这些指标的变化趋势形象生动、直观明了。

在实验报告中，可任选其中一种或几种方法并用，以获得最佳效果。

讨论

根据相关的理论知识对所得到的实验结果进行解释和分析。如果所得到的实验结果和预期的结果一致，那么它可以验证什么理论?实验结果有什么意义?说明了什么问题?这些是实验报告应该讨论的。但是,不能用已知的理论或生活经验硬套在实验结果上;更不能由于所得到的实验结果与预期的'结果或理论不符而随意取舍甚至修改实验结果，这时应该分析其异常的可能原因。如果本次实验失败了，应找出失败的原因及以后实验应注意的事项。不要简单地复述课本上的理论而缺乏自己主动思考的内容。

另外，也可以写一些本次实验的心得以及提出一些问题或建议等。

结论

结论不是具体实验结果的再次罗列，也不是对今后研究的展望，而是针对这一实验所能验证的概念、原则或理论的简明总结，是从实验结果中归纳出的一般性、概括性的判断,要简练、准确、严谨、客观。

★ 实验报告