大胖的部落格

Just a note
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  112 随笔 :: 0 文章 :: 3 评论 :: 0 Trackbacks
链表操作
向有序单向链表中插入元素：
1、插入节点是否合法。
2、链表是否合法。
3、插入节点是否加在链表最前，此时要更新链表头指针。
4、遍历链表时，使用两个节点指针记录位置，一前一后，当后面的节点值比插入节点值大时，停止，将前节点指向新节点，新节点指向后节点。
      移动终止条件还需要判断是否已经到了链表结尾。

判断单向链表中是否有环：
利用快慢指针，快指针一次移动两个，慢指针一次移动一个，都从链表开始出发，若存在环，则快指针必和慢指针再一次重合。

判断2链表是否相交：
1.将链表2首尾相接，若链表1有环，则相交。
2.将链表1各节点地址存入hash表，遍历链表2.
3.分别遍历两个链表至尾节点，若尾节点地址一样，则相交。


Code1: 向有序单向链表中插入元素：
#include <iostream>

using namespace std;

//节点
struct Node
{
    Node(int i):value(i),next(NULL){}
    int value;
    Node* next;
};

//单向链表
struct Chain
{
    Node* head;
    Node* InsertAscend(Node* p);
    void Print();
};

//升序插入节点
Node* Chain::InsertAscend(Node* newNode)
{
    //插入节点为空，则返回
    if(NULL == newNode)
    {
        return head;
    }
    
    //链表为空，则更新链表头，返回
    if(NULL == head)
    {
        head = newNode;
        return head;
    }

    //若插入节点值最小，则将此节点插入链表最前
    if(head->value > newNode->value)
    {
        newNode->next = head;
        head = newNode;
        return head;
    }

    //遍历链表，寻找插入点
    //使用两个节点指针记录位置，一前一后，当后面的节点值比插入节点值大时，停止，将前节点指向新节点，新节点指向后节点
    Node* p = head;
    Node* prev = p;
    while((NULL != p)&&(p->value <= newNode->value))
    {
        prev = p;    //在遍历指针移动前，记录位置
        p = p->next;
    }
    prev->next = newNode;
    newNode->next = p;

    return head;
}

//输出链表
void Chain::Print()
{
    Node* p = head;
    while(NULL != p)
    {
        printf("%d  ",p->value);
        p = p->next;
    }
}

void main()
{
    //创建5个Node
    Node* (pi[5]) = {NULL}; 
    for(int i=0; i<5; ++i)
        pi[i] = new Node(i);

    //创建chain，并插入Node
    Chain myChain;
    myChain.head = NULL;
    myChain.InsertAscend(pi[3]);
    myChain.InsertAscend(pi[2]);
    myChain.InsertAscend(pi[0]);
    myChain.InsertAscend(pi[4]);
    myChain.InsertAscend(pi[1]);
    myChain.Print();

    //删除Node
    for(int i=0; i<5; ++i)
        delete pi[i];
}


Code2: 判断单向链表中是否有环：

#include <iostream>

using namespace std;

//节点
struct Node
{
    Node* next;
};

//判断单向链表中是否存在环
bool CheckCircle(Node* p)
{
    Node* pFast = p;
    Node* pSlow = p;
    do
    {
        if(NULL != pFast)
            pFast = pFast->next;

        if(NULL != pFast)
            pFast = pFast->next;
        
        if(NULL != pSlow)
            pSlow = pSlow->next;
    } while((NULL !=pFast) && (pFast != pSlow));

    if(NULL == pFast)    //快指针到链表尾，无环
        return false;
    else                //快慢指针重合，有环
        return true;
}

void main()
{
    Node n1, n2, n3, n4, n5;
    n1.next = &n2;
    n2.next = &n3;
    n3.next = &n4;
    n4.next = &n5;
    n5.next = NULL;

    cout<<boolalpha<<CheckCircle(&n1)<<endl;

    n5.next = &n3;

    cout<<boolalpha<<CheckCircle(&n1)<<endl;

}
posted on 2009-07-30 23:36 大胖 阅读(242) 评论(0)  编辑 收藏 引用 所属分类: Algorithm

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理