数据结构的问题

数据结构问题？

题主你好，过程请参考图，图中源代码也给了。当然，首先放的是正经的方法，后面简述一个不正经的。几个函数和模块：

1、定义两个结构体，一个是链表的链表，为了索引所有的链表弄的，当然，头指针这里多定义了一个数量，也就是量表的长度，这个有没有无所谓。一个是普通的量表，一个元素一个指针

2、输入部分，根据链表数量创建链表的链表，然后再根据每一个链表里元素的数量动态创建。因为我这里是c++环境，cin需要和scanf做个替换

3、反向链表：反向操作也就相当于对每一个元素的指针方向反过来，这一步一定要注意不要丢失了引用，注意结束时候将原来的第一个元素的next指向NULL。我这里p表示当前元素，q是当前开始算第二个元素、m是第三个，因为我们转换过程中需要先将第二个和第三个之间的引用断开，所以要给第三个先引用到。

4、打印链表，为了输出

5、主函数及运行结果

不正经的：

因为是一个一个元素进行输入，正常状态下，我们的流程是：创建一个指针->让已有最后一个元素的next指向这个新指针。那我们要反向，就可以在输入时候处理：新建一个指针->让这个新建指针的next指向已有的第一个，让新输入的元素成为头，这样就在输入时候就已经反过来了

关于数据结构的问题

有关数据结构的问题?

数据结构的问题。

这个程序是我自己用c语言编写出来的，当中运用堆栈的办法。仅供参考。

#include

#include

structduizhan//堆栈

{

inttopnext;//topnext指向下一个存储位置

intnode_ip[5];

}zhan;

intline[13];//记录轨迹存的是节点的id

typedefstructnode*pnode;

structnode

{

intid;

pnodelcnode;

pnodercnode;

};

pnodeaddr[13];///为了方便实现，浪费一下空间也没有关系啦，本来是为建立所

//要求的图而设置的，后来有用到

voidgetspace(void)//先为各个节点分配空间，刚开始时其leftchildnode和right

//childnode都置为NULL，然后用build()函数按要求连接成所需要的图

{

inti;

for(i=0;i<13;i++)

{

addr[i]=(pnode)malloc(sizeof(structnode));

addr[i]->lcnode=NULL;

addr[i]->rcnode=NULL;

addr[i]->id=i+1;

}

}

intbuild(intfrom_id,intto_id)//将已分配了空间的各个节点按要求连接，

{ //优先用leftchild指针连接节点

if(from_id==0||to_id==0)

{

printf("Errorinput.\n");

return-1;

}

if(from_id>14||to_id>14)

{

printf("Errorinput.\n");

return-1;

}

if(addr[from_id-1]->lcnode==NULL)//如果leftchild还没有使用，则可以是有leftchild，

addr[from_id-1]->lcnode=addr[to_id-1];//否则就看一下rightchild能不能用

elseif(addr[from_id-1]->rcnode==NULL) //连rightchild都不能用的话，就发生了错误

addr[from_id-1]->rcnode=addr[to_id-1];

else

{

printf("Errorinbuild.\n");

return-1;

}

return0;

}

voidpush(intnode_id)//将有rightchild的节点的id压进堆栈

{

if(zhan.topnext>=5){printf("Areadyfull.\n");return;}

zhan.node_ip[zhan.topnext]=node_id;

zhan.topnext++;//zhan.topnext并不是指向栈顶元素

}

intpop(void)//出栈，返回的是压进堆栈的id

{

if(zhan.topnext==0){printf("Empty!\n");return-1;}

zhan.topnext--;

returnzhan.node_ip[zhan.topnext];

}

intsearch_id(intcunchu[],intwant_id)//从记录路径的line[10]数组里面寻找

{ //所要的节点的id，返回的是所在的下标

inti;

for(i=0;i<14;i++)

if(cunchu[i]==want_id)

returni;

return-1;

}

voidsearch_theway(intfirstid)//寻找路径

{

intcurid=firstid;

inti=0;

line[i]=curid;

while(zhan.topnext!=0||addr[curid-1]->lcnode!=NULL)//如果堆栈不是空的或者当前节点

{ //存在leftchildnode则执行while循环

if(zhan.topnext!=0&&addr[curid-1]->lcnode==NULL)//此情形是当前的节点已

{ //是路的尽头，但是堆栈中有数据

curid=pop();//将堆栈最上面的id看成当前id

i=search_id(line,curid);//寻找该id在line[10]中的下标

i++;

line[i]=addr[curid-1]->rcnode->id;//转到该节点的rightchild(本来就是有

//rightchild的节点的id才压进堆栈的)

curid=line[i];//记录路径

}

if(addr[curid-1]->rcnode!=NULL)push(curid);//如果该节点有rightchild，则将其压进栈，

i++; //没有，则移动并且记录路径

line[i]=addr[curid-1]->lcnode->id;

curid=line[i];

if(addr[curid-1]->lcnode==NULL)//到了路的尽头(没有leftchild的节点，就是路的尽头，原因在

{ //于初始化连接的时候，就规定优先用leftchild指针连接节点)

i++;

line[i]=-1;//作个标记

i=0;

printf("找到了路径：\n");

while(line[i]!=-1)

{

printf("%d",line[i]);

i++;

}

printf("\n\n");

}

}

}

voidmain()

{

chari,from_id=0,to_id=0;

intfrom_to[14][2]={{1,2},{2,3},{3,4},{4,5},{4,6},{5,7},{6,8},{7,11},{8,9},

{8,10},{9,12},{10,12},{12,11},{11,13}};

//为了调用函数建立所要求的图而设置

zhan.topnext=0;

getspace();

for(i=0;i<14;i++)

build(from_to[i][0],from_to[i][1]);

search_theway(addr[0]->id);

}

标签：信息技术 编程 算法 数据结构 编程语言