数据结构之树的双亲表示法

  请问数据结构中用双亲表示法这种存储结构来表示树时其中删除操作中有一地方不明白！
  程序倒数第8行 (*T).nodes[k-1]=(*T).nodes[k]; 因为for(k=j+1;k<=(*T).n;k++) k可以等于(*T).n，那么(*T).nodes[k]的值是什么呢? 也就是树的最后一个结点的后一个空间里的值是什么呢？假如一棵树有14个结点, 用一维数组data[100]存储 a[0]存根结点,那a[13]存放的不就是最后一个结点了吗? a[14]中存放的是什么呢？是随机数吗？那么如何进行删除操作呢？

// 删除T中结点p的第i棵子树
void DeleteChild(PTree *T,TElemType p,int i)
{
int j,k,n=0;
LinkQueue q;
QElemType pq,qq;

for(j=0;j<=(*T).n;j++)
deleted[j]=0;
pq.name='a'; // 此成员不用
InitQueue(&q);
for(j=0;j<(*T).n;j++)
if((*T).nodes[j].data==p)
break;
for(k=j+1;k<(*T).n;k++)
{
if((*T).nodes[k].parent==j)
n++;
if(n==i)
break;
}
if(k<(*T).n)
{
n=0;
pq.num=k;
deleted[k]=1;
n++;
EnQueue(&q,pq);
while(!QueueEmpty(q))
{
DeQueue(&q,&qq);
for(j=qq.num+1;j<(*T).n;j++)
if((*T).nodes[j].parent==qq.num)
{
pq.num=j;
deleted[j]=1;
n++;
EnQueue(&q,pq);
}
}
for(j=0;j<(*T).n;j++)
if(deleted[j]==1)
{
for(k=j+1;k<=(*T).n;k++)    //不明白k为什么可以等于(*T).n;
{
deleted[k-1]=deleted[k];
(*T).nodes[k-1]=(*T).nodes[k];  //此处不明白
if((*T).nodes[k].parent>j)
(*T).nodes[k-1].parent--;
}
j--;
}
(*T).n-=n;
}
}

4 个解决方案

#1

数据结构可是基础中的基础，好好研究吧。

#2

楼主可否给出是哪本教材的，或者贴出全部源码。

没有背景的代码，看起来，很疼。。
至少，要交待了树的基本结构在代码中定义

#3

第二补充，正在复习数据结构，可以加我好友，一起讨论

#4

果然是随机数呀! 这样不好! 应该在前面弄个赋值会更好! 呵呵本科教材不都是采用严老师的书吗? 我是参考严老师的书! 谢谢!

#1