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.