iht算法
A. 由于c++中没有实现如python中的string.split()和list.length()的方法，所以我自己写了两个程序,但有问题
很简单的问题啊，你仔细想一下，python的split切分出来的字符串数组是什么类型呢？list类型的啊！比如
x="abc def hgij"
x.split() 返回 ['abc', 'def', 'hgij']
那在C++中我也会整一个std::list啊，
std::list<string&> mystrlist;
来了一个字符串x
string x="abc def hgij"
pos1=x.find_first_not_of( ' ', pos2 );
截取到一段字符串之后
string y = x.substr( pos1, pos2-pos1 )
插入到list里面
mystrlist.push_back( y )
完事之后就可以对mystrlist做你想做的操纵了
mystrlist.size()
B. http://www.pudn.com/downloads518/sourcecode/math/detail2151378.html帮忙下载，谢谢
压缩感知 重构算法集合 包含：CoSaMP,GBP,IHT,IRLS,MP,OMP,SP
Reconstruction algorithms for sparse Representation of Compressed Sensing
https://share.weiyun.com/
C. 求一个关于二叉树的报告。 内容包括：（1）在二叉链表上实现二叉树运算 （2）哈夫曼编码和译码系统
这是哈夫曼树
#include<iostream.h>
#include<malloc.h>
#include<string.h>
#define MAXSIZE 30
#define MAX 100
typedef struct
{
char data;
int weight;
int parent; //父结点下标
int left; //左、右孩子结点下标
int right;
}HTNode,*HuffmanTree;
typedef char * *HuffmanCode;
typedef struct
{
char data;
int weight;
}Tdata;
HuffmanTree HT; //结构体变量
HuffmanCode HC; //定义的一个变量
void SelectMinTree(HuffmanTree HT,int n,int *sl,int *s2);
void HuffmanCoding(HuffmanTree HT,Tdata *w,int n);
int main()
{
Tdata w[MAXSIZE];
int n,i;
cout<<" 请输入元素数"<<endl;
cin>>n;
for(i=1;i<=n;i++)
{
cout<<" 输入第 "<<i<<" 点的数和权值:"<<endl;
cin>>w[i].data>>w[i].weight;
}
cout<<" ***********结果*************"<<endl;
HuffmanCoding(HT,w,n);
for(i=1;i<=n;i++)
cout<<w[i].data<<" ---------->"<<HC[i]<<endl;
return 0;
}
//从ht位置，查找未加入哈夫曼树的权值最小的两个数的位置S1,S2
//S1为权值最小的位置，S2为权值第二小的位置
void SelectMinTree(HuffmanTree HT,int n,int *s1,int *s2) //选最小生成树
{
int i,min1,min2;
* s2=* s1 = 0; //初始化为0位置
min1=min2=MAX;
for(i=1;i<=n;i++) //n表示总共有几个数
{
if(HT[i].parent==0) //还没处理过的，以前是初始化的
if(HT[i].weight<min1) //如小于r1的权则设置r1为i
{
min2 = min1;
min1 = HT[i].weight;
*s2 = *s1;
*s1 = i;
}
else
if(HT[i].weight<min2) //如大于r1的权，再和r2的权比较
{
min2 = HT[i].weight;
*s2 = i;
}
//从i等于3开始比较
}
}
void HuffmanCoding(HuffmanTree HT,Tdata *w,int n)
{
int m,i,s1,s2,start,c,f;
HTNode *p;
char *cd;
if(n <= 1) return; //n为结点的个数
m = 2*n -1; //总共有这么多个结点
HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode));
//初始化 哈夫曼树顺序存储结构
for(p=HT+1,i=1;i<=n;i++,p++)
{
p->data=w[i].data;
p->weight=w[i].weight;
p->left=0;
p->right=0;
p->parent=0;
}
for(;i<=m;i++,p++)
{
p->weight=0;
p->left=0;
p->right=0;
p->parent=0;
}
//构建哈夫曼树
for(i=n+1;i<=m;i++)
{
//在HT[1~i-1]中选择parent为0且weight最小的两个结点，其序号分别为s1和s2
SelectMinTree(HT,i-1,&s1,&s2);
HT[s1].parent = i; //把s1结点加入哈夫曼树，并设置他们的父结点位置为i
HT[s2].parent = i; //把s2结点加入哈夫曼树，并设置他们的父结点位置为i
HT[i].left = s1; //设置i结点的左孩子为s1
HT[i].right = s2; //设置i结点的右孩子为s2
HT[i].weight=HT[s1].weight+HT[s2].weight;//设置i结点的权值为s1和s2左右孩子权值的和
}
//创建哈夫曼编码
HC = (HuffmanCode) malloc((n+1)*sizeof(char *));
cd = (char *)malloc(n*sizeof(char)); //cd数组用于保存哈夫曼编码
cd[n-1] = '\0'; //设置字符串结束符
for(i=1;i<=n;i++) //分别输出n个结点的哈夫曼编码
{
start=n-1; //注意从cd数组的末尾向前加入编码
for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)//从叶子结点往上走到根结点为止
if(HT[f].left == c)
cd[--start] = '0'; //左0，
else
cd[--start] = '1'; //右1
HC[i] = (char *)malloc((n-start)*sizeof(char));
strcpy(HC[i],&cd[start]); //拷贝函数，把&cd[start]拷贝给HC[i]
}
free(cd); //释放空间
}
二叉树运算
#include<iostream.h>
#include<malloc.h>
#define FALSE 0
#define TRUE 1
#define OK 1
#define maxsize 100
typedef int status;
typedef int elemtype;
typedef struct binode
{
elemtype data;
struct binode *lchild,*rchild;
}binode,*bitree;
status treecreated=FALSE;
int leafcount=0;
status createbitree(bitree *t);
status preordertraverse(bitree t);
int height(bitree t);
void swap(bitree *t);
void leafcounts(bitree t);
void main()
{
int choice=0;
status leave=FALSE,flag;
binode *bt;
cout<<"===========二叉树演示程序==============="<<endl;
do
{
cout<<"1：创建一个二叉树，按先序遍历结果输入，空用0表示 "<<endl;
cout<<"2：先序遍历二叉树，递归方式遍历二叉树 "<<endl;
cout<<"3：求叶子数"<<endl;
cout<<"4：计算二叉树的高度"<<endl;
cout<<"5: 树进行左右翻转"<<endl;
cout<<"0：退出"<<endl;
cout<<"-------请输入你的选择:"<<endl;
cin>>choice;
switch(choice)
{
case 1:
if(treecreated)
{
cout<<"sorry,the tree has been already created!"<<endl;
break;
};
cout<<"请输入代表树的数字："<<endl;
flag=createbitree(&bt);
if(flag==OK)
{
cout<<"你已经建立了一棵树了！"<<endl;
treecreated=TRUE;
}
break;
case 2:
if(!treecreated)
{
cout<<"sorry,you must create a tree for further steps!"<<endl;
break;
}
cout<<"先序遍历顺序:"<<endl;
preordertraverse(bt);
cout<<endl;
break;
case 3:
if(!treecreated)
{
cout<<"sorry,you must create a tree for further steps!"<<endl;
break;
}
leafcounts(bt);
cout<<"树的叶子数:"<<leafcount<<endl;
cout<<endl;
break;
case 4:
int h;
h=height(bt);
cout<<"树的高度:"<<h<<endl;
break;
case 5:
swap(&bt);
cout<<"树已经翻转！！！"<<endl;
break;
case 0:
leave=TRUE;
break;
}
}while(!leave);
cout<<" 谢谢 再见了！！！"<<endl;
}
//递归方法实现创建
status createbitree(bitree *t)
{
int ch=0;
cin>>ch;
if(ch==0) //输入如果是0表示是空
(*t)=NULL;
else
{
(*t)=(bitree)malloc(sizeof(binode)); //申请空间
(*t)->data=ch; //把数据传给他
createbitree(&(*t)->lchild); //左孩子重新进入创建函数
createbitree(&(*t)->rchild); //右孩子重新进入创建函数
}
return OK;
}
//递归方法实现先序遍历
status preordertraverse(bitree t)
{
if(t)
{
cout<<t->data<<" "; //先把头结点输出
preordertraverse(t->lchild); //然后是左结点
preordertraverse(t->rchild); //然后是右结点
return OK;
}
else
return OK;
}
int height(bitree t)
{
int hl,hr;
if(t==NULL)
return 0;
hl=height(t->lchild)+1; //最下面的左孩子加一
hr=height(t->rchild)+1; //最下面的右孩子加一
return (hl>hr?hl:hr); //比较谁大就取谁
}
void swap(bitree *t) //进行左右翻转
{
bitree p;
if(*t!=NULL)
{
p=(*t)->lchild; //p为中间变量
(*t)->lchild=(*t)->rchild;
(*t)->rchild=p;
swap(&(*t)->lchild);
swap(&(*t)->rchild);
}
}
void leafcounts(bitree t) //求叶子数
{
if(t) //如果不为空
{
if(t->lchild==NULL && t->rchild==NULL)//左右孩子都为空 表明是叶子
leafcount++;
leafcounts(t->lchild);
leafcounts(t->rchild);
}
}
D. 压缩感知理论基本介绍
姓名：王鑫磊
学号：21011110262
学院：通信工程学院
【嵌牛导读】压缩感知是信号处理领域进入21世纪以来取得的最耀眼的成果之一，并在磁共振成像、图像处理等领域取得了有效应用。压缩感知理论在其复杂的数学表述背后蕴含着非常精妙的思想。基于一个有想象力的思路，辅以严格的数学证明，压缩感知实现了神奇的效果，突破了信号处理领域的金科玉律——奈奎斯特采样定律。即，在信号采样的过程中，用很少的采样点，实现了和全采样一样的效果。
【嵌牛鼻子】压缩感知，欠采样，稀疏恢复
【嵌牛提问】压缩感知相比奈奎斯特采样定律的主要突破是什么？
【嵌牛正文】
1.CS的初步理解
CS是一个针对信号采样的技术，是在采样过程中完成数据压缩的过程。我们知道在对模拟信号按一定采样频率进行采样并得到数字信号的过程中，要想完整保留原始信号中的信息，采样频率必须大于信号中最高频率的2倍（奈奎斯特采样定理）。但Candes等人又提出了，如果信号在频域是稀疏的，那么它可以由远低于采样定理要求的采样点重建恢复。Nyquist定理中的采样为等间距采样，若采样频率低必然会引起混叠，如果不等间距采样呢？如果是随机采样呢？随机采样必然会发生频谱泄露，但泄露会均匀分布在整个频域且泄露值都较小，而最大的几个峰值可以通过设置阈值检测出来，从而有了恢复出原始信号的可能。
图1展示了一原始的模拟信号在频域是稀疏的，仅由三个频率分量组成，为了得到数字信号，首先要在时域对其进行采样，根据压缩感知理论，可以在时域进行随机亚采样，之后得到的频谱会产生如图所示的泄露，但可以通过阈值检测求出原始信号的真实频率分量，从而恢复出原始信号。
2. CS的数学模型
CS有两个前提条件：
假设：x是长度为N的原信号，稀疏度为k，它是未知的；Φ为测量矩阵，对应采样过程，也就是压缩的过程，如随机采样，是已知的；采样后的结果为：y=Φx，也是已知的；因此压缩感知问题是：在已知测量值y和测量矩阵Φ的基础上，求解原信号x的过程。然而一般信号x本身并不稀疏，需要在某种稀疏基上进行稀疏表示，即x=Ψs, 其中s为稀疏向量，即为所求的稀疏信号；Ψ为稀疏基矩阵，也叫稀疏变换矩阵，如傅里叶变换。
于是最终问题表示为：
y = ΦΨs = Θs （1）
已知y，Φ，Ψ，求s， Θ称为感知矩阵。感知矩阵需要满足约束等距原则（RIP），因此需要测量矩阵Φ和稀疏基Ψ满足不相关，即采样过程与稀疏过程不相关。Candes等人又找到了独立同分布的高斯随机测量矩阵可以称为普适的压缩感知测量矩阵，于是满足高斯分布的随机测量矩阵就成了CS最常用的观测矩阵。
3. CS的常用方法
已知(1)方程有无数解，因此需要通过增加约束来得到唯一解。方程是稀疏的，因此我们需要找到这个方程里所有解中最稀疏的内个就行了。
求解上述方程一般有三种思路：凸优化算法，贪婪算法，贝叶斯理论。CS常用算法有：
基追踪重构算法 （Basis Pursuit, BP）：BP算法是一种凸优化方法。
正交匹配追踪算法 （OMP）：OMP属于贪婪算法。
阈值迭代算法 ： 包括软阈值迭代（ISTA）和迭代硬阈值（IHT）。ISTA的一种改进方法为快速阈值迭代（FISTA）。
【嵌牛参考】
[1]. Dandes, E. J. . “Near-optimal signal recovery from random projections.” Universal encoding strategies IEEE Transactions on Information Theory 52(2006).
[2]. Donoho, D. L. . “Compressed sensing.” IEEE Transactions on Information Theory 52.4(2006):1289-1306.