首页 > 代码库 > 串和广义表

串和广义表

参考文章:http://blog.csdn.net/lijuwen/article/details/1353084

然后又按照自己的方式敲了一遍,各种错。。。。

下面是我的代码:

#include "stdafx.h"#include <iostream>#include <string.h>using namespace std;typedef char AtomType;//定义tag类型typedef char AtomType;//定义原子类型为字符型typedef enum{ATOM,LIST} ElemTag;typedef struct{	char *ch;	int length;}HString;typedef struct GLNode{	ElemTag tag;	union{		AtomType data;		GLNode *subList;	}a;	GLNode *next;}*GLList,GLNode;//生成一个串等于charsvoid strAssign(HString *T,char *chars){	//如果T存在值,释放T的空间	if((*T).ch) free((*T).ch);	//求chars的长度	int i = strlen(chars);	if(i ==0)	{		T->ch =NULL;		T->length =0;	}else{		//T= (HString*)malloc(sizeof(HString));		(*T).ch = (char*)malloc(sizeof(char));//分配串的空间		if(!(*T).ch) exit(0);		for(int j=0;j<i;j++) T->ch[j]=chars[j];		T->length = i;	}}//将S的值复制给Tvoid strCopy(HString *T,HString *S){	if((*T).ch) free((*T).ch);	(*T).ch = (char*)malloc(sizeof(char));	if(!(*T).ch) exit(0);	for(int i=0;i<S->length;i++) T->ch[i] = S->ch[i];	T->length = S->length;}//判断串是否为空int strEmpty(HString *S){	if(S->length==0&&S->ch==NULL) return 1;	else return 0;}//比较两个字符的大小,前者大于后者返回1,相等返回0,前者小于后者返回-1int strCompare(HString *T,HString *S){	int i,j;	for(i=0,j=0;i<T->length,j<S->length;i++,j++)		if(T->ch[i] != T->ch[j]) return T->ch[i]-T->ch[j];	return T->length - S->length;}//得到串的长度int strLen(HString *S){	return S->length;}//清空串void clearStr(HString *S){//这样写跟.ch应该没差别	if(S->ch){		free(S->ch);		S->ch = NULL;	}	S->length =0;}//连接串void strConcat(HString *T,HString *S1,HString *S2){	if((*T).ch) free((*T).ch);	T->length = S1->length + S2->length;	(*T).ch = (char*)malloc(sizeof(char));	if(!(*T).ch) exit(0);	for(int i=0;i<S1->length;i++)		T->ch[i] = S1->ch[i];	for(int j=0;j<S2->length;j++)		T->ch[S1->length+j]=S2->ch[j];}//将S从pos位置截取length长的字符串赋值给subvoid subStr(HString *sub,HString *S,int pos,int length){	if(pos <1||pos>S->length||length<0||length>S->length+1-pos)    {		printf("%s","pos or length invalid");		exit(0);	}	if((*sub).ch) free((*sub).ch);	if((*S).ch == NULL){		(*sub).ch = NULL;		(*sub).length=0;	}else	{		(*sub).ch = (char*)malloc(sizeof(char));		if(!(*sub).ch) exit(0);		for(int i=0;i<length;i++)			sub->ch[i]=S->ch[pos+i];		sub->length = length;	}}//初始化串void initStr(HString *S){	(*S).length =0;	(*S).ch = NULL;}//两个字符串是否有重合,在S的pos位置之后,重合返回第一次重合的下标,不重合返回-1	int indexStr(HString *T,HString *S,int pos){	int length = (*S).length-(*T).length+1;	if(pos>0)	{		for(int i=pos;i<length;i++)		{			HString temp;			subStr(&temp,S,i,length);			if(!strCompare(&temp,T)) return i;		}	}	return -1;}//在S的pos位置插入Tvoid strInsert(HString *S,int pos,HString *T){	if(pos<1||pos>(*S).length+1||(*T).length<0) exit(0);	if((*S).ch) free((*T).ch);	(*S).ch = (char*)malloc(sizeof(char));	if(!(*S).ch) exit(0);	for(int i=(*S).length-1;i>pos-1;i--) //(*S).ch[i+pos] = (*S).ch[i];		(*S).ch[i+(*T).length] = (*S).ch[i];	for(int i=0;i<(*T).length;i++)		(*S).ch[pos+i-1] = (*T).ch[i];	(*S).length +=(*T).length;}//在S的pos位置删除len长度void strDelete(HString *S,int pos,int len){	if(len < 1||len>(*S).length-1||pos<1||pos>(*S).length-1||pos<(*S).length-1-len) exit(0);	for(int i=pos;i<(*S).length;i++) (*S).ch[pos]=(*S).ch[pos+len];	(*S).length -=len;	(*S).ch = (char*)realloc((*S).ch,(*S).length*sizeof(char));}//替换字符串,将V替换成Tvoid strReplace(HString *S,HString *T,HString *V){	int i=1;	if(strEmpty(S)) exit(0);	do	{		i = indexStr(S,V,i);//i为上次寻找的位置		if(i)		{			strDelete(S,i,(*V).length);			strInsert(S,i,T);			i+=(*V).length;		}	}while(i);}//输出strvoid strPrint(HString *S){	for(int i=0;i<(*S).length;i++)		printf("%c",(*S).ch[i]);	printf("/n");}//初始化广义表int initGList(GLList *L){	*L = NULL;	return 1;}//将str分成两部分,hstr为第一个,之前的字符串,str为第一个,之后的字符串int sever(HString *str,HString *hstr){	printf("%s","开始执行sever/n");	HString ch,c1,c2,c3;	initStr(&ch);initStr(&c1);initStr(&c2);initStr(&c3);	printf("%s","init success/n");	strAssign(&c1,",");strAssign(&c2,"(");strAssign(&c3,")");	printf("%s","strassgin success/n");	int n = strLen(str);	int i=1;	int k=0;	do{		printf("%s","begin to inter do/n");		printf("i=%d/n",i);		subStr(&ch,str,i,1);		printf("substr:%c",&ch);				if(!strCompare(&ch,&c2)) k++;		else if(!strCompare(&ch,&c3)) k--;		++i;	}while(i<=n&&strCompare(&ch,&c1)||k!=0);	printf("&ch=%c",ch);	if(i<n)	{		strCopy(&ch,str);		subStr(hstr,&ch,1,i-2);		subStr(str,&ch,i,n-i+1);	}	else	{		strCopy(hstr,str);		clearStr(str);	}	return 1;}//s为广义表格式的字符串,L为要创建的表,void createList(GLList &L,HString *S){	GLList p;	HString emp,sub,hsub;	initStr(&emp);initStr(&sub);initStr(&hsub);	strAssign(&emp,"()");	L = (GLList)malloc(sizeof(GLNode));	if(!L)	{		printf("%s","创建表失败");		exit(0);	}	if(!strCompare(S,&emp))//创建空表	{		L->tag = LIST;		L->next = NULL;		L->a.subList = NULL;	}else if(strLen(S)==1)//创建原子表	{		L->tag = ATOM;		L->next = NULL;		L->a.data = http://www.mamicode.com/(*S).ch[0];"脱外层括号之后:%s",sub);		sever(&sub,&hsub);		printf("sublist=%s",hsub);		printf("next=%s",sub);		createList(L->a.subList,&hsub);		p = L->a.subList;		while(!strEmpty(&sub))		{			sever(&sub,&hsub);			createList(p->next,&hsub);			p = p->next;		}	}}//销毁广义表void destroyList(GLList *L){	GLList subList,next;	if(*L)	{		if((*L)->tag = ATOM) subList = NULL;		else subList = (*L)->a.subList;		next = (*L)->next;		free(*L);		(*L) = NULL;		destroyList(&subList);		destroyList(&next);	}}// 由广义表L复制得到广义表Tint copyList(GLList *T,GLList L){	if(!L) 	{		*T = NULL;		return 1;	};	T = (GLList *)malloc(sizeof(GLList));	if(!(*T)) exit(0);	(*T)->tag = L->tag;	if(L->tag = ATOM) (*T)->a.data = http://www.mamicode.com/L->a.data;"%c",&ch);		if(ch == ‘#‘)*L = NULL;	else if(ch == ‘(‘)	{		L = (GLList *)malloc(sizeof(GLList));		if(!L) exit(0);		(*L)->tag = LIST;		createByScanf(&(*L)->a.subList);	}	else	{		L = (GLList *)malloc(sizeof(GLList));		if(!L) exit(0);		(*L)->tag = ATOM;		(*L)->a.data = http://www.mamicode.com/ch;"%c",&ch);	if(ch == ‘,‘)		createByScanf(&(*L)->next);	else if(ch == ‘)‘)		(*L)->next = NULL;}void main(){		HString t;	GLList l,m;	initStr(&t);	initGList(&l);	initGList(&m);	/*char c[80];	gets_s(c);	 strAssign(&t,c);	 createList(l,&t);//每次循环sub出来的的值都一样,但是每次执行的sub都不同	 printf("广义表l的长度=%d/n",listLength(&l));*/	createByScanf(&l);	printf("广义表l的长度=%d/n",listLength(&l));	/*HString t,m;	initStr(&t);	initStr(&m);	char c[10];	gets_s(c);	strAssign(&t,c);	subStr(&m,&t,1,1);	strPrint(&m);*/}
显示是调不通了,有机会再好好调下

  

串和广义表