电子商务网站建设与推广,电商入门视频教程免费,长春网站建设推荐网诚传媒,企业用的邮箱是什么邮箱线性表
单链表 单链表的定义 由于顺序表的插入删除操作需要移动大量的元素#xff0c;影响了运行效率#xff0c;因此引入了线性表的链式存储——单链表。单链表通过一组任意的存储单元来存储线性表中的数据元素#xff0c;不需要使用地址连续的存储单元#xff0c;因此它…线性表
单链表 单链表的定义 由于顺序表的插入删除操作需要移动大量的元素影响了运行效率因此引入了线性表的链式存储——单链表。单链表通过一组任意的存储单元来存储线性表中的数据元素不需要使用地址连续的存储单元因此它不要求在逻辑上相邻的两个元素在物理位置上也相邻。 单链表的特点 1.单链表不要求逻辑上相邻的两个元素在物理位置上也相邻因此不需要连续的存储空间。 2.单链表是非随机的存储结构即不能直接找到表中某个特定的结点。查找某个特定的结点时需要从表头开始遍历依次查找。 **单链表操作**#includeiostream
using namespace std;typedef struct LNode{int data;struct LNode *next;
}LNode,*LinkList;//初始化
void InitList(LinkList L){L(LNode *)malloc(sizeof(LinkList));L-nextNULL;
}//头插法建表
LinkList HeadInsert(LinkList L){InitList(L);int x;while(cinx){LNode *s(LNode *)malloc(sizeof(LNode));s-datax;s-nextL-next;L-nexts;}return L;
}//尾插法建表
LinkList TailInsert(LinkList L){InitList(L);LNode *s,*rL;int x;while(cinx){s(LNode *)malloc(sizeof(LNode));s-datax;r-nexts;rs;}r-nextNULL;return L;
} //输出表中元素
void PrintList(LinkList L){LNode *pL-next;while(p!NULL){coutp-data ;pp-next;}
} //求单链表的长度
int Length(LinkList L){LNode *p L-next;int len 0;while(p!NULL){len;p p-next;}return len;
}//按值查找查找x在L中的位置
LNode *LocateElem(LinkList L, int x){LNode *p L-next;while(p!NULLp-data!x){p p-next;}return p;
}//按位查找查找在单链表L中第i个位置的结点
LNode *GetElem(LinkList L, int i){int j1;LNode *p L-next;if(i0){return L;}if(i1){return NULL;}while(p!NULLji){p p-next;j;}return p;
}//判空操作
void Empty(LinkList L){if(L-next NULL){coutL is nullendl;}else{coutL is not nullendl;}
}//将x插入到单链表L的第i个位置上
void Insert(LinkList L, int i, int x){LNode *p GetElem(L,i-1);LNode *s (LNode *)malloc(sizeof(LNode));s-data x;s-next p-next;p-next s;
}//删除操作:将单链表中的第i个结点删除
void Delete(LinkList L, int i){if(i0||iLength(L)){cout数据有误; return ;}LNode *p GetElem(L,i-1);LNode *q p-next;p-next q-next;free(q);
}int main(){**自定义补充**return 0;
}双链表
循环链表
栈、队列、数组
树
图
查找
排序 排序算法可以分为内部排序和外部排序其中内部排序有插入排序直接插入排序、折半插入排序、希尔排序、交换排序冒泡排序、快速排序、选择排序简单选择排序、堆排序、归并排序、基数排序外部排序有多路归并排序。 插入排序 插入排序是一种简单直观的排序方法其基本思想是每次将一个待排序的记录按其关键字大小插入前面已排好序的子序列直到全部记录插入完成。由插入排序的思想可以引申出三个重要的排序算法直接插入排序、折半插入排序和希尔排序。 直接插入排序 要将元素 L(i)插入已有序的子序列 L[1…i-1]需要执行以下操作为避免混下面用L[ ]表示一个表而用 L( )表示一个元素: 1)查找出L(i)在L[l…i-1]中的插入位置k。 2)将L[k…i-1]中的所有元素依次后移一个位置。 3)将L(i)复制到L(k)。 #includeiostream
using namespace std;void InsertSort(int a[],int len){int temp,i,j;for(i1;ilen;i){if(a[i]a[i-1]){tempa[i];for(ji-1;tempa[j];j--){a[j1]a[j]; }a[j1]temp;}}
} int main(){int a[]{1,3,4,2,6,5,9,8,7};int lsizeof(a)/sizeof(int);InsertSort(a,l);for(int i0;il;i){couta[i] ;} return 0;
}时间复杂度On^2 最好情况下On 空间复杂度O1 稳定性由于每次插入元素时总是从后向前先比较再移动所以不会出现相同元素相对位置发生变化的情况即直接插入排序是一个稳定的排序方法。 适用性直接插入排序算法适用于顺序存储和链式存储的线性表。为链式存储时可以从前往后查找指定元素的位置。 折半插入排序 从直接插入排序算法中不难看出每趟插入的过程中都进行了两项工作1.从前面的有序子表中查找出待插入元素应该被插入的位置2.给插入位置腾出空间将待插入元素复制到表中的插入位置。注意到在该算法中总是边比较边移动元素。下面将比较和移动操作分离即先折半查找出元素的待插入位置然后统一地移动待插入位置之后的所有元素。当排序表为顺序表时可以对直接插入排序算法做如下改进由于是顺序存储的线性表所以查找有序子表时可以用折半查找来实现。确定待插入位置后就可统一地向后移动元素。 #includeiostream
using namespace std;void InsertSort(int a[],int len){int temp,low,high,mid;for(int i1;ilen;i){tempa[i];low0,highi-1;while(lowhigh){mid(lowhigh)/2;if(a[mid]temp){highmid-1;}else{lowmid1;}}for(int ji-1;jhigh1;j--){a[j1]a[j];}a[high1]temp;}
}int main(){int a[]{1,3,4,2,6,5,9,8,7};int lsizeof(a)/sizeof(int);InsertSort(a,l);for(int i0;il;i){couta[i] ;}return 0;
}从上述算法中不难看出折半插入排序仅减少了比较元素的次数约为 O(nlogn)该比较次数与待排序表的初始状态无关仅取决于表中的元素个数n而元素的移动次数并未改变它依赖于待排序表的初始状态。因此折半插入排序的时间复杂度仍为 O(n^2)但对于数据量不很大的排序表折半插入排序往往能表现出很好的性能。折半插入排序是一种稳定的排序方法。 希尔排序 希尔排序的基本思想是先将待排序表分割成若干形如L[i,id,i2d,i3d…ikd]的“特殊”子表即把相隔某个“增量”的记录组成一个子表对各个子表分别进行直接插入排序当整个表中的元素已呈“基本有序”时再对全体记录进行一次直接插入排序。 希尔排序的过程如下先取一个小于n 的步长 d1把表中的全部记录分成d1组所有距离为d1的倍数的记录放在同一组在各组内进行直接插入排序然后取第二个步长 d2d1重复上述过程直到所取到的di1即所有记录已放在同一组中再进行直接插入排序由于此时已经具有较好的局部有序性故可以很快得到最终结果。 #includeiostream
using namespace std;void InsertSort(int a[],int len){for(int dlen/2;d1;dd/2){int temp,i,j;for(id1;ilen;i){if(a[i]a[i-d]){tempa[i];for(ji-d;j0tempa[j];j-d){a[jd]a[j]; }a[jd]temp;}}}
} int main(){int a[]{1,3,4,2,6,5,9,8,7};int lsizeof(a)/sizeof(int); InsertSort(a,l);for(int i0;il;i){couta[i] ;}return 0;
}空间效率仅使用了常数个辅助单元因而空间复杂度为 O(1)。 时间效率由于希尔排序的时间复杂度依赖于增量序列的函数这涉及数学上尚未解决的难题所以其时间复杂度分析比较困难。当n在某个特定范围时希尔排序的时间复杂度约为On^1.3。在最坏情况下希尔排序的时间复杂度为 O(n^2)。 稳定性当相同关键字的记录被划分到不同的子表时可能会改变它之间的相对次序因此希尔排序是一种不稳定的排序方法。 适用性希尔排序算法仅适用于线性表为顺序存储的情况。 交换排序 所谓交换是指根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置。基于交换的排序算法很多主要有冒泡排序和快速排序。 冒泡排序 冒泡排序的基本思想是从后往前或从前往后两两比较相邻元素的值若为逆序即A[i-1]A[i]则交换它们直到序列比较完。我们称它为第一趟冒泡结果是将最小的元素交换到待排序列的第一个位置或将最大的元素交换到待排序列的最后一个位置关键字最小的元素如气泡一般逐渐往上“漂浮”直至“水面”或关键字最大的元素如石头一般下沉至水底。下一趟冒泡时前一趟确定的最小元素不再参与比较每趟冒泡的结果是把序列中的最小元素或最大元素放到了序列的最终位置…这样最多做n-1趟冒泡就能把所有元素排好序。 #includeiostream
using namespace std;void BubbleSort(int a[],int len){for(int i0;ilen-1;i){for(int j0;jlen-i;j){if(a[j1]a[j]){swap(a[j1],a[j]);}}}
} int main(){int a[]{1,3,4,2,6,5,9,8,7};int lsizeof(a)/sizeof(int); BubbleSort(a,l);for(int i0;il;i){couta[i] ;}return 0;
}算法改进由上述的示例数组元素为1,3,4,2,6,5,9,8,7可知其第二趟的结果1,2,3,4,5,6,7,8,9已经有序后面再进行排序其实是重复动作。因此当某一趟的结果已经有序时表示所给序列已经有序不必要再进行下一趟排序。 void BubbleSort(int a[],int len){for(int i0;ilen-1;i){bool flagfalse; for(int j0;jlen-i;j){if(a[j1]a[j]){swap(a[j1],a[j]);flagtrue;}}if(flagfalse){return ;}}
} 空间效率仅使用了常数个辅助单元因而空间复杂度为 O(1)。 时间效率当初始序列有序时显然第一趟冒泡后flag依然为false本趟冒泡没有元素交换从而直接跳出循环比较次数为n-1移动次数为0从而最好情况下的时间复杂度为O(n)当初始序列为逆序时需要进行n-1趟排序第i趟排序要进行n-i次关键字的比较而且每次比较后都必须移动元素3次来交换元素位置。这种情况下的时间复杂度为 O(n^2)其平均时间复杂度也为 O(n^2)。 稳定性:由于ij且a[i]a[j]时不会发生交换因此冒泡排序是一种稳定的排序方法。 快速排序 快速排序的基本思想是基于分治法的在待排序表 L[l…n]中任取一个元素pivot作为枢轴或基准通常取首元素通过一趟排序将待排序表划分为独立的两部分L[1…k-1]和L[kl…n]使得L[l…k-1]中的所有元素小于pivotL[kl…n]中的所有元素大于等于pivot则pivot放在了其最终位置 L(k)上这个过程称为一趟快速排序或一次划分。然后分别递归地对两个子表重复上述过程直至每部分内只有一个元素或空为止即所有元素放在了其最终位置上。 #includeiostream
using namespace std;void QuickSort(int a[],int low,int high){int ilow,jhigh,pivota[low];if(lowhigh){return ;}while(ij){while(a[j]pivotij){j--;}a[i]a[j];while(a[i]pivotij){i;}a[j]a[i];}a[i]pivot;QuickSort(a,low,i-1);QuickSort(a,i1,high);
}int main(){int a[]{1,3,4,2,6,5,9,8,7};int lsizeof(a)/sizeof(int); QuickSort(a,0,l-1);for(int i0;il;i){couta[i] ;}return 0;
}**快速排序另一种写法**int Partition(int a[],int low,int high){int pivota[low];while(lowhigh){while(a[high]pivotlowhigh){high--;}a[low]a[high];while(a[low]pivotlowhigh){low;}a[high]a[low];}a[low]pivot;return low;
}void QuickSort(int a[],int low,int high){if(lowhigh){int pivotpos Partition(a,low,high);QuickSort(a,low,pivotpos-1);QuickSort(a,pivotpos1,high);}
}选择排序 选择排序的基本思想是每一趟如第i趟在后面n-i1i1,2,…,n-1个待排序元素中选取关键字最小的元素作为有序子序列的第i个元素直到第n-1趟做完待排序元素只剩下1个就不用再选了。选择排序主要有简单选择排序和堆排序。 简单选择排序 简单选择排序算法的思想假设排序表为L[1…n]第i趟排序即从L[i…n]中选择关键字最小的元素与L(i)交换每一趟排序可以确定一个元素的最终位置这样经过n-1趟排序就可使得整个排序表有序。 #includeiostream
using namespace std;void SelectSort(int a[],int len){for(int i0;ilen-1;i){int mini;for(int ji1;jlen;j){if(a[j]a[min]){minj;}}if(min!i){swap(a[i],a[min]);}}
} int main(){int a[]{1,3,4,2,6,5,9,8,7};int lsizeof(a)/sizeof(int); SelectSort(a,l);for(int i0;il;i){couta[i] ;}return 0;
}空间效率仅使用常数个辅助单元故空间效率为0(1)。 时间效率从上述代码中不难看出在简单选择排序过程中元素移动的操作次数很少不会超过3(n-1)次最好的情况是移动0次此时对应的表已经有序但元素间比较的次数与序列的初始状态无关始终是 n(n-1)/2 次因此时间复杂度始终是 O(n^2)。 稳定性在第i趟找到最小元素后和第 i个元素交换可能会导致第i个元素与其含有相同关键字元素的相对位置发生改变。例如表L{2,2,1}经过一趟排序后L{1,2,2}最终排序序列也是L{1,2,2}显然2与2的相对次序已发生变化。因此简单选择排序是一种不稳定的排序方法。 堆排序 堆的定义如下n个关键字序列L[1…n]称为堆当且仅当该序列满足 1.L(i)L(2i)且L(i)L(2i1)或 2.L(i)L(2i)且L(i)(2i1) 1 i n/2 堆排序的思路很简单首先将存放在L[1…n]中的n个元素建成初始堆由于堆本身的特点以大顶堆为例堆顶元素就是最大值。输出堆顶元素后通常将堆底元素送入堆顶此时根结点已不满足大顶堆的性质堆被破坏将堆顶元素向下调整使其继续保持大顶堆的性质再输出堆顶元素。如此重复直到堆中仅剩一个元素为止。可见堆排序需要解决两个问题1.如何将无序序列构造成初始堆2.输出堆顶元素后如何将剩余元素调整成新的堆 堆排序的关键是构造初始堆。n个结点的完全二叉树最后一个结点是第n/2个结点的孩子。对第n/2个结点为根的子树筛选对于大根堆若根结点的关键字小于左右孩子中关键字较大者则交换使该子树成为堆。之后向前依次对各结点n/2-1,…,1为根的子树进行筛选看该结点值是否大于其左右子结点的值若不大于则将左右子结点中的较大值与之交换交换后可能会破坏下一级的堆于是继续采用上述方法构造下一级的堆直到以该结点为根的子树构成堆为止。反复利用上述调整堆的方法建堆直到根结点。 #includeiostream
using namespace std;void HeapAdjust(int a[],int k,int len){a[0]a[k];for(int i2*k;ilen;i*2){if(ilena[i]a[i1]){i; }if(a[0]a[i]){break;}else{a[k]a[i];ki;}}a[k]a[0];
}void BuildMaxHeap(int a[],int len){for(int ilen/2;i0;i--){HeapAdjust(a,i,len);}
}void HeapSort(int a[],int len){BuildMaxHeap(a,len);for(int ilen;i1;i--){swap(a[i],a[1]);HeapAdjust(a,1,i-1);}
} int main(){int b[]{1,3,4,2,6,5,9,8,7};int a[100],lsizeof(b)/sizeof(int);for(int i0;il;i){a[i1]b[i];}HeapSort(a,l);for(int i1;il;i){couta[i] ;}return 0;
} 空间效率仅使用了常数个辅助单元所以空间复杂度为 O(1)。 时间效率建堆时间为 O(n)之后有 n-1次向下调整操作每次调整的时间复杂度为 O(h)故在最好、最坏和平均情况下堆排序的时间复杂度为O(nlogn)。 稳定性:进行筛选时有可能把后面相同关键字的元素调整到前面所以堆排序算法是一种不稳定的排序方法。例如表L{1,2,2}构造初始堆时可能将2交换到堆顶此时L{2,1,2},最终排序序列为 L{1,2,2}显然2与2的相对次序已发生变化。 归并排序 归并排序是比较稳定的排序方法。它的基本思想是把待排序的元素分解成两个规模大致相等的子序列。如果不易分解将得到的子序列继续分解直到子序列中包含的元素个数为1。因为单个元素的序列本身就是有序的此时便可以进行合并从而得到一个完整的有序序列。 分治算法 归并排序其实就是一种分治算法那么在了解归并排序之前我们先来看看什么是分治算法。在算法设计中我们引入分而治之的策略称为分治算法其本质就是将一个大规模的问题分解为若干个规模较小的相同子问题分而治之。 分治算法解题 1.分解将要解决的问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题。 2.治理求解各个子问题。由于各个子问题与原问题形式相同只是规模较小而已而当子问题划分得足够小时就可以用简单的方法解决。 3.合并按原问题的要求将子问题的解逐层合并构成原问题的解。 归并排序解题步骤 步骤一首先将待排序的元素分成大小大致相同的两个序列。 步骤二再把子序列分成大小大致相同的两个子序列。 步骤三如此下去直到分解成一个元素停止这时含有一个元素的子序列都是有序的。 步骤四进行合并操作将两个有序的子序列合并为一个有序序列如此下去直到所有的元素都合并为一个有序序列。 数据模拟下面我将以序列49152430261820进行图解 1、初始化i lowj mid1mid (lowhigh)/2 申请一个辅助数组 b int b[high-low1];
int i low, j mid 1, k 0; 2、现在比较 a[i] 和 b[j]将较小的元素放在 b 数组中相应的指针向后移动直到 i mid 或者 jhight 时结束。 while (i mid j high) {if (a[i] a[j]) {b[k] a[i]; } else {b[k] a[j];}
}进行第一次比较 a[i]4 和 a[j]2将较小的元素 2 放入数组 b 中jk如下图 进行第二次比较 a[i]4 和 a[j]6将较小的元素放 4 入数组 b 中ik如下图 进行第三次比较 a[i]9 和 a[j]6将较小的元素放 6 入数组 b 中jk如下图 进行第四次比较 a[i]9 和 a[j]18将较小的元素放 9 入数组 b 中ik如下图 进行第五次比较 a[i]15 和 a[j]18将较小的元素放 15 入数组 b 中ik如下图 进行第六次比较 a[i]24 和 a[j]18将较小的元素放 18 入数组 b 中jk如下图 进行第七次比较 a[i]24 和 a[j]20将较小的元素放 20 入数组 b 中jk如下图 此时jhight 了while循环结束但 a 数组还剩下元素imid可直接放入 b 数组就可以了。如下图所示 while (i mid){ // j 序列结束将剩余的 i 序列补充在 b 数组中 b[k] a[i];
}
while (j high){ // i 序列结束将剩余的 j 序列补充在 b 数组中 b[k] a[j];
}现在比较 a[i] 和 b[j] 将较小的元素放在 b 数组中相应的指针向后移动直到 i mid 或者 j hight 时结束。 while (i mid j high) {if (a[i] a[j]) {b[k] a[i]; } else {b[k] a[j];}
}现在将 b 数组的元素赋值给 a 数组再将 b 数组销毁即可。 for (int i low; i hight; i) { //将 b 数组的值传递给数组 aa[i] b[k];
}
delete[]b; // 辅助数组用完后将其的空间进行释放销毁3、递归的形式进行归并排序 void MergeSort(int a[ ],int low,int high){if(lowhigh){int mid(lowhigh)/2;MergeSort(a,low,mid);MergeSort(a,mid1,high);Merge(a,low,mid,high);}
}**完整代码**
#includeiostream
using namespace std;void Merge(int a[],int low,int mid,int high){int *bnew int[high-low1]; //用 new 申请一个辅助函数int i low, j mid 1, k 0; // k为 b 数组的小标while (i mid j high){if (a[i] a[j]){b[k] a[i]; //按从小到大存放在 b 数组里面}else{b[k] a[j];}}while (i mid){ // j 序列结束将剩余的 i 序列补充在 b 数组中 b[k] a[i];}while (j high){ // i 序列结束将剩余的 j 序列补充在 b 数组中 b[k] a[j];}k 0; //从小标为 0 开始传送for (int i low; i high; i){ //将 b 数组的值传递给数组 aa[i] b[k];}delete []b; //销毁
}void MergeSort(int a[],int low,int high){if(lowhigh){int mid(lowhigh)/2;MergeSort(a,low,mid);MergeSort(a,mid1,high);Merge(a,low,mid,high);}
}int main(){int a[]{1,3,4,2,6,5,9,8,7};int lsizeof(a)/sizeof(int);MergeSort(a,0,l-1);for(int i0;il;i){couta[i] ;}return 0;
}基数排序
