线性表：一个线性表里面可以是任意的数据元素，但是同一个线性表里面数据应该是同类型的1 存在一个/唯一被称为第一个节点的节点2 存在一个/唯一被称为最后一个节点的节点3 除了第一个以外，每一个元素都有一个前驱节点4 除了最后一个，每一个元素都有一个后继节点满足以上性质，这个表就被称为线性表数组就是一个线性表想实现线性表的保存，我们需要考虑下面的事情1 元素要保存2 元素与元素之间的序偶关系谁是前面的谁是后面的我们有两种实现方式1 顺序结构 --- 数组所有的元素都有保存元素与元素之间的关系也被保存第一个的后面比是第二个，第二个的后面必是第三个......底层处理就是指针的步长来表示他们的关系a 第一个a + 1第二个.....序偶关系就被 +1 / -1表示出来了顺序表的基本操作增 -> O(n)删 -> O(n)改 -> O(1)查 -> O(n),如果有序，我们的查就可以提高效率(二分法)顺序表平时在使用的时候没有多大的问题，但是在数据量大的由于顺序表是连续的内存结构，因此面领着开不出空间的问题顺序表必须往大了开 --- 顺序表开出来之后就不可改变没有办法做到，你过来一个元素我才给你增加一个内存要解决顺序表的问题，我们需要考虑1 数据你要存2 元素与元素之间的序偶关系 --- 不像顺序表一样的，我们通过前后关系+1 -1就搞定了 我必须要弄一个什么东西来表示我们的前后最简单的就是指针，只要我这个元素里面有一个什么东西指向了我的后面的这个元素我就将我后面的关系给解决了因此我们的结构就变成了一个结构体，这个结构体里面分为两个部分1 数据元素2 序偶关系 --- 前后指针(单向只有一个指针，双向才会有两个指针)typedef int MyDataType;struct node{MyDataType data;//数据元素 数据域//序偶关系是指向我的前面或者后面的//前面的这个元素跟我是不是一模一样 //既然一模一样 那么就是本类指针struct node * next;//这个是指向我后面的元素 指针域struct node * prev;//这个是指向我前面的元素};单向链表：只需要保存它的前驱或者它的后继一般都是喜欢从前面往后面的因此我只需要一个next指针指向它的后继节点即可struct node//节点类型{MyDataType data;//数据元素 数据域struct node * next;//这个是指向我后面的元素 指针域};增 删 改 查 这些是基础的操作，见代码练习：尾插法插入到链表while(p ->next){p = p ->next;}//循环完毕 p就是最后一个在现有代码上面，输入一个什么数据，在这个链表找，如果有这个数据则返回他是第几个元素没有返回-1 -> 查 int SLLNH_Find_x(SLLNH_Node *first,const MyDataType x){}在x的前面加入y,如果x不存在则将y加入在最后x有可能是第一个，如果是第一个，将y加入到x的前面，第一个变成了y那么first就会发生改变，因此要将first返回SLLNH_Node * SLLNH_Add_x_y(SLLNH_Node *first,const MyDataType x,const MyDataType y){}删除x对应的那个节点(第一个) 如果x为first，删除之后first发生改变因此需要返回first 删除的这个节点是在堆上面的，因此要free，切记！！！SLLNH_Node * SLLNH_Delete_x(SLLNH_Node *first,const MyDataType x){}练习：1 我希望你建立一个升序的链表(链表的插入排序)找到第一个比它大的元素，将这个节点插入在这个元素的前面没有找到就插入到最后2 冒泡排序前面的比后面大就弄到交换位置3 反序输出这个链表 作业：1 就地逆置这个链表1 已经讲了2 每次将链表的第一个节点拿出来，头插法插入到新的链表将新的链表的第一个节点返回2 归并两个有序的链表，归并完毕，新的链表依然有序3 判断一个链表里面有没有环环：一坨形成一个圈了，循环不到终点利用快慢指针，如果快指针一次走两步，慢指针一次走一步快指针跑到终点就没有环快指针追上慢指针了，那么就有环了kuaide = kuaide ->next;if(kuaide){kuaide = kuaide ->next;}else{printf(没环);}
#include "SignalLinkedListNoHead.h"//弄一个节点出来 通过data弄出来一个节点
static SLLNH_Node * GetSLLNH_Node(const MyDataType data)
{SLLNH_Node * ptr = (SLLNH_Node *)calloc(1,sizeof(SLLNH_Node));//data赋值给数据域保存ptr ->data = data;ptr ->next = NULL;return ptr;//返回节点的地址
}//增加节点到链表 应你们的要求 我写的是头插法 每次都插入到第一个元素的前面
//那么它的第一个元素都在换 因此每次都要接收它的返回值-> 第一个元素的地址
//first为第一个元素 将node弄到first链表里面去//头插法
// static SLLNH_Node * SLLNH_Add_ForNode(SLLNH_Node *first,SLLNH_Node * node)
// {
// if(!node)//节点都没有 我增加个dr
// return first;
// //判断first是不是为空
// if(first)
// node ->next = first;//将node接到first的前面去
// return node;
// }//尾插法
SLLNH_Node * SLLNH_Add_Back_ForNode(SLLNH_Node *first,SLLNH_Node * node)
{// 如果要插入的节点为空，则直接返回原链表if(!node)return first;// 如果链表为空，则新节点成为头节点if(!first)return node;//遍历到最后一个节点SLLNH_Node * p = first;while(p -> next){//跳出条件p = p ->next; }//将新节点连接到末尾p -> next = node;//返回头节点，保证下一次从头节点开始遍历return first;
}//将data插入到链表里面去
SLLNH_Node * SLLNH_Add_ForData(SLLNH_Node *first,const MyDataType data)
{//将data弄成节点SLLNH_Node *node = GetSLLNH_Node(data);first = SLLNH_Add_Back_ForNode(first,node);return first;//return SLLNH_Add_ForNode(first,GetSLLNH_Node(data));
}//打印测试
void PrintSLLNH(SLLNH_Node *first)
{if(!first)return;//弄一个遍历指针SLLNH_Node * p = first;while(p){printf("%c ",p ->data);p = p ->next;}printf("\n");
}//查询
int SLLNH_Find_x(SLLNH_Node *first,const MyDataType x)
{if(!first){return -1;}int num = 1;SLLNH_Node *p = first;while(p){if(p -> data == x )//直接字符比较，不是字符串比较，不用使用strcmp{return num;}num++;p = p ->next;//比较完一个换下一个}return -1;
}//增加（插入节点）
SLLNH_Node * SLLNH_Add_x_y(SLLNH_Node *first,const MyDataType x,const MyDataType y)
{SLLNH_Node *node = GetSLLNH_Node(y);if(!first){return node;}//设置两个指针，一个指向当前节点，一个指向当前节点的下一个节点SLLNH_Node *f = first;SLLNH_Node *s = first;//遍历这个链表while(s){//判断是不是xif (x == s ->data){break;//如果是，就跳出循环，如果不是，就继续遍历}f = s;//两步让这个链表可以继续向后遍历s = s ->next;}//得到了和x相同的节点//开始根据s不同的的位置进行不同的插入//判断s是否在开头，如果在开头那么x就是现在链表里面的第一个节点，接完之后，新的节点成为第一个节点if(s == first){node ->next = first;//将新的节点的next指向firstreturn node;//返回新节点的值当作新的first}//s不在在开头就插入到s的前面f的后面f ->next = node;//f存入node的地址node ->next = s;//node存入s的地址return first;
}//删除
//删除x对应的那个节点(第一个) 如果x为first，删除之后first发生改变
//因此需要返回first 删除的这个节点是在堆上面的，因此要free，切记！！！
SLLNH_Node * SLLNH_Delete_x(SLLNH_Node *first,const MyDataType x)
{//判断有没有first，没有就不用删除直接返回firstif(!first){return first;}//依旧需要两个指针一前一后，保证在链表断裂后依旧能连接在一起SLLNH_Node * f = first;SLLNH_Node * s = first;//循环遍历寻找要删除的节点while(s){//马上判断第一个是不是要删除的的节点if(x == s ->data){break;//找到要删除的节点就立刻退出循环}f = s;s = s ->next;//指向下一个节点}//判断s位置以采取不同方案//如果是头，删掉之后应该让first 指向下一个节点if(s == first){first = first ->next;//删除头，将头的下一个节点作为新的头s ->next = NULL;//孤立这个节点free(s);//释放这个节点return first;//返回新的头}else if(s == NULL)//遍历全部都没有找到要删除的节点{printf("要删除的节点不存在\n");return first;}else//找到了节点，不在头部{f ->next = s ->next;//将f连接到s的下一个节点，然后释放ss ->next = NULL;free(s);return first;}}// 1 插入排序
// 我希望你建立一个升序的链表(链表的插入排序)
// 找到第一个比它大的元素，将这个节点插入在这个元素的前面
// 没有找到就插入到最后
SLLNH_Node * SLLNH_InsertSort(SLLNH_Node *first,const MyDataType data)//参数为插入值与头指针
{//首先得到一个插入值的节点SLLNH_Node * node = GetSLLNH_Node(data);//判断是否存在头指针if(!first)//如果没有头指针，那么直接返回插入值的指针{return node;}//如果有头指针，就要考虑插入哪里//插入一定会断裂或改变链表，所以需要两个节点指针连接链表SLLNH_Node * f = first;SLLNH_Node * s = first;//得到两个节点指针后开始遍历寻找要插入的位置while(s)//当s走到NULL之后代表没有比插入值更大的，所以插在最后面{//找到第一个比插入data大的data(如果找到第一个比插入data小的data，则插入在它前面，就会是反序)if(data < s ->data){break;}f = s;s = s ->next;}//同样要考虑只有头的问题if(s == first){node ->next = first;return node;}f -> next = node;node ->next = s;return first;
}// 2 冒泡排序
// 前面的比后面大就弄到交换位置
void SLLNH_Sort(SLLNH_Node *first)//参数只需要一个头指针
{//如果没有或者只有一个节点，就不需要排序直接退出if(!first || !first ->next){return;//排序无需返回值}//这次的冒泡只交换节点里面的数据，不交换地址//1 首先获取first里面的元素个数，决定了你冒泡的趟数//2 如果在一次完整的遍历后没有发生一次交换，代表不需排序，那么就直接退出，退出需要标记，所以要定义一个标记flag//不知道具体有多少元素，就先写个死循环让他排完序之后break出来while(1){int flag = 0;//同时也是跳出死循环的标志//定义两个指针，一个指向当前元素，一个指向下一个元素，方便两个值的交换SLLNH_Node *f = first;SLLNH_Node *s = first ->next;while(s)//到后值代表检查过所有节点，所以s为NULL时为退出条件{if(f ->data > s ->data)//如果前项 > 后项，就交换，得到的是升序排列{//定义一个中间变量进行交换MyDataType t;t = f ->data;f ->data = s ->data;s ->data = t;//有交换改变标记flag的值表示有过交换flag = 1;}f = s;s = s ->next;//指向下一个节点}//写跳出死循环的条件if(!flag)//代表一次循环都没有{break;}}}//反序输出这个列表（利用函数递归思维）
void SLLNH_ReverseOrder(SLLNH_Node *first)//只需要头指针一个参数
{if(!first)return;//我以相同的规则将后面的打印出来SLLNH_ReverseOrder(first ->next);//打印自己printf("%c ",first ->data);}//1 就地逆置这个链表
SLLNH_Node * SLLNH_ReverPlacement(SLLNH_Node *first)
{//首先如果没有节点或只有一个是用不上的if(!first || !first ->next){return;}//需要两个指针来完成操作SLLNH_Node * f = NULL;//新链表的头节点SLLNH_Node * s = NULL;// 用于保存下一个节点//遍历链表，逐个将节点插入新链表的头部 while(first != NULL){s = first ->next;// 保存原链表的下一个节点first ->next = f;// 将当前节点插入到新链表头部f = first;// 更新新链表的头节点first = s;// 移动到原链表的下一个节点}return f;}//2 归并两个有序的链表，归并完毕，新的链表依然有序
//两个参数为两个链表头节点
SLLNH_Node * SLLNH_Merge(SLLNH_Node *first1,SLLNH_Node *first2)
{//首先判断链表是否为空if(!first1){return first2;}if(!first2){return first1;}//开始合并两个链表//创建两个节点为合并后的头尾两节点SLLNH_Node * head = NULL;SLLNH_Node * tail = NULL;//确定合并后的头节点if(first1 ->data < first2 ->data)//两个链表的头节点比较，小的那个为新的头节点{head = first1;first1 = first1 ->next;}else{head = first2;first2 = first2 ->next;}//此时尾节点应该为头节点，即同一个节点tail = head;//比较两个节点，将较小的节点加入到合并后的链表里while(first1 && first2)//有一个加入完，剩下的全部排后面就可以{if(first1 ->data <first2 ->data){tail ->next = first1;first1 = first1 ->next;}else{tail ->next = first2;first2 = first2 ->next;}}//剩余的节点全部加入到合并后的链表里if(first1){tail ->next = first1;}else{tail ->next = first2;}return head;}//3 判断一个链表里面有没有环
//需要返回值表示是否有环
int SLLNH_Cycle(SLLNH_Node * first)//返回0表示无环，返回1表示有环
{//如果为空就无环if(!first){return 0;}//定义个快慢指针SLLNH_Node * slow = first;SLLNH_Node * fast = first;//写个循环让他们开始移动,当快的追上慢的代表有环while(fast && fast ->next){slow = slow ->next;fast = fast ->next ->next;if(slow == fast){return 1;}}return 0;
}
