Question

双链表程序语句求指教

rlink为结点的后继，llink为结点的前驱，在p所指结点后插入q所指的新结点，
语句p↑.rlink↑.llink=q,这是什么意思。。。。向上的箭头指的什么？和->一样吗？
谢谢~~~

Answer 1

p所指节点 的后继 的llink赋q的值
和p->rlink->llink=q一个概念应该
主要我不知道你说的是啥语言

追问

p所指结点的后继的前驱？。。。啥意思？？
我学的C，没见过这么写的才问的。。
谢谢~麻烦在解释下吧~~~辛苦辛苦

追答

光凭舌头我压力很大啊……你自己画个图看啦，把画出每个节点的成员。知道前驱后继不，p指着一个节点是不，这个节点有后继吧，这个后继是不是p->rlink指出来的？p->rlink这个语法在C里应该是有的，也可以写成(*p).rlink。就是取指向变量的成员啦，要是成员也是指针，连续指向还是写->方便。C的*p和Pascal的p^一个概念。现在这个rlink指向的是后继，后继节点有一个成员叫llink是吧，它指向这个节点的前驱，赋值之前和p指的是同一个节点。复制之后和q指的是同一个节点，就是你要X入的新节点啦……不知这么说你明白了没？

Answer 2

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<string.h>

#define OK 1
#define ERROR -1
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

typedef int Status;

struct BiNode{
//用结构体定义结点类型。
//数据域信息包含家谱中该对的男、女名字，其双亲名字，以及这对夫妇位于家谱中的辈分
//指针域指向他们的第一个孩子以及其他兄弟
char man[10],woman[10],father[10],mother[10];
int level;
struct BiNode *firstchild,*nextsibling;
};
struct SqStack{
//对栈类型进行定义
BiNode *base;
BiNode *top;
int stacksize;
};

//函数声明
Status InitStack (SqStack &S);
Status Push (SqStack &S,BiNode e);
Status CreateBiTree(BiNode *s);
Status Pop(SqStack &S,BiNode e);
Status EmptyStack(SqStack &S);
Status Preorder(BiNode *T,char name[10],BiNode *p);
//Status CreateParent(BiNode *s);
void findchildren(BiNode *p);
void putoutchildren(BiNode *q,int n);
void findparents(BiNode *p);
void levelhome(BiNode *T);
void leveling(SqStack S1,SqStack S2,int n);
void print(BiNode *p);

//主函数
void main()
{
BiNode *home=NULL,*p=NULL;
char name[10];
printf("请按先序遍历的顺序根据提示输入家谱信息，不存在则输入“#”\n");
CreateBiTree(home);
printf("层次化的家谱信息为\n");
levelhome(home);
printf("请输入要查找的人的名字");
gets(name);
Preorder(home,name,p);
if(!p)printf("家谱中无此人");
else{
printf("辈分：%d\n",p->level);
printf("孩子信息");
findchildren(p);
printf("父母信息：");
findparents(p);
}
}

//函数定义

Status InitStack (SqStack &S){
//初始化函数
S.base=(BiNode*)malloc(STACK_INIT_SIZE * sizeof(BiNode));
if(!S.base) return ERROR;
S.top=S.base;
S.stacksize =STACK_INIT_SIZE;
return OK;
}

