第5章数组与广义表.ppt

建立十字链表的算法 for(i=1;i=s;i++) { /* 建立头结点循环链表 */ p=( crosslist *)malloc(sizeof(crosslist)); p-row=0;p-col=0;cp[i]=p; p-right=p;p-down=p;cp[i-1]-next=p; } cp[s]-next=head; for (k=0;kt;k++) { scanf(“%d %d %d”,i,j,v); /* 输入一个非 零元素的三元组 */ p=( crosslist *)malloc(sizeof(crosslist)); p-row=i;p-col=j;p-value=v;q=cp[i]; 建立十字链表的算法 while((q-right!=cp[i])(q-right-colj)) q=q-right; p-right=q-right; q-right=p; q=cp[j]; /* 完成插入 */ while((q-down!=cp[j])(q-down-rowi)) q=q-down; p-down=q-down;q-down=p; /* 完成插入 */ } return(head); } 时间复杂度为O(t×s) 三、广义表 定义： 广义表是n≥0个元素a1，a2，…，an的有限序列，即Ls＝(a1，a2，…，an) 其中：Ls是广义表的名称，n是它的长度。ai可以是单个元素，也可以是广义表 若ai是单个元素，则称为表Ls的原子，若ai是广义表，则称为Ls的子表。当Ls非空时，a1为Ls的表头(Head)，其余元素组成的表(a2，a3，…，an)为表尾(Tail) 递归定义 注意：表尾一定是广义表 2、广义表举例 A＝（ ） A是一个空表，其长度为0。 B＝（b , c） B是一个长度为2的列表。 C＝（a ,（d , e , f））C是一个长度为2的列表，其中第一个元素是原子a，第二个元素是子表（d , e , f）。 D=(A , B , C) D是一个长度为3的列表，其中三个元素都是子表。 E＝（a , E） E是一个长度为2的列表，它是一个递归表 注：一般大写字母表示广义表（或子表），小写字母表示单个元素（或原子） 广义表的图形表示 3、广义表的图形表示 广义表的特点： 广义表中的元素可以是原子也可以是子表，广义表是一个多层次结构 广义表是可以共享的。如广义表B是D的子表 广义表允许递归，如广义表E是一个递归表 广义表的元素间存在次序关系和层次关系，广义表展开后包含的括号层数称为广义表的深度。如C的深度为2，E的深度为∞ 4、广义表的存储 typedef struct GenealNode { int tag; /* 0..1；取0表示原子节点 ，取1表示子表节点*/ union { DataType data; struct GenealNode *hp,*tp; }; } *GList; 注：tag＝0，tag分量和DataType分量有效 tag＝1， tag分量和 *hp、*tp分量有效 指针类型 存储举例 广义表的基本算法 (1)取表头GetHead()和取表尾GetTail() 如： GetHead(B)=b GetTail(B)=(c) GetHead(C)=a GetTail(C)=((d,e,f)) GetHead(D)=A GetTail(D)=(B,C) C实现 GList GetHead(GList p) { /*空表或是单个原子null， 否则返回表头指针*/ if (!p|| p-tag= =0) { printf(“空表或是单个原子\n”)； return (NULL)； } return(p-ptr.hp)； } Glist GetTail(Glist p) { /*空表或是单个原子,函数 无意义否则返回表尾指针*/ if (!p||!p-tag) { printf(“空表