先说明一下相关概念:
单链表: 单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据。
结点结构: ┌───┬───┐ │data │next │ └───┴───┘ data域–存放结点值的数据域 next域–存放结点的直接后继的地址(位置)的指针域(链域) 链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的,每个结点只有一个链域的链表称为单链表。
头结点: 在单链表第一个元素结点之前设置的一个结点,数据域可以不存任何信息,指针域指向单链表第一个元素的结点。减少了单链表添加删除时特殊情况的判断,减少了程序的复杂性。
头指针: 指向单链表的第一个结点的指针,如果单链表有头结点,则头指针指向头结点,如果单链表没有头结点,则头指针指向单链表中第一个有数据元素的结点。
尾节点: 终端结点无后继,故终端结点的指针域为空,即NULL。
头结点型单链表:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef struct node
{
int item;
struct node *next;
}node;
node sential = {0, NULL};/*node型的空*/
node *head = &sential;/*将空地址指向头结点*/
node *mk_node(int item)/*创建结点*/
{
node *p = (node *)malloc(sizeof(node));/*分配地址空间*/
if (p == NULL)
{
printf("malloc failed\n");
exit(1);
}
p->item = item;
p->next = NULL;
return p;
}
void free_node(node *p)/*释放结点资源*/
{
free(p);
}
void insert_node(node *p)/*插入结点*/
{
p->next = head->next;/*head->next为空,赋给p->next,使p之后空*/
head->next = p;/*p赋给head->next,使得p和空头结点连接*/
}
void traverse()/*遍历链表*/
{
node *p = head->next;
while (p != NULL)
{
printf("%d ", p->item);
p = p->next;
}
printf("\n");
}
node *search(int target)/*链表查询*/
{
node *p = head->next;
while (p != NULL)
{
if (p->item == target)
{
return p;
}
p = p->next;
}
return NULL;
}
void rm_node(node *p)/*删除结点p*/
{
node *pre = head;
while (pre->next != NULL)
{
if (pre->next == p)
{
pre->next = p->next;
return;
}
pre = pre->next;
}
}
void destroy()/*结点销毁*/
{
node *p ;
while (head->next != NULL)
{
p = head->next;
head->next = p->next;
free_node(p);
}
}
void rm_x_node(int x)/*删除数据域为x的结点*/
{
node *p;
while ((p = search(x)) != NULL)
{
rm_node(p);
free_node(p);
}
}
void rm_x_node2(int x)/*(方法二)删除数据域为x的结点*/
{
node *pre = head;
node *p;
while (pre->next != NULL)
{
p = pre->next;
if (p->item == x)
{
pre->next = p->next;
free_node(p);
continue;
}
pre = pre->next;
}
}
void rm_x_node_r(node *pre, int x)/*递归删除数据域为x的结点*/
{
node *p;
if (pre->next == NULL)
{
return;
}
if (pre->next->item == x)
{
p = pre->next;
pre->next = p->next;
free_node(p);
rm_x_node_r(pre, x);
}else
{
rm_x_node_r(pre->next, x);
}
}
int main(int argc, char const *argv[])
{
int item;
int i;
int target;
node *p;
srand(time(NULL));
for (i = 0; i < 10; i++)
{
//item = rand() % 100 + 1;
if (i < 5)
{
item = 10;
}else
{
item = i + 1;
}
p = mk_node(item);
insert_node(p);
}
traverse();
scanf("%d", &target);
// p = search(target);
// if (p == NULL)
// {
// printf("can't find target in link\n");
// }else
// {
// printf("%p %d %d\n", p, p->item, target);
// rm_node(p);
// printf("%d\n", p->item);
// free_node(p);
// p = NULL;
// traverse();
// }
// rm_x_node2(target);
// traverse();
rm_x_node_r(head, target);
traverse();
destroy();
traverse();
return 0;
}
头指针型单链表:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef struct node
{
int item;
struct node *next;
}node;
node *head = NULL;
node *mk_node(int item) /*动态链表内存分配*/
{
node *p = (node *)malloc(sizeof(node));
if (p == NULL)
{
printf("malloc failed\n");
exit(1);
}
p->item = item;
p->next = NULL;
return p;
}
void insert_node(node *p) /*头插*/
{
p->next = head;
head = p;
}
void traverse() /*遍历*/
{
node *p = head;
while (p != NULL)
{
printf("%d ", p->item);
p = p->next;
}
printf("\n");
}
node *search(int target) /*查找*/
{
node *p = head;
while (p != NULL)
{
if (p->item == target)
{
return p;
}
p = p->next;
}
return NULL;
}
void rm_node(node *p) /*删除指定结点*/
{
node *pre = head;
if (p == head)
{
head = head->next;
p->next = NULL;
return;
}
while (pre->next != NULL)
{
if (pre->next == p)
{
pre->next = p->next;
p->next = NULL;
return;
}
pre = pre->next;
}
}
void free_node(node *p) /*释放*/
{
free(p);
}
void destroy() /*销毁*/
{
node *p;
while (head != NULL)
{
p = head;
head = head->next;
//printf("%d ", p->item);
free_node(p);
}
//printf("\n");
}
void rm_x_node(int x) /*删除指定结点,每次从头开始,时间复杂度高*/
{
node *p;
while ((p = search(x)) != NULL)
{
rm_node(p);
free_node(p);
}
}
void rm_x_node2(int x) /*删除指定结点,从头开始,遇到则退出,时间复杂度较上低*/
{
node *pre = head;
node *p;
if (head == NULL)
{
return;
}
while (pre->next != NULL)
{
p = pre->next;
if (p->item == x)
{
pre->next = p->next;
free_node(p);
continue;
}
pre = pre->next;
}
if (head->item == x)
{
p = head;
head = head->next;
free_node(p);
}
}
void rm_x_node_m(node *pre, int x) /*递归删除指定结点,除首部*/
{
node *p;
if (pre == NULL || pre->next == NULL)
{
return;
}
if (pre->next->item == x)
{
p = pre->next;
pre->next = p->next;
free_node(p);
rm_x_node_m(pre, x);
}else
{
rm_x_node_m(pre->next, x);
}
}
void rm_x_node_r(node *pre, int x) /*递归删除指定结点时对首部的考虑,并调用上一函数*/
{
node *p;
rm_x_node_m(head, x);
if (head->item == x)
{
p = head;
head = head->next;
free_node(p);
}
}
void reverse() /*链表反转*/
{
node *nhead = NULL;
node *p;
while (head != NULL)
{
p = head;
head = head->next;
p->next = nhead;
nhead = p;
}
head = nhead;
}
int main()
{
int item;
int i;
int target;
node *p;
srand(time(NULL));
for (i = 0; i < 10; i++)
{
//item = rand() % 100 + 1;
if (i < 5)
{
item = 10;
}else
{
item = i + 1;
}
p = mk_node(item);
insert_node(p);
}
traverse();
scanf("%d", &target);
// p = search(target);
// if (p == NULL)
// {
// printf("can't find target in link\n");
// }else
// {
// printf("%p %d %d\n", p, p->item, target);
// rm_node(p);
// printf("%d\n", p->item);
// free_node(p);
// p = NULL;
// traverse();
// }
reverse();
traverse();
rm_x_node_r(head, target);
traverse();
destroy();
traverse();
return 0;
}