C语言链表详解
前言
学习链表之前,先来看几个术语:
首节点:存放第一个有效数据的节点;
尾节点:存放最后一个有效数据的节点;
头节点:头节点的数据类型与首节点的数据类型相同,并且头节点是首节点前面的那个节点,并不存放有效数据;头节点的存在只是为了方便链表的操作。
头指针:指向头节点的指针;
尾指针:指向尾节点的指针。
成都创新互联公司科技有限公司专业互联网基础服务商,为您提供西部信息机房,高防物理服务器租用,成都IDC机房托管,成都主机托管等互联网服务。
链表的基本操作
1. 节点的构造
#include
#include
#include
#define LEN sizeof(struct stu)
struct stu
{
//数据域
char num[10];
char name[20];
float score;
//指针域
struct stu * next;
};
2. 建立链表
//建立链表
struct stu * create(){
//声明头指针,p1和p2两个指针
struct stu * head;
struct stu * p1, *p2;
//建立头结点
head = (struct stu *) malloc(LEN);
head->next = NULL; //头指针指向的头结点的指针域为空
p1 = head; //把头指针的指向赋给指针p1,即p1指向头结点
p2 = (struct stu *)malloc(LEN); //分配第一个节点,并让p2指向他
printf("输入节点信息:学号、姓名和成绩\n");
scanf("%s%s%f",p2->num, p2->name, &p2->score);
getchar();
//学号为字符串'0'作为结束输入的条件
while(strcmp(p2->num,"0") != 0){
/*
执行结束后
1)p2的next域为NULL.
2)第一个节点的next域指向第二个节点的数据域
3)p1指针指向第二个节点的数据域
*/
p2->next = p1->next;
p1->next = p2;
p1 = p2;
//重新分配第三个节点,并让p2指向他
p2 = (struct stu *)malloc(LEN);
printf("输入节点信息:学号、姓名和成绩\n");
scanf("%s%s%f",p2->num, p2->name, &p2->score);
getchar();
}
//执行结束后释放p2指针,并返回头指针
free(p2);
return head;
};
3. 输出链表
//输出链表
void print(struct stu * head){
struct stu * p; //声明一个p指针
printf("num name score\n");
p = head->next; //指针p指向第一个节点
//依次输出各个节点直到最后一个节点
while(p!=NULL){
printf("%-10s %-20s %-4.1f\n",p->num, p->name, p->score);
p=p->next;
}
}
4. 插入节点
//插入节点
void insert(struct stu * head, struct stu * p0){
struct stu *p1, *p2;
p1 = head->next; //p1指向第一个节点
p2 = head; //p2为待插入节点的前面一个节点
while((p1!=NULL) && (strcmp(p0->num, p1->num)==1)){ //当p0的学号大于p1的学号并且没有到最后一个时不进行插入
p2=p1;
p1=p1->next;
}
//下面进行插入操作
p0->next = p2->next;
p2->next = p0;
}
5. 删除节点
int delete(struct stu *head, char num[]){
//声明两个结构体类型的指针,p1和p2
struct stu *p1, *p2;
p1 = head->next; //p1指向第一个节点
p2 = head; //p2指向p1的前驱结点
//查找要删除的节点的位置
while(p1!=NULL && strcmp(num, p1->num)!=0){
p2=p1;
p1=p1->next;
}
//要删除的节点不存在
if(!p1){
return 0;
}
//执行删除操作,并释放p1指针
p2->next = p1->next;
free(p1);
return 1;
}
6. 主函数
//主函数
int main()
{
struct stu * h, *p0;
char num[10];
printf("建立链表\n");
h = create();
p0 = (struct stu *)malloc(LEN);
//测试插入节点的操作
printf("输入待插入的节点信息:学号、姓名和成绩\n");
scanf("%s%s%f",p0->num, p0->name, &p0->score);
getchar();
if(strcmp(p0->num,"0") != 0){
insert(h, p0);
}
//测试删除节点的操作
printf("输入待删除节点的学号\n");
scanf("%s",num);
if(strcmp(num,"0") != 0){
delete(h, num);
}
printf("输出链表\n");
print(h);
return 0;
}
思路总结
1. 创建节点:头节点的指针域初始为空,将新创立的节点依次挂到上面。p1始终指向最后一个节点,p2始终为新建立的节点。
2. 插入节点:先查找该节点要插入的位置,在插入节点。插入的语句为:
p0->next = p2->next;
3. 删除节点:查找要删除的节点的位置,执行插入操作,语句:
p2->next = p1->next;
4. 输出链表:知道头指针,就能知道整个链表
分享名称:C语言链表详解
转载来源:http://pwwzsj.com/article/ihddpd.html