数据结构：单链表的基本操作

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。这组存储单元可以是连续的，也可以是不连续的。链表中的数据是以结点来表示的，一个结点包含数据域和指针域，数据域用来存储结点的值，指针域用来存储数据域的直接后继的地址，单链表结点的而结构如下图：
这里写图片描述
一般情况下使用链表只关心链表中结点之间的逻辑关系，并不关心链表的每个结点的实际存储位置，通常用箭头来表示链域中的指针，链表的逻辑结构可以直观的画成用箭头链接起来的结点序列。

C语言描述单链表的存储结构

typedef int DataType;typedef struct Node
{DataType Data;struct Node* Next;
}Node, *LinkList;

其中Node表示链表的结点类型，LinkList表示链表的指针类型，通常用Node* 定义链表的结点指针，用LinkList定义链表的头指针。

单链表的基本操作

（1）单链表的初始化

单链表的初始化就是把单链表初始化为空，带头节点的单链表的初始化需要为头结点分配存储空间，并将头节点的指针域置空。

void InitList(LinkList* PHead)
{if ((*PHead = (LinkList)malloc(sizeof(Node))) == NULL){printf("内存申请失败!\n");return;}(*PHead)->Next = NULL;
}

（2）判断单链表是否为空

判断单链表是否为空，就是看单链表的头结点的指针域是否为空，即：PHead->Next == NULL是否为真。

int ListEmpty(LinkList PHead)
{return  PHead->Next == NULL;
}

（3）头插法建表

从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志（-1）为止。

//头插法建表
void CreatFormHead(LinkList PHead)
{DataType data; Node* s;             //要插入的结点指针scanf("%d", &data);while (data != -1)    //输入要插入的值以-1作为结束标志{s = (Node*)malloc(sizeof(Node));s->Data = data;s->Next = PHead->Next;PHead->Next = s;scanf("%d", &data);}
}

（4）尾插法建表

尾插法建表是将新结点插入到当前链表的表尾上。为此必须增加一个尾指针tail，使其始终指向当前链表的尾结点。

