Posted on 2006-06-23 15:55
Enjoy Life 阅读(381)
评论(0) 编辑 收藏 引用 所属分类:
程序员面试功略
已知有一个单链表的两个指针,一个指向单链表的头部,一个指向单链表的尾部,
写出在链表中删除/插入一个元素的算法.
typedef struct elemT{
void *data;
struct elemT *next;
}element;
#define OK 1
#define ERROR 0
element *head;
element *tail;
删除:应该考虑的问题有:
1
、当删除的是head时应该如何处理
2
、当删除的是tail时应该如何处理
3
、当删除的是list中间的成员时应该如何处理
4
、当list只有一个成员时应该如何处理
int DeleteElem(element *elem){
element *CurPos;
CurPos = head;
if(!elem)
return 0;
if(elem == head){
head = head->next;
free(elem);
/*special case for 1 element list*/
if(!head)
tail = NULL;
return OK;
}
while(CurPos){
if(CurPos->next = elem){
CurPos->next = elem->next;
free(elem);
if(CurPos->next == NULL)
tail = CurPos;
return 1;
}
CurPos = CurPos->next;
}
return 0;
}
插入：应该考虑的情况有：
1
、插入在表头，即elem == NULL;
2
、当表是空表时，即head=tail==NULL;
int InsertAfter(element *elem, int data){
element *NewAdd;
element *CurPos;
CurPos = head;
NewAdd = (element *)malloc(sizeof(element));
if(!NewAdd)
return ERROR;
NewAdd->data = data;
/*Special for insert in the head*/
if(!elem){
NewAdd->next = head;
head = NewAdd;
/*Special for a NULL List,Need to modify tail pointer*/
if(!tail)
tail = NewAdd;
return 1;
}
while(CurPos){
if(CurPos == elem){
NewAdd->next = elem->next;
elem->next = NewAdd;
/*Special for insert in the tail*/
if(!(NewAdd->next))
tail = NewAdd;
return 1;
}
CurPos = CurPos->next;
}
/*Insert Position not found */
free(NewAdd);
return 0;
}