北京科技大学数据结构试验报告(附录含代码).docx

一、
1)功能描述
输入数据（设为整型）建立单链表，并求相邻两节点data值之和为最大的第一节点。
2)详细设计
遵循链表建立的基本思想，建立一个新的链表，H为表头，r为新节点，p为表尾节点指针，没存入一个新的数据则申请一个新的节点，知道没有数据输入，利用循环和打擂台法，比较和的大小，并输出。
3)测试分析
程序调试完成后，选取两组数据进行测试，都得出了正确结果（数据以0为结束符，若有相同和，则取第一组）
结果截图

4)心得体会
通过做第一题，学习到链表的建立以及链表里指针的使用，并且复习了比较法里面的打擂台法。
二、
1)功能描述
实现算术表达式求值程序（栈的运用），输入中缀表达式，可将其转换成后缀表达式
2)详细设计
本题目的程序是根据课本上的程序改进之后得出的，课本上有完整的程序，但是有bug，按照课本上的程序，结果会出现“烫烫烫烫烫”，原因是对于优先级的比较没有处理好，因此加了两行代码，将优先级的比较处理好，即现在的程序。
3)测试分析
程序调试完成后，选取题目所给的式子进行测试，得出了正确后缀表达式结果
结果截图

4)心得体会
通过做第二题，对于课本上的知识表示得出“实践出真知”的真理，即使书上的东西也不一定就是正确的，尤其是代码，最好是个人自己真正实践一下。
三、
1)功能描述
实现链式队列运算程序（队列的运用）
2)详细设计
本题目是队列相关应用，队列和栈是相反的，队列是先进的先出，因此输入12345，先出的是1，本着队列的这一特性，根据课本所学的队列的算法，设计了如下程序。
3)测试分析
程序调试完成后，选取12345进行测试，后缀加0，则一个字符出队，只输入0，则继续出队，输入@，则打印剩余全部元素。
结果截图

4)心得体会
通过做第三题，对于队列的特点有了更加深刻的认识，尤其区分队列与栈的不同点，需要特别注意。

四、
1)功能描述
①构造关于F的Huffman树；
②求出并打印D总各字符的Huffman编码。
2)详细设计
本题目是Huffman树的应用以及Huffman编码的应用，参照课本上关于Huffman树的建立以及Huffman编码的应用的实现，将所给数据依权值最小原则建立Huffman树，并实现Huffman编码。
3)测试分析
程序调试完成后，给出数据abcdefgh，相应频率为12345678，运行代码得出结果如图。同时选取另一组数据测试也得出了正确结论
结果截图

4)心得体会
通过做第四题，对于Huffman树有了更加深刻的体会，同时练习也使得对课本知识进行实践，有助于更好的理解Huffman树的算法。

五、
1)功能描述
设英文句子：“everyone round you can hear you when you speak.”
（1） 依次读入句中各单词，构造一棵二叉排序树；
（2） 按LDR遍历此二叉排序树。
LDR： can everyone hear round speak when you（有序）
2)详细设计
本题目是有关二叉树的建立和中序遍历的，二叉树作为数据存储一个很重要的结构，它的建立也是很重要的。本题目代码设计上采用课本上的对于二叉树建立的方法，将所给单词以二叉树形式建立并存储，然后中序遍历的到字典顺序。
3)测试分析
程序调试完成后，给出单词串everyone round you can hear you when you speak，运行代码得出中序遍历结果如图。
结果截图

4)心得体会
通过做第五题，练习运用二叉树模型解决了一些实际问题如现实中字典的编排问题，在熟悉算法的基础上，同时得出结论，好的算法可以应用与实际生活生产，使之更为便捷。

附录 程序代码
实验一：
#include"stdio.h"
#include"malloc.h"
typedef struct node
{
int data;
struct node *next;
}list,*List;
List Creatlist() //建立链表函数
{
List H,p,r; //H为表头，r为新节点，p为表尾节点指针
H=(List)malloc(sizeof(list)); //建立头节点
r=H;
p=(List)malloc(sizeof(list)); //申请新节点
while(scanf("%d",p)&&p->data!=0) //输入数据，直到为零（结束标志）
{
r->next=p; //新节点链入表尾
r=p;
p=(List)malloc(sizeof(list));
}
r->next=NULL; //将尾节点的指针域置空
return H; //返回已创建的头节点
}
List Adjmax(List H) //比较相邻两数之和
{ //返回相邻两数之和最大的第一个数指针
List p,r,q;
int sum=0;
p=H->next;
if(H->next ==NULL) //判断是否为空
{
printf("Empty List!");
q=(List)malloc(sizeof(list));
q->data =0;
}
while(p!=NULL) //比较相邻两数之和
{
r=p->next ;
if(p&&r)
if(r->data+p->data>sum)
{
q=p;
sum=r->data +p->data ;}//不断赋给sum新的最大值
else;
p=p->next ;
}
return q;
}
int main()
{
char ch;
printf("/// 请输入整形数据，以空格隔开，0结束。/// \n");
printf("Ready? \nY/N (enter 'y' or 'Y' to continue) \n");
while(scanf("%c",&ch)&&(ch=='Y'||ch=='y'))
{
List H,pmax;
H=Creatlist();
pmax=Adjmax(H);
printf("相邻两数之和最大的第一个数为：%d\nContinue? Y/N ",pmax->data );
free(H);
scanf("%c",&ch);
}
return 0;
}

