数据结构实验报告
1、实验一
输入数据（设为整型）建立单链表，并求相邻两节点data值之和为最大的第一节点。
例如输入：2 6 4 7 3 0（0为结束符）
运行代码：
#include"stdio.h"
#include"malloc.h"
typedef struct node
{
int data;
struct node *next;
}list,*List;
List Creatlist() //建立链表函数
{
List H,p,r;
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 ;}
else;
p=p->next ;
}
return q;
}
int main()
{
char ch;
printf("/// 请输入整形数据，以空格隔开，0结束。/// \n");
printf("Ready?Y/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;
}
运行结果：
2、实验二
实现算术表达式求值程序（栈的运用）
设操作数：0，1，2，……，8，9（可扩充）；
运算符：+，—，*，/，（，），#（#号为结束）。
输入中缀表达式，如：5+(4-2)*3 #，将其转换成后缀表达式：542-3*+#，
然后计算，本例结果为11。
运行代码：
#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#define MAX 100
typedef struct //定义操作符结构体
{
char op; //操作符
int level; //操作符优先顺序
}opt;
typedef struct //表达式栈
{
opt st[MAX];
int top;
}op_stack;
typedef struct //双精度操作数栈
{
double d[MAX];
int top;
}data_stack;
opt get(op_stack *s) //栈顶字符函数
{
opt error={'$',-2};
if(s->top>=0)
return s->st[s->top];
else
return error;
}
int IsEmpty(op_stack *s) //判断栈是否为空
{
if(s->top<0)
return 0;
else
return
s->st[s->top].op;
}
char push(op_stack *s,opt c) //进栈函数
{
s->top++;
s->st[s->top]=c;
return c.op;
}
opt pop(op_stack *s) //出栈函数
{
opt i;
opt error={'$',-2};
if(s->top>=0)
{
i=s->st[s->top];
s->st [s->top ].op='\0';
s->top--;
return i;
}
else
return error;
}
void clear(op_stack *s) //清空栈
{
s->top=-1;
}
double dget(data_stack *s) //双精度操作数栈取栈顶
{
if(s->top>=0)
return s->d[s->top];
else
return 0;
}
int DIsEmpty(data_stack *s)//判断操作数栈是否为空
{
if(s->top<0)
return 0;
else
return (int)(s->d[s->top]);
}
double dpush(data_stack *s,double c) //操作数进栈
{
s->top++;
s->d[s->top]=c;
return c;
}
double dpop(data_stack *s) //操作数出栈
{
double i;
if(s->top>=0)
{
i=s->d[s->top];
s->d[s->top]='\0';
s->top--;
return i;
}
else return 0;
}
void dclear(data_stack *s) //操作数栈清空
{
s->top=-1;
}
void midpost(char *str,char *expr,char *kkk) //中缀转换后缀
{
opt A={'+',1};
opt R={'-',1};
opt M={'*',2};
opt D={'/',2};
opt B={'(',-1};
op_stack os;
clear(&os);
while(*str!='#')
{
while(*str>='0'&&*str<='9'||*str=='.')//筛选数字与.
{ //存入后缀表达式
*expr=*str;
expr++;
str++;
}
*expr++=' '; //数字之间以空格隔开
switch(*str) // 处理操作符
{
case '+':
while(get(&os).level>=A.level&&IsEmpty(&os))
{
*expr++=pop(&os).op; //优先顺序高进栈
}
push(&os,A);
str++;
break;
case '-':
while(get(&os).level>=R.level&&IsEmpty(&os))
{
*expr++=pop(&os).op; //栈顶元素优先级高出栈
}
push(&os,R); //进栈
str++;
break;
case '*':
while(get(&os).level>=M.level&&IsEmpty(&os))
{
*expr++=pop(&os).op; //栈顶元素优先级高出栈
}
push(&os,M);//进栈
str++;
break;
case '/':
while(get(&os).level>=D.level&&IsEmpty(&os))
{
*expr++=pop(&os).op;//栈顶元素优先级高出栈
}
push(&os,D);//否则进栈
str++;
break;
case '(':
push(&os,B);//进栈
str++;
break;
case ')':
while(get(&os).op!='(') //出栈直到遇到‘（’
{
*expr++=pop(&os).op;
}
pop(&os);
str++;
break;
}
}
while(IsEmpty(&os)) //输出余下字符
{
*expr++=pop(&os).op ;
}
*expr++='#'; //结束标志
}
double count(char *ch) //计算后缀表达式值
{
data_stack Data;
int i,len,j=0;
double result=0;
double tmpdata,tmp1;
char tmp[MAX]={'\0'};
dclear(&Data);
while(*ch!='#')
{
j=0;
if(*ch==' ')
ch++;
else
{
while(*ch>='0'&&*ch<='9'||*ch=='.') //将数字字符与.拼成数字
{
tmp[j++]=*ch++;
}
tmp[j++]='\0';
tmp1=atof(tmp); //字符串转化成浮点数
if(j!=1)
dpush(&Data,tmp1); //只有转化成浮点数之后进操作数栈
len=strlen(tmp);
for(i=0;i<len;i++)
tmp[i]='\0';
}
if(*ch=='+')
{
result=dpop(&Data)+dpop(&Data);
dpush(&Data,result);
ch++;
}
else if(*ch=='-')
{
tmpdata=dpop(&Data);
result=dpop(&Data)-tmpdata;//先出栈为减数，后出栈为被减数
dpush(&Data,result);
ch++;
}
else if(*ch=='*')
{
result=dpop(&Data)*dpop(&Data);
dpush(&Data,result);
ch++;
}
else if(*ch=='/')
{
tmpdata=dpop(&Data);result=dpop(&Data)/tmpdata;//先出栈为除数，后出栈为被除数
dpush(&Data,result);
ch++;
}
}
return result;
}
int main()
{
char c;
c='y';
while(c=='y'||c=='Y')
{
char string[MAX];
char exp[MAX]={'\0'};
char *myexp;
myexp=exp;
puts("请输入表达式以‘#’结束：");
gets(string);
midpost(string,exp,myexp);
printf("后缀表达式：%s\n",exp);
printf("表达式结果：%f\n",count(exp));
printf("continue? y/n \n");
fflush(stdin);
scanf("%c",&c);
fflush(stdin);
}
}
运行结果：
3、实验三
实现队列运算程序（队列的运用）
运行代码：
#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;}
运行结果:
4、实验四
设电文字符集D及各字符出现的概率F如下：
D={a，b，c，d，e，f，g，h}（字符数n=8）
F={5，29，7，8，14，23，3，11}(%)
编写完成下列功能的程序：
①构造关于F的Huffman树；
②求出并打印D中各字符的Huffman编码。
运行代码：
#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);
}
}
运行结果：
5、实验五
设英文句子：“everyone round you can hear you when you speak.”，试编写完成下面任务的程序。
运行代码：
#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);
}}
运行结果：
-
数据结构实验报告
实验报告实验课程：数据结构实验项目：实验专业：计算机科学与技术姓名：**学号：***指导教师：**实验时间：20**-12-7重庆…
-
数据结构实验报告(C语言)(强力推荐)
数据结构实验实验内容和目的掌握几种基本的数据结构集合线性结构树形结构等在求解实际问题中的应用以及培养书写规范文档的技巧学习基本的查…
-
数据结构实验———图实验报告
数据结构实验报告目的要求掌握图的存储思想及其存储实现掌握图的深度广度优先遍历算法思想及其程序实现掌握图的常见应用算法的思想及其程序…
-
数据结构实验报告格式
数据结构实验报告格式实验11顺序表的基本操作一实验目的1掌握使用VC上机调试线性表的基本方法2掌握线性表的基本操作插入删除查找等运…
-
数据结构实验报告全集
数据结构实验报告全集实验一线性表基本操作和简单程序1实验目的1掌握使用VisualC60上机调试程序的基本方法2掌握线性表的基本操…
-
数据结构课程设计 实验报告 心得体会 链表 C语言
数据结构课程设计设计题目:两个链表的交叉合并专业班级:08软件工程3班姓名：**学号：***设计时间：20XX/9/25指导教师：…
-
焦作数据结构实验报告
河南省高等教育自学考试实验报告册计算机及应用专业本科段数据结构姓名李威威准考证号所属地市焦作市实验地点焦作大学实验实训中心实验日期…
-
数据结构实验报告
PracticeReportforDataStructuresandAlgorithmAnalysisDataStructuresCourseRepo…
-
天津理工大学数据结构实验报告4
计算机科学与工程系计算机科学与工程系2计算机科学与工程系附录可包括源程序清单或其它说明includeltstdiohgtinclu…
-
河南自考数据结构实验报告
河南省高等教育自学考试实验报告册计算机及应用专业本科段数据结构姓名准考证号所属地市实验地点实验日期2实验总成绩指导教师签名实验单位…
-
华中科技大学·计算机13级·数据结构实验报告
课程设计报告课程名称专业班级CS1308学号姓名陈劲龙指导教师报告日期计算机科学与技术目录实验一基于顺序结构的线性表实现11问题描…