链表呢是一种十分基础的数据结构类型，分为单向链表，双向链表以及循环链表，今天我们就来讲讲单向链表的基本操作。
什么是单向链表
链表是一种储存结构，包含数据域和指针域，一个数据域配一个指针域构成一个结点，数据域存放数据，指针域存放指针即地址，通过将下一个结点（后继结点）的地址存放在上一个结点（前驱结点）的指针域中将四处分散的结点连接起来，也就将分散的储存空间连接起来。
单向链表的优缺点
从上述描述我们可以看出，链表优点在于它的储存空间不用连续，因为它可以通过指针将各处分散的储存空间连接起来，而且链表的长度可以改变，是一种动态分配内存的模式，十分方便在任意位置添加删除结点。缺点在于不能随机访问结点,需要从头开始顺次一个结点一个结点的查找（单向链表），而数组就可以通过下标值直接找到需要的值。单向链表的基本操作（增,删,改,查）
首先呢开始准备工作，引用头文件，定义类型... #include<stdio.h>
#include<stdlib.h>
#define N 5 //链表的长度（链表的位置从1开始）
#define X 1 //待删除结点的起始位置
#define Y 3 //待删除结点的末位置
typedef struct node{
int data;
struct node* next;
}node,* List;
List L1,L2;
创建链表并赋值
此处链表的头指针数据域不存放数据 List CreateLinearList(List L1) //创建单向链表并向链表中写入值
{
int i,count;
node *q;
L1=(List)malloc(sizeof(node));
L1->next=0;
q=L1;
printf("Enter the number of your elements in the list:\n");
scanf("%d",&count);
printf("Enter %d elements for your linear list:\n",count);
for(i=0;i<count;i++)
{
node* p=(node*)malloc(sizeof(node)); //p是创建的新结点，往链表后面插，q指向链表的尾结点
scanf("%d",&p->data);
p->next=0;
q->next=p;
q=p;
}
q->next=0;
return L1;
}
插入结点
头插法
void InsertByHead(List L)
{
node* p=(node*)malloc(sizeof(node)) //创建新结点
printf("Enter the element to insert by head:\n");
scanf("%d",&p->data); //输入要插的数并存放在新结点的数据域
p->next=L->next; //将新结点插入链表头部
L->next=p;
}
尾插法
void InsertByTail(List L1)
{
node *p,*q; //p从头遍历找到链表的尾结点，q是要插入的新结点
p=L1;
q=(node*)malloc(sizeof(node)) ;
printf("Enter an element to insert to the tail:\n");
scanf("%d",&q->data);
q->next=0;
while(p->next)
{
p=p->next;
}
p->next=q;
}
指定位置插
void InsertByPosition(List L) //向链表指定位置插值
{
int position,i; //position记录插值的位置
node *q,*p=(node*)malloc(sizeof(node)); //q遍历链表找到待插位置的前一个结点，p存放待插的值
q=L;
printf("Enter the position and value to be inserted:\n");
scanf("%d%d",&position,&p->data);
if(position<=0) //位置不能为负值
{
printf("Invalid Position!\n");
exit(-1);
}
for(i=1;i<position;i++)
{
q=q->next;
if(q==0) //位置超过链表的最后一位的后一位
{
printf("Invalid position!\n");
exit(-1);
}
}
p->next=q->next;
q->next=p;
}
顺序表按顺序插
void InsertSorted(List L) //有序表按顺序插值
{
T e;
printf("Enter an element to be inserted:\n");
scanf("%d",&e);
node* p=(node*)malloc(sizeof(node));
node* q=L->next;
p->data=e;
p->next=0;
while(q->next&&q->next->data<e)
{
q=q->next;
}
p->next=q->next;
q->next=p;
}
删除结点
按位置删除一个结点
void DeleteElementByPosition(List L)
{
int i,position;
node *d,*p=L;
printf("Enter the position of value to be deleted:\n");
scanf("%d",&position);
if(position<=0)
{
printf("Invalid position!\n"); // 查询位值小于零，不合法，退出
exit(-1);
}
for(i=1;i<position;i++)
{
p=p->next; //p记录待删结点的前一个结点
if(p->next==0)
{
printf("Invalid position!\n")
exit(-1); //查询位置超过链表最后一个位置，不合法，退出
}
}
d=p->next; //d记录待删结点
p->next=p->next->next;
free(d); //释放待删结点
}
按值删除一个结点，删第一个
bool DeleteElement(List L)
{
int e;
node *p=L,*q;
printf("Enter the value to be deleted:\n");
scanf("%d",&e);
while(p->next!=0&&p->next->data!=e)
{
p=p->next;
}
if(p->next!=0) //若p->next!=0说明未遍历到链表最后一个结点 ，找到e
{
q=p->next; //q指向待删值所在结点
p->next=q->next;
free(q);
return true;
}
else
{
printf("There are no such value in the list!\n");
return false;
}
}
按值删除结点，全删
void DeleteElements(List L)
{
//反复调用函数DeleteElement（），直到返回值为false，即链表中已经没有待删值
while(DeleteElement(L))
;
}
按值删除结点，只留一个
void DeleteUnique(List L)
{
int e;
node *p=L->next,*q;
printf("Enter the value to be deleted:\n");
scanf("%d",&e);
while(p!=0&&p->data!=e)
{
p=p->next;
}
if(p!=0) //若p->next!=0说明未遍历到链表最后一个结点 ，找到e ，p指向第一个e所在的结点
{
DeleteElements(p); //保留第一个e,调用DeleteElements（p），删除其他的e
}
else
{
printf("There is no such value in the list!\n");
}
}
删去链表中最大值
void InsertMaxToListHead(List L1) //将链表的最大值移到头部
{
node *max=L1->next,*p=L1,*q;
while(p->next)
{
if(p->next->data > max->data)
{
max=p->next;
q=p;
}
p=p->next;
}
q->next=max->next;
max->next=L1->next;
L1->next=max;
}
void DeleteMaxOfList(List L1) // 删除链表中最大元素
{
node *max;
InsertMaxToListHead(L1); //调用InsertMaxToListHead()函数将最大值移到头部
max=L1->next;
L1->next=max->next; //删去结点L1->next即最大值结点
free(max);
}
更改结点的值
1.通过位置更改
2.通过值更改
打印链表
void PrintList(List L) //打印链表
{
int i;
node *p=L->next,*q=L;
while(p) //通过循环打印链表结点的值
{
printf("%d ",p->data);
p=p->next;
if(p==L->next) //如果是遍历循环链表，p往后遍历到表头处结束
{
break;
}
}
printf("\n");
}
其他操作:
求表长
int Len(List L)
{
node *q=L;
int count;
for(count=0;q->next!=0;q=q->next,count++);
return count;
}
链表转置
头插法转置单链表：void Reverse(List L) //将链表转置
{
int i;
node *tail,*p; //tail指向链表的尾结点，p指向尾结点的前一个结点
for(i=1;i<Len(L);i++) //每次都从链表头开始，找到链表尾结点
{
tail=L->next;
p=L;
while(tail->next) //遍历链表找到尾结点
{
tail=tail->next;
p=p->next;
}
p->next=0; //头插法将链表的尾结点插到链表头部
tail->next=L->next;
L->next=tail;
}
}
递归法转置单链表：
void Reverse(List L)
{
if(L==null||L->next==null) return;//单链表只有一个结点
List last = Reverse(L->next);
L->next->next=L;
L->next=null;
}
迭代法转置单链表
// 反转以 a 为头结点的链表
ListNode reverse(ListNode a) {
ListNode pre, cur, nxt;
pre = null; cur = a; nxt = a;
while (cur != null) {
nxt = cur.next;
// 逐个结点反转
cur.next = pre;
// 更新指针位置
pre = cur;
cur = nxt;
}
// 返回反转后的头结点
return pre;
}
链表排序（升序）
冒泡法排序：void OrderListByAscending(List L1) // 5.将链表按升序排序
{
int i;
node* p=L1;
for(i=1;i<N;i++)
{
InsertMaxToListHead(p); //多次调用InsertToMaxHead()将p链表的最大值移到p链表的头部
p=p->next; //p往后移直至移到L1链表的最后一个结点
}
}
链表相并
void Add(List1,List2) //两有序链表相并(并到链表L1上)
{
node *p=L1->next,*q=L2->next,*tail=L1;
//p遍历L1的结点，q遍历L2的结点，tail指向合并链表的尾结点
while(p&&q) //当遍历到某链表的尾结点时，循环结束
{
if(p->data < q->data) //tail指向p->data,q->data中较小的结点
{
tail->next=p;
tail=p;
p=p->next;
}
else if(p->data > q->data)
{
tail->next=q;
tail=q;
q=q->next;
}
else
{
tail->next=q;
tail=q;
q=q->next;
p=p->next;
}
}
tail->next=(q==0?p:q); //tail->next指向未遍历完的链表结点
}
上述有关链表操作的main函数根据需要写
一个有趣的实例：多项式相加
思路类似于有序链表的合并
完整代码如下
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
int fac; //多项式项的系数部分
int e; //多项式项的指数部分
struct node* next;
}node,* Poly;
void AddPoly(Poly P1,Poly P2) //两升序序多项式相加
{
node *p=P1->next,*q=P2->next,*tail=P1;
//p遍历L1的结点，q遍历L2的结点，tail指向合并链表的尾结点
while(p&&q) //当遍历到某链表的尾结点时，循环结束
{
if(p->e < q->e) //tail指向系数较小的结点
{
tail->next=p;
tail=p;
p=p->next;
}
else if(p->e > q->e)
{
tail->next=q;
tail=q;
q=q->next;
}
else //相同指数项系数相加
{
p->fac=p->fac+q->fac;
tail->next=p;
tail=p;
p=p->next;
q=q->next;
}
}
tail->next=(q==0?p:q); //tail->next指向未遍历完的链表结点
}
Poly CreatePoly(Poly P)
{
int count,i;
P=(node*)malloc(sizeof(node));
P->next=0; //头结点数据域不存放数据
node *m=P;
printf("Enter the number of your node:\n");
scanf("%d",&count);
printf("Enter coefficients and index:\n"); //输入多项式的系数和指数部分
for(i=0;i<count;i++)
{
node *q=(node*)malloc(sizeof(node));
scanf("%d%d",&q->fac,&q->e); //输入项的系数和指数
q->next=0;
m->next=q; //m记录待插的位置(链尾)，q是待插的结点
m=q;
}
return P;
}
void PrintPoly(Poly P)
{
int i;
node *m=P->next;
while(m)
{
printf("%dx^%d + ",m->fac,m->e);
m=m->next;
}
printf("\n");
}
int main(Void)
{
Poly P1,P2;
P1=CreatePoly(P1);
printf("P1=");
PrintPoly(P1);
P2=CreatePoly(P2);
printf("P2=");
PrintPoly(P2);
AddPoly(P1,P2);
printf("P1+P2=");
PrintPoly(P1);
return 0;
}
运行结果无误。
链表操作的递归实现
事实上尾递归都可以用循环实现，而递归算法十分占内存，所以上述链表中需要遍历的各种操作是没有必要用递归实现的，这里我们只做一点了解:代码如下（链表的头结点数据域不为空）
#include<iostream>
#include<stdio.h>
using namespace std;
typedef int T;
typedef struct node{
T data;
node * next;
}node,*List;
void Create(List &h) //将链表分为两部分：头结点和头结点后面部分
{ //而头结点后面部分又可以分为同样的两部分，依次类推
T e;
cin>>e;
if(e<=0)
{
h=0; //输入负数为结束标志
return;
}
h=new node;
h->data=e;
Create(h->next); //递归创建头结点后面的链表
}
//此方式不是尾递归，可以不用查找链表的尾结点来遍历倒序输出链表，是一个很好的倒序输出的方法
void ReverseTraverse(List h) //将链表倒序输出
{ //若递归到尾结点的next则递归结束
if(0==h)
{
return;
}
ReverseTraverse(h->next); //过程为:先输出头结点后面部分的链表，再输出头结点
cout<<h->data<<" "; //而头结点后面部分的链表又可以分为头结点和头结点后部分的链表,输出顺序如上一步骤
}
void Traverse(List h) //将链表正序输出
{
if(0==h) //若递归到链表尾结点的后面，则返回
{
return;
}
cout<<h->data<<" "; //过程为:先输出头结点,再输出头结点后面部分的链表
Traverse(h->next); //而头结点后面部分的链表又可以分为头结点和头结点后部分的链表,输出顺序如上一步骤
}
int Len(List &h)
{
if(0==h)
{
return 0; //链表为空时结束递归，返回值
}
return Len(h->next)+1; // 链表的长度为头结点后面部分构成链表的长度加1（头结点）
}
node* Locate(List h,T e) //查找
{
if(0==h) //递归到链表的尾结点，没找到待查值，返回地址为空
{
return 0;
}
if(h->data==0) //找到待查值，返回该值的位置
{
return h;
}
return Locate(h->next,e); //查找分为两部分：头结点和头结点后面部分的链表，依次类推
}
void Destroy(List h) //删除链表
{
if(0==h) //尾结点递归完毕，返回
{
return;
}
Destroy(h->next); //删除分为两部分：删除头结点和头结点后面部分的链表
delete h;
}
int main(void)
{
List h=0;
Create(h);
ReverseTraverse(h);
cout <<endl;
return 0;
}
至此大功告成！代码较为幼稚QAQ，思路值得学习~
