论坛 › 数据结构与算法 › 复习链表数据结构

yundi 发表于 2016-7-1 10:56:56

复习链表数据结构

本帖最后由 yundi 于 2016-7-1 11:00 编辑

一些知识点模模糊糊的，发个帖子回忆一下，有不当之处，欢迎指点
/* c 链表数据结构 1.0 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//节点结构
struct _tagNode
{
        int NData;//数据
        struct _tagNode * NextN;//节点指针，指向下一个结构
};

typedef struct _tagNode Node, * PNode;//为书写方便，自定义节点数据类型

int main()
{
        Node nodes;//定义了十个节点
        int i;
        PNode pnodex;//定义一个节点指针变量
        for(i=0;i<10;i++)
        {
                nodes.NData = i;
                if(i!=9){
                        nodes.NextN = &nodes;
                }else{
                        nodes.NextN = NULL;
                }               
        }//将十个节点串起来，就成了链表       

        pnodex = nodes;//指向首地址
        //用链表的方式遍历节点
        while(pnodex->NextN != NULL)
        {
                printf("%p:%d,next %p\n",pnodex,pnodex->NData,pnodex->NextN);
                pnodex++;
        }
        printf("%p:%d,next %p\n",pnodex,pnodex->NData,pnodex->NextN);//输出最后一个节点
        getchar();
}

以上是形式上用链表，本质还是数组。链表的特性（节点分散，逻辑线性）没有体现出来。下面才是链表的真面目。

/* c 链表数据结构 1.1 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//节点结构
struct _tagNode
{
        int NData;//数据
        struct _tagNode * NextN;//节点指针，指向下一个结构
};

typedef struct _tagNode Node, * PNode, * Link;//加上一个Link类型

int main()
{
        Node linkhead;//链表！头节点
        Link head = &linkhead ;//链表！固定一个指向链表头的指针。
        PNode pnodex;//浮标，在节点间移动
        Node a;
        head->NData = 0; //设数据为0，可用来保存链表长度,
        head->NextN = NULL;//下节点为NULL
        //添加节点
        //加上1个已存在节点       
        a.NData = 'a';
        a.NextN = NULL;
        pnodex = head;//浮标指向链表头
        pnodex->NextN = &a;//连上a节点
        (head->NData) ++;//计数+1
       
        //遍历每个节点
        while(pnodex->NextN != NULL)
        {
                printf("%p:%d,next %p\n",pnodex,pnodex->NData,pnodex->NextN);
                pnodex = pnodex->NextN;//移到下个节点！有别于数组的移动
        }
        printf("%p:%d,next %p\n",pnodex,pnodex->NData,pnodex->NextN);//输出最后一个节点
        getchar();
}

yundi 发表于 2016-7-1 10:58:24

上面代码仍然存在问题，既然已经定义a，可以随时访问a的地址和数据，何必又要弄个链表来保存a？换种说法，每加一个节点就定义一个节点变量明显不现实，所以用链表来管理没定义成变量的内存块，所以添加节点一般是这个样：
/* c 链表数据结构 1.2 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//节点结构
struct _tagNode
{
        int NData;//数据
        struct _tagNode * NextN;//节点指针，指向下一个结构
};

typedef struct _tagNode Node, * PNode, * Link;//加上一个Link类型

int main()
{
        Node linkhead;//链表！头节点
        Link head = &linkhead ;//链表！固定一个指向链表头的指针。
        PNode pnodex = head;//浮标，在节点间移动，初始指向头结点。
        head->NData = 0; //设数据为0，可用来保存链表长度,
        head->NextN = NULL;//下节点为NULL
        //添加节点
        pnodex->NextN = (PNode)malloc(sizeof(Node));//申请内存空间，并连接到链表末尾
        memset(pnodex->NextN,0,sizeof(Node));//初始化该片内存
        head->NData ++;//链表计数+1
        pnodex = pnodex->NextN;//浮标指向新节点
        pnodex->NData = 'x';//新节点数据赋值
        pnodex->NextN = NULL;//重定义链表尾
        //再加一个节点
        pnodex->NextN = (PNode)malloc(sizeof(Node));//申请内存空间，并连接到链表末尾
        memset(pnodex->NextN,0,sizeof(Node));//初始化该片内存
        head->NData ++;//链表计数+1
        pnodex = pnodex->NextN;//浮标指向新节点
        pnodex->NData = 'y';//新节点数据赋值
        pnodex->NextN = NULL;//重定义链表尾

        //遍历每个节点
        pnodex = head;
        while(pnodex->NextN != NULL)
        {
                printf("%p:%d,next %p\n",pnodex,pnodex->NData,pnodex->NextN);
                pnodex = pnodex->NextN;//移到下个节点！有别于数组的移动
        }
        printf("%p:%d,next %p\n",pnodex,pnodex->NData,pnodex->NextN);//输出最后一个节点
        getchar();
}

yundi 发表于 2016-7-1 10:59:31

本帖最后由 yundi 于 2016-7-3 00:41 编辑

接下来就是考虑该如何封装了！初始化、销毁链表，节点的增删改查，这些功能一个都不能少。

/* c 链表数据结构 1.3 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//节点结构
struct _tagNode
{
      int NData;//数据
      struct _tagNode * NextN;//节点指针，指向下一个结构
};

typedef struct _tagNode Node, * PNode, * Link;//加上一个Link类型

//1.封装添加节点
void CreateNode(Link * phead,PNode * ppn,int data)
        //因为要改变函数外部数据，所以参数用到指针
{
        (* ppn)->NextN = (PNode)malloc(sizeof(Node));
        memset((* ppn)->NextN,0,sizeof(Node));
        (*phead)->NData ++;
        (* ppn) = (* ppn)->NextN;
        (*ppn)->NData = data;
        (*ppn)->NextN = NULL;
        return ;
}

//2.删除节点
void DeleteNode(Link * phead,PNode * ppn,int data)
{
        //遍历链表，找到浮标所指的节点，将其前后节点连接，最后free浮标所指节点
        //代码略
}

int main()
{
        int i;
    Node linkhead;//链表！头节点
    Link head = &linkhead ;//链表！固定一个指向链表头的指针。
    PNode pnodex = head;//浮标，在节点间移动，初始指向头结点。
    head->NData = 0; //设数据为0，可用来保存链表长度,
    head->NextN = NULL;//下节点为NULL
    //添加节点
        for(i=0;i<10;i++)
        {
                CreateNode(&head,&pnodex,i);
        }
    //遍历每个节点
    pnodex = head;
    while(pnodex->NextN != NULL)
    {
            printf("%p:%d,next %p\n",pnodex,pnodex->NData,pnodex->NextN);
            pnodex = pnodex->NextN;//移到下个节点！有别于数组的移动
    }
    printf("%p:%d,next %p\n",pnodex,pnodex->NData,pnodex->NextN);//输出最后一个节点
    getchar();
}

上面仅仅对链表增加节点进行了封装，对链表的定义、浮标的移动等都是在main中进行，这种所谓的封装对调用者不透明，还必须写代码处理链表内部细节。经过再次琢磨，列出了下面的封装函数。

Link CreateLink();
void DestoryLink(Link * plink);
PNode CreateNode(int data);
void ChangeNode(PNode pnode,int data);
int InsertNode(Link * plink,int index,PNode pnodez);
int DeleteNode(Link * plink,int index);
PNode GetNodeById(Link * plink,int index);
int CountNode(Link * plink);
void SortLink(Link * plink,int );

我目前最大的问题就是不知道什么时候用什么方式封装，总觉得这样也可以、那样也行，代码写着写着就迷了方向。但是，当意识到封装的意义就是让代码更符合人的直观思维时，我突然觉得自己开悟了。例如：在main中写Node linkhead;Link head = &linkhead;是创建链表，但封装后改为Link myLink = CreateLink();就直观得多，所以，封装就是把代码整理成自己最容易理解的样子！再进一步理解，c虽然封装了函数，但仍然和数据是分离的，如链表变量和对链表的操作分离，与人的直观思维还是有差距，于是就出现了面向对象、类、c++这些。

zndownload 发表于 2017-1-1 14:47:25

这个不错！能不能再完整些！

查看完整版本: 复习链表数据结构