冲刺必会代码100题.docx

1、冲刺必会代码 100 题顺序表1、已知线性表（a1,a2,an）按顺序结构存储且每个元素为不相等的整数。设计把所有奇数移动到所有偶数前边的算法（要求时间最少，辅助空间最少）。【算法思想】：对于顺序表 L，从左向右找到偶数 L.datai，从右向左找到奇数L.dataj，将两者交换。循环这个过程直到 i 大于 j 为止。对应的算法如下：void move(SqList &L)int i = 0, j = L.length-1, k; ElemType temp;while(i = j) while(L.datai%2 = 1) while(L.dataj%2 = 0) if(i j) L.dat

2、ai = L.dataj; L.dataj = temp;/交换 L.datai和 L.datajtemp = L.datai;/j 指向一个偶数j-;/i 指向一个偶数i+;本算法的时间复杂度为 O(n)，空间复杂度为 O(1)。2、设计一个高效算法，将顺序表 L 中所有元素逆置，要求算法的空间复杂度为 O(1)。【算法思想】：扫描顺序表 L 的前半部分元素，对于元素 L.datai,将其与后半部分对应元素 L.dataL. length-i-1进行交换。对应的算法如下:void reverse(SqList &L)int i; ElemType x;for(i = 0; i C.lengt

3、h)/表长超过return false; int i = 0, j = 0,k = 0; while(i A.length & jB.length) /循环，两两比较，小者存入结果表 if(A.datai = B.dataj) C.datak+ = A.datai+; else C.datak+ = B.dataj+; while(i A.length) C.datak+ = A.datai+; while(j B.length) C.datak+ = B.dataj+; C.length = k; return true;4、从顺序表中删除具有最小值的元素（假设唯一）并由函数返回被删除元素的

4、值。空出的位置由最后一个元素填补。【算法思想】搜素整个顺序表，查找最小值元素并记在其位置，搜索结束后用最后一个元素填补空出的原最小值元素的位置。bool Delete_Min(SqList &L ,ElemType &value)/删除顺序表 L 中最小值元素结点，并通过引用型参数 value 返回其值 if(L.length = 0)return false; /表空，终止操作 value = L.data0;int pos = 0; /假设 0 号元素的值最小 for(int i = 1; iL.length; i+) /循环遍历，寻找具有最小值的元素 if(L.datai value)

