数据结构

发表于 | 分类于 | 本文总阅读量 次

anyview
最后修改：2017.09.29

1 第一章 绪论

1.1 以k阶Fibonacci数列开头吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**********
【题目】已知k阶裴波那契序列的定义为
    f(0)=0, f(1)=0, ..., f(k-2)=0, f(k-1)=1;
    f(n)=f(n-1)+f(n-2)+...+f(n-k), n=k,k+1,...
试编写求k阶裴波那契序列的第m项值的函数算法，
k和m均以值调用的形式在函数参数表中出现。
**********/
Status Fibonacci(int k, int m, int &f) 
//注意函数参数带个'&'符号的代表引用变量,会真实地改变f值.
/* 求k阶斐波那契序列的第m项的值f */
{   
    int i,j;
    int a[100];
    if(k<2||m<0)/*k<2为负数*/
        return ERROR;
    if(m<k-1) { 
        f=0;/*这个数列就是前k-1项为0*/
    }
    if(m==k-1){ 
        f=1;
    }
    if(m>k-1){
        a[k-1]=1;
        for(i=0;i<=k-2;i++)
            a[i]=0;/*保证前这么多项是0*/
        for(i=k;i<=m;i++){
            f=0;
    /*这一步置0很有意思，一般我们很容易疏忽已经定义的变量*/
            for(j=i-k;j<i;j++)/*仔细看这里*/
            f+=a[j];
            a[i]=f;
        }/*真相大白，其实不是前所有项之和而是前k项的和*/
        f=a[m];
    }
    return OK;
}

1.2 从结点创建开始

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**********
【题目】链表的结点和指针类型定义如下
    typedef struct LNode {
       ElemType  data;
       struct LNode *next;
    } LNode, *LinkList;
试写一函数，构建一个值为x的结点。
***********/
LinkList MakeNode(ElemType x)
/* 构建一个值为x的结点，并返回其指针。*/
/* 若构建失败，则返回NULL。          */
{
    LNode L;
    L.data=x;
    LNode *p=&L;
    return p;
}

1.3 从一个到两个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**********
【题目】链表的结点和指针类型定义如下
    typedef struct LNode {
       ElemType  data;
       struct LNode *next;
    } LNode, *LinkList;
试写一函数，构建长度为2且两个结点的值依次为x和y的链表。
**********/
LinkList CreateLinkList(ElemType x, ElemType y) 
/* 构建其两个结点的值依次为x和y的链表。*/
/* 若构建失败，则返回NULL。           */
{   LNode a,b;
    LNode *p=&a;
    LNode *q=&b;
    if(p==NULL||q==NULL) return NULL;
    a.data=x;
    b.data=y;
    a.next=q;
    return p;
}

2 第二章 线性数据结构


典型线性数据结构：

栈：只允许在序列末端操作；
队列：只允许在序列两端操作；
线性表：允许在序列任意位置操作；


线性结构的存储：

顺序存储：逻辑相邻=物理相邻，借助相对位置关系表示逻辑关系；
链式存储：借助指示数据元素存储地址的指针表示元素之间的逻辑；

顺序栈与链栈：前者一次分配好空间，后者一个一个结点分配空间；

2.1 顺序栈基本操作！

2.1.1 顺序栈的判空

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**********
【题目】试写一算法，实现顺序栈的判空操作
StackEmpty_Sq(SqStack S)。
顺序栈的类型定义为：
typedef struct {
  ElemType *elem; // 存储空间的基址
  int top;        // 栈顶元素的下一个位置，简称栈顶位标
  int size;       // 当前分配的存储容量
  int increment;  // 扩容时，增加的存储容量
} SqStack;        // 顺序栈
***********/
Status StackEmpty_Sq(SqStack S)
/* 对顺序栈S判空。                      */ 
/* 若S是空栈，则返回TRUE；否则返回FALSE */
{
    if(S.top==0)
    return TRUE;
    else return FALSE;
}

变式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**********
【题目】若顺序栈的类型重新定义如下。试编写算法，
实现顺序栈的判空操作。
typedef struct {
  ElemType *elem; // 存储空间的基址
  ElemType *top;  // 栈顶元素的下一个位置
  int size;       // 当前分配的存储容量
  int increment;  // 扩容时，增加的存储容量
} SqStack2;
***********/
Status StackEmpty_Sq2(SqStack2 S)
/* 对顺序栈S判空。                      */ 
/* 若S是空栈，则返回TRUE；否则返回FALSE */
{
    if(S.elem==S.top)
    return TRUE;
    else return FALSE;
}

