济南网站seo技术,神马网站可以做兼职,重庆论坛网站建设,邯郸匿豪网络科技有限公司问题#xff1a; 单链表带头结点的创建以及输出#xff0c;以及带与不带头节点的区别
思路#xff1a;
单链表#xff0c;逻辑上是线性结构#xff0c;由许多单链表结点#xff0c;串成一串。其单链表结构体中#xff0c;数据项由data数据域和结点指针域。带头节点是为…问题 单链表带头结点的创建以及输出以及带与不带头节点的区别
思路
单链表逻辑上是线性结构由许多单链表结点串成一串。其单链表结构体中数据项由data数据域和结点指针域。带头节点是为了使在空表时的操作更统一。如果不带头节点空表插入时直接让头指针和第一节点指针相等即可。而非空表插入时则时s-nextl-next;l-nexts;头插两个操作。而带上头节点所有情况下的插入操作都同意了即都为s-nextl-next;l-nexts。值得注意的是带头节点的单链表遍历输出时记得从第二哥结点开始遍历即让结点指针头指针的指针域。即snode*s l-next;在指针改变实际值时C语言中要么来哥双指针要么正常一维指针最后返回头指针主函数内接收即可。我觉得为了好理解就用返回这个吧整那么花里胡哨也挺乱的。嗯
头插法
//创建带头节点的单链表
snode* sheadlist(linklist l,int n)
{snode *pheadl; phead(snode*)malloc(sizeof(snode));//创建头节点 phead-nextNULL; int i0,xn,k0;printf(请输入想要插入的值\n);for(i0;ix;i){printf(输入第%d个值\n,i1);scanf(%d,k);snode *p(snode*)malloc(sizeof(snode));p-datak;p-nextphead-next;phead-nextp;}return phead;
}
尾插法
//创建带头结点尾插法
linklist srearlist(linklist l,int x)
{snode* pheadl;//创建头节点phead(linklist)malloc(sizeof(snode));//用头结点创造空间指针l没有创建因此返回的时候返回头节点 才能获取整个单链表地址 phead-nextNULL;int i,k;snode *endphead;//工作指针从头节点开始工作 printf(请输入值\n);for(i0;ix;i){scanf(%d,k);snode *p(snode*)malloc(sizeof(snode));//创建新结点用来尾插进单链表 p-datak;end-nextp;//直接给新结点连接起来 endp; //因为尾插所以要时刻知道最后一个结点的位置因此s指针也跑到新加入的结点p上面. }end-nextNULL; return phead;//头节点始终指向整个单链表因此返回头节点地址用来获取整个字符串
}
按位查找返回结点
//返回第i个结点指针
snode* Searchnode(snode* phead,int i)
{int count1;//从有序数据数组第一个开始计算snode* pphead-next;if(i0) return phead;//返回头节点if(i0) return NULL; //无效值while(p!NULL count ! i) //进行遍历每一次进行比对每次遍历指针后移{pp-next;count;}return p;
}
按值查找返回位置根据不同的情况需求在while判断条件那里改变条件进而求得想要的位置即可
//按值查找,查找比x大的并返回应插入的位置
int Search_zhinode(snode* phead,int x)
{snode* pphead-next;int count1;while(xp-data){pp-next;count;}return count;
}
在某个位置插入一个结点按位查找的妙用
(用按位查找找到第i-1个结点通过这个结点进行操作)
//在某个位置插入一个结点
snode* SInsert(snode* phead,int pos,int x)
{if(pos1 || posSLength(phead)) return NULL;//进行插入操作snode* p(snode*)malloc(sizeof(snode));p-datax;//获取第pos-1个位置上的结点在它后面插入 snode* ppreSearch_weinode(phead,pos-1);p-nextppre-next;ppre-nextp;return phead;
}
计算带头结点单链表长度
//计算单链表长度
int SLenth(snode* phead)
{if(pheadNULL) return 0;int count1;snode* p phead-next;//从有效数据第一个开始 while(p-next!NULL){pp-next;count;}return count;}
删除第i个结点(用按位查找找到第i-1个结点通过这个结点进行操作)
//删除第i个结点
snode* SDelete(snode* phead,int i,int *x)
{if(i1 || iSLenth(phead)) return NULL;snode* p Search_weinode(phead,i-1);snode* qp-next;*xq-data;p-nextq-next;free(q);return phead;
} 代码如下
#include stdio.h
#include string.h
#include stdlib.h
//创建带头结点单链表
typedef struct snode
{int data;struct snode *next;
}snode,*linklist;
//创建带头节点的单链表
snode* sheadlist(linklist l,int n)
{snode *pheadl; phead(snode*)malloc(sizeof(snode));//创建头节点 phead-nextNULL; int i0,xn,k0;printf(请输入想要插入的值\n);for(i0;ix;i){printf(输入第%d个值\n,i1);scanf(%d,k);snode *p(snode*)malloc(sizeof(snode));p-datak;p-nextphead-next;phead-nextp;}return phead;
} //创建带头结点尾插法
linklist srearlist(linklist l,int x)
{snode* pheadl;//创建头节点phead(linklist)malloc(sizeof(snode));//用头结点创造空间指针l没有创建因此返回的时候返回头节点 才能获取整个单链表地址 phead-nextNULL;int i,k;snode *endphead;//工作指针从头节点开始工作 printf(请输入值\n);for(i0;ix;i){scanf(%d,k);snode *p(snode*)malloc(sizeof(snode));//创建新结点用来尾插进单链表 p-datak;end-nextp;//直接给新结点连接起来 endend-next; //因为尾插所以要时刻知道最后一个结点的位置因此s指针也跑到新加入的结点p上面. }end-nextNULL; return phead;//头节点始终指向整个单链表因此返回头节点地址用来获取整个字符串
}
//返回第i个结点指针
snode* Search_weinode(snode* phead,int i)
{int count1;snode* pphead-next;//从头节点的后继节点开始遍历 if(i0) return phead;if(i0) return NULL;//遍历当值小于查找值时一直遍历直到相等count停止增加此时便时所找位置处的结点返回即可 while(p!NULL count ! i){pp-next;count;}return p;
}
//按值查找,查找比x大的并返回应插入的位置
int Search_zhinode(snode* phead,int x)
{//默认单链表单调递增因此从头遍历的话看谁比x大便找到了主要画图清楚 snode* pphead-next;int count1;while(xp-data){pp-next;count;}return count;
} void slprintf(snode *s)
{if(sNULL) return NULL; //空表 情况 snode *scan s-next;//因为带头结点第一个结点为头节点所以打印从第二个结点打印因此这里需要注意 while(scan ! NULL) {printf(%d-,scan-data);scan scan-next;} printf(NULL\n);
}
//在某个位置插入一个结点
snode* SInsert(snode* phead,int pos,int x)
{//进行插入操作//创建需要插入的结点给结点赋值 snode* p(snode*)malloc(sizeof(snode));p-datax;//获取第pos-1个位置上的结点在它后面插入 snode* ppreSearch_weinode(phead,pos-1);//进行插入操作 p-nextppre-next;ppre-nextp;return phead;
}
//计算单链表长度
int SLenth(snode* phead)
{if(pheadNULL) return 0;int count1;snode* p phead-next;//从有效数据第一个开始 while(p-next!NULL){pp-next;count;}return count;}
//删除第i个结点
snode* SDelete(snode* phead,int i,int *x)
{//判断插入合法性 if(i1 || iSLenth(phead)) return NULL;//找到删除结点的前驱结点 snode* p Search_weinode(phead,i-1);//用按位查找找到后返回前驱结点 //给q删除因此先让q指针指向删除结点取出值随后p的指针域指向q的后继节点最后给q释放。 snode* qp-next;*xq-data;//删除操作 p-nextq-next;free(q);return phead;
}int main()
{//创建头节点 snode* phead;
// pheadsheadlist(phead,3);//尾插法建立带头节点单链表 pheadsrearlist(phead,5); //打印单链表 slprintf(phead);
// snode *pSearchnode(phead,2);//在有序的列表里面默认有序插入数值4单链表仍有序 int posSearch_zhinode(phead,4);printf(pos%d\n,pos);//找到需要插入的位置后进行在pos处的插入操作——即找到pos的前驱结点之后进行插入 pheadSInsert(phead,pos,4);slprintf(phead);//计算单链表的长度 int lenSLenth(phead);printf(单链表长度为%d\n,len);//删除第4个结点并返回删除结点的数值 int x0;pheadSDelete(phead,4,x);//因为需要给删除数值带回来所以给x的地址传过去 printf(删除了%d\n,x);slprintf(phead);return 0;}
