建网站得多少钱,wordpress做淘宝客,网站建设的创新之处,重庆营销网站一、Xmind整理#xff1a; 双向链表的插入与删除#xff1a; 二、课上练习#xff1a; 练习1#xff1a;单链表任意元素删除
/** function: 按元素删除* param [ in] * param [out] * return 返回堆区首地址*/
Linklist delete_by_data(datatype key,Linklist L)
…一、Xmind整理 双向链表的插入与删除 二、课上练习 练习1单链表任意元素删除
/** function: 按元素删除* param [ in] * param [out] * return 返回堆区首地址*/
Linklist delete_by_data(datatype key,Linklist L)
{//1,先根据key查找位置int delete_possearch_by_data(key,L);if(delete_pos-1)return L;//2,元素存储Ldelete_by_pos(delete_pos,L);return L;/*int pos0;Linklist pL;while(L!NULL){pos;if(L-datakey){ pdelete_by_pos(pos,p);pos--;}else{LL-next;}}return p;*/}
练习2 单链表任意元素查找
/** function: 元素查找* param [ in] * param [out] * return 返回位置失败-1*/
int search_by_data(datatype key,Linklist L)
{//1,判断是否为空if(NULLL){return -1;}//2,查找元素keyint pos0;while(L!NULL){pos;if(L-datakey){return pos;}LL-next;}return -1;
}
练习3 单链表逆置 /** function: 逆置* param [ in] * param [out] * return 返回地址*/
Linklist rev_lInklist(Linklist L)
{//判断链表是否为空//判断链表甚至有一个节点if(NULL L || L-nextNULL){return L;}//链表有多个节点Linklist pL-next;int lenLen_linklist(L)-1;L-nextNULL;for(int i0;ilen;i){Linklist tp;pp-next;t-nextL;Lt;}return L;
}
练习4单链表排序冒泡排序 /** function: 冒泡排序* param [ in] * param [out] * return */
void Bubble(Linklist L)
{//1,判断是否为空//2判断如果链表只有一个节点if(NULLL || L-nextNULL){return ;}//冒泡排序int lenLen_linklist(L);Linklist p;int i,j;for( i1;ilen;i){for( j0,pL;jlen-i;j,pp-next){if(p-datap-next-data){datatype tp-data;p-datap-next-data;p-next-datat;}}}
}
练习5 单链表释放
/** function: 释放* param [ in] * param [out] * return 返回堆去首地址*/
Linklist free_space(Linklist L)
{if(NULLL){return NULL;}int lenLen_linklist(L);for(int i0;ilen;i){Ldelete_head(L);}return L;
}
练习6单向循环链表节点创建
/** function: 创建一个节点* param [ in] * param [out] * return */
Linklist create_node()
{
Linklist node(Linklist)malloc(sizeof(struct Node));if(NULLnode)return NULL;
node-data0;
node-nextnode;//循环链表的每个节点指针域指向自己return node;//0x10
}
练习7单向循环链表头插 /** function: 头插* param [ in] * param [out] * return 成功返回0 失败返回-1*/
Linklist loop_insert_head(datatype e,Linklist L)
{//在堆区创建一个节点Linklist nodecreate_node();//在堆区申请一个节点if(nodeNULL)return L;if(NULLL){Lnode;node-datae;}else{node-nextL-next;L-nextnode;node-dataL-data;L-datae;}return L;//因为自定义的函数指针的改变不影响实参需要返回
}练习8单向循环链表的尾插 /** function: 尾部插入* param [ in] * param [out] * return */
Linklist loop_insert_rear(datatype e,Linklist L)
{Linklist screate_node();s-datae;if(LNULL){Ls;}else{Linklist rearL;while(rear-next!L){rearrear-next;}rear-nexts;s-nextL;}return L;
}练习9单向循环链表的头删 /** function: 头删除* param [ in] * param [out] * return */
Linklist loop_delete_head(Linklist L)
{//判断链表是否为空if(NULLL){return L;}if(L-nextL){free(L);LNULL;}else{Linklist qL-next;L-dataq-data;L-nextq-next;free(q);qNULL;}return L;
}练习10单向循环链表的尾删 /** function: 尾部删除* param [ in] * param [out] * return */
Linklist delete_rear(Linklist L)
{//1.判断链表是否为空if(NULLL){return NULL;}//2.判断如果链表只有一个节点else if(L-nextL){free(L);LNULL;}else{//3.有多个节点//循环倒数第二个节点Linklist secondL;while(second-next-next!L){secondsecond-next;}free(second-next);second-nextL;}return L;
}练习11单向循环链表的遍历 /** function: 循环遍历* param [ in] * param [out] * return */
int loop_output(Linklist L)
{//判断是否创建//判断是否为空if(NULLL){return -1;}Linklist pL;do{printf(%d\t,p-data);pp-next;}while(p!L);puts();
}练习12约瑟夫环
约瑟夫环用循环链表编程实现约瑟夫问题
n个人围成一圈从某人开始报数1, 2, …, m数到m的人出圈然后从出圈的下一个人(m1)开始重复此过程直到全部人出圈于是得到一个出圈人员的新序列
如当n8m4时若从第一个位置数起则所得到的新的序列 为4, 8, 5, 2, 1, 3, 7, 6。 /** function: 约瑟夫环* param [ in] * param [out] * return */
void Joseph(Linklist L,int n,int m)
{Linklist pL;for(int i0;in;i){for(int j0;jm-2;j){pp-next;}Linklist qp-next;p-nextq-next;printf(%d\t,q-data);free(q);qNULL;pp-next;}printf(\n);
}单向循环链表目前整体代码
head.h
#ifndef __HEAD_H__
#define __HEAD_H__#include stdio.h
#include string.h
#include stdlib.h
typedef int datatype;
//定义单链表节点结构体
typedef struct Node
{//数据域数据元素datatype data;//指针域存储下一个节点的地址struct Node *next;
}*Linklist;
Linklist create_node();
Linklist loop_insert_head(datatype e,Linklist L);
int loop_output(Linklist L);
Linklist loop_insert_rear(datatype e,Linklist L);
Linklist loop_delete_head(Linklist L);
Linklist delete_rear(Linklist L);
void Joseph(Linklist L,int n,int m);#endiftest.c
#include head.h
/** function: 创建一个节点* param [ in] * param [out] * return */
Linklist create_node()
{Linklist node(Linklist)malloc(sizeof(struct Node));if(NULLnode)return NULL;node-data0;node-nextnode;//循环链表的每个节点指针域指向自己return node;
}
/** function: 头插* param [ in] * param [out] * return 成功返回0 失败返回-1*/
Linklist loop_insert_head(datatype e,Linklist L)
{//在堆区创建一个节点Linklist nodecreate_node();//在堆区申请一个节点if(nodeNULL)return L;if(NULLL){Lnode;node-datae;}else{node-nextL-next;L-nextnode;node-dataL-data;L-datae;}return L;//因为自定义的函数指针的改变不影响实参需要返回
}
/** function: 循环遍历* param [ in] * param [out] * return */
int loop_output(Linklist L)
{//判断是否创建//判断是否为空if(NULLL){return -1;}Linklist pL;do{printf(%d\t,p-data);pp-next;}while(p!L);puts();
}
/** function: 尾部插入* param [ in] * param [out] * return */
Linklist loop_insert_rear(datatype e,Linklist L)
{Linklist screate_node();s-datae;if(LNULL){Ls;}else{Linklist rearL;while(rear-next!L){rearrear-next;}rear-nexts;s-nextL;}return L;
}
/** function: 头删除* param [ in] * param [out] * return */
Linklist loop_delete_head(Linklist L)
{//判断链表是否为空if(NULLL){return L;}if(L-nextL){free(L);LNULL;}else{Linklist qL-next;L-dataq-data;L-nextq-next;free(q);qNULL;}return L;
}
/** function: 尾部删除* param [ in] * param [out] * return */
Linklist delete_rear(Linklist L)
{//1.判断链表是否为空if(NULLL){return NULL;}//2.判断如果链表只有一个节点else if(L-nextL){free(L);LNULL;}else{//3.有多个节点//循环倒数第二个节点Linklist secondL;while(second-next-next!L){secondsecond-next;}free(second-next);second-nextL;}return L;
}
/** function: 约瑟夫环* param [ in] * param [out] * return */
void Joseph(Linklist L,int n,int m)
{Linklist pL;for(int i0;in;i){for(int j0;jm-2;j){pp-next;}Linklist qp-next;p-nextq-next;printf(%d\t,q-data);free(q);qNULL;pp-next;}printf(\n);
}main.c
#include head.h
int main(int argc, const char *argv[])
{Linklist LNULL;/*int n;datatype e;printf(please enter n:);scanf(%d,n);for(int i0;in;i){printf(please enter element:);scanf(%d,e);//头插在头指针当前节点插入Lloop_insert_head(e,L);}loop_output(L);//尾部插入for(int i0;in;i){printf(please enter element:);scanf(%d,e);Lloop_insert_rear(e,L);}loop_output(L);//循环链表//loop_output(L);//头删//Lloop_delete_head(L);//loop_output(L);//尾删//Ldelete_rear(L);//loop_output(L);*/int n,m;//n表示节点的总个数m表示几个一出圈printf(输入一共有多个人);scanf(%d,n);for(int i0;in;i){Lloop_insert_rear(i1,L);}//约瑟夫环printf(输入几个一出圈);scanf(%d,m);Joseph(L,n,m);return 0;
}练习13双向链表节点创建
/** function: 创建节点* param [ in] * param [out] * return 返回节点的地址*/
DoubleLink create_node()
{
DoubleLink node(DoubleLink)malloc(sizeof(struct Node));if(NULLnode)return NULL;//对新节点的数据域初始化strcpy(node-data,);//对指针域赋值
node-nextnode-prevNULL;return node;
}
练习14双向链表头插 /** function: 双向链表头插* param [ in] * param [out] * return 返回链表*/
DoubleLink insert_head(datatype e,DoubleLink L)
{//1,创建新节点s
DoubleLink screate_node();if(NULLs)return L;strcpy(s-data,e);if(NULL !L){s-nextL;L-prevs;}Ls;return L;
}
练习15双向链表尾插 /** function: 尾部插入* param [ in] * param [out] * return 返回地址*/
DoubleLink insert_rear(datatype e,DoubleLink L)
{//1,创建新节点s
DoubleLink screate_node();if(NULLs)return L;strcpy(s-data,e);//链表为空if(NULLL){Ls;return L;}//表示存在多个节点//找到尾部节点
DoubleLink rearL;while(rear-next!NULL){rearrear-next;}
rear-nexts;
s-prevrear;return L;
}
练习16双向链表头删 /** function: 头删* param [ in] * param [out] * return 返回地址*/
DoubleLink delete_head(DoubleLink L)
{//1,如果链表为空if(NULLL)return L;//2,判断链表只有一个节点if(NULLL-next){free(L);LNULL;return L;}//3,有多个节点
DoubleLink qL-next;strcpy(L-data,q-data);
L-nextq-next;if(q-next!NULL)q-next-prevL;free(q);
qNULL;return L;
}
练习17双向链表尾删 /** function: 尾部删除* param [ in] * param [out] * return 返回地址*/
DoubleLink delete_rear(DoubleLink L)
{//1,如果链表为空if(NULLL)return L;//2,判断链表只有一个节点if(NULLL-next){free(L);LNULL;return L;}//3,存在多个节点//找到倒数第一个节点
DoubleLink rearL;while(rear-next!NULL)rearrear-next;rear-prev-nextNULL;free(rear);
rearNULL;return L;
}
练习18双向链表遍历 /** function: 循环输出* param [ in] * param [out] * return */
void output(DoubleLink L)
{//1,判断链表是否为空if(NULLL){return;}//正向遍历puts(正向遍历);while(L-next!NULL){printf(%s\t,L-data);LL-next;}printf(%s\t,L-data);puts(\n逆向遍历);while(L!NULL){printf(%s\t,L-data);LL-prev;}puts();}
双向链表目前整体代码
head.h
#ifndef __HEAD_H
#define __HEAD_H#include stdio.h
#include string.h
#include stdlib.h
typedef char datatype[20];//datatype--char [20]//定义双向链表节点的结构体
typedef struct Node
{//数据域数据元素datatype data;//指针域下一个节点的地址struct Node *next;//指针域上一个节点的地址struct Node *prev;
}*DoubleLink;DoubleLink create_node();
DoubleLink insert_head(datatype e,DoubleLink L);
void output(DoubleLink L);
DoubleLink insert_rear(datatype e,DoubleLink L);
DoubleLink delete_head(DoubleLink L);
DoubleLink delete_rear(DoubleLink L);#endiftest.c
#include double_head.h
/** function: 创建节点* param [ in] * param [out] * return 返回节点位置*/
DoubleLink create_node()
{DoubleLink node(DoubleLink)malloc(sizeof(struct Node));if(NULLnode)return NULL;//对新节点的数据域初始化strcpy(node-data,);//对指针域赋值node-nextnode-prevNULL;return node;
}
/** function: 双向链表头插* param [ in] * param [out] * return 返回链表*/
DoubleLink insert_head(datatype e,DoubleLink L)
{//1.创建新节点sDoubleLink screate_node();if(NULLs)return L;strcpy(s-data,e);if(NULL!L){s-nextL;L-prevs;}Ls;return L;
}
/** function: 循环输出* param [ in] * param [out] * return */
void output(DoubleLink L)
{//1.判断链表是否为空if(NULLL){return;}//正向遍历puts(正向遍历);while(L-next!NULL){printf(%s\t,L-data);LL-next;}printf(%s\t,L-data);puts();//逆向遍历puts(逆向遍历);while(L!NULL){printf(%s\t,L-data);LL-prev;}puts();
}
/** function: 双向链表尾插* param [ in] * param [out] * return */
DoubleLink insert_rear(datatype e,DoubleLink L)
{//1.创建新节点sDoubleLink screate_node();if(NULLs)return L;strcpy(s-data,e);//链表为空if(NULLL){Ls;return L;}//表示存在多个节点//找到尾部节点DoubleLink rearL;while(rear-next!NULL){rearrear-next;}rear-nexts;s-prevrear;return L;
}
/** function: 双向链表头删* param [ in] * param [out] * return 返回地址*/
DoubleLink delete_head(DoubleLink L)
{//1.如果链表为空if(NULLL)return L;//2.判断链表只有一个节点if(NULLL-next){free(L);LNULL;return L;}//3.存在多个节点DoubleLink qL-next;strcpy(L-data,q-data);L-nextq-next;if(q-next!NULL)q-next-prevL;free(q);qNULL;return L;
}
/** function: 双向链表尾删* param [ in] * param [out] * return 返回地址*/
DoubleLink delete_rear(DoubleLink L)
{//1.如果链表为空if(NULLL)return L;//2.判断链表只有一个节点if(NULLL-next){free(L);LNULL;return L;}//3.存在多个节点//找到倒数第一个节点DoubleLink rearL;while(rear-next!NULL)rearrear-next;rear-prev-nextNULL;free(rear);rearNULL;return L;
}main.c
#include double_head.h
int main(int argc, const char *argv[])
{DoubleLink LNULL;int n;datatype e;printf(please enter n:);scanf(%d,n);for(int i0;in;i){printf(please enter element:);scanf(%s,e);//Linsert_head(e,L);Linsert_rear(e,L);}//循环输出output(L);//头删//Ldelete_head(L);//尾删Ldelete_rear(L);output(L);return 0;
}三、课后作业
1.单向链表简单选择排序
void Sort(Linklist L)
{ //1.判断是否为空//2.判断如果链表只有一个节点if(NULLL||L-nextNULL){return;}//简单选择int lenLen_linklist(L);Linklist p;Linklist q;int i,j;for(i0,pL;ilen-1;i,pp-next){Linklist minp;for(ji1,qp-next;jlen;j,qq-next){if(min-dataq-data){minq;}}if(min!p){datatype tp-data;p-datamin-data;min-datat;}}
}2.单向链表任意元素插入
/** function: 按元素插入* param [ in] * param [out] * return 成功返回0 失败返回-1*/
int insert_by_data(datatype key,datatype e,Linklist L)
{//1.判断元素是否为空if(NULLL){return -1;}//2.查找元素keyLinklist p L;while(p!NULLp-data!key){p p-next;}//若key不存在则返回错误码-1if(pNULL){return -1;}//3.创建新节点并插入链表Linklist qcreate_node();q-datae;q-nextp-next;p-nextq;return 0;
}3.单向链表任意元素修改
/** function: 按元素修改* param [ in] * param [out] * return 成功返回0 失败返回-1*/
int update_by_data(datatype key,datatype e,Linklist L)
{//1.判断元素是否为空if(NULLL){return -1;}//2.查找元素keyLinklist p L;while(p!NULLp-data!key){p p-next;}//若key不存在则返回错误码-1if(pNULL){return -1;}p-datae;return 0;
}
