? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ?廣義表的創(chuàng)建與打印

? ??

? ? ? 本文取自《數(shù)據(jù)結(jié)構(gòu)與算法》(C語言版)(第三版)，出版社是清華大學(xué)出版社。

? ? ??本博文作為學(xué)習(xí)資料整理。

源碼是VC++ 6.0上可運(yùn)行程序，我挪到了VS2010中運(yùn)行。

? ? ??在VS2010中新建C++?Win32 控制臺應(yīng)用程序項(xiàng)目，創(chuàng)建結(jié)果截圖：

? ? ? ??

? ? ?

? ? ?1.廣義表的創(chuàng)建：

? ? ? 廣義表的存儲結(jié)構(gòu)示意圖：演示樣例：C(x, y, (a, b))

? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

? ? ? 廣義表能夠通過以下的遞歸方式進(jìn)行定義。

? ? ? 基本項(xiàng)：(1)廣義表為空表，當(dāng)s為空時；(2)廣義表為原子結(jié)點(diǎn)。當(dāng)s為單字符串時。

? ? ? 歸納項(xiàng)：如果Subs為S去掉最外層括號對的串，記作“S1。S2。...，Sn”。當(dāng)中Si(i=1,...,n)為非空字符串。對每一個Si建立表結(jié)點(diǎn)，并令其hp域的指針為由Si建立的子表的頭指針，除最后建立的表結(jié)點(diǎn)的尾指針為NULL外，其余表結(jié)點(diǎn)的尾指針均指向在它之后建立的表結(jié)點(diǎn)。也就是說，由于Si是一個字符串，首先要為這個字符串建立一個表結(jié)點(diǎn)，表結(jié)點(diǎn)的指針域指向Si中的元素。它的tp域指向下一次建立的Si+1，而Sn的tp域?yàn)榭铡?br /> ? ? ? 由于在廣義表的定義中要用到subs串，因此須要一個函數(shù)來求這個串。這里採用函數(shù)Getsubs(str,hstr)來實(shí)現(xiàn)。

當(dāng)中，hstr存放的是str中第1個","之前的子串，而且函數(shù)將str改動為刪除子串hstr和","之后的剩余串。

若串str中沒有","，則hstr即為str。而str改動為空串NULL。

? ?

? ? ?2.廣義表的打印：
? ? ?打印廣義表的算法思想是：先打印一個左括號"("，若遇到tag=ATOM，則打印該結(jié)點(diǎn)的值。假設(shè)此結(jié)點(diǎn)后面有后繼結(jié)點(diǎn)，則再打印一個","；假設(shè)tag=LIST，說明是一個子表，則遞歸調(diào)用函數(shù)，打印這個子表。打印全然部結(jié)點(diǎn)以后，最后打印一個“)”。

? ? ?源程序例如以下：GeneralList.cpp

// GeneralList.cpp : 定義控制臺應(yīng)用程序的入口點(diǎn)。#include "stdafx.h" #include <stdio.h> #include <stdlib.h> #include <string.h>typedef enum {ATOM, LIST}ElemTag; //ATOM==0 原子, LIST==1 子表struct GLNode {ElemTag tag; //標(biāo)識域union{char atom;struct GLNode *hp;};struct GLNode *tp; };typedef struct GLNode GList;//求取廣義表的子串Subs void Getsubs(char str[], char hstr[]) {int i=0;int j=0;int k=0; //用來記錄沒有匹配的左括號數(shù)int r=0; char s[100];while(str[i]&&(str[i]!=','||k)){if(str[i]=='(')k++;else if(str[i]==')')k--;if(str[i]!=','||str[i]==','&&k){hstr[j]=str[i];i++;j++;}}hstr[j]='\0';if(str[i]==',')i++;while(str[i]){s[r]=str[i];r++;i++;}s[r]='\0';strcpy(str,s);}//創(chuàng)建廣義表 GList *GListCreate(char str[]) {GList *G;char subs[100];char hstr[100];GList *q;int len=strlen(str);if(len==0||!strcmp(str,"()"))G=NULL;else if(len==1) //原子結(jié)點(diǎn)的情況{G=(GList *)malloc(sizeof(GList));if(!G){printf("申請空間失敗！");exit(0);}G->tag = ATOM;G->atom = *str;G->tp = NULL;}else{GList *p;G=(GList *)malloc(sizeof(GList));if(!G){printf("申請空間失敗！

"); exit(0); } G->tag = LIST; p=G; str++; strncpy(subs,str,len-2); //去掉最外面的() subs[len-2]='\0'; while(len>0) { GList *r; Getsubs(subs,hstr); //將subs分開為表頭hstr和表尾subs r=GListCreate(hstr); //生成表頭的廣義表 p->hp=r; q=p; len=strlen(subs); if(len>0) { p=(GList *)malloc(sizeof(GList)); if(!G) { printf("申請空間失敗！"); exit(0); } p->tag = LIST; q->tp=p; } } q->tp=NULL; } return G; } //打印廣義表 void GListPrint(GList *G) { GList *q,*p; printf("("); while(G) { p=G->hp; q=G->tp; if(p&&q&&!p->tag) //p為原子結(jié)點(diǎn)，而且有興許結(jié)點(diǎn) { printf("%c,",p->atom); p=q->hp; q=q->tp; } if(p&&!p->tag) //p為原子結(jié)點(diǎn)，而且沒有興許結(jié)點(diǎn) { printf("%c",p->atom); break; } else { if(!p) printf("()"); //p為空表 else GListPrint(p); if(q) printf(","); //還存在著興許的結(jié)點(diǎn) G=q; } } printf(")"); } int main() { int n; char *s; GList *G; printf("請輸入廣義表的字符數(shù)：\n"); scanf("%d",&n); printf("請輸入廣義表：\n"); s=(char *)malloc(n*sizeof(char)); scanf("%s",s); G=GListCreate(s); printf("所輸入的廣義表為：\n"); GListPrint(G); printf("\n"); return 0; }

? ? ?Ctrl+F5執(zhí)行GeneralList.cpp的執(zhí)行結(jié)果：例如以下截圖：

? ? ??

轉(zhuǎn)載于:https://www.cnblogs.com/brucemengbm/p/7183681.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的广义表的创建与打印的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。