有一个线性表,采用带头结点的单链表L来存储,设计一个算法将其逆置,且不能建立新节点,只能通过表中已有的节点的重新组合来完成。分析:线性表中关于逆序的问题,就是用建立链表的头插法.而本题要求不能建立新结点,也就不能把元素重新弄到一个表中.可以将L中的元素作为逆转后的L的元素来源,将L->next设置为空.然后将头结点后的一串结点用头插法逐个插入L中.
伪代码:
void reversel(LNode *L){ LNode *p=L->next, *q; L->next=NULL; //置为空 while(p!=NULL) { q=p->next; //q记录p的直接后继结点的位置 p->next=L->next; L->next=p; p=q; }}
cue:
1.LNode *p, *q;
并不是建立新结点,它们只是存储地址的变量.(我第一次遇到这个问题时没弄懂,以为这两是定义了新的结点.其实不是.)
2LNode *A=(LNode*)malloc(sizeof(LNode));
才是用户分配了一片LNode型空间,也就是构造了一个LNode型结点.这时候定义了名为A的指针来指向这个结点,同时我们也把A也当做这个结点的名字.这里A命名了两个东西,一个是结点,一个是指向这个结点的指针.
指针变量自身的存储空间是系统分配的,不需要用户调用函数free()释放,只有用户分配的存储空间才需要用户自己来释放.