IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 单链表笔记 -> 正文阅读

[数据结构与算法]单链表笔记

单链表

代码定义

typedef struct LNode
{
 ?ElemType data;            //值域
 ?struct LNode *next;       //定义域
}LNode,*LinkList;
?
//等价于
struct LNode{
 ? ?ElemType data;
 ? ?struct LNode *next;
};
typedef struct LNode LNode;
typedef struct LNode *LinkList;
//要表示一个单链表时,只需要申明一个头指针L,指向单链表的第一个节点
 
LNode *L                    //强调这是一个节点
LinkList L ? ==>二者等价     ?//强调这是一个链表
 ? ?
//初始化
 ? ?
//不带头节点
bool InitList(LinkList &L){
 ? ?L=NULL;
 ? ?return true;
}
?
//带头结点
bool InitList(LinkList &L){
 ? ?L=(LNode *)malloc(sizeof(LNode));   //分配一个头节点
 ? ?if(L==NULL)                      ?//分配失败
 ? ? ? ?return false;
 ? ?L->next=NULL:                    ?//头节点之后暂时没有节点
 ? ?return true;            
}
?
void test(){
 ? ?LinkList L;     //声明一个指向单链表的指针
 ? ?InitList(L);    //初始化
}

单链表的插入与删除

带头节点的单链表插入

//带头节点的单链表插入
/*
    在第i个位置进行插入一个数值,首先找到第i-1个节点,然后进行插入操作
*/
?
typedef struct LNode
{
 ?ElemType data;            //值域
 ?struct LNode *next;       //定义域
}LNode,*LinkList;
?
//在第i个位置插入元素e
bool ListInsert(LinkList &L,int i,ElemType e){
 ? ?//判断位置是否合理,i>=1
 ? ?if(i<1)
 ? ? ? ?return false;
 ? ?//声明一个指针指向头节点,与头指针一样
 ? ?LNode *p;
 ? ?p=L;
 ? ?//找到第i-1个节点
 ? ?int j=0;        //记录当前位置
 ? ?while(p!=NULL && j<i-1){
 ? ? ? ?p-p->next;
 ? ? ? ?j++;
 ?  }
 ? ?//if(p==NULL)
 ? ?// ?  return false;     //i值不合法
 ? ?//LNode *s=(LNode *)malloc(sizeof(LNode));
 ? ?//s->data=e;
 ? ?//s->next=p->next;
 ? ?//p->next=s;
 ? ?//return  true;
 ? ?return InsertNextNode(p,e);
}
?
//平均时间复杂度 ? O(n)

指定节点的后插操作

//指定节点的后插操作
//后插操作,在p节点之后插入元素e
bool InsertNextNode(LNode *p,ElemType e){
 ? ?if(p==NULL)
 ? ? ? ?return false;
 ? ?LNode *s=(LNode *)malloc(sizeof(LNode));    //申请一个节点
 ? ?if(s==NULL)
 ? ? ? ?return false;                        ?//申请失败
 ? ?s->data=e;
 ? ?s->next=p->next;
 ? ?p->next=s;
 ? ?return true;
}
//时间复杂度 ? O(1)

指定节点的前插操作

//思路:进行后插,交换节点里面的值
bool InsertPriorNode(LNode *p,ElemType e){
 ? ?if(p==NULL)
 ? ? ? ?return false;
 ? ?LNode *s=(LNode *)malloc(sizeof(LNode));    //申请一个节点
 ? ?if(s==NULL)
 ? ? ? ?return false;                        ?//申请失败
 ? ?//插入节点
 ? ?s->next=p->next;
 ? ?p->next=s;
 ? ?//交换数值
 ? ?s-data=p->data;
 ? ?p-data=e;
 ? ?return true;
}
//时间复杂度  O(1)

带头节点的单链表删除

