数据结构---单链表的基本操作代码块

89 阅读 0 评论 59 点赞

我是靠谱客的博主懵懂胡萝卜，最近开发中收集的这篇文章主要介绍数据结构---单链表的基本操作代码块，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

单链表的基本操作
//定义
typedef struct LNode
{
ElemType data;
//数据域
struct LNode *next;
//指针域
}LNode , *LinkList;
//初始化
Status InitList(LinkList &L)
{
L = new LNode;
//生成一个新结点
L->next = NULL;
//结点指针域置空
return ok;
}
//判空
Status Empty(LinkList L)
{
return (L->next == NULL);
}
//表长
int Length(LinkList L)
{
int len = 0;
LNode *p = L;
while (!p->next)
{
p = p->next;
len++;
}
return len;
}
//取值，在L表中，取第i个元素的值，并用e带回
Status GetElem(LinkList L, int i, ElemType &e)
{
LNode *p = L->next;
//定义一个结点类型的指针p，指向首元结点
int j = 1;
//p指向头结点j为1,记录p扫描的结点数
while (p && j < i - 1)
//p不为空且还没到i - 1个元素时
{
p = p->next;
//p顺着链域继续找
j++;
}
if (!p)
//p为空，返回error
return error;
e = p->data;
//找到了，就把该结点的数据域赋给e
return ok;
}
//按值查找, 在单链表中查找元素值为e的结点
LNode *LocateElem(LinkList L, ElemType e)
{
LNode *p = L->next;
//p指向首元结点
while (p && p->data != e)
//p不为空且p所指结点的数据域不等于e
p = p->next;
//p继续向下查找
return p;
}
//按位查找,返回第i个元素
LNode *GetElem(LinkList L, int i)
{
LNode *p ;
p = L;
//p指向头结点
int j = 0;
if (i == 1)
//查找第一个元素，就返回头结点
return L;
if (i < 1)
//i < 1位置不合法
return NULL;
if (p || j < i )
//p不为空且j小于i，p向下继续找
{
p = p->next;
j++;
}
return p;
//找到了，返回P
}
//插入算法，在L的第i个元素中插入e
Status ListInsert(LinkList L, int i, ElemType e)
{
LNode *p = L;
//定义一个结点类型的指针P指向头结点
int j = 0;
//记录p所扫描的结点数
while (p && j < i - 1)
{
p = p->next;
j++;
}
if (!p || j > i - 1)
return error;
LNode *s;
//将插入的元素，存放在一个s的新结点
s = new LNode;
//为新结点new一个结点空间
s->data = e;
//把e存放在新结点的数据域
s->next = p->next;
//将ai结点的地址存放在新结点的next域
p->next = s;
//再把新结点的地址存放在ai-1的next域
return ok;
}
//删除
//ListDelete(&L,i,&e)：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值
//1、查找结点ai-1（要删除结点的前驱结点）,并由指针p指向该结点；
//2、临时保存待删除结点a1的地址在q中，以备释放；
//3、将结点*p的指针域指向ai的直接后继结点；
//4、释放结点ai的空间。
Status ListDelete(LinkList &L, int i, ElemType &e)
{
LNode *p, *q;
//p指向当前扫描的结点
int j = 0;
//记录当前结点p指向第几个结点
p = L;
//L指向头结点，第0个结点（不存数据）
while (p->next && j < i- 1)
//循环找到删除结点的前驱结点，即第i-1个结点
{
p = p->next;
j++;
}
if (!p->next || j > i - 1)
//位置不合法
return error;
q = p->next;
//q指向被删除的结点
p->next = q->next;
//将*q结点从链中断开
e = q->data;
//用e返回元素的值
delete q;
//释放结点空间
return ok;
}
//输出
Status DispLsit(LinkList L)
{
LNode *p;
p = L->next;
while (p)
{
cout << p->data << ' ';
p = p->next;
}
cout << endl;
return ok;
}
//头插法
void CreatList_H(LinkList &L, int n)
{
L = new LNode ;
L->next = NULL;
//建立一个带头结点的单链表
for (int i = 0; i < n; i++)
{
LNode *p = new LNode;
//生成新结点*p
cin >> p->data;
//输入元素值赋给新结点的数据域
//将新结点插入到头结点之后
p->next = L->next;
L->next = p;
}
}
//尾插法
void CreatList_R(LinkList &L, int n)
{
L = new LNode ;
L->next = NULL;
//创建一个到头结点的空链表
LNode *r = L;
//尾指针指向头结点
for (int i = 0; i < n; i++)
{
LNode *p = new LNode;
//生成新结点
cin >> p->data;
//输入元素值赋给新结点*p的数据域
//将新结点*p插入到尾结点*r之后
p->next = NULL;
r->next = p;
r = p;
//r指向新的尾结点*p
}
}
//销毁
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;
delete p;
p = q;
}
L->next = NULL;
//头结点指针域为空
return ok;
}