基本数据结构和算法回顾
2015-08-01 03:37:00 2519 次浏览 去博主博客园看原文
最近想回过头来看看以前写的一些代码，可叹为何刚进大学的时候不知道要养成写博客的好习惯。现在好多东西都没有做记录，后面也没再遇到相同的问题，忘的都差不多了。只能勉强整理了下面写的一些代码，这些代码有的有参考别人的代码，但都是自己曾经一点点敲的，挂出来，虽然很基础，但希望能对别人有帮助。 链表
最近想回过头来看看以前写的一些代码，可叹为何刚进大学的时候不知道要养成写博客的好习惯。现在好多东西都没有做记录，后面也没再遇到相同的问题，忘的都差不多了。只能勉强整理了下面写的一些代码，这些代码有的有参考别人的代码，但都是自己曾经一点点敲的，挂出来，虽然很基础，但希望能对别人有帮助。
链表
链表是一种非常基本的数据结构，被广泛的用在各种语言的集合框架中。
首先链表是一张表，只不过链表中的元素在内存中不一定相邻，并且每个元素都可带有指向另一个元素的指针。
链表有，单项链表，双向链表，循环链表等。
单项链表的数据结构
如下
1 typedef struct NODE{ 2 struct NODE * link; 3 int value; 4 } Node;
对链表的操作
主要有增删查
1 Node * create(){ 2 Node * head,* p,* tail; 3 // 这里创建不带头节点的链表 4 head=NULL; 5 do 6 { 7 p=(Node*)malloc(LEN); 8 scanf("%ld",&p->value); 9 10 if(p->value ==0) break; 11 // 第一次插入 12 if(head==NULL) 13 head=p; 14 else 15 tail->link=p; 16 tail=p; 17 } 18 while(1); 19 tail->link=NULL; 20 return head; 21 } 22 23 int delet(Node **linkp,int del_value){ 24 register Node * current; 25 Node * m_del; 26 27 //寻找正确的删除位置，方法是按顺序访问链表，直到到达等于的节点 28 while((current = *linkp)!=NULL && current->value != del_value) 29 { 30 linkp = ¤t->link; 31 } 32 33 if(NULL==current) 34 return FALSE; 35 else 36 { 37 //把该节点删除，返回TRUE 38 m_del=current->link; 39 free(current); 40 *linkp=m_del; 41 } 42 return TRUE; 43 } 44 //需要形参为链表头指针的地址和要插入的值 45 int insert(Node **linkp,int new_value){ 46 register Node * current; 47 Node * m_new; 48 49 //寻找真确的插入位置，方法是按顺序访问链表，直到到达其值大于或等于新插入值的节点 50 while((current = *linkp)!=NULL && current->value < new_value) 51 { 52 linkp = ¤t->link; 53 } 54 //为新节点分配内存，并把新值存到新节点中，如果分配失败，返回FALSE 55 m_new =(Node*)malloc(LEN); 56 if(NULL==m_new) 57 return FALSE; 58 m_new->value = new_value; 59 //把新节点放入链表，返回TRUE 60 61 m_new->link = current; 62 *linkp=m_new; 63 64 return TRUE; 65 }
仅仅只需要将尾指针指向头节点，就可以构成单项循环链表，即tail->link=head;，有的时候，可能需要将链表逆置，当然，如果需要逆置，最好一开始就做双向链表。
1 Node * reverse(Node * head){ 2 Node * p,*q; 3 q= head; 4 p = head->link; 5 head = NULL; 6 while(p) 7 { 8 // 接到新链表里面去 9 q->link = head; 10 head = q; 11 // 继续遍历原来的链表 12 q = p; 13 p = p->link; 14 } 15 q->link = head; 16 head = q; 17 return head; 18 }
删除链表中所有值为x的节点，以及清除链表中重复的节点
1 // 功能： 删除链表中所有值为x的节点 2 // 形参： 1、若不带头结点，便是链表头指针的地址，即&head 3 // 2、若带头结点，便是链表头节点的next域的地址，即&head->next 4 // 形参： 为链表头指针的地址和要删除的值 5 void del_link(Node ** plink,int x){ 6 register Node * current; 7 while((current = *plink)!=NULL) 8 { 9 // 处理连续出现x的情况 10 while(current && current->data == x){ 11 // 保留指向下一个节点的指针 12 Node * temp = current; 13 * plink = current = current->next; 14 // 删除当前节点 15 free(temp); 16 } 17 18 //向下遍历链表 19 if (current) 20 { 21 plink = ¤t->next; 22 } 23 } 24 } 25 // 功能： 删除链表中重复多余的节点 26 // 形参： 1、若不带头结点，便是链表头指针的地址，即&head 27 // 2、若带头结点，便是链表头节点的next域的地址，即&head->next 28 void del_linkAll(Node ** plink){ 29 register Node * current; 30 while((current = *plink) != NULL){ 31 //注意，这里取指向下一个元素的指针的地址，这样删除是会保留这一个节点 32 del_link(¤t->next,current->data); 33 plink = ¤t->next; 34 } 35 }
对于双向链表，也就是在节点中再添加一个节点，让它与另一个指针指向的方向相反。当然，当节点有了两个节点之后，就可以构成更复杂的比如树图等复杂结构了，双向链表可像如下定义
1 #ifndef __LINKLISTEX_H__ 2 #define __LINKLISTEX_H__ 3 #include <string> 4 using std::string; 5 //================双向链表的定义=============== 6 template<class T> 7 class DulLinkList 8 { 9 private: 10 typedef struct DulNode{ 11 struct DulNode * prior; 12 T data; 13 struct DulNode * next; 14 }DulNode; 15 DulNode * frist; 16 void Init(); 17 void Del(DulNode * delNode); 18 public: 19 DulLinkList(); 20 ~DulLinkList(); 21 void AddElem(const T & data); 22 void DelElem(const T & data); 23 string ToString()const; 24 protected: 25 }; 26 #endif//__LINKLISTEX_H__
对双向链表的操作也无外乎增删改
1 #include "LinkListEx.h" 2 #include <iostream> 3 using namespace std; 4 5 template<class T> 6 DulLinkList<T>::DulLinkList(){ 7 Init(); 8 } 9 10 template<class T> 11 void DulLinkList<T>::Init(){ 12 // 初始化第一个结点 13 this->frist = new DulNode; 14 this->frist->prior = NULL; 15 this->frist->next = NULL; 16 } 17 18 template<class T> 19 void DulLinkList<T>::AddElem(const T & data){ 20 // 直接头部插入节点 21 DulNode * newNode = new DulNode; 22 newNode->data = data; 23 newNode->next = this->frist; 24 newNode->prior = NULL; 25 this->frist->prior = newNode; 26 this->frist = newNode; 27 } 28 29 30 template<class T> 31 void DulLinkList<T>::DelElem(const T & data){ 32 DulNode * current = this->frist->next; 33 while (current != NULL && current->data != data) { 34 current = current->next; 35 } 36 if (!current) 37 { 38 return; 39 } 40 Del(current); 41 } 42 43 template<class T> 44 void DulLinkList<T>::Del(DulNode * delNode){ 45 // 调整当前节点两端的节点的指针 46 delNode->prior->next = delNode->next; 47 delNode->next->prior = delNode->prior; 48 delete delNode; 49 } 50 template<class T> 51 DulLinkList<T>::~DulLinkList(){ 52 DulNode * current = this->frist; 53 while (current) 54 { 55 DulNode * old = current; 56 current = current->next; 57 delete old; 58 } 59 } 60 61 template<class T> 62 string DulLinkList<T>::ToString()const{ 63 string res; 64 DulNode * current = this->frist->next; 65 while (current) 66 { 67 res.append(1,current->data); 68 current = current->next; 69 } 70 return res; 71 }
链表是个很基础的东西，后面一些复杂的算法或数据结构的本质也是一个链表。链表和顺序表（也就是数组）都可以再进一步抽象成更复杂的数据结构。
比如队列和栈，不过是在链表或顺序表的基础上限制单端操作而已。再比如，由链表和顺序表还可以构成二叉树堆，它们还可以组合使用构成邻接表，十字链表，邻接多重表等结构用来描述图，等等。
字符串相关算法
做里快两年web开发了，可以说字符串是用多最多的数据类型了，所以针对字符串的算法也非常的多。先从简单的慢慢来。
首先最基本的是对字符串的求长，连接，比较，复制等
1 // 统计字符串长度 2 int str_len(char *str){ 3 return *str ? str_len(str+1)+1 : 0 ; 4 } 5 // 字符串复制 6 void str_cpy(char *str1,char *str2){ 7 while(*str1++ = *str2++); //当str2指向'\0'时，赋值给*str1 表达式的值为0 即为假。退出循环 8 //if(*str1 == '\0') // 考虑到 串2的长度大于串1的长度，防止指针越界 9 //break; 10 } 11 // 字符串比较 12 int str_cmp(char *str1,char *str2){ 13 int i;// i指向字符不同时数组下标 14 for(i=0;str1[i]==str2[i] && str1[i]!='\0' && str2[i]!='\0';i++); 15 return str1[i]-str2[i]; 16 } 17 // 字符串连接 18 void str_cat(char *str1,char *str2){ 19 while(*str1 != '\0') 20 str1++; 21 while(*str1++ = *str2++); 22 }
字符串比较复杂一点的就是模式匹配和子序列（编辑距离）的问题。
首先是较为简单的BF算法，这种算法原理非常简单，比如连个串a（主串）和b（模式串），首先将a1和b1进行比较，如果相同，则将b2与a2进行比较，如果还相同，继续拿a3与b3比，直到b串匹配完，怎匹配完成，如果出现不同的，怎回到最初的状态，将b1与a2进行比较，将b2与a3比较，等等，如此反复直到失败或成功。
1 typedef struct{ 2 char * str; 3 int length; 4 }String; 5 6 int Index_BF(String mainStr,String modeStr,int pos){ 7 int i = pos-1; 8 int j = 0; 9 while (i<mainStr.length && j<modeStr.length) 10 { 11 if (mainStr.str[i] == modeStr.str[j]) 12 { 13 i++,j++; 14 } 15 else{ 16 // 出现不同的，回退到模式第一个字符的状态，将模式右移进行匹配 17 i = i - j + 2; 18 j = 0; 19 } 20 } 21 if (j==modeStr.length) 22 { 23 return i - modeStr.length; 24 } 25 else{ 26 return 0; 27 } 28 }
较为复杂的算法是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算法
1 void GetNext(const char * mode,int * next){ 2 //求模式mode的next值并存入数组next中 3 int i=1,j=0; 4 next[1] = 0; 5 while(i < mode[0]){ 6 if(0 == j || mode[i] == mode[j]){ 7 i++;j++; 8 next[i] = j; 9 } 10 else 11 j = next[j]; 12 } 13 } 14 int Index_KMP(const char * str,const char * mode,int pos){ 15 int i=pos,j=1; 16 int * next = (int *)malloc(sizeof(int)*(mode[0]+1)); 17 next[0]=mode[0]; 18 GetNext(str,next); 19 while (i<=str[0] && j<= mode[0]) { 20 if (0==j || str[i] == mode[j]) { 21 i++;j++; 22 } 23 else{ 24 // 滑动模式串，注意next[j]是小于j的，这才是向右滑动 25 j = next[j]; 26 } 27 } 28 return j>mode[0] ? i - mode[0] : 0; 29 } 30 31 void main(){ 32 char string[16] = "\016abcabcabaabcac"; 33 char mode[10] = "\010abaabcac"; 34 printf("模式串在主串中的位置:%d\n",Index_KMP(string,mode,1)); 35 }
下面的问题是最长公共子序列，算法的思想是动态规划，核心是转义方程
，也就是当两个字符相等时取左上元素+1，不相等时取左和上中大的那个
1 #include <stdio.h> 2 #include <string.h> 3 #define MAXN 128 4 #define MAXM MAXN 5 int a[MAXN][MAXM]; 6 int b[MAXN][MAXM]; 7 char * str1 = "ABCBDAB"; 8 char * str2 = "BDCABA"; 9 10 int LCS(const char *s1,int m, const char *s2,int n) 11 { 12 int i, j; 13 a[0][0] = 0; 14 for( i=1; i <= m; ++i ) { 15 a[i][0] = 0; 16 } 17 memset(b,0,sizeof(b)); 18 for( i=1; i <= n; ++i ) { 19 a[0][i] = 0; 20 } 21 for( i=1; i <= m; ++i ){ 22 for( j=1; j <= n; ++j ){ 23 if(s1[i-1]==s2[j-1]){ //如果想等，则从对角线加1得来 24 a[i][j] = a[i-1][j-1]+1; 25 b[i][j] = 1; 26 } 27 else if(a[i-1][j]>a[i][j-1]){ //否则判段它上面、右边的值，将大的数给他 28 a[i][j]= a[i-1][j]; 29 b[i][j] = 2; 30 } 31 else{ 32 a[i][j] = a[i][j-1]; 33 b[i][j] = 3; 34 } 35 36 } 37 } 38 return a[m][n]; 39 } 40 char str[MAXN]; 41 int p=0; 42 void cSubQ(int i,int j){ 43 if(i<1 || j<1) return; 44 if(1==b[i][j]){ 45 cSubQ(i-1,j-1); 46 str[p++]=str1[i-1]; 47 } 48 else if(2 == b[i][j]) 49 { 50 cSubQ(i-1,j); 51 } 52 else{ 53 cSubQ(i,j-1); 54 } 55 } 56 int main() 57 { 58 int m = strlen(str1), n = strlen(str2); 59 LCS(str1,m,str2,n); 60 cSubQ(m,n); 61 str[p] = '\0'; 62 printf("%s\n",str); 63 return 0; 64 }
很显然，这个算法的时间复杂度和空间复杂度为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上
- 等等，暂时只记得这些了。
用数组和链表都可以存储二叉树，但我见过的算法大都用数组存储二叉树，想必链表虽然易于理解，但相比写起算法来未必好写。
对二叉树的操作
有增删查遍历等操作，代码如下。
1 typedef struct bitnode{ 2 int m_iDate; 3 struct bitnode * m_lChild/*左孩子指针*/,* m_rChild/*右孩子指针*/; 4 } CBiTNode; 5 6 7 //建立一个带头结点的空的二叉树 8 CBiTNode * Initiate(){ 9 CBiTNode * bt; 10 bt = (CBiTNode*)malloc(sizeof CBiTNode); 11 bt->m_iDate = 0; 12 bt->m_lChild = NULL; 13 bt->m_rChild = NULL; 14 return bt; 15 } 16 17 /* 18 //建立一个不带头结点的空的二叉树 19 CBiTNode * Initiate(){ 20 CBiTNode * bt; 21 bt = NULL; 22 return bt; 23 } 24 */ 25 26 //生成一棵以x为根节点数据域信息，以lbt和rbt为左右子树的二叉树 27 CBiTNode * Create(int x,CBiTNode * lbt,CBiTNode * rbt){ 28 CBiTNode * p; 29 if((p=(CBiTNode*)malloc(sizeof CBiTNode)) ==NULL) 30 return NULL; 31 p->m_iDate = x; 32 p->m_lChild = lbt; 33 p->m_rChild = rbt; 34 return p; 35 } 36 37 //在二叉树bt中的parent所指节点和其左子树之间插入数据元素为x的节点 38 bool InsertL(int x,CBiTNode * parent){ 39 CBiTNode * p; 40 41 if(NULL == parent){ 42 printf("L插入有误"); 43 return 0; 44 } 45 46 if((p=(CBiTNode*)malloc(sizeof CBiTNode)) ==NULL) 47 return 0; 48 49 p->m_iDate = x; 50 p->m_lChild = NULL; 51 p->m_rChild = NULL; 52 53 if(NULL == parent->m_lChild) 54 parent->m_lChild = p; 55 else{ 56 p->m_lChild = parent->m_lChild; 57 parent->m_lChild = p; 58 } 59 60 return 1; 61 } 62 63 //在二叉树bt中的parent所指节点和其右子树之间插入数据元素为x的节点 64 bool InsertR(int x,CBiTNode * parent){ 65 CBiTNode * p; 66 67 if(NULL == parent){ 68 printf("R??
评论