2.1.2 取栈顶元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**********
【题目】试写一算法，实现顺序栈的取栈顶元素操作
GetTop_Sq(SqStack S, ElemType &e)。
顺序栈的类型定义为：
typedef struct {
  ElemType *elem;  // 存储空间的基址
  int top;         // 栈顶元素的下一个位置，简称栈顶位标
  int size;        // 当前分配的存储容量
  int increment;   // 扩容时，增加的存储容量
} SqStack;         // 顺序栈
***********/
Status GetTop_Sq(SqStack S, ElemType &e) 
/* 取顺序栈S的栈顶元素到e，并返回OK； */ 
/* 若失败，则返回ERROR。              */
{
    if(S.top==NULL){
        return ERROR;
    }else
    e=S.elem[S.top-1];
    return OK;
}

2.1.3 出栈Pop

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**********
【题目】试写一算法，实现顺序栈的出栈操作
Pop_Sq(SqStack &S, ElemType &e)。
顺序栈的类型定义为：
typedef struct {
  ElemType *elem;  // 存储空间的基址
  int top;         // 栈顶元素的下一个位置，简称栈顶位标
  int size;        // 当前分配的存储容量
  int increment;   // 扩容时，增加的存储容量
} SqStack;         // 顺序栈
***********/
Status Pop_Sq(SqStack &S, ElemType &e) 
/* 顺序栈S的栈顶元素出栈到e，并返回OK；*/ 
/* 若失败，则返回ERROR。               */
{
    if(S.top==NULL) return ERROR;
    else {
        e=S.elem[--S.top];
        return OK;
    }
}

2.1.4 入栈Push

1
2
3
4
5
6
7
8
9
10
11
Status Push_Sq(SqStack &S,ElemType &e)
{ //若栈顶位标已到达所分配的容量，则栈满，扩容
    ElemType *newbase;
    if(S.top>=S.size){
        newbase = (ElemType*)realloc(S.elem,(S.size+S.increment)*sizeof(Elemtype));
        if(NULL==newbase) return OVERFLOW;
        S.elem = newbase;
        S.size += S.increment;
    }
    S.elem[S.top++] = e; //注意，若S.top定义为ElemType而不是int,需要改写成 *(S.top++)=e ， 判空改写成S.elem==S.top；
}

2.1.5 扩容

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**********
【题目】若顺序栈的类型重新定义如下。试编写算法，
构建初始容量和扩容增量分别为size和inc的空顺序栈S。
typedef struct {
  ElemType *elem; // 存储空间的基址
  ElemType *top;  // 栈顶元素的下一个位置
  int size;       // 当前分配的存储容量
  int increment;  // 扩容时，增加的存储容量
} SqStack2;
***********/
Status InitStack_Sq2(SqStack2 &S, int size, int inc)
/* 构建初始容量和扩容增量分别为size和inc的空顺序栈S。*/ 
/* 若成功，则返回OK；否则返回ERROR。                 */
{
    S.elem=(ElemType*)malloc(sizeof(ElemType));
    if(NULL==S.elem||size<=0||inc<=0) return ERROR;
    else{
        S.top=S.elem;
        S.size=size;
        S.increment=inc;
        return OK;
    }
    
}

2.2 循环队列

2.2.1 循环队列的长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**********
【题目】试写一算法，求循环队列的长度。
循环队列的类型定义为：
typedef struct {
  ElemType *base;  // 存储空间的基址
  int front;       // 队头位标
  int rear;        // 队尾位标，指示队尾元素的下一位置
  int maxSize;     // 最大长度
} SqQueue;
***********/
int QueueLength_Sq(SqQueue Q)
/* 返回队列Q中元素个数，即队列的长度。 */ 
{
    if( Q.front == (Q.rear+1) % Q.maxSize ) //满
        return Q.maxSize-1;
    else if(Q.front ==Q.rear) //空
        return 0;
    else{
        return Q.rear>Q.front?(Q.rear-Q.front):(Q.maxSize-Q.front+Q.rear);
    }
}

