超难面试题，跪求答案。在线等啊
一美资公司上机题目。
设计一个链表，要求插入和删除的时间复杂度为O(1)。而且不能使用哈西。那位高人指点一下。
[解决办法]
本来连表就用来快速插入和删除的啊
[解决办法]
# include "stdlib.h "
# include "malloc. h "
struct node /*节点的数据结构*/
{
int num;
char str[20];
struct node *next;
} ;
/* * * * * * * * * * * * * * * * * * * * * * * * * * * */
main( )
{
/*函数声明*/
struct node *creat();
struct node *insert();
struct node *delet();
void print( );
struct node *head;
char str[20];
int n;
head=NULL; /*做空表*/
head=creat (head); /*调用函数创建以head 为头的链表*/
p r i n t ( h e a d ) ；/*调用函数输出节点*/
printf( "\n input inserted num,name:\n ");
gets(str); /*输入学号*/
n=atoi (str);
gets(str); /*输入姓名*/
head=insert (head, str, n); 将/*节点插入链表*/
print (head)； /*调用函数输出节点*/
printf( "\n input deleted name:\n ");
gets(str); /*输入被删姓名*/
head=delet(head,str); /调*用函数删除节点*/
print (head); /*调用函数输出节点*/
r e t u r n ;
}
/* * * * * * * * * * * * * * * * * * * * * */
/* * * 创建链表* * * * * * * * * * * */
struct node *creat(struct node *head)
{
char temp[30];
struct node *pl,*p2;
pl=p2=(struct node*) malloc(sizeof(struct node));
printf ( "input num, name: \n; ")
printf( "exit:double times Enter!\n ");
g e t s ( t e m p ) ;
gets (p1-> str);
pl-> num=atoi (temp);
p l - > n e x t = N U L L ;
while (strlen (pl-> str)> 0
{
if (head==NULL) head=pl；
else p2-> next=p1;
P 2 = p l ；
pl=(struct node *)malloc(sizeof(struct node));
printf ( "input num, name: \n ");
printf( "exit:double times Enter!\n ");
g e t s ( t e m p ) ;
gets(pl -> str);
p1-> num=atoi (temp);
P 1 - > n e x t = N U L L ;
}
return head;
}
/* * * * * * * * * * * * * * * * * * * */
/* * * * * * * * * * 插入节点* * * * * * * * * */
struct node *insert (struct node *head, char *pstr,int n);
{
struct node *pl,*p2,*p3;
p1=(struct node*)malloc(sizeof(struct node));
strcpy (p1-> str, pstr);
p 1 - > n u m = n ;
p 2 = h e a d ;
if(head==NULL)
{
head=pl;pl-> next=NULL;
}
else
{
while (n> p2-> num&&p2-> next!=NULL)
{
p 3 = P 2
p 2 = p 2 - > n e x t ;
}
if (n <=p2-> num)
if (head==p2)
{
h e a d = p l ;
p l - > n e x t = p 2 ;
}
else
{
p 3 - > n e x t = p l ;
p l - > n e x t = p 2 ;
}
else
{
p 2 - > n e x t = p l ;
p l - > n e x t = N U L L ;
}
}
r e t u r n ( h e a d ) ;
}
/* * * * * * * * * * * * * * * * * * * * * * * * * /
/ * * * * * 删除节点* * * * * * * * * * * * */
struct node *delet (struct node *head, char *pstr)
{
struct node *temp,*p;
temp = head ;
if (head==NULL)
printf( "\nList is null!\n ");
else
{
temp = head ;
while (strcmp(temp-> str,pstr)!=O&&temp-> next!=NULL)
{
p = temp ;
temp=temp-> next,
}
if(strcmp(temp-> str,pstr)==0)
{
if (temp== head)
{
head=head-> next;
free( temp ) ;
}
else
{
p-> next =temp-> next;
printf( "delete string :%s\n ",temp-> str);
f r e e ( t e m p ) ;
}
}
else printf( "\nno find string!\n ");
}
return(head);
}
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * /
/ * * * * * * * * * * 链表各节点的输出* * * * * * * * * */
void print (struct node *head)
{
struct node *temp;
t e m p = h e a d ;
printf( "\n output strings:\n ");
while (temp!=NULL)
{
p r i n t f ( " \ n % d - - - - % s \ n " , t e m p - > n u m ，t e m p - > s t r ) ；
t e m p = t e m p - > n e x t ；
}
r e t u r n ;
}
[解决办法]
#include <stdio.h>
#include <malloc.h>
typedef struct node //定义双链表
...{
int data;
struct node *prior;
struct node *next;
}snode;
snode *creat() //创建双链表
...{
snode *head, *p, *q;
int x;
head = (snode *)malloc(sizeof(snode));
q = head;
printf( "请输入创建双链表的值,以-1结束. ");
printf( "x = ");
scanf( "%d ", &x);
while (x != -1)
...{
p = (snode *)malloc(sizeof(snode));
p-> data = x;
q-> next = p;
p-> prior = q;
q = p;
printf( "x = ");
scanf( "%d ", &x);
}
q-> next = NULL;
return head;
}
void display(snode *head)
...{
snode *p = head-> next;
while (p != NULL)
...{
printf( "%4d ", p-> data);
p = p-> next;
}
printf( " ");
}
int length(snode *head)//测链表的结点数
...{
snode *p = head-> next;
int i = 0;
while (p != NULL)
...{
p = p-> next;
i++;
}
return i;
}
void opposite(snode *head)
...{
snode *p = head-> next;
while (p-> next != NULL)
p = p-> next;
while (p != head)
...{
printf( "%4d ", p-> data);
p = p-> prior;
}
printf( " ");
}
int insnode(snode *head, int x, int i) //把x插入到链表的第i的位置
...{
snode *p = head-> next, *s;
if(i < 1 || i > length(head) + 1)
return 0;
else if (i == 1)
...{
s = (snode *)malloc(sizeof(snode)); //分配内存
s-> next = p;
p-> prior = s;
s-> prior = head;
head-> next = s;
s-> data = x;
}
else
...{
s = (snode *)malloc(sizeof(snode)); //分配内存
for (int j = 1; j < i - 1; j++)
p = p-> next;
if (p-> next != NULL)
...{
s-> next = p-> next;
p-> next-> prior = s;
p-> next = s;
s-> prior = p;
s-> data = x;
}
else
...{
s-> next = NULL;
p-> next = s;
s-> prior = p;
s-> data = x;
}
}
return 1;
}
int delnode(snode *head, int i)//删除链表中第i个结点
...{
snode *p = head-> next, *q = head;
if(i < 1 || i > length(head))
return 0;
else
...{
for (int j = 1; j < i; j++)
...{
p = p-> next;
q = q-> next;
}
if (p-> next != NULL)
...{
q-> next = p-> next;
p-> next-> prior = q;
}
else
q-> next = p-> next;
free(p);
}
return 1;
}
int main(void)
...{
snode *headl = creat(); //创建双链表
printf( "最初的链表如下： ");
display(headl);
printf( "为了证明是双链表反向输出： ");
opposite(headl);
int num, location;
printf( "请分别输入您要插入到链表中的数以及想插入的位置： ");
scanf( "%d %d ", &num, &location);
if (insnode(headl, num, location))
...{
printf( "插入新值以后的链表如下： ");
display(headl);
printf( "为了证明插入新值以后仍然是双链表，反向输出如下： ");
opposite(headl);
}
else
printf( "输入有误 ");
printf( "请输入您想删除的结点位置： ");
scanf( "%d ", &location);
if (delnode(headl, location))
...{
printf( "删除第%d个结点后的链表如下： ", location);
display(headl);
printf( "为了证明删除一个结点以后仍然是双链表，反向输出如下： ");
opposite(headl);
}
else
printf( "输入有误！ ");
}
[解决办法]
时间复杂度为o(1)，表示插入和删除所耗时间为常数值，即所耗时间不随数据规模的增大而增大。
在不使用辅助存储结构的情况下，还真想不到什么好办法。
如果使用的话就好办了，开个数组存下所有节点的指针，这部分所用时间复杂度为O（n）；
但之后所有删除和插入的复杂度都为o（1）。
不知道这样做合不合题意
[解决办法]
a--> b--> c--> d ... 删除b 时这样做, b = c , 然后删除 c 就是了, 不过对异构的链表就不好搞了 ...
[解决办法]
逻辑添加.删除就好了
(明白不)
[解决办法]
猛人啊,等待答案
如果使用的话就好办了，开个数组存下所有节点的指针，这部分所用时间复杂度为O（n）；
但之后所有删除和插入的复杂度都为o（1）。
不知道这样做合不合题意
------------------------------------------
这样行不行啊,人家应该是要的是此程序的复杂度,不仅仅是insert delete一个数据的复杂度吧
应该不是跟咱们玩文字游戏吧,毕竟是老外
[解决办法]
我看这样可以啊,添加我就不用说了,这个好实现,至于删除,这样弄
void dele(snode **head,snode *node)
{
if(node==(*head))
{
delete (*head);
(*head)=0;
}
else
{
//下面将头结点的值全copy到node结点
node-> data=(*head)-> data;
...
//然后将头结点前移一位,再删除原来头结点,
snode *p=(*head);
head=(*head)-> next;
delete p;
}
}
就是利用头结点来实现
[解决办法]
这个题目是一个大学考研的复式题
用空间换时间
把链表每个节点的指针留下作为一个数组
然后可以直接访问每个节点
插入和删除的时间复杂度就是o(1)
[解决办法]
#include <stdio.h>
typedef struct xlist_t xnode , xlist , *xpnode;
struct xlist_t
{
xpnode _next;
int _value;
};
#define xlist_init( __lH )((__lH)-> _next = (__lH))
#define xlist_insert_after( __n1 , __n )((__n)-> _next = (__n1)-> _next , (__n1)-> _next = (__n))
#define xlist_for_each( __lH , __p )for( p = (__lH)-> _next; p != (__lH) ; p = p-> _next )
int main()
{
xlist lH;
xnode a = {0, 'a '}, b={0, 'b '} , c={0, 'c '} , d={0, 'd '} , *p;
xlist_init( &lH );
xlist_insert_after( &lH , &a );
xlist_insert_after( &a , &b );
xlist_insert_after( &b , &c );
xlist_insert_after( &c , &d );
printf( "list_header " );
xlist_for_each( &lH , p )
printf( "--> %c " , p-> _value );
printf( "--> NULL\n " );
memcpy( &b , &c , sizeof( b ) );
printf( "after erase b , list_header " );
xlist_for_each( &lH , p )
printf( "--> %c " , p-> _value );
printf( "--> NULL\n " );
return 0;
}
[解决办法]
这样吧, 上面太难看了 ....
#include <stdio.h>
typedef struct xlist_t xnode , xlist , *xpnode;
struct xlist_t
{
xpnode _next;
int _value;
};
#define xlist_init( __lH )((__lH)-> _next = (__lH))
#define xlist_insert_after( __n1 , __n )((__n)-> _next = (__n1)-> _next , (__n1)-> _next = (__n))
#define xlist_for_each( __lH , __p )for( p = (__lH)-> _next; p != (__lH) ; p = p-> _next )
#define xlist_erase( __n )memcpy( (__n) , (__n)-> _next , sizeof( *(__n)) )
int main()
{
xlist lH;
xnode a = {0, 'a '}, b={0, 'b '} , c={0, 'c '} , d={0, 'd '} , *p;
xlist_init( &lH );
xlist_insert_after( &lH , &a );
xlist_insert_after( &a , &b );
xlist_insert_after( &b , &c );
xlist_insert_after( &c , &d );
printf( "list_header " );
xlist_for_each( &lH , p )
printf( "--> %c " , p-> _value );
printf( "--> NULL\n " );
xlist_erase( &b );
printf( "after erase b , list_header " );
xlist_for_each( &lH , p )
printf( "--> %c " , p-> _value );
printf( "--> NULL\n " );
xlist_erase( &a );
printf( "after erase b , list_header " );
xlist_for_each( &lH , p )
printf( "--> %c " , p-> _value );
printf( "--> NULL\n " );
return 0;
}
[解决办法]
常规的做法是不可能实现的, 不然人家STL干嘛不用常数时间的?
[解决办法]
Linux内核对进程表使用的也是双向链表，为了加快索引，同时采用了hash, 所以如果不用hash并且采用链表根本不可能达到O(1)的读写操作。
[解决办法]
还是强人多
[解决办法]
其实这道题还要主要看怎么理解这个 delete a specific node 删除指定的结点,觉得有点模糊
这个结点是给出来比如就是结点p,还是需要查找,如果值为p的结点.如果是前者我觉得我的算法没问题,如果是后者估计O(1)时间内实现,还要等等高人
[解决办法]
single link是不是单向链表啊.........
[解决办法]
single link 当然是当向连表拉
[解决办法]
历害