数据结构之---C语言实现广义表头尾链表存储表示
程序员文章站
2022-03-26 19:27:04
//广义表的头尾链表存储表示
//杨鑫
#include
#include
#include
#include
#define maxstrlen 40 )
typedef...
//广义表的头尾链表存储表示 //杨鑫 #include #include #include #include #define maxstrlen 40 ) typedef char sstring[maxstrlen+1]; typedef char atomtype; // 定义原子类型为字符型 typedef enum{ atom, list // atom==0:原子 list==1:子表 } elemtag; typedef struct glnode { elemtag tag; // 公共部分,用于区分原子结点和表结点 union // 原子结点和表结点的联合部分 { atomtype atom; // atom是原子结点的值域, atomtype由用户定义 struct { struct glnode *hp,*tp; }ptr; // ptr是表结点的指针域,prt.hp和ptr.tp分别指向表头和表尾 }a; } *glist, glnode; //初始化的广义表l int initglist(glist *l) { *l = null; return 1; } //销毁广义表l void destroyglist(glist *l) { glist q1,q2; if(*l) { if((*l)->tag == atom) { free(*l); *l = null; } else { q1 = (*l)->a.ptr.hp; q2 = (*l)->a.ptr.tp; free(*l); *l = null; destroyglist(&q1); destroyglist(&q2); // 递归删除表头和表尾结点 } } } // 采用头尾链表存储结构,由广义表l复制得到广义表t。 int copyglist(glist *t,glist l) { if(!l) *t = null; else { *t = (glist)malloc(sizeof(glnode)); if(!*t) exit(0); (*t)->tag = l->tag; if(l->tag == atom) (*t)->a.atom = l->a.atom; // 复制单原子 else // 是表结点,则依次复制表头和表尾 { copyglist(&((*t)->a.ptr.hp), l->a.ptr.hp); copyglist(&((*t)->a.ptr.tp), l->a.ptr.tp); } } return 1; } // 返回广义表的长度,即元素个数 int glistlength(glist l) { int len = 0; if(!l) return 0; if(l->tag == atom) return 1; while(l) { l = l->a.ptr.tp; len++; } return len; } // 采用头尾链表存储结构,求广义表l的深度。 int glistdepth(glist l) { int max, dep; glist pp; if(!l) return 1; // 空表深度为1 if(l->tag == atom) return 0; // 原子深度为0 for(max = 0, pp = l; pp; pp = pp->a.ptr.tp) { // 递归求以pp->a.ptr.hp为头指针的子表深度 dep = glistdepth(pp->a.ptr.hp); if(dep > max) max = dep; } return max+1; // 非空表的深度是各元素的深度的最大值加1 } // 判定广义表是否为空 int glistempty(glist l) { if(!l) return 1; else return 0; } // 取广义表l的头 glist gethead(glist l) { glist h,p; if(!l) { printf("空表无表头!\n"); exit(0); } p = l->a.ptr.tp; l->a.ptr.tp = null; copyglist(&h,l); l->a.ptr.tp = p; return h; } // 取广义表l的尾 glist gettail(glist l) { glist t; if(!l) { printf("空表无表尾!\n"); exit(0); } copyglist(&t, l->a.ptr.tp); return t; } // 插入元素e作为广义表l的第一元素(表头,也可能是子表) int insertfirst_gl(glist *l,glist e) { glist p = (glist)malloc(sizeof(glnode)); if(!p) exit(0); p->tag = list; p->a.ptr.hp = e; p->a.ptr.tp = *l; *l = p; return 1; } // 删除广义表l的第一元素,并用e返回其值 int deletefirst_gl(glist *l,glist *e) { glist p; *e = (*l)->a.ptr.hp; p = *l; *l = (*l)->a.ptr.tp; free(p); return 1; } // 利用递归算法遍历广义表l void traverse_gl(glist l,void(*v)(atomtype)) { if(l) if(l->tag == atom) v(l->a.atom); else { traverse_gl(l->a.ptr.hp,v); traverse_gl(l->a.ptr.tp,v); } } // 生成一个其值等于chars的串t int strassign(sstring t,char *chars) { int i; if(strlen(chars) > maxstrlen) return 0; else { t[0] = strlen(chars); for(i = 1; i <= t[0]; i++) t[i] = *(chars + i - 1); return 1; } } // 由串s复制得串t int strcopy(sstring t, sstring s) { int i; for(i = 0; i <= s[0]; i++) t[i] = s[i]; return 1; } // 若s为空串,则返回1,否则返回0 int strempty(sstring s) { if(s[0] == 0) return 1; else return 0; } // 若s>t,则返回值>0;若s=t,则返回值=0;若ss[0] || len < 0 || len > s[0]-pos+1) return 0; for(i = 1; i <= len; i++) sub[i]=s[pos+i-1]; sub[0] = len; return 1; } // 将非空串str分割成两部分:hsub为第一个','之前的子串,str为之后的子串 void sever(sstring str,sstring hstr) { int n,i, k; sstring ch,c1,c2,c3; n = strlength(str); strassign(c1,","); strassign(c2,"("); strassign(c3,")"); substring(ch,str,1,1); for(i = 1,k = 0;i <= n && strcompare(ch,c1) || k != 0; ++i) { substring(ch, str, i, 1); if(!strcompare(ch, c2)) ++k; else if(!strcompare(ch,c3)) --k; } if(i <= n) { substring(hstr, str, 1, i-2); substring(str, str, i, n - i + 1); } else { strcopy(hstr, str); clearstring(str); } } // 广义表l。设emp="()" int createglist(glist *l, sstring s) { sstring sub,hsub,emp; glist p,q; strassign(emp,"()"); if(!strcompare(s, emp)) *l = null; // 创建空表 else { *l = (glist)malloc(sizeof(glnode)); if(!*l) // 建表结点 exit(0); if(strlength(s) == 1) // s为单原子 { (*l)->tag = atom; (*l)->a.atom = s[1]; // 创建单原子广义表 } else { (*l)->tag = list; p = *l; substring(sub, s, 2, strlength(s)-2); // 脱外层括号 do { // 重复建n个子表 sever(sub, hsub); // 从sub中分离出表头串hsub createglist(&p->a. ptr. hp, hsub); q = p; if(!strempty(sub)) // 表尾不空 { p = (glnode *)malloc(sizeof(glnode)); if(!p) exit(0); p->tag = list; q->a.ptr.tp = p; } }while(!strempty(sub)); q->a.ptr.tp = null; } } return 1; } // 打印原子 void visit(atomtype e) { printf("%c ", e); } int main() { // 广义表的表示形式是,空表:(),单原子:a,表:(a,(b),c,(d,(e))) char p[80] = {"(a,(b),c,(d,(e)))"}; sstring t; glist l,m; initglist(&l); initglist(&m); printf("空广义表l的深度 = %d\nl是否空?%d(1:是 0:否)\n\n", glistdepth(l), glistempty(l)); strassign(t, p); createglist(&l, t); // 创建广义表 printf("\n广义表l的长度 = %d\n", glistlength(l)); printf("广义表l的深度 = %d \nl是否空?%d(1:是 0:否)\n", glistdepth(l), glistempty(l)); printf("遍历广义表l:\n"); traverse_gl(l, visit); printf("\n\n复制广义表m = l\n"); copyglist(&m, l); printf("广义表m的长度 = %d\n", glistlength(m)); printf("广义表m的深度 = %d\n", glistdepth(m)); printf("遍历广义表m:\n"); traverse_gl(m,visit); destroyglist(&m); m = gethead(l); printf("\n\nm是l的表头,遍历广义表m:\n"); traverse_gl(m, visit); destroyglist(&m); m = gettail(l); printf("\n\nm是l的表尾,遍历广义表m:\n"); traverse_gl(m,visit); insertfirst_gl(&m, l); printf("\n\n插入l为m的表头,遍历广义表m:\n"); traverse_gl(m,visit); printf("\n\n删除m的表头,遍历广义表m:\n"); destroyglist(&l); deletefirst_gl(&m, &l); traverse_gl(m, visit); printf("\n"); destroyglist(&m); return 0; }
上一篇: iOS开发之UIImageView
下一篇: C语言入门:03.关键字、标识符、注释