浙江科技学院《数据结构》实验报告年级班级学号姓名任课老师实验指导教师实验地点信息学院实验一线性表操作（一元多项式的运算）实验目的：1、定义线性表的链式存储2、实现对线性表的一些基本操作和具体函数定义实验要求：1、定义线性表的链式存储；2、实现对线性表的一些基本操作和具体函数定义。

3、定义输出一元多项式的函数；4、编写主程序调用上面的函数实现一元多项式的加减。

数据输入输出要求：输入示例：32 33 45 752 13 3-3 44 65 7（说明：第一个数据3表示该第一个一元多项式的项数为3，后面的2 3 表示第一项的系数为2 指数为3；按指数递增的次序输入）输出示例：一元多项式1： 2x(3)+3x(4)+5x(7)一元多项式2： 2x(1)+3x(3)-3x(4)+4x(6)+5x(7)加的结果：2x(1)+5x(3) +4x(6)+10x(7)减的结果：-2x(1)-1x(3)＋6x(4)-4x(6)程序代码：#include<map>#include<cstdlib>#include<iostream>#include<algorithm>#define null NULL#define polymal(poly*)malloc(sizeof(poly))using namespace std;struct poly{pair<int, int> data;poly* next;};void read(poly*a) {poly* poi = a;int n, xs, cs;cin >> n;for(int i = 0; i < n; i++) {poly* nex = polymal;cin >> cs >> xs;nex->data= make_pair(xs, cs);poi->next= nex;poi = poi->next;}poi->next= null;}void add(poly*a, poly*b, poly*ans) {poly* apo = a->next, *bpo = b->next, *cpo = ans;while(apo && bpo) {poly* sum = polymal;if(apo->data.first< bpo->data.first) {sum->data= apo->data;apo = apo->next;} else if(apo->data.first> bpo->data.first) {sum->data= bpo->data;bpo = bpo->next;} else{sum->data= make_pair(apo->data.first, apo->data.second+bpo ->data.second);apo = apo->next, bpo = bpo->next;if(!sum->data.second) {free(sum);continue;}}cpo->next= sum;cpo = cpo->next;}while(apo) {poly* sum = polymal;sum->data= apo->data;cpo->next= sum;cpo = cpo->next;apo = apo->next;}while(bpo) {poly* sum = polymal;sum->data= bpo->data;cpo->next= sum;cpo = cpo->next;bpo = bpo->next;}cpo->next= null;}void sub(poly*a, poly*b, poly*ans) {poly* apo = a->next, *bpo = b->next, *cpo = ans;while(apo && bpo) {poly* ex = polymal;if(apo->data.first< bpo->data.first) {ex->data= apo->data;apo = apo->next;} else if(apo->data.first> bpo->data.first) {ex->data= make_pair(bpo->data.first, -bpo->data.second);bpo = bpo->next;} else{ex->data= make_pair(apo->data.first, apo->data.second-bpo->data.second);apo = apo->next, bpo = bpo->next;if(!ex->data.second) {free(ex);continue;}}cpo->next= ex;cpo = cpo->next;}while(apo) {poly* sum = polymal;sum->data= apo->data;cpo->next= sum;cpo = cpo->next;apo = apo->next;}while(bpo) {poly* sum = polymal;sum->data= make_pair(bpo->data.first, -bpo->data.second);cpo->next= sum;cpo = cpo->next;bpo = bpo->next;}cpo->next= null;}void out(poly*a) {if(!a->next) {cout << 0;return;}poly* poi = a->next;cout << poi->data.second;if(poi->data.first) cout << "x("<< poi->data.first<< ")";poi = poi->next;while(poi) {if(poi->data.second> 0) cout << "+";cout << poi->data.second;if(poi->data.first) cout << "x("<< poi->data.first<< ")";poi = poi->next;}}int main() {poly* a, *b, *sumout, *subout;a = polymal;b = polymal;sumout = polymal;subout = polymal;read(a); read(b);cout << "一元多项式1: ";out(a);cout << endl << "一元多项式2: ";out(b);add(a, b, sumout);sub(a, b, subout);cout << endl << "加的结果: ";out(sumout);cout << endl << "减的结果: ";out(subout);return0;}运行结果：一元多项式1: 2x(3)+3x(4)+5x(7)+6x(8)一元多项式2: 2x(1)+3x(3)-3x(4)+4x(6)+5x(7) 加的结果: 2x(1)+5x(3)+4x(6)+10x(7)+6x(8)减的结果: -2x(1)-1x(3)+6x(4)-4x(6)+6x(8)实验二哈夫曼编码和译码实验目的：1、熟悉二叉树的顺序存储结构；2、熟悉二叉树的顺序存储结构和具体实现；3、熟悉哈夫曼编码和译码，及其在顺序存储结构下的实现实验要求：1、根据输入构造一棵哈夫曼树，要求该哈夫曼树的左子树小于等于右子树；2、根据构造的哈夫曼树给出对应的编码；左子树的编码为0，右子树的编码为1；3、输出各个字符对应的编码与平均编码长度；4、根据输入的编码，结合构造的哈夫曼树给出对应的译码5、对带有不同权值的字符进行编码；使用自己实现的编码表对输入的‘0’‘1’代码进行译码数据输入输出要求：输入示例：5A 8B 20C 30D 15E 27010*******#（说明：第一个数据5表示共有5个字符要编码，后面的“A 8”表示A的权为8，字符个数不超过20个；数据010*******＃是要解码的数据，最后以＃结束）输出示例：编码为：A 010B 00C 11D 011E 10平均编码长度为：2.23对应的译码为：ACDE程序代码：#include<map>#include<queue>#include<vector>#include<string>#include<iomanip>#include<cstdlib>#include<iostream>#include<algorithm>#define INF0x3f3f3f3f#define Binarytree_malloc(Binarytreepointer)malloc(sizeof(Binarytree))using namespace std;typedef struct Binarytree{int data;char ch;Binarytree *leftson, *rightson;void leaf_create(char ch) {this->ch= ch;cin >> data;leftson = nullptr;rightson = nullptr;}void father_create(Binarytree*leftson, Binarytree*rightson) {this->leftson= leftson;this->rightson= rightson;this->data= leftson->data+ rightson->data;}} Binarytree, *Binarytreepointer;struct Binarytreepointer_cmp{bool operator()(const Binarytreepointer a, const Binarytreepointer b) const{return(a->data) > (b->data);}};queue<char> leaf_ch;map<char, string> huffman_codes_map;priority_queue<Binarytreepointer, vector<Binarytreepointer>, Binarytreepointer_cmp> heap_sort;void read_leafnode() {int n;cin >> n;while(n--) {char ch;cin >> ch;Binarytreepointer leafnode = Binarytree_malloc;leafnode->leaf_create(ch);leaf_ch.push(ch);heap_sort.push(leafnode);}}Binarytreepointer huffman_bulid() {Binarytreepointer left_son = heap_sort.top(); heap_sort.pop();if(heap_sort.empty()) return left_son;Binarytreepointer right_son = heap_sort.top(); heap_sort.pop();Binarytreepointer father = Binarytree_malloc;father->father_create(left_son, right_son);heap_sort.push(father);return huffman_bulid();}pair<int, int> get_huffman_codes(Binarytreepointer root, string prefix) { if(root->leftson) {pair<int, int> left_average_coding_length = get_huffman_codes(root ->leftson, prefix + "0");pair<int, int> right_average_coding_length = get_huffman_codes(roo t->rightson, prefix + "1");return make_pair(left_average_coding_length.first+right_average_codin g_length.first, left_average_coding_length.second+right_average_coding_length.second) ;}huffman_codes_map[root->ch] = prefix;return make_pair(root->data* prefix.size(), root->data);}void print_huffman_codes(Binarytreepointer root) {pair<int, int> average_coding_length = get_huffman_codes(root, "");cout << "编码为:"<< endl;while(!leaf_ch.empty()) {char ch = leaf_ch.front(); leaf_ch.pop();cout << ch << " "<< huffman_codes_map[ch] << endl;}cout << "平均编码长度: "<< setw(2) << average_coding_length.first* 1.0/ average_coding_length .second<< endl;huffman_codes_map.clear();}void decode_huffman_codes(string key, Binarytreepointer root) {cout << "对应的编码为: ";for(int i = 0; ; ) {if(key[i] == '#') break;else{Binarytreepointer current = root;while(current->leftson) {if(key[i++] == '0') current = current->leftson;else current = current->rightson;}cout << current->ch;}}cout << endl;}void huffman_destroy(Binarytreepointer current) {if(current->leftson) {huffman_destroy(current->leftson);huffman_destroy(current->rightson);}free(current);}int main() {string key;read_leafnode();/*检验heap_sort正确性while(!heap_sort.empty()) {cout << heap_sort.top()->data << endl;heap_sort.pop();}*/cin >> key;Binarytreepointer huffman_root = huffman_bulid();print_huffman_codes(huffman_root);decode_huffman_codes(key, huffman_root);huffman_destroy(huffman_root);return0;}运行结果：编码为:A 010B 00C 11D 011E 10平均编码长度: 2.23对应的编码为: ACDE实验三求图的最小生成树实验目的：1、熟悉图的邻接矩阵、邻接表和边集数组表示；2、掌握建立图的邻接矩阵的算法；3、熟悉求图的最小生成树的普里姆算法和克鲁斯卡尔算法。