按值查找返回位置
//按值查找返回位置 int search_value(node_p H,int value) { if(H==NULL) {return;} if(empty_double(H)){return;} int i; node_p p=H->next; for(i=1;p!=NULL;i++,p=p->next) { if(p->data==value) { printf("值的位置是%d\n",i); return i; } printf("双向链表内没有该值\n"); } }按位置修改元素
//按位置修改元素 void update_pos(node_p H,int pos,int change_value) { if(H==NULL){return;} if(empty_double(H)){return;} if(pos<=0){return;} int i; node_p p=H; for(i=0;i<pos;i++,p=p->next) { if(p==NULL) { printf("插入位置不合理\n"); } } p-data=change_value; }
自己实现双向循环链表的代码
a.创建
b.创建结点
c.头插
d.尾插
e.按位置插入
f.头删、尾删、按位置删除
g.按位置查找返回- 功能函数文件
#include "cycle.h" //1、创建双向循环链表 node_p create_cycle() { node_p H = (node_p)malloc(sizeof(node)); if(H == NULL) return NULL; // 正确初始化循环链表 H->len = 0; H->next = H; // 头节点的next指向自身 H->pri = H; // 头节点的pri指向自身 return H; } //2、创建结点 node_p create_node(int data) { node_p new = (node_p)malloc(sizeof(node)); if(new == NULL) { printf("申请空间失败\n"); return NULL; } new->data = data; // 新节点的next和pri都先指向自身 new->next = new; new->pri = new; return new; } //3、判空 int empty_cycle(node_p H) { if(H == NULL) return -1; // 循环链表判空条件：头节点的next是否指向自身 return H->next == H ? 1 : 0; } //4、头插 void insert_head(node_p H, int value) { if(H == NULL) { printf("入参为空\n"); return; } node_p new = create_node(value); // 插入新节点到头部 new->next = H->next; new->pri = H; H->next->pri = new; H->next = new; H->len++; // 更新长度 } //5.尾插 void insert_tail(node_p H, int value) { if(H == NULL) return; node_p new = create_node(value); // 插入到尾部（即头节点的前面） new->next = H; new->pri = H->pri; H->pri->next = new; H->pri = new; H->len++; // 更新长度 } //6.输出 void show_cycle(node_p H) { if(H == NULL) { printf("入参为空\n"); return; } if(empty_cycle(H)) { printf("链表为空\n"); return; } // 遍历循环链表，从头节点的下一个节点开始，直到再次回到头节点 node_p p = H->next; printf("H->"); while(p != H) { printf("%d<->", p->data); p = p->next; } printf("H\n"); // 显示循环回到头节点 } //7.任意位置插入 void insert_pos(node_p H, int pos, int value) { if(H == NULL) return; if(pos <= 0) return; // 如果pos大于长度，插入到尾部 if(pos > H->len + 1) { insert_tail(H, value); return; } int i = 0; node_p p = H; // 找到pos-1位置的节点 for(; i < pos-1; i++, p = p->next); node_p new = create_node(value); // 插入新节点 new->next = p->next; new->pri = p; p->next->pri = new; p->next = new; H->len++; // 更新长度 } //8、头删 void dele_head(node_p H) { if(H == NULL || H->next == H) // 链表为空或只有头节点 return; node_p dele = H->next; // 调整指针，移除第一个节点 H->next = dele->next; dele->next->pri = H; free(dele); H->len--; } //9、尾删 void dele_tail(node_p H) { if(H == NULL || H->next == H) // 链表为空或只有头节点 return; node_p dele = H->pri; // 尾节点是头节点的前一个 // 调整指针，移除尾节点 H->pri = dele->pri; dele->pri->next = H; free(dele); H->len--; } //10、按位删除 void dele_pos(node_p H, int pos) { if(H == NULL || H->next == H) // 链表为空 return; if(pos <= 0 || pos > H->len) // 位置无效 return; int i = 0; node_p p = H->next; // 从第一个节点开始 // 找到要删除的节点 for(; i < pos-1; i++, p = p->next); // 调整指针，移除节点 p->pri->next = p->next; p->next->pri = p->pri; free(p); H->len--; } //11、按值查找返回位置 int search_value(node_p H, int value) { if(H == NULL || H->next == H) // 链表为空 return -1; int pos = 1; node_p p = H->next; // 从第一个节点开始 while(p != H) { // 遍历直到回到头节点 if(p->data == value) return pos; p = p->next; pos++; } return -1; // 未找到 } //12、按位置修改元素 void update_pos(node_p H, int pos, int change_value) { if(H == NULL || H->next == H) // 链表为空 return; if(pos <= 0 || pos > H->len) // 位置无效 return; int i = 0; node_p p = H->next; // 从第一个节点开始 // 找到要修改的节点 for(; i < pos-1; i++, p = p->next); p->data = change_value; }主函数文件
#include "cycle.h" int main() { node_p H = create_cycle(); // 修正函数名 if(H == NULL) { printf("创建链表失败\n"); return 1; } insert_head(H, 12); insert_head(H, 23); insert_head(H, 43); show_cycle(H); // 修正函数名 // 测试插入 insert_pos(H, 1, 25); // 在位置1插入25 show_cycle(H); // 测试删除 dele_tail(H); // 修正函数名 show_cycle(H); return 0; }头文件
#ifndef __CYCLE_H__ #define __CYCLE_H__ #include <stdio.h> #include <stdlib.h> typedef struct node { union { int len; int data; }; struct node *pri; //指向前驱结点的指针 struct node *next; //指向后继结点的指针 } node, *node_p; // 修改：正确定义指针类型 //1、创建双向循环链表 node_p create_cycle(); //2、创建结点 node_p create_node(int data); //3、判空 int empty_cycle(node_p H); //4、头插 void insert_head(node_p H, int value); //5、尾插 void insert_tail(node_p H, int value); //6、输出 void show_cycle(node_p H); //7、任意位置插入 void insert_pos(node_p H, int pos, int value); //8、头删 void dele_head(node_p H); //9、尾删 void dele_tail(node_p H); //10、按位置删除 void dele_pos(node_p H, int pos); //11、按值查找返回位置 int search_value(node_p H, int value); //12、按位置修改元素 void update_pos(node_p H, int pos, int change_value); #endifmakefile文件
EXE=link Objs=$(patsubst %.c,%.o,$(wildcard *.c)) CC=gcc CFlags=-c -o all:$(EXE) $(EXE):$(Objs) $(CC) $^ -o $@ %.o:%.c $(CC) $^ $(CFlags) $@ clean: rm *.o $(Objs)
C 语言中，链表和顺序表（数组）是两种常见的数据结构，它们各有优缺点，适用于不同场景。以下是两者的对比：
顺序表（数组）
优点：
随机访问高效：通过下标直接访问元素，时间复杂度为 O (1)。
内存连续：缓存命中率高，适合大量数据的批量处理。
实现简单：无需额外维护指针，代码复杂度低。
缺点：
插入 / 删除效率低：需要移动大量元素，时间复杂度为 O (n)。
固定容量：静态数组大小编译时确定，动态数组扩容需重新分配内存并复制数据。
内存碎片：动态扩容可能导致内存碎片，尤其在频繁增删时。
链表（单链表 / 双链表）
优点：
动态扩展：按需分配内存，适合元素数量不确定的场景。
插入 / 删除高效：只需修改指针，时间复杂度为 O (1)（若已知位置）。
内存利用率高：无需预先分配大块连续内存，避免碎片。
缺点：
随机访问慢：必须从头遍历，时间复杂度为 O (n)。
额外空间开销：每个节点需存储指针域，增加内存消耗。
缓存不友好：节点内存不连续，可能影响性能。
适用场景
顺序表：适用于需要频繁随机访问、元素数量固定或变化不大的场景（如矩阵运算、查找表）。
链表：适用于频繁插入删除、元素数量动态变化的场景（如消息队列、LRU 缓存）