2.2.2 tag标识入队出队

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**********
【题目】如果希望循环队列中的元素都能得到利用，
则可设置一个标志域tag，并以tag值为0或1来区分尾
指针和头指针值相同时的队列状态是"空"还是"满"。
试编写与此结构相应的入队列和出队列的算法。
本题的循环队列CTagQueue的类型定义如下：
typedef struct {
  ElemType elem[MAXQSIZE];
  int tag;
  int front;
  int rear;
} CTagQueue;
**********/
Status EnCQueue(CTagQueue &Q, ElemType x)
/* 将元素x加入队列Q，并返回OK；*/
/* 若失败，则返回ERROR。       */
{
    if(Q.tag&&Q.front==Q.rear) return ERROR;
    else{
        Q.elem[Q.rear]=x;
        Q.rear=(Q.rear+1)%MAXQSIZE;
        if(Q.rear==Q.front) Q.tag=1;
        return OK;
    }
}
Status DeCQueue(CTagQueue &Q, ElemType &x)
/* 将队列Q的队头元素退队到x，并返回OK；*/
/* 若失败，则返回ERROR。               */
{
    if(!Q.tag&&Q.front==Q.rear) return ERROR;
    else{
        x=Q.elem[Q.front];
        Q.front=(Q.front+1)%MAXQSIZE;
        if(Q.rear==Q.front) Q.tag=0;
        return OK;
    }
}

2.2.3 循环队列的k阶Fibonacci

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**********
【题目】已知k阶斐波那契序列的定义为:
    f0=0,  f1=0,  …,  fk-2=0,  fk-1=1;
    fn=fn-1+fn-2+…+fn-k,  n=k,k+1,…
试利用循环队列编写求k阶斐波那契序列中第
n+1项fn的算法。
本题的循环队列的类型定义如下：
typedef struct {
  ElemType *base; // 存储空间的基址
  int front;      // 队头位标
  int rear;       // 队尾位标，指示队尾元素的下一位置
  int maxSize;    // 最大长度
} SqQueue;
**********/
long Fib(int k, int n)
/* 求k阶斐波那契序列的第n+1项fn */
{
    long fn;
    int i,j;
    SqQueue Q;
    Q.base=(ElemType*)malloc(sizeof(ElemType));
    if(NULL==Q.base)return ERROR;
    Q.maxSize=k;
    Q.front=0;
    Q.rear=0;    
    for(i=0;i<k-1;i++){
        Q.base[Q.rear]=0; //前k-1项置0
        Q.rear=(Q.rear+1)%Q.maxSize;
    }
    Q.base[Q.rear]=1;
    Q.rear=(Q.rear+1)%Q.maxSize;
    if(n<k-1)return 0;
    if(n==k-1)return 1;
    for(i=k;i<n+1;i++){
        fn=0;
        for(j=0;j<k;j++){
            fn+=Q.base[j]; //前k项之和
        }
        Q.base[Q.rear]=fn;
        Q.rear=(Q.rear+1)%Q.maxSize;
    }
    return fn;
}

2.3 一元稀疏多项式

采用压缩存储
类型定义：

1
2
3
4
5
6
7
8
typedef struct{
    float coef; //系数
    int expn; //指数
}ElemType,Term; //项
typedef struct{
    Term *elem;
    int length;
} Poly; //一元稀疏多项式

2.3.1创建一元稀疏多项式 CreatePoly

1
2
3
4
5
6
7
8
9
10
Status CreatePoly(Poly &P, Term e[], int n){
    int i;
    P,elem = (Term*)malloc(sizeof(Term)*n);
    if(NULL==P.elem)return OVERFLOW;
    for(i=o;i<n;i++){
        P.elem[i] = e[i];
    }
    P.length = n;
    return OK;
}

2.3.2 加法操作AddPoly

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Status AddPoly(Poly pa,Poly pb,Poly &pc){ //求pc=pa+pb
    int i=0,j=0,k=0;
    float c;
    pc.elem = (Term*)malloc((pa.length+pb.length)*sizeof(Term));
    if(NULL==pc.elem)return OVERFLOW;
    while(i<pa.length && j< pb.length){ //谁项比较小，添加谁到pc
        if(pa.elem[i].expn<pb.eem[j].expn)
            pc.elem[k++] = pa.elem[i++];
        else if(pa.elem[i].expn>pb.elem[j].expn)
            pc.elem[k++] = pb.elem[j++];
        else{  //相等
            c=pa.elem[i].coef + pb.elem[j].coef;
            if(c!=0){
                pc.elem[k].expn=pa.elem[i].expn;
                pc.elem[k].coef=c;
                k++;
            }
            i++;j++;
        }
    }
    if(i==pa.length)
        while(j<pb.length) pc.elem[k++]=pb.elem[j++];
    if(j==pb.length)
        while(i<pa.length) pc.elem[k++]=pa.elem[j++];
    if(k<pa.length+pb.length)
        if(NULL==(pc.elem=(Term*)realloc(pc.elem,k*sizeof(Term))))
            return OVERFLOW;
    pc.length=k;
    return OK;
}

