- 1、本文档共93页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
数据结构c语言描述 第二章线性表.ppt
小帖士: LinkList和Node *同为结构体指针类型,这两种类型说明本质上是等价的。 通常习惯上用LinkList来说明头指针变量,强调它是某个单链表的头指针。例如: LinkList L,则L为单链表的头指针。 通常用Node *来定义指向单链表中任意结点的指针,例如: Node *p,则p可以指向单链表中的任意结点。 对于顺序表,以下说法错误的是( ) A、顺序表是用一维数组实现的线性表,数组的下标可以看成是元素的绝对地址 B、顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列 C、顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻 D、顺序表的特点是:逻辑上相邻的元素,存储在物理位置也相邻的单元中 2. 对顺序表上的插入、删除算法的时间复杂性分析来说,通常以( )为标准操作 A、条件判断 B、结点移动 C、算术表达式 D、赋值语句 4.设指针P指向双链表的某一结点,则双链表结构的对称性可用( )式来刻画 A、 p-prior-next==p-next-next B 、 p-prior-prior==p-next-prior C 、 p-prior-next==p-next-prior D 、 p-next-next==p-prior-prior 6.以下说法错误的是 ( ) A、对循环链表来说,从表中任一结点出发都能通 过前后操作而扫描整个循环链表 B、对单链表来说,只有从头结点开始才能扫描表中全部结点 C、双链表的特点是找结点的前趋和后继都很容易 D、对双链表来说,结点*P的存储位置既存放在其前趋结点的后继指针域中,也存放在它的后继结点的前趋指针域中。 7.双向链表结点结构如下: 其中:Prior是指向前驱结点的指针域:data是存放数据元素的数据域;next是指向后继结点的指针域。 下面给出的算法段是要把一个新结点*Q作为非空双向链表中的结点*p的前驱,插入到此双向链表中。能正确完成要求的算法段是( ) A、 Q-Prior=P-Prior; Q-next=P; P-Prior=Q; P-Prior-next=Q; B 、P-Prior=Q; Q-next=P; P-Prior-next=Q; Q-Prior=P-Prior; C 、Q-Prior=P-Prior;Q-next=P;P-Prior-next=Q;P-Prior=Q; 算法例1:已知顺序表L中的数据元素类型为int。设计算法将其调整为左右两部分,左边的元素(即排在前面的)均为奇数,右边所有元素(即排在后面的)均为偶数,并要求算法的时间复杂度为O(n),空间复杂度为O(1)。 【算法思路】 只需要将位于表左半部分的偶数与位于表右半部分的奇数通过一个辅助变量进行交换即可。 AdjustSqlist(SeqList *L) {int i=0,j=L-last; while(ij) { while(L-elem[i]%2!=0) i++; while(L-elem[j]%2= =0) j--; if(ij) {t= L-elem[i]; L-elem[i]= L-elem[j]; L-elem[j]=t;}/*交换*/ } }/*end of AdjustSqlist*/ 算法例2:算法实现带头结点单链表的就地逆置问题。 【算法思路】: 逆置后的单链表初始为空,表中的结点不是新生成的,而是从原链表中依次“删除”,再逐个头插入到逆置表中。设逆置链表的初态为空表,“删除”已知链表中的第一个结点,然后将它“插入”到逆置链表的“表头”,即使它成为逆置链表中“新”的第一个结点,如此循环,直至原链表为空表止。 void ReverseList(LinkList L) /*逆置带头结点的单链表L */ { p=L-next; /* P为原链表的当前处理结点*/ L-next=NULL; /*逆置单链表初始为空表*/ while(p!=NULL) /*当原链表未处理完*/ { q=p-next; /*q指针保留原链表当前处理结点的下一个结点*/ p-next=L-next; L-next=p; /*将当前处理结点p插入到逆置表L的表头*/ p=q; /*p指向下一个待插入的结点*/ } /*end of while*/ }/*end of ReverstList*/ 一元多项式的表示 在计算机中,可以用一个线性表来表示:
您可能关注的文档
最近下载
- 2024-2025学年高中思想政治必修1 中国特色社会主义统编版(部编版)教学设计合集.docx
- 员工培训---病理.ppt
- 2025年上海市数学高考一轮复习精讲精练 第10讲空间向量与立体几何(11类核心考点精讲精练)含详解.docx
- 养老院活动记录表(新版).doc VIP
- 二年级上学期数学基础知识《填空题》专项练习及一套完整答案.docx
- 建设工程质量资料管理.ppt VIP
- 酒店智能弱电系统工程设计模板.doc VIP
- 烟草种植气象服务规范.pdf VIP
- 2023上海高三二模优秀作文汇编.doc
- 第5 2课《学习工匠事迹,领略工匠风采》(课件)-【中职专用】高二语文同步精品课件(高教版2023·职业模块).pptx VIP
文档评论(0)