一.单链表的设计

1.单链表的结构定义:

typedef struct Node{
int data;//数据域
struct Node* next;//后继指针
}Node,*List;

2.单链表的设计示意图:

3.注意:

单链表的最后一个节点的next域为NULL;

4.为什么要有一个头节点?

简单方便,不用传二级指针;

二.单链表的实现

//初始化
}//考试重点
//删除第一个val的值
bool DelVal(List plist, int val)
{Node* p = GetPrio(plist, val);if (p == NULL)return false;Node* q = p->next;//删除qp->next = q->next;//p->next=p->next->next;//释放qfree(q);return true;
}//返回key的前驱地址，如果不存在返回NULL；
Node* GetPrio(List plist, int key)
{for (Node* p = plist; p->next != NULL; p = p->next){if (p->next->data == key)return p;}return NULL;
}//返回key的后继地址，如果不存在返回NULL；
Node* GetNext(List plist, int key)
{assert(plist != NULL);if (plist == NULL)return NULL;Node* p = Search(plist, key);if (p == NULL)return NULL;return p->next;
}//输出
void Show(List plist)
{//注意，头节点不能访问datafor (Node* p = plist->next; p != NULL; p = p->next){printf("%d ", p->data);}printf("\n");
}//清空数据
void Clear(List plist)
{Destroy(plist);
}void Destroy(List plist)
{//总是删除第一个数据节点Node* p;while (plist->next != NULL){p = plist->next;plist->next = p->next;free(p);//error//plist->next = plist->next->next;//free(plist->next);}
}

三.单链表的总结

1.单链表的特点：

头插，头删 时间复杂度是O(1)

尾插，尾删 时间复杂度是O(n)

2.P初始化成什么?

如果我们要修改表的结构(或者说依赖于前驱,比如插入,删除):遍历:

for(Node *p=plist;p->next!=NULL;p=p->next)

如果我们不修改表的结构(或者说不依赖于前驱, 比如求长度,打印,查找) :遍历:

for (Node* p = plist->next; p != NULL; p = p->next)

3.注意考点:

头插,尾插,按值删除;