ID #5713

单链表相关算法

[1]打印单链表,void PrintList(List list);

使用一个指针遍历所有链表节点。

[2]两个升序链表,打印tarList中的相应元素,这些元素的序号由SeqList指 定,void PrintLots(List tarList, List seqList);

使用两个指针分别遍历两个链表,每次取出序列链表的一个序号后,根据该 序号,到达目标链表指定节点。

[3]两个升序链表交集 ,List Intersect(List l1, List l2);

[4]两个升序链表并集 ,List Join(List l1, List l2);

[5]单链表就地置逆,void Reverse(List l);

使用三个指针表示前驱,当前和后继节点,每次将当前节点的Next指向前驱 节点,然后向后遍历直到链表末尾。

mylist.c

#include <stdio.h>
#include <stdlib.h>
#include "list.h"
void PrintList(List list);
static List InitList(int * arr, int size);
void PrintLots(List tarList, List seqList);
List Intersect(List l1, List l2);
List Join(List l1, List l2);
void Reverse(List l);
int main()
{
    int tarArr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int seqArr[] = {1, 4, 9, 16};
    List target = InitList(tarArr, 9);
    List sequence = InitList(seqArr, 4);
    PrintList(target);
    PrintList(sequence);
    PrintLots(target, sequence);
    ////////////////////////////////////////
    int arr1[] = {4, 5, 8, 9, 16, 22};
    int arr2[] = {1, 4, 9};
    List list1 = InitList(arr1, 6);
    List list2 = InitList(arr2, 3);
    PrintList(list1);
    PrintList(list2);
    List interList = Intersect(list1, list2);
    PrintList(interList);
    List joinList = Join(list1, list2);
    PrintList(joinList);
    ///////////////////////////////////////
    int arr[] = {1, 2, 3, 4, 5, 6};
    List list = InitList(arr, 6);
    PrintList(list);
    Reverse(list);
    PrintList(list);
    return 0;
}
/*---www.bianceng.cn 嬉咫汽全燕侭嗤圷殆 */
void PrintList(List list)
{
    Position p = First(list);
    while (p != NULL)
    {
        printf("%d ",Retrieve(p));
        p = Advance(p);
    }
    printf("n");
}
static List InitList(int * arr, int size)
{
    List list = CreateList();
    int i;
    for (i = size - 1; i >= 0; i--)
        Insert(*(arr + i), list, list);
    return list;
}
/* 曾倖幅會全燕,嬉咫tarList嶄議・哘圷殆・宸乂圷殆議會催喇SeqList峺協 */
void PrintLots(List tarList, List seqList)
{
    int seq;
    int i;
    int lastPos = 1;
    Position pSeq = First(seqList);
    Position pTar = First(tarList);
    while (pSeq != NULL)
    {
        seq = Retrieve(pSeq);
        for (i = lastPos; i < seq; i++)
        {
            pTar = Advance(pTar);
            lastPos++;
            if (pTar == NULL)//欺器朕炎全燕挑硫
            {
                printf("n");
                return;
            }
        }
        printf("%d ",Retrieve(pTar));
        pSeq = Advance(pSeq);
    }
    printf("n");
}
/* 曾倖幅會全燕住鹿 */
List Intersect(List l1, List l2)
{
    List list = CreateList();
    Position p = list;
    Position p1 = First(l1);
    Position p2 = First(l2);
    while (p1 != NULL && p2 != NULL)
    {
        if (Retrieve(p1) == Retrieve(p2))
        {
            Insert(Retrieve(p1), list, p);
            p = Advance(p);
            p1 = Advance(p1);
            p2 = Advance(p2);
        }
        else if (Retrieve(p1) < Retrieve(p2))
            p1 = Advance(p1);
        else
            p2 = Advance(p2);
    }
    return list;
}
/* 曾倖幅會全燕旺鹿 */
List Join(List l1, List l2)
{
    List list = CreateList();
    Position p = list;
    Position p1 = First(l1);
    Position p2 = First(l2);
    while (p1 != NULL && p2 != NULL)
    {
        if (Retrieve(p1) == Retrieve(p2))
        {
            Insert(Retrieve(p1), list, p);
            p1 = Advance(p1);
            p2 = Advance(p2);
        }
        else if (Retrieve(p1) < Retrieve(p2))
        {
            Insert(Retrieve(p1), list, p);
            p1 = Advance(p1);
        }
        else
        {
            Insert(Retrieve(p2), list, p);
            p2 = Advance(p2);
        }
        p = Advance(p);
    }
    while (p1 != NULL)
    {
        Insert(Retrieve(p1), list, p);
        p1 = Advance(p1);
        p = Advance(p);
    }
    while (p2 != NULL)
    {
        Insert(Retrieve(p2), list, p);
        p2 = Advance(p2);
        p = Advance(p);
    }
    return list;
}
/* 汽全燕祥仇崔剃 */
void Reverse(List l)
{
    Position prev = NULL;
    Position curr = First(l);
    Position next = Advance(curr);
    while (next != NULL)
    {
        SetAdvance(curr, prev);
        prev = curr;
        curr = next;
        next = Advance(next);
    }
    SetAdvance(curr, prev);
    SetAdvance(l, curr);//header
}


2011-07-01 18:29
阅读:
I'm VC , Just U know Y
本站部分文章来源于互联网,版权归原作者所有。

延伸阅读:

老调重提,利用SDK实现迷宫算法

几个数字信号处理算法程序

写个过河算法

CRC算法与实现

牛顿和拉格朗日插值算法