单链表的基本操作（学习总结）
单链表的声明初始化：
1.头文件：
这里不做太多说明，是学习C语言的基础。
#include
#include 2.结构声明：
数据结构算法中，每个表，树，图类的工具组都需要定义它的结构来符合我们的需求。
例如本次的单链表：
这里的 Lnode和*Linklist(指针型)是结构体的不同表达方式，二者都可任意使用，例如：Lnode *H=Linklist H
typedef struct Lnode{int data;struct Lnode *next;
}Lnode,*Linklist; 结点结构：
一、单链表的创建
单链表的创建有头插和尾插两种方式，默认单链表都均有头结点。
1.头插法：
思路：申请头节点并置空（NULL）；依次读入元素，如果不是结束符（可任意自定）则申请结点，将新结点插在头节点之后。但是，此类方法插入的元素与输出的顺序相反。
//单链表的创建(头插法)void CreateLB1(Linklist &L){ Linklist p;int n,num; L = (Linklist)malloc(sizeof(Lnode)); //创建链表的头节点 L->next=NULL; //头结点置空 printf("请输入要创建的元素个数： ");int x=scanf("%d",&n); //int x判断类型是否正确 if(x==0){printf("输入元素类型错误!!");}for(int i=0;idata = num; //把输入的元素赋值给结点 p->next = L->next; L->next = p; //链接结点 }printf("创建成功！\n");
} 2.尾插法：
思路：申请头节点并置空（NULL）；设置两个指针（头指针和尾指针）都指向头结点，依次输入元素；申请新结点将新结点插入尾指针的后面，在移动尾指针指向新结点。（与头插法类似，在此只简单说明问题）
//单链表的建立（尾插法）
void Create(Linklist &L){L=(Linklist)malloc(sizeof(Lnode));L->next=NULL;Lnode *s,*p=L;int n,num;printf("请输入要创建的个数:");scanf("%d",&num);for(int i=1;i<=num;i++){printf("请输入第%d个元素的值:",i);scanf("%d",&n);s=(Linklist)malloc(sizeof(Lnode));s->data=n;p->next=s;p=s;p->next=NULL;}printf("创建成功！\n");
} 运行结果：
二、单链表的查找
链表查找分为按值查找和按序号查找。
1.按序号（常用）
思路：从链表第一个元素结点起判断当前结点是否为第k个，若是则返回该结点的指针，否则继续查找下一个，直到结束。
//单链表的查找（按序号）successLinklist Find2(Linklist L,int num){Linklist p=L;int j=0; //定义一个计数器 while(p->next!=NULL&&jnext;j++;} if(j==num){ //找到位置 return p;}else{printf("error-查找失败！");}} 在此可以将 num的值设置为用户自行输入的值，但是后面用到的删除和插入需要调用调用此方法，所以常用。
2.按值查找
思路：从链表的第一个元素结点起，判断当前结点的值是否等于你需要查找的值，若是返回该结点指针，否则继续向后查找，直到结束。
//查找结点 successint Search(Linklist L){Lnode *p=L;int i=1; //哨兵 int a=0; //需要查找的值 int j=0; //值所在的位置 printf("请输入需要查找的元素："); scanf("%d",&a); while(p->next){p=p->next;if(a==p->data){j=i;printf("找到与%d相等的元素，位置为：%d",a,j);return 1;}i++; }printf("未找到！！");return -1;} 运行如下：
三、单链表的插入：
①：s->next=p->next; 先1的目的是保存后边的结点数据，以免丢失。
②:p->next=s;
思路：
- 查找需要插入位置的前一个结点。
- 创建新结点。
- 新结点的next域指向第i个结点。
- 第i-1个结点指向新结点。
//插入元素 int Insert(Linklist &L){Lnode* p;int data,place;int flag=1;printf("请输入你要插入的元素：\n");scanf("%d",&data);printf("请输入你要插入的位置:\n");scanf("%d",&place);p=Find2(L,place); //此处调用前面的序号查询 if(p==NULL){printf("位置错误！");return -1;}else{Lnode *H=(Lnode *)malloc(sizeof(Lnode));H->data=data;H->next=p->next;p->next=H;printf("插入成功！\n");}} 运行结果：
四、单链表的删除
①：q->next=p->next;
②:free(p); //此处是解放空间的意思
思路：
- 查找第i-1的序号,存在就继续进行。
- 若存在第i个结点。
- 第i-1个结点的next域指向结点i+1。
- 释放第i个结点。
//删除元素int Delate(Linklist &L){Linklist p,H;int num;printf("请输入要删除的元素序号：\n");scanf("%d",&num);p=Find2(L,num-1);H=Find2(L,num);if(p==NULL){printf("删除错误，该结点已为空值！");return -1; }else{p->next=H->next;free(H);printf("删除成功！");return 1;}} 运行如下：
删除操作同样也可以将查找定义为查找值操作，在此不多叙述。
五、单链表的逆置
思路：依次取原链表中的每个结点，将其作为第一个结点插入新链表中（头插法）
//单链表的逆置void Reverse(Linklist &L) {Lnode *p,*q;p=L->next; //p指向第一个数据结点 L->next=NULL; //将原表设置为空 while(p!=NULL){q=p;p=p->next; //这里的p->next必须在赋给q值后进行，为的是不让后面的数据丢失。 q->next=L->next; //将当前结点插入头结点后面 L->next=q;}printf("逆置成功！\n"); }运行如下：
六、删除重复的结点
思路：用指针p指向第一个结点，从他的直接后继开始找与其值相同的结点，找到后将该结点删除；p在指向下一个结点，以此类推。
//删除重复的结点void DelateOver(Linklist &L){Lnode *p,*q,*r;p=L->next; //p指向第一个结点 if(p!=NULL)while(p->next){q=p;while(q->next!=NULL){ //从p的后继开始查找 if(q->next->data==p->data){ //找到并删除 r=q->next;q->next=r->next;free(r);}else{q=q->next;}}p=p->next; //p继续遍历 } } 运行如下：
七、求差集
思路：在A中有的B没有就是差集。因此，对于A的元素在B中依次查找，若存在则从A中删除。
//求差集 void Add(Linklist &A,Linklist B) {Lnode *p,*q,*pre,*r;pre=A; //删除元素需要的前驱 p=A->next;q=B->next;while(p){while(q&&q->data!=p->data){ //扫描B中的元素 q=q->next;}if(q){ //删除操作 r=p;pre->next=r->next;p=p->next;free(r);}else{pre=p; //指针移动 p=p->next;}} }运行如下：
八、*和&的理解
1.若要改变实参中的值就用&，表引用；对形参的改变相应的改变实参。（传参调用）
2.不加&则形参是实参的副本，改变形参的值不影响形参。（传值调用）
我的理解是，如果要改变形参中的值 例如：创建，删除，插入一类有明显的变化 则需要加&；
像查找，求表长等这一类不需要改变表中的元素则可以不加&。
&也可以当作取地址符，在其他教材中有“引用”这个名词来解释，
int a=2;
Triple(a); //这里的函数表明将a的值扩大三倍
printf(a); //不加引用表示 a=2进去，a变成6，然而输出的a还是2int a=2;
Triple(&a); //这里的函数表明将a的值扩大三倍
printf(a); //加引用表示 a=2进去，a变成6，输出的a就是6总结：本人一点拙见，希望大家给予建议和鼓励，共同进步。
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！