《数据结构作业答案.ppt》由会员分享，可在线阅读，更多相关《数据结构作业答案.ppt（15页珍藏版）》请在装配图网上搜索。
1、线性表 作业答案 1、 编写算法实现顺序表的就地逆置。 #define MaxSize typedef struct DataType listMaxSize; int size; SeqList; void ConverseSeqList(SeqList * L) int mid,i; DataType x; mid=L-size/2; for(i=0;ilisti; L-listi=L-listL-size-1-i; L-listL-size-1-i=x; 2.编写算法实现单链表的就地逆置 。 先定义结点结构： typedef struct Node DataType data; stru
2、ct Node * next; SLNode; void ConverseSList(SLNode * head) SLNode *p,*q; p=head-next; head-next=NULL; while (p!=NULL) q=p; p=p-next; q-next=head-next; head-next=q; 3、已知线性表中的元素以值递增有序排 列，并以单链表作存储结构。设计算法删 除表中所有值大于 mink且小于 maxk的元素。 分析： 删除的结点的特点： mink =maxk void Delete_Between(SLNode *L,int mink,int maxk)
3、 /删除元素递增排列的链表 L中值大于 mink且 /小于 maxk的所有元素 SLNode * p,*pre,*q,*s; p=L-next; while (p if (p) while (p q=pre-next; pre-next=p; while (q!=p) s=q; q=q-next; free(s); 4、已知 A、 B和 C为三个有序链表，编写算法从 A表中删除 B表和 C表中共有的数据元素。 分析： 被删元素的特点： ai=bj=ck 其它元素则为： aibj 或 bjck 或 ckdatadata) pre=pa;pa=pa-next; else if (pb-datada
4、ta) pb=pb-next; else if (pc-datadata) pc=pc-next; else pre-next=pa-next;free(pa); pa=pre-next; 循环条件 ：三个指针均不为空。 void DelSame(SLNode * la, SLNode * lb, SLNode * lc) SLNode * pre,*pa,*pb,*pc; pre=la;pa=la-next; pb=lb-next;pc=lc-next; while (papa=pa-next; else if (pb-datadata) pb=pb-next; else if (pc-da
5、tadata) pc=pc-next; else pre-next=pa-next; free(pa); pa=pre-next; 5、设将 n(n1)个整数存放到一维数组 R中。试设计一个 在时间和空间两方面尽可能高效的算法，将 R中的序 列循环左移 p（ 0pn）个位置，即将 R中的数据由 （ x0,x1, ,xn-1）变换为 （ xp,xp+1, ,xn-1,x0,x1, ,xp-1）。 要求： （ 1）给出算法的基本设计思想。 （ 2）根据设计思想，采用 C或 C+语言描述算法，关键 之处给出注释。 （ 3）说明你所设计算法的时间复杂度和空间复杂度。 （ 1）算法的基本设计思想： 先将
6、 n个数（ x0,x1, ,xp, ,xn-1）原地逆置，得到 （ xn-1, ,xp,xp-1, x0），然后再将前 n-p个和后 p个 元素分别原地逆置，得到最终结果： xp,xp+1, ,xn-1,x0,x1, ,xp-1。 算法可以用两个函数实现： 一个是逆置函数 reverse()，它将给定的数据逆置； 另一个是循环左移函数 leftShift()，它调用 reverse()函数三次，实现相应功能。 （ 2）算法实现： void reverse(int r, int left, int right) int k=left, j=right, temp; /k等于左边界 left， j
7、等于右边界 right while(k0 /将全部数据逆置 reverse(r,0,n-p-1); /将前 n-p个元素逆置 reverse(r,n-p,n-1); /将后 p个元素逆置 （ 3）算法的时间复杂度为 O(n)，空间复杂度为 O(1)。 6、假设利用两个线性 表 LA和 LB分别表示两个集合 A 和 B（即：线性表中的数据元素即为集合中的成 员），现要求一个新的集合 A=A B。采用单链表 作为存储结构，编写算法。 上述问题等价于： 要求对线性表作如下操作：扩大线性表 LA，将存 在于线性表 LB中而不存在于线性表 LA中的数据元 素插入到线性表 LA中去。 1从线性表 LB 中依次察看每个数据元素 ; 2依值在线性表 LA 中进行查访 ; 3若不存在，则插入之。 GetElem(LB, i)e LocateElem(LA, e, equal( ) ListInsert(LA, n+1, e) ( n 表示线性表 LA 当前长度 ) 操作步骤：
数据结构作业答案.ppt
