再话链表

前言

在学数据结构的时候,感觉知识点就没有形成一个体系,于是最近也在有意无意地把以前学习过的知识再串联起来。

1
2
3
4
struct node {
type data;
node* next;
}

线性表分为顺序表和链表,而链表也根据是否存在头节点分为带头的和不带头的。一般我们称带头的节点为头节点head,其数据域data不存放任何内容,其next域指向第一个节点。事实上,这两种链表的写法大同小异,这里统一使用带头的节点。同时,最后一个节点的next域指向NULL,即空地址。申请一个空间可以用stdlib.h文件下的malloc函数,即node* p=(node)malloc(sizeof(node));,这句话的逻辑是分配node所需要的大小作为参数,malloc函数将会向内存申请一块相应大小的空间,并且返回这个空间的指针。但这个指针初始时是一个void\类型的,所以需要cast一下,得到一个node*类型的指针p。如果申请失败则返回NULL。一般来说不会失败,可能在申请大地址空间(较大动态数组)的时候可能会失败。而new是C++用于申请的运算符,即node* p=new node;。但如果分配失败,则不会返回NULL而是启动C++异常处理。然后就回到了大一长谈的内存泄漏问题,内存泄漏是指借用了内存空间但是使用之后忘记释放,导致在程序结束之前始终占据内存空间,所以有些较大的程序很容易导致在运行的时候无内存继续分配,当然进程结束后应该还是问题不大。清空一个空间用free(p)或者delete p就行。一般做oj的时候问题不大,但是开发的时候还是应该把内存管理好一些。
链表分就实现上可分为动态链表和静态链表,静态链表在一些PAT题目中经常会用到,其思想就是开辟一个较大的内存空间,每一个节点都会有一个int型的next域,其地址由其索引决定。

创建链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
#include <stdlib.h>
struct node{
int data;
node* next;
};
node* create(int Array[],int n)
{
node *p,*pre,*head;
head=new node;head->next=NULL;
pre=head;
for(int i=0;i<n;i++)
//sizeof(Array)/sizeof(int)这么写是错误的
{
p=new node;
p->data=Array[i];
p->next=NULL;
pre->next=p;
pre=p;
}
return head;
}

查找链表中是否有给定的元素或者有多少个?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int search(node *head,int x)
{
int count=0;
node* p=head->next;
while(p!=NULL)
{
if(p->data==x)
{
counter++;
}
p=p->next;
}
return count;
}

插入元素:在链表指定位置插入一个节点

1
2
3
4
5
6
7
8
9
10
11
12
void insert(node* node,int pos,int x)
{
node* p=head;
for(int i=0;i<pos-1;i++)
{
p=p->next;
}
node* q=new node;
q->data=x;
q->next=p->next;
p->next=q;
}

删除链表上所有值为x的节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void deleteX(node *head,int x)
{
node *p=head->next;
node *pre=head;
while(p!=NULL)
{
if(p->data==x)
{
pre->next=p->next;
delete(p);
p=pre->next;
}else{
pre=p;
p=p->next;
}
}
}

链表反转

1
2
3
4
5
6
7
8
9
10
11
12
13
struct node* reverse(node* head)
{
node* cur=NULL,*pre=head->next;//pre为第一个节点
while(pre!=NULL)
{
node* t=pre->next;//t指向第二个点
pre->next=cur; //第一个点指向前一个,即NULL
cur=pre; //cur向后移动一格
pre=t; //pre向后移动一个
}
head->next=cur;
return head;
}

TEST

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int main() {
int Array[5]= {1,2,3,4,5};
int n=sizeof(Array)/sizeof(int);
node *L=create(Array,n);
node *head=L;
L=L->next;//从第一个节点开始有数据域
while(L!=NULL) {
printf("%d ",L->data);
L=L->next;
}
node* new_head=reverse(head);
node* pp=new_head->next;
while(pp!=NULL) {
printf("%d ",pp->data);
pp=pp->next;
}
return 0;
}