单链表——c语言

1.什么是链表

  
链表是一种常见的数据结构。它与常见的数组是不同的，使用数组时先要指定数组包含元素的个数，即为数组的长度，但是如果向这个数组中加入的元素超过了数组的大小时，便不能将内容全部保存。
  链表这种存储方式，其元素个数是不受限定的，当进行添加元素的时候存储的个数就会随之改变。

在链表中有一个头指针，这个指针指向链表的第一个结点，每个结点包括两个部分：数据域和指针域，指针域存放下一个结点的地址，最后一个结点的指针域必须为NULL

2.设计链表

2.1 创建结点（结构体）
struct Node { int data; struct Node* next; };
2.2定义全局链表头尾指针方便调用
struct Node* head = NULL;//头指针 struct Node* end = NULL;//尾指针
2.3创建链表，实现在链表增加结点

法一：头插法

 
void AddList(int i)//头插法 { struct Node* tmp = (struct
Node*)malloc(sizeof(struct Node)); if (tmp == NULL) { return; } tmp->data = i;
//赋值 tmp->next = NULL; if (head == NULL) { head = tmp; end = tmp; } else {
tmp->next = head; head = tmp; } }
法二：尾插法

 
void AddList(int i)//尾插法 { struct Node* tmp = (struct
Node*)malloc(sizeof(struct Node)); if (tmp == NULL) { return; } tmp->data = i;
tmp->next = NULL; if (head == NULL) { head = tmp; end = tmp; } else { end->next
= tmp; end = tmp; } }
2.4查询指定的结点