实验二：
#include<stdio.h>
#include<malloc.h>
#include<conio.h>
typedef struct node //栈节点类型
{
char data; //存储一个栈元素
struct node *next; //后继指针
}snode,*slink;
int Emptystack(slink S) //检测栈空
{
if(S==NULL) return(1);
else return(0);
}
char Pop(slink*top) //出栈
{
char e;
slink p;
if(Emptystack(*top)) return(-1); //栈空返回
else
{
e=(*top)->data; //取栈顶元素
p=*top; *top=(*top)->next; //重置栈顶指针
free(p);return(e);
}
}
void Push(slink*top,char e) //进栈
{
slink p;
p=(slink)malloc(sizeof(snode)); //生成进栈p节点
p->data=e; //存入元素e
p->next=*top; //p节点作为新的栈顶链入
*top=p;
}
void Clearstack(slink*top) //置空栈
{
slink p;
while(*top!=NULL)
{
p=(*top)->next;
Pop(top); //依次弹出节点直到栈空
*top=p;
}
*top=NULL;
}
char Getstop(slink S) //取栈顶
{
if(S!=NULL)return(S->data);
return(0);
}
//符号优先级比较
int Precede(char x,char y) //比较x是否"大于"y
{
switch(x)
{
case '(':x=0;break;
case '+':
case '-':x=1;break;
case '*':
case '/':x=2;break;
default: x=-1;
}
switch(y)
{
case '+':
case '-':y=1;break;
case '*':
case '/':y=2;break;
case '(':y=3;break;
default: y=100;
}
if (x>=y)return(1);
else return(0);
}
//中后序转换
void mid_post(char post[],char mid[])//中缀表达式mid到后缀表达式post的转换的算法
{
int i=0,j=0;
char x;
slink S=NULL;//置空栈
Push(&S,'#');//结束符入栈
do
{
x=mid[i++];//扫描当前表达式分量x
switch(x)
{ case '#':
{ while(!Emptystack(S))
post[j++]=Pop(&S);
}break;
case ')':
{ while(Getstop(S)!='(')
post[j++]=Pop(&S);//反复出栈直至遇到'（'
Pop(&S);//退掉'（'
}break;
case '+':
case '-':
case '*':
case '/':
case '(':
{ while(Precede(Getstop(S),x))//栈顶运算符（Q1）与x比较
post[j++]=Pop(&S);//Q1>=x时，输出栈顶符并退栈
Push(&S,x);//Q1<x时x进栈
}break;
default:post[j++]=x;//操作数直接输出
}
}while(x!='#');
post[j]='\0';
}
//后缀表达式求值
int postcount(char post[])//后缀表达式post求值的算法
{
int i=0;
char x;
float z,a,b;
slink S=NULL;//置栈空
while (post[i]!='#')
{ x=post[i];//扫描每一个字符送x
switch(x)
{case '+':b=Pop(&S);a=Pop(&S);z=a+b;Push(&S,z);break;
case '-':b=Pop(&S);a=Pop(&S);z=a-b;Push(&S,z);break;
case '*':b=Pop(&S);a=Pop(&S);z=a*b;Push(&S,z);break;
case '/':b=Pop(&S);a=Pop(&S);z=a/b;Push(&S,z);break;//执行相应运算结果进栈
default:x=post[i]-'0';Push(&S,x);//操作数直接进栈
}
i++;
}
if (!Emptystack(S))return(Getstop(S));//返回结果
}
void main()
{
char post[255],mid[255]="";
printf("请输入要处理的中缀表达式：\n");
scanf("%s",mid);
printf("相应的后缀表达式为：\n");
mid_post(post,mid);
printf("%s\n",post);
printf("表达式的值为：%d\n",postcount(post));
getch();
}

实验三：

#include"stdio.h"
#include"malloc.h"
#define max 1000

typedef struct node
{
char ch[max];
int front,rear;
}squeue,*sq;
void Clearqueue(sq Q)
{
Q->front=Q->rear;
}
int Emptyqueue(sq Q)
{
if(Q->rear==Q->front)
return 1;
else
return 0;
}
void Enqueue(sq Q,char ch)
{
if(Q->rear>=max)
{
printf("FULL QUEUE!");
}
else
{
Q->ch [Q->rear]=ch;
Q->rear ++;
}}
void Dequeue(sq Q)
{
if(Emptyqueue(Q))
{
printf("Empty QUEUE!\n");
}
else
{
printf("出队：%c\n",Q->ch[Q->front]);
Q->front ++;
}
}
void Printqueue(sq Q)
{
if(Emptyqueue(Q))
;
else
{
printf("队列中全部元素：\n");
while(Q->front!=Q->rear-1)
{
printf("%c",Q->ch[Q->front]);
Q->front++;
}
printf("\n");
}
}
int main()
{
sq Queue;
char f;
printf("*******************************************\n");
printf("请输入字符X\nX ≠'@'并且 X ≠'@'字符入队；\n");
printf("X='0',字符出队；\n");
printf("X='@',打印队列中各元素。\n");
printf("*******************************************\n");
Queue=(sq)malloc(sizeof(squeue));
Queue->front =Queue->rear=0;
while(scanf("%c",&f)&&f!='@')
{
if(f!='0')
Enqueue(Queue,f);
else
Dequeue(Queue);
}
if(f=='@')
Printqueue(Queue);
else;
return 0;}

