Chinaunix首页 | 论坛 | 博客
  • 博客访问: 778751
  • 博文数量: 230
  • 博客积分: 6330
  • 博客等级: 准将
  • 技术积分: 2188
  • 用 户 组: 普通用户
  • 注册时间: 2009-07-10 15:55
个人简介

脚踏实地

文章分类

全部博文(230)

文章存档

2017年(1)

2016年(7)

2015年(10)

2014年(32)

2013年(24)

2012年(33)

2011年(50)

2010年(30)

2009年(43)

分类: C/C++

2009-12-04 20:50:46

Q1  链表的反序
Q2  找出链表的中间元素  //多设指针,2种速度
Q3  链表排序
Q4  判断一个单链表是否有环
 
以下给出链表结点的数据结构:
typedef struct _list_node
{
    double keyVal;
    struct _list_node *next;
}ListNode;

Q1 单链表的反序
Code:
ListNode* reverseList(ListNode* head)
{
    ListNode *p1, *p2 , *p3;
    //链表为空,或是单结点链表直接返回头结点
    if (head == NULL || head->next == NULL)
    {
        return head;
    }
    p1 = head;
    p2 = head->next;
    while (p2 != NULL)
    {
        p3 = p2->next;
        p2->next = p1;
        p1 = p2;
        p2 = p3;
    }
    head->next = NULL;
    head = p1;
return head;
}

Q2 找出链表的中间元素
Code:
ListNode* find_midlist(ListNode* head)
{
    ListNode *p1, *p2;
   
    if (head == NULL || head->next == NULL)
    {
        return head;
    }
    p1 = p2 = head;
    while (1)
    {
        if (p2->next != NULL && p2->next->next != NULL)
        {
            p2 = p2->next->next;
            p1 = p1->next;
        }
        else
        {
            break;
        }
    }
    return p1;
}
思路分析:
单链表的一个比较大的特点用一句广告语来说就是“不走回头路”,不能实现随机存取(random access)。如果我们想要找一个数组a的中间元素,直接a[len/2]就可以了,但是链表不行,因为只有a[len/2 - 1] 知道a[len/2]在哪儿,其他人不知道。因此,如果按照数组的做法依样画葫芦,要找到链表的中点,我们需要做两步(1)知道链表有多长(2)从头结点开始顺序遍历到链表长度的一半的位置。这就需要1.5n(n为链表的长度)的时间复杂度了。有没有更好的办法呢?有的。想法很简单:两个人赛跑,如果A的速度是B的两倍的话,当A到终点的时候,B应该刚到中点。这只需要遍历一遍链表就行了,还不用计算链表的长度。
上面的代码就体现了这个想法。


Q3  链表排序
链表相对于数组来说: 非常适合插入,删除等操作,不适合直接去某一项的值。
一般有三种: 插入排序, 冒泡排序, 归并排序。

插入排序:
  1. struct student{
  2.     int num;
  3.     struct student* next;
  4. };
  5. struct student *InsertSort(struct student *head)
  6. {
  7.     struct student *first; /*为原链表剩下用于直接插入排序的节点头指针*/
  8.     struct student *t; /*临时指针变量:插入节点*/
  9.     struct student *p; /*临时指针变量*/
  10.     struct student *q; /*临时指针变量*/

  11.     first = head->next; /*原链表剩下用于直接插入排序的节点链表:可根据图12来理解。*/
  12.     head->next = NULL; /*只含有一个节点的链表的有序链表:可根据图11来理解。*/

  13.     while (first != NULL) /*遍历剩下无序的链表*/
  14.     {
  15.         /*注意:这里for语句就是体现直接插入排序思想的地方*/
  16.         for (t=first, q=head; ((q!=NULL) && (q->num < t->num)); p=q, q=q->next); /*无序节点在有序链表中找插入的位置*/

  17.         /*退出for循环,就是找到了插入的位置*/
  18.         /*注意:按道理来说,这句话可以放到下面注释了的那个位置也应该对的,但是就是不能。
  19.          * 原因:你若理解了上面的第3条,就知道了。*/
  20.         first = first->next; /*无序链表中的节点离开,以便它插入到有序链表中。*/

  21.         if (q == head) /*插在第一个节点之前*/
  22.         {
  23.             head = t;
  24.         }
  25.         else /*p是q的前驱*/
  26.         {
  27.             p->next = t;
  28.         }
  29.         t->next = q; /*完成插入动作*/
  30.         /*first = first->next;*/
  31.     }
  32.     return head;
  33. }

合并排序算法:
递归算法很容易,不再阐述,非递归算法思路如下:将数组中的相邻元素两两配对。用merge函数将他们排序,构成n/2组长度为2的排序好的子数组段,然后再将他们排序成长度为4的子数组段,如此继续下去,直至整个数组排好序。
  1. void mergeSort2(int n){
  2.     int s=2,i;
  3.     while(s<=n){
  4.         i=0;
  5.         while(i+s<=n){
  6.             merge(i,i+s-1,i+s/2-1);
  7.             i+=s;
  8.         }
  9.         //处理末尾残余部分
  10.         merge(i,n-1,i+s/2-1);
  11.         s*=2;
  12.     }
  13.     //最后再从头到尾处理一遍
  14.     merge(0,n-1,s/2-1);
  15. }
关于 merge函数的实现,参考算法导论中文版 P17,很简单。。。


思路分析:
链表排序最好使用归并排序算法。堆排序、快速排序这些在数组排序时性能非常好的算法,在链表只能“顺序访问”的魔咒下无法施展能力;但是归并排序却如鱼得水,非但保持了它O(nlogn)的时间复杂度,而且它在数组排序中广受诟病的空间复杂度在链表排序中也从O(n)降到了O(1)。真是好得不得了啊,哈哈。以上程序是递推法的程序,另外值得一说的是看看那个时间复杂度,是不是有点眼熟?对!这就是分治法的时间复杂度,归并排序又是divide and conquer。


Q4  判断一个单链表是否有环

int is_looplist (ListNode *head)
{
    ListNode *p1, *p2;
    p1 = p2 = head;
 
if (head == NULL || head->next == NULL)
    {
        return 0;
    }
while (p2->next != NULL && p2->next->next != NULL)
    {
        p1 = p1->next;
        p2 = p2->next->next;
        if (p1 == p2)
        {
            return 1;
        }
    }
return 0;
}
思路分析:
这道题是《C专家编程》中的题了。其实算法也有很多,比如说:我觉得进行对访问过的结点进行标记这个想法也不错,而且在树遍历等场合我们也经常使用。但是在不允许做标记的场合就无法使用了。在种种限制的条件下,就有了上面的这种算法,其实思想很简单:就像两个人在操场上跑步一样,只要有个人的速度比另一个人的速度快一点,他们肯定会有相遇的时候的。不过带环链表与操场又不一样,带环链表的状态是离散的,所以选择走得快的要比走得慢的快多少很重要。比如说这里,如果一个指针一次走三步,一个指针一次走两步的话,很有可能它们虽然在一个环中但是永远遇不到,这要取决于环的大小以及两个指针初始位置相差多少了。呵呵。

参考资料
1. 欧立奇等著《程序员面试宝典》,电子工业出版社
2. 《C专家编程》
3.Jurgen Appelo 《软件开发者面试百问》
--------------

阅读(936) | 评论(0) | 转发(0) |
0

上一篇:Linux下c开发 之 线程通信

下一篇:3G常识

给主人留下些什么吧!~~