单链表删除操作

Question

typedef struct Node
{
string name;
string tel;
Node * next;
}linkList;

/************************************************************************/
/* 函数名: deleteNode（链表指针，节点位置） */
/* 函数作用: 删除一个已存在的记录 */
/************************************************************************/
void deleteNode(linkList *list, int location)
{
linkList *p;
int cnt;

p = list;
cnt = 0;
while (p && cnt != location - 1)
{
cnt++;
p = p->next;
}

// 删除节点，释放内存空间
p->next = p->next->next;
delete p->next;
}

/************************************************************************/
/* 函数名: displayAll */
/* 函数作用: 显示通讯录所有记录 */
/************************************************************************/
void displayAll(const linkList * list)
{
linkList *p;
int cnt;

p = list->next;
cnt = 1;
while (p)
{
cout << "Case " << cnt << ":" << endl;
cout << " name: " << p->name << endl;
cout << " phone: " << p->tel << endl;

cnt++;
p = p->next;
}
}
感觉删除出了问题 , 删掉哪个位置的结点 , displayAll的时候再到那个位置结点就会出问题

再有人拿随便搜的答案糊弄人就把问题关掉 一楼的哥们忒垃圾

/************************************************************************/
/* 函数名: sortNode() */
/* 函数作用: 对链表进行排序(冒泡法) */
/************************************************************************/
void sortNode(linkList *&list)
{
linkList *p;
linkList *q;

p = list;
while ( p->next )
{
q = p->next;
while (q->next)
{
// 按name排序
if (p->next->name[0] > q->next->name[0]) // 条件为真，交换两节点位置
{
linkList *temp;

temp = p->next->next;
p->next->next = q->next->next;
q->next->next = temp;

p->next = q;
q->next = p;
}
q = q->next;
}
p = p->next;
}
}
这个函数无法实现排序功能 搞了半天了 还是没法实现排序 急~！！

Answer 1

// 删除节点，释放内存空间
p->next = p->next->next;
delete p->next;
******************************************
若链表为：
链表节点 | 1 | 2 | 3 |...
对应指针 | p | p->next | p->next->next|...

你想删除节点2（p->next），
但你的做法是：
p->next = p->next->next;（1的下一个由指向2改为指向3）；
链表节点 | 1 | 2 | 3 |...
对应指针 | p | | p->next |...
delete p->next;（删除3）
这就错了，若要删除必须先将被删的节点2保存给临时变量，修改链表后再删除。正确的做法是：
linkList* tmp = NULL;
...
tmp = p->next;
p->next = p->next->next;
delete tmp;

另外，while (p && cnt != location - 1)这种写法虽然正确，但很不规范且危险，容易出现优先级和默认值的疏忽。

关于你补充的问题，不分析你的代码了，直接给你重写一个吧，看懂了就可以自己改了。
void Sort(linkList* L)
{
bool done_flag = FALSE;
linkList* p = L;
linkList* temp = NULL;

if (p->next == NULL)
{
return;
}

/*你的链表结构存在独立首节点，所以p可以直接做两个交换节点的父节点*/

/*若未发现乱序，说明已经排好*/
while(!done_flag)
{
done_flag = TRUE;

/*遍历链表 保证p下至少存在两个节点*/
while(p->next->next != NULL)
{
/*若顺序错误则对换*/
if (p->next->name[0] > p->next->next->name[0])
{
/*存在乱序*/
done_flag = FALSE;

/*链表：p p1 p2 p3*/
/*交换p1 p2*/

/*temp 指向 p1*/
temp = p->next;

/*p 的下一个改为 p2*/
p->next = p->next->next;

/*将 p3挂到p1后面，此时p的下一个是p2，所以p的下一个的下一个是p3，temp此时为p1*/
temp->next = p->next->next;

/*p 的下一个此时为 p2，将p2的下一个指向 temp(p1)*/
p->next->next = temp;
}

/*p后移*/
p = p->next;
}
}
}

bool你那里有问题的话，可以改为int或char。

结题吧。

Answer 2

单链表的删除操作是指删除第i个结点，返回被删除结点的值。删除操作也需要从头引用开始遍历单链表，直到找到第i个位置的结点。如果i为1，则要删除第一个结点，则需要把该结点的直接后继结点的地址赋给头引用。对于其它结点，由于要删除结点，所以在遍历过程中需要保存被遍历到的结点的直接前驱，找到第i个结点后，把该结点的直接后继作为该结点的直接前驱的直接后继。删除操作如图

单链表的删除操作示意图

删除操作的算法实现如下：
public T Delete(int i)
{
if (IsEmpty()|| i < 0)
{
Console.WriteLine("Link is empty or Position is error!");
return default(T);
}
Node q = new Node();
if (i == 1)
{
q = head;
head = head.Next;
return q.Data;
}
Node p = head;
int j = 1;
while (p.Next != null&& j < i)
{
++j;
q = p;
p = p.Next;
}
if (j == i)
{
q.Next = p.Next;
return p.Data;
}
else
{
Console.WriteLine("The ith node is not exist!");
return default(T);
}
}
算法的时间复杂度分析：单链表上的删除操作与插入操作一样，时间主要消耗在结点的遍历上。如果表为空则不进行遍历。当表非空时，删除第i个位置的结点， i等于1遍历的结点数最少（1个），i等于n遍历的结点数最多（n个，n为单链表的长度），平均遍历的结点数为n/2。所以，删除操作的时间复杂度为O（n）。