线性链表
采用链式存储的线性表
存储特点：每个结点都分两部分
数据域：存储元素的值
指针域：存放直接前趋或直接后继元素的地址信息
链表的存储结构
链表的定义和初始化
struct LNode {
ElemType data; // 数据域，ElemType代表某种数据类型 struct LNode *next; // 指针域 } ; LNode* head; // 定义头指针 head = new LNode; // 定义头结点 head->next = NULL; // 头结点指针域为空 求单链表的长度
int Length( ) {
LNode *p=head->next; //p指向第一个元素所在结点 int len=0; while( p!=NULL ) {
//逐个检测p结点存在与否 len++; p=p->next; //指针后移 } return len; } 在链表的第i个位置插入新的结点
void Insert(LNode *head, int i, ElemType x) {
if(i<1) {
cout<<"不存在第"<<i<<"个位置"; } else {
LNode *p=head; //p最终将指向第i-1个结点 int k=0; //p目前指向第0个结点(头结点) while( p!=NULL&&k<i-1 ) {
p=p->next; k++; } if(p==NULL) cout<< i<<"超出链表最大可插入位置"; else {
LNode *s=new LNode; //建立新结点s s->data = x; s->next=p->next; //修改结点s的指针 p->next=s; //修改结点p的指针 } } } 从链表中删除第i个结点
从单链表中删除第i个结点
void Delete(LNode *head，int i ) {
if(i<1) cout<<”不存在第”<<i<<”个元素”; else {
LNode *p=head; //p指向头结点(第0个结点) LNode *q; //q和p最终分别指向第i-1和第i个结点 int k=0; while( p!=NULL&&k<i ) {
q=p; p=p->next; k++; } if(p==NULL) cout<< i<<”超出链表长度”; else {
q->next=p->next; //从链表中删除该结点 delete p; //释放结点p } } } 查找链表中的结点
LNode* Find(LNode *head, ElemType x ) {
LNode *p=head->next; //p指向第一个元素所在结点 while ( p!=NULL && p->data!=x ) p = p->next; return p; } 其它形式的链表
单向循环链表
将单链表尾结点的指针由NULL改为指向头结点，首尾连接
形成一个环形，简称为循环链表
双向链表
每个结点的指针域中再增加一个指针，使其指向该结点的直接前趋结点
这样构成的链表中有两个不同方向的链
双向循环链表
将双向链表的头结点的前趋指针指向尾结点
将尾结点的后继指针指向头结点
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/200585.html原文链接：https://javaforall.net
