7-数据结构-（带头节点）单链表的增删改查

问题：

        单链表带头结点的创建以及输出，以及带与不带头节点的区别

思路：

1. 单链表，逻辑上是线性结构，由许多单链表结点，串成一串。其单链表结构体中，数据项由data数据域和结点指针域。
2. 带头节点是为了使在空表时的操作更统一。如果不带头节点，空表插入时，直接让头指针，和第一节点指针相等即可。而非空表插入时，则时s->next=l->next;l->next=s;头插，两个操作。而带上头节点，所有情况下的插入操作，都同意了即都为s->next=l->next;l->next=s。
3. 值得注意的是，带头节点的单链表，遍历输出时，记得从第二哥结点开始遍历，即让结点指针=头指针的指针域。即snode*s =l->next;
4. 在指针改变实际值时，C语言中，要么来哥双指针，要么正常一维指针，最后返回头指针，主函数内接收即可。我觉得为了好理解，就用返回这个吧，整那么花里胡哨，也挺乱的。嗯

头插法：

//创建带头节点的单链表
snode* sheadlist(linklist l,int n)
{snode *phead=l;      phead=(snode*)malloc(sizeof(snode));//创建头节点 phead->next=NULL;  int i=0,x=n,k=0;printf("请输入想要插入的值\n");for(i=0;i<x;i++){printf("输入第%d个值\n",i+1);scanf("%d",&k);snode *p=(snode*)malloc(sizeof(snode));p->data=k;p->next=phead->next;phead->next=p;}return phead;
} 

尾插法：

//创建带头结点尾插法 
linklist srearlist(linklist l,int x)
{snode* phead=l;//创建头节点phead=(linklist)malloc(sizeof(snode));//用头结点创造空间，指针l没有创建，因此返回的时候返回头节点 才能获取整个单链表地址 phead->next=NULL;int i,k;snode *end=phead;//工作指针，从头节点开始工作 printf("请输入值\n");for(i=0;i<x;i++){scanf("%d",&k);snode *p=(snode*)malloc(sizeof(snode));//创建新结点，用来尾插进单链表 p->data=k;end->next=p;//直接给新结点连接起来 end=p;      //因为尾插，所以要时刻知道最后一个结点的位置，因此s指针也跑到新加入的结点p上面. }end->next=NULL;	return phead;//头节点始终指向整个单链表，因此返回头节点地址，用来获取整个字符串 
} 

按位查找，返回结点：

//返回第i个结点指针
snode* Searchnode(snode* phead,int i)
{int count=1;//从有序数据，数组第一个开始计算snode* p=phead->next;if(i==0) return phead;//返回头节点if(i<0) return NULL;  //无效值while(p!=NULL && count != i)  //进行遍历，每一次进行比对，每次遍历指针后移{p=p->next;count++;}return p;	
} 

按值查找，返回位置：（根据不同的情况需求在while判断条件那里改变条件，进而求得想要的位置即可）

//按值查找,查找比x大的，并返回应插入的位置 
int Search_zhinode(snode* phead,int x)
{snode* p=phead->next;int count=1;while(x>p->data){p=p->next;count++;}return count;	
} 

在某个位置插入一个结点：（按位查找的妙用：

(用按位查找找到第i-1个结点，通过这个结点，进行操作)）

//在某个位置插入一个结点 
snode* SInsert(snode* phead,int pos,int x)
{if(pos<1 || pos>SLength(phead)) return NULL;//进行插入操作snode* p=(snode*)malloc(sizeof(snode));p->data=x;//获取第pos-1个位置上的结点，在它后面插入 snode* ppre=Search_weinode(phead,pos-1);p->next=ppre->next;ppre->next=p;return phead;
}

计算带头结点单链表长度：

