焦作市网站建设哪家好,一流的句容网站建设,网页设计题目,怀化市建设局网站地址目录 一、概念与结构
二、实现单链表
三、链表的分类
四、单链表算法题 一、概念与结构 1、节点 结点的组成主要有#xff1a;当前结点要保存的数据和保存下一个节点的地址#xff08;指针变量#xff09; 图中指针变量plist保存的是第一个结点的地址#xff0c;我们称p…目录 一、概念与结构
二、实现单链表
三、链表的分类
四、单链表算法题 一、概念与结构 1、节点 结点的组成主要有当前结点要保存的数据和保存下一个节点的地址指针变量 图中指针变量plist保存的是第一个结点的地址我们称plist此时“指向”第一个结点。 链表中每个结点都是独立申请的如果需要插入数据时才去申请一块结点的空间我们需 要通过指针变量来保存下一个结点位置才能从当前结点找到下一个结点。 2、链表的性质
【链表机构在逻辑上是连续的在物理结构上不一定连续。
【结点一般是从堆上申请的。
【从堆上申请来的空间是按照一定策略分配出来的每次申请的空间可能连续可能不连续。 二、实现单链表 1、创立文件 2、定义链表的结构
【SList.h】
//定义链表(结点)的位置
typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;void SLTPrint(SLTNode* phead);
3、打印函数
【SList.h】
//打印函数
void SLTPrint(SLTNode* phead);
【SList.c】
//打印函数
void SLTPrint(SLTNode* phead)
{SLTNode* pcur phead;while (pcur){printf(%d-, pcur-data);pcur pcur-next;}printf(NULL\n);
}
【test.c】
//创建一个链表并且打印链表
void createSList()
{SLTNode* node1 (SLTNode*)malloc(sizeof(SLTNode));node1-data 1;SLTNode* node2 (SLTNode*)malloc(sizeof(SLTNode));node1-data 2;SLTNode* node3 (SLTNode*)malloc(sizeof(SLTNode));node1-data 3;SLTNode* node4 (SLTNode*)malloc(sizeof(SLTNode));node1-data 4;node1-next node2;node2-next node3;node3-next node4;node4-next NULL;//第一个结点的地址作为参数传递过去SLTNode* plist node1;SLTPrint(node1);
} 4、判断插入时空间是否足够
【SList.c】
//判断插入数据时空间是否足够
SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* node (SLTNode*)malloc(sizeof(SLTNode));if (node NULL){perror(malloc fail!);exit(1);}node-data x;node-next NULL;return node;
} 5、尾插
【SList.h】
//尾插
void SLTPushBack(SLTNode** pphead,SLTDataType x);
【SList.c】
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);//形参pphead -- 实参plist//*pphead 解引用 -- plist//申请新结点SLTNode* newnode SLTBuyNode(x); //判断是否有足够空间if (*pphead NULL){*pphead newnode;}else{//尾节点 -- 新结点//找尾节点SLTNode* ptail *pphead;while (ptail-next){ptail ptail-next;}//ptail -- newnodeptail-next newnode;}
}
【test.c】
void SListTest01()
{SLTNode* plist NULL;SLTPushBack(plist, 1);SLTPrint(plist); //1-NULLSLTPushBack(plist, 2);SLTPrint(plist); //1-2-NULLSLTPushBack(plist, 3);SLTPrint(plist); //1-2-3-NULLSLTPushBack(plist, 4);SLTPrint(plist); //1-2-3-4-NULL
}
【运行结果】 6、头插
【SList.h】
//头插
void SLTPushFront(SLTNode** pphead,SLTDataType x);
【SList.c】
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode SLTBuyNode(x); //判断是否有足够空间//newnode *ppheadnewnode-next *pphead;*pphead newnode;
}
【test.c】
void SListTest01()
{SLTNode* plist NULL;//头插SLTPushFront(plist, 1);SLTPushFront(plist, 2);SLTPushFront(plist, 3);SLTPushFront(plist, 4);SLTPrint(plist); //4-3-2-1-NULL
}【运行结果】 7、尾删
【SList.h】
//尾删
void SLTPopBack(SLTNode** pphead);
【SList.c】
//尾删
void SLTPopBack(SLTNode** pphead)
{//判断链表是不是空若为空则不可以删assert(pphead *pphead);//处理只有一个结点的情况要删除的就是头结点当next指针为空if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else{//找尾结点ptail 和尾结点的前一个结点prevSLTNode* ptail *pphead;SLTNode* prev NULL;//遍历数组,找尾结点while (ptail-next){prev ptail;ptail ptail-next;}prev-next NULL;free(ptail);ptail NULL;}
}
【test.c】
void SListTest01()
{SLTNode* plist NULL;//头插SLTPushFront(plist, 1);SLTPushFront(plist, 2);SLTPushFront(plist, 3);SLTPushFront(plist, 4);//尾删SLTPopBack(plist);SLTPrint(plist); //4-3-2-NULLSLTPopBack(plist);SLTPrint(plist); //4-3-NULLSLTPopBack(plist);SLTPrint(plist); //4-NULLSLTPopBack(plist);SLTPrint(plist); //NULL
}
【运行结果】 8、头删
【SList.h】
//头删
void SLTPopFront(SLTNode** pphead);
【SList.c】
//头删
void SLTPopFront(SLTNode** pphead)
{assert(pphead *pphead);SLTNode* next (*pphead)-next;//删除*pphead -- nextfree(*pphead);*pphead next;
}
【test.c】
void SListTest01()
{SLTNode* plist NULL;//头插SLTPushFront(plist, 1);SLTPushFront(plist, 2);SLTPushFront(plist, 3);SLTPushFront(plist, 4);//SLTPrint(plist); //4-3-2-1-NULL//头删SLTPopFront(plist);SLTPrint(plist); //3-2-1-NULLSLTPopFront(plist);SLTPrint(plist); //2-1-NULLSLTPopFront(plist);SLTPrint(plist); //1-NULLSLTPopFront(plist);SLTPrint(plist); //NULL
}【运行结果】 9、查找
【SList.h】
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
【SList.c】
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{assert(phead);SLTNode* pcur phead;while (pcur){if (pcur-data x){return pcur;}pcur pcur-next;}//跳出循环说明没找到return NULL;
}
【test.c】
void SListTest01()
{SLTNode* plist NULL;//头插SLTPushFront(plist, 1);SLTPushFront(plist, 2);SLTPushFront(plist, 3);SLTPushFront(plist, 4);//SLTPrint(plist); //4-3-2-1-NULL//查找SLTNode* find SLTFind(plist, 3);if (find NULL){printf(没找到\n);}else{printf(find it!\n);}
}【运行结果】 10、在指定位置之前插入数据
【SList.h】
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
【SList.c】
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);//如果pos恰好是头结点if (pos *pphead){SLTPushFront(pphead, x); //相当于头插}else{SLTNode* newnode SLTBuyNode(x);//找到pos的前一个结点:prevSLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}//跳出这个循环说明prev的前一个结点就是pos//将newnode插入prev和pos之间newnode-next pos;prev-next newnode;}
}
【test.c】
void SListTest01()
{SLTNode* plist NULL;//头插SLTPushFront(plist, 1);SLTPushFront(plist, 2);SLTPushFront(plist, 3);SLTPushFront(plist, 4);SLTPrint(plist); //4-3-2-1-NULL//查找SLTNode* find SLTFind(plist, 2);//在指定位置之前插入数据SLTInsert(plist, find, 11); //在2之前插入11SLTPrint(plist); //4-3-11-2-1-NULL
}
【运行结果】 11、在指定位置之后插入数据
【SList.h】
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
【SList.c】
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode SLTBuyNode(x);//把newnode放到pos的下一个位置pos-nextnewnode-next pos-next;pos-next newnode;
}
【test.c】
void SListTest01()
{SLTNode* plist NULL;//头插SLTPushFront(plist, 1);SLTPushFront(plist, 2);SLTPushFront(plist, 3);SLTPushFront(plist, 4);SLTPrint(plist); //4-3-2-1-NULL//查找SLTNode* find SLTFind(plist, 2);//在指定位置之后插入数据SLTInsertAfter(find, 9); //在2之后插入9SLTPrint(plist); //4-3-2-9-1-NULL
}【运行结果】 12、删除pos结点
【SList.h】
//删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos);
【SList.c】
//删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pos);assert(pphead *pphead);//头插如果pos恰好为头结点*pphead,那就没有前一个结点prev了if (pos *pphead){SLTPopFront(pphead);}else{SLTNode* prev *pphead;while (prev-next ! pos){ //遍历数组寻找posprev prev-next;}//跳出循环prev刚好是pos的前一个结点(要删除pos)prev-next pos-next;free(pos);pos NULL;}}
【test.c】
void SListTest01()
{SLTNode* plist NULL;//头插SLTPushFront(plist, 1);SLTPushFront(plist, 2);SLTPushFront(plist, 3);SLTPushFront(plist, 4);SLTPrint(plist); //4-3-2-1-NULL//查找SLTNode* find SLTFind(plist, 2);//删除pos结点SLTErase(plist, find); //删除pos(2)这个结点SLTPrint(plist); //4-3-1-NULL
}
【运行结果】 13、删除pos之后的结点
【SList.h】
//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos);
【SList.c】
//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos)
{assert(pos);assert(pos-next);//删除pos的下一个结点就要让pos的下一个结点直接指向pos的next的next//但是后面要把pos-next释放删除掉所以先把这个指针保存起来SLTNode* del pos-next;pos-next pos-next-next;free(del);del NULL;
}
【test.c】
void SListTest01()
{SLTNode* plist NULL;//头插SLTPushFront(plist, 1);SLTPushFront(plist, 2);SLTPushFront(plist, 3);SLTPushFront(plist, 4);SLTPrint(plist); //4-3-2-1-NULL//查找SLTNode* find SLTFind(plist, 2);//删除pos之后的结点SLTEraseAfter(find);SLTPrint(plist); //4-3-2-NULL
}
【运行结果】 14、销毁链表
【SList.h】
//销毁链表
void SListDestroy(SLTNode** pphead);
【SList.c】
//销毁链表
void SListDestroy(SLTNode** pphead)
{assert(pphead);assert(*pphead);SLTNode* pcur *pphead;while (pcur){SLTNode* next pcur-next;free(pcur);pcur next;}*pphead NULL;
}
【test.c】
void SListTest01()
{SLTNode* plist NULL;//头插SLTPushFront(plist, 1);SLTPushFront(plist, 2);SLTPushFront(plist, 3);SLTPushFront(plist, 4);SLTPrint(plist); //4-3-2-1-NULL//查找SLTNode* find SLTFind(plist, 2);//销毁链表SListDestroy(plist);SLTPrint(plist); //NULL
}
【运行结果】 三、链表的分类 四、单链表算法题
1、反转链表
【思路】 【代码】
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head)
{//处理空链表if(head NULL){return head;}//创建三个指针ListNode* n1,*n2,*n3;n1 NULL , n2 head , n3 n2-next; while(n2){n2-next n1;n1 n2;n2 n3;if(n3){n3 n3-next;}}//此时n1就是链表反转后新的头结点headreturn n1;
}
2、链表的中间结点
【思路】 【代码】
typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {ListNode* slow head,*fast head;//慢指针每次走一步//快指针每次走两步while(fast fast-next) //等价于fast!NULL fast-next!NULL
//当fast或fast-fast任何一个为空指针为假时就跳出循环{slow slow-next;fast fast-next-next;}//此时slow指向得节点刚好就是中间节点return slow;}
3、合并两个有序链表
【思路】 【代码】
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{//处理链表为空的情况if(list1 NULL){return list2;}if(list2 NULL){return list1;}//创建新链表ListNode*newHead NULL,*newTail NULL;//创建两个指针分别指向两个链表的头结点ListNode* l1 list1;ListNode* l2 list2;//比大小while(l1 l2){if(l1-val l2-val){//l1尾插到新链表中if(newHead NULL){newHead newTail l1;}else{newTail-next l1;newTail newTail-next;}l1 l1-next;}else{//l2尾插到新链表if(newHead NULL){newHead newTail l2;}else{newTail-next l2;newTail newTail-next;}l2 l2-next;}}//跳出while循环只有两种情况l1为空l2肯定不为空 或 l2为空l1不为if(l1) //l1不为空{newTail-next l1;}if(l2) //l2不为空{newTail-next l2;}return newHead;
}
4、链表分割
【思路】 【代码】
class Partition
{
public:ListNode* partition(ListNode* pHead, int x) { //创建两个非空链表小链表、大链表//小链表ListNode* lessHead,*lessTail;lessHead lessTail (ListNode*)malloc(sizeof(ListNode));//大链表 ListNode* greaterHead,*greaterTail;greaterHead greaterTail (ListNode*)malloc(sizeof(ListNode));//遍历原链表与x比较大小// x的尾插进入大链表 x的尾插进入小链表ListNode* pcur pHead;while(pcur) //等价于pcur ! NULL{if(pcur-val x){ //尾插到小链表lessTail-next pcur;lessTail lessTail-next;}else { //尾插到大链表greaterTail-next pcur;greaterTail greaterTail-next;}pcur pcur-next;}//将大链表的尾结点的next置为空greaterTail-next NULL;//让大小链表首尾相连lessTail-next greaterHead-next;ListNode* ret lessHead-next;free(lessHead);free(greaterHead);lessHead greaterHead NULL;return ret;}
};
5、链表的回文结构
【代码】
class PalindromeList
{
public:
ListNode* findMidNode(ListNode* phead)
{//使用快慢指针寻找中间结点ListNode* slow phead;ListNode* fast phead;while(fast fast-next){slow slow-next;fast fast-next-next;}return slow;
}ListNode* reverseList(ListNode* phead)
{//链表反转ListNode* n1,*n2,*n3;n1 NULL;n2 phead;n3 n2-next;while(n2){n2-next n1;n1 n2;n2 n3;if(n3){n3 n3-next;}}return n1;
}bool chkPalindrome(ListNode* A) {//1、找中间结点ListNode* mid findMidNode(A);//2、根据中间结点将中间结点后的链表反转ListNode* right reverseList(mid);//3、从原链表的头和反转链表比较结点值 (开始时left指头right指尾)ListNode* left A;while(right){if(left-val ! right-val){return false;}left left-next;right right-next;}return true;}
};
未完待续...
