前言
学习链表之前, 先来看几个术语:首节点: 存放第一个有效数据的节点;尾节点: 存放最后一个有效数据的节点;头节点: 头节点的数据类型与首节点的数据类型相同, 并且头节点是首节点前面的那个节点, 并不存放有效数据; 头节点的存在只是为了方便链表的操作.头指针: 指向头节点的指针;尾指针: 指向尾节点的指针.
链表的基本操作
1. 节点的构造
- #include <stdio.h>
- #include <stdlib.h>
- #include <malloc.h>
- #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. 输出链表: 知道头指针, 就能知道整个链表
来源: http://www.bubuko.com/infodetail-2746356.html