数据结构实验学期总结
摘要：
本学期我完成的主要实验任务有：裴波那锲序列、约瑟夫环、表达式求值、赫夫曼编码
文档内容：本学期以来，我所完成的所有实验及其总结，分别包括实验名称、实验目的及要求、实验主要内容、实验结果结论、实验分析，还有我对该课程学习总结和建议。
关键字：
数据结构实验总结数组链表栈二叉树
实验一
实验名称：裴波那锲序列
实验目的及要求：
1. 熟悉开发工具的编程环境。
2. 体会算法和程序的不同。
3. 学习用不同算法实现同一程序功能，并能熟练编程实现。
4. 学习分析算法。对比不同算法实现的效率有何不同，所占空间有何
不同。对比不同算法的优点和缺点
实验主要内容：
概要设计和存储结构
K阶（k>=2）裴波那契序列的第m项值假设为sum，则： sum(m) =sum(m-1)+sum(m-2)+……+sum(m-k)
=sum(m-1)+sum(m-2)+……+sum(m-k)+sum(m-k-1)-sum(m
-k-1)
=sum(m-1)+[sum(m-2)+……+sum(m-k)+sum(m-k-1)]-sum
(m-k-1)
=2*sum(m-1)-sum(m-k-1)
所以最后return返回的是2*f(m-1,k)-f(m-k-1,k)，如此便实现了裴
波那契序列第m 项的计算。
下面程序段中@语句的时间复杂度为：O(sum)=2(m-k) (m>k) 程序中未曾使用线性表或链表结构
主要算法
int f(int m,int k){ if(m<=k-1) return 0;
else if(m==k+1||m==k) return 1;
@ else return (2*f(m-1,k)-f(m-k-1,k)); } //f( )函数实现裴波那契序列
实验结果和结论
实验分析：
通过建立一个f( )函数，用递归的方式来实现第m 项输出的值，本次程序的设计因为采用了递归调用，所以速度相对比非递归要慢了些。
实验二
实验通过三组数据的测试，基本实现了实验要求的功能，经过几次的修改后，自己没有再发现什么bug 了，感觉还是很满意的
实验名称：约瑟夫环
实验目的及要求：
通过实习题的上机实践，帮助学生掌握线性表的基本操作在两种存储结构上算法的实现，特别是链表，实验以各类链表的操作和应用作为重点。
采用循环单链表作为存储结构，按照出列的顺序打印出各人的编号
实验主要内容：
概要设计和存储结构
分三个模块：自主定义的二个函数以及一个主函数
Creat函数目的在于建立一个循环链表
Count是实现本程序所要求的主要功能
而主函数main通过依次调用以上函数完成程序
Struct huan* creat (int n) 是用于构建一个单循环动态链表，通过malloc 开辟一个结构体结点，在main（）中通过由循环语句for将其连接成一个循环链表
struct huan{
int num;
int data;
struct huan *next;
}；定义的结构体形式
Struct huan* creat (int n) 创建一个单循环链表，目的用来存放人的位置及密码
void count(struct huan* head,int n) 实现约瑟夫环的功能 主要算法
struct huan* creat(int n)
{//创建一个单循环链表，目的用来存放人的位置及密码
struct huan* head;
if((head=(struct huan*)malloc(sizeof(struct huan)))==NULL) return NULL;
head->num=n;
//可以替换下一句head->data=rand()%100+1;密码随机产生
scanf("%d",&head->data);
return head;
}//creat
/*实现出列功能*/
void count(struct huan* head,int n)
{
struct huan *p2=head,*p1;
for(;p2->next!=head;p2=p2->next);
p1=p2->next;
int code;
printf("\n请输入起始密码:\n");
scanf("%d",&code);
int pas=code%n;
printf("出列次序:\n位置密码\n");
while(n>1)
{if(pas==0) pas=n;
for(int i=1;i
p2->next=p1->next;
printf(" %d\t%d\n",p1->num,p1->data);
code=p1->data;
free(p1);
p1=p2->next;
n--;
pas=code%n;
}
printf(" %d\t%d\n",p1->num,p1->data);
free(p1);
}//count
实验结果和结论
实验要求完成的功能已经全部完成了，但是对于手动输入密码和随机产生密码这两种功能没能够通过程序选择来完成
实验分析：
可以看出这一题是考查单链表的应用，而且这一题中的循环单链表是不需要“头结点”的，要注意空表和非空表的界限。程序运行后要求用户指定初始报数上界值，人数及各人的密码。可先设n≤30。
实验三
实验名称：表达式求值
实验目的及要求：
通过上机实践掌握队列和栈的顺序存储结构和链式存储结构，以便我们能在相应的应用问题中正确选用它们；掌握栈和队列的特点，即先进后出与先进先出的原则；掌握栈和队列的基本运算，如入栈和出栈、入队与出队等运算在顺序存储结构和链式存储结构上的实现。
以字符序列形式从终端输入语法正确的、不含变量的整数表达式。利用课本3.2.5节中给出的算符优先关系，实现对算术四则混合运算表达式的求值，并仿照课本上的例子演示在求值过程中运算符栈、运算数栈、输入字符和主要操作的变化过程。
实验主要内容：
概要设计和存储结构
构建了两个栈OPTR, OPND（OPTR为运算符栈，OPND为运算数栈）typedef struct
{
ElemType *base;
ElemType *top;
int stacksize;
}Stack;//定义栈类型
int IfEmptyStack(Stack S);//判断栈是否为空
void InitStack(Stack &S);//构建一个栈
void EmptyStack(Stack &S);//栈空时，则返回值
void Push(Stack &S, ElemType e); //插入元素e为新的栈顶元素
void Pop(Stack &S, ElemType &e); //若栈不空，则删除s的栈顶元素，用e 返回其值
void ShowStack(Stack S); //输出计算结果
int In(char ch); //判断字符ch是不是运算符
char Precede(char a,char b);//判定运算符栈顶运算符a与读入b之间优先权int Operate(int a, char f, int b); //进行二元运算的函数
void EvaluateExpression();//算术表达式求值的算符优先算法
main函数调用EvaluateExpression，EvaluateExpression嵌套调用以上各函数 主要算法
int IfEmptyStack(Stack S) {//判断栈是否为空，是则返回1，否则返回0
if(S.base==S.top)
return 1;
return 0;
}
void InitStack(Stack &S) {//构建一个空栈s
S.base=(ElemType
*)malloc(STACK_INIT_SIZE*si zeof(ElemType));
S.top=S.base;
S.stacksize=STACK_INIT_SIZE ;
return ;
}
void EmptyStack(Stack &S) {//若栈为空，则返回值
S.top=S.base; return ;
}
void Push(Stack &S, ElemType e)
{//插入元素e为新的栈顶元素
if(S.top-S.base>=S.stacksiz e)
{//栈满，追加存储空间
S.base=(ElemType*)realloc(S .base,
(S.stacksize+S TACKINCREMENT)*sizeof(ElemT ype));
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT ;
}
*S.top++=e;
return ;
}//Push
void Pop(Stack &S, ElemType &e)
{//若栈不空，则删除s的栈顶元素，用e返回其值
if(S.top==S.base)
return ;
e=*--S.top;
return ;
}
ElemType GetTop(Stack &S) {//栈不空，返回栈顶元素
if(S.top==S.base)
return 0;
return *(S.top-1);
}
void ShowStack(Stack S)
{//输出计算结果
ElemType *p=S.base;
while(p!=S.top)
printf("%d",*p++);
return;
} int In(char ch)
{//判断字符ch是不是运算符
int res;
switch(ch)
{
case '+':
case '-':
case '*':
case '/':
case '(':
case ')':
case '=': res=1;break; default: res=0;break;
}
return res;
}
char Precede(char a, char b) {//判定运算符的栈顶运算符a 与读入b之间优先权
int i,j;
int OP[7][7]=
{
{1,1,-1,-1,-1,1,1},{1,1
,-1,-1,-1,1,1},{1,1,1,1
,-1,1,1},{1,1,1,1,-1,1,
1},
{-1,-1,-1,-1,-1,0,2},{1
,1,1,1,2,1,1},
{-1,-1,-1,-1,-1,2,0}
};
switch(a)
{
case '+':i=0;break;
case '-':i=1;break;
case '*':i=2;break;
case '/':i=3;break;
case '(':i=4;break;
case ')':i=5;break;
case '=':i=6;break;
}
switch(b)
{
case '+':j=0;break;
case '-':j=1;break;
case '*':j=2;break;
case '/':j=3;break;
case '(':j=4;break;
case ')':j=5;break;
case '=':j=6;break;
}
if(OP[i][j]==1)
return '>';
else if(OP[i][j]==-1)
return '<';
else if(OP[i][j]==2)
{ printf("表达式输入错误！\n");
system("pause");
exit (0);
}
else if(OP[i][j]==0)
return '=';
}//Precede
int Operate(int a, char f, int b)
{//进行二元运算的函数
switch(f)
{
case '+': return a+b; case '-': return a-b; case '*': return a*b; case '/': return a/b; }
return 0;
}//Operate
void EvaluateExpression() {//算术表达式求值的算符优先算法
char c, d[100];
int i, f,num, tmpa, tmpb; Stack OPTR, OPND;//OPTR为运算符栈，OPND为运算数栈
InitStack(OPTR);InitStack(O PND);
Push(OPTR, '=');
c=getchar();
while(c!='='||GetTop(OPTR)!
='=')
{
if(c>='0'&&c<='9')
{
i=0;
do{
d[i++]=c;
c=getchar();
}while(c>='0'&&c
<='9');
d[i]='\0';
num=atoi(d);
Push(OPND, num);
}//if
else if(In(c))
{
switch(Precede(GetTop(OPTR), c))
{
case '<': Push(OPTR, (int)c);c=getchar(); break; case '=': Pop(OPTR, f);c=getchar(); break;
case '>': Pop(OPTR, f);Pop(OPND, tmpb);Pop(OPND, tmpa);
Push(OPND, Operate(tmpa, f, tmpb));
break;
}//switch
}//else if
}//while
c=getchar();//接收最后输入的一个回车符，否则在主函数中只能输入一次
printf("计算结果为: ");
ShowStack(OPND);
printf("\n");
}//EvaluateExpression
所有的运算数都定义为整型，运算符定义为字符型
实验结果和结论
程序在表达式输入错误即括号不相匹配时能够报错了,并结束程序。但是在连续输入‘+’，‘-’，‘*’，‘/’时，程序不能够报错还是能够给出计算结果（如截图4所示）
实验分析：
显然要先考虑所用到的栈存储结构，以及栈的初始化、出栈、入栈、取栈顶元素等一系列的栈的基本操作的实现，以便生成运算符栈和操作数栈，及实现算符优先法的算法。注意，在读入表达式的字符序列的同时完成运算符和操作数的识别处理，以及相应的运算。在识别操作数的同时，别忘记将字符序列形式转换成整数形式！还要在程序的适当位置输出运算符栈、操作数栈、输入字符和主要操作的内容。有可能的话，还要考虑用户输入表达式时可能会犯的简单的语法错误，给予适当的提示，象括号不匹配、错误的运算符之类。
实验四
实验名称：赫夫曼编码
实验目的及要求：
通过上机实践，帮助学生进一步掌握指针变量和动态变量的含义，掌握二叉树的结构特性，以及各种存储结构的特点及适用范围，掌握用指针类型描述、访问和处理二叉树的运算
一个完整的系统应具有以下功能：
（1）初始化。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存储于文件hfmtree中。
（2）编码。利用建好的哈夫曼树，对要传输的文件tobefile中的正文进行编码，然后将结果存入另一个文件codefile中。
（3）译码。利用建好的哈夫曼树将文件codefile中的代码进行译码，结果存入文件文件textfile中。
（4）印代码文件。将文件codefile以紧凑格式显示在终端屏幕上，每行50个代码，同时将此字符形式的编码文件写入文件codeprin中。
（5）印哈夫曼树。将已在内存中的哈夫曼树以直观的形式（树或凹入表或其它形式）显示在终端上，同时将此字符形式的哈夫曼树写入文
件treeprint中。
实验主要内容：
概要设计和存储结构
赫夫曼树中没度1的结点，则n个叶子结点的赫夫曼树共有2n-1个结
点，可以存储在一个大小为2n-1的一维数组中。为求编码需从叶子结点出
发走一条从叶子到根的路径；而为译码需从根出发走一条从根到叶子的路
径。
故建立存储如下：
typedef struct
{ unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; /* 动态分配数组存储赫夫曼树 */
typedef char **HuffmanCode; /* 动态分配数组存储赫夫曼编码表 */
向量HT的前n个分量表示叶子结点，最后一个分量表示根结点。各字符的编码长度不等，所以按实际长度动态分配空间。
程序中总共建立了四个模块：
int min(HuffmanTree t,int i)
void select(HuffmanTree t,int i,int *s1,int *s2)
void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,int n) int main()
select函数调用min函数选择两个权值最小的结点
HuffmanCoding函数调用select函数将权值小的两个结点连接起来，算出编码
Main函数调用HuffmanCoding函数实现整个程序的功能
主要算法
typedef struct
{ unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; /* 动态分配数组存储赫夫曼树 */ typedef char **HuffmanCode; /* 动态分配数组存储赫夫曼编码表 */
int min(HuffmanTree t,int i)
{ /* 函数void select()调用 */
int j,flag;
unsigned int k=UINT_MAX; /* 取k为不小于可能的值 */
for(j=1;j<=i;j++)
if(t[j].weight k=t[j].weight,flag=j; t[flag].parent=1; return flag; } void select(HuffmanTree t,int i,int *s1,int *s2) { /* s1为最小的两个值中序号小的那个 */ int j; *s1=min(t,i); *s2=min(t,i); if(*s1>*s2) {j=*s1; *s1=*s2; *s2=j;} } void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,int n) { /* w存放n个字符的权值(均>0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC*/ int m,i,s1,s2,start; unsigned c,f; HuffmanTree p; char *cd; if(n<=1)return; m=2*n-1; *HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /* 0号单元未用 */ for(p=*HT+1,i=1;i<=n;++i,++p,++w) { (*p).weight=*w; (*p).parent=(*p).lchild=(*p).rchild=0; } for(;i<=m;++i,++p) (*p).weight=(*p).parent=(*p).lchild=(*p).rchild=0; for(i=n+1;i<=m;++i) /* 建赫夫曼树 */ { /*在HT[1~i-1]中选择parent为0且weight最小的两个结点,其序号分别为s1和s2 */ select(*HT,i-1,&s1,&s2); (*HT)[s1].parent=(*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个字符编码的头指针向量([0]不用) */ 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); /* 释放工作空间 */ } 实验结果和结论 通过截图可看出：以上数据基本正确，但是第四张图在遇到两个或两个以上相同最大权值时，计算的结果不正确，但是还没发纠正过来。 实验分析： 注意编码结果是以文本文件的方式存储在文件codefile中！为方便用户，界面可以设计成具有几种功能的菜单样式。在程序的一次执行过程中，第一次执行初始化、编码或译码命令之后，哈夫曼树已经存在于内存中，不必再读入，每次执行中不一定都要执行初始化命令，因为文件hfmtree可能早已建好了。 综合分析部分 相关理论及实验结论 本学期通过对数据结构的学习，我对线性表、树有了很深的了解，再通过几个实验使我深刻的明白这门课程的重要性。下面简单介绍我做的实验。 数据结构是相互之间存在的一种或多种特定关系的数据元素的集合。数据结构在计算机中的表示称为数据的物理结构又称为存储结构。它包括数据元素的表示和关系的表示。在计算机中表示信息的最小单位是二进制数的一位，叫做位，在计算机中，我们可以用一个由若干位组合起来形成的一位串表示一个数据元素，通常称这个位串为元素或结点。当数据元素由若干数据项组成时，位串中对应于各个数据项的子位串称为数据域。数据元素之间的关系在计算机中有两种不同的表示方法：顺序映像和非顺序映像，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。顺序映像的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系；非顺序映像的特点是借助指示元素存储地址的指针表示数据元素之间的逻辑关系。 而算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每条指令表示一个或多个操作；此外，一个算法还具有下列5个重要特性：有穷性，确定性，可行性，输入，输出。 而算法设计的要求： 正确性，可读性，健壮性，效率和低存储量需求。 我做的第一个实验是裴波那锲序列，该函数主要通过递归调用来实现的。 存储结构是顺序存储，构建的是顺序线性表。 而线性表是最常用且最简单的一种数据结构。简言之，一个线性表是n 个数据元素的有限序列。线性表有顺序表示和链式表示两种实现：顺序存储结构的线性表称为顺序表，特点是，为表中相邻的元素的存储位置也相邻； 线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，链式存储结构的线性表有单链表、循环链表、双向链表等。 我的第二个实验是约瑟夫环，该实验是通过建立一个链表来存储数据的。 在该实验中我明白指针的使用要时刻注意指针的位置，以及建立了多少个数据结点，和有没有够成环结构...... 栈是限定仅在表尾进行插入和删除操作的线性表，可称为先进后出的线性表，表尾称为栈顶，表头端称为栈底。栈也有两种存储表示方法，一种是顺序栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素； 另一种是链表栈。与栈相反的是队列，一种先进先出的线性表，允许插入的一端叫做队尾，允许删除的一端叫做队头，种类有线性队列、双端队列、链队列、循环队列。 表达式求值是我完成的第三个实验。为完成字符和运算符的存储，我建立了两个栈，同时我还开辟了一个数组用来存储运算符之间的优先级。 树形结构是一类重要的非线性数据结构，其中树与二叉树最为常用。赫夫曼树又称为最优树，是一类带权路劲长度最短的树。 赫夫曼编码便是最后一个实验了，到了此时也就意味着学期即将结束了，回顾自己对数据结构的学习，感觉这课还真是难学啊，还那么重要。 自我总结和你对课程的建议 经过一学期的学习，我觉得自己收获颇丰。首先，自己当初C语言学的不够扎实，通过数据结构的学习加强了我对C语言的了解和运用；其次，数据结构让我懂得了如何在编程时尽量减少内存的消耗，而不是仅仅完成程序就行的；最后，就是数据结构让我明白想学好数据结构就必须加强数学的功底。 课程建议：因为数据结构很重要，根据平时的学习发现课时似乎不够，在最后查找排序的章节老师上的有些“赶”，学生不太容易吸收。所以建议学校能够增加些课时，这样老师也有足够的教学时间，讲课也可以讲的更加详细些。 《数据结构课程实验》大纲 一、《数据结构课程实验》的地位与作用 “数据结构”是计算机专业一门重要的专业技术基础课程，是计算机专业的一门核心的关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用的多种查找和排序技术，并做了性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因，使得掌握这门课程具有较大的难度： （1）内容丰富，学习量大，给学习带来困难； （2）贯穿全书的动态链表存储结构和递归技术是学习中的重点也是难点； （3）所用到的技术多，而在此之前的各门课程中所介绍的专业性知识又不多，因而加大了学习难度； （4）隐含在各部分的技术和方法丰富，也是学习的重点和难点。 根据《数据结构课程》课程本身的技术特性，设置《数据结构课程实验》实践环节十分重要。通过实验实践内容的训练，突出构造性思维训练的特征, 目的是提高学生组织数据及编写大型程序的能力。实验学时为18。 二、《数据结构课程实验》的目的和要求 不少学生在解答习题尤其是算法设计题时，觉得无从下手，做起来特别费劲。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。 为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法，如算法设计的构思方法，动态链表，算法的编码，递归技术，与特定问题相关的技术等，要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。在掌握基本算法的基础上，掌握分析、解决实际问题的能力。 三、《数据结构课程实验》内容 课程实验共18学时，要求完成以下六个题目： 实习一约瑟夫环问题（2学时） 数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include 数据结构实验报告全集 实验一线性表基本操作和简单程序 1 ．实验目的 （1 ）掌握使用Visual C++ 6.0 上机调试程序的基本方法； （2 ）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2 ．实验要求 （1 ）认真阅读和掌握和本实验相关的教材内容。 （2 ）认真阅读和掌握本章相关内容的程序。 （3 ）上机运行程序。 （4 ）保存和打印出程序的运行结果，并结合程序进行分析。 （5 ）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include iostream.h>// 头文件 #include nodetype *create()// 建立单链表，由用户输入各结点data 域之值， // 以0 表示输入结束 { elemtype d;// 定义数据元素d nodetype *h=NULL,*s,*t;// 定义结点指针 int i=1; cout<<" 建立一个单链表"< 数据结构实验总结报告 一、调试过程中遇到哪些问题？ （1）在二叉树的调试中，从广义表生成二叉树的模块花了较多时间调试。 由于一开始设计的广义表的字符串表示没有思考清晰，处理只有一个孩子的节点时发生了混乱。调试之初不以为是设计的问题，从而在代码上花了不少时间调试。 目前的设计是： Tree = Identifier(Node,Node) Node = Identifier | () | Tree Identifier = ASCII Character 例子：a(b((),f),c(d,e)) 这样便消除了歧义，保证只有一个孩子的节点和叶节点的处理中不存在问题。 （2）Huffman树的调试花了较长时间。Huffman编码本身并不难处理，麻烦的是输入输出。①Huffman编码后的文件是按位存储的，因此需要位运算。 ②文件结尾要刷新缓冲区，这里容易引发边界错误。 在实际编程时，首先编写了屏幕输入输出（用0、1表示二进制位）的版本，然后再加入二进制文件的读写模块。主要调试时间在后者。 二、要让演示版压缩程序具有实用性，哪些地方有待改进？ （1）压缩文件的最后一字节问题。 压缩文件的最后一字节不一定对齐到字节边界，因此可能有几个多余的0，而这些多余的0可能恰好构成一个Huffman编码。解码程序无法获知这个编码是否属于源文件的一部分。因此有的文件解压后末尾可能出现一个多余的字节。 解决方案： ①在压缩文件头部写入源文件的总长度（字节数）。需要四个字节来存储这个信息（假定文件长度不超过4GB）。 ②增加第257个字符（在一个字节的0~255之外）用于EOF。对于较长的文件， 会造成较大的损耗。 ③在压缩文件头写入源文件的总长度%256的值，需要一个字节。由于最后一个字节存在或不存在会影响文件总长%256的值，因此可以根据这个值判断整个压缩文件的最后一字节末尾的0是否在源文件中存在。 （2）压缩程序的效率问题。 在编写压缩解压程序时 ①编写了屏幕输入输出的版本 ②将输入输出语句用位运算封装成一次一个字节的文件输入输出版本 ③为提高输入输出效率，减少系统调用次数，增加了8KB的输入输出缓存窗口 这样一来，每写一位二进制位，就要在内部进行两次函数调用。如果将这些代码合并起来，再针对位运算进行一些优化，显然不利于代码的可读性，但对程序的执行速度将有一定提高。 （3）程序界面更加人性化。 Huffman Tree Demo (C) 2011-12-16 boj Usage: huffman [-c file] [-u file] output_file -c Compress file. e.g. huffman -c test.txt test.huff -u Uncompress file. e.g. huffman -u test.huff test.txt 目前的程序提示如上所示。如果要求实用性，可以考虑加入其他人性化的功能。 三、调研常用的压缩算法，对这些算法进行比较分析 （一）无损压缩算法 ①RLE RLE又叫Run Length Encoding，是一个针对无损压缩的非常简单的算法。它用重复字节和重复的次数来简单描述来代替重复的字节。尽管简单并且对于通常的压缩非常低效，但它有的时候却非常有用（例如，JPEG就使用它）。 变体1：重复次数+字符 文本字符串：A A A B B B C C C C D D D D，编码后得到：3 A 3 B 4 C 4 D。 中南民族大学管理学院学生实验报告 实验项目: 约瑟夫问题 课程名称：数据结构 年级： 专业：信息管理与信息系统 指导教师： 实验地点：管理学院综合实验室 完成日期： 小组成员： 2012 学年至2013 学年度第1 学期 一、实验目的 （1）掌握线性表表示和实现； （2）学会定义抽象数据类型； （3）学会分析问题，设计适当的解决方案； 二、实验内容 【问题描述】：编号为1,2,…,n的n 个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自 1 开始顺序报数，报到m 时停止报数。报m 的人出列，将他的密码作为新的m 值，从他在顺时针方向上的下一个人开始重新从1 报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 【基本要求】：利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。 【测试数据】：m 的初值为20；密码：3，1，7，2，4，8，4（正确的结果应为6，1，4，7，2，3，5）。 三、实验步骤 （一）需求分析 对于这个程序来说，首先要确定构造链表时所用的插入方法。当数到m 时一个人就出列，也即删除这个节点，同时建立这个节点的前节点与后节点的联系。由于是循环计数，所以才采用循环列表这个线性表方式。 程序存储结构利用单循环链表存储结构存储约瑟夫数据（即n个人的编码等），模拟约瑟夫的显示过程，按照出列的顺序显示个人的标号。编号为1,2,…,n 的 n 个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值 m，从第一个人开始按顺时针方向自1 开始顺序报数，报到 m 时停止报数。报 m 的人出列，将他的密码作为新的 m 值，从他在顺时针方向上的下一个人开始重新从 1 报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。基本要求是利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。 程序执行的命令（1）构造单向循环链表。 （2）按照出列的顺序引出各个人的标号。 测试数据 m 的初值为 20；密码：3，1，7，2，4，8，4（正确的结果应为 6，1，4，7，2，3，5） （1）、插入：在把元素插入到循环链表中时，由于是采用的头插法，所以我保留了front头结点。在每加入一个节点时，都会直接连接在front后面，从而保证一开始就赋值的rear尾节点不用修改。 伪代码阐释如下： 数据结构实验总结报告 李博杰PB10000603 一、调试过程中遇到哪些问题？ （1）在二叉树的调试中，从广义表生成二叉树的模块花了较多时间调试。 由于一开始设计的广义表的字符串表示没有思考清晰，处理只有一个孩子的节点时发生了混乱。调试之初不以为是设计的问题，从而在代码上花了不少时间调试。 目前的设计是： Tree = Identifier(Node,Node) Node = Identifier | () | Tree Identifier = ASCII Character 例子：a(b((),f),c(d,e)) 这样便消除了歧义，保证只有一个孩子的节点和叶节点的处理中不存在问题。 （2）Huffman树的调试花了较长时间。Huffman编码本身并不难处理，麻烦的是输入输出。 ①Huffman编码后的文件是按位存储的，因此需要位运算。 ②文件结尾要刷新缓冲区，这里容易引发边界错误。 在实际编程时，首先编写了屏幕输入输出（用0、1表示二进制位）的版本，然后再加入二进制文件的读写模块。主要调试时间在后者。 二、要让演示版压缩程序具有实用性，哪些地方有待改进？ （1）压缩文件的最后一字节问题。 压缩文件的最后一字节不一定对齐到字节边界，因此可能有几个多余的0，而这些多余的0可能恰好构成一个Huffman编码。解码程序无法获知这个编码是否属于源文件的一部分。因此有的文件解压后末尾可能出现一个多余的字节。 解决方案： ①在压缩文件头部写入源文件的总长度（字节数）。需要四个字节来存储这个信息（假定文件长度不超过4GB）。 ②增加第257个字符（在一个字节的0~255之外）用于EOF。对于较长的文件，会造成较大的损耗。 ③在压缩文件头写入源文件的总长度%256的值，需要一个字节。由于最后一个字节存在或不存在会影响文件总长%256的值，因此可以根据这个值判断整个压缩文件的最后一字节末尾的0是否在源文件中存在。 （2）压缩程序的效率问题。 在编写压缩解压程序时 ①编写了屏幕输入输出的版本 ②将输入输出语句用位运算封装成一次一个字节的文件输入输出版本 ③为提高输入输出效率，减少系统调用次数，增加了8KB的输入输出缓存窗口 这样一来，每写一位二进制位，就要在内部进行两次函数调用。如果将这些代码合并起来，再针对位运算进行一些优化，显然不利于代码的可读性，但对程序的执行速度将有一定提高。 数据结构课程设计 ——停车场管理问题 姓名: 学号: 问题描述 设有一个可以停放n辆汽车的狭长停车场，它只有一个大门可以供车辆进出。车辆按到达停车场时间的早晚依次从停车场最里面向大门口处停放（最先到达的第一辆车放在停车场的最里面）。如果停车场已放满n辆车，则后来的 车辆只能在停车场大门外的便道上等待，一旦停车场内有车开走，则排在便道上的第一辆车就进入停车场。停车场内如有某辆车要开走，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车辆再依原来的次序进场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车未进停车场就要离去，允许其离去，不收停车费，并且仍然保持在便道上等待的车辆的次序。编制一程序模拟该停车场的管理。 二、实现要求 要求程序输出每辆车到达后的停车位置（停车场或便道上），以及某辆车离开停车场时应交纳的费用和它在停车场内停留的时间。 三、实现提示 汽车的模拟输入信息格式可以是：（到达/离去，汽车牌照号码，到达/离去的时刻）。例如，（‘A'，，1，5）表示1号牌照车在5这个时刻到达，而（‘ D '，，5，20）表示5号牌照车在20这个时刻离去。整个程序可以在输入信息为（‘ E '，0，0）时结束。本题可用栈和队列来实现。 四、需求分析 停车场采用栈式结构，停车场外的便道采用队列结构（即便道就是等候队列）。停车场的管理流程如 下 ①当车辆要进入停车场时，检查停车场是否已满，如果未满则车辆进栈（车辆进入停车场）；如果停车场已满，则车辆进入等候队列（车辆进入便道等候）。 ②当车辆要求出栈时，该车到栈顶的那些车辆先弹出栈（在它之后进入的车辆必须先退出车场为它让路），再让该车出栈，其他车辆再按原次序进栈（进入车场）。当车辆出栈完毕后，检查等候队列（便道） 中是否有车，有车则从队列头取出一辆车压入栈中。 2009级数据结构实验报告 实验名称：约瑟夫问题 学生姓名：李凯 班级：21班 班内序号：06 学号：09210609 日期：2010年11月5日 1．实验要求 1）功能描述：有n个人围城一个圆圈，给任意一个正整数m，从第一个人开始依次报数，数到m时则第m个人出列，重复进行，直到所有人均出列为止。请输出n个人的出列顺序。 2）输入描述：从源文件中读取。 输出描述：依次从显示屏上输出出列顺序。 2. 程序分析 1）存储结构的选择 单循环链表 2）链表的ADT定义 ADT List{ 数据对象：D={a i|a i∈ElemSet,i=1,2,3,…n,n≧0} 数据关系：R={< a i-1, a i>| a i-1 ,a i∈D,i=1,2,3,4….,n} 基本操作： ListInit(&L)；//构造一个空的单链表表L ListEmpty(L); //判断单链表L是否是空表，若是，则返回1，否则返回0. ListLength(L); //求单链表L的长度 GetElem（L，i）；//返回链表L中第i个数据元素的值； ListSort(LinkList [内容要求] 1、存储结构：顺序表、单链表或其他存储结构，需要画示意图，可参考书上P59 页图2-9 2.2 关键算法分析 结点类： template 数据结构实验报告 第次实验 学号： 20141060106 姓名：叶佳伟 一、实验目的 1、复习二叉树的逻辑结构、存储结构及基本操作； 2、掌握二叉链表及二叉树的创建、遍历； 3、了解二叉树的应用。 二、实验内容 1、（必做题）假设二叉树中数据元素类型是字符型，请采用二叉链表实现二叉树的以下基本操作： （1）根据二叉树的先序序列和中序序列构造二叉树； （2）根据先序遍历二叉树； （3）根据中序遍历二叉树； （4）根据后序遍历二叉树。 测试数据包括如下错误数据： 先序：1234；中序：12345 先序：1234；中序：1245 先序：1234；中序：4231 2、（必做题）对于一棵二叉树，请实现： （1）计算二叉树的叶子数目； （2）计算二叉树的深度。 三、算法描述 （采用自然语言描述） 1、先构造一个二叉树的结构体，再构造createtree的函数实现数据的输入。在键盘上输入先序和中序序列。先判断先序和后序序列是否符合逻辑。若符合逻辑，则在先序、中序、后序函数将二叉树输出。 四、详细设计 （画出程序流程图） 五、程序代码 （给出必要注释） #define max 5 #define TEL 2*max+1 #include "stdio.h" #include "stdlib.h" #include "string.h" typedef char TElemType; typedef struct BiTNode{ TElemType data; //数据域 struct BiTNode *lchild, *rchild; //左右孩子指针域 } BiTNode, *BiTree; BiTNode root; BiTree rt=&root; int calculate(char c,char s[],int st) {char *p; p=s+st; while(*p!=c && *p!='\0') p++; return p-s; } void createtree(BiTree *t,int i1,int i2,int len,char preorder[],char pinorder[]) {int r,llen,rlen; if(len<=0) *t=NULL; else {*t=(BiTree)malloc(sizeof(BiTNode)); (*t)->data=preorder[i1]; r=calculate(preorder[i1],pinorder,i2); llen=r-i2; rlen=len-(llen+1); createtree(&(*t)->lchild,i1+1,i2,llen,preorder,pinorder); createtree(&(*t)->rchild,i1+llen+1,r+1,rlen,preorder,pinorder); } } void PostOrderTraverse(BiTree t) {if(t) {PostOrderTraverse(t->lchild); PostOrderTraverse(t->rchild); putchar(t->data); } } void PreOrderTraverse(BiTree t) {if(t) {putchar(t->data); 《用哈夫曼编码实现文件压缩》 实验报告 课程名称数据结构 实验学期2015至2016学年第一学期 学生所在系部计算机学院 年级2014专业班级物联B142班 学生姓名杨文铎学号201407054201 任课教师白磊 实验成绩 用哈夫曼编码实现文件压缩 1、了解文件的概念。 2、掌握线性表的插入、删除的算法。 3、掌握Huffman树的概念及构造方法。 4、掌握二叉树的存储结构及遍历算法。 5、利用Haffman树及Haffman编码，掌握实现文件压缩的一般原理。 微型计算机、Windows系列操作系统、Visual C++6.0软件 根据ascii码文件中各ascii字符出现的频率情况创建Haffman树，再将各字符对应的哈夫曼编码写入文件中，实现文件压缩。 本次实验采用将字符用长度尽可能短的二进制数位表示的方法，即对于文件中出现的字符，无须全部都用S为的ascii码进行存储，根据他们在文件中出现的频率不同，我们利用Haffman算法使每个字符能以最短的二进制数字符进行存储，已达到节省存储空间，压缩文件的目的，解决了压缩需要采用的算法，程序的思路已然清晰: 1、统计需压缩文件中的每个字符出现的频率 2、将每个字符的出现频率作为叶子节点构建Haffman树，然后将树中结点引向 其左孩子的分支标“0”，引向其右孩子的分支标“1”；每个字符的编码 即为从根到每个叶子的路径上得到的0、1序列，这样便完成了Haffman 编码，将每个字符用最短的二进制字符表示。 3、打开需压缩文件，再将需压缩文件中的每个ascii码对应的haffman编码按bit 单位输出。 4、文件压缩结束。 （1）构造haffman树的方法一haffman算法 构造haffman树步骤： I.根据给定的n个权值{w1，w2，w3…….wn}，构造n棵只有根结点的二叉 树，令起权值为wj。 II.在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和。 III.在森林中删除这两棵树，同时将得到的二叉树加入森林中。 IV.重复上述两步，知道只含一棵树为止，这棵树即哈夫曼树。 对于haffman的创建算法，有以下几点说明： a）这里的Haffman树采用的是基于数组的带左右儿子结点及父结点下标作为 2011~2012第一学期数据结构实验报告 班级：信管一班 学号：201051018 姓名：史孟晨 实验报告题目及要求 一、实验题目 设某班级有M（6）名学生，本学期共开设N（3）门课程，要求实现并修改如下程序（算法）。 1. 输入学生的学号、姓名和 N 门课程的成绩（输入提示和输出显示使用汉字系统）， 输出实验结果。（15分） 2. 计算每个学生本学期 N 门课程的总分，输出总分和N门课程成绩排在前 3 名学 生的学号、姓名和成绩。 3. 按学生总分和 N 门课程成绩关键字升序排列名次，总分相同者同名次。 二、实验要求 1．修改算法。将奇偶排序算法升序改为降序。（15分） 2．用选择排序、冒泡排序、插入排序分别替换奇偶排序算法,并将升序算法修改为降序算法；。（45分）） 3．编译、链接以上算法，按要求写出实验报告（25）。 4. 修改后算法的所有语句必须加下划线，没做修改语句保持按原样不动。 5．用A4纸打印输出实验报告。 三、实验报告说明 实验数据可自定义，每种排序算法数据要求均不重复。 (1) 实验题目：《N门课程学生成绩名次排序算法实现》； (2) 实验目的：掌握各种排序算法的基本思想、实验方法和验证算法的准确性； (3) 实验要求：对算法进行上机编译、链接、运行； (4) 实验环境（Windows XP-sp3,Visual c++)； (5) 实验算法（给出四种排序算法修改后的全部清单）； (6) 实验结果（四种排序算法模拟运行后的实验结果）； (7) 实验体会（文字说明本实验成功或不足之处）。 三、实验源程序（算法） Score.c #include "stdio.h" #include "string.h" #define M 6 #define N 3 struct student { char name[10]; int number; int score[N+1]; /*score[N]为总分,score[0]-score[2]为学科成绩*/ }stu[M]; void changesort(struct student a[],int n,int j) {int flag=1,i; struct student temp; while(flag) { flag=0; for(i=1;i 精品文档 这次课程设计的心得体会通过实习我的收获如下1、巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。2、培养了我选用参考书，查阅手册及文献资料的能力。培养独立思考，深入研究，分析问题、解决问题的能力。3、通过实际编译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。4、通过课程设计，培养了我严肃认真的工作作风，逐步建立正确的生产观念、经济观念和全局观念。从刚开始得觉得很难，到最后把这个做出来，付出了很多，也得到了很多，以前总以为自己对编程的地方还不行，现在，才发现只要认真做，没有什么不可能。 编程时要认真仔细，出现错误要及时找出并改正，（其中对英语的要求也体现出来了，因为它说明错误的时候都是英语）遇到问题要去查相关的资料。反复的调试程序，最好是多找几个同学来对你的程序进行调试并听其对你的程序的建议，在他们不知道程序怎么写的时候完全以一个用户的身份来用对你的用户界面做一些建议，正所谓当局者迷旁观者清，把各个注意的问题要想到；同时要形成自己的编写程序与调试程序的风格，从每个细节出发，不放过每个知识点，注意与理论的联系和理论与实践的差别。另外，要注意符号的使用，注意对字符处理，特别是对指针的使用很容易出错且调试过程是不会报错的，那么我们要始终注意指针的初始化不管它怎么用以免不必要麻烦。 通过近两周的学习与实践，体验了一下离开课堂的学习，也可以理解为一次实践与理论的很好的连接。特别是本组所做的题目都是课堂上所讲的例子，在实行之的过程中并不是那么容易事让人有一种纸上谈兵的体会，正所谓纸上得来终觉浅绝知此事要躬行。实训过程中让我们对懂得的知识做了进一步深入了解，让我们的理解与记忆更深刻，对不懂的知识与不清楚的东西也做了一定的了解，也形成了一定的个人做事风格。 通过这次课程设计，让我对一个程序的数据结构有更全面更进一步的认识，根据不同的需求，采用不同的数据存储方式，不一定要用栈，二叉树等高级类型，有时用基本的一维数组，只要运用得当，也能达到相同的效果，甚至更佳，就如这次的课程设计，通过用for的多重循环，舍弃多余的循环，提高了程序的运行效率。在编写这个程序的过程中，我复习了之前学的基本语法，哈弗曼树最小路径的求取，哈弗曼编码及译码的应用范围，程序结构算法等一系列的问题它使我对数据结构改变了看法。在这次设计过程中，体现出自己单独设计模具的能力以及综合运用知识的能力，体会了学以致用、突出自己劳动成果的喜悦心情，也从中发现自己平时学习的不足和薄弱环节，从而加以弥补。 精品文档 图实验 一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template 数据结构(C语言版) 实验报告 专业班级学号姓名 实验1 实验题目：单链表的插入和删除 实验目的： 了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。 实验要求： 建立一个数据域定义为字符串的单链表，在链表中不允许有重复的字符串；根据输入的字符串，先找到相应的结点，后删除之。 实验主要步骤： 1、分析、理解给出的示例程序。 2、调试程序，并设计输入数据（如：bat，cat，eat，fat，hat，jat，lat，mat，#），测试程序 的如下功能：不允许重复字符串的插入；根据输入的字符串，找到相应的结点并删除。 3、修改程序： （1）增加插入结点的功能。 （2）将建立链表的方法改为头插入法。 程序代码: #include"stdio.h" #include"string.h" #include"stdlib.h" #include"ctype.h" typedef struct node //定义结点 { char data[10]; //结点的数据域为字符串 struct node *next; //结点的指针域 }ListNode; typedef ListNode * LinkList; // 自定义LinkList单链表类型 LinkList CreatListR1(); //函数，用尾插入法建立带头结点的单链表 LinkList CreatList(void); //函数，用头插入法建立带头结点的单链表 ListNode *LocateNode(); //函数，按值查找结点 void DeleteList(); //函数，删除指定值的结点 void printlist(); //函数，打印链表中的所有值 void DeleteAll(); //函数，删除所有结点，释放内存 华南农业大学信息学院 综合性、设计性实验 起止日期:2011秋 学院软件学院专业班级10软件工程7班学号20103100070 4 姓名黄定康 实 验 题 目 实现平衡二叉排序树的各种算法 自我评价 项目算法设计独立完成情况算法熟练程度测试 通过 成功失败独立帮助掌握了解不懂 插入新结点√√√√ 前序、中序、后序遍历二叉树 （递归） √√√√ 前序、中序、后序遍历的非递 归算法 √√√√ 层次遍历二叉树√√√√ 在二叉树中查找给定关键字√√√√ 交换各结点的左右子树√√√√ 求二叉树的深度√√√√ 叶子结点数√√√√ 删除某结点√√√√ ●A---------完成实验要求的全部功能并运行通过，算法有一定的新意，程序代码 符合书写规范，实验报告叙述清晰完整，有详尽的分析和总结。 ●B---------完成实验要求的全部功能，程序代码符合书写规范，实验报告叙述 清晰完整。 ●C---------完成实验要求的大部分功能，实验报告良好。 ●D---------未按时完成实验，或者抄袭。 成 绩 教师签名：杨秋妹 实验报告 题目：实现平衡二叉排序树的各种算法 班级：10软件工程7班 姓名：黄定康 学号：201031000704 完成日期：2011/12/07 （一）分析题目要求 （1）函数说明 void R_rotate(ptr& t) -右旋转函数，从T开始做右旋转 int coutdeep(ptr t)-计算深度函数 void L_rotate(ptr& t)-左旋转函数 void leftbalance(ptr&t)-左平衡函数，从T开始做左平衡处理 void rightbalance(ptr&t)-右平衡函数 int insertA VL(ptr& t,int e,int & taller)-插入结点函数 void preorder(ptr t)-（递归）先序遍历 void preorder_2(ptr t)-（非递归）先序遍历 void inorder(ptr t)-（递归）中序遍历 void inorder_2(ptr t)-（非递归）中序遍历 void posorder(ptr t)-（递归）后序遍历 void posorder_2(ptr t)-（非递归）后序遍历 void dfs(ptr t,int type)-（递归）深度优先遍历（包含中序先序后续） void dfs_2(ptr t,int type)-(递归) 深度优先遍历 int bfs(ptr t)-层次便利 int delete_node(ptr& t,int&shorter,int temp);-删除结点函数 int Delete(ptr& t,int shorter)-删除结点函数 int transfer(ptr&t)-左右子树交换函数 int countleaf(ptr t)-计算叶节点 int checkup(ptr t,int temp)- 从树t中查找temp是否存在，存在返回1否则返回0 int main()-主函数 void show_menu(ptr t)-简单的菜单函数 （2）输入形式及输入值范围 输入形式：当树没创建时，先在第一行输入树的节点数目n，第二行再输入n个大于0的不重复整数，以空格隔开。删除结点时，直接输入要删除结点的值。 输入范围：所有int类型的大于零的值，注意不能重复输入。 长春大学计算机学院网络工程专业 数据结构实验报告 实验名称：实验二栈和队列的操作与应用 班级：网络14406 姓名：李奎学号：041440624 实验地点：日期： 一、实验目的： 1．熟练掌握栈和队列的特点。 2．掌握栈的定义和基本操作，熟练掌握顺序栈的操作及应用。 3．掌握链队的入队和出队等基本操作。 4．加深对栈结构和队列结构的理解，逐步培养解决实际问题的编程能力。 二、实验内容、要求和环境： 注：将完成的实验报告重命名为：班级+学号+姓名+（实验二），（如：041340538张三（实验二）），发邮件到：ccujsjzl@https://www.doczj.com/doc/5e18219224.html,。提交时限：本次实验后24小时之内。 阅读程序，完成填空，并上机运行调试。 1、顺序栈，对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数 (1)文件SqStackDef. h 中实现了栈的顺序存储表示 #define STACK_INIT_SIZE 10 /* 存储空间初始分配量*/ #define STACKINCREMENT 2 /* 存储空间分配增量*/ typedef struct SqStack { SElemType *base; /* 在栈构造之前和销毁之后，base 的值为NULL */ SElemType *top; /* 栈顶指针*/ int stacksize; /* 当前已分配的存储空间，以元素为单位*/ }SqStack; /* 顺序栈*/ (2)文件SqStackAlgo.h 中实现顺序栈的基本操作（存储结构由SqStackDef.h 定义） Status InitStack(SqStack &S) { /* 构造一个空栈S */ S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base) exit(OVERFLOW); /* 存储分配失败*/ S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; } int StackLength(SqStack S) { // 返回S 的元素个数，即栈的长度, 编写此函数 附录A 实验报告 课程：数据结构（c语言）实验名称：图的建立、基本操作以及遍历系别：数字媒体技术实验日期： 12月13号 12月20号 专业班级：媒体161 组别：无 姓名：学号： 实验报告内容 验证性实验 一、预习准备： 实验目的： 1、熟练掌握图的结构特性，熟悉图的各种存储结构的特点及适用范围； 2、熟练掌握几种常见图的遍历方法及遍历算法； 实验环境：Widows操作系统、VC6.0 实验原理： 1.定义： 基本定义和术语 图(Graph)——图G是由两个集合V(G)和E(G)组成的,记为G=(V,E)，其中：V(G)是顶点(V ertex)的非空有限集E(G)是边(Edge)的有限集合，边是顶点的无序对(即：无方向的，（v0,v2）)或有序对（即：有方向的, 无向图中顶点V i的度TD(V i)是邻接矩阵A中第i行元素之和有向图中， 顶点V i的出度是A中第i行元素之和 顶点V i的入度是A中第i列元素之和 邻接表 实现：为图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（有向图中指以Vi为尾的弧） 特点: 无向图中顶点Vi的度为第i个单链表中的结点数有向图中 顶点Vi的出度为第i个单链表中的结点个数 顶点Vi的入度为整个单链表中邻接点域值是i的结点个数 逆邻接表：有向图中对每个结点建立以Vi为头的弧的单链表。 图的遍历 从图中某个顶点出发访遍图中其余顶点，并且使图中的每个顶点仅被访问一次过程.。遍历图的过程实质上是通过边或弧对每个顶点查找其邻接点的过程，其耗费的时间取决于所采用的存储结构。图的遍历有两条路径：深度优先搜索和广度优先搜索。当用邻接矩阵作图的存储结构时，查找每个顶点的邻接点所需要时间为O（n2），n为图中顶点数；而当以邻接表作图的存储结构时，找邻接点所需时间为O（e），e 为无向图中边的数或有向图中弧的数。 实验内容和要求： 选用任一种图的存储结构，建立如下图所示的带权有向图： 要求：1、建立边的条数为零的图；数据结构实验报告格式
数据结构实验报告
(完整版)数据结构实验报告全集
数据结构实验总结报告
约瑟夫问题数据结构实验报告汇总.
数据结构实验总结报告
数据结构停车场问题实验报告汇总
数据结构实验报告模板
数据结构实验报告
数据结构实验报告
数据结构实验报告及心得体会
最新数据结构实训总结
数据结构实验报告图实验
数据结构实验报告 - 答案汇总
数据结构实验报告
数据结构实验
数据结构实验报告(图)
相关主题
文本预览