《一基础知识题》PPT课件.ppt

一.基础知识题,2.2填空题 （1）在顺序表中插入或删除一个元素，需要平均移动表中一半 元素，具体移动的元素个数与表长和该元素在表中的位置 有关。 （2）顺序表种逻辑上相邻的元素的物理位置必定 紧邻。单链表种逻辑上相邻的元素的物理位置不一定 紧邻。 （3）在单链表种，除了首元结点外，任一结点的存储位置由其直接前驱结点的链域的值 指示。 （4）在单链表种设置头结点的作用是插入合删除首元素时不必进行特殊处理 。,2.6 已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。 a. 在P结点后插入S结点的语句序列是 (4) (1) 。 b. 在P结点前插入S结点的语句序列是 (7)（11）（8）（4）（1） 。 c. 在表首插入S结点的语句序列是 (5) (12) 。 d. 在表尾插入S结点的语句序列是 (11) (9) (1) (6) 。 （1）P-next=S;（2）P-next=P-next-next; （3）P-next=S-next;（4）S-next=P-next; （5）S-next=L;（6）S-next=NULL; （7）Q=P; （8）while (P-next!=Q) P=P-next; （9）while (P-next!=NULL) P=P-next; （10）P=Q; （11）P=L; （12）L=S; （13）L=P;,2.7 已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。,a. 删除P结点的直接后继结点的语句序列是 (11) (3) (14) 。 b. 删除P结点的直接前驱结点的语句序列是 (10) (12) (8) (11) (3) (14) 。 c. 删除P结点的语句序列是 10) (12) (7) (3) (14) 。 d. 删除首元结点的语句序列是 (12) (11) (3) (14) 。 e. 删除尾元结点的语句序列是 (12) (9) (11) (3) (14) 。,(1) P=P-next; (2) P-next=P; (3) P-next=P-next-next; (4) P=P-next-next; (5) while (P!=NULL) P=P-next; (6) while (Q-next!=NULL) PQ；QQ-next; (7) while (P-next!=Q) P=P-next; (8) while (P-next-next!=Q) P=P-next; (9) while (P-next-next!=NULL) P=P-next; (10) Q=P; (11) Q=P-next; (12) P=L; (13) L=L-next; (14) free(Q);,简述以下算法的功能：,Status A (LinkedList L) /L是无表头的单链表 if(LQnext=null； return ok ,解答：,如果链表为空或只有一个结点就不做处理。 否则，把链表中的第2个结点变成头结点，而把表中第1结点放置到链表尾部作为尾结点。,简述以下算法的功能：,void BB(LNode *s, LNode *q ) p =s ; while (p-next!=q) p =p-next ; p-next =s; /BB void AA(LNode *pa, LNode *pb) / pa 和 pb 分别指向单循环链表中的两个结点 BB(pa, pb); BB(pb, pa); /AA 此算法的功能为：_,解答：,首先你清楚什么是循环链表吧！ 比如说一根绳子，收尾连在一起，就是一个圆圈了。这个圆圈上有两个点，一个s，一个q，然后用剪刀在q点之前剪断，剪断后再连接到s点，自己想象一下这跟绳子变成什么效果了，是不是好像蝌蚪形状了。这个就是AA里面的第一个BB函数的功能。 AA里面的第二个BB函数功能，就是将蝌蚪的尾巴截断，再绕成一个圈。于是就变成两个圈了，也就是两个循环链表。 所以，AA的功能就是将一个循环链表变成两个循环链表，BB的功能就是将链表中的节点截断并形成一个新的小的循环链表。,2.11 设顺序表va中的数据元素递增有序。试写一算法，将x 插入到顺序表的适当位置上，以保持该表的有效性。 2.19 已知线性表中的元素以值递增有序，并以单链表作存储 结构。试写一高效的算法，删除有序表中所有其值大于 mink 且小于maxk的数据元素。 2.21 试写一算法，实现顺序表的就地逆置，即利用原表的存储 空间将线性表（a1,a2,an) 逆置为（an,an-1,a1)。 2.22 试写一算法，对单链表进行就地逆置。 2.41 试以循环链表作为稀疏多项式的存储结构，编写求其导 函数的算法，要求利用原多项式中的结点空间存放其导函数（ 多项式），同时释放所有无用（被删）的结点。,本章算法设计涉及的顺序表和线形链表的类型定义如下 ：,#define LIST_INIT_SIZE 100 #define LISTCREMENT 10 typedef struct ElemType *elem; /存储空间基址 int length; /当前长度 int listsize; /当前分配的存储容量 SqList; /顺序表类型,typedef struct Lnode ElemType data; struct Lnode *next； LNode, *LinkList; /线性链表类型,Status Insert_Sq( SqList /Insert_Sq,题 2.11,返回,题2.19,删除有序表中所有其值大于 mink 且小于maxk的数据元素。,首先分析需要删除的结点的特点：,mink,=maxk,pre,q,p,修改指针: pre-next = p;,释放结点: while (q!=p) s=q-next; free(q); q=s; , ,void delete(LinkList &L, int mink, int maxk) / delete,while (p /查找第一个值mink的结点,if (p) / if,q=pre-next; pre-next=p; / 修改指针,while (q!=p) s=q-next; delete q; q=s; / 释放结点空间,p=L-next;,while (p / 查找第一个值 maxk 的结点,返回,2.21 顺序表的就地逆置,void reverse(SqList /reverse,题2.22,逆置线性链表,a1,a2,a3,L,p,a1,a2,a3,基本操作：,1）标志后继结点； 2）修改指针（将*p插入在头结点之后）； 3）重置结点*p（p重新指向原表中后继）；,void inverse(LinkList ,返回,题 2.41,void Difference_L( LinkedPoly pa ) / pa 为指向稀疏多项式循环链表的头指针， / 本算法将链表改变为该多项式的导函数 p = pa-next; pre = pa; while