复习链表数据结构

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

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

本帖最后由 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[10];//定义了十个节点
int i;
PNode pnodex;//定义一个节点指针变量
for(i=0;i<10;i++)
{
nodes[i].NData = i;
if(i!=9){
nodes[i].NextN = &nodes[i+1];
}else{
nodes[i].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

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

账号		自动登录	找回密码
密码			立即注册

[技术交流] 复习链表数据结构

马上注册，结交更多好友，享用更多功能^_^