第二章作业与实验.doc

2.1 描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。2.2 填空题 （1）在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。 （2）顺序表中逻辑上相邻的元素的物理位置紧邻。单链表中逻辑上相邻的元素的物理位置紧邻。 （3）在单链表中，除了首元结点外，任一结点的存储位置由指示。 （4）在单链表中设置头结点的作用是。257382.4 对以下单链表分别执行下列各程序段，并画出结果示意图。L P Q R S （1）Q=P-next; （2）L=P-next; （3）R-data=P-Data; （4）R-data=P-next-Data; （5）P-next-next-next-data=P-Data; （6）T=P; while(T!=NULL)T-data=T-data*2;T=T-next; （7）T=P; while(T-next!=NULL)T-data=T-data*2;T=T-next;2.5 画出执行下列各行语句后各指针及链表的示意图。L=(LinkList)malloc(sizeof(LNode); P=L;for(i=1;inext=(LinkList) malloc(sizeof(LNode);P=P-next; P-data=i*2-1;P-next=NULL;for(i=4;i=1;i-) Ins_LinkList(L,i+1,i*2);for(i=1;inext = 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.8 已知P结点是某双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。A在P结点后插入S结点的语句序列是_。B在P结点前插入S结点的语句序列是_。C删除P结点的直接后继结点的语句序列是_。D删除P结点的直接前驱结点的语句序列是_。E删除P结点的语句序列是_。(1) P-next = P-next-next;(2) P-priou = P-priou-priou;(3) P-next = S;(4) P-priou = S;(5) S-next = P;(6) S-priou = P;(7) S-next = P-next;(8) S-priou = P-priou;(9) P-priou-next = P-next;(10) P-priou-next = P;(11) P-next-priou = P;(12) P-next-priou = S;(13) P-priou-next = S(14) P-next-priou = P-priou;(15) Q = P-next;(16) Q = P-priou;(17) free(P);(18) free(Q);2.9 简述以下算法的功能。(1) Status A(LinkedList L) /L是无表头结点的单链表 if(L&L-next) Q=L; L=L-next; P=L; while(P-next) P=P-next; P-next=Q; Q-next=NULL; Return OK; /A(2) 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); /AA2.13 试写一算法在带头结点的单链表结构上实现线性表操作LOCATE(L,X)。2.14 试写一算法在带头结点的单链表结构上实现线性表操作LENGTH(L)。2.31 假设某个单向循环链表的长度大于1，且表中既无头结点也无头指针。已知s是指向链表中某个结点的指针，编写算法在链表中删除s所指结点的前驱结点。1.设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，并仍保持该表的有序性。2.写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表（a1,a2,.an）逆置为(an,.,a2,a1)。2.11,2.12,2.21, 2.19,2.22,2.24实验二（必做, 设计性实验，2学时）实验题目：顺序表的基本操作的实现1、在非递减有序的顺序表中插入一个元素x，保持顺序表有序性。2、顺序表元素的逆置3、两个（有序或无序）顺序表的合并实验目的：1、 熟悉将算法转换成程序代码的过程。2、 了解顺序表的逻辑结构特性，熟练掌握顺序表存储结构的C语言描述方法。3、 熟练掌握顺序表的基本操作：查找、插入、删除、合并等，掌握顺序表的随机存取特性。实验要求：1、要求用静态分配的一维数组和动态分配的一维数组来完成实验题目。分析静态分配的一维数组和动态分配的一维数组在顺序表基本操作实现上的共同点和区别。2、对顺序表插入的算法，要求用两种方法实现：其一：自己编写实现函数；其二：调用顺序表基本操作ListInsert(SqList &L,int i,ElemType x)，比较使用自己编写的插入函数和调用顺序表基本操作的函数两种实现方法之间的优缺点。3、对所编写的算法进行时间复杂度分析。实验内容和实验步骤：（由学生填写）实验用测试数据和相关结果分析：（由学生填写）实验总结：（由学生填写）实验三（必做, 设计性实验，2学时）实验题目：单链表的基本操作1、在线性单链表中删除值介于mink和maxk之间的结点。2、线性单链表逆置3、两个（有序或无序）单链表的合并实验目的：1、 了解线性表的链式存储结构和顺序存取特性，熟练掌握线性表的链式存储结构的C语言描述方法，2、 熟练掌握动态链表的基本操作查找、插入、定位等，能在实际应用中选择适当的链表结构。3、 掌握用链表表示特定形式的数据的方法，并能编写出有关运算的算法。实验要求：1、与实验二比较，对于线性表的基本操作的实现