[转帖]单链表直接插入排序 _MySQL, Oracle及数据库讨论区_Weblogic技术|Tuxedo技术|中间件技术|Oracle论坛|JAVA论坛|Linux/Unix技术|hadoop论坛_联动北方技术论坛  
网站首页 | 关于我们 | 服务中心 | 经验交流 | 公司荣誉 | 成功案例 | 合作伙伴 | 联系我们 |
联动北方-国内领先的云技术服务提供商
»  游客             当前位置:  论坛首页 »  自由讨论区 »  MySQL, Oracle及数据库讨论区 »
总帖数
1
每页帖数
101/1页1
返回列表
0
发起投票  发起投票 发新帖子
查看: 2625 | 回复: 0   主题: [转帖]单链表直接插入排序         下一篇 
dwx8023
注册用户
等级:上尉
经验:612
发帖:114
精华:0
注册:2011-11-8
状态:离线
发送短消息息给dwx8023 加好友    发送短消息息给dwx8023 发消息
发表于: IP:您无权察看 2014-12-30 15:16:00 | [全部帖] [楼主帖] 楼主

今天看到顺序表的插值排序,所以研究了一下,想在链表上用直接插入排序。

北京联动北方科技有限公司

总的思想:最前面的一个数据节点则默认为有序,那么后面的n-1个数据节点为无序。将无序的节点一个一个插到有序链表合适的位置中,直到所有的节点都插完,就可形成一个有序链表。

具体方法:

首先创建链表:

//Link List structure
typedef struct node
{
      int Data;
      struct node *next;
}LinkList;
// create linklist
LinkList *head, *pNode;
head = NULL;
int Data = 0;
while ( Data < 9 )
{
      LinkList *pNode = new LinkList();
      pNode->Data = rand()%10;
      pNode->next = head;
      head = pNode;
      Data = Data + 1;
}
Data = 0;
//注意这里不能直接使用head->next,它会移动指针
pNode = head;
while(Data < 9)
{
      printf("%d n", pNode->Data);
      pNode = pNode ->next;
      Data = Data + 1;
}


下面开始排序:

第一步、、判断是否只有一个头节点或者只有一个数据节点?

如果是的话,那当然就不用排序了。因为已经成有序了。

Link Sort(Link Head)
{//我创建的是带头节点的链表。
if(!Head->next||!Head->next->next)//此步条件判断非常有价值。
return Head;


第二步:既然有多个数据节点,那就要排序了。此步做初始工作:先将一个整个链表分成一个有序链表和一个无序链表。如图形式2。

Link Sort(Link Head)
{//我创建的是带头节点的链表。
if(!head->next||!head->next->next)//此步条件判断非常有价值。
return Head;
ptr=head->next->next;
ptr_F=head;
head->next->next=NULL;//到此,分成了两个链表。


第三步:现在正式开始!(此步骤需要注意:不要让后面的无序链表断了,找不着了。)

Link Sort(Link Head)
{//我创建的是带头节点的链表。用直接插入法。
if((head->next==NULL)||(nead->next->next==NULL))//此步条件判断非常有价值。
{


cout<<"数据节点数少于2个,不用排序!"<<endl;

return Head;
}
//-----------第二步;
Link ptr;
Link ptr_F;
Link ptr_N;
ptr=nead->next->next;
ptr_F=Head;
head->next->next=NULL;//到此,分成了两个链表。
//第三步。
while(ptr)
{
      ptr_N=ptr->next;
      ptr_F=head;//ptr_F的归位。
      while(ptr_F->next)
      {
            if(ptr->Data>ptr_F->next->Data)
            {
                  ptr->next=ptr_F->next;
                  ptr_F->next=ptr;
                  break;
            }
            else
            {
                  if(ptr_F->next->next )
                  ptr_F = ptr_F->next;
                  else
                  {
                        ptr->next = ptr_F->next->next;
                        ptr_F->next->next = ptr;
                        break;
                  }
            }
      }
      ptr = ptr_N;
}
}//while(ptr)


cout<<"从高到低,排序成功!"<<endl;

return Head;
}


反转链表分两种方法,循环算法和递归算法,其中递归算法如下:

Linklist* resverse(Linklist *l)
{
      if(l == NULL || l->pNext == NULL)
      return l;
      Linklist *n = resverse(l->pNext);
      l->pNext->pNext = l;
      l->pNext = NULL;
      return n;
}


--转自 北京联动北方科技有限公司




赞(0)    操作        顶端 
总帖数
1
每页帖数
101/1页1
返回列表
发新帖子
请输入验证码: 点击刷新验证码
您需要登录后才可以回帖 登录 | 注册
技术讨论