炫意html5
最早CSS3和HTML5移动技术网站之一

C语言指针 -C语言单链表的基本操作(附带源码)

对于单向链表常见的操作有链表结点数据的查找、插入和删除。

单向链表的插入和删除操作
图 1:单向链表的插入和删除操作

1) 单链表节点的查找

在单向链表中,查找目标数据,只需从 head 指向的表头结点出发,沿着链表顺序遍历整个链表,并一一比较各个结点数值域中的数据即可。例如,从 head 为头指针的单向链表中查找数值域中成员 data 为 x 的结点,可以编写成以下函数 find( ):

struct node{
int data;
struct node *next;
} *head;
void find(struct node *head, int x){
int i=1;
struct node *this;    //定义一个当前结点指针
this = head;    //当前结点从头结点开始查找
while((this != NULL) && !(this->data == x)){    //遍历链表
this = this->next;    //不匹配,当前结点指针指向下一个结点
i++;
}
if(this==NULL)
printf("没有找到!\n");
else
printf("%d在链表的第%d个结点中!\n",x,i);
}

2) 单链表节点的插入

在数组的某个元素后面插入一个新的元素时,需要将该元素后面的所有元素都向后移动位置。而在链表的结点 p 后面插入一个新的结点,不必像数组那样移动后面的结点,只要将 p 的后继指针指向新的结点,并将新结点的后继指针指向 p 原来的后继结点即可(见图 1a) )。例如,在单向链表的 p 结点后面插入一个数值域成员 data 的值为 x 的新结点,可以编写成以下函数 ins( ):

void ins(struct node *p,int x){
struct node *new;    //定义新结点
new = malloc(sizeof(struct node));    //为新结点申请内存空间
new->data = x;    //给新结点数值域成员赋值
new->next = p->next;    //新结点后继指针指向 p 的后继结点
p->next = new;    //p 的后继结点指向新结点
}

3) 单链表节点的删除

在单向链表中,要删除指针 p 指向的结点,只要将其前面一个结点(前驱结点)的后继指针指向 p 后面的结点(后继结点),并释放 p 所占用的内存即可(见图 1b) )。例如,从 head 为头指针的单向链表中删除 p 指向结点,可以编写成以下函数 del( ):

void del(struct node *p){
struct node *this;    //定义一个当前结点指针
this = head;    //当前结点从头结点开始查找
if (this == p)    //p 为头结点时
head = this->next;
else{
while(this->next !=p)    // 遍历链表,查找 p 的前驱结点
this = this->next;    //不匹配,当前结点指针指向下一个结点
this->next = p->next;    //当前结点 this 的后继指针指向 p 的后继结点
}
free(p);    //释放结点 p 占用的内存空间
}

完整示例+代码

1) 单链表节点的查找和插入

读入整数 n,建立一个单向链表,按顺序存储自然数 1 至 n,然后再在所有偶数后面插入 2。

C语言代码清单 1:在链表中查找、插入结点

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
struct node{
int data;
struct node *next;
} *head, *q, *p;
void ins(struct node *p, int x)
{
struct node *new;
new = malloc(sizeof(struct node));
new -> data = x;
new -> next = p -> next;
p -> next = new;
}
void print( )
{
for(q = head; q != NULL; q = q -> next)
printf("%d ",q -> data);
printf("\n");
}
int main( )
{
int i,n;
printf("请输入一个正整数n:");
scanf("%d",&n);
head = malloc(sizeof(struct node));   //创建初始链表
head -> data = 1;
head -> next = NULL;
q = head;
for(i = 2; i <= n; i++){  //循环插入2~n
ins(q,i);
q = q -> next;
}
print();
for(q = head; q != NULL; q = q -> next){  //查找偶数并在后面插入2
if((q -> data) % 2 == 0){
ins(q,2);
q = q->next;
}
}
print();
system("pause");
return 0;
}

运行结果为:

请输入一个正整数n:8
1 2 3 4 5 6 7 8
1 2 2 3 4 2 5 6 2 7 8 2

2) 单链表节点的删除

读入整数 n,建立一个单向链表,按顺序存储自然数 1 至 n,然后删除其中所有的奇数。

代码清单 2:在链表中删除结点

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
struct node{
int data;
struct node *next;
} *head, *q, *p;
void ins(struct node *p, int x)
{
struct node *new;
new = malloc(sizeof(struct node));
new -> data = x;
new -> next = p -> next;
p -> next = new;
}
void print( )
{
for(q = head; q != NULL; q = q -> next)
printf("%d ",q -> data);
printf("\n");
}
int main( )
{
int i,n;
printf("请输入一个正整数n:");
scanf("%d",&n);
head = malloc(sizeof(struct node));   //创建初始链表
head -> data = 1;
head -> next = NULL;
q = head;
for(i = 2; i <= n; i++){  //循环插入2~n
ins(q,i);
q = q -> next;
}
print();
q = head;
while(q -> next != NULL){  //查找并删除所有奇数
if((q -> data) % 2 == 1) {
q = head -> next;
free(head);
head = q;
}
else{
p = q -> next;
if((p -> data) % 2 == 1){
q -> next = p -> next;
free(p);
}
else
q = q -> next;
}
}
print();
system("pause");
return 0;
}

运行结果为:

请输入一个正整数n:8
1 2 3 4 5 6 7 8
2 4 6 8

炫意HTML5 » C语言指针 -C语言单链表的基本操作(附带源码)

Java基础教程Android基础教程