1 单链表的定义
线性表的链式存储又称为单链表。它是指通过一组任意的存储单元来存储线性表中的数据元素。
单链表的结点类型的描述如下：
typedef int ElemType;
typedef struct LNode { //定义单链表结点类型
ElemType data; //数据域
struct LNode *next; //指针域
} LNode, *LinkList;
2 单链表上基本操作的实现
设结点的数据类型是整型，32767作为结束标志。
1）采用头插法建立单链表
该方法从一个空表开始，生成新结点，并将读取到的数据存放到新节点的数据域中，然后将新结点插入到当前链表的表头，即头结点之后。
LNode *createLinkList(void) {
int data;
LNode *head, *p;
//创建头结点
head = (LNode *) malloc(sizeof(LNode));
//初始为空链表
head->next = NULL;
while (1) {
scanf("%d", &data);
if (data == 32767) {
break;
}
p = (LNode *) malloc(sizeof(LNode));
//数据域赋值
p->data = data;
//新结点总是作为第一个结点
p->next = head->next;
head->next = p;
}
return head;
}
采用头插法建立单链表，读入数据的顺序与生成的链表中的元素的顺序是相反的。每个结点的插入的时间为O(1)，设单链表长为n，则总的时间复杂度为O(n)。
2）采用尾插法建立单链表
头插法生成的链表中结点的次序与输入数据的顺序不一致。若希望两者次序一致，可采用尾插法。为此必须增加一个尾指针last，使其始终指向当前链表的尾结点。
LNode *createLinkList2(void) {
int data;
LNode *head, *last, *p;
//创建头结点
head = (LNode *) malloc(sizeof(LNode));
//初始尾结点就是头结点
last = head;
while (1) {
scanf("%d", &data);
if (data == 32767) {
break;
}
p = (LNode *) malloc(sizeof(LNode));
p->data = data;
//头结点的下一个为p
last->next = p;
//last指向新的尾结点
last = p;
}
last->next = NULL;
return head;
}
时间负责度为O(n)。
3）按序号查找结点值
在单链表中从第一个结点出发，顺指针next逐个往下搜索，直到找到第i个结点为止，否则返回最后一个结点指针域NULL。
//取出单链表L（带头结点）第i个位置的结点指针
LNode *getElem(LinkList L, int i) {
int j = 1;
LNode *p = L->next;
if (i == 0) {
return L;
}
if (i < 1) {
return NULL;
}
//while(p)等价于while(p != NULL)
while (p && j < i) {
p = p->next;
j++;
}
return p;
}
按序号查找的时间复杂度为O(n)。
4）按值查找表结点
从单链表第一个结点开始，由前往后依次比较表中各结点数据域的值，若某结点数据域的值等于给定值e，则返回该结点的值；若整个单链表中没有这样的结点，则返回NULL。
LNode *LocateElem(LinkList L, ElemType e) {
LNode *p = L->next;
while (p && e != p->data) {
p = p->next;
}
return p;
}
5）插入结点操作
插入操作是将值为x的新结点插入到单链表的第i个位置上。先检查插入位置的合法性，然后找到待插入位置的前驱结点，即第i-1个结点，再在其后插入新结点。
void InsertLNode(LNode *L, int i, ElemType e) {
int j = 0;
LNode *p;
p = L->next;
while (p && j < i - 1) {
p = p->next;
j++;
}
if (j != i - 1) {
printf("i太大或i为0");
} else {
LNode *q = (LNode *) malloc(sizeof(LNode));
q->data = e;
//以下两步不能颠倒
q->next = p->next;
p->next = q;
}
}
本算法主要的时间开销在于查找i-1个元素，时间复杂度为O(n)。若是在给定的结点后面插入新结点，则时间复杂度仅为O(1)。
6）删除结点操作
①按序号删除
删除第i个结点。
void DeleteLinkList(LNode *L, int i) {
int j = 0;
LNode *p = L->next;
while (p && j < i - 1) {
p = p->next;
j++;
}
if (j != i - 1) {
printf("i太大或i为0");
} else {
LNode *q = p->next;
p->next = q->next;
//释放结点的存储空间f
free(q);
}
}
时间复杂度为O(n)。
②按值删除
删除单链表中值为key的第一个结点。
void DeleteLinkList2(LNode *L, ElemType e) {
LNode *p = L;
LNode *q = p->next;
while (q && e != q->data) {
p = q;
q = q->next;
}
if (q->data != e) {
printf("所要删除的结点不存在");
} else {
p->next = q->next;
free(q);
}
}
时间复杂度为O(n)。
③变形一：
删除单链表中值为key的所有结点。
void DeleteLinkList3(LNode *L, ElemType e) {
LNode *p = L;
LNode *q = p->next;
while (q) {
if (e == q->data) {
p->next = q->next;
free(q);
} else {
p = q;
q = q->next;
}
}
}
④变形二：
删除单链表中所有值重复的结点，使得所有结点的值都不相同。
void DeleteLinkList4(LNode *L) {
LNode *p = L->next;
LNode *q, *ptr;
while (p) {
q = p;
ptr = q->next;
while (ptr && ptr->data != p->data) {
q = ptr;
ptr = ptr->next;
}
if (ptr->data == p->data) {
q->next = ptr->next;
free(ptr);
}
p = p->next;
}
}
时间复杂度O(n2)，需优化。
