基本数据结构和算法回顾

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 = &current->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 = &current->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 = &current->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(&current->next,current->data);
33         plink = &current->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??
            

评论