Status Push (SqStack &S,BiNode e){
//将e结点推入栈，作为栈顶元素
if(S.top-S.base >=S.stacksize ){
S.base=(BiNode *)realloc(S.base ,(S.stacksize +STACKINCREMENT)*sizeof(BiNode));
if(!S.base ) return ERROR;
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return OK;
}

Status Pop(SqStack &S,BiNode e){
//取出栈顶元素
if(S.base==S.top) return ERROR;
e=*--S.top;
return OK;
}

Status EmptyStack(SqStack &S){
//若栈空，则返回0
return (S.top == NULL);
}

Status CreateBiTree(BiNode *root){
//创建家谱二叉树
char man1[10],woman1[10],father[10],mother[10];
printf("man:");//男方名字，不存在则输入“#”
gets(man1);
printf("woman:");//女方名字，不存在则输入“#”
gets(man1);
if(strcmp(man1,"#")==0&&strcmp(woman1,"#")==0)//若该结点男女都不存在，则说明该结点为空，即该子树的根结点不存在
{
root=NULL;
}
else{
root=(BiNode *)malloc(sizeof(BiNode));
strcpy(root->man,man1); //将男女的名字赋给该结点的数据域
strcpy(root->woman,woman1);

printf("father:"); //输入该结点的双亲名字
gets(father);
printf("mother:");
gets(mother);

CreateBiTree(root->firstchild); //递归创建该结点的左、右子树
CreateBiTree(root->nextsibling);
root->level=0;//将改结点的层数暂时定义为0
}
return OK;

}

Status Preorder(BiNode *T,char name[10],BiNode *p){
//先序遍历家谱树，查找与name名字相同的结点位置
if(T){
if(strcmp(T->man,name)==0||strcmp(T->woman,name)==0){
p=T;
return OK;
}
else{
if(Preorder(T->firstchild,name,p))return OK;
else return(Preorder(T->nextsibling,name,p));
}
}
else return ERROR;
}

void findchildren(BiNode *p){
//查找所得名字的孩子信息，输出他们的名字，若无孩子，则输出无孩子
int n=1;
BiNode *q;
if(p->firstchild){//该结点的firstchild指针指向的为他的第一个孩子
q=p->firstchild;
putoutchildren(q,n);//输出
}
while(q->nextsibling){
//第一个孩子的nextsibling指针指向的为孩子的兄弟，即第二个孩子
//如此继续，知道结点的右指针为空
q=q->nextsibling;
putoutchildren(q,n);//输出
}
if(n==1)printf("无孩子");
}

void putoutchildren(BiNode *q,int n){
//输出其孩子的结点的信息，并把孩子数加一
printf("第%d个孩子,男方名字%s,女方名字%s\n",n++,q->man,q->woman);
}

void findparents(BiNode *s){
//查询该结点的双亲名字
if(s->father=="#"&&s->mother=="#")
printf("没有父母信息");
else{
if((s->father)!="#")printf("father:%s\n",s->father);
if((s->mother)!="#")printf("mother:%s\n",s->mother);
}
}

void levelhome(BiNode *T){
//按层输出该家谱
SqStack S,N; //定义两个栈并初始化
InitStack(S);
InitStack(N);
BiNode *p;
p=T;
int n=1;
printf("第%d层的信息为:\n");
if(p){
print(p);
p->level=n;//修改p所指向的结点的辈分信息
Push(S,*p);//将该结点推进栈S
}
while(p=p->nextsibling){
//用循环来查找该层的所有信息，只要其nextsibling指向的结点不空，均为同一层
print(p);
p->level=n;
Push(S,*p);
}
while(!EmptyStack(S)||!EmptyStack(N)){
//循环，知道栈S和N都为空，说明按辈分遍历完成
leveling(S,N,n++);
leveling(N,S,n++);
}
printf("\n");
}

void leveling(SqStack S1,SqStack S2,int n){
//将S1栈保存的信息一一取出，查找他孩子的结点，输出其名字，并推入栈S2.
//即S2栈保存的结点是S1的下一辈
BiNode *p,*q;
printf("第%d层的信息为：\n");
while(!EmptyStack(S1)){
Pop(S1,*p);
q=p->firstchild;
if(q){
print(q);
q->level=n;
Push(S2,*q);
while(q=q->nextsibling){
print(q);
q->level=n;
Push(S2,*q);
}
}
}
}

void print(BiNode *p){
//输出该结点处的夫妇名字
printf("%s,%s\\",p->man,p->woman);
}