做财经直播网站,wordpress主题错位,重庆市网站建设,wordpress的ftp设置1.线性表
线性表 #xff08; linear list #xff09; 是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使 用的数据结构#xff0c;常见的线性表#xff1a;顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构#xff0c;也就说是连续的一…1.线性表
线性表 linear list 是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使 用的数据结构常见的线性表顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构上并不一定是连续的 线性表在物理上存储时通常以数组和链式结构的形式存储。 2.顺序表
2.1概念及结构
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。在数组上完成数据的增删查改。
注顺序表只能从头开始连续存储。
顺序表一般可以分为 静态顺序表使用定长数组存储元素 动态顺序表使用动态开辟的数组存储。 我们思考一个问题为什么容量空间不够时候我们经常扩容是进行2倍扩容呢而不是其他倍数或者常数呢 因为2倍扩容相对合适越扩频率越低而且c库里面扩容也是2倍扩容。但是1.5倍扩容或者一倍扩容都可以。
2.2接口实现
2.2.1接口实现代码
静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了空间开多了浪费开少了不够用。所以现实中基本都是使用动态顺序表根据需要动态的分配空间 大小所以下面我们实现动态顺序表:
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.htypedef int SLDataType;//数据类型最好typedef下否则数据类型会有各种变化变化以后所有都得修改typedef struct SeqList
{//int* a;SLDataType* a; //指向动态开辟的数组int size; //有效数据int capacity; //空间容量
}SL;void SLInit(SL* psl);//初始化
void SLDestroy(SL* psl);//释放空间void SLPrint(SL* psl);//打印
void SLCheakCapacity(SL* psl);//检查空间容量是否够用不够则扩容//头尾插入删除
void SLPushBack(SL* psl, SLDataType x);//尾插
void SLPushFront(SL* psl, SLDataType x);//头插
void SLPopBack(SL* psl);//尾删
void SLPopFront(SL* psl);//头删//任意下标位置的插入删除
void SLInsert(SL* psl, int pos, SLDataType x);//插入
void SLErase(SL* psl, int pos);//删除//找到返回下标
//没有找到返回-1
int SLFind(SL* psl, SLDataType x);#includeSeqList.hvoid SLInit(SL* psl)
{psl-a NULL;psl-size 0;psl-capacity 0;
}void SLDestroy(SL* psl)
{assert(psl);if (psl-a ! NULL){free(psl-a);psl-a ! NULL;psl-size 0;psl-capacity 0;}
}void SLPrint(SL* psl)
{assert(psl);for (int i 0; i psl-size ;i){printf(%d , psl-a[i]);}printf(\n);
}void SLCheakCapacity(SL* psl)
{assert(psl);if (psl-size psl-capacity){int newCapacity psl-capacity 0 ? 4 : psl-capacity * 2;SLDataType* tmp (SLDataType*)realloc(psl-a, sizeof(SLDataType) * newCapacity);if (tmp NULL){perror(ralloc fail);return;}psl-a tmp;psl-capacity newCapacity;}
}void SLPushBack(SL* psl, SLDataType x)
{assert(psl);SLCheakCapacity(psl);psl-a[psl-size] x;psl-size;
}void SLPushFront(SL* psl, SLDataType x)
{assert(psl);SLCheakCapacity(psl);int end psl-size - 1;while (end 0){psl-a[end 1] psl-a[end];--end;}psl-a[0] x;psl-size;
}void SLPopBack(SL* psl)
{assert(psl);if (psl-size 0){return;}assert(psl-size 0);psl-size--;
}
void SLPopFront(SL* psl)
{assert(psl);assert(psl-size 0);for (int begin 0; begin psl-size; begin){psl-a[begin] psl-a[begin1];}psl-size--;
}void SLInsert(SL* psl, int pos, SLDataType x)
{assert(psl);assert(pos 0 pos psl-size);//如果等于则是头插尾插SLCheakCapacity(psl);int end psl-size;while (end pos){psl-a[end] psl-a[end - 1];end--;}psl-a[end] x;psl-size;
}//void SLInsert(SL* psl, int pos, SLDataType x)
//{
// assert(psl);
// assert(pos 0 pos psl-size);
//
// SLCheakCapacity(psl);
//
// // 挪动数据
// int end psl-size - 1;
// while (end pos)
// {
// psl-a[end 1] psl-a[end];
// --end;
// }
//
// psl-a[pos] x;
// psl-size;
//}void SLErase(SL* psl, int pos)
{assert(psl);assert(pos 0 pos psl-size);int begin pos;for(;beginpsl-size ;begin){ psl-a[begin] psl-a[begin 1];}psl-size--;
}int SLFind(SL* psl, SLDataType x)
{assert(psl);for (int j 0; j psl-size; j){if (psl-a[j] x){return j;}}return -1;
}#includeSeqList.hvoid TestSL1()
{SL sl;SLInit(sl);SLPushBack(sl, 1);SLPushBack(sl, 2);SLPushBack(sl, 3);SLPrint(sl);SLPushFront(sl, 10);SLPushFront(sl, 20);SLPushFront(sl, 30);SLPrint(sl);SLPopBack(sl);SLPopBack(sl);SLPrint(sl);SLPopFront(sl);SLPopFront(sl);SLPrint(sl);
}void TestSL2()
{SL sl;SLInit(sl);SLPushBack(sl, 1);SLPushBack(sl, 2);SLPushBack(sl, 3);SLPushBack(sl, 4);SLPushBack(sl, 5);SLPrint(sl);SLInsert(sl, 3, 50);SLInsert(sl, 3, 40);SLPrint(sl);SLErase(sl, 5);SLPrint(sl);int pos SLFind(sl, 3);if (pos ! -1){SLErase(sl , pos);}SLPrint(sl);}int main()
{TestSL2();// 越界一定报错吗//int a[10];// 越界读基本不会报错//printf(%d\n, a[10]);//printf(%d\n, a[11]);// 越界写可能会报错//a[10] 1;//a[11] 1;//因为越界的检查是一种抽查行为return 0;
}free错误
1.free位置不对
2.存在越界访问
2.2.2 接口实现思路
SList.c
void SLCheakCapacity(SL* psl)检查空间是否足够若不够则空间为0则开辟4个空间若不为零则将原有的空间的大小乘以2
void SLCheakCapacity(SL* psl)
{assert(psl);if (psl-size psl-capacity){int newCapacity psl-capacity 0 ? 4 : psl-capacity * 2;SLDataType* tmp (SLDataType*)realloc(psl-a, sizeof(SLDataType) * newCapacity);if (tmp NULL){perror(ralloc fail);return;}psl-a tmp;psl-capacity newCapacity;}
} 尾插
void SLPushBack(SL* psl, SLDataType x)先判断psl链表是否为空为空直接结束不为空继续执行。再检查空间是否够用不够则开辟够则把x的值给数组a然后size。
void SLPushBack(SL* psl, SLDataType x)
{assert(psl);SLCheakCapacity(psl);psl-a[psl-size] x;psl-size;
}头插
void SLPushFront(SL* psl, SLDataType x);void SLPushFront(SL* psl, SLDataType x)
{assert(psl);SLCheakCapacity(psl);int end psl-size - 1;while (end 0){psl-a[end 1] psl-a[end];--end;}psl-a[0] x;psl-size;
}思路如下 尾删
void SLPopBack(SL* psl);void SLPopBack(SL* psl)
{assert(psl);if (psl-size 0){return;}assert(psl-size 0);psl-size--;
}头删
void SLPopFront(SL* psl);void SLPopFront(SL* psl)
{assert(psl);assert(psl-size 0);for (int begin 0; begin psl-size; begin){psl-a[begin] psl-a[begin1];}psl-size--;
}任意下标位置的插入
void SLInsert(SL* psl, int pos, SLDataType x);//插入void SLInsert(SL* psl, int pos, SLDataType x)
{assert(psl);assert(pos 0 pos psl-size);//如果等于则是头插尾插SLCheakCapacity(psl);int end psl-size;while (end pos){psl-a[end] psl-a[end - 1];end--;}psl-a[end] x;psl-size;
} 任意下标位置的删除
void SLErase(SL* psl, int pos);//删除void SLErase(SL* psl, int pos)
{assert(psl);assert(pos 0 pos psl-size);int begin pos;for(;beginpsl-size ;begin){ psl-a[begin] psl-a[begin 1];}psl-size--;
} 找下标
//找到返回下标
//没有找到返回-1
int SLFind(SL* psl, SLDataType x);int SLFind(SL* psl, SLDataType x)
{assert(psl);for (int j 0; j psl-size; j){if (psl-a[j] x){return j;}}return -1;
}2.3 数组相关面试题 删除排序数组中的重复项。 26. 删除有序数组中的重复项 - 力扣LeetCode 代码 int removeDuplicates(int* nums, int numsSize)
{int src1;int dst0;while(srcnumsSize){if(nums[src]nums[dst]){src;}else{dst;nums[dst]nums[src];src;}}return dst1;
} 解题思路 合并两个有序数组。 88. 合并两个有序数组 - 力扣LeetCode 代码如下 void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{int j mn - 1;int n1 m - 1;int n2 n - 1;while(n10 n20){if(nums1[n1]nums2[n2]){nums1[j--]nums1[n1--];}else{nums1[j--]nums2[n2--];}}while(n20){nums1[j--]nums2[n2--];}
} 解题思路
2.4 顺序表的问题及思考
问题 OJ链接 1. 中间/头部的插入删除时间复杂度为O(N) 2. 增容需要申请新空间拷贝数据释放旧空间。会有不小的消耗。 3. 增容一般是呈2倍的增长势必会有一定的空间浪费。例如当前容量为100满了以后增容到 200我们再继续插入了5个数据后面没有数据插入了那么就浪费了95个数据空间。 思考如何解决以上问题呢下面给出了链表的结构来看看。 m - 1; int n2 n - 1; while(n10 n20) { if(nums1[n1]nums2[n2]) { nums1[j–]nums1[n1–]; } else { nums1[j–]nums2[n2–]; } } while(n20) { nums1[j–]nums2[n2–]; } }
解题思路[外链图片转存中...(img-Iu1JfGs6-1712583978516)]## 2.4 顺序表的问题及思考问题 OJ链接 1. 中间/头部的插入删除时间复杂度为O(N) 2. 增容需要申请新空间拷贝数据释放旧空间。会有不小的消耗。 3. 增容一般是呈2倍的增长势必会有一定的空间浪费。例如当前容量为100满了以后增容到 200我们再继续插入了5个数据后面没有数据插入了那么就浪费了95个数据空间。 思考如何解决以上问题呢下面给出了链表的结构来看看。
