2019/04/10 10:10

# 双向的循环链表

c语言实现:

#include <stdio.h>
#include <stdlib.h>
//定义节点结构
typedef struct Node {
struct Node *next, *prior;
int data, length;

//初始化链表
}
//获取指定位置的节点
Node *get(RDLinkList list, int position) {
if (position<1 || position > list->length){
return NULL;
}
Node *current;
int index,reverse;
//判断要获取的位置在左边还是右边,从而确定遍历方向,以减少遍历次数
if (position <= (list->length / 2)){
//目标位置小于等于中心位置 从左边开始
index = 1;
current = list->next;//指向首节点
reverse = 0;
}else{
//目标位置大于中心位置 从右边开始
index = list->length;
current = list->prior;//指向终端节点
reverse = 1;
}
//如果下面还有值并且还没有到达指定的位置就继续遍历
while (current != list && position != index){
printf("loop\n");//查看当前循环次数
if (reverse == 1){
current = current->prior;
index -= 1;
}else{
current = current->next;
index += 1;
}
}
if (index == position && current!=list) {
return current;
}
return NULL;
}
//插入一个新节点到指定位置
void insert(RDLinkList list, int data, int position) {
Node *newNode, *pre;
if (position == 1) {
pre = list;
} else {
pre = get(list, position - 1);
}
//判断其位置是否可插入
if (pre == NULL) {
printf("位置非法");
exit(-1);
}
newNode = malloc(sizeof(Node));
newNode->data = data;

newNode->next = pre->next;
newNode->prior = pre;
pre->next = newNode;
newNode->next->prior = newNode;
list->length += 1;
}
//删除某个位置节点
Node * target = get(list,position);
if (target != NULL){
target->prior->next = target->next;
target->next->prior = target->prior;
free(target);
}
list->length-=1;
}

//插入到左边
insert(list,data,1);
}
//插入到右边
insert(list,data,list->length+1);
}
Node *target;
if (left == 1){
target = get(list,1);
} else{
target = get(list,list->length);
}
if (target != NULL){
target->prior->next = target->next;
target->next->prior = target->prior;
free(target);
}
return target;
}
//弹出最左边一个元素
return pop(list,1);
}
//弹出最右边一个元素
return pop(list,0);
}

int main() {
printf("Hello, World!\n");
//查找测试 从右边遍历 只需要遍历两个节点就能找到第9个
if (res != NULL){
printf("%d\n",res->data);
}

//    pop  push测试
return 0;
}


0
0 收藏

0 评论
0 收藏
0