这个直接上代码吧
struct Node* FindListNode(int i) { struct Node* tmp = head; while (tmp !=
NULL) { if (i == tmp->data) { return tmp; } tmp = tmp->next; } return NULL; }
2.5插入操作

 
void ListInsert(int i,int number)//在第i个位置之前插入number这个数据 { if (head ==
NULL||i<=1||i>MAX) { printf("无法插入\n"); return; } struct Node* tmp = (struct
Node*)malloc(sizeof(struct Node)); if (tmp == NULL) { return; } tmp->data
=number; struct Node* p = head; int j = 1; while (j < i-1) { p = p->next; j++;
} tmp->next = p->next; p->next = tmp; }
2.5删除尾结点
void ListDeleTail() { if (head == NULL)//判断是不是空链表 { printf("空链表\n"); return; }
if (head == end)//链表只有一个结点 { free(head); head = NULL; end = NULL; }
else//链表有多个结点 { struct Node* tmp = head; while (tmp->next != end) { tmp =
tmp->next;//找尾结点前一个结点 } free(end);//释放尾巴 end = tmp;//重新标记尾结点 end->next =
NULL;//将尾结点指针域置为空指针 } }

尾删除的过程首先应判断这个链表是不是为空或者只有一个节点，若只有一个节点则直接置NULL，若不为空，则先通过遍历找到倒数第二个节点，将最后一个节点释放内存，再将倒数第二个节点设置为end，然后将它的指针指向NULL。

2.6删除第一个结点
void ListDeleHead() { struct Node* tmp = head;//标记原来头的位置 if (head ==
NULL)//判断是否为空链表 { printf("空链表\n"); return; } head = head->next; free(tmp); tmp
= NULL; }
2.7删除指定的结点

 
void ListDele(int i) { if (head==NULL)//判断是不是空链表 { printf("空链表\n"); return; }
struct Node* tmp = FindListNode(i);//查找结点位置 if (tmp == NULL) { printf("查无\n");
return; } if (head == end)//链表只有一个结点 { free(head); head = NULL; end = NULL; }
else if (head->next==end)//链表有两个结点 { if (head == tmp)//判断删头还是尾 {
ListDeleHead(); } else if (end == tmp) { ListDeleTail(); } } else { if (head ==
tmp)//判断删头还是尾 { ListDeleHead(); } else if (end == tmp) { ListDeleTail(); } else
{ struct Node* p = head;//找要删除的前一个结点 while (p->next != tmp) { p = p->next; }
p->next = tmp->next; free(tmp); tmp = NULL; } } }
剩下的函数实现就没什么难的，下面上全部代码
#define _CRT_SECURE_NO_WARNINGS 1 #define MAX 10 #include<stdio.h>
#include<stdlib.h> #include<string.h> struct Node { int data; struct Node*
next; }; struct Node* head = NULL;//头指针 struct Node* end = NULL;//尾指针 //void
AddList(int i)//头插法 //{ // struct Node* tmp = (struct
Node*)malloc(sizeof(struct Node)); // if (tmp == NULL) //{ // return; //} //
tmp->data = i; //赋值 // tmp->next = NULL; // if (head == NULL) // { // head =
tmp; // end = tmp; // } // else // { // tmp->next = head; // head = tmp; // }
//} void AddList(int i)//尾插法 { struct Node* tmp = (struct
Node*)malloc(sizeof(struct Node)); if (tmp == NULL) { return; } tmp->data = i;
tmp->next = NULL; if (head == NULL) { head = tmp; end = tmp; } else { end->next
= tmp; end = tmp; } } void ListInsert(int i,int number)//在第i个位置之前插入number这个数据 {
if (head == NULL||i<=1||i>MAX) { printf("无法插入\n"); return; } struct Node* tmp =
(struct Node*)malloc(sizeof(struct Node)); if (tmp == NULL) { return; }
tmp->data =number; struct Node* p = head; int j = 1; while (j < i-1) { p =
p->next; j++; } tmp->next = p->next; p->next = tmp; } struct Node*
FindListNode(int i) { struct Node* tmp = head; while (tmp != NULL) { if (i ==
tmp->data) { return tmp; } tmp = tmp->next; } return NULL; } void
ListDeleHead() { struct Node* tmp = head;//标记原来头的位置 if (head == NULL)//判断是否为空链表
{ printf("空链表\n"); return; } head = head->next; free(tmp); tmp = NULL; } void
ListDeleTail() { if (head == NULL)//判断是不是空链表 { printf("空链表\n"); return; } if
(head == end)//链表只有一个结点 { free(head); head = NULL; end = NULL; } else//链表有多个结点
{ struct Node* tmp = head; while (tmp->next != end) { tmp =
tmp->next;//找尾结点前一个结点 } free(end);//释放尾巴 end = tmp;//重新标记尾结点 end->next =
NULL;//将尾结点指针域置为空指针 } } void ListDele(int i) { if (head==NULL)//判断是不是空链表 {
printf("空链表\n"); return; } struct Node* tmp = FindListNode(i);//查找结点位置 if (tmp
== NULL) { printf("查无\n"); return; } if (head == end)//链表只有一个结点 { free(head);
head = NULL; end = NULL; } else if (head->next==end)//链表有两个结点 { if (head ==
tmp)//判断删头还是尾 { ListDeleHead(); } else if (end == tmp) { ListDeleTail(); } }
else { if (head == tmp)//判断删头还是尾 { ListDeleHead(); } else if (end == tmp) {
ListDeleTail(); } else { struct Node* p = head;//找要删除的前一个结点 while (p->next !=
tmp) { p = p->next; } p->next = tmp->next; free(tmp); tmp = NULL; } } } void
ListPrint() { struct Node* tmp = head; while (tmp != NULL) { printf("%d\n",
tmp->data); tmp = tmp->next; } } void ListFree() { struct Node* tmp = head; if
(head == NULL) { printf("链表已空\n"); return; } while (tmp != NULL) { struct Node*
p = tmp; tmp = tmp->next; free(p); p = NULL; } head = NULL; end = NULL;
printf("清空成功\n"); } int main() { int i = 0; for (i = 0; i < MAX; i++)//创10个结点 {
AddList(i); } ListInsert(4,14);//在第4个位置之前插入14这个数据 struct Node* find; find =
FindListNode(4); if (find != NULL) { printf("找到%d\n", find->data); } else {
printf("没找到\n"); } ListDele(3);//删除第3个结点 ListPrint();//输出链表 ListFree();//删除整个链表
return 0; }

• « 上一篇：基于TF-IDF与k-means的情感聚类
• » 下一篇：Alibaba内部出品“Java初学者宝典”，让你就业没压力