单链表基本操作

1.头插法建立单链表

2.尾插法建立单链表

3.查找结点

3.修改结点

4.插入结点

5.删除结点

本篇只有c语言代码，具体思路讲解请看这篇博客：数据结构-线性结构-单链表

1.头插法建立单链表

#include<stdio.h>#include<stdlib.h>//单链表的结构定义 typedef struct LNode{int data;//data存放结点数据域 struct LNode *next;//指向后继结点的指针 }LNode;//定义单链表结点类型 //头插法建立单链表void createlistF(LNode *&L, int a[], int n){LNode *s;int i;L = (LNode*)malloc(sizeof(LNode));L ->next = NULL;for(i=0;i<n;++i){s = (LNode*)malloc(sizeof(LNode));s ->data = a[i];//下面两句为头插法的关键步骤 s ->next = L ->next;//s所指新结点的指针域next指向L中的开始结点 L ->next = s;//头结点的指针域next指向s结点，使得s成为新的开始结点 }} //打印链表数据 void printfList(LNode *L){LNode *temp = L;int count = 0;printf("表中的元素为:\n");while(temp->next){temp = temp->next;printf("%d\t",temp->data);count++;if(count%5==0){printf("\n");}}printf("\n");}int main(){LNode *L;int n;printf("请输入数组的个数："); scanf("%d",&n);int a[n];printf("请输入数组中的数(用空格分开)：\n");for(int i=0;i<n;++i){scanf("%d",&a[i]);}//测试头插法建立链表createlistF(L,a,n);//查看建立后的链表 printfList(L);return 0;}

运行结果如下：

2.尾插法建立单链表

#include<stdio.h>#include<stdlib.h>typedef struct LNode{int data;//data中存放结点的数据域 struct LNode *next;//指向后继结点的指针 }LNode; //定义单链表结点类型//尾插法建立链表void createlistR(LNode *&L, int a[], int n) //要改变的变量用引用型 {LNode *s,*r;//s用来指向新申请的结点，r之中指向L的终端结点 int i;L = (LNode *)malloc(sizeof(LNode));//申请L的头结点空间 L -> next = NULL;r = L;// r指向头结点，因为此时头结点就是终端结点 for(i=0;i<n;++i)// 循环申请n个结点，来接受数组a中的元素 {s = (LNode*)malloc(sizeof(LNode));// s指新申请的结点 s ->data = a[i];// 用新申请的结点来接受a中的一个元素 r ->next = s;// 用来接纳新结点 r = r ->next;// r指向终端结点，以便于接纳下一个到来的结点 }r ->next = NULL;// 数组a中所有的元素都已经装入链表L中，L的终端结点的指针域置为NULL，L建立完成 } //打印链表数据 void printfList(LNode *L){LNode *temp = L;int count = 0;//计数器printf("表中的元素为:\n");while(temp->next){temp = temp->next;printf("%d\t",temp->data);count++;if(count%5==0)//每5个元素作为一行{printf("\n");}}printf("\n");}int main(){LNode *L;int n;printf("请输入数组的个数："); scanf("%d",&n);int a[n];printf("请输入数组中的数(用空格分开)：\n");for(int i=0;i<n;++i){scanf("%d",&a[i]);}//测试尾插法建立链表 createlistR(L,a,n);//查看建立后的链表 printfList(L);return 0;}

运行结果如下：

3.查找结点

#include<stdio.h>#include<stdlib.h>//单链表的结构定义 typedef struct LNode{int data;//data存放结点数据域 struct LNode *next;//指向后继结点的指针 }LNode;//定义单链表结点类型 //头插法建立单链表void createlistF(LNode *&L, int a[], int n){LNode *s;int i;L = (LNode*)malloc(sizeof(LNode));L ->next = NULL;for(i=0;i<n;++i){s = (LNode*)malloc(sizeof(LNode));s ->data = a[i];s ->next = L ->next;L ->next = s;}} //打印链表数据 void printfList(LNode *L){LNode *temp = L;int count = 0;//计数器printf("表中的元素为:\n");while(temp->next){temp = temp->next;printf("%d\t",temp->data);count++;if(count%5==0)//每5个元素作为一行{printf("\n");}}printf("\n");}//在链表L中查找与e相等的元素，找到的话返回其位置， 否则返回未找到。 int searchElem(LNode *L, int e){LNode *temp = L;int i = 1;int p = 0;while(temp ->next){temp = temp ->next;if(e == temp->data){p = i;printf("找到了与%d相等元素位置为%d\n",e,p);return 1;}i++;}printf("抱歉，没有找到！");return -1;}int main(){LNode *L;int n;printf("请输入数组的个数："); scanf("%d",&n);int a[n];printf("请输入数组中的数(用空格分开)：\n");for(int i=0;i<n;++i){scanf("%d",&a[i]);}createlistF(L,a,n);printfList(L);//测试查找结点 int e;printf("请输入要查找的结点:");scanf("%d",&e);searchElem(L,e);return 0;}

运行结果如下：

4.修改结点