//按位序删除
bool ListDelete(LinkList &L,int i,ElemType &e){
 ? ?if(i<1)
 ? ? ? ?return fasle;
 ? ?//找到第i-1个节点
 ? ?LNode *p;
 ? ?p=L;
 ? ?int j=0;
 ? ?while(p!=NULL && j<i-1){
 ? ? ? ?p=p->next;
 ? ? ? ?j++;
 ?  }
 ? ?if(p==NULL)
 ? ? ? ?return false;           //i不合法
 ? ?LNode *q=p->next;
 ? ?p->next=q->next;
 ? ?e=q->data;
 ? ?free(q);
 ? ?return true;
}
//平均时间复杂度  O(n)
?
//指定节点的删除
bool DeleteNode(LNode *p,ElemType e){
 ? ?//由于找前驱节点非常麻烦,所以找到后继节点,交换值,然后释放后继节点
 ? ?LNode *q=p->next;
 ? ?e=p->data;
 ? ?p->data=q->data;
 ? ?p->next=q->next;
 ? ?free(q);
 ? ?return true;
 ? ?
 ? ?//时间复杂度  O(1)
 ? ?
}

单链表的查找

按值查找 LocateElem(L,e)

//按值查找
LNode * LocateElem(LinkList L,ElemType e){
 ? ?LNode *p;
 ? ?p=L;        //p指向头节点
 ? ?p=p->next;
 ? ?while(p!=NULL && p->data!=e){
 ? ? ? ?p=p->next;
 ?  }
 ? ?return p;
}
?
//平均时间复杂度 ? O(n)

按位查找 GetElem(L,i)

//按位查找,返回第i个元素(带头结点)
LNode * GetElem(LinkList L,int i){
 ? ?if(i<0)
 ? ? ? ?return NULL;
 ? ?LNode *p;       //表示当前扫描到的节点
 ? ?int j=0;        //当前p指向第几个节点
 ? ?p=L;
 ? ?while(p!=NULL && j<i){
 ? ? ? ?p=p->next;
 ? ? ? ?j++;
 ?  }
 ? ?return p;
}//时间复杂度  O(n)

单链表长度

//求单链表的长度
int Length(LinkList L){
 ? ?int len=0;      //长度
 ? ?LNode *p=L;
 ? ?while(p->next!=NULL){
 ? ? ? ?p=p->next;
 ? ? ? ?len++;
 ?  }
 ? ?return len;
}
//时间复杂度 ? O(n)

单链表的建立

you have many numbers,you should fix it in a LinkList

step 1:初始化一个单链表

step 2:每次取一个数据元素,插入到表头/尾

头插法

//插入表头
//每次对头节点进行后插操作
LinkList List_HeadInsert(LinkList &L){
 ? ?//建立头节点
 ?  L=(LinkList)malloc(sizeof(LNode));
 ? ?L->next=NULL;
 ? ?int x;
 ? ?scanf("%d",&x);
 ? ?LNode *s=L;     //指针指向头节点
 ? ?while(x!=9999){
 ? ? ? //s申请一个新的空间
 ?   ? ?s=(LNode *)malloc(sizeof(LNode));
 ? ? ? ?s->data=x;
 ? ? ? ?s->next=L->next;
 ? ? ? ?L->next=s;
 ? ? ? ?scanf("%d",&x);
 ?  }
 ? ?return L;
}
?
//时间复杂度 ? O(n)

尾插法

//尾插法建立单链表,带头结点
//思路:首先建立一张空表,然后建立两个指针r,s都指向头节点,s每次申请一个新节点进行插入,r始终指向尾部
LinkList List_TailInsert(LinkList &L){
 ? ?L=(LinkList)malloc(sizeof(LNode));  //头节点
 ? ?LNode *s,*r;
 ? ?r=s=L;                          //都指向头节点
 ? ?int x;
 ? ?scanf("%d",&x);
 ? ?while(x!=9999){
 ? ? ? ?//进行后插
 ? ? ? ?//s申请一个新的节点
 ? ? ? ?s=(LNode *)malloc(sizeof(LNode));
 ? ? ? ?s->data=x;
 ? ? ? ?r->next=s;
 ? ? ? ?r=s;
 ? ? ? ?scanf("%d",&x);
 ?  }
 ? ?r->next=NULL;
 ? ?return L;
}
?
//时间复杂度 ? O(n)
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-07-11 16:51:09  更:2021-07-11 16:52:16 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/25 17:53:46-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码