合肥建设管理学院网站,wordpress允许评论,建筑工程网络计划,江西网站建设哪家好文章目录 一、什么是线性表1. 什么是顺序表动态开辟空间和数组的问题解释LeetCode-exercise 2. 什么是链表2.1链表的分类2.2常用的链表结构及区别2.3无头单向非循环链表的实现2.4带头双向循环链表的实现2.5循序表和链表的区别LeetCode-exercise 3. 快慢指针LeetCode-exercise 一… 文章目录 一、什么是线性表1. 什么是顺序表动态开辟空间和数组的问题解释LeetCode-exercise 2. 什么是链表2.1链表的分类2.2常用的链表结构及区别2.3无头单向非循环链表的实现2.4带头双向循环链表的实现2.5循序表和链表的区别LeetCode-exercise 3. 快慢指针LeetCode-exercise 一、什么是线性表 概念线性表linear list是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构常见的线性表顺序表、链表、栈、队列、字符串…。线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构上并不一定是连续的线性表在物理上存储时通常以数组和链式结构的形式存储。 关于为什么物理结构上并不一定是连续的可以看我的另外一篇文章【c语言】动态内存管理 1. 什么是顺序表 概念 首先顺序表是线性表其中之一其次顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。在数组上完成数据的增删查改。 顺序表一般可以分为 静态顺序表使用定长数组存储元素。 a.静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了空间开多了浪费开少了不够用。所以现实中基本都是使用动态顺序表根据需要动态的分配空间大小所以下面我们实现动态顺序表。 b. 那我们在学习数据结构之前肯定学习了C语言C语言的题目大多是以IO的形式进行调试的而我们学数据结构的题目大多是以接口的形式进行调试的。 2. 动态顺序表使用动态开辟的数组存储。 接口的实现 #pragma once
// SeqList.h
#include stdio.h
#include assert.h
#include stdlib.h
// 顺序表的动态存储
typedef int SLDataType;
typedef struct SeqList
{SLDataType* a; // 指向动态开辟的数组[a是array的意思]-----关于这里动态开辟和数组的问题见下面解释int size ; // 有效数据个数int capicity ; // 容量空间的大小
}SeqList;
// 基本增删查改接口
// 顺序表初始化void SeqListInit(SeqList* ps);
// 检查空间如果满了进行增容
void SeqListCheckCapacity(SeqList* ps);
// 顺序表尾插
void SeqListPushBack(SeqList* ps, SLDateType x);
// 顺序表尾删
void SeqListPopBack(SeqList* ps);
// 顺序表头插
void SeqListPushFront(SeqList* ps, SLDateType x);
// 顺序表头删
void SeqListPopFront(SeqList* ps);
// 顺序表查找
int SeqListFind(SeqList* ps, SLDateType x, int begin);
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLDateType x);
// 顺序表删除pos位置的值
void SeqListErase(SeqList* ps, int pos);
// 顺序表销毁
void SeqListDestroy(SeqList* ps);
// 顺序表打印
void SeqListPrint(SeqList* ps);#define _CRT_SECURE_NO_WARNINGS 1
//SeqList.c
#include SeqList.h
//动态顺序表
void SeqListInit(SeqList* ps)
{assert(ps);ps-a NULL;ps-size 0;ps-capacity 0;
}void SeqListCheckCapacity(SeqList* ps)
{assert(ps);if (ps-size ps-capacity){int newCapacity ps-capacity 0 ? 4 : ps-capacity * 2;SLDateType* tmp (SLDateType*)realloc(ps-a, newCapacity*sizeof(SLDateType));if (tmp NULL){perror(realloc fail);exit(-1);}ps-a tmp;ps-capacity newCapacity;}
}void SeqListPushBack(SeqList* ps, SLDateType x)
{ //assert(ps);//SLCheckCapacity(ps);//ps-a[ps-size] x;//因为顺序表的数据存放要连续//ps-size;SeqListInsert(ps, ps-size ,x);}
void SeqListPopBack(SeqList* ps)
{//assert(ps);//assert(ps-size 0);//ps-a[ps-size - 1] 0;//ps-size--;SeqListErase(ps, ps-size - 1);
}
void SeqListPushFront(SeqList* ps, SLDateType x)
{//assert(ps);//SLCheckCapacity(ps);从前往后挪动数据 -- 再在前面插入数据//int end ps-size - 1;//while (end 0)//{// ps-a[end 1] ps-a[end];// end--;//}//ps-a[0] x;//ps-size;SeqListInsert(ps, 0, x);}
void SeqListPopFront(SeqList* ps)
{//assert(ps);//assert(ps-size 0);//int begin 1;//while (begin ps-size )//{// ps-a[begin - 1] ps-a[begin];// begin;//}//ps-size--;SeqListErase(ps, 0);}
int SeqListFind(SeqList* ps, SLDateType x ,int begin){assert(ps);for (int i begin; i ps-size; i){if (ps-a[i] x){return 1;}}return -1;
}
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLDateType x)
{assert(ps);assert(pos 0 pos ps-size);SLCheckCapacity(ps);int end ps-size - 1;while (end pos){ps-a[end 1] ps-a[end];end--;}ps-a[pos] x;ps-size;}
void SeqListErase(SeqList* ps, int pos)
{assert(ps);assert(pos 0 pos ps-size);int begin pos 1;while (begin ps-size){ps-a[begin - 1] ps-a[begin];begin;}ps-size--;
}
void SeqListDestroy(SeqList* ps)
{assert(ps);if (ps-a ! NULL){free(ps-a);ps-a NULL;ps-size 0;ps-capacity 0;}
}
void SeqListPrint(SeqList* ps)
{assert(ps);for (int i 0; i ps-size; i){printf(%d , ps-a[i]);}printf(\n);}动态开辟空间和数组的问题解释 [ ]运算符是C语言几乎最高优先级的运算符。[ ]运算符需要两个操作数一个指针类型一个整数。标准的写法是这样的a[int]。这样编译器会返回 *(aint) 的值。 a[int] 就等于 *(a int)。平时static开辟的空间是存在静态区而在函数中定义使用的数组是存在栈区而malloc动态开辟空间返回地址解决了静态数组而需要实时更改数组大小以及一系列的问题。关于malloc动态内存管理可以看我之前写的文章 【c语言】动态内存管理 LeetCode-exercise 原地移除数组中所有的元素val要求时间复杂度为O(N)空间复杂度为O(1)。 2. 什么是链表 概念首先链表是线性表之一其次链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。 2.1链表的分类 单向或者双向 带头或者不带头 循环或者非循环 2.2常用的链表结构及区别 那么组合起来呢2 ^ 3 8所以总共有 8 种链表结构。但是常用的链表结构呢主要有两种无头单向非循环链表和带头双向循环链表 区别 a.无头单向非循环链表结构简单一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。 b. 带头双向循环链表结构最复杂一般用在单独存储数据。实际中使用的链表数据结构都是带头双向循环链表。另外这个结构虽然结构复杂但是使用代码实现以后会发现结构会带来很多优势实现反而简单了后面我们代码实现了就知道了。 2.3无头单向非循环链表的实现
//#pragma once
#include stdio.h
#include stdlib.h
#include assert.h
// slist.h// 1、无头单向非循环链表增删查改实现
typedef int SLTDateType;
typedef struct SListNode
{SLTDateType data;struct SListNode* next;
}SListNode;
// 动态申请一个结点
SListNode* BuySListNode(SLTDateType x);
//节点的连接
SListNode* CreateSList(int n);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos);// 单链表的销毁
void SListDestroy(SListNode** plist);SListNode* BuySListNode(SLTDateType x)
{SListNode* newnode (SListNode*)malloc(sizeof(SListNode));//if (newnode NULL){perror(malloc fail);exit(-1);}newnode-data x;newnode-next NULL;//申请节点先保证 这个指针不是野指针 初始化return newnode;
}
//SListNode* plist CreateSList(5);
SListNode* CreateSList(int n)//最后phead地址传给CreateSList
{SListNode* phead NULL,*ptail NULL;for (int i 0; i n; i){SListNode* newnode BuySListNode(i);if (phead NULL){ptail phead newnode;}else{ptail-next newnode;ptail newnode;}}return phead;
}// 单链表打印
//SListPrint(plist);
void SListPrint(SListNode* plist)//此时的plist是 上面传回来的 phead
{SListNode * cur plist;while (cur ! NULL){printf(%d-, cur-data);cur cur-next;//下一个节点的地址}printf(NULL\n);//表示链表遍历结束标识没有下一个节点
}
// 单链表尾插--------最后一个节点连接新节点
//SListPushBack(plist , 100);
void SListPushBack(SListNode** pplist, SLTDateType x)//传递过来的是指针变量的地址
{//这里要改变的是实参所以要用** plist如果这里传的是plist则无法通过改变形参来达到改变实参SListNode* newnode BuySListNode(x);if (*pplist NULL)//如果前面没有开辟 节点链表为空{//这里就是解引用访问*plist 为访问指针pplist*pplist newnode;}else{SListNode* tail *pplist;while (tail-next)//直到最后tail-next节点结束位置获取到tail的地址{tail tail-next;}tail-next newnode;//给tail后面 新开辟节点地址 实现尾插}
}// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{ //如果pplist为NULL 不用检查 不影响SListNode* newnode BuySListNode(x);newnode-next *pplist;*pplist newnode;//生成新的 头地址指针
}
// 单链表的尾删
//SListPopBack(pplist);
void SListPopBack(SListNode** pplist)
{ //暴力的检查 assert(*pplist);//排除 链表为空时 还继续一直删除if ((*pplist)-next NULL){free(*pplist);*pplist NULL;//此时又实参与由形参的问题}else{SListNode* tail *pplist;while (tail-next-next){tail tail-next;}free(tail-next);//tail NULL; tail是个局部变量 tail-next NULL;}
}// 单链表头删
void SListPopFront(SListNode** pplist)
{ //链表为空 不用删assert(*pplist);SListNode* next (*pplist)-next;//*和-都是解引用 优先级确定不了所以要加括号free(*pplist);*pplist next;
}
// 单链表查找
//SListNode* pos SListFind(plist , 3);
//
SListNode* SListFind(SListNode* plist, SLTDateType x)
{SListNode* cur plist;while (cur){if (cur-data x){return cur;}cur cur-next;}return NULL;
}
// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入
void SListInsertAfter(SListNode* pos, SLTDateType x)
{assert(pos);SListNode* newnode BuySListNode(x);newnode-next pos-next;pos-next newnode;
}
void SListEraseAfter(SListNode* pos)
{assert(pos);if (pos-next NULL){return; }else{//free(pos-next);//pos-next pos-next-next;//如果pos的next被释放则其值为随机值但原本应该存放next的next的地址SListNode* nextNode pos-next;pos-next nextNode-next;free(nextNode);}
} // 单链表的销毁
void SListDestroy(SListNode** plist)
{SListNode* cur *plist;while (cur){SListNode* next cur-next;free(cur);cur next;}*plist NULL;
}2.4带头双向循环链表的实现
//.h
// 2、带头双向循环链表增删查改实现
#pragma once#include stdio.h
#include assert.h
#include stdlib.h// 带头双向循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{LTDataType _data;struct ListNode* _next;struct ListNode* _prev;
}ListNode;//创建一个节点
ListNode* BuyListNode(LTDataType x);// 创建返回链表的头结点.
ListNode* ListCreate();
// 双向链表销毁
void ListDestory(ListNode* pHead);
// 双向链表打印
void ListPrint(ListNode* pHead);
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* pHead);
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* pHead);
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);#define _CRT_SECURE_NO_WARNINGS 1#include DList.hListNode* BuyListNode(LTDataType x)
{ListNode* node (ListNode*)malloc(sizeof(ListNode));if (node NULL){perror(malloc fail);exit(-1);}node-_data x;node-_next NULL;node-_prev NULL;return node;}
// 创建返回链表的头结点.
ListNode* ListCreate()
{ListNode* phead BuyListNode(-1);phead-_next phead;phead-_prev phead;return phead;
}
// 双向链表销毁
void ListDestory(ListNode* pHead)
{assert(pHead);ListNode* cur pHead-_next;while (cur ! pHead){ListNode* ne_nextxt cur-_next;free(cur);cur ne_nextxt;}free(pHead);//phead NULL;}
// 双向链表打印
void ListPrint(ListNode* pHead)
{assert(pHead);ListNode* cur pHead-_next;printf(guard\n);while (cur ! pHead) {printf(%d, cur-_data);cur cur-_next;}printf(\n);}
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* newnode BuyListNode(x);ListNode* tail pHead-_prev;tail-_next newnode;newnode-_prev tail;newnode-_next pHead;pHead-_prev newnode;
}
// 双向链表尾删
void ListPopBack(ListNode* pHead)
{assert(pHead);assert(pHead-_next ! pHead); // 空ListNode* tail pHead-_prev;ListNode* tailPrev tail-_prev;tailPrev-_next pHead;pHead-_prev tailPrev;free(tail);
}
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{assert(pHead);/*LTNode* newnode BuyListNode(x);newnode-next phead-next;phead-next-prev newnode;phead-next newnode;newnode-prev phead;*/ListNode* newnode BuyListNode(x);ListNode* first pHead-_next;// phead newnode first // 顺序无关pHead-_next newnode;newnode-_prev pHead;newnode-_next first;first-_prev newnode;
}
// 双向链表头删
void ListPopFront(ListNode* pHead)
{assert(pHead);assert(pHead-_next ! pHead); // 空/*LTNode* first phead-next;LTNode* second first-next;free(first);phead-next second;second-prev phead;*/ListErase(pHead-_next);
}
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* cur pHead-_next;while (cur ! pHead){if (cur-_data x){return cur;}cur cur-_next;}return NULL;
}
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* _prev pos-_prev;ListNode* newnode BuyListNode(x);// prev newnode pos_prev-_next newnode;newnode-_prev _prev;newnode-_next pos;pos-_prev newnode;
}
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{assert(pos);ListNode* _prev pos-_prev;ListNode* _next pos-_next;free(pos);_prev-_next _next;_next-_prev _prev;
}
2.5循序表和链表的区别 LeetCode-exercise 1.删除链表中等于给定值 val 的所有结点 3. 快慢指针
LeetCode-exercise 给你一个链表的头节点 head 判断链表中是否有环。 方法一暴力解法判断引用地址是否重复 这道题最简单的做法就是在遍历链表的同时记录下每一个节点在遍历过程中不停的判断当前节点是不是之前已经记录过的节点。如果遍历时发现有和记录下来的节点重复的则证明是环形链表 如果整个链表能够遍历完也没有重复节点则证明不是环形链表。 方法二快慢指针解法简单原理就是用两个指针一个快一个慢。 慢指针走一步快指针走两步。 如果存在环那么快指针始终可以追上慢指针即两个指针一定会出现指向同一个节点的状态就好像赛跑中被套圈。因为是判断链表是否有环所以我们考虑使用追及相遇来解决。我们使用快慢指针fast和slow初始化它们都为头结点然后让slow一次走一步fast一次走两步。为什么肯定能追击上呢 如果存在环当slow进环时fast肯定在环里此时两者相差N的距离这个时候它们开始追及。因为fast的步长是slow的两倍所以它们之间的距离每走一次是减小1的它们之间的距离逐渐逼近这样slow和fast一定可以相遇。当它们距离减小到0时即它们相遇这个时候就可以确定链表肯定有环。 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
bool hasCycle(struct ListNode *head) {struct ListNode* slow head, *fast head;while(fast fast-next)//如果不带环fast会为NULLfast不为NULL那么slow肯定不为NULLfast-next不为NULL{slow slow-next;fast fast-next-next;if(slow fast)return true;}return false;
}
