亚洲av成人无遮挡网站在线观看,少妇性bbb搡bbb爽爽爽,亚洲av日韩精品久久久久久,兔费看少妇性l交大片免费,无码少妇一区二区三区

  免費(fèi)注冊(cè) 查看新帖 |

Chinaunix

  平臺(tái) 論壇 博客 文庫
最近訪問板塊 發(fā)新帖
樓主: emacsnw
打印 上一主題 下一主題

一個(gè)關(guān)于單向鏈表的面試題。 [復(fù)制鏈接]

論壇徽章:
0
71 [報(bào)告]
發(fā)表于 2007-04-28 10:05 |只看該作者
兩個(gè)步進(jìn)不一樣的指針是個(gè)好辦法。

但如果有好的內(nèi)存分配策略的話,應(yīng)該可以簡(jiǎn)化這個(gè)問題。

比如說,鏈表的每一項(xiàng),從前到后,分配的內(nèi)存地址都是有序的的話,
只需要把list->next指針和list本身比較一下看是否符合順序就知道是否找到節(jié)點(diǎn)了。

不過這個(gè)內(nèi)存分配方法不好辦。

論壇徽章:
0
72 [報(bào)告]
發(fā)表于 2007-04-28 12:17 |只看該作者
首先用1步長(zhǎng)2步長(zhǎng)的方法判斷是否有環(huán)存在O(n)。
如果有環(huán),那就再?gòu)念^開始,看每個(gè)節(jié)點(diǎn)的next是不是空。如果是空,就是我們要找的節(jié)點(diǎn);不是空的話,就把它置空。O(n)
以樓主的例子,到8的時(shí)候,前面的節(jié)點(diǎn)的next都是空了,然后8指向3,發(fā)現(xiàn)3的next為空,就找到了最終結(jié)果。

這樣的方法復(fù)雜度時(shí)間O(n),空間O(1)
但是破環(huán)了原有的鏈表
如果想不破壞
就需要一個(gè)輔助鏈表保存原始鏈表的信息,這樣就需要O(n)的空間

所以最終結(jié)論是時(shí)間空間都是O(n)

論壇徽章:
0
73 [報(bào)告]
發(fā)表于 2007-04-28 12:38 |只看該作者
我想到一個(gè)新算法,不知道行不行得通,大家看一下,先是直接開一個(gè)空間,讓這整個(gè)空間的地址是連續(xù)的,然后根據(jù)上面的連表一個(gè)個(gè)考過去,因?yàn)榈刂肥沁B續(xù)的,所以當(dāng)出現(xiàn)一個(gè)指向的結(jié)構(gòu)體的地扯比自已小的時(shí)候,這時(shí)就出現(xiàn)了一個(gè)循環(huán),也就是找到了樓主的循環(huán)點(diǎn),可是這里有一個(gè)能點(diǎn)就是這個(gè)考的過程,我現(xiàn)在還沒想出來.大家看看,能不能實(shí)現(xiàn)。

[ 本帖最后由 jist12321 于 2007-4-28 12:39 編輯 ]

論壇徽章:
0
74 [報(bào)告]
發(fā)表于 2007-04-28 12:56 |只看該作者
原帖由 jist12321 于 2007-4-28 12:38 發(fā)表
我想到一個(gè)新算法,不知道行不行得通,大家看一下,先是直接開一個(gè)空間,讓這整個(gè)空間的地址是連續(xù)的,然后根據(jù)上面的連表一個(gè)個(gè)考過去,因?yàn)榈刂肥沁B續(xù)的,所以當(dāng)出現(xiàn)一個(gè)指向的結(jié)構(gòu)體的地扯比自已小的時(shí)候,這時(shí) ...


為什么地址小的時(shí)候就可以斷定是循環(huán)呢,這種說法沒有任何根據(jù)

論壇徽章:
0
75 [報(bào)告]
發(fā)表于 2007-04-28 13:08 |只看該作者
原帖由 deadlylight 于 2007-4-28 12:56 發(fā)表


為什么地址小的時(shí)候就可以斷定是循環(huán)呢,這種說法沒有任何根據(jù)


對(duì)不起,后面沒看下去,剛剛轉(zhuǎn)回去看了一下,行不通。不過,一步二步法是絕對(duì)可以的,而且我認(rèn)認(rèn)應(yīng)該是時(shí)間復(fù)雜度是最小的了。

