数据结构day02（链表）

【1】链表 Link list

链表又称单链表/链式存储结构，用于存储逻辑关系为“一对一”的数据

和顺序表不同，使用链表存储数据，不强制要求在内存中集中存储，各个元素可以分散存储在内存中。

所以在链表中，每个数据元素可以配有一个指针用于找到下一个元素即节点，这意味着，链表上的每个“元素”都如下图

 

 链表的特性

逻辑结构：线性结构

存储结构：链式存储

特点：内存不连续，需要通过指针链接，大小不固定，解决顺序表插入删除麻烦的问题

操作：增删查改

struct node
{
int data;                      //数据域，用于存储数据
struct node * next;            //指针域，用于存储下一个节点的地址
};

单项链表

有头链表：存在一个头结点，头节点的数据域无效，指针域有效

无头链表：每一个节点的数据域和指针域都有效

 遍历无头单向链表

#include <stdio.h>
#include <stdlib.h>
typedef char datatype; // 重定义字符类型
typedef struct node
{datatype data;     // 数据用来存数据struct node *next; // 指针域用来存下一个节点的地址
} Node_t, *Node_p;     // 重定义结构体数据类型,和结构体指针类型/*遍历无头单项链表*/int main(int argc, char const *argv[]){//定义4个节点并赋值Node_t A = {'a',NULL};Node_t B = {'b',NULL};Node_t C = {'c',NULL};Node_t D = {'d',NULL};//连接4个节点A.next = &B;B.next = &C;C.next = &D;//定义一个头指针指向第一个节点Node_p p = &A;//通过指针遍历无头单项链表while(p != NULL){printf("%c ",p->data);//打印每个节点数据域中的值p = p->next;//让p指向下一个节点}printf("\n");return 0;}

