文章目录
带头结点的单链表
- 带头结点的单链表中，head指向的是头结点，不是实际结点
- 第一个实际结点 head->next
建立空的单链表
不带头结点
node *init()
{
return NULL;
}
带头结点(要申请空间)
node *head;
head=(node*)malloc(sizeof(node));
head->next=NULL；
return head;
插入
尾插法建立带头结点的的单链表
- 申请空间
- 将x赋值s info域
- r->next=s 将s添加
- r往后移 r=s
- 最后 r->next=NULL
头插法建立单链表
带结点
头结点链表头插入
头结点中间插入
不带头结点
插入链表开头
x->next=head->next;
head=x//这里不是head->next=x
插入链表其他位置
用p等于插入前的结点
x->next=p->next;
p->next=x;
删除
头结点
p等于删除前的结点
p->next=x->next;
free(x)
不带头结点
p等于删除前的结点
- 删除第一个结点
head=head->next;
- 删除其他结点
p->next=x->next;//p的下一结点指向x的下一结点，将x置空
free(x)
查找
查找初始化
pre=head;
p=head->next;
查找
while(p&p->info!=x){
pre=p;p=p->next;
}
链表带头结点和不带头结点的区别
所有链表都有一个头指针head，带头结点中head数据为空，不带头结点在头结点存在数据，此时从头插入数据是时，head时刻变化。
带头结点head->next=p
不带头结点 没有head->next
循环单链表
插入
在最前面插入带x的新结点
在中间插入（两步）
删除
在最前面删除带x的新结点（3）
q=head;//保留被删除点地址
head=q->next;
pre->next=head;
free(p);
在中间删除带x的新结点（找到删除点的前驱）
pre->next=p->next;
free(p);
不明白：为什么要保留被删除结点位置?
前两行为什么不直接写成head=head->next?
课后答疑
前两行为什么不直接写成head=head->next?
因为要保存被删除点的地址，否则这个地址会游离，造成很多不确定性事件插入元素的平均移动个数
1/（n+1）* n(n+1)/2 = n/2
(3+1)/6=4
0+1+1=2
队首删除，队尾插入
- 已知
循环队列存储在一个数组中，数组大小为n,队首指针和队尾指针分别为front和rear，写出循环队列中当前结点的表达式
（n+rear-front）%n