苏州住房建设局网站首页,美术馆展厅设计方案,广州网站建设选哪家,桂林seo第二弹火爆来袭中
这波是单链表的内容整理#xff0c;废话不多说#xff0c;上小龙虾呀(又到了龙虾季节了#xff0c;哎#xff0c;口水直流了~~) beautiful的分割线 文章目录 第二弹火爆来袭中这波是单链表的内容整理#xff0c;废话不多说#xff0c;上小龙虾呀(又到了…第二弹火爆来袭中
这波是单链表的内容整理废话不多说上小龙虾呀(又到了龙虾季节了哎口水直流了~~) beautiful的分割线 文章目录 第二弹火爆来袭中这波是单链表的内容整理废话不多说上小龙虾呀(又到了龙虾季节了哎口水直流了~~)...线性表的链式表示定义链表种类链表的表示链表的特点单链表表示方法单链表的初始化判断链表是否为空单链表的销毁(头结点也不存在了)清空单链表(头指针和头结点还在)求单链表的表长取单链表中第i个元素的内容单链表中的按值查找单链表的插入操作单链表的删除操作单链表的查找、插入、删除时间效率单链表的建立 ... TO BE CONTINUED... …
线性表的链式表示
定义
用一组物理位置任意的存储单元来存放线性表的数据元素存储单元对连续性没要求可零散分布链表的每个节点由 数据指针 组成
eg: 26个英文字母小写存储 链表种类
单链表双链表循环链表 链表的表示 头指针是指向链表中第一个结点的指针 首元结点是指链表中存储第一个数据元素a1的结点 头结点是在链表的首元结点之前附设的一个结点 链表存储的时候可以选择带和不带头节点 好处 便于首元结点的处理(链表的第一个数据也能有往前的指针处理起来和后面的正常元素就一样了)便于空表和非空表的统一处理如下(第二种方案) 头结点的数据域可以为空也可以放线性表长度等附加信息但此节点不能计入链表长度值。
链表的特点
存储上位置任意不需要相邻访问元素时只能通过头指针进入链表并扫描剩下每个节点直到找到目标找到第一个节点和最后一个节点的时间不等 顺序表– 随机存取链表– 顺序存取(找第i个元素时必须从第一个元素一直到i-1个元素再到元素i)
单链表
表示方法
单链表由表头唯一确定可以用头指针的名字来命名头指针为L则把链表称为表L.
存储结构 typedef struct Lnode{ //声明结点的类型和指向结点的指针类型ElemType data; //结点的数据域struct Lnode *next; //结点的指针域(嵌套了)
}Lnode,*LinkList; //LinkList为指向结构体Lnode的指针类型LinkList L; //定义链表L
Lnode *p; //定义节点指针p (可以用linkList p 但是不推荐)例子存储学生的学号姓名成绩的单链表
// 通常定义法
typedef Struct {char num[8]; //数据域char name[8]; //数据域int score; //数据域
} ElemType;typedef struct Lnode{ElemType data; //数据域struct Lnode *next; //指针域
}Lnode, *LinkListLinklist L; 单链表的初始化
Status InitList_L(LinkList L){Lnew LNode; // C or C语言 L(LinkList) malloc (sizeof (LNode))L-nextNULL;return OK;
}判断链表是否为空
int ListEmpty(LinkList L){ //空表返回1否则返回0if(L-next) //非空return 0;elsereturn 1;
}单链表的销毁(头结点也不存在了)
Status DestroyList_L(LinkList L){Lnode *p;while(L){pL;LL-next;delete p; // C 用法 or C用法 free p;}return OK;
}清空单链表(头指针和头结点还在)
依次从首元结点开始释放所有节点最后将头结点的指针域设为空 Status EmptyList_L(LinkList L){Lnode *p,*q;pL-next;while (p){qp-next;delete p;pq;}L-nextNULL;return OK;
}求单链表的表长
int List_Length(LinkList L){Lnode *p;pL-next; //p指向第一个节点首元结点i0;while (p){ //遍历单链表统计节点数i;pp-next}return OK;
}取单链表中第i个元素的内容
思路从头指针触发顺着链域next逐个往下搜索直到搜索到第i个节点为止因此链表不是随机存取结构需判断找不到的情况和i的正确取值情况。
Status GetElem_L(LinkList L, int i, ElemType e){pL-next;j1; //初始化p指向首元结点j来累计遍历过的位置while (!p ji){ //向后扫描直到p指向第i个元素或者p为空时pp-next;j; //注意这里是前加加返回的是自增后的j, j 后加加是返回自增前的j}if (!p || j i) return ERROR; //p指向空节点或者i各元素不存在时返回ERRORep-data;return OK;
}//GetElem_L单链表中的按值查找 返回该数据所在位置(改数据地址) Lnode *LocateElem_L(LinkList L, ElemType e){
//在单链表中查找元素为e的数据元素找到后返回e的地址未找到返回NULLpL-next;while (p p-data!e){pp-next;}return p;
}返回该数据所在的位置序号(第几个元素) int LocateElem_L(LinkList L, ElemType e){
// 使用计数器i返回查找到的位置pL-next;j1;while (p p-data!e){pp-next;j;}if (p) return j; //p非空情况下的i才有意义else return 0;
}单链表的插入操作
在第i个节点前插入值为e的新节点 - 找前趋 //单链表的插入操作在第i个位置插入元素数据域为e的元素
Status ListInset_L(LinkList L, int i, ElemType e){pL;j0 //初始化p指向头结点计数器为0while (p ji-1) {pp-next; j;} //寻找i-1节点if (!p || ji-1) return ERROR; //当p为空时p已经指向了表长1的节点位置此时插入位置变为表长2这种情况不允许所以这里排除掉了插入位置大于表长1位置和i小于1的不合理情况。snew Lnode;s-datae; // 创建即将插入的新节点ss-nextp-next; // s指向原来的i节点p-nexts; //i-1节点指向新节点sreturn OK;
}//ListInset_L单链表的删除操作
删除第i各元素 - 找前趋 Status List_Delete_L(LinkList L, int i, ElemType e){pL;j0; Lnode *q; //初始化p指向头结点计数器清零while(p-next ji-1) {pp-next; j;} //寻找i-1元素注意此处判定改为了p-next, 当p-next为NULL时说明i-1个元素已经是表的最后一个元素,那么要删除的i元素就是表长1的元素而它是不存在的if(!p-next || ji-1) return ERROR; // 排除不合理的i元素qp-next; eq-data; //将待删除元素信息做保留p-nextq-next; // i-1元素指向i1元素delete q; //删除指针return OK;
}//ListDelete_L单链表的查找、插入、删除时间效率 查找 - 时间效率为O(n) 插入/删除 单个操作并不会移动元素只是动指针时间效率为O(1) 查找并操作时时间效率为O(n)
单链表的建立 头插法 - 元素倒序依次插入链表头结点后面 从一个空表开始重复读入数据 生成新节点将读入数据放入新节点的数据域中 从最后一个节点开始依次将各节点插入到链表的前端 算法时间复杂度O(n) //头插法创建单链表Void CreateList_H(LinkList L, int n){Lnew Lnode; L-nextNULL; //建立一个带头结点的单链表for (in;i0;--i){ //循环倒序插入所有元素pnew Lnode; //生成(C)新节点p(Lnode*)malloc(sizeof(Lnode));cinp-data; //输入(C)元素值scanf(p-data)p-nextL-next;L-nextp;}}//CreateList_H尾插法 - 新元素正序依次插入末尾 从一个空链表L开始新节点依次插入链表尾部尾指针r指向链表尾结点 初始时r/L都指向头结点。每读取一个数据元素则申请一个新节点并插入尾结点后r指向新的尾结点。 算法时间复杂度O(n) //尾插法创建单链表Void CreateList_R(LinkList L, int n){Lnew Lnode; L-nextNULL; //创建空单链表rL; // 尾指针初始化等于头结点for (i0;in;i){ //依次正序添加节点pnew Lnode; cinp-data;p-nextNULL; //新节点的指针域置空作为新的尾结点 r-nextp; //新节点链接前一个节点rp; //尾指针移动到新尾结点}}//CreateList_R…
TO BE CONTINUED…
