计算机软件技术基础实验报告
计算机软件基础实验报告
姓名 学号
实验目的
1. 掌握C语言程序设计方法，并学会上机调试。
2. 熟悉Huffman编码源程序，并构造Huffman树。
实验内容
1. 试设计一算法，从包括n个元素的数组中，求最大和最小元素，并使得当n个元素为有序排列时，元素之间的比较次数仅为n-1次。
2. 在给出的Huffman编码源程序基础上，要求画出Huffman树，求出与等长编码相比时的压缩比。
实验要求
1.根据实验内容编写算法，并用 C 语言进行程序设计。
2. 将所编程序在计算机上调试通过，并全面测试。
实验结果
1．以一个含有8个元素的一维数组{1，2，3，5，7，8，9，12}为例,设计程序如下：
#include<stdio.h>
int maxArray(int x ,int y);
int minArray(int x ,int y);
int main(void)
{
int i = 0 ;
int array[8]={ 1，2，3，5，7，8，9，12} ;
printf;
do
{
scanf("%d",&array[i]);
i++;
} while(i < 8);
int maxTemp = array[0];
int minTemp = array[0];
int maxIndex = 0;
int minIndex = 0;
for(i=1;i<8;i++)
{
maxTemp = maxArray(array[i] , maxTemp);
minTemp = minArray(array[i] , minTemp);
}
for(i=0;i<8;i++)
{
if (maxTemp == array[i])
{
maxIndex = i;
}
if (minTemp == array[i])
{
minIndex = i;
}
}
printf;
return 0;
}
运行结果如下：
2.Huffman编码源程序
#include <dos.h>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct
{unsigned int weight; //结点权值
unsigned int parent,lchild,rchild; //结点的父指针，左右孩子指针
}HTNode,*HuffmanTree; //动态分配数组存储哈夫曼树
typedef char **HuffmanCode; //动态分配数组存储哈夫曼编码表
void CreateHuffmanTree(HuffmanTree &,unsigned int*,int ); //生成哈夫曼树
void HuffmanCoding(HuffmanTree,HuffmanCode &,int ); //对哈夫曼树进行编码
void PrintHuffmanCode(HuffmanCode,unsigned int*,int); //显示哈夫曼编码
void Select(HuffmanTree,int,int&,int&); //在数组中寻找权值最小的两个结点
void main()
{HuffmanTree HT; //哈夫曼树HT
HuffmanCode HC; //哈夫曼编码表HC
int n,i; //n是哈夫曼树叶子结点数
unsigned int *w; //w存放叶子结点权值
char j='y';
printf("演示构造哈夫曼树.\n");
printf("输入需要进行编码的字符数目.\n例如:8\n");
printf("然后输入每个字符出现的次数/权值.\n");
printf("例如:5 29 7 8 14 23 3 11\n");
printf("自动构造一棵哈夫曼树并显示哈夫曼编码.\n");
printf(" 5---0110\n 29---10\n 7---1110\n 8---1111\n 14---110\n");
printf(" 23---00\n 3---0111\n 11---010\n");
while(j!='N'&&j!='n')
{printf("请输入字符数目:");
scanf("%d",&n); //输入字符数目
if(n<=1) {printf("该数不合理!\n");continue;}
w=(unsigned int*)malloc(n*sizeof(unsigned int)); //开辟空间存放权值
printf("请输入各字符出现的次数/权值:\n");
for(i=0;i<n;i++) scanf("%d",&w[i]); //输入各字符出现的次数/权值
CreateHuffmanTree(HT,w,n); //生成哈夫曼树
HuffmanCoding(HT,HC,n); //进行哈夫曼编码
PrintHuffmanCode(HC,w,n); //显示哈夫曼编码
printf("哈夫曼树构造完毕，还要继续吗?(Y/N)");
scanf(" %c",&j);
}
}
void CreateHuffmanTree(HuffmanTree &HT,unsigned int *w,int n)
{//w存放n个结点的权值，将构造一棵哈夫曼树HT
int i,m;
int s1,s2;
HuffmanTree p;
if(n<=1) return;
m=2*n-1; //n个叶子结点的哈夫曼树，有2*n-1个结点
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //开辟2*n各结点空间
for(p=HT+1,i=1;i<=n;++i,++p,++w) //进行初始化
{p->weight=*w;
p->parent=0;
p->lchild=0;
p->rchild=0;
}
for(;i<=m;++i,++p)
{p->weight=0;
p->parent=0;
p->lchild=0;
p->rchild=0;
}
for(i=n+1;i<=m;++i) //建哈夫曼树
{Select(HT,i-1,s1,s2);
//从HT[1...i-1]中选择parent为0且weight最小的两个结点，其序号分别为s1和s2
HT[s1].parent=i; HT[s2].parent=i; //修改s1和s2结点的父指针parent
HT[i].lchild=s1; HT[i].rchild=s2; //修改i结点的左右孩子指针
HT[i].weight=HT[s1].weight+HT[s2].weight; //修改权值
}
}
void HuffmanCoding(HuffmanTree HT,HuffmanCode &HC,int n)
{//将有n个叶子结点的哈夫曼树HT进行编码， 所编的码存放在HC中
//方法是从叶子到根逆向求每个叶子结点的哈夫曼编码
int i,c,f,start;
char *cd;
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'; //若是左孩子编为'0'
else cd[--start]='1'; //若是右孩子编为'1'
HC[i]=(char *)malloc((n-start)*sizeof(char)); //为第i个编码分配空间
strcpy(HC[i],&cd[start]); //将编码从cd复制到HC中
}
free(cd); //释放工作空间
}
void PrintHuffmanCode(HuffmanCode HC,unsigned int *w,int n)
{//显示有n个叶子结点的哈夫曼树的编码表
int i;
printf("HuffmanCode is :\n");
for(i=1;i<=n;i++)
{printf(" %3d---",w[i-1]);
puts(HC[i]);
}
printf("\n");
}
void Select(HuffmanTree HT,int t,int&s1,int&s2)
{//在HT[1...t]中选择parent不为0且权值最小的两个结点，其序号分别为s1和s2
int i,m,n;
m=n=10000;
for(i=1;i<=t;i++)
{if(HT[i].parent==0&&(HT[i].weight<m||HT[i].weight<n))
if(m<n)
{n=HT[i].weight;s2=i;}
else {m=HT[i].weight;s1=i;}
}
if(s1>s2) //s1放较小的序号
{i=s1;s1=s2;s2=i;}
}
运行结果如下:
输入数据后的运行结果:
实验心得
要熟练掌握程序的编写，如果没有一定的想象能力和大量的上机实践是根本无法完成的。
首先要做的是多看程序，勤编程序。完整地编写一个准确、严谨的程序绝非易事。大量阅读程序有助于我们掌握编程的常用语法和基本要领。随着阅读量的不断增加，我们大脑中对于知识的积累越来越丰富，对于编程的感觉也越来越敏感。渐渐地，在基本掌握了编程的方法套路后，我们大脑中的“数据库”日益壮大，编写各种类型的程序便会显得得心应手，也不再像以前那样看到编程就会一头雾水。当对程序熟练到一定程度后，我们甚至可以试着去纠正别人程序中的一些不妥之处，这不仅使得程序更加完善，更是对自己编程能力的更高一层的肯定。
其次，上机实践，也是必不可少的环节。上机实践的目的是能够更好地检验所编程序的准确性和可行性,还可以帮助我们更加深刻地了解程序的运行过程。对于一个编写完成的程序，如果没有上机调试过，即使程序完全正确，也未必能够充分理解其功能和目的。
总之，编程有一定的难度。但只要勤加训练，定能熟能生巧。
第二篇：软件技术基础上机实验报告(链表)
ex2：链表的插入与删除
1）首先创建一个单链表：从键盘读入五个整数，按输入顺序形成单链表。将创建好的链表元素依次输出到屏幕上。
2）在已创建好的链表中插入一个元素：从键盘读入元素值和插入位置，调用插入函数完成插入操作。然后将链表元素依次输出到屏幕上。
3）在已创建好的链表中删除一个元素：从键盘读入欲删除的元素位置（序号），调用删除函数完成删除操作。然后将链表元素依次输出到屏幕上。
4）从键盘任意输入一个整数，在单链表中查询该数，如果单链表中已经存在这个数，就调用删除函数，删除该元素所在结点，并将单链表在删除前后的数据元素依次输出到屏幕上；如果单链表中不存在这个数，就调用插入函数，将这个数插入到单链表尾，并将单链表在插入前后的数据元素依次输出到屏幕上
软件技术基础上机实验报告
姓名：肖燕平 学号：2011019090028
上机实验 二
Ex2_1（链表的创建和插入删除）
#include<stdio.h>
#include <malloc.h>
typedef struct node_type //定义链点
{
int data;
struct node_type *next;
}node_type;
typedef struct list_type //定义链表
{
node_type *head;
node_type *tail;
int length;
} list_type;
int read()
{
int x;
scanf("%d",&x);
return x;
}
void error(int x)
{
switch(x)
{
case 1:
printf("\nthe place of the data is wrong ,please input the place again\n");
break;
}
}
void creat_list(list_type *lianbiao) //创建链表
{
node_type *p,*s; //注意此处的指针要为链点结构体类型
int x;
lianbiao->head=(node_type*)malloc(sizeof(node_type));
lianbiao->length=0;
p=lianbiao->head;
while(lianbiao->length<5) //输入五个数
{
scanf("%d",&x);
s=(node_type*)malloc(sizeof(node_type));
s->data=x;
p->next=s;
p=s; //在链点连接上出现了问题导致后面显示链表时也出问题
lianbiao->length++;
}
p->next=NULL;
lianbiao->tail=p;
}
void show_list(list_type *lianbiao) //把链表元素打印出来
{
node_type *p;
p=lianbiao->head->next;
printf("\nThe linked list is\n\n");
while(p!=NULL)
{
printf("%d ",p->data);
p=p->next; //p往下走一步
}
printf("\nThe length of this linked list is %d\n",lianbiao->length);
}
void insert_list(list_type *lianbiao,int newdata,int place)
{
node_type *newnode,*p;
int i=0;
newnode=(node_type*)malloc(sizeof(node_type));
newnode->data=newdata;
p=lianbiao->head;
while(lianbiao->length+1<place||place<1)//判断插入的位置是否正确
{
error(1);
place=read(); //位置错误则重新输入位置
}
while(i<place-1) //使p指针指向插入位置的前一个
{
p=p->next;
i++;
}
newnode->next=p->next; //插入链点
p->next=newnode;
if(newnode->next==NULL)
{
lianbiao->tail=newnode; //若插入的位置为表尾，则改变尾指针
}
lianbiao->length++;
}
void delete_list(list_type *lianbiao,int place)
{
int i=0;
node_type *p,*g;
p=lianbiao->head;
while(place>lianbiao->length||place<1) //检查删除元素的位置是否符合要求
{
error(1);
place=read();
}
while(i<place-1) //使p指针指向删除位置的前一个
{
p=p->next;
i++;
}
g=p->next;
p->next=p->next->next; //删除链点
free(g);
if(p->next==NULL) //若删除的是最后一个元素，则改变尾指针的指向
{
lianbiao->tail=p;
}
lianbiao->length--; //链表长度自减一
}
void search_list(list_type *lianbiao,int number )//寻找那个整数
{
node_type *p;
int i=0;
int m;
m=lianbiao->length; //记录原来链表的长度
p=lianbiao->head;
while(p->next!=NULL) //p如果指向最后一个元素，则跳出循环
{
while(p->next->data==number)
{
delete_list(lianbiao,i+1);//p的下一个元素如果是这个数，那么删除
if(p->next==NULL)//若p已经指向最后一个那么跳出删除的循环
{
break;
}
}
if(p->next!=NULL) //若p没有指向最后一个那么让p指向下一个
{
p=p->next;
i++;
}
}
if(i==m) //若链表中元素没有与指定数相同的，则将数插入链表
{
insert_list(lianbiao,number,m+1);
}
}
void main()
{
list_type lianbiao;
int newdata,place;
int del_place;
int number;
printf("please input the the list\n");
creat_list(&lianbiao); //创建链表 ,把链表这一包含头和尾的指针传过去
show_list(&lianbiao); //而没有像书上一样传链点
printf("\nplease input the new data\n");
newdata=read();
printf("please input the place of the new data where it should be\n");
place=read();
insert_list(&lianbiao,newdata,place);
show_list(&lianbiao);
printf("\nplease input the place of the number which will be deleted\n");
del_place=read();
delete_list(&lianbiao,del_place);
show_list(&lianbiao);
printf("\nplease input the number that you want to search\n");
number=read();
search_list(&lianbiao,number);
show_list(&lianbiao);
}
输出数据如图所示
录入五个数
插入一个数
删除一个数
查找一个数，如果链表中有数与之相同，则删除这些数
问题及解决方法
问题1：创建链表时定义的指向结构体的指针没有定义为结构体类型
解决方法：将原先定义的int型改为结构体的类型
注意：指向结构体的指针要定义为结构体类型
问题2：未给链点动态分配空间
注意：定义一个结构体变量只分配一个结构体空间，而不是整个链表的空间都分配了，链表中每个链点的空间要动态申请
解决方法：没用一个链点前动态分配一个空间
问题3：定义了一个链表结构类型的的变量，但未定义或动态分配空间给该变量内部head指针所指向的结构体便直接访问该结构体，导致错误。
解决方法：再另动态分配空间给该指针变量所指向的结构体
注意：结构体定义时并未分配空间，系统给某指针分配了空间不代表给他的指向变量也分配了空间。
问题4：创建链表时各链点未衔接。
解决方法：再增加一个指针握住原链表。
注意：在使用动态分配空间增加链点时要使用两个指针，其中一个作为动态空间的指向，另一个握住原已经形成的链表。
并且，要注意分析链表时从中间开始去考虑
问题4：用scanf时输入不进数
遗漏了“&”！！！！
解决方法：加上。
注意：scanf如果多输了数，它会把值赋给下面的scanf，并且中间程序照跑；
总结：
编程前要先想好思路，列出流程，写出核心的算法。
对于链表类的程序，要先想模型，并且先从链表中间开始想思路，再想边界的问题。
注意删除链点后动态空间要释放。
程序太完美啦！！！
-
计算机软件技术基础实验报告
计算机软件技术基础实验报告姓名班级0801105学号日期20xx125班级0801105学号姓名第5周星期三910节成绩一实验目的…
-
计算机软件技术基础实验报告
山东建筑大学实验报告学院信电学院班级姓名课程计算机软件技术基础实验日期20xx年11月22日成绩实验八数据库应用系统开发一实验目的…
-
计算机软件技术基础实验报告
计算机软件基础实验报告实验一一元多项式的相加一实验的目的与要求1熟悉单链表的一些操作2掌握采用链表结构实现一元多项式的相加的算法二…
-
计算机软件技术基础实验报告
计算机软件技术基础实验报告专业年级学号学生姓名指导老师南华大学计算机学院编I实验要求1每次实验中有若干习题每个学生至少应该完成其中…
-
计算机软件基础实验报告
石家庄铁道大学实验报告课程名称计算机软件基础建筑与艺术学院系11021班试验者姓名学号实验日期年月日评分教师签名123456789…
-
大学计算机基础实验报告
大学计算机基础课程实验报告手册学院年级专业姓名学号2220xx319xx20xx任课教师上机地点以上由学生填写实验教师签字西南大学…
-
太原理工大学 计算机软件技术基础 顺序表的冒泡排序 实验报告
太原理工大学现代科技学院计算机软件技术基础课程实验报告专业班级学号姓名指导教师太原理工大学现代科技学院实验报告装订线实验名称顺序表…
-
计算机应用基础实验报告
上海建桥学院本科实验报告课程名称学号姓名专业班级计算机应用基础1222534单国原物流管理B121指导教师朱凯伦课内实验目录及成绩…
-
计算机软件技术基础上机实验报告
计算机软件基础实践报告题目C语言程序上机操作专业学生姓名准考证号指导教师20xx年5月1一单链表实验内容单链表的定义创建插入和删除…
-
软件技术基础实验报告——线性表的操作
软件开发技术基础实验报告姓名XXXXX学号XXXXXXXx班级XXXXXXX指导教师实验名称实验一线性表的操作班级学号姓名第周星期…
-
计算机软件技术实验报告
计算机软件技术基础实验报告实验一代码编写于VC60环境下includequotiostreamquotincludeltconio…