定义:
广义表是n(n≥0)个元素a1,a2,…,ai,…,an的有限序列。
其中:
①ai--或者是原子或者是一个广义表。
②广义表通常记作:
Ls=( a1,a2,…,ai,…,an)。
③Ls是广义表的名字,n为它的长度。
④若ai是广义表,则称它为Ls的子表。
注意:
①广义表通常用圆括号括起来,用逗号分隔其中的元素。
②为了区分原子和广义表,书写时用大写字母表示广义表,用小写字母表示原子。
③若广义表Ls非空(n≥1),则al是Ls的表头,其余元素组成的表(a2,a3,…,an)称为Ls的表尾。
④广义表是递归定义的 [1]
广义表储存方式有两种:
头尾链表存储结构
typedef enum {ATOM, LIST} ElemTag; /* ATOM=0,表示原子;LIST=1,表示子表*/
typedef struct GLNode
{
ElemTag tag; /*标志位tag用来区别原子结点和表结点*/
union
{
AtomType atom; /*原子结点的值域atom*/
struct { struct GLNode * hp, *tp;} htp; /*表结点的指针域htp, 包括
表头指针域hp和表尾指针域tp*/
} atom_htp; /* atom_htp 是原子结点的值域atom和
表结点的指针域htp的联合体域*/
} *GList;
扩展线性存储
typedef enum {ATOM,LIST} ElemTag;
typedef struct GLNode
{ELemTag tag;
union
{AtomType atom;
struct GLNode *hp;
}
struct GLNode *ht;
}*GList;
下面我就扩展线性存储,创建广义表和 *** 作
#include
#include
#define MAXSIZE 10
#include
typedef struct GLNode//定义广义表类型
{
int tag;
union
{
char atom;
struct GLNode* hp;
}atom_hp;
struct GLNode* tp;
}GLNode;
void split_str(char* a, char* head, char* tail)//把传入的字符串,分割成表头和表尾
{
if(a[1] == '(')
{
int i = 0;
for(i = 0; i < strlen(a); i++)
{
if(a[i] == ')')
break;
}
char newtail[20] = {0};
strncpy(head, a+1, i);
strncpy(tail, a+i+2,strlen(a)-i-2);
newtail[0] = '(';
strcat(newtail, tail);
strcpy(tail, newtail);
}
else
{
char newtail[20] = {0};
strncpy(head, a+1, 1);
strncpy(tail, a+3,strlen(a)-2);
newtail[0] = '(';
strcat(newtail, tail);
strcpy(tail, newtail);
}
}
void creat_GLink(char* a, GLNode** GL)//通过输入自定义的字符串,创建广义表
{
if(a[0] != '(' && a[strlen(a)-1] != ')')//输入格式必须为"(...)"
{
printf("输入不合法,应该以(开头,以)结尾");
}
*GL = (GLNode*)malloc(sizeof(GLNode));
char head[20] = {0};//用来保存表头
char tail[20] = {0};//用来保存表尾
split_str(a, head, tail);
if(head[0] != '(')//判断第一个元素是原子还是子表
{
(*GL)->tag = 0;
(*GL)->atom_hp.atom = head[0];//给表头赋值
}
else
{
(*GL)->tag = 1;
creat_GLink(head, &((*GL)->atom_hp.hp));//创建子表(表头)
}
if(tail[1] != '\0')
{
creat_GLink(tail, &((*GL)->tp));//创建子表(表尾)
}
else
{
(*GL)->tp = NULL;
return;
}
}
void get_head(GLNode* GL)
{
if(GL->tag == 0)
{
printf("表头为%c\n",GL->atom_hp.atom);
}
else
{
printf("表头地址为%p\n", GL->atom_hp.hp);
}
}
void get_tail(GLNode* GL)
{
printf("表尾地址为%p\n", GL->tp);
}
void get_elem(GLNode* GL,char ch)//查找指定元素
{
if(GL)//表不为空
{
if(GL->atom_hp.atom == ch)
{
printf("找到了,位置在:%p\n", &(GL->atom_hp.atom));
return;
}
else if(GL->tag == 0)//递归查找元素
{
get_elem(GL->tp, ch);
}
else
{
get_elem(GL->atom_hp.hp, ch);//头部和尾部都为表,所以要分两步查找
get_elem(GL->tp, ch);
}
}
}
int main()
{
char input[20];
GLNode* GL;
printf("请输入您要创建的广义表,以回车键结束:>\n");
scanf("%s",input);
creat_GLink(input, &GL);
get_head(GL);//找表头
get_tail(GL);//找表尾
get_elem(GL,'c');//查找元素
return 0;
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)