网站底部悬浮广告代码,怎么做营销推广方案,家具家居网站建设,ace网站建设……接上文 6. 双向链表 6.1 特性 逻辑结构#xff1a;线性结构 存储结构#xff1a;链式结构 操作#xff1a;增删改查 建立双向链表结构体#xff1a; //双向链表的节点定义 typedef int datatype;typedef struct node_t{datatype data;//数据域 struct node_t *next;//………接上文 6. 双向链表 6.1 特性 逻辑结构线性结构 存储结构链式结构 操作增删改查 建立双向链表结构体 //双向链表的节点定义 typedef int datatype;typedef struct node_t{datatype data;//数据域 struct node_t *next;//指向下一个节点的指针 next 先前的struct node_t *prior;//指向前一个节点的指针 prior 下一个}link_node_t,*link_node_p; //将双向链表的头指针和尾指针封装到一个结构体里 //思想上有点像学的链式队列typedef struct doublelinklist{link_node_p head; //指向双向链表的头指针link_node_p tail; //指向双向链表的尾指针int len; //用来保存当前双向链表的长度}double_list_t,*double_list_p;6.2 双向链表相关操作 需要注意的是与单链表不同双链表创建过程中每创建一个新节点都要与其前驱节点建立两次联系分别是 (1) 将新节点的 prior 指针指向直接前驱节点。 (2) 将直接前驱节点的 next 指针指向新节点。 1) 创建空的双向链表 //1.创建一个空的双向链表
double_list_p createEmptyDoubleLinkList()
{// 1. 申请空间存放头尾指针结构体double_list_p p (double_list_p)malloc(sizeof(double_list_t));if(NULL p){perror(createEmptyDoubleLinkList);return NULL;}p-len 0;//2.初始化头尾指针分别指向开辟头节点因为当前链表为空p-head p-tail (link_node_p)malloc(sizeof(link_node_t));if(p-head NULL){perror(p-head malloc failed!);return NULL;} p-head-next NULL;p-head-prior NULL;return p;
}2) 指定位置插入 // 2.向双向链表的指定位置插入数据 post位置 data数据
int insertIntoDoubleLinkList(double_list_p p, int post, datatype data)
{link_node_p temp NULL; // 用来临时保存head或者tail的位置if (post 0 || post p-len){perror(insertIntoDoubleLinkList err);return -1;} link_node_p pnew (link_node_p)malloc(sizeof(link_node_t));if (pnew NULL){perror(pnew malloc err);return -1;}// 初始化新节点pnew-data data;pnew-prior NULL;pnew-next NULL;// 插入链表的尾巴if (post p-len){p-tail-next pnew;pnew-prior p-tail;p-tail pnew; // 移动尾指针}// 中间差else{if (post p-len / 2) // 前半段{// temp移动到插入位置temp p-head;for (int i 0; i post; i)temp temp-next;}else // 后半段{temp p-tail;for (int i p-len - 1; i post; i--)temp temp-prior;}// 2) 进行插入操作(先连前面再练后面)pnew-prior temp-prior;temp-prior-next pnew;pnew-next temp;temp-prior pnew;}p-len; // 插入完成链表长度1return 0;
}3) 双向链表遍历 // 3.遍历双向链表
void showDoubleLinkList(double_list_p p)
{link_node_p temp NULL;printf(正向遍历\n);temp p-head;while (temp-next ! NULL){temp temp-next;printf(%d , temp-data);}printf(\n);printf(反向遍历\n);temp p-tail;while (temp ! p-head){printf(%d , temp-data);temp temp-prior;}printf(\n----------------\n);
}4) 判断双向链表是否为空 //4.判断双向链表是否为空
int isEmptyDoubleLinkList(double_list_p p)
{return p-len 0;
}5) 删除双向链表指定位置 //5.删除双向链表指定位置数据
int deletePostDoubleLinkList(double_list_p p,int post)
{link_node_p temp NULL;// 1. 容错判断if(isEmptyDoubleLinkList(p) || post p-len || post 0){error(deletePostDoubleLinkList err\n);return -1;}//2.对删除位置进行分析分为两种情况if(post p-len-1) // //删除的是链表最后一个节点{// 1)将尾指针向前移动一个位置p-tail p-tail-prior;// 2)释放被删除节点也就是最后一个节点free(p-tail-next);// 3)将最后一个节点与链表断开p-tail-next NULL;}else // 中间删除{if(post p-len/2) // 说明在前半段{temp p-head;for (int i 0; i post; i)temp temp-next;}else // 说明在后半段{temp p-tail;for (int i p-len-1; i post; i--){temp temp-prior;}}// 进行删除操作temp-prior-next temp-next;temp-next-prior temp-prior;free(temp);temp NULL;}// 3. 双向链表的长度-1p-len--;return 0;
}6) 求双向链表的长度 //6.求双向链表的长度
int lengthDoubleLinkList(double_list_p p)
{return p-len;
}7) 查找指定数据出现的位置 //7.查找指定数据出现的位置 data被查找的数据
int searchPostDoubleLinkList(double_list_p p,datatype data)
{link_node_p temp p-head;int post 0; // 保存位置while(temp-next ! NULL){temp temp-next;if(temp-data data){return post;}post;}return -1;
}8) 修改指定位置的数据 //8.修改指定位置的数据,post修改的位置 data被修改的数据
int changeDataDoubleLinkList(double_list_p p,int post, datatype data)
{if(isEmptyDoubleLinkList(p) || post p-len || post 0){perror(changeDataDoubleLinkList err);return -1;}link_node_p temp NULL;if(post p-len/2) // 说明在前半段{temp p-head;for (int i 0; i post; i)temp temp-next;}else{temp p-tail;for (int i p-len-1; i post; i--)temp temp-prior;}temp-data data;return 0;
}9) 删除双向链表中指定数据 // 9.删除双向链表中的指定数据 data代表删除所有出现的data数据
/*思想从头节点后节点开始用指针h遍历相当于遍历无头链表遇到需要删除节点的就用h指向它然后删除如果不需要删除则h继续往后走一个。这里因为是双向链表可以找到前驱所以不需要每次指向被删除节点的前一个然后跨过了。
*/
void deleteDataDoubleLinkList(double_list_p p, datatype data)
{link_node_p h p-head-next;link_node_p pdel NULL;while (h ! NULL) // 遍历双向链表(相当于遍历无头单向链表){if (h-data data) // 相等{if (h p-tail) // 尾节点{p-tail p-tail-prior;free(p-tail-next);p-tail-next NULL;h NULL;}else // 中间节点{h-prior-next h-next;h-next-prior h-prior;pdel h;h h-next;free(pdel);pdel NULL;}p-len--;}else{h h-next;}}
}main函数代码 int main(int argc, char const *argv[])
{// int i;double_list_p p createEmptyDoubleLinkList();for (int i 0; i 5; i){insertIntoDoubleLinkList(p, i, i);}showDoubleLinkList(p);deletePostDoubleLinkList(p, 2);printf(len is %d\n, lengthDoubleLinkList(p));showDoubleLinkList(p);deletePostDoubleLinkList(p, 3);showDoubleLinkList(p);printf(1 post is: %d\n, searchPostDoubleLinkList(p, 1));int len lengthDoubleLinkList(p);for (int i 0; i len; i){deletePostDoubleLinkList(p, 0);}printf(len is %d\n, lengthDoubleLinkList(p));showDoubleLinkList(p);printf(is Empty? %d\n, isEmptyDoubleLinkList(p));free(p);p NULL;return 0;
} 未完待续……
