1链表概念
链表是线性表的链式存储方式,逻辑上相邻的数据在计算机内的存储位置不相邻,可以给每个元素附加一个指针域,指向下一个存储位置,如图所示:
2链表的要素
一个链表的节点包括两个部分组成
1 数据域: 储存数据
2 指针域: 指向下一个节点的内存地址
单链表的结构:
双链表的结构(此章节不细说):
单链表的结构体的定义:
typedef struct LinkNode
{
int data; //结点的数据域
struct LinkNode *next; //结点的指针域
}LinkNode, LinkList; //链表节点、链表
3单链表的算法实现
(1)单链表的初始化
typedef struct _LinkNode_
{
int data; //结点的数据域
struct LinkNode *next; //结点的指针域
}LinkNode, LinkList; //链表节点、链表
bool InitList(LinkList* &L)//构造一个空的单链表 L
{
L=new LinkNode; //生成新结点作为头结点，用头指针 L 指向头结点
if(!L)return false; //生成结点失败
L->next=NULL; //头结点的指针域置空
return true;
}
(2)单链表增加元素
<1>前插法
//前插法
bool ListInsert_front(LinkList* &L, LinkNode * node)
{
if(!L || !node ) return false;
node->next = L->next;
L->next = node;
return true;
}
<2>尾插法
//尾插法
bool ListInsert_back(LinkList* &L, LinkNode *node)
{
LinkNode *last = NULL;
if(!L || !node ) return false; //找到最后一个节点
last = L;
while(last->next) last=last->next; //新的节点链接到最尾部
node->next = NULL;
last->next = node;
return true;
}
<3>任意位置插法
//任意位置插法
bool LinkInsert(LinkList* &L, int i, int &e)//单链表的插入
{
//在带头结点的单链表 L 中第 i 个位置插入值为 e 的新结点
int j;
LinkList *p, *s;
p=L;
j=0;
while (p&&j<i-1) //查找第 i-1 个结点，p 指向该结点
{
p=p->next;
j++;
}
if (!p || j>i-1)//i＞n+1 或者 i＜1
{
return false;
}
s=new LinkNode; //生成新结点
s->data=e; //将新结点的数据域置为 e
s->next=p->next; //将新结点的指针域指向结点 ai
p->next=s; //将结点 p 的指针域指向结点 s
return true;
}
(3)单链表的遍历
void LinkPrint(LinkList* &L) //单链表的输出
{
LinkNode* p;
p=L->next;
while (p)
{
cout <<p->data <<"\t";
p=p->next;
}
cout<<endl;
}
(4)单链表的获取元素
bool Link_GetElem(LinkList* &L, int i, int &e)//单链表的取值
{
//在带头结点的单链表 L 中查找第 i 个元素
//用 e 记录 L 中第 i 个数据元素的值
int j;
LinkList* p;
p=L->next;//p 指向第一个结点，
j=1; //j 为计数器
while (j<i && p) //顺链域向后扫描，直到 p 指向第 i 个元素或 p 为空
{
p=p->next; //p 指向下一个结点
j++; //计数器 j 相应加 1
}
if (!p || j>i)
{
return false; //i 值不合法 i＞n 或 i<=0
}
e=p->data; //取第 i 个结点的数据域
return true;
}
(5)单链表的查找元素
bool Link_FindElem(LinkList *L, int e) //按值查找
{
//在带头结点的单链表 L 中查找值为 e 的元素
LinkList *p;
p=L->next;
while (p && p->data!=e)
{
//顺链域向后扫描，直到 p 为空或 p 所指结点的 数据域等于 e
p=p->next; //p 指向下一个结点
}
if(!p)return false; //查找失败 p 为 NULL
return true;
}
(6)单链表的删除元素
bool LinkDelete(LinkList* &L, int i) //单链表的删除
{
//在带头结点的单链表 L 中，删除第 i 个位置
LinkList *p, *q;
int j;
p=L;
j=0;
while((p->next)&&(j<i-1)) //查找第 i-1 个结点，p 指向该结点
{
p=p->next; j++;
}
if (!(p->next)||(j>i-1))//当 i>n 或 i<1 时，删除位置不合理
return false;
q=p->next; //临时保存被删结点的地址以备释放空间
p->next=q->next; //改变删除结点前驱结点的指针域
delete q; //释放被删除结点的空间
return true;
}
(7)单链表的销毁
void LinkDestroy(LinkList* &L) //单链表的销毁
{
//定义临时节点 p 指向头节点
LinkList *p = L;
cout<<"销毁链表!"<<endl;
while(p)
{
L=L->next; //L 指向下一个节点
cout<<"删除元素: "<<p->data<<endl;
delete p; //删除当前节点
p=L; //p 移向下一个节点
}
}
[奇牛学院]