实验四：

#include"stdio.h"
#include"malloc.h"
#define N 8
#define MAX 100
#define M 2*N-1
typedef struct
{
char letter;
int w;
int parent,lchild,rchild;
}Huffm;
typedef struct
{
char bits[N+1];
int start;
char ch;
}ctype;
void inputHT(Huffm HT[M+1])
{
int i;
for(i=1;i<=M;i++)
{
HT[i].w=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
printf("请输入电文字符集：");
for(i=1;i<=N;i++)
{
scanf("%c",&HT[i].letter );
}
printf("请输入字符出现的频率：");
for(i=1;i<=N;i++)
{
scanf("%d",&HT[i].w );
}
}
void CreatHT(Huffm HT[M+1])
{
int i,j,min1,min2;
int tag1,tag2; //权值最小两个点标号；
for(i=N+1;i<=M;i++)
{
tag1=tag2=0;
min1=min2=MAX;
for(j=1;j<=i-1;j++)
{
if(HT[j].parent ==0)
if(HT[j].w <min1)
{ min2=min1;
min1=HT[j].w;
tag2=tag1;
tag1=j;
}
else
if(HT[j].w <min2)
{
min2=HT[j].w;
tag2=j;
}
}
HT[tag1].parent =HT[tag2].parent =i;
HT[i].lchild =tag1;
HT[i].rchild =tag2;
HT[i].w =HT[tag1].w +HT[tag2].w;
}
}
void Huffmcode(Huffm HT[M+1]) // Huffm编码函数
{
int i,j,p,tag;
ctype mcode,code[N+1];
for(i=1;i<=N;i++)
{
code[i].ch=HT[i].letter;
}
for(i=1;i<=N;i++)
{
mcode.ch =code[i].ch;
mcode.start=N+1;
tag=i;
p=HT[i].parent ;
for(j=0;j<=N;j++)
mcode.bits [j]=' ';
while(p!=0)
{
mcode.start--;
if(HT[p].lchild ==tag)
mcode.bits[mcode.start ]='0';
else
mcode.bits [mcode.start ]='1';
tag=p;p=HT[p].parent ;
}
code[i]=mcode;
}
for(i=1;i<=N;i++)
{
printf(" '%c'的Huffm编码为：",code[i].ch );
for(j=0;j<=N;j++)
printf("%c",code[i].bits [j]);
printf("\n");
}
}
int main()
{
char ch;
printf("******************************************************\n");
printf("电文字符集含8个字符，连续输入，不同频率之间以空格隔开 \n");
printf("******************************************************\n");
ch='y';
while(ch=='y')
{
Huffm HT[M+1];
inputHT(HT);
CreatHT(HT);
Huffmcode(HT);
printf("Continue? Y/N ");
fflush(stdin);
scanf("%c",&ch);
fflush(stdin);
}
}

实验五：

#include"stdio.h"
#include"malloc.h"
#include"string.h"
typedef struct bsnode
{
char word[20];
struct bsnode *lchild,*rchild;
}BStree,*BST;
BST BSTinsert(BST T,BST s)
{
BST f,p;
if(T==NULL)
return s;
p=T;f=NULL;
while(p)
{
f=p;
if(strcmp(s->word,p->word)==0 )
{
free(s);
return T;
}
if( strcmp(s->word,p->word)<0 )
p=p->lchild ;
else
p=p->rchild ;
}
if(strcmp(s->word ,f->word)<0)
f->lchild=s ;
else
f->rchild=s ;
return T;}
BST CreatBst()
{
BST T,s;
char keyword[20];
T=NULL;
gets(keyword);
while(keyword[0]!='0')
{
s=(BST)malloc(sizeof(BStree));
strcpy(s->word,keyword);
s->lchild=s->rchild=NULL;
T=BSTinsert(T,s);
gets(keyword);
}
return T;}
void Inorder(BST T)
{
if(T)
{
Inorder(T->lchild );
printf("%s ",T->word );
Inorder(T->rchild );
}
}
int main()
{ char ch;
BST T;
printf("************************************************************\n");
printf("请输入英文句子，每输入一个单词以回车结束，句子结束以'0'结束。\n");
printf("************************************************************\n");
ch='y';
while(ch=='Y'||ch=='y')
{
T=CreatBst();
printf("按LDR遍历此二叉排序树(字典顺序):\n");
Inorder(T);
free(T);
printf("\nContinue? Y/N ");
scanf("%c",&ch);
}}