近想回过头来看看以前写的一些代码，可叹为何刚进大学的时候不知道要养成写博客的好习惯。现在好多东西都没有做记录，后面也没再遇到相同的问题，忘的都差不多了。只能勉强整理了下面写的一些代码，这些代码有的有参考别人的代码，但都是自己曾经一点点敲的，挂出来，虽然很基础，但希望能对别人有帮助。
　　链表
　　链表是一种非常基本的数据结构，被广泛的用在各种语言的集合框架中。
　　首先链表是一张表，只不过链表中的元素在内存中不一定相邻，并且每个元素都可带有指向另一个元素的指针。
　　链表有，单项链表，双向链表，循环链表等。
　　单项链表的数据结构
　　如下
　　typedef struct NODE{
　　struct NODE * link;
　　int value;
　　} Node;
　　对链表的操作
　　主要有增删查
　　Node * create(){
　　Node * head，* p，* tail;
　　//  这里创建不带头节点的链表
　　head=NULL;
　　do
　　{
　　p=(Node*)malloc(LEN);
　　scanf("%ld"，&p->value);
　　if(p->value ==0) break;
　　//  第一次插入
　　if(head==NULL)
　　head=p;
　　else
　　tail->link=p;
　　tail=p;
　　}
　　while(1);
　　tail->link=NULL;
　　return head;
　　}
　　int delet(Node **linkp，int del_value){
　　register Node * current;
　　Node * m_del;
　　//寻找正确的删除位置，方法是按顺序访问链表，直到到达等于的节点
　　while((current = *linkp)!=NULL  &&  current->value != del_value)
　　{   
　　linkp = &current->link;
　　}
　　if(NULL==current)
　　return FALSE;
　　else
　　{
　　//把该节点删除，返回TRUE
　　m_del=current->link;
　　free(current);
　　*linkp=m_del;
　　}
　　return TRUE;
　　}
　　//需要形参为链表头指针的地址和要插入的值
　　int insert(Node **linkp，int new_value){
　　register Node * current;
　　Node * m_new;
　　//寻找真确的插入位置，方法是按顺序访问链表，直到到达其值大于或等于新插入值的节点
　　while((current = *linkp)!=NULL  &&  current->value < new_value)
　　{   
　　linkp = &current->link;
　　}
　　//为新节点分配内存，并把新值存到新节点中，如果分配失败，返回FALSE
　　m_new =(Node*)malloc(LEN);
　　if(NULL==m_new)
　　return FALSE;
　　m_new->value = new_value;
　　//把新节点放入链表，返回TRUE
　　m_new->link = current;
　　*linkp=m_new;
　　return TRUE;
　　}
　　仅仅只需要将尾指针指向头节点，可以构成单项循环链表，即tail->link=head;，有的时候，可能需要将链表逆置，当然，如果需要逆置，好一开始做双向链表。
　　Node * reverse(Node * head){
　　Node * p，*q;
　　q= head;
　　p = head->link;
　　head = NULL;
　　while(p)
　　{   
　　//  接到新链表里面去
　　q->link = head;
　　head  = q;
　　//  继续遍历原来的链表
　　q = p;
　　p = p->link;
　　}
　　q->link = head;
　　head  = q;
　　return  head;
　　}
　　删除链表中所有值为x的节点，以及清除链表中重复的节点
　　//    功能：    删除链表中所有值为x的节点
　　//    形参：    1、若不带头结点，便是链表头指针的地址，即&head
　　//            2、若带头结点，便是链表头节点的next域的地址，即&head->next
　　//    形参：    为链表头指针的地址和要删除的值
　　void del_link(Node ** plink，int x){
　　register Node * current;
　　while((current = *plink)!=NULL)
　　{
　　// 处理连续出现x的情况
　　while(current && current->data == x){
　　//  保留指向下一个节点的指针
　　Node * temp = current;
　　* plink = current = current->next;
　　//  删除当前节点
　　free(temp);
　　}
　　//向下遍历链表
　　if (current)
　　{
　　plink = &current->next;
　　}
　　}
　　}
　　//    功能：    删除链表中重复多余的节点
　　//    形参：    1、若不带头结点，便是链表头指针的地址，即&head
　　//            2、若带头结点，便是链表头节点的next域的地址，即&head->next
　　void del_linkAll(Node ** plink){
　　register Node * current;
　　while((current = *plink) != NULL){
　　//注意，这里取指向下一个元素的指针的地址，这样删除是会保留这一个节点
　　del_link(&current->next，current->data);
　　plink = &current->next;
　　}
　　}
　　对于双向链表，也是在节点中再添加一个节点，让它与另一个指针指向的方向相反。当然，当节点有了两个节点之后，可以构成更复杂的比如树图等复杂结构了，双向链表可像如下定义
　　#ifndef __LINKLISTEX_H__
　　#define __LINKLISTEX_H__
　　#include <string>
　　using std::string;
　　//================双向链表的定义===============
　　template<class T>
　　class DulLinkList
　　{
　　private:
　　typedef struct DulNode{
　　struct DulNode * prior;
　　T    data;
　　struct DulNode * next;
　　}DulNode;
　　DulNode * frist;
　　void Init();
　　void Del(DulNode * delNode);
　　public:
　　DulLinkList();
　　~DulLinkList();
　　void AddElem(const T &  data);
　　void DelElem(const T & data);
　　string ToString()const;
　　protected:
　　};
　　#endif//__LINKLISTEX_H__
　　对双向链表的操作也无外乎增删改
　　#include "LinkListEx.h"
　　#include <iostream>
　　using namespace  std;
　　template<class T>
　　DulLinkList<T>::DulLinkList(){
　　Init();
　　}
　　template<class T>
　　void DulLinkList<T>::Init(){
　　// 初始化第一个结点
　　this->frist = new DulNode;
　　this->frist->prior = NULL;
　　this->frist->next = NULL;
　　}
　　template<class T>
　　void DulLinkList<T>::AddElem(const T & data){
　　// 直接头部插入节点
　　DulNode * newNode = new DulNode;
　　newNode->data = data;
　　newNode->next = this->frist;
　　newNode->prior = NULL;
　　this->frist->prior = newNode;
　　this->frist = newNode;
　　}
　　template<class T>
　　void DulLinkList<T>::DelElem(const T & data){
　　DulNode * current = this->frist->next;
　　while (current  != NULL  && current->data != data) {
　　current = current->next;
　　}
　　if (!current)
　　{
　　return;
　　}
　　Del(current);
　　}
　　template<class T>
　　void DulLinkList<T>::Del(DulNode * delNode){
　　// 调整当前节点两端的节点的指针
　　delNode->prior->next = delNode->next;
　　delNode->next->prior = delNode->prior;
　　delete delNode;
　　}
　　template<class T>
　　DulLinkList<T>::~DulLinkList(){
　　DulNode * current = this->frist;
　　while (current)
　　{
　　DulNode * old = current;
　　current = current->next;
　　delete old;
　　}
　　}
　　template<class T>
　　string DulLinkList<T>::ToString()const{
　　string res;
　　DulNode * current = this->frist->next;
　　while (current)
　　{
　　res.append(1，current->data);
　　current = current->next;
　　}
　　return res;
　　}
　　链表是个很基础的东西，后面一些复杂的算法或数据结构的本质也是一个链表。链表和顺序表（也是数组）都可以再进一步抽象成更复杂的数据结构。
　　比如队列和栈，不过是在链表或顺序表的基础上限制单端操作而已。再比如，由链表和顺序表还可以构成二叉树堆，它们还可以组合使用构成邻接表，十字链表，邻接多重表等结构用来描述图，等等。
　　字符串相关算法
　　做里快两年web开发了，可以说字符串是用多多的数据类型了，所以针对字符串的算法也非常的多。先从简单的慢慢来。
　　首先基本的是对字符串的求长，连接，比较，复制等
　　// 统计字符串长度
　　int str_len(char *str){
　　return *str ? str_len(str+1)+1 : 0 ;
　　}
　　// 字符串复制
　　void str_cpy(char *str1，char *str2){
　　while(*str1++ = *str2++); //当str2指向''时，赋值给*str1 表达式的值为0 即为假。退出循环
　　//if(*str1 == '')    // 考虑到 串2的长度大于串1的长度，防止指针越界
　　//break;
　　}
　　// 字符串比较
　　int str_cmp(char *str1，char *str2){
　　int i;// i指向字符不同时数组下标
　　for(i=0;str1[i]==str2[i] && str1[i]!='' && str2[i]!='';i++);
　　return str1[i]-str2[i];
　　}
　　// 字符串连接
　　void str_cat(char *str1，char *str2){
　　while(*str1 != '')
　　str1++;
　　while(*str1++ = *str2++);
　　}
　　字符串比较复杂一点的是模式匹配和子序列（编辑距离）的问题。
　　首先是较为简单的BF算法，这种算法原理非常简单，比如连个串a（主串）和b（模式串），首先将a1和b1进行比较，如果相同，则将b2与a2进行比较，如果还相同，继续拿a3与b3比，直到b串匹配完，怎匹配完成，如果出现不同的，怎回到初的状态，将b1与a2进行比较，将b2与a3比较，等等，如此反复直到失败或成功。
　　typedef struct{
　　char * str;
　　int length;
　　}String;
　　int Index_BF(String mainStr，String modeStr，int pos){
　　int    i = pos-1;
　　int    j = 0;
　　while (i<mainStr.length && j<modeStr.length)
　　{
　　if (mainStr.str[i] == modeStr.str[j])
　　{
　　i++，j++;
　　}
　　else{
　　// 出现不同的，回退到模式第一个字符的状态，将模式右移进行匹配
　　i = i - j + 2;
　　j = 0;
　　}
　　}
　　if (j==modeStr.length)
　　{
　　return i - modeStr.length;
　　}
　　else{
　　return 0;
　　}
　　}
　　较为复杂的算法是kmp算法，KMP算法的关键是避免BF算法中的回朔。并且当匹配失败后向右滑动到一个能自左大对齐的位置继续匹配。
　　若在ai，bj的位置匹配失败，所以已经匹配的串便是
　　B1 B2 … Bj-1 == Ai-j+1 Ai-j+2 … Ai-1;
　　假设滑动完后要让Bk与Ai对齐，则应该有
　　B1 B2 B3 … Bk-1 == Ai-k+1 A-k+2 … Ai-1;
　　因为是向右滑动，想一想i的位置不变，B向右滑动，很显然，k要小于j。
　　所以进一步可以得到k到j之间B的子串（Bj前面的k-1个字符）与Ai前的k-1个字符是相同的，即
　　Bj-k+1 Bj-k+2 … Bj-1 == Ai-k+1 Ai-k+2 … Ai-1;
　　所以有
　　B1 B2 B3 … Bk-1  == Bj-k+1 Bj-k+2 … Bj-1
　　可以看出来，这个有个特点，字符串 B1 B2 ….. Bj-1关于Bk有种对称的感觉，不过这个不是镜像对称，不过我还是喜欢这么记`对称`，这也是求next值的依据，这个next是k，是偏移值。
　　next(j) = 0 (j==1) || max{k|1<=k<j && B1 B2 B3 … Bk-1  == Bj-k+1 Bj-k+2 … Bj-1} || 1；
　　下面是完整的KMP算法
　　void GetNext(const char * mode，int * next){
　　//求模式mode的next值并存入数组next中
　　int i=1，j=0;
　　next[1] = 0;
　　while(i < mode[0]){
　　if(0 == j || mode[i] == mode[j]){
　　i++;j++;
　　next[i] = j;
　　}
　　else
　　j = next[j];
　　}
　　}
　　int Index_KMP(const char * str，const char * mode，int pos){
　　int i=pos，j=1;
　　int * next = (int *)malloc(sizeof(int)*(mode[0]+1));
　　next[0]=mode[0];
　　GetNext(str，next);
　　while (i<=str[0] && j<= mode[0]) {
　　if (0==j || str[i] == mode[j]) {
　　i++;j++;
　　}
　　else{
　　// 滑动模式串，注意next[j]是小于j的，这才是向右滑动
　　j = next[j];
　　}
　　}
　　return j>mode[0] ?  i - mode[0] : 0;
　　}
　　void main(){
　　char string[16] = "16abcabcabaabcac";
　　char mode[10] = "10abaabcac";
　　printf("模式串在主串中的位置:%d "，Index_KMP(string，mode，1));
　　}
　　下面的问题是长公共子序列，算法的思想是动态规划，核心是转义方程

