网站有那些风格,韩城网站建设,徐州工作招聘信息网,官方小程序单链表的局限#xff1a; 单链表的缺点#xff1a;逆序访问单链表中的元素耗时大。#xff08;时间复杂度#xff1a;O#xff09;
双向链表的定义 第0个节点【a1】的pre指针为NULL#xff0c;要注意
插入操作#xff1a; 删除操作#xff1a; 初步实现双链表 代码 单链表的缺点逆序访问单链表中的元素耗时大。时间复杂度O²
双向链表的定义 第0个节点【a1】的pre指针为NULL要注意
插入操作 删除操作 初步实现双链表 代码
插入代码中要注意 注意第0个元素的pre指针为NULL
插入的是空双链表中的 第一个元素,示意图 插入的为最后一个元素 main.c
//双链表
#include DLinkList.h
struct Value
{DLinkListNode header;int v;
};
int main() {int i;DLinkList* list DLinkList_Create();struct Value v1;struct Value v2;struct Value v3;struct Value v4;struct Value v5;v1.v 1;v2.v 2;v3.v 3;v4.v 4;v5.v 5;DLinkList_Insert(list, v1, DLinkList_Length(list));DLinkList_Insert(list, v2, DLinkList_Length(list));DLinkList_Insert(list, v3, DLinkList_Length(list));DLinkList_Insert(list, v4, DLinkList_Length(list));DLinkList_Insert(list, v5, DLinkList_Length(list));for ( i 0; i DLinkList_Length(list); i){struct Value* pv (struct Value*)DLinkList_Get(list, i);printf(%d\n, pv-v);}printf(\n);DLinkList_Delete(list, DLinkList_Length(list) - 1);DLinkList_Delete(list, 0);for (i 0; i DLinkList_Length(list); i){struct Value* pv (struct Value*)DLinkList_Get(list, i);printf(%d\n, pv-v);}DLinkList_Destory(list);
}DLinkList.h
#pragma once
#pragma once
#pragma once
#include stdio.htypedef void DLinkList;
//定义包含指针next的结构体
typedef struct _tag_DLinkListNode DLinkListNode;
typedef struct _tag_DLinkListNode
{DLinkListNode* next;DLinkListNode* pre;
};/*
该方法用于创建并且返回一个空的线性表
*/
DLinkList* DLinkList_Create();/*
该方法用于销毁一个线性表DLinkList
*/
void DLinkList_Destory(DLinkList* list);/*
该方法用于将一个线性表DLinkList中的所有元素清空
使得线性表回到创建时的初始状态
*/
void DLinkList_Clear(DLinkList* list);/*
该方法用于返回一个线性表DLinkList中的所有元素个数
*/
int DLinkList_Length(DLinkList* list);int DLinkList_Capacity(DLinkList* list);/*
该方法用于向一个线性表DLinkList的pos位置处插入新元素node
返回值为1表示插入成功0表示插入失败
*/
int DLinkList_Insert(DLinkList* list, DLinkListNode* node, int pos);/*
该方法用于获取一个线性表DLinkList的pos位置处的元素
返回值为pos位置处的元素NULL表示获取失败
*/
DLinkListNode* DLinkList_Get(DLinkList* list, int pos);/*
该方法用于删除一个线性表DLinkList的pos位置处的元素
返回值为被删除的元素NULL表示删除失败
*/
DLinkListNode* DLinkList_Delete(DLinkList* list, int pos);
DLinkList.c
#include DLinkList.htypedef struct _tag_DLinkList
{DLinkListNode header;//头指针int length;//单链表的长度
}TDLinkList; //类型既代表头结点又代表整个单链表DLinkList* DLinkList_Create() {TDLinkList* ret (TDLinkList*)malloc(sizeof(TDLinkList));if (ret) {ret-length 0;ret-header.next NULL;ret-header.pre NULL;}
}void DLinkList_Destory(DLinkList* list) {free(list);
}void DLinkList_Clear(DLinkList* list) {((TDLinkList*)list)-length 0;((TDLinkList*)list)-header.next NULL;((TDLinkList*)list)-header.pre NULL;}int DLinkList_Length(DLinkList* list) {return ((TDLinkList*)list)-length;
}int DLinkList_Insert(DLinkList* list, DLinkListNode* node, int pos) {TDLinkList* tll (TDLinkList*)list;int i 0;int ret -1;ret (tll ! NULL) (pos 0) (node ! NULL);if (ret) {DLinkListNode* current (DLinkListNode*)tll;DLinkListNode* next NULL;//移动current指针到pos位置for (i 0; (i pos) (current-next ! NULL); i){current current-next;}next current-next; ////关键current-next node;//插入的步骤node-next next;if (next) {next-pre node;}node-pre current;//个人认为这个判定条件不对如果链表原来长度为5现在要插入第0个位置【即链表第一个节点】此if的代码不会被执行//那么第一个节点的pre指针就不能被赋值为NULL导致问题if (tll-length 0) {node-pre NULL; }tll-length;}return ret;
}DLinkListNode* DLinkList_Get(DLinkList* list, int pos) {TDLinkList* tll (TDLinkList*)list;DLinkListNode* ret NULL;int i 0;if ((tll ! NULL) (pos 0) pos tll-length) {DLinkListNode* current (DLinkListNode*)tll;for (i 0; i pos; i){current current-next;}ret current-next;}return ret;
}DLinkListNode* DLinkList_Delete(DLinkList* list, int pos) {TDLinkList* tll (TDLinkList*)list;DLinkListNode* ret NULL;int i 0;if ((tll ! NULL) (pos 0) pos tll-length) {DLinkListNode* current (DLinkListNode*)tll;DLinkListNode* next NULL;for (i 0; i pos; i){current current-next;}ret current-next;next ret-next; current-next next;//删除的步骤if (next) {next-pre current;if (current (DLinkListNode*)tll) { //如果删除的是第一个元素next-pre NULL;}}tll-length--;}return ret;
} 最终的代码
添加“游标”操作
