前言
链表是表示一系列结点的数据结构。链表由结点组成，每个结点包含结点值以及指向其他结点的指针。
链表的种类包括单向链表、双向链表和循环链表。单向链表中的每个结点包含一个指针，指向链表中的后一个结点。双向链表中的每个结点包含两个指针，分别指向链表中的前一个结点和后一个结点。
结点
链表中一个数据元素需要存储本身的信息，还需要存储直接后继的存储位置，这两部分构成结点（node）。
换种方式来说，一个结点需要包含两部分内容，数据域和指针域。
数据域：存储数据元素信息
指针域：存储直接后继的存储位置
如下所示为一个结点，data表示数据域，next表示指针域。
实验内容
定义
1）类型定义linklistDef.h
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LNode , *LinkList;
（2）线性链表的基本操作linklistAlgo.h
Status ListInit_Link(LinkList &L)
{ /* 操作结果：构造一个空的线性表 L */
//L=(LinkList)malloc(sizeof(struct LNode));
L=new LNode;
if(!L)
exit(OVERFLOW);
L->next=NULL;
return OK;
}
获取长度
int ListLength_Link (LinkList L)
{ /* 初始条件：线性表 L已存在。*/
/* 操作结果：返回 L中数据元素个数 */
int i= 0 ;
LinkList p=L->next;
while(p)
{ i=i+1;
p=p->next;
}
return i;
}
获取元素
Status GetElem_Link (LinkList L,int i,ElemType &e)
{ /* 初始条件: L为带头结点的单链表的头指针*/
/* 操作结果：当第 i个元素存在时,其值赋给 e并返回 OK,否则返回ERROR */
int j=1;
LinkList p=L->next;
while(p&&j<i)
{ p=p->next;
j++;
}
if(!p||j>i)
return ERROR;
e=p->data;
return OK;
}
插入
Status ListInsert_Link (LinkList L,int i,ElemType e)
{ /* 在带头结点的单链线性表 L中第 i个位置之前插入元素 e */
int j=0;
LinkList p=L,s;
while(p&&j<i-1)
{ p=p->next;
j++;
}
if(!p||j>i-1)
return ERROR;
s=new LNode;
s->data=e;
s->next=p->next;
p->next=s;
return OK;
}
删除
Status ListDelete_Link (LinkList L,int i,ElemType &e)
{ /* 在带头结点的单链线性表 L中，删除第 i个元素,并由 e返回其值 */
int j=0;
LinkList p=L,q;
while(p->next&&j<i-1)
{p=p->next;
j++;
}
if(!p->next||j>i-1)
return ERROR;
q=p->next;
p->next=q->next;
e=q->data;
delete q;
return OK;
}
遍历输出
Status ListTraverse_Link (LinkList L)
{ /* 初始条件：线性表L已存在 */
/* 操作结果:依次对 L的每个数据元素的值进行输出 */
LinkList p=L->next;
while(p)
{printf("%d ",p->data);
p=p->next;
}
printf("/n");
return OK;
}
创建链表
void CreateList2_Link (LinkList &L,int n)
{ /* 正位序(插在表尾)输入 n 个元素的值，建立带表头结构的单链线性表 */
int i;
LinkList p,q;
L=new LNode;
L->next=NULL;
q=L;
printf("请输入%d个数据/n",n);
for(i=1;i<=n;i++)
{
p=new LNode;
scanf("%d",&p->data);
q->next =p;
q= p ;
}
p->next =NULL;
}
分析：p用作临时指针存放输入的数据，每次循环需要保存上一个指针，所以推出 q->next =p; q= p ;
最终p或q->next需要变成NULL，保证最后一个元素的Next域不存在数据。
测试
#include"pubuse.h"
typedef int ElemType;
#include"linklistDef.h"
#include"linklistAlgo.h"
int main()
{ int n=5;
LinkList La;
int i;
ElemType e;
printf("链表内容, ");
CreateList2_Link (La,n);
printf("La=");
ListTraverse_Link (La);
printf("/n 输入要取第几个元素 : ");
scanf("%d",&i);
if(GetElem_Link (La,i,e))
printf("/n所对应的元素 e=%d/n",e);
else
printf("input error!/n");
printf("/n 输入插入位置和插入的元素 : ");
scanf("%d %d",&i,&e);
if(ListInsert_Link (La,i,e))
{
printf("La=");
ListTraverse_Link (La);}
else
printf("input error!/n");
printf("/n 输入所要删除的元素位序 : ");
scanf("%d",&i);
if(ListDelete_Link (La,i,e))
{ printf("/n所删除的元素 e=%d/n",e);
printf("La=");
ListTraverse_Link (La);
}
else
printf("input error!/n");
return 0;
}结果：
