数据结构：第2讲：线性表

目录1.线性表的定义和特点2.线性表的顺序表示与实现 顺序表3.线性表的链式表现与实现链表4.线性表的应用5.单向循环链表6.判断链表是否有环7.双向链表1.线性表的定义和特点1定义由 nn0个数据特性相同的元素构成的有限序列有限即数量有限序列理解为集合称为线性表。2特点线性表中元素的个数 nn0定义为线性表的长度当 n0 时称之为空表。对于非空的线性表其特点是存在唯一的一个被称作“第一个”的数据元素。存在唯一的一个被称作“最后一个”的数据元素。除第一个元素之外结构中的每个数据元素均只有一个前驱前一个元素叫前驱。除最后一个元素外结构中的每个数据元素均只有一个后继后一个元素。2.顺序表1定义用一组连续的内存单元依次存储线性表的各个元素也就是说逻辑上相邻的元素实际的物理存储空间也是连续的。2存储结构简单来说该结构体里有一个数组还有一个 lengthlength 的值为几就说明数组中有几个元素。3初始化数组不需要去初始化因为只要写了就已经在内存中开辟了100个位置的连续空间了故数组默认已经有了只用对 length 初始化。4在尾部添加元素5遍历6插入元素intinsertElem(Seqlist*L,intpos,ElemType e)//pos 是位置不是数组下标{if(L-lengthMAXSIZE){printf(表已经满了\n);return0;}if(pos1||posL-length){printf(插入位置错误\n);return0;}if(posL-length){for(intiL-length-1;ipos-1;i--){L-data[i1]L-data[i];}L-data[pos-1]e;L-length;}return1;}注往第一个位置插需要 n 次往最后一个位置插需要 1 次。所以顺序表插入数据的最好时间复杂度是 O(1)最坏时间复杂度是 O(n)。7删除元素本质是覆盖。ElemType *e 的作用是用来储存被删除的数据便于后续观察。8查找在当前顺序表中查找有没有自己想要的元素9动态分配内存地址初始化3.链表1链表存储结构的特点用一组任意的存储单元存储线性表的数据元素这组存储单元可以是连续的也可以是不连续的。23存储结构注顺序表是有一个结构体能完整的表示一个顺序表而链表是用一个结构体来表达一个节点。4单链表单一方向的链表单链表的初始化单链表的初始化是去创建一个头节点。注头节点不存有效数据的头节点不算链表的有效节点真正链表从 head - next 开始所以 head -next 的位置才是1。头插法每一次插入新数据的时候都把新数据放在头节点的后面。所以头插法的插入顺序和 printf 输出的排列顺序是相反的。L 是头节点也可以说是一条链表。遍历尾插法要先获得尾节点地址再进行尾插法在指定位置插入数据要先把 70 的 next 赋值给 new 的 next再把 new 的地址赋值给 70 的 next。new 插入后的位置是 2不是 3。删除节点找到要删除节点的前置节点 p用指针 q 记录要删除的节点通过改变 p 的后继节点来实现删除释放被删除节点的空间。intdeleteNode(Node*L,intpos){Node*pL;inti0;while(ipos-1){pp-next;i;if(pNULL){return0;}}if(p-nextNULL){printf(要删除的位置错误\n);return0;}Node*qp-next;p-nextq-next;free(q);return1;}获取链表长度该长度包括了头节点。释放链表除了头节点以外的所有节点都要给它删除掉。思路让指针 p 指向头节点后的第一个节点判断指针 p 是否指向空节点如果 p 不为空用指针 q 记录指针 p 的后继节点然后释放指针 p 指向的节点把指针 q 赋值给指针 q 让指针 p 和指针 q 指向同一节点循环上面操作最后再把头节点的 next 置空。4.线性表的应用1单链表应用1①思路快慢指针假设要找倒数第三个节点。声明两个指针都指向头节点后的这个节点。因为要找倒数第三个节点所以让快指针先走三步。快慢指针同时走快指针指向空的时候慢指针就找到了倒数第三个节点。②代码实现intfindNodeFS(Node*L,intk){for(inti0;ik;i){fastfast-next;}while(fast!NULL){fastfast-next;slowslow-next;}printf(倒数第%d个节点值为%d\n,k,slow-data);return1;}2单链表应用2①思路先分别求出两条链表的长度 m 和 n。fast 指针指向较长的链表先走 m-n 或 n-m 步。同步移动指针判断它们是否指向同一个节点。②代码实现Node*findIntersectionNode(Node*headA,Node*headB){if(headANULL||headBNULL){returnNULL;}Node*pheadA;intlenA0;intlenB0;while(p!NULL){pp-next;lenA;}pheadB;while(p!NULL){pp-next;lenB;}Node*m;Node*n;intstep;if(lenAlenB){steplenA-lenB;mheadA;nheadB;}else{steplenB-lenA;mheadB;nheadA;}for(inti0;istep;i){mm-next;}while(m!n){mm-next;nn-next;}returnm;}3单链表应用3①思路找到链表中绝对值最大的数假如是21然后创建一个长度为22的数组保证数组下标有21并将数组中每个元素置0。开始去遍历链表先拿到了21然后把21当成下标将数组下标为21的元素置1。同理遇到-15将数组下标为15的元素置1。又遇到了-15去找数组下标为15的元素发现不是0而是1说明之前已经见过绝对值为15的值了将此节点删除并释放内存。后面同理。②代码实现voidremoveNode(Node*L,intn)//L是头节点n是链表中绝对值最大的数的绝对值{NOde*pL;intindex;int*q(int*)malloc(sizeof(int)*(n1));for(inti0;in1;i){*(qi)0;}while(p-next!NULL){indexabs(p-next-data);if(*(qindex)0){*(qindex)1;pp-next;}else{Node*tempp-next;p-nexttemp-next;free(temp);}}free(q);}4单链表应用4反转链表①思路先准备三个指针把 first 赋值给 second 的 next把三个指针往后挪即把second赋值给first把third赋值给second并将third指向second的next。再将first赋值给second的next。后面同理直到second指向NULL循环结束。最后再加个头节点。②代码实现Node*reverseList(Node*head){Node*firstNULL;Node*secondhead-next;Node*third;while(second!NULL){thirdsecond-next;second-nextfirst;firstsecond;secondthird;}Node*hdinitList();hd-nextfirst;returnhd;}该代码与上面思路略有不同把 third 往后走一步放到了循环的最前面。5单链表应用5删除链表中间节点①思路利用快慢指针让快指针指向1慢指针指向头节点。每次让慢指针走一步快指针走两步。即可找到中间节点的前驱节点即可删除中间节点。②代码实现intdelMiddleNode(Node*head){Node*fasthead-next;Node*slowhead;while(fast!NULLfast-next!NULL){fastfast-next-next;slowslow-next;}Node*qslow-next;slow-nextq-next;free(q);return1;}6单链表应用6①思路将456翻转见缝插针q1放p1后面q2放p2后面以此类推。②代码实现voidreOrderList(Node*head){Node*fasthead-next;Node*slowhead;while(fast!NULLfast-next!NULL){fastfast-next-next;slowslow-next;}Node*firstNULL;Node*secondslow-next;slow-nextNULL;Node*thirdNULL;while(second!NULL){thirdsecond-next;second-nextfirst;firstsecond;secondthird;}Node*p1head-next;Node*q1first;Node*p2,q2;while(p1!NULLq1!NULL){p2p1-next;q2q1-next;p1-nextq1;q1-nextp2;p1p2;q1q2;}}5.单向循环链表1特点表中最后一个节点的指针域指向头节点整个链表形成一个环。6.判断链表是否有环1判断是否有环①题目意思解析比如此链表写出一个程序判断该链表是否有环不一定是循环链表头尾相连。②思路利用快慢指针快指针每次比慢指针多走一步如果链表中有环则二者一定会相遇生活中的例子两人在操场跑圈只要一个人始终比另一个人跑的快则两人一定会相遇。③代码实现intisCycle(Node*head){Node*fasthead;Node*slowhead;while(fast!NULLfast-next!NULL){fastfast-next-next;slowslow-next;if(fastslow){return1;}}return0;}7.双向链表1在双向链表的节点中有两个指针域一个直接指向后继另一个直接指向前驱。2组成3初始化Node*initList(){Node*head(Node*)malloc(sizeof(Node));head-data0;head-prevNULL;head-nextNULL;returnhead;}4头插法intinsertHead(Node*L,ElemType e){Node*p(Node*)malloc(sizeof(Node));p-datae;p-prevL;p-nextL-next;if(L-next!NULL){L-next-prevp;}L-nextp;return1;}5尾插法Node*insertTail(Node*tail,ElemType e){Node*p(Node*)malloc(sizeof(Node));p-datae;p-prevtail;tail-nextp;p-nextNULL;returnp;}注使用尾插法要先获得尾部节点Node*get_tail(Node*L){Node*pL;while(p-next!NULL){pp-next;}returnp;}6指定位置插入intinsertNode(Node*L,intpos,ElemType e){Node*pL;inti0;while(ipos-1){pp-next;i;if(pNULL){return0;}}Node*q(Node*)malloc(sizeof(Node));q-prevp;q-nextp-next;p-next-prevq;p-nextq;return1;}7删除节点intdeletNode(Node*L,intpos){Node*pL;inti0;while(ipos-1){pp-next;i;if(pNULL){return0;}}if(p-nextNULL){printf(要删除的位置错误\n);return0;}Node*qp-next;p-nextq-next;q-next-prevp;free(q);return1;}