論壇徽章:
0
76 [報(bào)告]
發(fā)表于 2007-04-28 13:24 |只看該作者
原帖由 星塵細(xì)雨 于 2007-4-28 10:05 發(fā)表
兩個(gè)步進(jìn)不一樣的指針是個(gè)好辦法。

但如果有好的內(nèi)存分配策略的話,應(yīng)該可以簡(jiǎn)化這個(gè)問題。

比如說,鏈表的每一項(xiàng),從前到后,分配的內(nèi)存地址都是有序的的話,
只需要把list->next指針和list本身比較一 ...

我想的方法跟你差不多啊,可是這個(gè)內(nèi)存分配有序的話就不存在鏈表一說,直接用數(shù)組了,像我說用考出整個(gè)鏈表更可笑,鏈表尾都不知道,怎么可能知道考哪里為止。做了一回傻瓜。

論壇徽章:
0
77 [報(bào)告]
發(fā)表于 2007-04-28 16:36 |只看該作者
各位給了很多方法,可惜沒給代碼,小弟也就沒認(rèn)真看了。
長(zhǎng)期做系統(tǒng)程序,算法思維僵化了,想從現(xiàn)在開始鍛煉鍛煉,我就直接貼代碼了。
算法很笨,先用不同步長(zhǎng)前進(jìn)找到圈,然后把圈中所有元素存到數(shù)組中(c99動(dòng)態(tài)數(shù)組),最后再?gòu)逆湵眍^走一遍,第一個(gè)在數(shù)組中存在的元素就是圈的首節(jié)點(diǎn)。
不會(huì)算復(fù)雜度,估計(jì)是O(n^3)左右了,太爛了,開始練習(xí)算法。

  1. #include <stdio.h>
  2. #include <stdlib.h>

  3. typedef struct list
  4. {
  5.     int val;
  6.     struct list *next;
  7. } list_t;
復(fù)制代碼

  1. //不用細(xì)看,用來產(chǎn)生帶圈的鏈表。
  2. //len參數(shù)指定鏈表長(zhǎng)度,loop_pos指定最后一個(gè)元素指向鏈表中的第幾個(gè)元素。
  3. //loop_pos如果大于len,則鏈表尾指向鏈表頭。
  4. list_t *pro_list(int len, int loop_pos)
  5. {
  6.     list_t *head = malloc(sizeof(list_t));
  7.     list_t *t = head, *n = head;
  8.     int i;
  9.     head->val = 0;

  10.     for ( i=1; i<len; i++ )
  11.     {   
  12.         list_t *m = malloc(sizeof(list_t));
  13.         m->val = i;
  14.         t->next = m;
  15.         t = m;
  16.     }   

  17.     if ( loop_pos <= len )
  18.         for ( i=0; i<loop_pos; i++ )
  19.             n = n->next;

  20.     t->next = n;
  21.    
  22.     return head;
  23. }

復(fù)制代碼

  1. //鏈表打印函數(shù),不用細(xì)看
  2. void print_list(list_t *head)
  3. {
  4.     list_t *t = head;
  5.     while (1)
  6.     {
  7.         printf("val:%d, addr:%p\n", t->val, t);
  8.         if ( NULL == t->next )
  9.             break;

  10.         t = t->next;
  11.     }
  12. }
復(fù)制代碼

  1. //用來找圈的頭節(jié)點(diǎn),被find_loop調(diào)用
  2. //addr保存的是圈中所有節(jié)點(diǎn)的地址,head指向鏈表頭,lo_len表示圈中有多少個(gè)節(jié)點(diǎn)
  3. list_t *find_loop_begin(list_t *addr[], list_t *head, int lo_len)
  4. {
  5.     int i;
  6.     list_t *t = head;

  7.     while (1)
  8.     {
  9.         for ( i=0; i<lo_len; i++ )
  10.             if ( addr[i] == t )
  11.                 return addr[i];

  12.         t = t->next;
  13.     }

  14.     // should not be here
  15.     return NULL;
  16. }


  17. list_t *find_loop(list_t *head)
  18. {
  19.     list_t *t1 = head;
  20.     list_t *t2 = head->next;

  21.     while (1)
  22.     {
  23.         if ( t1 == t2 )
  24.         {
  25.             int lo_len = 1;
  26.             int i = 1;
  27.             t1 = t1->next;
  28.            //先找出圈中有多少個(gè)節(jié)點(diǎn)
  29.             while ( t1 != t2 )
  30.             {
  31.                 lo_len ++;
  32.                 t1 = t1->next;
  33.             }
  34.            //把圈中的所有幾點(diǎn)存入數(shù)組
  35.             list_t *addr[lo_len];
  36.             addr[0] = t2;
  37.             t1 = t2->next;
  38.             while ( t1 != t2 )
  39.             {
  40.                 addr[i++] = t1;
  41.                 t1 = t1->next;
  42.             }
  43.             //找出圈中的第一個(gè)節(jié)點(diǎn)
  44.             return find_loop_begin(addr, head, lo_len);
  45.         }
  46.         t1 = t1->next;
  47.         t2 = t2->next->next;
  48.     }

  49.     return t1;
  50. }
