单链表的基本操作
#include"List.h"
#include"pch.h"
#include<iostream>
using namespace std;
constexpr auto MAXSIZE = 100;
typedef struct LNode
{
int data;//结点的数据域
struct LNode *next;//结点的指针域
}LNode,*LinkList;//LinkList为指向结构体LNode的指针类型
Status InitList_L(LinkList &L)
{//单链表的初始化
L->next = NULL;
return OK;
}
Status DestroyList_L(LinkList &L)
{//销毁一个单链表
LinkList P;
while (L)
{
P = L;
L = L->next;
delete P;
}
return OK;
}
Status ClearList(LinkList &L)
{//将L重置为空表
LinkList p,q;
p = L->next;//P指向第一个结点
while (p)//没到表尾
{
q= p->next;
delete p;
p = q;
}
L->next = NULL;//头结点指针域为空
return OK;
}
int ListLength_L(LinkList L)
{//返回L中数据元素的个数
LinkList p;
p = L->next;//p指向第一个结点
int i = 0;
while (p)
{//遍历单链表，统计结点数
i++;
p = p->next;
return i;
}
}
int ListEmpty(LinkList L)
{//若L表为空，则返回1，否则返回0
if (L->next)//为空
return 0;
else
return 1;
}
Status GetElem_L(LinkList L, int i, int &e)
{
LinkList p;
p = L->next;
int j = 1;//初始化
while (p&&j<i)//向后扫描，直到p指向第i个元素或者p为空
{
p = p->next;
++j;
}
if (!p || j > i)//第i个元素不存在
return ERROR;
e = p->data;//取出第i个元素
return OK;
}//GetElem_L
LNode *LocateElem1_L(LinkList L, int e)
{//返回L中值为e的元素的地址，查找失败返回NULL
LinkList p;
p = L->next;
while (p&&p->data!=e)
p = p->next;
return p;
}
int LocateElem2_L(LinkList L, int e)
{//返回L中值为e的元素的位置序号，查找失败返回0
LinkList p;
p = L->next;
int j = 1;
while (p&&p->data != e)
{
p = p->next;
j++;
}
if (p)
return j;
else
return 0;
}
Status ListInsert_L(LinkList &L, int i, int e)
{//在L中第i个元素前插入元素e
LinkList p,s;
p = L; int j = 0;
while (p&&j<i-1)
{
p = p->next;
++j;//寻找第i个结点
}
if (!p || j > i - 1)//i大于表长加1或者小于1
return ERROR;
s = new LNode;//生成新结点s
s->data = e;//将结点s的数据域置为e
s->next = p->next;//将结点s插入L中
p->next = s;
return OK;
}//ListInsert_L
Status ListDelete_L(LinkList &L, int i, int e)
{//将线性表L中的第i个元素删除
LinkList p,q;
p = L;
int j = 0;
while (p->next&&j<i-1)//寻找第i个结点，并令p指向其前驱
{
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;
}//ListDelete_L
void CreatList1_L(LinkList &L, int n)
{//前插法
LinkList p;
L->next = NULL;//先建立一个带头结点的单链表
for (int i=n ; i >0; --i)
{
p = new LNode;//生成新结点
cin>> p->data;//输入元素组
p->next = L->next;
L->next = p;//插入到表头
}
}//CreatList1_L
void CreatList2_L(LinkList &L, int n)
{//尾插法
LinkList p,r;
L->next = NULL;
r = L;//尾指针r指向头结点
for (int i = 0; i < n; ++i)
{
p = new LNode;//生成新结点
cin >> p->data;//输入元素值
p->next = NULL;
r->next = p;//插入到表尾
r = p;
}
}//CreatList2_L