#include <stdio.h>
#include <stdlib.h>
typedef char datatype; // 重定义字符类型
typedef struct node
{datatype data;     // 数据用来存数据struct node *next; // 指针域用来存下一个节点的地址
} Node_t, *Node_p;     // 重定义结构体数据类型,和结构体指针类型
/*遍历有头单项链表*/int main(int argc, char const *argv[]){// 定义4个节点并附值Node_t A = {'a', NULL};Node_t B = {'b', NULL};Node_t C = {'c', NULL};Node_t D = {'d', NULL};// 连接4个节点A.next = &B;B.next = &C;C.next = &D;// 定义头节点,数据域无效,指针域有效Node_t H = {'\0', &A};// 定义一个头指针,指向头节点Node_p p = &H;#if 0 //条件编译p = p->next; // 先跨越头节点,指向第一个数据域有效的节点Awhile (p != NULL) //当前指针不是空{printf("%c ", p->data);//打印数据域内容p = p->next;//指向下一个节点}printf("\n");#elsewhile (p->next != NULL)//当前指针的指针域内数据是否为空{p = p->next;printf("%c ",p->data);}printf("\n");#endifreturn 0;}

 链表尾插法

#include <stdio.h>
#include <stdlib.h>
typedef char datatype; // 重定义字符类型
typedef struct node
{datatype data;     // 数据用来存数据struct node *next; // 指针域用来存下一个节点的地址
} Node_t, *Node_p;     // 重定义结构体数据类型,和结构体指针类型
/*链表尾插法*/int main(int argc, char const *argv[]){Node_p p_new = NULL;  // 先定义一个结构体指针,置空待用Node_p p_tail = NULL; // 先定义一个结构体指针,置空待用int score = -1;            // 定义一个变量存放成绩// 创建一个头节点,用头指针p指向头节点Node_p H = (Node_p)malloc(sizeof(Node_t));//malloc开辟堆区空间if (NULL == H)//判断堆区空间是否开辟成功{printf("malloc lost");}H->next = NULL;//头节点指针域置空p_tail = H;//让尾指针指向头节点//循环输入学生成绩直到-1结束,创建新节点存放学生成绩,尾插的链表中while(1)//循环输入成绩{scanf("%d",&score);if(score == -1)//结束条件{break;}p_new = (Node_p)malloc(sizeof(Node_t));//创建新节点,用来存放学生成绩if(NULL == p_new)//判断堆区空间是否开辟成功{printf("malloc error");}//初始化新节点,把成绩赋值到数据域,指针域置空p_new->data = score;p_new->next = NULL;p_tail->next = p_new;//将新节点连接到当前尾节点,作为新的尾节点,就是把新节点的地址存放到当前尾节点的指针域中p_tail = p_new;//将当前尾节点移动到新节点上,是新节点成为尾节点,尾指针永远指向最后一个节点}//遍历链表while(H->next != NULL){H = H->next;printf("%d ",H->data);}printf("\n");return 0;}

 有头单向链表的函数操作

#include <stdio.h>
#include <stdlib.h>
typedef char datatype; // 重定义字符类型
typedef struct node
{datatype data;     // 数据用来存数据struct node *next; // 指针域用来存下一个节点的地址
} Node_t, *Node_p;     // 重定义结构体数据类型,和结构体指针类型/*有头单向链表的函数操作*/
/*创建一个空的单向链表*/
Node_p Create()
{Node_p p = (Node_p)malloc(sizeof(Node_t)); // 开辟一个节点大小的堆区空间if (NULL == p)                             // 开辟失败{printf("malloc lost");return NULL;}p->next = NULL; // 初始化头节点指针域return p;       // 开辟成功,返回
}/*计算链表的长度*/
int length(Node_p p)
{int len = 0;            // 定义一个变量来表示长度,并赋初始值为0while (p->next != NULL) // 当指针域不等于NULL就说明没到最后一个节点{p = p->next; // 指针向下一个节点移动len++;       // 长度加加}return len; // 返回长度值
}/*向项链表中插入数据*/
void Insert(Node_p p, int post, int data)
// p 保存链表的头指针   post 要插入的位置   data  要插入的数据
{// 容错判断if (post < 0 || post > length(p)) // 插入位置小于0或大于链表长度{printf("post error");}Node_p p_new = NULL;           // 创建一个指针,置空备用,用来存放要插入的新数据for (int i = 0; i < post; i++) // for循环遍历到要查如位置前的那该个节点p = p->next;p_new = (Node_p)malloc(sizeof(Node_t)); // 开辟一个节点大小堆区空间存放新数据if (NULL == p_new){printf("malloc lost");}p_new->data = data; // 在数据域存放要查入的数据p_new->next = NULL; // 初始化为NULL;// 链接新节点时,要先连后面,再连前面(否则,先连前面后面的地址就找不到了)p_new->next = p->next; // 让新节点链接到要插入的位置节点上p->next = p_new;       // 让要插入位置前的那个节点连接到新的节点上
}/*修改链表的内容*/
void Modify(Node_p p, int post, int data)
// p 保存链表的头指针  post  要修改的数据位置  data   要修改成的数据
{// 容错判断if (post < 0 || post > length(p)){printf("error\n");}for (int i = 0; i < post; i++) // for循环遍历到要插入位置前的那该个节点p = p->next;Node_p mod = p->next; // 定义一个指针指向要插入位置的节点mod->data = data;     // 修改要修改的值
}/*删除链表的内容*/
void Delete(Node_p p, int post)
// p 保存链表的头指针  post  要删除的数据位置
{// 容错判断if (post < 0 || post > length(p)){printf("delete error\n");}for (int i = 0; i < post; i++)p = p->next;Node_p p_del; // 定义一个指针指向要删除的节点p_del = p->next;p->next = p_del->next; // 让被删除的节点前的那个节点链接到被删除的那个节点后的节点free(p_del);           // 释放被删除的那个节点p_del = NULL;          // 将指向被删除的那个节点的指针置空
}/*查找链表中的内容*/
int Serarch(Node_p p, int post)
// p 保存链表的头指针  post  要查询的数据位置
{// 容错判断if (post < 0 || post > length(p)){printf("error\n");return -1;}for (int i = 0; i < post; i++)p = p->next;Node_p ser = p->next; // 定义一个指针指向要查询的节点return ser->data;     // 返回查询的节点数据域中的内容
}
/*遍历链表*/
void show(Node_p p)
// p 保存链表的头指针
{while (p->next != NULL){p = p->next;printf("%d ", p->data);  }printf("\n");
}int main(int argc, char const *argv[])
{Node_p H = Create();for (int i = 0; i < 5; i++) // 循环调用插入函数Insert(H, i, i);printf("插入后:\n");show(H);// Insert(H, -1, 6);Delete(H, 4);printf("删除后:\n");show(H);Modify(H, 1, 100);printf("修改后:\n");show(H);int data = Serarch(H, 1);printf("查询的数据:\n");printf("%d\n", data);return 0;
}