共享ip服务器做网站,做网站建设业务,医疗器械管理软件,创建网站开发公司目录 链表
单向链表
单向循环链表
双向链表 设计表 初始化 在auchor后插入节点#xff0c; 在auchor前插入节点 删除节点 传统链表 通过使用链表我们可以将一个数组中的数据分开到不同位置存放并使用指针指向他们#xff0c;使之逻辑相连#xff0c;解决了顺序存储所需要…目录 链表
单向链表
单向循环链表
双向链表 设计表 初始化 在auchor后插入节点 在auchor前插入节点 删除节点 传统链表 通过使用链表我们可以将一个数组中的数据分开到不同位置存放并使用指针指向他们使之逻辑相连解决了顺序存储所需要一大块内存的问题同时删除插入和扩展节点非常便利。为此我们需要在定义链表时预留一个指针指向其他数据存放的地址使得节点逻辑连贯根据不同情况我们可以设置单向或者双向指针
单向链表 单向链表指的就是节点中只包含一个指针该指针用来指向相邻节点。对链表的操作最基本的就是初始化空链表、创建新节点、插入节点、删除节点、移动节点、查找节点和遍历链表下面先给出节点的设计代码然后针对以上所述的操作各个击破。 第一设计节点 节点的设计非常重要关乎后续对链表各种操作而单向循环链表节点的设计就非常简单假设我们要处理的数据类型叫datatype我们只需要在节点中增加一个指向本节点类型的指针即可
typedef struct node
{int data;struct node *next;
}listnode,*singly_list; 第二初始化 空链表分为有头节点的空链表和不带头节点的空链表在不带有头节点的空链表情况下插入时要先判断头节点是否为空因此我们一般更倾向于创建带有头节点的空链表创建函数如下
singly_list init_list (void)
{singly_list mylist malloc(sizeof(listnode));if(mylist ! NULL){mylist-next NULL;}return mylist;
} 第三插入节点 链表最大的又是就是插入删除非常简单单向链表中插入节点只需要修改两个指针将新节点指向插入位置后一个节点将前一个节点指向新节点
void insert_node(singly_list p,singly_list new)
{if(p NULL || new NULL)return;new-next p-next;p-next new;
}第四删除节点 对于单向链表来说没有指向前置节点的指针因此我们要先创建一个指针寻找到前置指针然后再进行删除 bool remove_node(singly_list mylist,singly_list delete)
{if(is_empty(mylist))return false;singly_list p mylist;while (p ! NULL p-next ! delete){p p-next;}if(p NULL)return false;p-next delete-next;delete-next NULL;return true;
} 第五移动节点 因为我们在前面已经将插入和删除封装进了函数因此我们移动节点将会很简便
void move_node(singly_list mylist , singly_list p , singly_list anchor)
{if(mylist NULL || p NULL || anchor NULL)return ;remove_node(mylist,p);insert_node(anchor,p);
} 第六根据内容查找指针 singly_list remove_node(singly_list mylist,int data)
{if(is_empty(mylist))return NULL;singly_list p;// p mylist;// while (p ! NULL p-next-data ! data)// {// p p-next;// }// if(p NULL)// return false;// p p-next;for(p mylist-next ; p ! NULL ; p p-next){if (p-data data){break;}}return p;
}用了两种方法逻辑相同酌情使用 单向循环链表 所谓单线循环链表就是单向链表中最后一个节点指向头节点,初始化方式如下
linklist init_list (void)
{linklist head malloc(sizeof(listnode));head-next head;return head;
} 删除节点对于单向循环链表来说不是必须指定头节点可以直接从需要删除的节点开始轮询
void remove_node(linklist delete)
{linklist temp delete;while (temp-next ! delete){temp temp-next;}temp-next delete-next;delete-next NULL;
}移动节点相比于单链表循环链表不需要从头节点开始轮询所以可以减少参数
void move_node(linklist p , linklist anchor)
{if(p NULL || anchor NULL)return ;remove_node(p);insert_node(anchor,p);
} 查找节点查找节点方面循环列表跟单链表的区别就是判断查找结束的条件不同
linklist find_node(linklist mylist,int data)
{if(is_empty(mylist))return NULL;linklist p;for(p mylist-next ; p ! mylist ; p p-next){if (p-data data){break;}}return p mylist ? NULL : p;
} 双向链表 设计表 相较于单链表来说双向链表多了一个指向前一个节点的指针
typedef struct node
{int data;struct node *next;struct node *prev;
}listnode,*double_list; 初始化 比单链表多一个指向自己的指针
double_list init_list (void)
{double_list mylist malloc(sizeof(listnode));if(mylist ! NULL){mylist-prev mylist-next NULL;}return mylist;
} 在auchor后插入节点 在双向链表中需要操作四个指针
void insert_next(double_list new,double_list auchor)
{if(new NULL||auchor NULL);return;new-prev auchor;new-next auchor-next;auchor-next new;new-next-prev new;
} 在auchor前插入节点 void insert_prev(double_list new,double_list auchor)
{if(new NULL||auchor NULL);return;new-prev auchor-prev;new-next auchor;new-prev-next new;auchor-prev new;
}删除节点 void remove_node(double_list delete)
{if(delete NULL);return;delete-prev-next delete-next;delete-next-prev delete-prev;delete-next NULL;delete-prev NULL;
}移动节点 分为移动到目标前后
void move_next(double_list p,double_list auchor)
{remove_node(p);insert_next(p,auchor);
}void move_prev(double_list p,double_list auchor)
{remove_node(p);insert_prev(p,auchor);
} 查找节点
double_list find_node(double_list mylist,int data)
{if(is_empty(mylist))return NULL;double_list p;for(p mylist-next ; p ! mylist ; p p-next){if (p-data data){break;}}return p mylist ? NULL : p;
}
传统链表的坏处 传统的双向循环链表概念简单操作方便但存在有致命的缺陷用一句话来概括就是每一条链表都是特殊的不具有通用性。换句话说对于每一种不同的数据所构建出来的传统链表都是跟这些数据相关的所有的链表操作函数也都是数据相关的换一种数据节点则所有的操作函数都需要一一重写编写这种缺陷对于一个具有成千上万种数据节点的工程来说是灾难性的是不可接受的。 简而言之对于每个不同类型的节点我们没办法使用同一套函数操作他们这在大型工程中很不方便 究其原因传统节点不仅包含了表达链表逻辑的指针更包含了某一个具体类型的数据而指针无法跟数据分开于是出现了这样的问题