2.3.3 稀疏矩阵

定义：在nxm矩阵中,有t个元素不为0，令δ=t/(mxn),称δ为稀疏因子。
δ<=0.05时称为稀疏矩阵。
稀疏矩阵的非0元可用三元组表示，如：
00000230
50000000
00000900
00000000
可表示为：
((1,6,2),(1,7,3),(2,1,5),(3,6,9))
(行数,列数,元素值)；

类型定义：

1
2
3
4
5
6
7
8
typedef struct{
    int i,j; //非0元的行和列
    ElemType e; //非0元的值
}Triple; //三元组
typedef struct{
    Triple *data; //0号单元不使用
    int mu,nu,tu; //矩阵行数，列数和非0元个数
}TSMatrix; //三元组顺序表

2.3.4 三元组顺序表快速转置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
Status FastTransposeSMatrix(TSMatrix M,TSMatrix &T){
    int j,q,k,p;
    int *num , *cpos;
    T.mu=M.nu;
    T.nu=M.mu;
    T.tu=M.tu;
    if(T.tu!=0){
        T.data=(Triple*)malloc(sizeof(Triple)*(T.tu+1));
        num=(int*)malloc((M.nu+1)*sizeof(int));
        cpos=(int*)malloc((M.nu+1)*sizeof(int));
        if(NULL==T.data||NULL==num||NULL==cpos)return OVERFLOW;
        for(j=1;j<M.nu;j++)num[j]=0;
        for(k=1;k<=M.tu;++k) ++num[M.data[k].j];
        cpos[1]=1;
        for(j=2;j<M.nu;j++)
            cpos[j]=cpos[j-1]+num[j-1];
        for(p=1;p<=M.tu;p++){
            j=M.data[p].j;
            q=cpos[j];
            T.data[q].i=M.data[p].j;
            T.data[q].j=M.data[p].i;
            T.data[q].e=M.data[p].e;
            ++cpos[j];
        }
    }
    free(num);
    free(cpos);
    return OK;
}

2.5 链式存储

2.5.1 链栈

1
return S==NULL?TRUE:FALSE; //判空
1
2
3
4
5
if(S==NULL)return ERROR; //取栈顶
else{
    e=S->data;
    return OK;
}

2.5.2 链队列

1
return Q.front==NULL?TRUE:FALSE; //判空
1
2
3
4
5
6
7
8
9
10
if(Q.front==NULL) return ERROR; //求队列长度
    int i=1;
    QueuePtr p;
    p=Q.front;
    while(p!=Q.rear)
    {
        p=p->next;
        i++;
    }
    return i;

2.5.3 单链表

1
return L->next==NULL?TRUE:FALSE; //带头结点判空

3 第三章 排序基础

3.1 直接插入排序算法

监视哨为L.rcd[0]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void InsertSort(RcdSqList &L)
{
    int i,j;
    for(i=1;i<L.length;i++){
        if(L.rcd[i+1].key<L.rcd[i].key){
            L.rcd[0]=L.rcd[i+1];
            j=i+1;
            do{
                j--;
                L.rcd[j+1]=L.rcd[j];
            }while(L.rcd[0].key<L.rcd[j-1].key);
            L.rcd[j]=L.rcd[0];
        }
    }
}