//尾插法建表
void CreatFormTail(LinkList PHead)
{Node* s;Node* tail;             DataType data;tail = PHead;scanf("%d", &data);while (data != -1){s = (Node*)malloc(sizeof(Node));s->Data = data;s->Next = tail->Next;tail->Next = s;tail = s;   //tail始终指向表尾scanf("%d", &data);}
}

（5）按序号查找

按序号查找，即查找序号为i的元素对应的值，如果找到的话，返回结点的指针p，对应的值可以通过p->Data打印，定义一个指针p使其指向头指针p = PHead;从头指针开始，一直往后查找，定义一个变量j初始化为0，指针p每次后移一位，j++当j=i时跳出循环，返回指向第i个结点的指针p，在查找元素是要判断表是否为空，保证p的下一个结点不为空，否则，就没有办法保证执行循环体中的p = p->Next;

Node* Get(LinkList PHead, int i)
{Node* p;   //结点指针int j = 0;p = PHead;if (ListEmpty(PHead))    //空表{printf("表为空！\n");return 0;}while (!ListEmpty(PHead) && j < i){p = p->Next;j++;}if (j == i){return p;   /*返回指向第i个结点的指针p*/}return NULL;
}

（6）按值查找

按值查找，即查找单链表中与给定元素data相等的元素，并返回这个元素的下标。定义一个变量i赋初值为1，从第一个结点（头结点的下一个结点）PHead->Next开始一直往后查找，指针p每次后移一位i++当p->Data != data时跳出循环，返回i的值即为要查找的元素data在链表中的位置。

//按值查找
int Locate(LinkList PHead, DataType data)
{Node*p = PHead->Next;int i = 1;while (p){while (`p->Data != data`){p = p->Next;i++;}break;              //找到节点时退出循环}return i;
}

（7）求表长操作

链表的长度即链表中元素的个数，定义一个变量int len = 0;定义一个指针p = PHead;从头结点开始依次遍历链表中的每个结点，指针每后移一次len++;，当链表为空即p->Next != NULL时跳出循环，返回len的值。

//求单链表的长度
int length(LinkList PHead)
{Node *p;p = PHead;int len = 0;while (p->Next != NULL){len++;p = p->Next;}return len;
}

（8）插入操作

在单链表的第i个位置插入一个元素data，首先需要找到要插入位置的前驱结点位置，即：第i-1个结点，定义一个指针p指向头结点，从头结点开始一直往后查找，当要插入的位置j=i-1时，跳出循环，指针p指向该节点。然后，创建一个新结点，使指针s指向新创建的结点，将要插入的数据data,赋给新创建的结点的数据域s->Data = data;将新结点的指针域指向第i个结点s->Next = p->Next;将第i-1个结点的指针域指向新结点p->Next = s；

//任意位置插入
void InsList(LinkList PHead, int i, DataType data)
{Node*p;Node*s;p = PHead;int j = 0;while (p->Next != NULL && j < i - 1){p = p->Next;j++;}if (p == NULL){return; //插入位置不合法}s = (Node*)malloc(sizeof(Node));  //新建一个结点s->Data = data;s->Next = p->Next;p->Next = s;
}

（9）删除操作

将单链表的第i个结点删除，data用于存放删除结点的值，删除第i个结点同样也需要找到第i个结点的前驱结点，定义一个指针p指向头结点，从头往后查找第i-1个结点，如果找到则指针p指向要删除操作的前驱结点（第i-1个结点），s指向要删除的节点is = p->Next;，将前驱结点的指针域指向要删除结点的下一个结点p->Next = s->Next;也就是让s指向的结点与单链表断开，然后释放s指向的结点，即释放要删除结点的空间，返回删除结点的值*data在删除操作时要判断删除的位置是否合法。

//任意位置删除
int DelList(LinkList PHead, int i, DataType* data)
{Node* p;Node* s;p = PHead;int k = 0;/*删除位置i小于0，或者删除位置大于元素个数，比如链表中只有一个元素，i=2时*/if (i < 0 || i>length(PHead)){printf("删除位置不合法！\n");return 0;  //删除位置不合法}while (p->Next != NULL && k < i - 1){p = p->Next;k++;}s = p->Next;*data = s->Data;p->Next = s->Next;free(s);return *data;
}

（10）销毁链表

单链表的结点是动态申请的，在程序结束时将这些结点空间通过free函数释放。

//销毁链表
void DestoryList(LinkList PHead)
{Node* p;Node* q;p = PHead;while (p->Next != NULL){q = p;p = p->Next;free(q);}
}

（11）打印表中元素

依次打印顺序表中的元素。

void PrintList(LinkList PHead)
{Node* p;p = PHead->Next;while (p){printf("%d ", p->Data);p = p->Next;}printf("\n");
}

单链表的基本操作源代码

LinkList.h定义链表的数据结构和链表操作的函数声明

#ifndef __LinkList_H__
#define __LincList_H__typedef int DataType;typedef struct Node
{DataType Data;struct Node* Next;
}Node, *LinkList;void InitList(LinkList* PHead);   //单链表的初始化
int ListEmpty(LinkList PHead);    //判断单链表是否为空
void CreatFormHead(LinkList PHead); //头插法建表
void CreatFormTail(LinkList PHead); //尾插法建表
Node* Get(LinkList PHead, int i);  //按序号查找
int Locate(LinkList PHead, DataType data); //按值查找
int length(LinkList PHead); //求表长操作
void InsList(LinkList PHead, int i, DataType data); //插入操作
int DelList(LinkList PHead, int i, DataType* data); //删除操作
void DestoryList(LinkList PHead);  //销毁顺序表
void PrintList(LinkList PHead);    //打印表中元素#endif

LinkList.c 单链表操作函数的具体实现

#include <stdio.h>
#include <stdlib.h>
#include "LinkList.h"//单链表的初始化void InitList(LinkList* PHead)
{if ((*PHead = (LinkList)malloc(sizeof(Node))) == NULL){printf("内存申请失败!\n");return;}(*PHead)->Next = NULL;
}//判断单链表是否为空int ListEmpty(LinkList PHead)
{return  PHead->Next == NULL;
}//头插法建表
void CreatFormHead(LinkList PHead)
{DataType data; Node* s;             //要插入的结点指针scanf("%d", &data);while (data != -1)    //输入要插入的值以-1作为结束标志{s = (Node*)malloc(sizeof(Node));s->Data = data;s->Next = PHead->Next;PHead->Next = s;scanf("%d", &data);}
}//尾插法建表
void CreatFormTail(LinkList PHead)
{Node* s;Node* tail;             DataType data;tail = PHead;scanf("%d", &data);while (data != -1){s = (Node*)malloc(sizeof(Node));s->Data = data;s->Next = tail->Next;tail->Next = s;tail = s;   //tail始终指向表尾scanf("%d", &data);}
}//按序号查找Node* Get(LinkList PHead, int i)
{Node* p;   //结点指针int j = 0;p = PHead;if (ListEmpty(PHead))    //空表{printf("表为空！\n");return 0;}while (!ListEmpty(PHead) && j < i){p = p->Next;j++;}if (j == i){return p;   /*返回指向第i个结点的指针p*/}return NULL;
}//按值查找
int Locate(LinkList PHead, DataType data)
{Node*p = PHead->Next;int i = 1;while (p){while (p->Data != data){p = p->Next;i++;}break;              //找到节点时退出循环}return i;
}//求单链表的长度
int length(LinkList PHead)
{Node *p;p = PHead;int len = 0;while (p->Next != NULL){len++;p = p->Next;}return len;
}//任意位置插入
void InsList(LinkList PHead, int i, DataType data)
{Node*p;Node*s;p = PHead;int j = 0;while (p->Next != NULL && j < i - 1){p = p->Next;j++;}if (p == NULL){return; //插入位置不合法}s = (Node*)malloc(sizeof(Node));  //新建一个结点s->Data = data;s->Next = p->Next;p->Next = s;
}//任意位置删除
int DelList(LinkList PHead, int i, DataType* data)
{Node* p;Node* s;p = PHead;int k = 0;/*删除位置i小于0，或者删除位置大于元素个数，比如链表中只有一个元素，i=2时*/if (i < 0 || i>length(PHead)){printf("删除位置不合法！\n");return 0;  //删除位置不合法}while (p->Next != NULL && k < i - 1){p = p->Next;k++;}s = p->Next;*data = s->Data;p->Next = s->Next;free(s);return *data;
}//销毁链表
void DestoryList(LinkList PHead)
{Node* p;Node* q;p = PHead;while (p->Next != NULL){q = p;p = p->Next;free(q);}
}//打印表中元素
void PrintList(LinkList PHead)
{Node* p;p = PHead->Next;while (p){printf("%d ", p->Data);p = p->Next;}printf("\n");
}

main.c 操作函数的简单测试代码

#include <stdio.h>
#include <stdlib.h>
#include <Windows.h>
#include "LinkList.h"int main()
{LinkList L;LinkList L1;DataType data;int num;   //需要操作的元素序号int val;   //插入元素值 InitList(&L);InitList(&L1);printf("头插法建表(L1)：");CreatFormHead(L1);printf("链表中的元素有:\n");PrintList(L1);printf("\n");printf("尾插法建表(L)：");CreatFormTail(L);//后面为对尾插法所建表的操作printf("链表中的元素有:\n");PrintList(L);printf("\n");printf("在链表中插入一个元素：\n");printf("请输入插入位置：");scanf("%d", &num);printf("请输入插入元素值：");scanf("%d", &val);InsList(L, num, val);printf("链表中的元素有:\n");PrintList(L);printf("\n");printf("删除链表中的元素:\n");printf("请输入删除位置：");scanf("%d", &num);DelList(L, num, &data);printf("删除元素的值为%d\n", data);printf("\n");printf("链表中的元素有:\n");PrintList(L);printf("\n");printf("链表的长度为：%d\n", length(L));printf("\n");printf("请输入要查找的元素序号：\n");scanf("%d", &num);Node* p = Get(L, num);printf("第%d 个元素值为：%d\n", num, p->Data);printf("请输入要查找的元素值：\n");scanf("%d", &val);printf("%d在表中的位置序号为：%d\n", val, Locate(L, val));printf("\n");system("pause");return 0;
}