1.概念与特点
概念：
逻辑结构：线性结构 一对一
存储结构：链式存储 内存中不一定是连续的
特点：
在链表中 每个数据元素都是一个结点，以结构体的方式封装
包含数据域和指针域
数据域：用于存储数据元素的信息
指针域：用于存储数据元素下一个结点的首地址
2.创建节点的结构体类型
1
2
3
4
5
6typedef struct node{ int data; //保存节点的数据(数据域) struct node *next; //保存下个节点的地址(指针域) }link_list_t;
3.创建新节点的函数create_linklist()
（1）定义一个结点类型的指针*L，并用malloc在堆空间分配内存；
（2）初始化结点数据，L->data=-1；L->next=NNULL；
（3）返回结点的首地址。
1
2
3
4
5
6
7
8
9
10
11
12link_list_t *create_linklist(){ link_list_t *L=malloc(sizeof(link_list_t));//给结构体指针在堆内存上分配内存 if(NULL==L){ printf("创建链表失败n"); return NULL; } L->data=-1; //初始化节点数据为-1 L->next=NULL; //初始化节点next指向为空 return L; }
4.创建头节点
1
2link_list_t *L=create_linklist(); //创建一个节点作为头节点
5.插入节点--头插法
1
2
3
4
5
6
7
8
9
10
11
12
13int head_link(link_list_t *L,data_t value){//L单链表的头结点，value新节点的数据 if(NULL==L){ printf("参数有误n"); return -1; } link_list_t *N=create_linklist(); //创建一个新节点 N->data=value; //初始化节点数据 N->next=L->next; L->next=N; return 0; }
6.遍历单链表
（1）定义一个新的节点类型*q，初始化为q=L->next；
（2）循环条件q!=NULLL;
（3）循环体：q=q->next;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19int show_link(link_list_t *L){ if(NULL==L){ printf("参数有误n"); return -1; } if(NULL==L->next){ printf("链表为空n"); return -1; } link_list_t *q=L->next; //定义一个移动的节点类型的指针，用于遍历 while(q!=NULL){ //从首个有效的节点开始遍历 printf("%d ",q->data); q=q->next; } puts(""); return 0; }
7.任意位置删除节点
思路：找到要删除位置的前一个节点。
条件：pos大于等于0，且小于链表的长度
（1）定义一个动点*q=L；int i=0;
（2）循环q=q->next;直到定位到要删除节点的前一位；
（3）在循环时要判断p->next是否为空，如果为空则退出循环，表示pos位没有数据；
（4）当定位到要删除的前一个节点，定义另一个节点保存要删除节点的位置*p=q->next;
（5）令q->next=p->next;p->next=NULL;释放p指向的堆空间。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25//删除时，要定位到要删除节点的前一个位置，以便删除 int pos_delete(link_list_t *L,int pos){ //pos位置信息 if(NULL==L){ printf("参数有误n"); return -1; } if(NULL==L->next){ printf("链表为空n"); return -1; } int i=0; link_list_t *q=L; for(i=0;i<pos;i++){ q=q->next; if(q->next==NULL){ return -1; } } link_list_t *p=q->next; q->next=p->next; free(p); p=NULL; return 0; }
8.翻转单链表
链表翻转：
现象：输出前---12345
输出后---54321
思路：将链表分为两个链表，从第一个有效数据后断开，前半部分为一个链表，后半部分 为 一个链表。对后半部分进行头删的同时将节点头插到前半部分，直到后半部分为空。
（1）定义一个节点类型的指针*q=L->next->next;
（2）拆分为两个链表分别为L和q，L->next->next=NULL;
（3）定义一个新的节点类型指针*p=NULL，指向要操作的节点；
（4）判断q是否为空，否的话令p=q;q=q->next;p->next=L->next;L->next=p;
（5）循环执行第4步，直到q==NULL。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25//将单链表分为俩个单链表，分别进行头删和头插 int overturn_list(link_list_t *L){ if(NULL==L){ printf("参数有误n"); return -1; } if(NULL==L->next){ printf("链表为空n"); return -1; } link_list_t *p=L->next->next; if(p==NULL){ printf("仅有一个元素n"); return -1; } L->next->next=NULL; link_list_t *q=p; while(q!=NULL){ p=q; q=p->next; p->next=L->next; L->next=p; } return 0; }
9.任意位置查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21data_t pos_find(link_list_t *L,int pos){ if(NULL == L || pos<0){ printf("输入参数有误n"); return -1; } if(NULL == L->next){ printf("表为空n"); return -1; } link_list_t *q=L; int i=0; for(;i<=pos;i++){ q=q->next; if(NULL == q){ printf("输入的位置参数过大n"); return -1; } printf("%d位置的数据是%dn",pos,q->data); return 0; } }
10.排序
思路：只交换数据，不交换节点(冒泡排序)。
（1）定义两个移动的节点类型的指针q和p,一个用于交换数据的三方变量temp；
（2）判断L->next和L->next->next是否为空，成立的话，程序结束，表位空表或只有一个节点；
（3）上述不成立，则令q=L->next；
（4）令p=q->next;判断q->data是否大于p->data，成立，则交换数据；不成立，执行第5步；
（5）令p=p->next；判断p是否为空，不成立执行第4步；成立，执行第6步；
（6）令q=q->next；判断q是否为空，不成立，执行第4步，成立退出循环，程序结束。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27//只交换数据 int sort_link(link_list_t *L){ if(NULL == L){ printf("输入参数有误n"); return -1; } if(NULL == L->next || NULL == L->next->next){ printf("表为空表或表中只有一个元素n"); return -1; } link_list_t *q=L->next; link_list_t *p=NULL; data_t temp=0; while(NULL != q){ p=q->next; while(NULL != p){ if(q->data>p->data){ temp = p->data; p->data=q->data; q->data=temp; } p=p->next; } q=q->next; } return 0; }
最后
以上就是畅快蛋挞最近收集整理的关于单链表的创建与操作（有头节点）的全部内容，更多相关单链表内容请搜索靠谱客的其他文章。
发表评论 取消回复