復(fù)制代碼


  1. int main()
  2. {
  3.     list_t *head = pro_list(20, 11);
  4.     list_t *lo = find_loop(head);
  5.     printf("val:%d, addr:%p\n", lo->val, lo);
  6.     //print_list(head);

  7. }
復(fù)制代碼

論壇徽章:
0
78 [報(bào)告]
發(fā)表于 2007-04-28 17:01 |只看該作者

回復(fù) 74樓 deadlylight 的帖子

怎么沒有根據(jù)?

這個(gè)是有個(gè)前提條件的!只是滿足這個(gè)前提條件比較困難而已。

論壇徽章:
0
79 [報(bào)告]
發(fā)表于 2007-04-28 20:07 |只看該作者
原帖由 deadlylight 于 2007-4-28 12:17 發(fā)表
首先用1步長(zhǎng)2步長(zhǎng)的方法判斷是否有環(huán)存在O(n)。
如果有環(huán),那就再?gòu)念^開始,看每個(gè)節(jié)點(diǎn)的next是不是空。如果是空,就是我們要找的節(jié)點(diǎn);不是空的話,就把它置空。O(n)
以樓主的例子,到8的時(shí)候,前面的節(jié)點(diǎn)的ne ...



我覺得這個(gè)算法是可以的,還有那個(gè)大步小步的,應(yīng)該也是可以的,不過對(duì)于推出的公式,還不能確定是否正確,因?yàn)榇笮〔讲灰欢ㄊ且蝗,而是大步m圈,小步n圈之后才相遇的,想到這個(gè)就暈了,就搞不清公式是否正確,不過應(yīng)該大小步是能解這個(gè)問題的。
再想想。。。

論壇徽章:
0
80 [報(bào)告]
發(fā)表于 2007-04-28 20:52 |只看該作者
原帖由 emacsnw 于 2007-2-6 04:27 發(fā)表
想了一下,似乎下面的算法可以:O(1)空間,O(n)時(shí)間。
兩個(gè)額外指針p1, p2,開始都指向頭S。設(shè)需要找到的循環(huán)部分第一個(gè)結(jié)點(diǎn)的位置為A,S到A的距離為x (x可能為0),鏈表的循環(huán)部分長(zhǎng)度為y (y > 0)。

算法 ...



這個(gè)算法應(yīng)該是看懂了,畫了個(gè)圖分析了一下,似乎是這樣的,如果還是有什么地方不對(duì),請(qǐng)指出來。還是很有意思的一道題目。

鏈表問題.jpg (115.92 KB, 下載次數(shù): 54)

鏈表循環(huán)問題

鏈表循環(huán)問題
您需要登錄后才可以回帖 登錄 | 注冊(cè)

本版積分規(guī)則 發(fā)表回復(fù)

  

北京盛拓優(yōu)訊信息技術(shù)有限公司. 版權(quán)所有 京ICP備16024965號(hào)-6 北京市公安局海淀分局網(wǎng)監(jiān)中心備案編號(hào):11010802020122 niuxiaotong@pcpop.com 17352615567
未成年舉報(bào)專區(qū)
中國(guó)互聯(lián)網(wǎng)協(xié)會(huì)會(huì)員  聯(lián)系我們:huangweiwei@itpub.net
感謝所有關(guān)心和支持過ChinaUnix的朋友們 轉(zhuǎn)載本站內(nèi)容請(qǐng)注明原作者名及出處

清除 Cookies - ChinaUnix - Archiver - WAP - TOP