UC知道数据结构 有序链表的问题
来源：百度知道 编辑：UC知道 时间：2024/05/17 06:24:17
大家好,
小弟在看数据结构时,遇到一条题目不明白,
想了上整一个通宵,还是不明白,
feel frustrate .
请各位路过的好人,高手,请回答一下我的问题行吗?
因为小弟积分不多,只有30分了,真不好意思,本来想多
给一些您们.
题目:有一个带头结点的单链表L,设计一个算法使其元素递增有序
void sor(linklist *&L)
{
linklit *p=L->next,*q,*r;
if(p!=NULL)
{r=p->next;
p->next=NULL;
p=r;
while (p!=NULL)
{r=p->next;
q=L;
while (q->next!=NULL && q->next->data<p->data)
q=q->next;
p->next=q->next;
q->next=p;
p=r;
}
}
}
可以帮我解释每一句的意思和用途吗?
因为我真的不明白,
小弟嗑头以谢!
关键问题是:
当q->next->data>p->data时会怎样?
万分感谢
小弟在看数据结构时,遇到一条题目不明白,
想了上整一个通宵,还是不明白,
feel frustrate .
请各位路过的好人,高手,请回答一下我的问题行吗?
因为小弟积分不多,只有30分了,真不好意思,本来想多
给一些您们.
题目:有一个带头结点的单链表L,设计一个算法使其元素递增有序
void sor(linklist *&L)
{
linklit *p=L->next,*q,*r;
if(p!=NULL)
{r=p->next;
p->next=NULL;
p=r;
while (p!=NULL)
{r=p->next;
q=L;
while (q->next!=NULL && q->next->data<p->data)
q=q->next;
p->next=q->next;
q->next=p;
p=r;
}
}
}
可以帮我解释每一句的意思和用途吗?
因为我真的不明白,
小弟嗑头以谢!
关键问题是:
当q->next->data>p->data时会怎样?
万分感谢
void sor(linklist* &L) >>
{
linklist *p=L->next,*q,*r; >>三个指针，p指向L的第一个非头的节点
if(p!=NULL) >> p不指向空
{r=p->next; >> r指向p的下一个节点
p->next=NULL; >> p的next赋空 等于把链表切开，只保留第一个节点(*)
p=r; >> p后移一位
while (p!=NULL) >> p不指向空，即当前不是最后一个节点-循环
{r=p->next; >> r指向是p的下一个节点
q=L; >> q指向头节点(**)
while (q->next!=NULL && q->next->data<p->data) >>链表的第一个节点的值小于p（当前处理的节点）的值
q=q->next; >>q从链表首节点开始后移 直到找到一个比他小的节点或者q到了L的最后一个节点（即2）
p->next=q->next; >>若找到比p小的，pq交换；如果q到了L的最后一个节点，则不变顺序，L增加到p这个节点
q->next=p; >> 同上
p=r; >> p继续后移
}
}
}
例如：
L 2 4 8 1 3
p r
--
第一步，切开：(*)
L 2 | 4 8 1 3
rp
--
第二步：(**)
L 2 | 4 8 1 3
q p r
此时比较：q->next < p，所以q后移
--
L 2 | 4 8 1 3
q p r
此时，q