赞
踩
数据结构继续学习,这次进行,双链表的学习。
提示:以下是本篇文章正文内容,下面案例可供参考
双链表是在单链表的基础上拓展出来的,单链表是一个结点中包含两部分,分别是数据和下一个结点的指针。
而双链表则是一个结点包含三个部分,分别是结点存储的数据,结点的下一个结点骶椎的指针,和结点的上一个结点的位置的指针。
双链表的结构体相比于单链表,实际上就是多了一个前一个结点的指针,其余并没有变化,还是数据和下一个结点的指针。
typedef struct Node
{
int data;
struct Node* pre;
struct Node* next;
}Node;
所谓初始化就是定义一个头节点,将其中所容纳的数据定义为链表的长度,并作出两个空指针。
//初始化
Node* init(){
Node* node=(Node*)malloc(sizeof(Node));
node->pre=NULL;
node->next=NULL;
node->data=0;
return node;
}
头插法,一如既往的将新数据插入到头节点后面。
步骤:
1. 初始化一个结点,并将数据赋值给结点的data
2. 将结点的next指针指向头节点的next的结点,并将pre指针指向头节点
3. 将头节点的next更正为当前结点的指针。
4. 将头节点中的数据+1,意为链表的长度+1
//头插法
void head_insert(Node* node,int data){
Node* curnode = (Node*)malloc(sizeof(Node));
curnode->data=data;
curnode->pre = node;
curnode->next = node->next;
node->next=curnode;
node->data++;
}
尾插法总是比头插法难一点,双链表也不例外
尾插法就是将数据插入到链表的尾部,然后将链表的长度+1
步骤:
1. 初始化两个结点,一个结点作为当前结点用来存储新的数据,另一个结点用来循环
2. 对用来循环的结点进行循环,在循环中判断结点的next指针是否为空,为空说明当前结点已经到了单链表的尾部。
3. 此时,将数据赋予新的结点,并将循环的结点的next指向新的结点,同时新的结点的前置指针指向循环结点。
4. 链表的长度+1.
//尾插法 void tail_insert(Node* node,int data){ Node* prenode = node->next; Node* curnode=(Node*)malloc(sizeof(Node)); curnode->data = data; while(prenode){ if(prenode->next==NULL){ curnode->pre = prenode; curnode->next= NULL; prenode->next = curnode; node->data++; break; } prenode=prenode->next; } }
删除结点的步骤基本上和单链表没有区别,只是多了一个pre指针的指向。
1. 删除的过程中,首先初始化两个指针,指针1用来辅助,指针2用来循环和判断。
2. 对指针2进行循环,同时一直保持指针1在指针2的前一个结点,当指针2的data等于要删除的数据时,将指针1指向当前结点的next,并让指针2的next的pre指针指向指针1。(其中可以增加一个指针2的next是否为空的情况)
3. 当判定到指针2的next指针为空时,结束循环,说明链表中并不存在该数据
4. 链表的长度-1
//删除 void delete(Node* node , int data){ Node* prenode = (Node*)malloc(sizeof(Node)); Node* curnode = (Node*)malloc(sizeof(Node)); prenode = node; curnode = node->next; while(curnode){ if(curnode->data==data){ prenode->next = curnode->next; curnode->next->pre = prenode; node->data--; break; } if(curnode->next==NULL){ break; } } }
双链表遍历就真的和单链表如出一辙了,感觉真的是一点变化都没有的那种。
步骤:
1. 和单链表一样,首先初始化一个结点用来遍历
2. 将首元结点赋给刚创建的结点,然后对利用该节点对链表进行循环输出,直到到达链表的尾部。
//遍历
void print(Node* node){
Node* curnode = (Node*)malloc(sizeof(Node));
curnode = node->next;
while(curnode){
printf("%d\n",curnode->data);
curnode = curnode->next;
}
}
双链表和单链表也基本一样的了,就是多了一个结点的pre指针指向。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。