#include<stdio.h>#include<stdlib.h>//单链表的结构定义 typedef struct LNode{int data;//data存放结点数据域 struct LNode *next;//指向后继结点的指针 }LNode;//定义单链表结点类型 //头插法建立单链表void createlistF(LNode *&L, int a[], int n){LNode *s;int i;L = (LNode*)malloc(sizeof(LNode));L ->next = NULL;for(i=0;i<n;++i){s = (LNode*)malloc(sizeof(LNode));s ->data = a[i];s ->next = L ->next;L ->next = s;}} //打印链表数据 void printfList(LNode *L){LNode *temp = L;int count = 0;//计数器printf("表中的元素为:\n");while(temp->next){temp = temp->next;printf("%d\t",temp->data);count++;if(count%5==0)//每5个元素作为一行{printf("\n");}}printf("\n");}// 修改单链表L的第p个位置上的结点 int replace(LNode *L, int p, int e){LNode *temp = L;temp = temp ->next;for(int i=1;i<p;++i){temp = temp ->next;}temp ->data = e;} int main(){LNode *L;int n;printf("请输入数组的个数："); scanf("%d",&n);int a[n];printf("请输入数组中的数(用空格分开)：\n");for(int i=0;i<n;++i){scanf("%d",&a[i]);}createlistF(L,a,n);printfList(L);//测试修改结点 int p,e;printf("请输入要修改的位置和更改后的元素(用空格分开)：\n");scanf("%d %d",&p,&e);replace(L,p,e);//修改后打印链表数据 printfList(L); return 0;}

运行结果如下：

5.插入结点

#include<stdio.h>#include<stdlib.h>//单链表的结构定义 typedef struct LNode{int data;//data存放结点数据域 struct LNode *next;//指向后继结点的指针 }LNode;//定义单链表结点类型 //头插法建立单链表void createlistF(LNode *&L, int a[], int n){LNode *s;int i;L = (LNode*)malloc(sizeof(LNode));L ->next = NULL;for(i=0;i<n;++i){s = (LNode*)malloc(sizeof(LNode));s ->data = a[i];s ->next = L ->next;L ->next = s;}} //打印链表数据 void printfList(LNode *L){LNode *temp = L;int count = 0;//计数器printf("表中的元素为:\n");while(temp->next){temp = temp->next;printf("%d\t",temp->data);count++;if(count%5==0)//每5个元素作为一行{printf("\n");}}printf("\n");}//在链表L的第p个位置上插入元素e void insertElem(LNode *L, int p, int e){LNode *temp = L;int i = 0;while(i<p-1){temp = temp ->next;++i;}LNode *s = (LNode*)malloc(sizeof(LNode)); //创建新结点 s ->data = e;s->next = temp ->next;temp ->next = s;}int main(){LNode *L;int n;printf("请输入数组的个数："); scanf("%d",&n);int a[n];printf("请输入数组中的数(用空格分开)：\n");for(int i=0;i<n;++i){scanf("%d",&a[i]);}createlistF(L,a,n);printfList(L);//测试插入结点 int p,e;printf("请输入要插入的位置和要插入的元素(用空格分开)：\n");scanf("%d %d",&p,&e);insertElem(L,p,e);//插入后打印链表数据printfList(L); return 0;}

运行结果如下：

6.删除结点

#include<stdio.h>#include<stdlib.h>//单链表的结构定义 typedef struct LNode{int data;//data存放结点数据域 struct LNode *next;//指向后继结点的指针 }LNode;//定义单链表结点类型 //头插法建立单链表void createlistF(LNode *&L, int a[], int n){LNode *s;int i;L = (LNode*)malloc(sizeof(LNode));L ->next = NULL;for(i=0;i<n;++i){s = (LNode*)malloc(sizeof(LNode));s ->data = a[i];s ->next = L ->next;L ->next = s;}} //打印链表数据 void printfList(LNode *L){LNode *temp = L;int count = 0;//计数器printf("表中的元素为:\n");while(temp->next){temp = temp->next;printf("%d\t",temp->data);count++;if(count%5==0)//每5个元素作为一行{printf("\n");}}printf("\n");}//删除单链表L中第p位置上的结点 void deleteElem(LNode *L, int p, int *e){LNode *temp = L;int i = 0;//找到删除结点的上一结点，即第p-1个结点while(i<p-1){temp = temp ->next;++i;}LNode *q = temp->next;//定义一个q指针指向被删除结点*e = q->data;//保存被删除的结点的数据域temp->next = q->next;//删除结点的上一个结点的指针域指向删除结点的下一个结点free(q);//释放q所指结点的内存空间 } int main(){LNode *L;int n;printf("请输入数组的个数："); scanf("%d",&n);int a[n];printf("请输入数组中的数(用空格分开)：\n");for(int i=0;i<n;++i){scanf("%d",&a[i]);}createlistF(L,a,n);printfList(L);//测试删除结点 int p,e;e = NULL;printf("请输入要删除结点的位置：\n");scanf("%d",&p);deleteElem(L,p,&e);//插入后打印链表数据printfList(L); return 0;}

运行结果如下：