单链表实现及操作
相关操作的函数传递运用了C++的引用
初始定义
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef int ElemType;
//类型定义
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode,*LinkList;
单链表创建并初始化
头插法
void CreateList_L1(LinkList &L,int n){//带头结点的单链表(头插法) L为头结点 n为元素个数
LinkList p;
L = (LinkList)malloc(sizeof(LNode)); //为分配头结点空间
L->next = NULL;
for(int i=0;i<n;i++){
p = (LinkList)malloc(sizeof(LNode));
scanf("%d",&p->data);
//核心代码
p->next = L->next;
L->next = p;
}
}
尾插法
void CreateList_L2(LinkList &L,int n){//带头结点的单链表(尾插法) L为头结点 n为元素个数
LinkList p,tail;
L = (LinkList)malloc(sizeof(LNode));
L->next = NULL;//初始化为空链表
tail = L;//tail为尾指针
for(int i = 0;i<n;i++){
p = (LinkList)malloc(sizeof(LNode));
scanf("%d",&p->data);
//核心代码
tail->next = p;
tail = p;
}
tail->next = NULL; //最后结点的next置空
}
获取单链表的长度
int GetLength_L(LinkList L){//获取单链表的长度 传参为头结点
LinkList p = L->next;
int len = 0;
while(p){ //当p!=NULL时
len++;
p = p->next; //指向下一结点
}
return len; //返回单链表长度
}
单链表遍历输出
void OutputList_L(LinkList L){//单链表输出
LinkList p;
p = L->next;
while(p!=NULL){ //p!=NULL时
printf("%d ",p->data);
p = p->next; //指向下一结点
}
}
判断是否为空
Status ListEmpty_L(LinkList L){//判断单链表是否为空
if(L->next==NULL)
return TRUE;
else
return FALSE;
}
获取元素操作
获取第i个元素值 并用e接收
Status GetElem_L(LinkList L,int i,int &e){//获取第i个元素 其值赋给e 返回OK
LinkList p;
p = L->next;
int j = 1;//j为计数器
//if(p)等价于p!=NULL if(!p)等价于p==NULL
while(p&&j<i){ //遍历到第i个元素位置
p = p->next;
j++;
}
if(!p||j>i){ //不符合条件
return ERROR;
}
e = p->data; //取第i个元素
return OK;
}
删除操作
删除第i个元素 用e返回其值
Status ListDelete_L(LinkList &L,int i,int &e){//在带头结点的单链线性表L中 删除第i个元素 并由e返回其值
LinkList p;
p = L->next;
int j = 1;
while(p->next&&j<i-1){ //寻找第i-1个结点
p = p->next;
j++;
}
if(!(p->next)||j>i-1){ //不存在元素或p->next = NULL
return ERROR;
}
LinkList q;
q = p->next; //应删除位置
p->next = q->next; //调整删除元素前后位置的指针
e = q->data; //用e返回删除元素
free(q);
return OK;
}
插入操作
在单链表的第i个位置之前插入元素e
Status ListInsert_L(LinkList &L,int i,int e){
LinkList p;
p = L->next;
int j = 1;
//这里也可以写为：p = L; int j = 0;
while(p&&j<i-1){ //寻找第i-1个结点
p = p->next;
j++;
}
if(!p||j>i-1){
return ERROR;
}
LinkList s;
s = (LinkList)malloc(sizeof(LNode)); //为增加元素分配空间
s->data = e;
//插入核心代码
s->next = p->next;
p->next = s;
return OK;
}
整表删除
Status ClearList_L(LinkList &L){//单链表的整表删除
LinkList p,q;
p = L->next; //指向头结点的下一节点
while(p){ //p不为NULL时
q = p->next;
free(p); //释放结点
p = q;
}
L->next = NULL; //将头结点的next指针置NULL
return OK;
}
——————END——————
作者注：
记录学习，分享经验。
有兴趣可以关注博主，以后还会持续更新内容哦~