什么是哈夫曼树 哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的带权路径长度记为WPL=(W1L1+W2L2+W3L3+…+ WnLn)，N个权值Wi(i=1,2,…n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li(i=1,2,…n)。可以证明哈夫曼树的WPL是最小的。 构造哈夫曼树的算法如下： 1）对给定的n个权值{W1,W2,W3,…,Wi,…,Wn}构成n棵二叉树的初始集合F={T1,T2,T3,…,Ti,…, Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。 2）在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。 3）从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。 4）重复2）和3），直到集合F中只有一棵二叉树为止。 例如，对于4个权值为1、3、5、7的节点构造一棵哈夫曼树，其构造过程如下图所示： 哈夫曼树的算法实现 #include<iostream>#include<iomanip>#include<cfloat>using namespace std; const int n=5; const int m=2*n-1; typedef struct{ float weight; int parent,lchild,rchild; }nodetype; typedef nodetype hftree[m]; hftree T; void huffman(hftree T){ int p1,p2,i,j; float small1,small2; for(i=0;i<n;i++){ T[i].parent=T[i].lchild=T[i].rchild=-1; } for(i=0;i<n;i++){ cin>>T[i].weight; } for(i=n;i<m;i++){ p1=p2=-1; small1=small2=FLT_MAX; for(j=0;j<=i-1;j++){ if(T[j].parent!=-1)continue; if(T[j].weight<small1){ small2=small1; small1=T[j].weight; p2=p1; p1=j; } else if(T[j].weight<small2){ small2=T[j].weight; p2=j; } } T[p1].parent=T[p2].parent=i; T[i].parent=-1; T[i].lchild=p1; T[i].rchild=p2; T[i].weight=small1+small2; } } 输出哈夫曼树 这里用到了头文件，主要是运用setw()控制一下输出的格式……

阅读全文

算法的基本思想：依次输入结点信息，若输入的结点不是虚结点，则建立一个新结点；若新结点是第1个结点，则令其为根节点；否则将新结点作为孩子链接到它的双亲结点上。如此重复下去，直到输入字符“#”为止 核心代码： Bitree level_create(){ char ch; pointer Q[maxsize+1]; int front,rear; pointer root,s; root=NULL; front=rear=0; while(cin>>ch,ch!='#'){ if(ch!='@'){ s=new node; s->data=ch; s->lchild=s->rchild=NULL; } else s=NULL; rear++;//不管结点是否为虚，都要入队 Q[rear]=s; if(rear==1){//第一个结点是根，要修改头指针，它不是孩子 root=s; front=1; } else{ if(s&&Q[front]){ if(rear%2==0)Q[front]->lchild=s; else Q[front]->rchild=s; } if(rear%2==1)front++;//不论是否为虚，右孩子入队后，双亲出队 } } return root; } ……

阅读全文

在学习算法spfa的过程之中，其代码的实现过程是用了链式前向星结构实现，因此了解并学习了一下链式前向星 什么是链式前向星 前向星的本质其实是静态链表，如果说邻接表存的是点的集合，那么链式前向星是存的是边的集合。 为什么要采用链式前向星 如果说邻接表是不好写但效率好，邻接矩阵是好写但效率低的话，前向星就是一个相对中庸的数据结构。前向星固然好些，但效率并不高。而在优化为链式前向星后，效率也得到了较大的提升。虽然说，世界上对链式前向星的使用并不是很广泛，但在不愿意写复杂的邻接表的情况下，链式前向星也是一个很优秀的数据结构。 主要代码实现 struct Edge { int next;//下一条边的编号 int to;//这条边到达的点 int dis;//这条边的长度 }edge[maxm]; void add_edge(int from,int to,int dis) //加入一条从from到to距离为dis的单向边 { edge[++num_edge].next=head[from]; edge[num_edge].to=to;//将to记录 edge[num_edge].dis=dis;//将dis记录 head[from]=num_edge;// } head[i]数组与next 关于head[i]的含义，我们理解为指向 i 结点的第一条边。这是方便于我们在接下来调用的时候能够完好的访问：i结点第一条边通过head访问，剩下的边通过next指针指向。 总的来说： head[i]来指向 i 结点的第一条边 next指向下一条边 调用核心代码 for(int i=head[k];i!=0;i=edge[i].next) ……

阅读全文

#include<iostream>using namespace std; typedef int datatype; const int maxsize = 100; typedef struct node { datatype data[maxsize]; int front, rear; }sqqueue; void init_sqqueue(sqqueue* lq) { lq->front = lq->rear = 0; cout << "创建队列成功" << endl; } int en_sqqueue(sqqueue* lq, datatype x) { if ((lq->rear + 1) % maxsize == lq->front) { cout << "队满，无法入队" << endl; return 0; } lq->rear = (lq->rear + 1) % maxsize; lq->data[lq->rear] = x; cout << "入队元素为" << x << endl; return 1; } int de_sqqueue(sqqueue* lq, datatype* x) { if (lq->front == lq->rear) { cout << "队列为空" << endl; return 0; } lq->front = (lq->front + 1) % maxsize; *x = lq->data[lq->front]; cout << "出队元素为" << *x << endl; return 1; } int empty_sqqueue(sqqueue* lq) { if (lq->front == lq->rear) { cout << "队空" << endl; return 1; } else { cout << "队不空" << endl; return 0; } } int main() { sqqueue* lq; datatype* x; x = new datatype; lq = new sqqueue; init_sqqueue(lq); empty_sqqueue(lq); en_sqqueue(lq, 100); en_sqqueue(lq, 200); empty_sqqueue(lq); de_sqqueue(lq, x); de_sqqueue(lq, x); empty_sqqueue(lq); return 0; } ……

阅读全文

最近数据结构老师要求我们在上机课上要不看书敲出来链式队列并实现功能，所以在此练练手 由于比较简单，所以直接上代码 #include<iostream> using namespace std; typedef int datatype; typedef struct node* pointer; struct node{ datatype data; pointer next; }; typedef struct{ pointer front,rear; }lkqueue; void init_lkqueue(lkqueue *lq){//创建链队列 pointer p; p=new node; p->next=NULL; lq->front=p; lq->rear=p; } void enter_lkqueue(lkqueue *lq,datatype x){//入队功能实现 pointer s; s=new node; s->data=x; lq->rear->next=s; lq->rear=s; s->next=NULL; } int empty_lkqueue(lkqueue *lq){//判断队列是否为空 if(lq->front==lq->rear)return 1; else return 0; } int out_lkqueue(lkqueue *lq,datatype *x){//出队功能实现 pointer s; if(lq->front==lq->rear){ cout<<"队空，不能出队!"<<endl; return 0; } s=lq->front->next; *x=s->data; lq->front->next=s->next; cout<<"出队元素为"<<*x<<endl; delete s; return 1; } int main(){ lkqueue *lq; lq=new lkqueue; datatype *x; x=new datatype; init_lkqueue(lq); empty_lkqueue(lq); enter_lkqueue(lq,100); empty_lkqueue(lq); out_lkqueue(lq,x); empty_lkqueue(lq); return 0; } ……

阅读全文

对着书本敲了一个钟的二叉树，被二叉树建立时的输入问题困扰了很久。二叉树的建立一般使用递归算法，将所有节点的数据猛的输入，递归无法停止，二叉树就无法建立。 自己对着书本敲了一次也没发现怎么回事，最后看了一篇博文之后，豁然开朗。我们在输入节点数据的时候，必须输入空闲叶子结点，并用特殊符号标记。 最后自己终于实现了最终的二叉链表的构造及其三种顺序遍历的实现 PS：输入的时候得适当制造一定数量的空节点才能结束二叉树的输入，这个需要个人自己体会。 代码如下： #include <iostream> using namespace std; typedef struct node* pointer; typedef char datatype; typedef struct node { datatype data; pointer left, right; }BinTNode;//定义结构体BinTNode typedef BinTNode* BinTree;//结构体指针BinTree BinTree Create_Tree()//二叉树的创建 { BinTree p; char c; cin >> c; if (c == '#')//如果遇到字符串"#"，则设该结点值为空 p = NULL; else { p = new node; p->data = c; p->left = Create_Tree(); p->right = Create_Tree(); } return p;//返回二叉树结构体指针 } void preorder(BinTree T) {//先序遍历 if (T !……

阅读全文

思路分析： 只需要用一个变量来存储余数，并入栈即可。另外需要注意一下maxsize-1才是栈满；p.data[p.top]代表的是datatype x的值。 下面是代码实现： #include <iostream> using namespace std; const int maxsize = 16; typedef int datatype; typedef struct { datatype data[maxsize]; int top; }sqstack; void init_sqstack(sqstack* sq) { sq->top = -1; } int empty_sqstack(sqstack* sq) { if (sq->top == -1)return 1; else return 0; } int push_sqstack(sqstack* sq, datatype x) { if (sq->top == maxsize - 1) { cout << "栈满，不能进栈！\n"; return 0; } sq->data[++sq->top] = x; return 1; } int pop_sqstack(sqstack* sq, datatype* x) { if (sq->top == -1) { cout << "栈空，不能退栈!……

阅读全文

如何用栈实现简单的括号匹配 思路很简单，利用栈的压栈出栈的特点，输入的字符为“（”就入栈，“）”就出栈，如果栈是空，就是匹配成功，因为“（）”成对出现。 接下来为代码实现，分别是C++本身的STL库中的stack和自己手写的stack功能实现： C++STL: #include<iostream> #include<stack> using namespace std; stack<int>st; int main(){ char x; int flag,a,b; while(cin>>x){ if(x=='('){ st.push(x); } if(x==')'){ st.pop(); } if(st.empty()){ flag=1; } else { flag=0; } } if(flag){ cout<<"1"<<endl; }else { cout<<"0"<<endl; } return 0; } 自己手写的栈功能： #include<iostream> using namespace std; const int maxsize=100; typedef char datatype; typedef char ElemType; typedef struct{ datatype data[maxsize]; int top; }sqstack; void init_sqstack(sqstack *sq){ sq->top=-1; } int empty(sqstack *sq){ if(sq->top==-1){ return 1; } else return 0; } int push_sqstack(sqstack *sq,datatype x){ if(sq->top==maxsize-1){ cout<<"栈满，不能进栈!……

阅读全文

数据结构上机课的一次作业： 实现多项式的加法。开始并没有立刻做出来，主要原因是用insert插入的时候的i值没有把握好，以及当值两个链表中的指数相等的时候的处理没有到位。后来经过一番修改后，功能都得以实现。 当天晚上学习了一下怎么放图片博客，终于万事俱备，开始写博客啦 #include <iostream> using namespace std; typedef int datatype; typedef int index; typedef struct node* pointer; struct node { datatype data; index ind; pointer next; }; typedef pointer lklist; lklist init() { pointer head; head = new node; head->next = NULL; return head; } lklist create(lklist head) { pointer rear, s; int a,b; rear = head; while (cin >> a >> b && (a != -1 && b !……

阅读全文