DS第二章课后习题答案

1、第二章线性表 2. 1填空题 (1) 一半插入或删除的位置 (2) 静态 动态不一定头结点的next前一个元素的next 一定 (1)A(2) DAGKHDAEL IAF IFA(IDA) (3) D(4)D (5) D 2. 3 头指针：在带头结点的链表中，头指针存储头结点的地址；在不带头结点的链表屮，头指 针存放第一个元素结点的地址； 头结点：为了操作方便，在第一个元素结点前申请一个结点，其指针域存放第一个元素结点 的地址，数据域可以什么都不放； 首元素结点：第一个元素的结点。 2.4已知顺序表L递增有序，写一算法，将X插入到线性表的适当位置上，以保持线性表的 有序 性。 void Ins

2、erList(SeqList *L, ElemType X) int i二L-last; if (L-last=MAXSIZE-l) return FALSE; /顺序表已满 while(i=0 L-last+; 2.5删除顺序表中从i开始的k个元素 int DelList(SeqList *L,int i,int k) int j, 1; if(iLlast) printf (The Initial Position is Error!z，) ; return 0; 辻(k=L-last) L-last=L-last-k; /modify the length*/ forl=i+k-l;ll

3、ast;j+,1+) L-elemj=L-eleml; L-lasL-last-k; return 1; 0(n)、空间复杂度 2.6已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为 为0(1)的算法，删除线性表中所有值为item的数据元素。 算法1 void DeleteItem(SeqList *L, ElemType item) int i=0,j=L-last; while(ij) while(ielemi!=item) while(ielemi=item) if(ielemi=L-elemj; i+； J-； L-las t 二 iT; 算法2 void Deletelte

4、m (SeqList *L, ElemType e) int i, j； i于0; while(L-elemi!=e j二i+1； while(jlast) while(L-elemj=e 辻(jlast) L-elemi=L-elemj; i+； j+； L-last=i-l; 2.7编写算法，在一非递减的顺序表L中，删除所有值相等的多余元素。要求时间复杂度为0( n), 空间复杂度为0(1)。 void DeleteRepeatItem(SeqList *L) int i=0,j=l; while(jlast) if(L-elemi=L-elemjJ) j+； else L-elemi+l

5、=L-elemj; i+； j+； Llast=i; 2.8已知线性表屮的元素(整数)以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除 表屮所有大于mink且小于maxk的元素(若表中存在这样的元素),分析你的算法的时间复杂度。 void DelData(LinkList L, ElemType mink, ElemType maxk) Node *p=L-next, *pre二L; whi.le(!p else pre-next=p-next; free(p); p=prenext; T (n)二0 (n); 即在原表的存储空间将线性表 (a1, 2. 9试分别以不同的存储结构实

6、现线性表的就地逆置算 法，32逆置为(如a n-i)o (1) i,., a以一维数组作存 (2) 储结构。以单链表作存储 (略) (1) void ReverseArray (ElemType a, int n) int i=0, j=n-l; ElemType t; while(inext; L-next=NULL; wh订e(p!二NULL) q=p-next; p-next二Lnext; Lnext=p; P 二q; 2. 10已知一个带有表头结点的单链表，假设链表只给出了头指针 Lo在不改变链表的前提下， 请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点(k为正整数)。若

7、查 找成功，算法输出该结点的data域的值，并返回1;否则，至返回0o (提示：设置两个指针，步 长为k) int SearchNode (LinkList L, int k) Node *p=L, *q; int i二0; while(inext; if(pNULL) return 0; / 不存在倒数第k个元素 q=L-next; while (p-next!=NULL) /p到终点时，q所指结点为倒数第k个 q二q_next; p二p_next; printfq-data );return 1; 2. 11把元素递增排列的链表A和B合并为C,且C中元素递减排列，使用原空间。(头插法) L

8、inkList ReverseMerge(LinkList *A, LinkList *B) LinkList C; Node *pa=Anext, *pb=Bnext; /pa 和 pb 分别指向 A, B 的当前元素 Anext=NULL; OA; while(pa!=NULL pa-next二Cnext; C-next=pa; pa=temp; else temp 二 pb-next; pb - next 二 C-next; Cnext=pb; pb 二 temp; /* 将 pb 的元素 前插到 pc 表 */ while(pb!=NULL) 将剩余pa的元素前插到pc 将剩余pb的元

9、素前插到pc tempzzpa-next; panexCnext; C-next=pa; pa=temp; /* 表*/ while(pb!=NULL) tempzzpb-next; pbnexCnext; C-next=pb; pb二temp; /* 表*/ :return he; 大于该结点的元 2. 12 一单链表，以第一个元素为基准，将小于该元素的结点全部放到前面, 素全部放到后面。时间复杂度要求为0(n),不能申请新空间。 void AdjustList(LinkList L) Node *pFlag=L-next, *q=L-next-next, *temp二NULL; pflag

10、-next二NULL; while(q!=NULL) 辻(q-data data)/插到链表首端 temp=q-next; q-next=L-next; L-next=q; q二temp; Else 插到pFlag结点后面 temp二q-next; q-next=pFlag-next; pFlag-next=q; q=temp; 2.13假设有一个循环链表的长度大于1,且表屮既无头结点也无头指针。已知s为指向链表 某个结点的指针，试编写算法在链表中删除指针s所指结点的前驱结点。 void DelPreNode(Node* s) Node* p=s; while (p-next-next!=s)

11、p二p-next; free (p-next); p-next=s; 2. 14已知由单链表表示的线性表屮含有三类字符的数据元素(如字母字符、数字字符和其他字 符)，试编写算法来构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表 中的结点空间作为这三个表的结点空间，头结点可另辟空间。 /L为待拆分链表 /Lch为拆分后的字母链；Lnum为拆分后的数字链，Loth为拆分后的其他字符链 /Lch, Lnum, Loth均已被初始化为带头结点的单循环链表，采用头插法 void splitLinkList(LinkList L, LinkList Lch,LinkList Lnum

12、, LinkList Loth) Node *p=L-next; while(p!=NULL) 辻(p-data = a Lch-next=p;p= temp; else 辻(p-data二O p-next=Lnum-next; Lnum-next=p; p= temp; else temp=p-next; p-next=Loth-next; Loth-next=p; p= temp; 2. 15设线性表A= (ai, a2, , am), B= (bi, b2,bn),试写一个按下列规则合并A、B为线性表C 的算法，使得： C (a 二 1, bi,，am, bm, bm+1,，bn) 或者

13、 C= (a 1, bi, , an, bn, an+i, , am) 当 mn【甘。 线性表A、B、C均以单链表作为存储结构，且C表利用A表和B表屮的结点空间构成。注意： 单链表的长度值m和n均未显式存储。 /将A和B合并为C, C已经被初始化为空单链表 void MergeLinkList(LinkList A, LinkList B,LinkList C) Node *pa=A-next ,*pb=B-next, *pc二C; int tag=l; while(pa tag=0; if (tag) pcnext=pa-next; pc=pcnext; pa=pa-next; else p

14、c-next=pb-next; pc二pc-next; pbzzpb-next; if (pa) pc-next二pa-next; else pc-next=pb-next; s 2. 16将一个用循环链表表示的稀疏多项式分解成两个多项式，次使这两个多项式中各自仅含奇 项或偶次项，并要求利用原链表屮的结点空间来构成这两个链表。 /A为循环单链表，表示某多项式;将A拆分为B和C 其屮B 只含奇次项，C只含偶次项;奇偶按照幕次区分/B,C均已被初始 化为带头结点的单链表 void SplitPolyList(PolyList A, PolyList B,PolyList C) PolyNode *

15、pa=A-next,*rb二B, *rc二C; while (pa) 辻(pa-exp%2=0) /偶次项 rcnext=pa-next; rc=rc-next; pa=panext; else / 奇次项 rbnext=pa-next; rb=rb-next; pa=panext; rb-next=NULL; rc-next=NULL; data 域 1运算 */ 2.17建立一个带头结点的线性链表，用以存放输入的二进制数，链表中每个结点的 存放一个二进制位。并在此链表上实现对二进制数加1的运算。 void BinAdd(LinkList 1) /*用带头结点的单链表 L存储二进制数，实现加 Node *q, *s; q=l-next; r 二1; while(q!=NULL) /*查找最后一个值域为0的结点*/ 辻(q-data 二二 0) r 二 q; q 二 q-next; if (r != 1) r-data = 1;/*将最后一个值域为0的结点的值域赋为1*/ /* else未找到值域为0的结点*/ s=(Node*)malloc(sizeof(Node); s-data=l; snext二Lnext; L-next = s; r = s; /*申请新结点存放最高进 * 位/ /*值域赋为1*/ /*插入到头结点之后*/