C语言数据结构-bo5-5.c

blake

1. /* bo5-5.c 广义表的头尾链表存储(存储结构由c5-5.h定义)的基本操作(11个) */
   
2. Status InitGList(GList *L)
   
3. { /* 创建空的广义表L */
   
4.    *L=NULL;
   
5.    return OK;
   
6. }
   
7. 
   
8. void DestroyGList(GList *L) /* 广义表的头尾链表存储的销毁操作 */
   
9. { /* 销毁广义表L */
   
10.    GList q1,q2;
    
11.    if(*L)
    
12.    {
    
13.      if((*L)->tag==ATOM)
    
14.      {
    
15.        free(*L); /* 删除原子结点 */
    
16.        *L=NULL;
    
17.      }
    
18.      else /* 删除表结点 */
    
19.      {
    
20.        q1=(*L)->a.ptr.hp;
    
21.        q2=(*L)->a.ptr.tp;
    
22.        free(*L);
    
23.        *L=NULL;
    
24.        DestroyGList(&q1);
    
25.        DestroyGList(&q2);
    
26.      }
    
27.    }
    
28. }
    
29. 
    
30. Status CopyGList(GList *T,GList L)
    
31. { /* 采用头尾链表存储结构,由广义表L复制得到广义表T。算法5.6 */
    
32.    if(!L) /* 复制空表 */
    
33.      *T=NULL;
    
34.    else
    
35.    {
    
36.      *T=(GList)malloc(sizeof(GLNode)); /* 建表结点 */
    
37.      if(!*T)
    
38.        exit(OVERFLOW);
    
39.      (*T)->tag=L->tag;
    
40.      if(L->tag==ATOM)
    
41.        (*T)->a.atom=L->a.atom; /* 复制单原子 */
    
42.      else
    
43.      {
    
44.        CopyGList(&((*T)->a.ptr.hp),L->a.ptr.hp);
    
45.        /* 复制广义表L->ptr.hp的一个副本T->ptr.hp */
    
46.        CopyGList(&((*T)->a.ptr.tp),L->a.ptr.tp);
    
47.        /* 复制广义表L->ptr.tp的一个副本T->ptr.tp */
    
48.      }
    
49.    }
    
50.    return OK;
    
51. }
    
52. 
    
53. int GListLength(GList L)
    
54. { /* 返回广义表的长度,即元素个数 */
    
55.    int len=0;
    
56.    if(!L)
    
57.      return 0;
    
58.    if(L->tag==ATOM)
    
59.      return 1;
    
60.    while(L)
    
61.    {
    
62.      L=L->a.ptr.tp;
    
63.      len++;
    
64.    }
    
65.    return len;
    
66. }
    
67. 
    
68. int GListDepth(GList L)
    
69. { /* 采用头尾链表存储结构,求广义表L的深度。算法5.5 */
    
70.    int max,dep;
    
71.    GList pp;
    
72.    if(!L)
    
73.      return 1; /* 空表深度为1 */
    
74.    if(L->tag==ATOM)
    
75.      return 0; /* 原子深度为0 */
    
76.    for(max=0,pp=L;pp;pp=pp->a.ptr.tp)
    
77.    {
    
78.      dep=GListDepth(pp->a.ptr.hp); /* 求以pp->a.ptr.hp为头指针的子表深度 */
    
79.      if(dep>max)
    
80.        max=dep;
    
81.    }
    
82.    return max+1; /* 非空表的深度是各元素的深度的最大值加1 */
    
83. }
    
84. 
    
85. Status GListEmpty(GList L)
    
86. { /* 判定广义表是否为空 */
    
87.    if(!L)
    
88.      return TRUE;
    
89.    else
    
90.      return FALSE;
    
91. }
    
92. 
    
93. GList GetHead(GList L)
    
94. { /* 取广义表L的头 */
    
95.    GList h,p;
    
96.    if(!L)
    
97.    {
    
98.      printf("空表无表头!\n");
    
99.      exit(0);
    
100.    }
     
101.    p=L->a.ptr.tp;
     
102.    L->a.ptr.tp=NULL;
     
103.    CopyGList(&h,L);
     
104.    L->a.ptr.tp=p;
     
105.    return h;
     
106. }
     
107. 
     
108. GList GetTail(GList L)
     
109. { /* 取广义表L的尾 */
     
110.    GList t;
     
111.    if(!L)
     
112.    {
     
113.      printf("空表无表尾!\n");
     
114.      exit(0);
     
115.    }
     
116.    CopyGList(&t,L->a.ptr.tp);
     
117.    return t;
     
118. }
     
119. 
     
120. Status InsertFirst_GL(GList *L,GList e)
     
121. { /* 初始条件: 广义表存在 */
     
122.    /* 操作结果: 插入元素e作为广义表L的第一元素(表头,也可能是子表) */
     
123.    GList p=(GList)malloc(sizeof(GLNode));
     
124.    if(!p)
     
125.      exit(OVERFLOW);
     
126.    p->tag=LIST;
     
127.    p->a.ptr.hp=e;
     
128.    p->a.ptr.tp=*L;
     
129.    *L=p;
     
130.    return OK;
     
131. }
     
132. 
     
133. Status DeleteFirst_GL(GList *L,GList *e)
     
134. { /* 初始条件: 广义表L存在 */
     
135.    /* 操作结果: 删除广义表L的第一元素,并用e返回其值 */
     
136.    GList p;
     
137.    *e=(*L)->a.ptr.hp;
     
138.    p=*L;
     
139.    *L=(*L)->a.ptr.tp;
     
140.    free(p);
     
141.    return OK;
     
142. }
     
143. 
     
144. void Traverse_GL(GList L,void(*v)(AtomType))
     
145. { /* 利用递归算法遍历广义表L */
     
146.    if(L) /* L不空 */
     
147.      if(L->tag==ATOM) /* L为单原子 */
     
148.        v(L->a.atom);
     
149.      else /* L为广义表 */
     
150.      {
     
151.        Traverse_GL(L->a.ptr.hp,v);
     
152.        Traverse_GL(L->a.ptr.tp,v);
     
153.      }
     
154. }

复制代码