链表的基本操作（c语言）
目录
链式存储结构
用一组物理位置任意的存储单元来存放线性表的数据元素
这组存储单元既可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任一位置上的
链表中元素的逻辑次序和物理次序不一定相同
结点：数据元素的存储映像，由数据域和指针域两部分组成
链表：n个结点由指针链组成一个链表
结点只有一个指针域的链表称为单链表或者线性链表
结点有两个指针域的链表，称为双链表
首尾相接的链表称为循环链表
什么时候是空表
无头结点时，头指针为空时表示空表
有头结点时，当头结点的指针域为空时表示空表
在链表中设置头结点的好处
1.便于首元结点的处理：首元结点的地址保存在头结点的指针域中，所以在链表的第一个位置上的操作和其他位置一致，无需进行特殊处理
2.便于空表和非空表的统一处理：无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和非空表的处理也就统一了
头结点的数据域
头结点的数据域可以为空，也可存放线性表长度等附加信息，头结点不能计入链表长度值
链式存储结构的特点
1.在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻
2.访问时只能通过头指针进入链表，并通过每个结点的指针域依次向后顺序扫描其余结点，所以寻找第一个结最后一结点所花的时间不等
这存取元素的方法被称为顺序存取法
优点：结点空间可以动态申请和释放
数据元素的逻辑次序靠结点的指针来指示，插入和删除时不需要移动数据元素。
缺点：存储密度小，每个结点的指针域需要额外占用存储空间，当每个节点的数据与所占字节不多时，指针域所占存储空间的比重显得很大
存储密度：
存储密度是指结点数据本身所占的存储量和整个结点结构中所占的存储量之比，即：
存储密度=结点数据本身占用的空间/节点占用的空间总量
一般地，存储密度越大，存储空间的利用率就越高，显然，顺序表的存储密度为1（100%），而链表的存储密度小于一。
链式存储结构是非随机存取的结构，对任一节点的操作都要从头指针依指针链查找到该结点，这增加了算法的复杂度
代码实现
注：许多课程里调用函数时函数的形参用&S，但这个&S好像在c语言编译器会报错，应该是c++可以实现，所以c语言在函数调用时还是定义一个指针变量以实现各种操作。
链表初始化
int Initlist(linklist* S) //链表初始化
{
(*S) = (linklist)malloc(sizeof(Lnode));
if (!(*S)) {
printf("链表初始化失败！n");
return error;
}
(*S)->next = NULL;
printf("链表初始化完毕！n");
return ok;
}头插法(前插法)创建含k个结点的单链表
int headlist(linklist* S, int k) //头插法(前插法)创建含n个结点的单链表
{
int i;
linklist p;
for (i = k; i>0; i--) {
p = (linklist)malloc(sizeof(Lnode));
printf("请输入第%d个结点的数据：n",i);
scanf_s("%d", &(p->data));
p->next = (*S)->next;
(*S)->next = p;
}
printf("头插法创建单链表成功！n");
return ok;
}尾插法(后插法)创建含k个结点的单链表
int endlist(linklist* S, int k) //尾插法(后插法)创建含k个结点的单链
{
int i;
linklist p,q=(*S);
for (i = 0; i < k; i++) {
p = (linklist)malloc(sizeof(Lnode));
printf("请输入第%d个结点的数据：n", i + 1);
scanf_s("%d", &(p->data));
p->next = NULL;
q->next = p;
q = p;
}
printf("尾插法创建单链表成功！n");
return ok;
}取第i个节点的数据域
int getlist(linklist S, int i) 取第i个节点的数据域
{
int j=0;
linklist p;
p = S;
while (p && j < i) {
p = p->next;
j++;
}
if (!p || j > i) {
printf("该节点不存在！n");
return error;
}
printf("该结点数据为%d n", p->data);
return ok;
}寻找数据域等于e的结点返回该结点序号
int locatelist(linklist S, int e) //寻找数据域等于e的结点返回该结点序号
{
int j = 1;
linklist p=S->next;
while (p && p->data != e) {
p = p->next;
j++;
}
if (!p) {
printf("未找到和该数据相等结点！n");
return error;
}
printf("该结点序号为%d n",j);
return ok;
}在第i个结点插入数据域为e的结点
int insertlist(linklist* S, int i, int e) //在第i个结点插入数据域为e的结点
{
int j=0;
linklist p = (*S),q;
q = (linklist)malloc(sizeof(Lnode));
while (p && j < i - 1) {
p = p->next;
j++;
}
if (i <= 0 || !p) {
printf("结点溢出,插入失败！n");
return error;
}
q->data = e;
q->next = p->next;
p->next = q;
printf("数据插入完毕！n");
return ok;
}删除第i个结点
int deletelist(linklist* S, int i) //删除第i个结点
{
int j=0;
linklist p, q;
p = (*S);
if (i <= 0 && !(p->next)) {
printf("程序错误,删除失败!n");
return error;
}
while (p->next && j < i - 1) {
p = p -> next;
j++;
}
q = p->next;
printf("被删除的结点元素是%d n", q->data);
p ->next = q->next;
free(q);
return ok;
}遍历链表
int printlist(linklist S) //遍历链表
{
int i=1;
linklist p;
p = S->next;
if (!p) {
printf("链表为空无法遍历！n");
return error;
}
while (p) {
printf("第%d个结点的数据域是:%dn",i,p->data);
p = p->next;
i++;
}
return ok;
}求链表结点个数(链表长度）
int lengthlist(linklist S) //求链表结点个数(链表长度）
{
int j=1;
linklist p=S->next;
if (!p) {
printf("链表为空！n");
}
while (p->next) {
p = p->next;
j++;
}
printf("该链表有%d个结点 n",j);
return ok;
}销毁链表
int destorylist(linklist* S) //销毁链表
{
linklist p=(*S);
while (!p) {
p = p->next;
free(*S);
}
printf("该链表已销毁！n");
return ok;
}合并两个链表
int merge(linklist* S1, linklist* S2,linklist *S3) //合并两个链表
{
linklist pa, pb, pc;
pa = (*S1)->next;
pb = (*S2)->next;
pc=(*S3) = (*S1);
while (pa && pb) {
if (pa->data <= pb->data) {
pc->next = pa;
pa = pa->next;
pc = pc->next;
}
else {
pc->next = pb;
pb = pb->next;
pc = pc->next;
}
}
if (!pa) {
pc->next = pb;
}
else {
pc -> next = pa;
}
return ok;
}总代码实现
#include<stdio.h>
#include<stdlib.h>
#define ok 1
#define error 0
typedef struct {
int data;
struct Lnode* next;
}Lnode,*linklist;
int Initlist(linklist* S); //链表初始化
int headlist(linklist* S,int k); //头插法(前插法)创建含k个结点的单链表
int endlist(linklist* S, int k); //尾插法(后插法)创建含k个结点的单链表
int getlist(linklist S, int i); //取第i个节点的数据域保存在*e中
int locatelist(linklist S, int e); //寻找数据域等于e的结点返回该结点序号
int insertlist(linklist* S, int i, int e); //在第i个结点插入数据域为e的结点
int deletelist(linklist* S,int i); //删除第i个结点
int printlist(linklist S); //遍历链表
int lengthlist(linklist S); //求链表结点个数(链表长度）
int destorylist(linklist* S); //销毁链表
int merge(linklist* S1, linklist* S2,linklist *S3); //合并两个链表
int main()
{
linklist La, Lb,Lc;
int i,j,k, n,m;
j=Initlist(&La);
if (!j) {
return error;
}
j=Initlist(&Lb);
if (!j) {
return error;
}
printf("请输入La的结点数：n");
scanf_s("%d", &n);
headlist(&La, n);
printlist(La);
printf("请输入Lb的结点数：n");
scanf_s("%d", &n);
endlist(&Lb, n);
printlist(Lb);
printf("请输入想获取的La的结点数据的序号：n");
scanf_s("%d", &k);
getlist(La, k);
printf("请输入La中想要寻找的数据：n");
scanf_s("%d", &m);
locatelist(La,m);
printf("请输入想要插入La的结点序号以及数据：n");
scanf_s("%d %d", &n, &m);
insertlist(&La, n, m);
lengthlist(La);
printlist(La);
printf("请输入想要删除La中的结点序号：n");
scanf_s("%d", &n);
deletelist(&La, n);
printlist(La);
lengthlist(La);
merge(&La, &Lb,&Lc);
printlist(Lc);
destorylist(&La);
destorylist(&Lb);
return 0;
}
int Initlist(linklist* S) //链表初始化
{
(*S) = (linklist)malloc(sizeof(Lnode));
if (!(*S)) {
printf("链表初始化失败！n");
return error;
}
(*S)->next = NULL;
printf("链表初始化完毕！n");
return ok;
}
int headlist(linklist* S, int k) //头插法(前插法)创建含n个结点的单链表
{
int i;
linklist p;
for (i = k; i>0; i--) {
p = (linklist)malloc(sizeof(Lnode));
printf("请输入第%d个结点的数据：n",i);
scanf_s("%d", &(p->data));
p->next = (*S)->next;
(*S)->next = p;
}
printf("头插法创建单链表成功！n");
return ok;
}
int endlist(linklist* S, int k) //尾插法(后插法)创建含k个结点的单链
{
int i;
linklist p,q=(*S);
for (i = 0; i < k; i++) {
p = (linklist)malloc(sizeof(Lnode));
printf("请输入第%d个结点的数据：n", i + 1);
scanf_s("%d", &(p->data));
p->next = NULL;
q->next = p;
q = p;
}
printf("尾插法创建单链表成功！n");
return ok;
}
int getlist(linklist S, int i) //取第i个节点的数据域保存在*e中
{
int j=0;
linklist p;
p = S;
while (p && j < i) {
p = p->next;
j++;
}
if (!p || j > i) {
printf("该节点不存在！n");
return error;
}
printf("该结点数据为%d n", p->data);
return ok;
}
int locatelist(linklist S, int e) //寻找数据域等于e的结点返回该结点序号
{
int j = 1;
linklist p=S->next;
while (p && p->data != e) {
p = p->next;
j++;
}
if (!p) {
printf("未找到和该数据相等结点！n");
return error;
}
printf("该结点序号为%d n",j);
return ok;
}
int insertlist(linklist* S, int i, int e) //在第i个结点插入数据域为e的结点
{
int j=0;
linklist p = (*S),q;
q = (linklist)malloc(sizeof(Lnode));
while (p && j < i - 1) {
p = p->next;
j++;
}
if (i <= 0 || !p) {
printf("结点溢出,插入失败！n");
return error;
}
q->data = e;
q->next = p->next;
p->next = q;
printf("数据插入完毕！n");
return ok;
}
int deletelist(linklist* S, int i) //删除第i个结点
{
int j=0;
linklist p, q;
p = (*S);
if (i <= 0 && !(p->next)) {
printf("程序错误,删除失败!n");
return error;
}
while (p->next && j < i - 1) {
p = p -> next;
j++;
}
q = p->next;
printf("被删除的结点元素是%d n", q->data);
p ->next = q->next;
free(q);
return ok;
}
int printlist(linklist S) //遍历链表
{
int i=1;
linklist p;
p = S->next;
if (!p) {
printf("链表为空无法遍历！n");
return error;
}
while (p) {
printf("第%d个结点的数据域是:%dn",i,p->data);
p = p->next;
i++;
}
return ok;
}
int lengthlist(linklist S) //求链表结点个数(链表长度）
{
int j=1;
linklist p=S->next;
if (!p) {
printf("链表为空！n");
}
while (p->next) {
p = p->next;
j++;
}
printf("该链表有%d个结点 n",j);
return ok;
}
int destorylist(linklist* S) //销毁链表
{
linklist p=(*S);
while (!p) {
p = p->next;
free(*S);
}
printf("该链表已销毁！n");
return ok;
}
int merge(linklist* S1, linklist* S2,linklist *S3) //合并两个链表
{
linklist pa, pb, pc;
pa = (*S1)->next;
pb = (*S2)->next;
pc=(*S3) = (*S1);
while (pa && pb) {
if (pa->data <= pb->data) {
pc->next = pa;
pa = pa->next;
pc = pc->next;
}
else {
pc->next = pb;
pb = pb->next;
pc = pc->next;
}
}
if (!pa) {
pc->next = pb;
}
else {
pc -> next = pa;
}
return ok;
}