数据结构之链表(一)

数据结构中主要有三种数据形式,链表,树,图。其中链表是线性结构,其他的两种是非线性结构。

这里先从链表说起。

无论是哪种数据结构,都是由节点构成的。节点可以称之为,其基本单位。因而,一般写程序时。都先用结构体来定义一个节点。链表节点如下:

typedef struct NodeNODE,*PNODE;

但是,链表为方便程序员对其操作,创建了头节点。该节点只有地址没有数据,也就是说该节点只起到指向下个节点的作用。下个节点为首节点。该节点有数据,有地址(指针),与其他的有效节点一样。是链表数据链真正开始的标志。这里我用了数据链这个辞藻,在我的浅知拙见里是比较恰当的。尾节点是链表结束的标志因而尾节点只有数据,并没有地址(指针)。

因为头节点的存在,我们需要一个参数---头指针,就可以对链表操作了。

链表又分为了单链表,双链表,循环链表。。。这里只介绍最常见的单链表了。

关于链表,主要有以下几个难点以及重点:

链表的创建和遍历

链表长度的判断

链表是否为空,为满的判断

链表插入和删除

接下来,逐步进行介绍。

1)静态链表的创建:

静态链表的创建主要涉及到三个参数:len-用来设定有效节点个数;int--用于设定循环次数,来输入各个节点的数据,val-输入节点的值。动态链表的节点个数,无需事先指定。其链表创建直到达到某种条件时结束创建。

静态链表创建的示例程序如下:

PNODE creat_list(void){int len;int i;int val;//用于存放节点临时数据PNODE pHead = (PNODE)malloc(sizeof(NODE));//为头节点指针分配一个内存空间if (NULL == pHead){printf("分配失败,程序终止!\n");exit(-1);}PNODE pTail = pHead;//分配一个尾节点 ,指向头节点pTail 指向pHeadpTail->pNext = NULL;//将尾节点的指针域 清空printf("输入链表节点数:\n");scanf_s("%d", &len);

for (i = 0; i data = val;// pTail->pNext = pNew;//将新的节点挂到尾节点后面, pNew->pNext = NULL; //再将此时的新节点指针域清空 pTail = pNew; //然后再将pTail指向pNew}return pHead;}

程序有几个地方要注意的地方:

这里先为头节点动态分配一个内存。只允许程序员手动释放。这里有个问题,剩下的节点也是按照动态来分配的吗?

接下来判断头节点,判断是否为空。若空,则说明分配失败。后面还有涉及到,对某节点的指针来判断是否为空。这个问题后面再详述其区别。这里可以用:assert(pHead != NULL);来判断其是否为空。

然后再创建尾节点,将头节点指针也赋尾节点指针。同样动态创建?再将尾节点的指针(地址域)清空。确定尾节点。

接下来,循环创建。

先动态创建一个临时节点,备用。

最重要的四行来了!!

第一行,将节点值赋给新节点的数据域。

然后将尾节点指向临时节点,也就是说将临时节点挂到尾节点(也是头节点没有指针域那个节点)后面。

再将临时节点的指针域清空。此时,临时节点暂为 尾节点。

这里尾节点又指向临时节点。也就是说这里,临时节点彻底变成了尾节点。因为,这意味着现在的尾节点彻底有了含义!成为了有效数据。以下的节点构造同理。

2)链表的遍历

遍历的程序是比较容易理解的。示例程序如下:

void traverse_list(PNODE pHead){PNODE p = pHead->pNext;//将头指针指针域赋给pwhile (NULL != p) //当指针域不为空的时候,也就是不是尾节点的时候,继续{printf("%d\n", p->data);//打印该节点的数据p = p->pNext; //指针下移,指向下一个节点}printf("\n"); //换行return;}

这里借助指针p来不断下移打印数据,不可将p直接改为p->pHead。因为这样的话,只能打印第一个有效节点了。这里出过错。

————————————————————————————————

解释那四句话的时候,终于感受到了,想说说不出来的难受!!

补充一点:堆和栈都是动态存储。先写在这里,后面,写栈的时候再补上。

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180315G0YFD700?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券