Chinaunix首页 | 论坛 | 博客
  • 博客访问: 526883
  • 博文数量: 96
  • 博客积分: 2960
  • 博客等级: 少校
  • 技术积分: 1850
  • 用 户 组: 普通用户
  • 注册时间: 2006-12-11 15:25
文章分类

全部博文(96)

文章存档

2009年(37)

2008年(59)

我的朋友

分类:

2008-05-20 18:08:10

codes is included below, this arithmetic is not the best one, but it is the one that easy to be understand. others method not included here, you can google or baidu it for more informations.

-bash-3.2# gcc -o loop_in_list loop_in_list.c
-bash-3.2# ./loop_in_list
NOT LOOP LIST
-bash-3.2# gcc -D_LOOP_LIST -o loop_in_list loop_in_list.c
-bash-3.2# ./loop_in_list
LOOP LIST

/* - loop_in_list.c, not test yet, just for notes - */
#include <stdio.h>
#include <assert.h>

typedef struct node_t{
    int key;
    struct node_t *next;
} node_t;

/*
 * DESC:
 * chk whether 'nd' in the list defined by 'hdr' and 'tail'
 * INPUT:
 * hdr/r: the 1st node pointer
 * tail/r: the last node pointer
 * nd/r: the nd to chk
 * OUTPUT:
 * -1: err
 * 0: no in
 * 1: in
 */

int inlist(node_t *hdr, node_t *tail, node_t *nd)
{
    assert(NULL != hdr);
    assert(NULL != tail);

    if (NULL == nd) return 0;

    for (; hdr != tail; hdr=hdr->next) {
        assert(NULL != hdr);
        /*
        if (NULL == hdr)
            return -1;
        */

        if (nd == hdr)
            return 1;
    }

    /* hdr == tail now */
    if (nd == tail)
        return 1;
   
    return 0;
}

/*
 * DESC:
 * chk whether list has loop nodes
 * INPUT:
 * list/r: the list header
 * OUTPUT:
 * 1: looped
 * 0: it's OK
 */

int loopinlist(node_t *list)
{
    node_t *hdr = list;
    node_t *tail = hdr;
    node_t *cur = NULL;

    assert(NULL != list);

    for (cur=tail->next; NULL!=cur; cur=cur->next) {
        if (inlist(hdr, tail, cur))
            return 1;
        tail = cur;
    }

    return 0;
}

#define LIST_EQ(list, node) \
    (node)->next = (list)->next; \
    (list)->next = (node); \
/*
 * Defines a list to test
 */

int main(void)
{
    int i = 0;
    node_t list[100]; /* not initialized */

    list[0].next = NULL; /* list initialized */
   
    for (i=1; i<100; i++) {
        LIST_EQ(list, &list[i]);
    }

    i = 0;
   
#ifdef _LOOP_LIST
    /* choose a loop */
    list[66].next = &list[55];
    i = loopinlist(list);
#endif
   
    printf("%s\n", (0==i)?"NOT LOOP LIST":"LOOP LIST");

    return 0;
}

阅读(1030) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~