<<  【驱动笔记12】SSDT HOOK实现进程保护 | 首 页 | 【驱动笔记13】有关cr0的一点记录  >>

  • 【原创】数据结构之链表

    2009-03-02

    分类：数据结构

    版权声明：转载时请以超链接形式标明文章原始出处和作者信息及本声明
    http://nokyo.blogbus.com/logs/35932222.html

        最近表现的非常郁闷，在学校积累的一点点自信全被打击的没有了，连续两个项目都没写出哪怕是一句代码。虽然的确跟自己不喜欢图形编程之类的问题有关，但也总不能拿这个当借口啊。

        索性啥也不做了，好好复习下数据结构，至于能不能留下就听天由命了。

        上学期为了找工作稍微复习了下数据结构，写了一个简单的链表程序，先发出来开个场。其实如果只是为了应用的话也没必要，STL里面有现成的链表、向量等等都很好用。现在复习数据结构主要是为了了解一下那些比较复杂的图操作，还有一些经典的算法如贪心算法等等。

        下面是一个简单的链表程序，它的功能是输入两个链表（以-1结束输入），然后将这两个链表合并起来。

    #include <stdio.h>
    #include <windows.h>

    typedef struct LNode{
        int        data;
        LNode    *next;
    }LNode, *LinkList;

    //
    // 函数声明
    //
    void     CreateList(LinkList &L);
    int         GetElem(LinkList L, int i);
    LinkList MergeList(LinkList L1,LinkList L2);
    void     SortList(LinkList &L,BOOL flag);
    void     PrintList(const LinkList &L);

    int main()
    {
        LinkList L1;
        LinkList L2;

        printf("第一个链表：\n");
        CreateList(L1);
        PrintList(L1);

        printf("第二个链表：\n");
        CreateList(L2);
        PrintList(L2);

        printf("合并后的链表：\n");
        LinkList L = MergeList(L1,L2);
        PrintList(L);

        return 0;
    }

    //
    //    创建链表L(遇到-1时结束)
    //
    void CreateList(LinkList &L)
    {
        LinkList head;
        LinkList p;

        // 建立第一个结点
        L = (LinkList)malloc(sizeof(LNode));
        L->next = NULL;
        scanf("%d",&L->data);

        // 保存头结点
        head = L;

        int iData;
        while (TRUE)
        {
            scanf("%d",&iData);
            if (iData == -1)
                break;

            // 建立一个结点p
            p = (LinkList)malloc(sizeof(LNode));
            p->data = iData;
            p->next = NULL;

            // 把L指针指向结点p
            L->next = p;
            L = L->next;
        }
        // 把指针移动到头结点
        L = head;
    }

    //
    //    提取出链表L中第i个结点的值（暂时没用上）
    //
    int GetElem(LinkList L, int i)
    {
        LinkList p;
        int j = 1;

        p = L;
        while (p && (j < i))
        {
            p = p->next;
            ++j;
        }
        if ((!p) || (j>i))
        {
            return -1;
        }

        return (p->data);
    }

    //
    //    合并链表L1和L2(递归法)
    //
    LinkList MergeList(LinkList L1,LinkList L2)
    {
        if(L1 == NULL)
        {
            return L2;
        }
        if(L2 == NULL)
        {
            return L1;
        }

        LinkList head;

        if(L1->data <= L2->data)
        {
            head = L1;
            head->next = MergeList(L1->next,L2);
        }
        else
        {
            head = L2;
            head->next = MergeList(L1,L2->next);
        }

        return head;
    }

    //
    //    输出链表的所有结点
    //
    void PrintList(const LinkList &L)
    {
        LinkList p;
        p = L;

        while(p)
        {
            printf("%d -> ",p->data);
            p = p->next;
        }

        printf("NULL\n");
    }


    随机文章：





    Tag：
    引用地址：
    grayfox 发表于10:14:23 | 编辑 | 继续话题 | 转发 | 分享　0