5、/让 value 记忆当前具有最小值的元素 value = L.datai; pos = i;L.datapos = L.dataL.length-1; /空出的位置由最后一个元素填补 L.length-; return true;5、已知长度为 n 的线性表 L 采用顺序存储结构,编写一个时间复杂度为 O(n)、空间复杂度为 O(1)的算法,该算法删除线性表中所有值为 x 的数据元素。【算法思想】解法 1：用 k 记录顺序表 L 中等于 x 的元素个数,边扫描 L 边统计 k,并将不为 x 的元素前移 k 位,最后修改 L 的长度。对应的算法如下:void del_x(SqList &L,

6、ElemType x)int k, i = 0;/k 用于记录 L 中值等于 x 的元素个数，初试值为 0 while(iL.length) if(L.datai = x)k+;/k 自增 else L.datai-k = L.datai;/将不为 x 的元素元素前移 k 个位置 i+; L.length = L.length-k;/顺序表长度较少 k解法 2：用 i 从头开始遍历顺序表 L，k 置初始 0。若 L.datai不等于 x，则将其存放在 L.datak中，k 增 1;若 L.datai等于 x，则跳过继续判断下一个元素。最后顺序表长度置为 k。对应算法如下。void del_x(

7、SqList &L, ElemType x)int i; k = 0;/k 用于记录 L 中值等于 x 的元素个数，初试值为 0for(i = 0; iL.length; i+) if(L.datai != x) L.datak = L.datai; k+;L.length = k;/表长置为 k6、设计一个算法，从一给定的顺序表 L 中删除元素值在 x 到 y(xy)之间的所有元素， 要求以较高的效率来实现，空间复杂度为 O(1)。【算法思想】解法一：本题是上诉题目的变形。可以采用上诉解法一的方法，只是将 L.datai = xint i,k = 0;for(i = 0; j= x & L.

8、datai = x & L.datai = y。void del_xy(SqList &L, ElemType x, ElemType y)解法二：void del_xy(SqList &L, ElemType x, ElemType y)int i = 0, k = 0; while(i= x & L.datai 1)个整数存放在一维数组R 中。试着设计一个在时间复杂度和空间复杂度都尽可能高效的算法，将 R 中保存的序列循环左移 p（ 0pn ） 个 位 置 ， 即 将 R 中 的 数 据 由 （ x0,x1,xn-1 ） 变 换 为 （ xp, xp+1,xn-1,x0,x1,xp-1）。

9、要求：（1） 给出算法的基本设计思想；（2） 根据算法设计思想，采用 C 或 C+语言描述，关键之处给出注释（3） 说明你所设计算法的时间复杂度和空间复杂度。【算法思想】先将 n 个数据 x0,x1, ,xn-2,xn-1 原地逆置，得到 xn-1,xn-2,x,x0,然后再将 n-p 个数据和后 p 个数据分别原地逆置， 得到最终结果： xp, xp+1,xn-1,x0,x1,xp-1void Reverse(int R, int left, int right) /将数组原地逆置i = left, j = right;while(i 0 & pnext;/pa 是链表 La 的工作指针，初

10、始化为首元结点pa = La-next; while(pa & pb)if(pa-data data) /取较小者 Lb 中的元素，将 pb 链接在 pc 的后面，pb 指针后移pc-next = pa;pc = pa;/if pa = pa-next; else if(pa-data pb-data)pc-next = pb; /取较小者 Lb 中的元素，将 pb 链接在 pc 的后面，pb 指针后移pc = pb; pb = pb-next;/else if elsepc = pa; pc-next = pa; pa = pa-next;q = pa-next;free(pb);pb =

11、q; pc-next = pa?pa:pb;/将非空的剩余元素直接链接在 Lc 表的最好free(Lb);/释放 Lb 的头结点2、将两个非递减的有序表合并为一个非递增的有序表。要求结果链表仍然使用原来两个链表的存储空间，不占用另外的存储空间。表中允许有重复的数据。【算法思想】与上述题目类似，从原有两个链表中依次摘取结点，通过更改结点的指针域重新建立新的元素之间的线性关系，得到一个新链表。但与上面题目不同的点有两个：为保证新表与原表顺序相反，需要利用前插法建立单链表，而不能利用后插法；当一个表到达表尾结点为空时，另一个非空表的剩余元素应该依次摘取，依次链接在 Lc 表的表头结点之后，而不能全部

12、直接链接在 Lc 表的最后。算法思想是:假设待合并的链表为 La 和 Lb，合并后的新表使用头指针 Lc(Lc 的表头结点设为 La 的表头结点)指向。pa 和 pb 分别是链表 La 和 Lb 的工作指针， 初始化为相应链表的首元结点。从首元结点开始进行比较，当两个链表 La 和 Lb 均为到达表尾结点时，依次摘取其中较小者重新链接在 Lc 表的表头结点之后， 如果两个表中的元素相等，只摘取 La 表中的元素，保留 Lb 表中的元素。当一个表到达表尾结点为空时,将非空表的剩余元素依次摘取，链接在 Lc 表的表头结点之后。最后释放链表 Lb 的头结点。void MergeList(LinkLi

13、st &La, LinkList &Lb, LinkList &Lc)/将两个非递减的有序表 La 和 Lb 合并为一个非递增的有序链表 LcLc-next = NULL;/用 La 的头结点作为 Lc 的头结点Lc = pc = La；/pb 是链表 Lb 的工作指针，初始化为首元结点pb = Lb-next;/pa 是链表的 La 的工作指针，初始化为首元结点pa = La-next;/La 表为空，用 q 指向 pb,pb 指针后移if(!pa)/只要有一个表未到达表尾指针，用 q 指向待摘取的元素while(pa | pb)q = pb; pb = pb-next;else if(!p

14、b)/Lb 表为空，用 q 指向 pa,pa 指针后移q = pa; pa = pa-next; else if(pa-data data)/去较小者 La 中的元素，用 q 指向 pa，pa 指针后移q = pa;/去较小者 Lb 中的元素，用 q 指向 pb，pb 指针后else pa = pa-next;移q = pb;pb = pb-next;Lc-next = q;free(Lb)q-next = Lc-next;3、已知两个链表 A 和 B 分别为两个集合，其元素递增排列。请设计一个算法， 用于求出 A 与 B 的交集，并存放在 A 链表中。【算法思想】A 与 B 的交集是指同时出

15、现在两个集合中的元素，因此，此题的关键点在于:依次摘取两个表中相等的元素重新进行链接,删除其他不等的元素。算法思想是:假设待合并的链表为 La 和 Lb，合并后的新表使用头指针 Lc(Lc 的表头结点设为 La 的表头结点)指向。pa 和 pb 分别是链表 La 和 Lb 的工作指针， 初始化为相应链表的首元结点。从首元结点开始进行比较，当两个链表 La 和 Lb 均为到达表尾结点时，如果两个表中的元素相等，摘取 La 表中的元素，删除 Lb 表中的元素;如果其中一个表中的元素较小，删除此表中较小的元素，此表的工作指针后移。当链表 La 和 Lb 有一个到达表尾结点为空时，依次删除另一个非空表

16、中的所有元素。最后释放链表 Lb 的头结点。void Intersection(LinkList &La, LinkList &Lb, LinkList &Lc)/pb 是链表 Lb 的工作指针，初始化为首元结点pb = Lb-next;/pa 是链表 La 的工作指针，初始化为首元结点pa = La-next;/相等，交集并入结果表中if(pa-data = pb-data)while(pa & pb)/用 La 的头结点作为 Lc 的头结点Lc = pc = La; pc-next = pa;pc = pa;u = pb; pa = pa-next; pb = pb-next;free(u

17、); else if(pa-data data)/删除较小者 La 中的元素 u = pa;pa = pa-next;free(u);else/删除较小者 La 中的元素u = pb;pb = pb-next;free(u);while(pa)/Lb 为空，删除非空表 La 中的所有元素u = pa;pa = pa-next;free(u);while(pb)/La 为空，删除非空表 Lb 中的所有元素u = pb;pb = pb-next;free(u);pc-next = NULL;free(Lb)4、已知两个链表 A 和 B 分别表示两个集合，其元素递增排列。请设计两个算法求出两个集合

18、A 和 B 的差集（即仅由在 A 中出现而不在 B 中出现的元素所构成的集合），并且以同样的形式存储，同时返回该集合的元素个数。【算法思想】求两个集合 A 和 B 的差集是指在 A 中删除 A 和 B 中共有的元素，即删除链表中的数据域相等的结点。由于要删除结点，此题的关键点在于:在遍历链表时，需要保存待删除结点的前驱。算法思想是:假设待求的链表为 La 和 Lb，pa 和 pb 分别是链表La 和 Lb 的工作指针，初始化为相应链表的首元结点。pre 为 La 中 pa 所指结点的前驱结点的指针，初始化为 La。从首元结点开始进行比较，当两个链表 La 和 Lb 均未到达表尾结点时，如果 L

19、a 表中的元素小于 Lb 表中的元素，La 表中的元素即为待求差集中的元素，差集元素个数增 1，pre 置为 La 表的工作指针 pa,pa 后移;如果 Lb 表中的元素小于La 表中的元素,pb 后移;如果La 表中的元素等于Lb 表中的元素， 则在 La 表删除该元素值对应的结点。void Difference(LinkList &La, LinkList &Lb, int &n)/pb 是链表 Lb 的工作指针，初始化为首元结点pa = Lb-next;/pa 是链表的 La 的工作指针，初始化为首元结点pa = La-next;/A 链表当前的结点指针后移if(pa-data data

20、)while(pa & pb)/pre 为 La 中 pa 所指结点的前驱结点的指针pre = La;n+;pre = pa;/在 La 中删除 La 和 Lb 中元素值相同的结点else/A 链表当前的结点指针后移pb = pb-next;else if(pb-data pb-data) pa = pa-next; pre-next = pa-next;u = pa;free(u); pa = pa-next;5、试编写在带头结点的单链表 L 中删除一个最小值结点的高效率算法（假设最小值结点是唯一的）。算法思想：用 p 从头至尾扫描单链表，pre 指向*p 结点的前驱，用 minp 保存值最

21、小的结点指针（初值为 p）,minpre 指向*minp 结点的前驱（初值为 pre）。一遍扫描，一边比较，若 p-data 小于 minp-data，则将 p、pre 分别赋值给 minp， minpre，如下图所示。当 p 扫描完毕，minp 指向最小值结点，minpre 指向最小值结点的前驱结点，再将 minp 所指结点删除即可。LinkList Delete_Min(LinkList &L) /L 是带头结点的单链表，本算法是删除其最小值结点 LNode *pre = L, *p = pre-next;/p 为工作指针，pre 指向其前驱if(p-data data)minp = p;

22、 minpre = pre;pre = p;p = p-next;/继续扫描下一节点free(minp); return L;/删除最小值结点minpre-next = minp-next;while(p != NULL)LNode *minpre = pre, *minp = p;/保存最小值结点及其前驱6、在带头结点的单链表 L 中，删除所有值为 x 的结点，并释放其空间，假设值为 x 的结点不唯一，试编写算法实现上述操作。算法思想：解法一：用 p 从头至尾扫描单链表，pre 指向*p 结点的前驱。若 p 所指结点的值为 x，则删除，并让 p 移向下一个结点，否则让 pre、p 同步后移一

23、个结点。提示：本算法其实也算的上是一个删除某结点相关题型的代码模板。此题是在无序单链表中删除满足某种条件的所有结点，这里的条件是结点的值为 x，实际上， 这个条件是可以任意改写的，只需要修改 if 条件即可。例如，我们要求删除结点值介于 mink 和 maxk 之间的所有结点， 则只需要将 if 语句修改为if(p-data mink & p-data next, *pre = L, *q; /置 p 和 pre 的初值p = p-next;/q 指向该结点q = p;/否则，pre 和 p 同步后移else/释放*q 结点的空间free(q);/删除*q 结点pre-next = p; if

24、(p-data = x)pre = p;p = p-next;/else /while解法二：采用尾插法建立单链表。用 p 指针扫描 L 的所有结点，当其值不为 x时将其链接到 L 之后，否则将其释放。void Delet_x(Linklist &L, ElemType x) /L 为带头结点的单链表，本算法删除 L 中所有值为 x 的结点 LNode *p = L-next, *r = L, *q;/r 指向尾节点，其初值为头结点while(p != NULL)if(p-data != x)/*p 结点值不为 x 时将其链接到 L 的尾部/继续扫描p = p-next;r = p; r-ne

25、xt = p; elseq = p; p = p-next;free(q);/whiler-next = NULL;/插入结束后置尾节点指针为 NULL 7、试编写算法将带头结点的单链表就地逆置，所谓“就地”是辅助空间复杂度为O(1)。算法思想：将头结点摘下，然后从第一结点开始，一次插入到头结点的后面（头插法建立单链表），直到最后一个结点为止，这样就实现了链表的逆置，如下图所示。LinkList Reverse(LinkList L) /L 是带头结点的单链表，本算法将 L 逆置/先将头结点 L 的 next 域值为 NULLL-next = NULL;/从第一个元素结点开始p = L-nex

26、t;/p 为工作指针，r 为 p 的后继，以防断链LNode *p, *r;/暂存 p 的后继r = p-next;/依次将元素结点摘下while(p != NULL) p-next = L-next;/将 p 结点插入到头结点之后 L-next = p;p = r; return L;8、将一个带头结点的单链表 A 分解为两个带头结点的单链表 A 和 B，使得 A 表中中含有原标中序号为奇数的元素，而 B 表中含有原表中序号为偶数的元素， 且保持其相对顺序不变。LinkList DisCreat(LinkList &A) /将 A 表中结点按照序号的奇偶性分解到表 A 或者表 B 中i =

27、0;/i 记录表 A 中结点的序号 B = (LinkList)malloc(sizeof(LNode); /创建 B 表表头B-next = NULL;/B 表初始化 LNode *ra = A, *rb = B;/ra 和 rb 将分别指向将创建的 A 表和 B 表的尾节点p = A-next; A-next = NULL;/将 A 表置空/处理序号为偶数的链表结点if(i % 2 = 0)/序号+1i+;while(p != NULL)rb-next = p;/在表尾插入新结点rb = p;/rb 指向新尾结点elsera-next = p;/处理原序号为奇数的结点ra = p;/在 A

28、 表尾插入新的结点p = p-next;/将 p 恢复为指向新的待处理结点ra-next = NULL;rb-next = NULL;return B;9、设 C = a1，b1，a2，b2，an，bn为线性表，采用头结点的 hc 单链表存放， 设计一个就地算法，将其拆分为两个单链表，使得 A = a1，a2，an，B = bn， b2，b1。算法思想：本题的思路和上题基本一样，不设置序号变量。二者的差别仅在于对B 表的建立不采用尾插法，而是采用头插法。LinkList DisCreat(LinkList &A) LinkList B = (LinkList)malloc(sizeof(LNd

29、e); /创建 B 表表头while(p != NULL)/ra 始终指向 A 的尾节点LNode *ra = A;/p 为工作指针LNode *p = A-next, *q;/B 表的初始化B-next = NULL; ra-next = p; ra = p;/将*p 链接到 A 的表尾 /头插后，*p 将断链，因此 q 记忆*p 的后继p-next = B-next;q = p-next;p = p-next;return B;/A 的尾节点的 next 域置空ra-next = NULL;p = q;/*p 插入到 B 的前端B-next = p; 10、设计算法将一个带头结点的单链表

30、A 分解为两个具有相同结构的链表 B 和C，其中 B 表的结点为 A 表中小于零的结点，而 C 表中的结点为 A 表中值大于零的结点（链表 A 中的元素为非零整数，要求 B、C 表利用 A 表的结点）。【算法思想】首先将 B 表的头结点初始化 A 表的头结点，为 C 申请一个头结点，初始化为空表。从 A 表的首元结点开始，一次对 A 表进行遍历。p 为工作指针，r 为 p 的后继指针。当 p-datadata0 时，将 p 指向的结点适用前插法插入到 C 表，然后 p 指向新的待插入的结点void Decompose(LinkList &A, LinkList &B, LinkList &C)

31、 /单链表 A 分解为两个具有相同结构的链表 B 和 CB = A;B-next = NULL;C-next = NULL; C = (LinkList)malloc(sizeof(LinkList);p = A-next; while(p != NULL)r = p-next;/暂存 p 的后继if(p-data next = p; p-next = B-next; else p-next = C-next;C-next = p;p = r;/p 指向新的待处理结点11、设计一个算法，通过一趟遍历确定长度为 n 的单链表中值最大的结点，返回该结点的数据域。【算法思想】此题的关键在于：在遍历的

32、时候利用指针 pmax 记录值最大的结点的 位置。算法思想：初值时候指针 pmax 指向首元结点，然后在遍历过程中，用 pmax 依次和后面的结点进行比较，发现大者则用 pmax 指向该结点。这样将链表从头到尾遍历一遍时，pmax 所指向的结点中的数据即为最大值。ElemType Max(LinkList L)/p 指向第二个结点p = L-next-next;/pmax 指向首元结点pmax = L-next;return NULL;if(L-next = NULL) /确定单链表中值最大的结点/p 指向下一个结点，继续遍历p = p-max;/pmax 指向数值大的结点pmax = p;i

33、f(p-data pmax-data)/遍历链表，如果下一个结点存在while(p != NULL) return pmax-data; 12、设计一个算法，删除递增有序表中值大于 mink 且小于 maxk（mink 和 maxk是给定的两个参数，其值可以和表中的元素相同，也可以不同）的所有元素void Delete_Min_Max(LinkList &L, int mink, int maxk) /删除递增有序表 L 中值大于 mink 且小于 maxk 的所有元素p = L-next; while(p & p-data next; while(p & p-data next;q = pr

34、e-next;pre-next = p;/修改待删除结点的指针while(q != p)/依次释放待删除结点的空间 s = q-next;free(q);q = s;13、在一个递增有序的线性表中，有数值相同的元素存在。若存储方式为单链 表，设计算法去掉数值相同的元素，使表中不再具有重复的元素。【算法思想】注意到题目是有序表，说明所有相同值域的结点都是相邻的。用 p 扫描递增单链表 L，若*p 结点的值域等于其后继结点的值域，则删除后者，否则 p 移向下一个结点。void DeleteSame(LinkList &L) /L 是递增有序的单链表，本算法删除表中数值相同的元素if(p = NUL

35、L) LNode *p = L-next, *q;/p 为扫描工作指针return ;/q 指向*p 的后继结点q = p-next; while(p-next != NULL) if(p-data = q-data)/找到重复值的结点 free(q); p-next = q-next;/释放 q 结点 else p = p-next;14、已知由单链表表示的线性表中,含有 3 类字符的数据元素(如:字母字符数字字符和其他字符),试编写算法构造3 个以循环链表表示的线性表,使每个表中只含同一类的字符,且利用原表中的节点空间作为这三个表的节点空间,头节点可另辟空间。【算法思想】先创建 3 个头节

36、点,用 p 扫描带头节点的单键表 L,将不同类型的数据元素采用头插法插入到相应的循环单链表中。对应的算法如下:void Split(LinkList *L, LinkList * &A,LinkList * &B,LinkList * &C)LinkList * p= L- next,* q; A= (LinkList *)malloc(sizeof(LinkList) );A-next = A;B-next = B; B= (LinkList *) malloc(sizeof (LinkList); C= (LinkList *)malloc(sizeof (LinkList);C-next

37、 = C; while (p!= NULL) if (p- data=A & p-datadata = a & p-datanext; q-next = A-next;A-next = p;/采用头插法建表 Aelse if (p-data =O & p-datanext;q-next = A-next;A-next =p;/采用头插法建表 Bq = p;p=p-next;q-next = C-next;C-next = p;/采用头插法建表 Celse15、已知带头节点的循环单链表 L 中至少有两个节点,每个节点的两个字段为data 和 next,其中 data 的类型为整型。试设计一个算法判断该链表中每个元素的值是否小于其后续两个节点的值之和。若满足,则返回 true;否则返回 false。【算法思想】用