一流的常州网站建设,微信微网站教程,江西省网站开发,缙云企业网站建设单向循环链表单向循环链表是一种特殊的单向链表#xff0c;尾节点的指针指向头节点#xff0c;形成一个闭环。适用于需要循环访问的场景#xff0c;如轮询调度。结构特点#xff1a;每个节点包含数据域和指向下一个节点的指针#xff0c;尾节点的指针指向头节点而非空值。…单向循环链表单向循环链表是一种特殊的单向链表尾节点的指针指向头节点形成一个闭环。适用于需要循环访问的场景如轮询调度。结构特点每个节点包含数据域和指向下一个节点的指针尾节点的指针指向头节点而非空值。操作复杂度插入/删除头节点O(1)插入/删除尾节点O(n)需遍历到尾部代码示例C
struct Node {int data;Node* next;Node(int val) : data(val), next(nullptr) {}
};
双向链表双向链表的每个节点包含前驱和后继指针支持双向遍历但需要更多内存存储指针。结构特点节点包含前驱指针prev、数据域和后续指针next。操作复杂度任意位置插入/删除O(1)已知前驱节点时按值查找O(n)代码示例C
struct DNode {int data;DNode* prev;DNode* next;DNode(int val) : data(val), prev(nullptr), next(nullptr) {}
};作业 1.双向链表的部分操作
#include linklist.hint main(int argc, const char *argv[])
{//定义一个头linklistptr headptrNULL;//定义循环变量int i;//定义位置变量int seat;//头的初始化headptrLinklistHeadnodeApply();//定义新输入数据datatype nwedata;//循环输入数据for(i0;i5;i){puts(请输入一个数);scanf( %d,nwedata);//调用双向链表的头插函数LinklistHeadinsert(headptr,nwedata);}//调用双向链表的遍历函数nextLinklistShownext(headptr);//调用双向链表的遍历函数frontLinklistShowfront(headptr);//循环输入数据for(i0;i5;i){puts(请输入一个数);scanf( %d,nwedata);//双向链表的尾插函数LinklistTailinsert(headptr,nwedata);}//调用双向链表的遍历函数nextLinklistShownext(headptr);//调用双向链表的头删函数LinklistHeaddelete(headptr);//调用双向链表的遍历函数nextLinklistShownext(headptr);//调用双向链表的尾删函数LinklistTaildelete(headptr);//调用双向链表的遍历函数nextLinklistShownext(headptr);//分别输入位置和新数据puts(输入想插入的位置);scanf( %d,seat);puts(输入想插入的数据);scanf( %d,nwedata);//调用双向链链表按位置插入函数LinklistSeatinsert(headptr,seat,nwedata);//调用双向链表的遍历函数nextLinklistShownext(headptr);//输入位置puts(输入想删除的位置);scanf( %d,seat);//调用双向链链表按位置插入函数LinklistSeatdelete(headptr,seat);//调用双向链表的遍历函数nextLinklistShownext(headptr);//分别输入位置和新数据puts(输入想要修改的位置);scanf( %d,seat);puts(输入想改成的数据);scanf( %d,nwedata);//调用双向链链表按位置修改函数LinklistSeatalter(headptr,seat,nwedata);//调用双向链表的遍历函数nextLinklistShownext(headptr);//输入位置puts(输入想查找的位置);scanf( %d,seat);//调用双向链链表按位置查找函数LinklistSeatsift(headptr,seat);return 0;
}#ifndef _LINKLIST_H__
#define _LINKLIST_H__#include stdio.h
#include string.h
#include stdlib.h
#include math.h//返回值枚举
enum returntype
{//失败返回FAULSE-1,//成功返回SUCCESS
};//存储数据类型
typedef int datatype;//双向链链表结构体
typedef struct Node
{//数据域共用体union{//头节点数据域int len;//普通节点数据域datatype data;};//前向指针域struct Node *front;//后向指针域struct Node *next;
}linklist,*linklistptr;//头节点堆区申请函数
linklistptr LinklistHeadnodeApply(void);//普通节点堆区申请函数
linklistptr LinklistComnodeApply(datatype nwedata);//双向链表的头插函数
int LinklistHeadinsert(linklistptr headptr,datatype nwedata);//双向链表的遍历函数next
int LinklistShownext(linklistptr headptr);//双向链表的遍历函数front
int LinklistShowfront(linklistptr headptr);//双向链表的尾插函数
int LinklistTailinsert(linklistptr headptr,datatype nwedata);//双向链表的头删函数
int LinklistHeaddelete(linklistptr headptr);//双向链表的尾删函数
int LinklistTaildelete(linklistptr headptr);//双向链链表按位置插入函数
int LinklistSeatinsert(linklistptr headptr,int seat,datatype nwedata);//双向链链表按位置删除函数
int LinklistSeatdelete(linklistptr headptr,int seat);//双向链链表按位置修改函数
int LinklistSeatalter(linklistptr headptr,int seat,datatype nwedata);//双向链链表按位置查找函数
linklistptr LinklistSeatsift(linklistptr headptr,int seat);#endif
#include linklist.h//头节点堆区申请函数
linklistptr LinklistHeadnodeApply(void)
{//头节点堆区申请linklistptr headptr(linklistptr)malloc(sizeof(linklist));//判断申请是否成功if(headptrNULL){return NULL;}//初始化headptr-len0;headptr-frontNULL;headptr-nextNULL;return headptr;
}//普通点堆区申请函数
linklistptr LinklistComnodeApply(datatype nwedata)
{//普通节点堆区申请linklistptr comptr(linklistptr)malloc(sizeof(linklist));//判断申请是否成功if(comptrNULL){return NULL;}//初始化comptr-datanwedata;comptr-frontNULL;comptr-nextNULL;return comptr;
}//双向链表的头插函数
int LinklistHeadinsert(linklistptr headptr,datatype nwedata)
{//定义普通节点指针linklistptr comptrNULL;//判断是否为nullif(headptrNULL){return FAULSE;}//普通节点申请comptrLinklistComnodeApply(nwedata);//申请判断if(comptrNULL){return FAULSE;}//头插comptr-nextheadptr-next;comptr-frontheadptr;//判断是否为首个数据if(headptr-next){headptr-next-frontcomptr;}headptr-nextcomptr;//个数自增headptr-len;return SUCCESS;
}//双向链表的遍历函数next
int LinklistShownext(linklistptr headptr)
{//定义链表指针linklistptr ptrNULL;//定义循环变量int i;//判断是否为null//判断链表是否为空if(headptrNULL||headptr-len0){return FAULSE;}//输出ptrheadptr-next;puts(正序链表现有数据);while(ptr){printf(%d ,ptr-data);ptrptr-next;}putchar(10);return SUCCESS;
}//双向链表的遍历函数front
int LinklistShowfront(linklistptr headptr)
{//定义链表指针linklistptr ptrNULL;//定义循环变量int i;//判断是否为NULL//判断链表是否为空if(headptrNULL||headptr-len0){return FAULSE;}//找尾部ptrheadptr-next;while(ptr-next){ptrptr-next;}//输出puts(逆序链表现有数据);while(ptr!headptr){printf(%d ,ptr-data);ptrptr-front;}putchar(10);return SUCCESS;
}//双向链表的尾插函数
int LinklistTailinsert(linklistptr headptr,datatype nwedata)
{//定义链表指针和普通节点指针linklistptr ptrNULL,comptrNULL;//判断头是否为nullif(headptrNULL){return FAULSE;}//找尾部ptrheadptr;while(ptr-next){ptrptr-next;}//初始化普通节点comptrLinklistComnodeApply(nwedata);//判断申请是否成功if(comptrNULL){return FAULSE;}//尾插ptr-nextcomptr;comptr-frontptr;//个数自增headptr-len;return SUCCESS;
}
//双向链表的头删函数
int LinklistHeaddelete(linklistptr headptr)
{//定义链表指针和将删节点指针linklistptr deltrNULL,ptrNULL;//判断头是否为nullif(headptrNULL||headptr-len0){return FAULSE;}//找到要删除的数据第一个节点deltrheadptr-next;//头删headptr-nextdeltr-next;//判断是否只有一个节点if(deltr-next){deltr-next-frontheadptr;}free(deltr);deltrNULL;//个数自减headptr-len--;return SUCCESS;
}//双向链表的尾删函数
int LinklistTaildelete(linklistptr headptr)
{//定义链表指针和将删节点指针linklistptr deltrNULL,ptrNULL;//判断头是否为nullif(headptrNULL||headptr-len0){return FAULSE;}//找尾部ptrheadptr;while(ptr-next){ptrptr-next;}ptr-front-nextNULL;free(ptr);ptrNULL;headptr-len--;return SUCCESS;
}//双向链链表按位置插入函数
int LinklistSeatinsert(linklistptr headptr,int seat,datatype nwedata)
{//定义循环变量int i;//定义链表指针和普通节点指针linklistptr ptrNULL,comptrNULL;//判断头是否为NULL//判断位置是否合法if(headptrNULL||seat0||seatheadptr-len1){return FAULSE;}//找到对应位置的前一个位置ptrheadptr;for(i0;iseat-1;i){ptrptr-next;}//初始化普通节点comptrLinklistComnodeApply(nwedata);//if(comptrNULL){return FAULSE;}//插入comptr-nextptr-next;comptr-frontptr;if(ptr-next!NULL){ptr-next-frontcomptr;}ptr-nextcomptr;headptr-len;return SUCCESS;
}//双向链链表按位置删除函数
int LinklistSeatdelete(linklistptr headptr,int seat)
{//定义循环变量int i;//定义链表指针和将删节点指针linklistptr deltrNULL,ptrNULL;//判断是否为NULL//判断链表是否为空//判断位置是否合法if(headptrNULL||headptr-len0||seat0||seatheadptr-len){return FAULSE;}//找到对应位置的前一个位置ptrheadptr;for(i0;iseat-1;i){ptrptr-next;}deltrptr-next;ptr-nextdeltr-next;if(deltr-next!NULL){deltr-next-frontdeltr-front;}free(deltr);deltrNULL;headptr-len--;return SUCCESS;
}//双向链链表按位置修改函数
int LinklistSeatalter(linklistptr headptr,int seat,datatype nwedata)
{//定义循环变量int i;//定义链表指针linklistptr ptrNULL;//判断是否为NULL//判断链表是否为空//判断位置是否合法if(headptrNULL||headptr-len0||seat0||seatheadptr-len){return FAULSE;}//找到对应位置ptrheadptr;for(i0;iseat;i){ptrptr-next;}ptr-datanwedata;return SUCCESS;
}//双向链链表按位置查找函数
linklistptr LinklistSeatsift(linklistptr headptr,int seat)
{//定义循环变量int i;//定义链表指针linklistptr ptrNULL;//判断是否为NULL//判断链表是否为空//判断位置是否合法if(headptrNULL||headptr-len0||seat0||seatheadptr-len){return NULL;}//找到对应位置ptrheadptr;for(i0;iseat;i){ptrptr-next;}printf(linklist[%d]%d\n,seat,ptr-data);return ptr;
}运行示例2.牛客网刷题
