- 浏览: 898368 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (537)
- Java SE (114)
- Struts (18)
- Hibernate (25)
- Spring (3)
- Page_Tech (41)
- Others (87)
- Database (29)
- Server (24)
- OpenSource_Tools (15)
- IDE_Tool (22)
- Algorithm (28)
- Interview (22)
- Test (28)
- Hardware (1)
- Mainframe (25)
- Web application (4)
- Linux (3)
- PHP (17)
- Android (1)
- Perl (6)
- ubuntu (1)
- Java EE (9)
- Web Analysis (5)
- Node.js (2)
- javascript (2)
最新评论
-
一键注册:
request.getRequestURL()和request.getRequestURI() -
SuperCustomer:
...
SED的暂存空间和模式空间 -
juyo_ch:
讲得挺好理解的,学习了
java 死锁及解决 -
chinaalex:
最后一题答案正确,但是分析有误.按照如下过程,上一行为瓶,下一 ...
zz智力题 -
liaowuxukong:
多谢博主啦,弱弱的了解了一点。
C++/Java 实现多态的方法(C++)
先什么也不说,假设链表节点的数据结构为:
struct node
{
int data;
struct node* next;
};
创建单链表的程序为:
struct node* create(unsigned int n)
{
//创建长度为n的单链表
assert(n > 0);
node* head;
head = new node;
head->next = NULL;
cout << "请输入head节点的值(int型):";
cin >> head->data;
if (n == 1)
{
return head;
}
node* p = head;
for (unsigned int i = 1; i < n; i++)
{
node* tmp = new node;
tmp->next = 0;
cout << "请输入第" << i+1 << "个节点的值(int):";
cin >> tmp->data;
p->next = tmp;
p = tmp;
}
return head;
}
问题1:链表逆置
思想为:head指针不断后移,指针反向即可,代码为:
void reverse(node*& head)
{
if (head != NULL && head->next != NULL)
{
node* p = head;
node* q = head->next;
p->next = NULL;
while (q->next != NULL)
{
head = q->next;
q->next = p;
p = q;
q = head;
}
head->next = p;
}
return;
}
问题2:删除不知头结点链表的某个节点
如果单向链表不知道头节点,一个指针指向其中的一个节点,问如何删除这个指针指向的节点?
思想为:把这个节点的下一个节点的值复制给该节点,然后删除下一个节点即可。
问题3:怎么判断链表中是否有环?
思想为:设置两个指针,一个步长为1,另一个步长为2,依次后移,如果相遇且都不为空,则有环。
与这个类似的问题包括:怎么快速检测出一个巨大的链表中的死链?或者如何找出一个单链表的中间节点?
代码为:
bool loop(node* head)
{
bool flag = true;
if (head == NULL)
{
flag = false;
}
node* one = head;
node* two = head->next;
if (two == NULL)
{
flag = false;
}
while (one != two)
{
if (one != NULL)
{
one = one->next;
}
if (two != NULL)
{
two = two->next;
}
if (two == NULL)
{
break;
}
two = two->next;
if (one == NULL || two == NULL)
{
break;
}
}
if (one == NULL || two == NULL)
{
flag = false;
}
return flag;
}
问题4:如果一个单向链表,其中有环,怎么找出这个链表循环部分的第一个节点?
思想为:假设该节点在x位置处,假设步长为1的指针和步长为2的指针相遇在x+z处,循环的长度为y,那么2(x+z)-(x+z)=k*y,
那么当一个指针再从开始出后移时,另一个指针从相遇点开始后移时,这两个指针就会在循环开始处相遇。
代码为:
node* findLoopPlace(node* head, unsigned int* place = NULL)
{
//查找循环的位置,place存储位置
if (!loop(head))
{
return NULL;
}
node* one = head;
node* two = head->next;
unsigned int count = 1;
while (one != two)
{
one = one->next;
two = two->next->next;
}
one = head;
while (one != two)
{
if (count != 1)
{
one = one->next;
}
two = two->next;
count++;
}
*place = count;
return one;
}
问题5:如何查找链表中倒数第k个节点?
思想为:两个指向头结点的指针,一个先向后移动k位,然后两个同时向后面移动直到一个节点到达链尾,前面一个指针的位置就是了。
node* findLastK(node* head,unsigned int k)
{
//查找单链表倒数第k个位置
node* p = head;
unsigned int count = 0;
while (p != NULL)
{
p = p->next;
count++;
}
if (count < k)
{
return NULL;
}
p = head;
node* q = head;
for (unsigned int i = 0; i < k; i++)
{
p = p->next;
}
while (p != NULL)
{
q = q->next;
p = p->next;
}
return q;
}
问题6:编程序判断两个链表是否相交。
这个问题的精彩解说请参见《编程之美》一书之《编程判断两个链表是否相交》,这里就不写了,该书的pdf文档在网上很好下。
文章后面给了两个扩展问题:
(1)如果链表可能有环,如何做判断?
思想为:首先应该明白,只有一个链表有环的情况下是不会相交的,只有都有环或者都没有环的情况下才可能相交,都没有环的情况下最简便的方法就是判断链尾是否相交即可;都有环的情况下,分别找到环上的任一点,一个不动,另一个步进,即可判断是否相交。
(2)如何求相交链表的第一个节点?应该为单链表情况
思想为:方法一是先把任一个链表连成环,即从表尾接到表头,按照问题4的解法;方法二是计算两个链表的长度,而两个链表是按照尾部对齐的,那么从短链表的第一个位置从长链表的第长度差+1的位置依次比较指针值,相等的位置即是。
相关程序包括:单链表中在某个位置插入环以及销毁链表等,代码如下:
void insertCircle(node* head, unsigned int n)
{
//在第n个位置形成环,记head为n=1
node* p = head;
node* q = head;
unsigned int count = 1;
while(p->next != NULL)
{
p = p->next;
count++;
}
if (n <= count)
{
for (unsigned int i = 1; i < n; i++)
{
q = q->next;
}
p->next = q;
}
return;
}
void destroy(node* head)
{
//销毁链表
if (loop(head))
{
node *q = findLoopPlace(head);
while (head != q)
{
node* p = head;
head = head->next;
delete p;
}
head = head->next;
q->next = NULL;
destroy(head);
}
else
{
while (head != NULL)
{
node* p = head;
head = head->next;
delete p;
}
}
}
发表评论
-
不使用/,%,+和*,如何判断一个数能否被3整除
2012-05-30 14:28 1751如果n的二进制末位为0,那么n和n>>1同时被 ... -
一些数学知识
2012-03-31 20:12 820zz:http://hi.baidu.com/imak ... -
高阶幂的求余的方法
2012-03-31 16:41 2730通常会有如下问法: 有两个数,A和B,A的范围 ... -
从N个变量中找出一个错误变量的方法
2012-03-31 12:17 834假设有N包咖啡,里面有一包咖啡是掺和了沙子的,可以将咖啡放到水 ... -
【转】大数据量算法
2012-03-06 16:11 1224第一部分、十五道海量数据处理面试题 1. 给定a、b两个 ... -
Trie Tree
2010-10-26 11:34 1453给你100000个长 ... -
字典树(trie tree)
2010-10-26 11:19 1365今天AC了两题tri ... -
高度为n的平衡二叉树最少需要多少个节点
2010-10-24 13:42 9375递推关系 A(1)=1 A(2)=2 A ... -
如何判断两个单向链表是否有相交,并找出交点
2010-10-24 13:37 1681题比较简单,单向链表有交点意思就是交点后的节点都是 ... -
大数据排序或取重或去重相关问题解决方案
2010-10-21 16:13 2753Q:TC群里有人发消息说在10亿个数据中找出所有的重复数,内存 ... -
分配排序(桶排序..)
2010-10-21 13:39 1852分配排序的基本思想:排序过程无须比较关键字,而是通过&qu ... -
Rete(3)
2010-10-21 09:59 9574.6 连接节点(Join node) ... -
Rete(2)
2010-10-21 09:57 1136使用RETE算法的模块系统 ... -
Rete(1)
2010-10-21 09:53 1032一、 rete概述Rete算法是一种前向规则快速匹配算法,其匹 ... -
[转]海量数据处理面试题
2010-10-20 15:15 10051. 给定a、b两个文件,各存放50亿个url,每个url各占 ... -
用JDBC实现数据的分页
2010-10-20 11:23 1201数据分页主要用到了resultSet的absolute()方法 ... -
如何求N的阶乘所得的数字末尾含有多少个0
2010-10-19 13:13 2147原题是这样: 给定 ... -
数据库笔试题(经典SELECT语句用法)
2010-10-18 22:49 2090问题描述: 为管理岗位业务培训信息,建立3个表: S ... -
Java分页实现
2010-10-18 22:11 1479Java代码 public interf ... -
Linux下大文件的排序和去重复
2010-10-15 10:02 2096Linux下我们用 sort 与 uniq 的命令来实现去重复 ...
相关推荐
C++常见笔试题和面试题目-富士通南大软件 ①链表反转 单向链表的反转是一个经常被问到的一个面试题,也是一个非常基础的问题。比如一个链表 是这样的: 1->2->3->4->5 通过反转后成为5->4->3->2->1。 最容易想到的...
常见的数据结构有数组、链表、栈、队列、树、图等。 算法则是解决特定问题的步骤,是对数据运算和操作的详细描述。算法的设计和选择会直接影响到程序的效率,因此,在设计和选择算法时,需要考虑到时间复杂度、空间...
21. C语言编程常见问题分析 108 22. C语言编程易犯毛病集合 112 23. C语言缺陷与陷阱(笔记) 119 24. C语言防止缓冲区溢出方法 126 25. C语言高效编程秘籍 128 26. C运算符优先级口诀 133 27. do/while(0)的妙用 134 ...
21. C语言编程常见问题分析 108 22. C语言编程易犯毛病集合 112 23. C语言缺陷与陷阱(笔记) 119 24. C语言防止缓冲区溢出方法 126 25. C语言高效编程秘籍 128 26. C运算符优先级口诀 133 27. do/while(0)的妙用 134 ...
21. C语言编程常见问题分析 108 22. C语言编程易犯毛病集合 112 23. C语言缺陷与陷阱(笔记) 119 24. C语言防止缓冲区溢出方法 126 25. C语言高效编程秘籍 128 26. C运算符优先级口诀 133 27. do/while(0)的妙用 134 ...
21. C语言编程常见问题分析 108 22. C语言编程易犯毛病集合 112 23. C语言缺陷与陷阱(笔记) 119 24. C语言防止缓冲区溢出方法 126 25. C语言高效编程秘籍 128 26. C运算符优先级口诀 133 27. do/while(0)的妙...
21. C语言编程常见问题分析 108 22. C语言编程易犯毛病集合 112 23. C语言缺陷与陷阱(笔记) 119 24. C语言防止缓冲区溢出方法 126 25. C语言高效编程秘籍 128 26. C运算符优先级口诀 133 27. do/while(0)的妙用 134 ...
21. C语言编程常见问题分析 108 22. C语言编程易犯毛病集合 112 23. C语言缺陷与陷阱(笔记) 119 24. C语言防止缓冲区溢出方法 126 25. C语言高效编程秘籍 128 26. C运算符优先级口诀 133 27. do/while(0)的妙用 134 ...
21. C语言编程常见问题分析 108 22. C语言编程易犯毛病集合 112 23. C语言缺陷与陷阱(笔记) 119 24. C语言防止缓冲区溢出方法 126 25. C语言高效编程秘籍 128 26. C运算符优先级口诀 133 27. do/while(0)的妙用 134 ...
21. C语言编程常见问题分析 108 22. C语言编程易犯毛病集合 112 23. C语言缺陷与陷阱(笔记) 119 24. C语言防止缓冲区溢出方法 126 25. C语言高效编程秘籍 128 26. C运算符优先级口诀 133 27. do/while(0)的妙用 134 ...
C语言编程常见问题分析 ............................................................................................................ 97 22. C语言编程易犯毛病集合 ..........................................