目前建设网站,中国移动积分商城,公司网站建设怎么入账,热点事件注#xff1a;本文只探讨带头结点的情况(查找思路类似循环找到第i-1 个结点的代码)
一.按位查找#xff1a;
1.代码演示#xff1a;
版本一#xff1a;
#includestdio.h
#includestdlib.h
//定义单链表结点类型
typedef struct LNo… 注本文只探讨带头结点的情况(查找思路类似循环找到第i-1 个结点的代码)
一.按位查找
1.代码演示
版本一
#includestdio.h
#includestdlib.h
//定义单链表结点类型
typedef struct LNode
{int data; //每个结点存放一个数据元素struct LNode *next; //指针指向下一个结点
}LNode,*LinkList;
//初始化一个单链表(带头结点)
bool InitList(LinkList L)
{L (LNode *)malloc( sizeof(LNode) ); //分配一个头结点if(LNULL) //代表内存不足分配失败--意味着带头结点的单链表无法创建 {return false;}else{L - next NULL; //头结点之后暂时还没有节点所以指向NULLreturn true; }
}
//判断单链表是否为空(带头结点)
bool Empty(LinkList L)
{if(L-nextNULL) //头结点之后如果指向NULL,代表没有数据 {return true;}else{return false;}
}
//按位查找返回第i个元素(带头结点即第0个结点)
LNode * GetElem(LinkList L,int i)
{if(i0){return NULL;}LNode *p; //指针p指向当前扫描到的结点 int j0; //当前p指向的是第几个结点j为0代表头结点 pL; //L指向头结点头结点是第0个结点(不存数据)while(p!NULL ji) //循环找到第i个结点 {p p-next;j;} return p;
}
int main()
{//声明一个指向单链表的指针LinkList L;//初始化一个空表InitList(L); return 0;
}
版本二王道书版本
#includestdio.h
#includestdlib.h
//定义单链表结点类型
typedef struct LNode
{int data; //每个结点存放一个数据元素struct LNode *next; //指针指向下一个结点
}LNode,*LinkList;
//初始化一个单链表(带头结点)
bool InitList(LinkList L)
{L (LNode *)malloc( sizeof(LNode) ); //分配一个头结点if(LNULL) //代表内存不足分配失败--意味着带头结点的单链表无法创建 {return false;}else{L - next NULL; //头结点之后暂时还没有节点所以指向NULLreturn true; }
}
//判断单链表是否为空(带头结点)
bool Empty(LinkList L)
{if(L-nextNULL) //头结点之后如果指向NULL,代表没有数据 {return true;}else{return false;}
}
//按位查找返回第i个元素(带头结点即第0个结点)
LNode * GetElem(LinkList L,int i)
{int j1; //代表p结点刚开始指向第一个结点(不是头结点) LNode *pL-next;if(i0){return L; //返回头结点 }if(i1){return NULL;}while(p!NULL ji) //循环找到第i个结点 {p p-next;j;} return p;
}
int main()
{//声明一个指向单链表的指针LinkList L;//初始化一个空表InitList(L); return 0;
} 2.返回第0个元素即头结点 3.返回的结点大于链表的长度
while循环进行到第5次时p指向NULL不满足下一次循环条件跳出while循环此时返回的p为NULL代表查找失败 最终可知当i值不合法时即i为负数或者i值大于链表长度时最终都返回NULL因此只需要判断返回结果是否为NULL即可
得知是否查找成功。
4.返回的结点在链表内 a.计算时间复杂度需要要查找的元素在合法范围内。
b.平均时间复杂度是指此次输入的i值它取的合法范围内的任何一个数字的概率都等可能的情况
具体的算法和顺序表的按位查找的分析方法一样。
5.封装
案例一GetElem用来获取第i个结点传入参数i-1即可找到第i-1个结点 案例二后插操作的加入 右下角的InsertNextNode函数中需要一个if(pNULL)进行是否为空指针的判断因为如果传入GetElem函数的i值不合法即i-1也不合法会导致p为NULL即空指针 二.按值查找
1.代码演示
按值查找操作只能从第一个结点开始循环依次向后查找
#includestdio.h
#includestdlib.h
//定义单链表结点类型
typedef struct LNode
{int data; //每个结点存放一个数据元素struct LNode *next; //指针指向下一个结点
}LNode,*LinkList;
//初始化一个单链表(带头结点)
bool InitList(LinkList L)
{L (LNode *)malloc( sizeof(LNode) ); //分配一个头结点if(LNULL) //代表内存不足分配失败--意味着带头结点的单链表无法创建 {return false;}else{L - next NULL; //头结点之后暂时还没有节点所以指向NULLreturn true; }
}
//判断单链表是否为空(带头结点)
bool Empty(LinkList L)
{if(L-nextNULL) //头结点之后如果指向NULL,代表没有数据 {return true;}else{return false;}
}
//按值查找找到数据域等于e的结点
LNode * LocateElem(LinkList L,int e)
{LNode *p L-next; //L代表头结点,L-next就是第一个节点此时p就是第一个结点 //从第一个结点开始查找数据域为e的结点(头结点不存数据,所以不从头结点开始)while(p ! NULL p-data ! e){p p-next;}//找到后返回该节点指针否则返回NULLreturn p;
}
int main()
{//声明一个指向单链表的指针LinkList L;//初始化一个空表InitList(L); return 0;
}
平均时间复杂度为O(n)。
2.图解
例一
p为第一个节点第一次循环时p不为NULL且p内部的值不为8符合循环条件指向p p-next即向后指一个元素 第二次循环时p内部的值为8不符合循环条件跳出while循环 例二 最终返回NULL代表不存在数据域为6的结点。
3.如果要找的数据域元素不是基本数据类型如结构体类型就需要复杂的判断
如结构体struct类型要用到运算符.访问每一个成员变量来比较。 三.求单链表的长度 四.总结
