县电子政务办网站建设工作思路,传媒公司是干嘛的,网站建设头像,wordpress幻灯片插件 汉化单向链表
1. 概念
单向链表 单向循环链表 双向链表 双向循环链表
解决#xff1a;长度固定的问题#xff0c;插入和删除麻烦的问题
1、逻辑结构#xff1a; 线性结构
2、存储结构#xff1a; 链式存储 链表就是将 结点 用链串起来的线性表#xff0c;链就是 结点 中的…单向链表
1. 概念
单向链表 单向循环链表 双向链表 双向循环链表
解决长度固定的问题插入和删除麻烦的问题
1、逻辑结构 线性结构
2、存储结构 链式存储 链表就是将 结点 用链串起来的线性表链就是 结点 中的指针域。
(赵, 钱, 孙, 李, 周, 吴, 郑, 王) 存储地址 数据域 指针域 头指针H 99 1 李 43 7 钱 13 13 孙 1 19 王 NULL 25 吴 37 31 赵 7 37 郑 19 43 周 25 99 31
2. 接口实现 用来操作顺序表的结构体定义
struct SeqList
{int data[10]; // 顺序表int last;
}
用来操作有头单向链表的结构体定义struct node_t
{int data; //数据域struct node_t *next;//指针域 指针指向自身结构体的类型(存放的下一个节点的地址)
}
链表 操作链表的结构体就是链表中结点的结构体。
顺序表 操作顺序表的结构体中就包含了顺序表数组。 3. 链表前言1
typedef struct node_t{char data; //数据域struct node_t *next;//指针域 指针指向自身结构体的类型(存放的下一个节点的地址)}link_node_t,* link_list_t;struct node_t《-》link_node_tlink_list_t《-》struct node_t * 《-》link_node_t *typedef struct node_t * - link_list_t
#if 0
struct node_t *p;
link_node_t *p;
link_list_t p;
int a;
int *p;
#endif
4. 链表前言2
4.1 遍历无头的单向链表
链表中的每一个节点的数据域和指针域都是有效的 while(p! NULL)
{printf(%c\n,p-data);p p-next;
} #include stdio.h
typedef struct node_t
{char data;struct node_t *next;
}link_node_t,*link_list_t;
int main(int argc, const char *argv[])
{link_node_t A{A,NULL};link_node_t B{.data B,.next NULL,};link_node_t C {C,NULL};link_node_t D {D,NULL};A.next B;B.next C;C.next D;link_list_t p A;while(p ! NULL)//无头单向链表的遍历条件{printf(%c\n,p-data);p p-next;//链表指针往后走} return 0;
}
4.2 遍历有头的单向链表 while(p-next ! NULL)
{
p p-next;
printf(%c, p-data);
}
#include stdio.h
//定义结构体类型
typedef struct node_t
{char data;struct node_t *next;
}link_node_t,*link_list_t;
int main(int argc, const char *argv[])
{
//定义结构体类型所对应的变量link_node_t head;link_node_t A;A.data A;A.next NULL;link_node_t B {B,NULL};link_node_t C {C,NULL};link_node_t D {D,NULL};head.next A;A.next B;B.next C;C.next D;link_list_t p head;while(p-next! NULL){p p-next;printf(%c\n,p-data);//A//p B;//B//p C;//c//p D;}return 0;
}
A B C D
有头链表中的第一个头节点的数据域无效但指针域有效
无头链表中的每一个节点的数据域和指针域都是有效的
在对有头单链表进行操作之前需要对其进行初始化即创建一个空的有头单链表。
初始化只需malloc开辟一个结点大小的空间存放有头单向链表头结点然后让有头单链表中的头结点指针域指向NULL即可。
想要找到单向链表并对其进行操作就需要一个指针来指向单向链表的头结点该指针就是头指针p
5. 有头单向链表操作函数
#ifndef _LINKLIST_H_
#define _LINKLIST_H_
#include stdio.h
#include stdlib.h
typedef int datatype;
typedef struct node_t
{datatype data;//数据域struct node_t *next;//指针域,指向自身结构体的指针
}link_node_t,*link_list_t;
//1.创建一个空的单向链表(有头单向链表)
link_node_t *CreateEpLinkList();
//2.向单向链表的指定位置插入数据
//p保存链表的头指针 post 插入的位置 data插入的数据
int InsertIntoPostLinkList(link_node_t *p,int post, datatype data);
//3.遍历单向链表
void ShowLinkList(link_node_t *p);
//4.求单向链表长度的函数
int LengthLinkList(link_node_t *p);
//5.删除单向链表中指定位置的数据 post 代表的是删除的位置
int DeletePostLinkList(link_node_t *p, int post);
//6.删除单向链表中出现的指定数据,data代表将单向链表中出现的所有data数据删除
int DeleteDataLinkList(link_node_t *p, datatype data)
//7.判断单向链表是否为空 1代表空 0代表非空
int IsEpLinkList(link_node_t *p);
//8.修改指定位置的数据 post 被修改的位置 data修改成的数据
int ChangePostLinkList(link_node_t *p, int post, datatype data);
//9.查找指定数据出现的位置 data被查找的数据 //search 查找
int SearchDataLinkList(link_node_t *p, datatype data);
//10.转置链表
void ReverseLinkList(link_node_t *p);
//11.清空单向链表
void ClearLinkList(link_node_t *p);
#endif
开辟空间存放头结点并返回指向头结点的指针该指针称为该链表的头指针。
5.1. 长度
使用伪头指针遍历单向链表
有头单向链表的遍历条件H-next ! NULL
无头单向链表的遍历条件H ! NULL
//4.求单向链表长度的函数
int LengthLinkList(link_node_t *p)
{int len 0;while(p-next ! NULL){p p-next;len;}return len;
}
#include linklist.h
int main(int argc, const char *argv[])
{ link_list_t p CreateEpLinkList();//尾插InsertIntoPostLinkList(p,0,996);InsertIntoPostLinkList(p,1,520);InsertIntoPostLinkList(p,2,666);ShowLinkList(p);//头插InsertIntoPostLinkList(p,0,88);ShowLinkList(p);//中间插InsertIntoPostLinkList(p,2,77);ShowLinkList(p);printf(led %d\n,LengthLinkList(p));return 0;
}
led 5
5.2. 插入
假设要在有头单向链表的post位置插入一个新的结点。
post类比下标即从0开始。 解题思想
1、先遍历找到要插入节点的前一个节点假设这个节点为AA的下一个节点为B
将C插入A与B之间
2、先让C的指针域指向B
3、再让A的指针域指向C
容错判断 [0, len]
post不能小于0post不能大于链表的长度
移动伪头指针使其指向插入位置的前一个结点
for (int i 0; i post; i)
p p-next;
生成新结点
link_list_t pnew malloc()
pnew-data data;
pnew-next NULL;
插入先后再前
pnew-next p-next;
p-next pnew; #include linklist.h
link_node_t *CreateEpLinkList()
{link_list_t p (link_list_t)malloc(sizeof(link_node_t));if(NULL p){printf(malloc error\n);return NULL;}//成员初始化p-next NULL;return p;
}
//2.向单向链表的指定位置插入数据
p保存链表的头指针 post 插入的位置 data插入的数据
int InsertIntoPostLinkList(link_node_t *p,int post, datatype data)
{if(post 0 || post LengthLinkList(p)){printf(InsertIntoPostLinkList post error\n);return -1;}link_list_t pnew (link_list_t)malloc(sizeof(link_node_t));if(NULL pnew){printf(InsertIntoPostLinkList malloc pnew error\n);return -1;}//初始化pnew节点pnew-data data;pnew-next NULL;//遍历到插入位置的前一个位置 int i;for(i 0; i post; i){p p-next;}//插入动作 pnew-next p-next;p-next pnew; return 0;
}
//3.遍历单向链表
void ShowLinkList(link_node_t *p)
{while(p-next ! NULL){p p-next;printf(%d ,p-data);}printf(\n);
}
#if 1
//4.求单向链表长度的函数
int LengthLinkList(link_node_t *p)
{int len 0;while(p-next ! NULL){p p-next;len;}return len;
}
#endif
#include linklist.h
int main(int argc, const char *argv[])
{ link_list_t p CreateEpLinkList();//尾插InsertIntoPostLinkList(p,0,996);InsertIntoPostLinkList(p,1,520);InsertIntoPostLinkList(p,2,666);ShowLinkList(p);//头插InsertIntoPostLinkList(p,0,88);ShowLinkList(p);//中间插InsertIntoPostLinkList(p,2,77);ShowLinkList(p);printf(led %d\n,LengthLinkList(p));return 0;
}
996 520 666
88 996 520 666
88 996 77 520 666
led 5
5.3. 查找
思路
post 0遍历 如果相等return post不等post
遍历结束没找到return -1 //8.查找指定数据出现的位置 data被查找的数据 //search 查找
int SearchDataLinkList(link_node_t *p, datatype data)
{if(IsEpLinkList(p)){printf(SearchDataLinkList failed\n);return -1;}int i 0;while(p-next ! NULL){ p p-next;if(p-data data){return i;}i;}return -1;
}
修改
修改指定位置数据
post类比下标即从0开始。 //7.修改指定位置的数据 post 被修改的位置 data修改成的数据
int ChangePostLinkList(link_node_t *p, int post, datatype data)
{if(post 0 || post LengthLinkList(p) || IsEpLinkList(p)){printf(ChangePostLinkList failed\n);return -1;}int i;for(i 0; i post; i){p p-next;}p-data data;return 0;
}
5.4. 删除
如果将伪头指针遍历指向删除结点那么其前驱的指针域next无法访问。
虽然能够知道前驱指针域next的值但无法对其进行修改。
前驱指针域next的值就是移动以后的H虽能知道其值是H但无法修改前驱的next。
删除结点会涉及三个结点
删除位置结点前驱后继
因为是单向链表故只能从前往后找不能从后往前找。这三个结点谁在最前面就让头指针遍历指向它。
5.4.1. 删除指定位置 由于链表中的每个结点都是malloc开辟出来的故需要一个PDel指针指向结点将其释放掉。 //5.删除单向链表中指定位置的数据 post 代表的是删除的位置
int DeletePostLinkList(link_node_t *p, int post)//5(4)
{//判断表是否为空||位置是否合理if(IsEpLinkList(p) || post 0 || post LengthLinkList(p)-1){printf(DeletePostLinkList error\n);return -1;}//1)遍历到删除节点的前一个节点 int i;for(i 0; i post; i){p p-next;} //2)pdel指向要删除的节点link_list_t pdel p-next;//3)将删除节点的前一个节点和删除节点的后一个节点链接到一起p-next pdel-next;free(pdel);pdel NULL;return 0;
}
//6.判断单向链表是否为空 1代表空 0代表非空
int IsEpLinkList(link_node_t *p)
{ return p-next NULL;
}
#include linklist.h
int main(int argc, const char *argv[])
{ link_list_t p CreateEpLinkList();//尾插InsertIntoPostLinkList(p,0,996);InsertIntoPostLinkList(p,1,520);InsertIntoPostLinkList(p,2,666);ShowLinkList(p);//头插InsertIntoPostLinkList(p,0,88);ShowLinkList(p);//中间插InsertIntoPostLinkList(p,2,77);ShowLinkList(p);//printf(led %d\n,LengthLinkList(p));DeletePostLinkList(p,2);ShowLinkList(p);return 0;
}
996 520 666
88 996 520 666
88 996 77 520 666
88 996 520 666
5.4.2. 删除指定数据
与删除指定位置思想一致。一定要让伪头指针在删除结点前。故使用头指针指向结点的后继的数据域与指定数据进行比较。 在链表中插入或删除某个结点不需要移动元素仅修改指针即可。
//7.删除单向链表中出现的指定数据(节点free)
//data代表将单向链表中出现的所有data数据删除
int DeleteDataLinkList(link_node_t *p, datatype data)
{link_list_t pdel NULL;if(IsEpLinkList(p)){printf(DeletePostLinkList error\n);return -1;}while(p-next ! NULL){if(p-next-data data){pdel p-next;p-next pdel-next;free(pdel);pdel NULL;}else{p p-next;}}return 0;
}
#include linklist.h
int main(int argc, const char *argv[])
{link_list_t p CreateEpLinkList();//尾插InsertIntoPostLinkList(p,0,996);InsertIntoPostLinkList(p,1,520);InsertIntoPostLinkList(p,2,666);ShowLinkList(p);//头插InsertIntoPostLinkList(p,0,88); ShowLinkList(p);//中间插InsertIntoPostLinkList(p,2,77);ShowLinkList(p);//printf(led %d\n,LengthLinkList(p));DeletePostLinkList(p,2);ShowLinkList(p);DeleteDataLinkList(p,520);ShowLinkList(p); return 0;
}
996 520 666
88 996 520 666
88 996 77 520 666
88 996 520 666
88 996 666
5.5. 清空 5.6. 转置
头-1-2-3-4-5 --- 头-5-4-3-2-1
步骤
头 1-2-3-4-5
头-1 2-3-4-5
头-2-1 3-4-5
头-3-2-1 4-5
思想将链表拆成空的有头单向链表和一个无头单向链表
遍历无头单向链表将每个结点头插进有头单向链表中 单向循环链表
约瑟夫问题
设编号为12……n的n个人围坐一圈约定编号为k (1≤k≤n)的人从1开始报数数到m的那个人出列。它的下一位继续从1开始报数数到m的人出列依次类推最后剩下一个为猴王。 假设n6总共6人k1从第一个人开始m5每次从1数到5。 第一轮报数从1号开始数5个数数完5个数5号被杀死第一轮报数后剩余人数如下。 第二轮报数 第三轮 第四轮 第五轮 #include stdio.h
#include stdlib.htypedef struct LinkListNode
{int data;struct LinkListNode *next;
} LLN, *LL;int main(int argc, const char *argv[])
{int i;LL PDel NULL; // 用于指向被删除节点LL PTail NULL; // 永远指向当前链表的尾LL PNew NULL; // 永远指向新创建的节点LL H NULL;int all_num 6; // 猴子总数int start_num 1; // 从几号猴子开始数int kill_num 5; // 数到几杀死猴// 1.创建出一个单向循环链表//(1)创建有all_num个节点的单向链表H (LL)malloc(sizeof(LLN));if (NULL H){perror(H malloc failed);return -1;}H-data 1;H-next NULL;PTail H; // 尾指针指向当前的第一个结点for (i 2; i all_num; i){// 创建新的节点PNew (LL)malloc(sizeof(LLN));if (NULL PNew){perror(PNew malloc failed);return -1;}// 将新结点装上数据PNew-data i;PNew-next NULL;// 将新结点链接到链表尾PTail-next PNew; // 链接到链表的尾PTail PNew; // 尾指针继续指向当前链表的尾}// 1 2 3 4 5 6//(2)将头指针保存到链表的尾形成单向循环链表PTail-next H; // 形成单向循环链表// 2.开始杀猴子//(1)将头指针移动到开始猴子的号码处for (i 0; i start_num - 1; i)H H-next;//(2)循环进行杀猴子while (H ! H-next) // 终止就剩一个猴子,只有一个节点{// 将头指针移动到即将删除节点的前一个节点for (i 0; i kill_num - 2; i)H H-next;PDel H-next;// 跨过删除节点H-next PDel-next;printf(kill is -------------%d\n, PDel-data);free(PDel);PDel NULL;// 杀死猴子后从下一个节点开始继续开始数,将头指针移动到开始数的地方H H-next;}printf(king is %d\n, H-data);return 0;
} 双向链表
单向链表 有头 无头
单向循环链表
链式栈 无头单向链表
链式队列有头单向链表
以上链表均只能从头往后找。即结点只有数据域和一个指向后继结点的指针域next。
双向链表即可以从前往后或者从后往前找这就意味着链表的结点就不能只有一个指针域next了还需要一个指向前驱结点的指针域prior。 1. 概念 逻辑结构线性结构物理结构链式存储结构
2. 接口实现
2.1. 定义操作双向链表的结构体
//双向链表的节点定义 typedef int datatype;typedef struct node_t{datatype data;//数据域 struct node_t *next;//指向下一个节点的指针 prior 先前的struct node_t *prior;//指向前一个节点的指针 next 下一个}link_node_t,*link_list_t;//将双向链表的头指针和尾指针封装到一个节点体里 //思想上有点像学的链式队列typedef struct doublelinklist{link_list_t head; //指向双向链表的头指针link_list_t tail; //指向双向链表的尾指针int len; //用来保存当前双向链表的长度}double_node_t,*double_list_t;
假如链表有一百个结点那么长想要删除第98个结点如果结构体中有链表的长度可以更加方便的使用尾指针进行操作。
2.2. 创建空的双向链表 开辟空间存放操作双向链表的结构体对结构体成员初始化的同时开辟空间存放头结点初始化头结点返回结构体指针
//1.创建一个空的双向链表
double_list_t createEmptyDoubleLinkList()
{//1.申请保存头指针和尾指针的空间double_list_t p (double_list_t)malloc(sizeof(double_node_t));if(NULL p){perror(createEmptyDoubleLinkList malloc failed);return NULL;}//2.将头指针和尾指针同时指向头节点因为当前链表为空p-len 0;//当前链表的长度为0p-head p-tail (link_list_t)malloc(sizeof(link_node_t));if(NULL p-head){perror(p-head malloc failed!!);return NULL;}//3.对双向链表的头结点进行初始化p-head-prior NULL;p-head-next NULL;//返回结构体指针return p;
}
2.3. 插入 PNew|post前驱新结点post结点| |PTemp-prior PTemp
插入位置有以下情况
尾插中间插 中间插前半段包括头插 移动头指针中间插后半段 移动尾指针
为什么将头插归类到中间插前半段中
因为只有尾插涉及到的是终端结点和新结点这两个结点。
头插涉及到的是头结点、新结点、零号结点这三个节点。
步骤
判错创新尾插中间插 中间插前半段 中间插后半段 无论前半段还是后半段伪指针指向插入位置post结点后其插入代码都是一样的
中间插口诀
先前再后temp-prior按兵不动
或
先新再旧temp-prior按兵不动
//2.向双向链表的指定位置插入数据 post位置 data数据
int insertIntoDoubleLinkList(double_list_t p, int post, datatype data)
{int i;link_list_t temp NULL;//用来临时保存head或tail的位置//1.容错判断if(post 0 || post p-len){printf(insertIntoDoubleLinkList post failed!!);return -1;}//2.创建一个新的节点用来保存插入的数据link_list_t pnew (link_list_t)malloc(sizeof(link_node_t));if(NULL pnew){perror(pnew malloc failed);return -1;}pnew-data data;//将参数上插入的数据装入节点pnew-prior NULL;pnew-next NULL;//3.将节点链接到链表中//先对插入位置进行判断分两种情况if(post p-len)//说明插入的是链表的尾巴{p-tail-next pnew;pnew-prior p-tail;p-tail pnew;//将尾指针再次移动到当前链表的尾永远指向尾}else//0-len-1{//(1)将temp移动到插入位置if(post p-len/2)//说明在前半段{temp p-head;//用头向后移动for(i 0; i post1; i)temp temp-next;}else//说明插入位置在后半部分{temp p-tail;//用尾向前移动for(i 0; i p-len-post-1; i)temp temp-prior;}//(2)进行插入操作(先连前面再连后面)pnew-prior temp-prior;temp-prior-next pnew;pnew-next temp;temp-prior pnew;}p-len;//链表的长度1return 0;
}
2.4. 打印
遍历双向链表
从前往后从后往前
//3.遍历双向链表
void showDoubleLinkList(double_list_t p)
{link_list_t temp NULL;printf(正向遍历:);temp p-head;while(temp-next ! NULL)//类似于遍历有头单向链表{temp temp-next;printf(%d ,temp-data);}printf(\n);printf(反向遍历:);temp p-tail;while(temp ! p-head)//类似于遍历无头单向链表{printf(%d ,temp-data);temp temp-prior;}printf(\n---------------------------------\n);
}2.5. 删除
2.5.1. 删除指定位置 前驱 post 后继| | |PTemp-prior PTemp PTemp-next1. 给前驱的next域赋值
2. 给后继的prior域赋值
//4.删除双向链表指定位置的数据
int deletePostDoubleLinkList(double_list_t p, int post)
{int i;link_list_t temp NULL;//临时用来保存头或尾指针//1.容错处理if(post 0 || post p-len){printf(deletePostDoubleLinkList post failed!!\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{//将temp移动到删除位置if(post p-len/2)//说明在前半段{temp p-head;for(i 0; i post1; i)temp temp-next;}else//说明在后半段{temp p-tail;for(i 0; i p-len-1-post; i)temp temp-prior;}//进行删除操作temp-prior-next temp-next;temp-next-prior temp-prior;free(temp);temp NULL;}//3.双向链表的长度-1p-len--;return 0;
}//5.判断双向链表是否为空
int isEmptyDoubleLinkList(double_list_t p)
{return p-len 0;
}
//6.求双向链表的长度
int lengthDoubleLinkList(double_list_t p)
{return p-len;
}
2.6. 修改
修改指定位置的数据
//8.修改指定位置的数据,post修改的位置 data被修改的数据
int changeDataDoubleLinkList(double_list_t p,int post, datatype data)
{link_list_t temp NULL;int i;//1.容错判断 if(post 0 || post p-len){printf(changeDataDoubleLinkList post is failed!!\n);return -1;}//2.将temp移动到修改数据的位置if(post p-len/2){temp p-head;for(i 0; i post1; i)temp temp-next;}else{temp p-tail;for(i 0; i p-len-post-1; i)temp temp-prior;}//3. 修改数据 temp-data data;return 0;
} 双向循环链表
思想和单向循环一样只需要将双向链表尾的next和头的prior双向链接即可。
#include stdio.h
#include stdlib.htypedef int datatype;
typedef struct node_t
{datatype data;struct node_t * prior;struct node_t * next;
}link_node_t,*link_list_t;typedef struct doublelinklist
{link_list_t head;link_list_t tail;
}double_node_t,*double_list_t;int main(int argc, const char *argv[])
{int i;int all_num 8;//猴子总数int start_num 3;//从3号猴子开始数int kill_num 3;//数到几杀死猴子 link_list_t h NULL;link_list_t pdel NULL;//用来指向被杀死猴子的节点printf(请您输入猴子的总数开始号码出局号码:\n);scanf(%d%d%d,all_num,start_num,kill_num);//1.创建一个双向的循环链表double_list_t p (double_list_t)malloc(sizeof(double_node_t));//申请头指针和尾指针if(NULL p){perror(malloc failed);return -1;}p-head p-tail (link_list_t)malloc(sizeof(link_node_t));if(NULL p-tail){perror(p-tail malloc failed);return -1;}p-head-data 1;p-head-prior NULL;p-head-next NULL;//将创建n个新的节点链接到链表的尾for(i 2; i all_num; i){link_list_t pnew (link_list_t)malloc(sizeof(link_node_t));if(NULL pnew){perror(pnew malloc failed);return -1;}pnew-data i;pnew-prior NULL;pnew-next NULL;//(1)将新的节点链接到链表的尾p-tail-next pnew;pnew-prior p-tail;//(2)尾指针向后移动指向当前链表的尾p-tail pnew;}//(3)形成双向循环链表 p-tail-next p-head;p-head-prior p-tail;//调试程序
#if 0while(1){printf(%d\n,p-head-data);p-head p-head-next;sleep(1);}
#endif//2.循环进行杀死猴子h p-head;//(1)先将h移动到start_num处也就是开始数数的猴子号码处for(i 0; i start_num-1; i)h h-next;while(h-next ! h)//当h-next h 就剩一个节点了循环结束{//(2)将h移动到即将杀死猴子号码的位置for(i 0; i kill_num-1; i)h h-next;//(3)进行杀死猴子经过上面的循环后此时的h指向即将杀死的猴子h-prior-next h-next;h-next-prior h-prior;pdel h;//pdel指向被杀死猴子的位置printf(kill is -------%d\n,pdel-data);h h-next;//需要移动从杀死猴子后的下一个位置开始数free(pdel);}printf(猴王是%d\n,h-data);return 0;
}