//计算单链表长度
int SLenth(snode* phead)
{if(phead==NULL) return 0;int count=1;snode* p =phead->next;//从有效数据第一个开始 while(p->next!=NULL){p=p->next;count++;}return count;} 

删除第i个结点：(用按位查找找到第i-1个结点，通过这个结点，进行操作)

//删除第i个结点 
snode* SDelete(snode* phead,int i,int *x)
{if(i<1 || i>SLenth(phead)) return NULL;snode* p =Search_weinode(phead,i-1);snode* q=p->next;*x=q->data;p->next=q->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 *phead=l;      phead=(snode*)malloc(sizeof(snode));//创建头节点 phead->next=NULL;  int i=0,x=n,k=0;printf("请输入想要插入的值\n");for(i=0;i<x;i++){printf("输入第%d个值\n",i+1);scanf("%d",&k);snode *p=(snode*)malloc(sizeof(snode));p->data=k;p->next=phead->next;phead->next=p;}return phead;
} //创建带头结点尾插法 
linklist srearlist(linklist l,int x)
{snode* phead=l;//创建头节点phead=(linklist)malloc(sizeof(snode));//用头结点创造空间，指针l没有创建，因此返回的时候返回头节点 才能获取整个单链表地址 phead->next=NULL;int i,k;snode *end=phead;//工作指针，从头节点开始工作 printf("请输入值\n");for(i=0;i<x;i++){scanf("%d",&k);snode *p=(snode*)malloc(sizeof(snode));//创建新结点，用来尾插进单链表 p->data=k;end->next=p;//直接给新结点连接起来 end=end->next;      //因为尾插，所以要时刻知道最后一个结点的位置，因此s指针也跑到新加入的结点p上面. }end->next=NULL;	return phead;//头节点始终指向整个单链表，因此返回头节点地址，用来获取整个字符串 
} 
//返回第i个结点指针
snode* Search_weinode(snode* phead,int i)
{int count=1;snode* p=phead->next;//从头节点的后继节点开始遍历 if(i==0) return phead;if(i<0) return NULL;//遍历，当值小于查找值时，一直遍历，直到相等，count停止增加，此时便时所找位置处的结点，返回即可， while(p!=NULL && count != i){p=p->next;count++;}return p;	
} 
//按值查找,查找比x大的，并返回应插入的位置 
int Search_zhinode(snode* phead,int x)
{//默认单链表单调递增，因此从头遍历的话，看谁比x大，便找到了，主要画图清楚 snode* p=phead->next;int count=1;while(x>p->data){p=p->next;count++;}return count;	
} void slprintf(snode *s)
{if(s==NULL) 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->data=x;//获取第pos-1个位置上的结点，在它后面插入 snode* ppre=Search_weinode(phead,pos-1);//进行插入操作 p->next=ppre->next;ppre->next=p;return phead;
}
//计算单链表长度
int SLenth(snode* phead)
{if(phead==NULL) return 0;int count=1;snode* p =phead->next;//从有效数据第一个开始 while(p->next!=NULL){p=p->next;count++;}return count;} 
//删除第i个结点 
snode* SDelete(snode* phead,int i,int *x)
{//判断插入合法性 if(i<1 || i>SLenth(phead)) return NULL;//找到删除结点的前驱结点 snode* p =Search_weinode(phead,i-1);//用按位查找，找到后返回前驱结点 //给q删除，因此先让q指针指向删除结点，取出值，随后p的指针域指向q的后继节点，最后给q释放。 snode* q=p->next;*x=q->data;//删除操作 p->next=q->next;free(q);return phead;
}int main()
{//创建头节点 snode* phead;
//	phead=sheadlist(&phead,3);//尾插法建立带头节点单链表 phead=srearlist(phead,5); //打印单链表 slprintf(phead);
//	snode *p=Searchnode(phead,2);//在有序的列表里面（默认有序），插入数值4，单链表仍有序 int pos=Search_zhinode(phead,4);printf("pos=%d\n",pos);//找到需要插入的位置后，进行在pos处的插入操作——即找到pos的前驱结点，之后进行插入 phead=SInsert(phead,pos,4);slprintf(phead);//计算单链表的长度 int len=SLenth(phead);printf("单链表长度为%d\n",len);//删除第4个结点，并返回删除结点的数值 int x=0;phead=SDelete(phead,4,&x);//因为需要给删除数值带回来，所以给x的地址传过去 printf("删除了%d\n",x);slprintf(phead);return 0;}