网站开发公司所需投入资源/微信软文范例大全100
1、已知一个带有表头结点的单链表，结点结构如下：
| data | link |
假设该链表只给出头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的data值，并返回1；否则，只返回0。要求：
1）描述算法的基本设计思想。
2）描述算法的详细实现步骤
3）根据设计思路和实现步骤，采用程序设计语言描述算法，关键之处给出注释
设计思想：
博主看到题目的第一反应是先遍历一遍，然后得出链表的长度，然后再进行第二遍遍历，找到第k个元素。但是这样的方法需要遍历第二遍。下面介绍一种使用两个指针只需要遍历一遍的方法：
定义两个指针p,q，一开始都指向链表头，然后q先走k个结点，完了之后p和q一起走，等q走到链表尾的时候，p所指的结点就是倒数第k个结点。
实现步骤：
①locate = 0; p和q指向头结点的下一个结点
②当q为空时，返回0；
③当locate < k,则一直执行q=q-<next；
④当lcoate=k，p = p->next; q = q->next;
⑤当q=NULL时，输出p->data；返回1
⑥算法结束
算法实现：
typedef int ElemType;
typedef struct LNode
{ElemType data;struct LNode *next;
}LNode, *LinkList;int searchTailK(LinkList list,int k)
{LinkList p = list->next, q = list->next;int locate = 0;while (q) {if (locate < k)++locate;elsep = p->next;q = q->next;}if (locate < k)return 0;else{std::cout << p->data << std::endl;return 1;}
}2、假定采用带头结点的单链表保存单词，当两个单词有相同后缀时，可共享相同的后缀空间，例如，“loading”和“being”的存储映像如下图所示。
设str1和str2分别指向两个单词所在单链表的头结点，链表结点结构为 |data|next|，请设计一个在时间上尽可能高效的算法，找出由str1和str2所指向两个链表共同后缀的起始位置（如上图所示的位置p）。要求：
1）给出算法的基本设计思路
2）根据设计思想。采用c或c++或Java语言描述算法，关键之处给出注释
3）说明你所设计算法的时间复杂度和空间复杂度
设计思想：
因为共同后缀的起始结点是公用的，所以直接比较地址就好。
①p、q分别指向链表str1和str2。
②分别求出p链表和q链表的长度，分别记为m,n。若m>n，则p先走m-n+1个结点。反之若n>m，则q先走n-m+1个结点。
③p和q同时走，走到p->next=q-next时，即返回p->next。
算法实现：
typedef int ElemType;
typedef struct LNode
{ElemType data;struct LNode *next;
}LNode, *LinkList;int getLen(LinkList list)
{list = list->next;int count = 0;while (list) {++count;list = list->next;}return count;
}LNode* pos(LinkList p,LinkList q)
{int m = getLen(p);int n = getLen(q);if (m > n) {while (m != n) {p = p->next;--m;}}else{while (m != n){q = q->next;--n;}}while (p->next && q->next && (p->next != q->next)) {p = p->next;q = q->next;}return p->next;
}时间复杂度：O(max(len1,len2))
3、用单链表保存m个整数，结点的结构为[data][link]，且|data|<=n（n为正整数）。现要求设计一个时间复杂度尽可能高效的算法，对于链表中data的绝对值相等的结点，进保留第一次出现的结点而删除其余绝对值相等的结点。例如。若给定的单链表head如下：
要求：
1）给出算法的基本设计思路。
2）使用c或c++语言，给出单链表结点的数据类型定义。
3）根据设计思想。采用c或c++语言描述算法，关键之处给出注释。
4）说明你所设计算法的时间复杂度和空间复杂度。
算法的基本设计思路：
从题目中|data|<=n，我们可以考虑一种用空间换时间的做法。
①开辟一个大小为n的数组, arr[n]，初始化为0；
②开始遍历链表，去看arr[p->data]的值，若为0，则arr[p->data] 赋值为1。否则删除当前结点。最后得到的链表就是所求的新链表
单链表结点的数据定义类型：
typedef int ElemType;
typedef struct LNode
{ElemType data;struct LNode *next;
} *LinkList;算法实现过程：
//默认带头结点
LinkList Uniq(LinkList &list,int n)
{int *arr = new int[n] {0};LinkList p = list,r = NULL;while (p->next) {if (arr[abs(p->next->data)] == 0) {arr[abs(p->next->data)] == 1;p = p->next;}else{r = p->next;p->next = p->next->next;free(r);}}return list;
}时间复杂度：O(m)
空间复杂度：O(n)
人，总是要有一点精神的，不是吗