结构体与链表
结构体与链表
在 C 语言中，结构体是一种用户自定义的数据类型，它可以把不同类型的数据组合在一起，形成一个整体。
struct Node {
int data;
struct Node *next;
};
这段代码定义了一个叫 Node 的结构体，它有两个成员：
- int data：用来存储实际的数据，比如整数。
- struct Node *next：是一个指针，指向下一个 Node 类型的结构体。
结构体的内存布局
当我们定义了一个 struct Node，编译器会为它分配一块连续的内存空间，大小等于所有成员占用空间之和。
假设 int 占 4 字节，指针也占 8 字节（64位系统），那么每个 Node 节点总共占 12 字节（或更多，因对齐规则可能增加）。
如何创建链表节点
静态创建
struct Node node1;
struct Node node2;
struct Node node3;
struct Node node4;
node1.data = 1;
node2.data = 2;
node3.data = 3;
node4.data = 4;
node1.next = &node2;
node2.next = &node3;
node3.next = &node4;
- 这里是直接在栈上声明变量，四个 Node 对象都存放在程序的栈区。
- 每个节点有名字（如 node1），可以通过名字访问。
- 使用 &node2 获取 node2 的地址，赋值给 node1.next，就建立了连接。
动态创建
struct Node *node1 = (struct Node *)malloc(sizeof(struct Node));
struct Node *node2 = (struct Node *)malloc(sizeof(struct Node));
// … 其他节点 - 使用 malloc() 在堆（heap） 上申请内存。
- 返回的是一个指向该内存的指针，所以我们必须用指针接收。
- 每个节点都是独立申请的，可以随时增删。
起别名
typedef struct Node {
int data;
struct Node *next;
} Node, LinkNode, *sNode;
typedef struct Node {…} Node;
给 struct Node 起了个别名 Node，以后可以直接写 Node 而不用写 struct Node。比如：Node node1; 就等价于 struct Node node1;
LinkNode 是另一个别名可以当作 Node 的别名使用，用于命名一致性。
*sNode 是指针类型的别名，sNode 表示“指向 Node 结构体的指针”
所以 sNode node4; 相当于 struct Node *node4;
链接链表
node1->data = 1;
node2->data = 2;
node3->data = 3;
node4->data = 4;
node1->next = node2;
node2->next = node3;
node3->next = node4;
node1 → node2 → node3 → node4 → NULL
内存地址: 0x1000 0x2000 0x3000 0x4000
±---------±---------±---------±---------+
| data=1 | next=0x2000| data=2 | next=0x3000| …
±---------±---------±---------±---------+
遍历读取链表
voidprintList(Node*head){for(Node*cur=head;cur!=NULL;cur=cur->next){printf("%d",cur->data);if(cur->next!=NULL){printf("->");}}printf("\n");}插入/删除链表
插入链表：
intinsertAt(Node**head,intindex,intvalue){intlen=getListLen(*head);if(index<0||index>len){return-1;// 插入失败}Node*newNode=(Node*)malloc(sizeof(Node));if(!newNode){return-1;}newNode->data=value;if(index==0){newNode->next=*head;*head=newNode;}else{Node*prev=*head;for(inti=0;i<index-1;i++){prev=prev->next;}newNode->next=prev->next;prev->next=newNode;}return0;}这里传参需要二维指针是因为需要修改指针指向，若一维指针只是拷贝传递。
删除链表:
// 删除第一个值为 data 的节点voiddelList(Node**head,intdata){if(*head==NULL)return;// 如果要删除的是头节点if((*head)->data==data){Node*temp=*head;*head=(*head)->next;free(temp);return;}Node*cur=*head;while(cur->next!=NULL){if(cur->next->data==data){Node*temp=cur->next;cur->next=cur->next->next;free(temp);return;// 只删第一个匹配项}cur=cur->next;}}双向链表
#include<stdio.h>#include<stdlib.h>typedefstructNode{intdata;structNode*next;structNode*prev;}Node;// 获取链表长度intgetListLen(Node*head){inti=0;for(Node*cur=head;cur!=NULL;cur=cur->next){i++;}returni;}intinsertAt(Node**head,intindex,intvalue){intlen=getListLen(*head);if(index<0||index>len){return-1;}Node*newNode=(Node*)malloc(sizeof(Node));if(!newNode){return-1;}newNode->data=value;newNode->next=NULL;newNode->prev=NULL;if(index==0){newNode->next=*head;if(*head!=NULL){(*head)->prev=newNode;}*head=newNode;}else{Node*cur=*head;for(inti=0;i<index;i++){cur=cur->next;}newNode->next=cur;newNode->prev=cur->prev;cur->prev->next=newNode;cur->prev=newNode;}return0;}// 输出链表voidprintList(Node*head){for(Node*cur=head;cur!=NULL;cur=cur->next){printf("%d",cur->data);if(cur->next!=NULL){printf("->");}}printf("\n");}// 删除第一个值为 data 的节点voiddelList(Node*head,intdata){if(head==NULL)return;Node*cur=head;while(cur!=NULL){if(cur->data==data){if(cur->prev!=NULL){cur->prev->next=cur->next;}else{head=cur->next;// 删除头节点}if(cur->next!=NULL){cur->next->prev=cur->prev;}free(cur);return;}cur=cur->next;}}intmain(){constintN=4;intvalues[N]={10,20,30,40};Node*head=NULL;Node*tail=NULL;// 使用头插法for(inti=0;i<N;i++){Node*newNode=(Node*)malloc(sizeof(Node));if(!newNode){return-1;}newNode->data=values[i];newNode->next=NULL;newNode->prev=tail;if(head==NULL){head=tail=newNode;}else{;tail=newNode;}}intlen=getListLen(head);printf("链表长度: %d\n",len);// 插入printf("index=2 ，99");if(insertAt(&head,2,99)==0){printf("插入后: ");printList(head);}// 删除printf("请输入要删除的数据: ");intdata;scanf("%d",&data);delList(head,data);printf("删除后: ");printList(head);return0;}