目录链式表的分类方式按节点连接方式分类按存储结构分类按功能扩展分类带头双向循环动态链表模拟实现链式表的分类方式链式表链表根据不同的结构和特性可以分为以下几类按节点连接方式分类单向链表每个节点包含数据和指向下一个节点的指针只能单向遍历。优点结构简单内存占用较小。缺点无法反向遍历删除节点需从头查找前驱节点。双向链表每个节点包含数据、指向下一个节点的指针和指向前一个节点的指针。优点支持双向遍历删除和插入操作更高效。缺点每个节点多占用一个指针空间内存开销较大。循环链表尾节点指向头节点形成闭环。可分为单向循环链表和双向循环链表。优点适合环形数据处理如轮询调度。缺点需注意循环终止条件避免无限循环。按存储结构分类静态链表使用数组模拟链表通过数组下标代替指针。优点无需动态内存分配适合嵌入式系统等受限环境。缺点容量固定灵活性差。动态链表节点通过动态内存分配如malloc创建内存可动态扩展。优点灵活性强内存利用率高。缺点需手动管理内存易产生内存泄漏。按功能扩展分类带头节点的链表在链表头部添加一个不存储数据的节点头节点简化插入/删除操作。优点统一操作逻辑避免对头节点的特殊处理。不带头节点的链表直接以第一个数据节点作为头节点。优点节省一个节点的空间。缺点需单独处理头节点操作。而今天我要模拟实现的是带头双向循环动态链表。带头双向循环动态链表模拟实现链表的结构结构体typedef int DCLDataType; typedef struct DCListNode { DCLDataType data; // 存储数据元素的值 struct DCListNode* prev; // 存放前驱结点的指针 struct DCListNode* next; // 存放后继结点的指针 }DCListNode;链表的初始化// 链表初始化 DCListNode* DCListInit() { DCListNode* head (DCListNode*)malloc(sizeof(DCListNode)); if (head NULL) { perror(malloc); exit(1); } head-next head-prev head; return head; }注意点在该链式表内因为要实现的循环链表所以需要在初始化的时候需要进行一个头尾相连向头指针。链式表的销毁// 销毁链表 void DCListDestroy(DCListNode* L) { if (L NULL) { return; } DCListNode* dest ,*head L; L L-next; while (L ! head) { dest L; L L-next; free(dest); dest NULL; } free(head); head NULL; return; }因为是一个循环链表需要进行特殊的处理先从链式表头指针往后的第一个节点进行销毁遇到头指针停止循环销毁对头指针单独销毁。获取链式表的为序i节点// 获取链表的位序i的结点 DCListNode* DCListGetElem(DCListNode* L, int i) { if (i 0 || L NULL)//错误操作指针为空 { return NULL; } DCListNode* node L-next; int I 1; for (I 1; I i L ! node; I) { node node-next; } if (L node)//超出链式表的最大访问遇到 return NULL; return node; }1.判断头指针是否为空或者i小于等于02.声明节点跳过头指针开始查找。3.超出最大链式的极限返回NULL 没有就返回node 节点在pos位置后插入值为x的结点 和 头插 尾插void DCListInsert(DCListNode* pos, DCLDataType x) { DCListNode* news (DCListNode*)malloc(sizeof(DCListNode)); if (news NULL) { perror(malloc); exit(1); } news-next pos-next; news-prev pos; pos-next-prev news; pos-next news; news-data x; return; } // 头插 void DCListPushFront(DCListNode* L, DCLDataType x) { assert(L ! NULL); DCListInsert(L, x); return; } // 尾插 void DCListPushBack(DCListNode* L, DCLDataType x) { assert(L); DCListInsert(L-prev, x); return; }节点插入都要先申请一个节点这个节点为了方便解释设为C点要插入某个节点前面我们设A点下一个节点为B节点的各个节点一定要遵循A-B的节点最后改不然会导致找不到B点或者可以用其他方式来实现总之要保证B点有能够存取的地址的方式。我的步骤就是先把申请来的新地址先把新节点C的前后指针存入B和A把B的后指针存入C再把A的前指针存入C再把C的data存入x。头插和尾插都只需要把对应的地址传参即可如果要实现对应位置插入就用刚才的DCListGetElem函数利用起来就可以实现对应位置插入。//对应位置插入 void DCListPushNode(DCListNode* L, DCLDataType x,int i) { DCListNode* node DCListGetElem(L, i); assert(node); DCListInsert(node, x); return; }删除pos位置的结点头删和尾删// 删除pos位置的结点 void DCListDelete(DCListNode* pos) { assert(pos ! NULL); if (pos pos-next) { return; } pos-next-prev pos-prev; pos-prev-next pos-next; free(pos); pos NULL; return; } // 头删 void DCListPopFront(DCListNode* L) { assert(L ! NULL); DCListDelete(L-next); return; } // 尾删 void DCListPopBack(DCListNode* L) { assert(L ! NULL); DCListDelete(L-prev); return; }对应位置删除只关注前后指针前后指针从新链接就可以。当前位置的前指针节点的后指针 改成 当前位置的指针的后一个节点当前位置的后指针节点的前指针 改成 当前位置的指针的前一个节点这样及保证前后指针完美链接也可以不用声明多的变量只用pos 进行空间释放。注意点头删时把头指针的往后一个节点进行释放而不是头指针释放所以传参传L-next尾删就是把头指针的L-prev 进行释放。原则就是保证删除的不是头指针只有销毁才需要把头指针进行销毁。打印输出// 打印链表中的元素 void DCListPrint(DCListNode* L) { assert(L!NULL); DCListNode* node L-next; while (L!node) { printf(%d - ,node-data); node node-next; } printf(\n); return; }模拟实现void List_test() { DCListNode* head DCListInit(); DCListPushBack(head, 1); DCListPushBack(head, 2); DCListPushBack(head, 3); DCListPushBack(head, 4); DCListPushBack(head, 5); DCListPushBack(head, 6); DCListPrint(head); DCListPushFront(head, 2); DCListPushFront(head, 3); DCListPushFront(head, 4); DCListPushFront(head, 5); DCListPushFront(head, 6); DCListPrint(head); DCListPopFront(head); DCListPrint(head); DCListPopFront(head); DCListPrint(head); DCListPopFront(head); DCListPrint(head); DCListDestroy(head); return; } int main() { List_test(); return 0; }感谢观看悠仁さん