　　，也是当两个字符相等时取左上元素+1，不相等时取左和上中大的那个
　　#include <stdio.h>
　　#include <string.h>
　　#define MAXN 128
　　#define MAXM MAXN
　　int a[MAXN][MAXM];
　　int b[MAXN][MAXM];
　　char * str1 = "ABCBDAB";
　　char * str2 = "BDCABA";
　　int LCS(const char *s1，int m， const char *s2，int n)
　　{
　　int i， j;
　　a[0][0] = 0;
　　for( i=1; i <= m; ++i ) {
　　a[i][0] = 0;
　　}
　　memset(b，0，sizeof(b));
　　for( i=1; i <= n; ++i ) {
　　a[0][i] = 0;
　　}
　　for( i=1; i <= m; ++i ){
　　for( j=1; j <= n; ++j ){
　　if(s1[i-1]==s2[j-1]){          //如果想等，则从对角线加1得来
　　a[i][j] = a[i-1][j-1]+1;
　　b[i][j] = 1;
　　}
　　else if(a[i-1][j]>a[i][j-1]){    //否则判段它上面、右边的值，将大的数给他
　　a[i][j]= a[i-1][j];
　　b[i][j] = 2;
　　}
　　else{
　　a[i][j] = a[i][j-1];
　　b[i][j] = 3;
　　}
　　}
　　}
　　return a[m][n];
　　}
　　char str[MAXN];
　　int p=0;
　　void cSubQ(int i，int j){
　　if(i<1 || j<1) return;
　　if(1==b[i][j]){
　　cSubQ(i-1，j-1);
　　str[p++]=str1[i-1];
　　}
　　else if(2 == b[i][j])
　　{
　　cSubQ(i-1，j);
　　}
　　else{
　　cSubQ(i，j-1);
　　}
　　}
　　int main()
　　{
　　int m = strlen(str1)， n = strlen(str2);
　　LCS(str1，m，str2，n);
　　cSubQ(m，n);
　　str[p] = '';
　　printf("%s "，str);
　　return 0;
　　}
　　很显然，这个算法的时间复杂度和空间复杂度为o(n*m)
　　二叉树
　　树这里主要以二叉树为例，二叉树算是一种特殊的树，一种特殊的图。
　　二叉树具备如下特征
　　第i层多有2^(i-1)次方个节点
　　深度为k的树多有2^i-1个节点，也是满二叉树等比求和
　　n0=n2+1，即叶子节点的数量恰好是度为2的节点数加1，主要原因是节点数总比度数多1，因为根节点没有入度，所以有 n0 + n1 + n2 -1 = n1 + 2*n2。
　　对于满二叉树，如果以有序表存储，根节点放在0的位置上，左右孩子放在1，2上，相当于从上到下，从左到右，从0开始对节点进行编号，则对于节点i，它的左孩子应该位于2*i+1上，右孩子位于2*i+2上
　　等等，暂时只记得这些了。
　　用数组和链表都可以存储二叉树，但我见过的算法大都用数组存储二叉树，想必链表虽然易于理解，但相比写起算法来未必好写。
　　对二叉树的操作
　　有增删查遍历等操作，代码如下。
　　typedef struct bitnode{
　　int m_iDate;
　　struct bitnode * m_lChild/*左孩子指针*/，* m_rChild/*右孩子指针*/;       
　　} CBiTNode;
　　//建立一个带头结点的空的二叉树
　　CBiTNode * Initiate(){
　　CBiTNode * bt;
　　bt = (CBiTNode*)malloc(sizeof CBiTNode);
　　bt->m_iDate = 0;
　　bt->m_lChild = NULL;
　　bt->m_rChild = NULL;
　　return bt;
　　}
　　/*
　　//建立一个不带头结点的空的二叉树
　　CBiTNode * Initiate(){
　　CBiTNode * bt;
　　bt = NULL;
　　return bt;
　　}
　　*/
　　//生成一棵以x为根节点数据域信息，以lbt和rbt为左右子树的二叉树
　　CBiTNode * Create(int x，CBiTNode * lbt，CBiTNode * rbt){
　　CBiTNode * p;
　　if((p=(CBiTNode*)malloc(sizeof CBiTNode)) ==NULL)
　　return NULL;
　　p->m_iDate = x;
　　p->m_lChild = lbt;
　　p->m_rChild = rbt;
　　return p;
　　}
　　//在二叉树bt中的parent所指节点和其左子树之间插入数据元素为x的节点
　　bool InsertL(int x，CBiTNode * parent){
　　CBiTNode * p;
　　if(NULL == parent){
　　printf("L插入有误");
　　return 0;
　　}
　　if((p=(CBiTNode*)malloc(sizeof CBiTNode)) ==NULL)
　　return 0;
　　p->m_iDate = x;
　　p->m_lChild = NULL;
　　p->m_rChild = NULL;
　　if(NULL == parent->m_lChild)
　　parent->m_lChild = p;
　　else{
　　p->m_lChild = parent->m_lChild;
　　parent->m_lChild = p;
　　}
　　return 1;
　　}
　　//在二叉树bt中的parent所指节点和其右子树之间插入数据元素为x的节点
　　bool InsertR(int x，CBiTNode * parent){
　　CBiTNode * p;
　　if(NULL == parent){
　　printf("R插入有误");
　　return 0;
　　}
　　if((p=(CBiTNode*)malloc(sizeof CBiTNode)) ==NULL)
　　return 0;
　　p->m_iDate = x;
　　p->m_lChild = NULL;
　　p->m_rChild = NULL;
　　if(NULL == parent->m_rChild)
　　parent->m_rChild = p;
　　else{
　　p->m_rChild = parent->m_rChild;
　　parent->m_rChild = p;
　　}
　　return 1;
　　}
　　//在二叉树bt中删除parent的左子树
　　bool DeleteL(CBiTNode *parent){
　　CBiTNode * p;
　　if(NULL == parent){
　　printf("L删除出错");
　　return 0;
　　}
　　p = parent->m_lChild;
　　parent->m_lChild = NULL;
　　free(p);//当*p为分支节点时，这样删除只是删除了子树的根节点。子树的子孙并没有被删除
　　return 1;
　　}
　　//在二叉树bt中删除parent的右子树
　　bool DeleteR(CBiTNode *parent){
　　CBiTNode * p;
　　if(NULL == parent){
　　printf("R删除出错");
　　return 0;
　　}
　　p = parent->m_rChild;
　　parent->m_rChild = NULL;
　　free(p);//当*p为分支节点时，这样删除只是删除了子树的根节点。子树的子孙并没有被删除
　　return 1;
　　}
　　//二叉树的遍历
　　//先序遍历二叉树
　　bool PreOrder(CBiTNode * bt){
　　if(NULL == bt)
　　return 0;
　　else{
　　printf("bt->m_iDate == %d "，bt->m_iDate);
　　PreOrder(bt->m_lChild);
　　PreOrder(bt->m_rChild);
　　return 1;
　　}
　　}
　　对二叉树可以有先序遍历，中序遍历，后序遍历得到的序列中每个元素互第一个和后一个节点外都会有一个前驱和后驱节点。如果把前驱节点和后驱节点的信息保存在节点中构成了线索二叉树，显然只要免礼一遍能得到线索二叉树。
　　二叉树比较经典的有哈夫曼编码问题，二叉堆等问题，二叉堆放到堆排序一起讲。
　　哈夫曼问题是要让频率高的节点编码短，也是要节点在哈夫曼树中的深度小。
　　//    Huffman.h
　　#ifndef __HUFFMAN_H__
　　#define __HUFFMAN_H__
　　typedef struct {
　　unsigned int weight;
　　unsigned int parent，lchild，rchild;
　　}HTNode，* HuffmanTree;            // 动态分配数组储存哈夫曼树
　　typedef char * *HuffmanCode;    // 动态分配数组储存哈夫曼编码表
　　#endif//__HUFFMAN_H__
　　//    HuffmanTest.cpp
　　#include "Huffman.h"
　　#include <string.h>
　　#include <malloc.h>
　　// 函数功能：在哈夫曼编码表HT[1...range]中选择 parent 为0且weight小的两个结点，将序号分别存到s1和s2里
　　void Select(const HuffmanTree &HT，int range，int &s1，int &s2){
　　int i;
　　int * pFlags;
　　pFlags = (int *)malloc((range+1)*sizeof(int));
　　int iFlags=0;
　　for(i=1;i<=range;i++){
　　if(0 == HT[i].parent){
　　pFlags[++iFlags] = i;
　　}
　　}
　　int Min=1000;
　　int pMin=pFlags[1];
　　for(i=1;i<=iFlags;i++){
　　if(HT[pFlags[i]].weight < Min){
　　pMin = i;
　　Min=HT[pFlags[i]].weight;
　　}
　　}
　　s1=pFlags[pMin];
　　Min=1000;
　　for(i=1;i<=iFlags;i++){
　　if(pFlags[i]!=s1)
　　if(HT[pFlags[i]].weight < Min){
　　pMin = i;
　　Min=HT[pFlags[i]].weight;
　　}
　　}
　　s2=pFlags[pMin];
　　}
　　void HuffmanCoding(HuffmanTree &HT，HuffmanCode &HC，int * w， int n){
　　// w存放n个字符的权值（均>0），构造哈夫曼树HT，并求出n个字符的哈夫曼编码HC
　　if(n <= 1) return;
　　int m = 2*n-1;
　　HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode));        // 0 单元不使用
　　int i;
　　HuffmanTree p=NULL;
　　// 初始化哈夫曼编码表
　　for(p=HT+1，i=1;i<=n;i++，p++，w++){
　　p->weight = *w，p->parent = p->lchild = p->rchild = 0;
　　}
　　for( ;i<=m;i++，p++){
　　p->weight = p->parent = p->lchild = p->rchild = 0;
　　}
　　// 建立哈夫曼树
　　int s1，s2;
　　for(i=n+1;i<=m;i++){
　　Select(HT，i-1，s1，s2);
　　HT[s1].parent = HT[s2].parent = i;
　　HT[i].lchild = s1，HT[i].rchild = s2;
　　HT[i].weight = HT[s1].weight+HT[s2].weight;
　　}
　　// 从叶子节点到根逆向求每个字符的哈夫曼编码
　　HC = (HuffmanCode)malloc((n+1)*sizeof(char *));        // 分配n个字符编码的头指针向量
　　char * cd = (char*)malloc(n*sizeof(char));            // 分配求编码的工作空间
　　int start;                                            // 编码起始位置
　　cd[n-1] = '';                                        // 编码结束符
　　for(i=1;i<=n;i++){                                    // 逐个字符求哈夫曼编码
　　start = n-1;                                    // 将编码起始位置和末位重合
　　for(int c=i，f=HT[i].parent;f != 0; c=f，f=HT[f].parent){
　　if(c == HT[f].lchild)
　　cd[--start] = '0';
　　else
　　cd[--start] = '1';
　　}
　　HC[i] = (char*)malloc((n-start)*sizeof(char));    // 为第i个字符编码分配空间
　　strcpy(HC[i]，&cd[start]);                        // 从 cd 复制字符串到 HC
　　}
　　free(cd);
　　}
　　哈夫曼树的测试数据
　　#include "Huffman.h"
　　#include <stdio.h>
　　#include <stdlib.h>
　　void HuffmanCoding(HuffmanTree &HT，HuffmanCode &HC，int * w， int n);
　　void main(){
　　system("color F0");
　　HuffmanTree HT = NULL;
　　HuffmanCode HC = NULL;
　　char chArr[8]={'A'，'B'，'C'，'D'，'E'，'F'，'G'，'H'};
　　int w[8]={7，19，2，6，32，3，21，10};
　　HuffmanCoding(HT，HC，w，8);
　　int i，j;
　　printf(    "HT    weight   parent  lchild  rchild ");
　　for(i=1;i<=15;i++){
　　printf("%02d %2u %2u %2u %2u "，i，HT[i].weight，HT[i].parent，HT[i].lchild，HT[i].rchild);
　　}
　　printf(" 字符    权值    编码 ");
　　for(i=0;i<8;i++){
　　printf("%c %2d %-8s "，chArr[i]，w[i]，HC[i+1]);
　　}
　　}

　　图相关算法
　　图是一种比较复杂的数据结构，图的定义不在此复述了。
　　图的一些表示方法（存储结构）