监视哨为L.rcd[length+1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
typedef struct {
   KeyType key; 
   ... 
} RcdType;
typedef struct {
   RcdType rcd[MAXSIZE+1]; // rcd[0]闲置
   int length;
} RcdSqList;
void InsertSort(RcdSqList &L)
{
	int i,j;   
	for(i=L.length;i>1;i--){    
		if(L.rcd[i-1].key>L.rcd[i].key){    
			L.rcd[L.length+1]=L.rcd[i-1];    
			j=i-1;     
			do{
				j++;L.rcd[j-1]=L.rcd[j];  
			}while(L.rcd[L.length+1].key>L.rcd[j+1].key); 
			L.rcd[j]=L.rcd[L.length+1];   
		}		  
}

3.2 计数排序

http://www.cnblogs.com/kkun/archive/2011/11/23/2260299.html

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int i,j,t;
    int c[100];
    
    for(i=1;i<=L.length;i++){
        c[i]=0;
        for(j=1;j<=L.length;j++){
            if(L.rcd[j].key<L.rcd[i].key){
                c[i]++;
            }
        }        
    }                 
    RcdType *L1;   
    if(L.length!=0)    
        L1=(RcdType*)malloc(L.length*sizeof(RcdType)); 
    for(i=1;i<L.length+1;i++){    
        L1[c[i]]=L.rcd[i];  /*核心的一句*/ 
    }    
    for(i=1;i<L.length+1;i++){
         L.rcd[i]=L1[i-1];   
    }    
    free(L1);

4 第四章 哈希表

4.1 线性探测开放定址法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/*题目*/
/******************
已知某哈希表的装载因子小于1,
哈希函数H(key)为关键字(标识符)的第一个字母在字母表中的序号，
处理冲突的方法为线性探测开放定址法。
试编写一个按第一个字母的顺序输出哈希表中所有关键字的算法。
哈希表的类型HashTable定义如下：
*/
#define SUCCESS    1
#define UNSUCCESS  0
#define DUPLICATE -1
typedef char StrKeyType[4];
typedef struct {
   StrKeyType key; // 关键字项
   int    tag;     // 标记 0:空；1:有效; -1:已删除
   void  *any;     // 其他信息
} RcdType;
typedef struct {
  RcdType *rcd;    // 存储空间基址
  int      size;   // 哈希表容量
  int      count;  // 表中当前记录个数
} HashTable;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
//解
/*哈希函数*/
int Hash(char key){   
     int i;    
     i=(key-'A')%11;   
     return i;  
 }      
 /*求得下一个探查地址*/
 void collision(int &p,int size){   
    p=(p+1)%size;  
 } 
 /*查找是否符合条件*/
 int SearchHash(HashTable H,char key,int &p,int &c){
    p=Hash(key);    
    while(H.rcd[p].tag!=0&&(H.rcd[p].key[0]!=key)||-1==H.rcd[p].tag){
    //这句话很关键，判断某个位置是否为空，若空再判断两个值是否相同，
    //相同则再加判断是否已经删除
    //若&&结果为1就不往后看了
        collision(p,H.size);
        c++;   
    }    
    if(H.rcd[p].key[0]==key)   
    return 1;   
    else return 0;  
 }        
 /* 依题意用print输出关键字 */
 void PrintKeys(HashTable ht, void(*print)(StrKeyType))  {
     int p,c=0,t;  
     char key='A';  
     do{
          if(SearchHash(ht,key,p,c)==1)   
            t=p;
          while(ht.rcd[p].tag!=0&&Hash((ht.rcd[p].key[0])==t)){   
            if(ht.rcd[p].key[0]==key&&ht.rcd[p].tag!=-1)    
                print(ht.rcd[p].key);    
            collision(p,ht.size);     
          }    
          key++;   
     }while(key<='Z');  
 }

4.2 链地址法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/*题目*/
//假设哈希表长为m，哈希函数为H(x)，用链地址法
//处理冲突。试编写输入一组关键字并建造哈希表的算法。
//哈希表的类型ChainHashTab定义如下：
#define NUM         7
#define NULLKEY    -1
#define SUCCESS     1
#define UNSUCCESS   0
#define DUPLICATE  -1
typedef char HKeyType;
typedef struct HNode {
   HKeyType  data;
   struct HNode*  next;
}*HLink;
typedef struct {
   HLink  *rcd;   // 指针存储基址，动态分配数组
   int    count;  // 当前表中含有的记录个数
   int    size;   // 哈希表的当前容量
}ChainHashTab;    // 链地址哈希表
int Hash(ChainHashTab H, HKeyType k) { // 哈希函数
  return k % H.size;
}
Status Collision(ChainHashTab H, HLink &p) {
  // 求得下一个探查地址p 
  if (p && p->next) { 
    p = p->next;
    return SUCCESS;
  } else return UNSUCCESS;
}

解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int SearchHash(ChainHashTab H,HKeyType key,HLink &p,int &j){
   j=Hash(H,key);   
   p=H.rcd[j];    
   if(p==NULL)   
        return 0;    
   while(p->next!=NULL&&p->data!=key){
       Collision(H,p);   
   }    
   if(p->data==key)   
   return 1;   
   else return 0;  
}
int BuildHashTab(ChainHashTab &H, int n, HKeyType es[]) 
/* 直接调用下列函数                             */
/* 哈希函数：                                   */
/*    int Hash(ChainHashTab H, HKeyType k);     */
/* 冲突处理函数：                               */
/*    int Collision(ChainHashTab H, HLink &p);  */
{
    int i,j;   
    HLink p,t;    
    for(i=0;i<n;i++){
         if(SearchHash(H,es[i],p,j)==0){
                t=(HNode*)malloc(sizeof(HNode));      
                t->data=es[i];      
                t->next=H.rcd[j];      
                H.rcd[j]=t;    
         }  
    }    
    return 1;
    
}

5 第五章 递归

5.1 颜色

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**********
【题目】假设以二维数组g[1..m][1..n]表示一个图像
区域，g[i][j]表示该区域中点(i,j)所具颜色，其值
为从0到k的整数。试编写递归算法，将点(i0,j0)所在
区域的颜色置换为颜色c。约定与(i0,j0)同色的上、
下、左、右的邻接点为同色区域的点。
表示图像区域的类型定义如下：
typedef char GTYPE[m+1][n+1];
**********/
/* 在g[1..m][1..n]中，将元素g[i0][j0] */
/* 所在的同色区域的颜色置换为颜色c    */
void ChangeColor(GTYPE g, int m, int n, 
                 char c, int i0, int j0)
{
     char color = g[i0][j0];     
     if(g[i0][j0]==c)
        return;     
     else{         //四个方向递归
        g[i0][j0] = c;          
     if(j0-1>=1&&g[i0][j0-1]==color) 
        ChangeColor(g,m,n,c,i0,j0-1);         
     if(i0-1>=1&&g[i0-1][j0]==color)
        ChangeColor(g,m,n,c,i0-1,j0);         
     if(j0+1<=n&&g[i0][j0+1]==color) 
        ChangeColor(g,m,n,c,i0,j0+1);         
     if(i0+1<=m&&g[i0+1][j0]==color) 
        ChangeColor(g,m,n,c,i0+1,j0);              
     }
}

5.2 递归广义深度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**********
【题目】试按依次对每个元素递归分解的分析方法重写求广义表的深度的递归算法。
广义表类型GList的定义：
typedef enum {ATOM,LIST} ElemTag;
typedef struct GLNode{
     ElemTag tag;
     union {
       char atom;
       struct { 
         GLNode *hp, *tp;
       } ptr;
     }un;
} *GList;
**********/
int GListDepth(GList ls)
/* Return the depth of list */
{
    int h1,h2;
    GList p=ls;
    if(ls==NULL)return 1;
    if(ATOM==ls->tag)return 0;
    h2 = GListDepth(p->un.ptr.hp)+1; //两句反过来不影响
    h1 = GListDepth(p->un.ptr.tp);    
    return h1>h2?h1:h2;
}

##5.3 递归判断广义表是否相等

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**********
【题目】试编写判别两个广义表是否相等的递归算法。
广义表类型GList的定义：
typedef enum {ATOM,LIST} ElemTag;
typedef struct GLNode{
     ElemTag tag;
     union {
       char atom;
       struct { 
         GLNode *hp, *tp;
       } ptr;
     }un;
} *GList;
**********/
Status Equal(GList A, GList B)
/* 判断广义表A和B是否相等,是则返回TRUE,否则返回FALSE */
{
    if(A==NULL&&B==NULL)return TRUE;        
    if(A->tag==ATOM&&B->tag==ATOM&&A->un.atom==B->un.atom)
         return TRUE;     
    if(A->tag==LIST&&B->tag==LIST)
        if( Equal(A->un.ptr.hp,B->un.ptr.hp)&&Equal(A->un.ptr.tp,B->un.ptr.tp))
             return TRUE;    
     return FALSE;
}

递归输出广义表原子项及层次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**********
【题目】试编写递归算法，输出广义表中所有原子项及其所在层次。
广义表类型GList的定义：
typedef enum {ATOM,LIST} ElemTag;
typedef struct GLNode{
     ElemTag tag;
     union {
       char atom;
       struct { 
         GLNode *hp, *tp;
       } ptr;
     }un;
} *GList;
**********/
void OutAtom(GList A, int layer, void(*Out2)(char, int))
/* 递归地用函数Out2输出广义表的原子及其所在层次,layer表示当前层次 */
{
    if(A){       
            if(A -> tag == ATOM)//如果是原子节点，直接输出  
                Out2(A -> un.atom,layer);  
            else{//非原子节点，递归       
                OutAtom(A -> un.ptr.hp, layer+1, Out2);//表头节点，递归  
                OutAtom(A -> un.ptr.tp, layer, Out2);//表尾节点，递归  
            }      
       }  
}

未完成

###

1
2

###

1
2