做网站申请个体户,百度助手,企业网站建设word,推广普通话手抄报句子十六.循环链表
概念 循环链表是一种头尾相接的链表#xff08;最后一个结点的指针域指向头结点#xff0c;整个链表形成一个环#xff09;优点 从表任一结点出发均可找到表中其他结点判断终止 由于循环链表中没有NULL指针#xff0c;所以涉及遍历操作时#xff0c;终止条…十六.循环链表
概念 循环链表是一种头尾相接的链表最后一个结点的指针域指向头结点整个链表形成一个环优点 从表任一结点出发均可找到表中其他结点判断终止 由于循环链表中没有NULL指针所以涉及遍历操作时终止条件不像非循环链表那样判断p或p-next是否为空而是是否等于头指针循环条件从pNULL到pLp-nextNULL到p-nextL单循环链表时间复杂度 头指针表示单循环链表 找a~1的时间复杂度O1找a~n的时间复杂度On 注意 表的操作常常在表的首尾位置上进行尾指针表示单循环链表 a~1的存储位置是R-next-nexta~n的存储位置是R时间复杂度均为O1 LinkList Connect(LinkList Ta,LinkList Tb) //假设Ta.Tb都是非空的单循环链表
{vpTa-next; //p存表头结点Ta-nextTb-next-next; //Tb表头连接Ta表尾delete Tb-next; //释放Tb表头结点Tb-nextp; //修改指针return Tb;
}
十七.双向链表
双向链表的由来 查找某结点的后续结点的执行时间O(1) 单链表结点-有指示后继的指针域-后继结点查找某结点的前驱结点的执行时间On - -无指示前驱的指针域-依次寻找前驱结点双向链表的概念 在单链表的每个结点里再增加一个指向其直接前驱的指针域prior这样链表就形成了有两个方向不同的链。双向链表的特点 双向链表也有循环表 让头结点的前驱指针指向链表的最后一个节点让最后一个节点的后继指针指向头结点双向链表结构的对称性 p-prior-nextpp-next-prior在双向链表中有些操作如ListLength、GetElem等因仅涉及一个方向的指针所以它们的算法与线性链表的相同。在插入、删除时则需同事修改两个方向上的指针两个的操作的时间复杂度都为On。
双向链表的插入
void ListInsert_DuL(DuLinkList L,Init i,ElemType e) //在带头结点的双向循环链表L中第i个位置之前插入元素e
{if(!(pGetElemP_DuL(L,i)))return ERROR;snew DuLNOde;s-datee;s-priorp-prior;p-prior-nexts;s-nextp;p-priors;return OK;
}//ListInsert_Dul
双向链表的删除
void ListDelete_DuL(DuLinkList L,Init i,ElemType e) //删除带头节点的双向循环链表L的第i个元素并返回e
{if(!(pGetElemP_DuL(L,i)))return ERROR;ep-data;p-prior-nextp-next;p-next-priop-prior;free(p)return OK;
}//ListDelete_Dul
十八.单链表循环链表和双向链表的时间效率比较 时间效率的比较 查找表头结点首元结点 查找表尾结点 查找结点*P的前驱结点 带头结点的单链表L L-next 时间复杂度O(1) 从L-next依次向后遍历时间复杂度O(n) 通过p-next无法找到其前驱 带头结点仅设头指针L的循环单链表 L-next 时间复杂度O(1) 从L-next依次向后遍历时间复杂度O(n) 通过p-next可以找到其前驱 时间复杂度O(n) 带头结点仅设尾指针R的循环单链表 R-next| 时间复杂度O(1) R 时间复杂度O(1) 通过p-next可以找到其前驱 时间复杂度O(n) 带头结点的双向循环链表L L-next 时间复杂度O(1) L-prior 时间复杂度O(1) p-prior 时间复杂度O(1)
十九.顺序表和链表的比较
链式存储结构的优点 节点空间可以动态申请和释放数据元素的逻辑次序靠节点的指针来指示插入和删除时不需要移动数据元素链式存储结构的缺点 存储密度小每个结点的指针域需额外占用存储空间。当每个节点的数据域所占字节不多时指针域所占存储空间的比重闲得很大。 存储密度 概念 结点数据本身所占的存储量和整个节点结构所占的存储量之比公式 存储密度结点数据本身占用的空间/结点占用的空间总量比较 顺序表存储密度1链式小于1。链式存储结构是非随机存储结构。对任一结点的操作都要从头指针依指针链查找到该结点增加了算法的复杂度。顺序表和链表比较图 比较项目\存储结构 顺序表 链表 空间-存储空间 预先分配导致空间闲置或溢出现象 动态分配不会出现存储空间闲置或溢出现象 空间-存储密度 不用为表示结点间的逻辑关系而增加额外的存储开销存储密度等于1 需要借助指针来体现元素间的逻辑关系存储密度小于1. 时间-存取元素 随机存储按位置访问元素的时间复杂度O(1) 顺序存储按位置访问元素时间复杂度O(n) 时间-插入、删除 平均移动约表中一半元素时间复杂度O(n) 不需要移动元素确定插入删除位置后时间复杂度O 适用情况 表长变化不大能事先确定变化的范围。很少进行插入或删除操作经常按元素位置序号访问数据元素。 长度变化较大频繁进行插入或删除操作
二十.线性表的应用
线性表的合并 问题 假设利用两个线性表La和Lb分别表示两个集合A和B,现要求一个新的集合AAUB解决
void union(List La,List Lb)
{La_lenListLength(La);Lb_lenListLength(Lb);for(i1;iLb_len;i){GetElem(Lb,i,e);if(!LocateElem(La,e))ListInsert(La,La_len,e); }
} //算法的时间复杂度是O(ListLength(La)*ListLength(Lb))
有序表的合并 问题 已知线性表La和Lb中的数据元素按值非递减有序排列现要求LA和Lb归并为一个新的线性表LcLc中的数据元素扔按值非递减有序排列。解决 创建一个空表Lc依次从La或Lb中“摘取”元素值较小的节点插入到Lc表的最后直到其中一个表边空为止继续将La或Lb其中一个表的剩余节点插入在Lc表的最后
用顺序表来实现
void MergeList_Sq(SqList LA,SqList Lb,SqList LC)
{paLA.elem;pbLB.elem; //指针pa和pb的初值分别指向两个表的第一个元素LC.lengthLA.lengthLB.length; //新表长度为待合并量表的长度之和LC.elemnew ElemType[LC.length]; //为合并后的新表分配一个数组空间pcLC.elem; //指针pc指向新表的第一个元素pa_lastLA.elemLA.length-1; //指针pa_last指向LA表的最后一个元素pb_lastLB.elemLB.length-1; //指针pa_last指向LB表的最后一个元素while(papa_last pbpb_last) //两个表都非空{if(*pa*pb)*pc*pa; //依次“摘取”两表中的最小值else *pc*pb; }while(papa_last)*pc*pa; //LB表已到达表尾将LA中剩余元素加入LCwhile(pbpb_last)*pc*pb; //LA表已到达表尾将LB中剩余元素加入LC
} //MergeList_Sq//算法的时间复杂度是O(ListLength(La)*ListLength(Lb))
用链表来实现
void MergeList_L(SqList La,SqList Lb,SqList Lc)
{paLa-next;pbLb-next;pcLcLa; //用La的头结点作为Lc的头结点while(papb){if(pa-datapb-data){pc-nextpa;pcpa;papa-next; } else{pc-nextpb;pcpb;pbpb-next; } }pc-nextpa?pa:pb //插入剩余段delete Lb; //释放Lb的头结点
} //算法的时间复杂度是O(ListLength(La)*ListLength(Lb))
一元多项式的运算 多项式创建创建一个只有头结点的空链表根据多项式的项的个数n循环n次执行以下操作 生成一个新结点*s输入多项式当前项的系数和指数赋给新节点*s的数据域设置一前驱指针pre用于指向待找到的第一个大于输入项指数的结点的前驱pre初值指向头结点。指针q初始化指向首元结点循链向下逐个比较链表中当前结点与输入项指数找到第一个大与输入项指数的节点*q将输入项结点*s插入到结点*q之前
void CreatePolyn(Polynomial P,int n) //输入m项的系数和指数建立表示多项式的有序链表P
{Pnew PNode;p-nextNULL; //先建立一个带头结点的单链表for(i1;in;i) //依次输入n个非零项{snew PNode; //生成新节点cins-coefs-expn; //输入系数和指数preP; //pre用于保存q的前驱初值为头结点qP-next; //q初始化指向首元结点while(qq-expns-expn) //找到第一个大于输入项指数的项*q{preq;qq-next; } s-nextq; //将输入项s插入到q和其前驱结点pre之间pre-nexts;}
}
