目录
本文相关知识：以链式存储结构来实现线性表（C++）
如有错误请指正~~谢谢~后面更新循环链表和双向链表
单链表（有头结点）
以带头结点的单链表为例，操作更加简便！
定义
首先，为了增强程序的可读性，做出以下定义：
#define TURE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define MAXSIZE 100 //表的最大长度
typedef int Status; //函数返回值的类型
typedef int ElemType; //元素的类型
typedef struct Lnode
{
ElemType data;
struct Lnode *next;//Lnode* 强调指向链表中某个结点的指针
}LNode,*LinkList;//LinkList 强调指向某个单链表的头指针
初始化
Status InitList(LinkList &L)
{
L=new LNode;//生成新结点，用指针L指向头结点
L->next=NULL;//头结点的指针域置空
return OK;
}
判空
Status IsEmpty(LinkList L)
{
if(L->next)
return OK;
else
return ERROR;
}
销毁
//销毁后链表就不存在了
Status DestoryList(LinkList &L)
{
Lnode *p;
while(L)
{
p=L;//从头结点开始依次释放所有结点
L=L->next;
delete p;
}
return OK;
}
清空
//清空后链表（的头指针和头结点）仍存在，只是没有元素变成了空链表
Status ClearList(LinkList &L)
{
Lnode *p,*q;
p=L->next;
while(p)//没到表尾
{
q=p->next;//用q保存下一个结点的地址，不然删除后就找不到
delete p;
p=q;
}
L->next=NULL;
return OK;
}
求表长
int ListLength(LinkList L)
{
Lnode *p=L->next;//p指向第一个结点
int len=0;
while(p)//遍历链表统计结点数
{
len++;
p=p->next;
}
return len;
}
取值
Status GetElem(LinkList L,int i,ElemType &e)
{
Lnode *p=L->next;
int j=1;
while(p&&j<i)//当链表遍历完或j=i找到该元素时，循环结束
{
p=p->next;
j++;
}
if(!p||j>i)//p为空or位置i非法时返回错误，元素i不存在
return ERROR;
e=p->data;
return OK;
}
查找
int LocateElem(LinkList L,ElemType e)
{
Lnode *p=L->next;
int j=1;
while(p&&p->data!=e)//当链表遍历完或找到该元素时，循环结束
{
p=p->next;
j++;
}
if(p)//p不为空时返回值为e的元素的位置j
return j;
else
return ERROR;
}
插入
Status InsertNode(LinkList &L,int i,ElemType e)
{//在第i个元素之前插入元素
Lnode *p=L;
int j=0;
while(p&&j<i-1)//找到第i-1个元素
{
p=p->next;
j++;
}
if(!p||j>i-1)
return ERROR;
Lnode *s=new LNode;//生成新结点
s->data=e;
s->next=p->next;//使新结点的指针域指向第i个结点
p->next=s;//使第i-1个结点的指针域指向新结点
return OK;
}
删除
Status DeleteNode(LinkList &L,int i)
{
Lnode *p=L->next;
int j=1;
while(p&&j<i-1)
{
p=p->next;
j++;
}
Lnode *q=p->next;//保存第i个元素的地址，防止丢失
p->next=p->next->next;//使第i-1个结点的指针域指向第i+1个结点
delete q;
return OK;
}
创建
头部创建
void CreateList_Front(LinkList &L,int n)
{
L=new LNode;
L->next=NULL;//先建立一个空链表
Lnode *p;
for(i=0;i<n;i++)
{
p=new LNode;
cin>>p->data;//逆序输入元素值赋给新结点的数据域
p->next=L->next;
L->next=p;//把新结点插入头结点之后
}
}
尾部创建
void CreateList_Rear(LinkList &L,int n)
{
L=new LNode;
L->next=NULL;//先建立一个空链表
Lnode *p,*r=L;
for(i=0;i<n;i++)
{
p=new LNode;
cin>>p->data;//顺序输入元素值赋给新结点的数据域
r->next=p;
p->next=NULL;//把新结点连在尾结点后面
r=p;//尾指针指向新的尾结点
}
}