当前位置:首页 » 《休闲阅读》 » 正文

《C++》解密--顺序表

22 人参与  2024年12月18日 08:02  分类 : 《休闲阅读》  评论

点击全文阅读


目录

​编辑

一、线性表

二、顺序表

1、概念

2、顺序表和数组区别

三、分类

四、动态顺序表的实现

1、创立文件

2、顺序表的初始化和销毁

【SeqList.h】

【SeqList.c】

【test.c】

3、打印

【SeqList.c】

【test.c】

4、判断空间是否足够

【SeqList.c】

5、头插

【SeqList.h】

【SeqList.c】

【test.c】

6、尾插

【SeqList.h】

【SeqList.c】

【test.c】

7、头删

【SeqList.h】

【SeqList.c】

【test.c】

8、尾删

【SeqList.h】

【SeqList.c】

【test.c】

10、在指定位置之前插入数据

【SeqList.h】

【SeqList.c】

【test.c】

11、删除指定位置的数据

【SeqList.h】

【SeqList.c】

【test.c】

12、查找

【SeqList.h】

【SeqList.c】

【test.c】

13、整体代码

五、顺序表算法题

【示例1】

【示例2】

【示例3】

【思考】


一、线性表

           线性表是n个具有相同特性的数据元素的有限序列。                                                                           线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈......

      线性表在【逻辑上】是线性结构,也就是连续的一条直线;                                                            但在【物理结构】上不一定是连续的,线性表在物理上储存时,通常是数组、链式结构等形式。

二、顺序表

1、概念

     顺序表是线性表的一种。

     顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般采用数组存储。

     【顺序表在逻辑结构、物理结构上都是线性的】

2、顺序表和数组区别

    顺序表的底层结构是数组,对数组的封装,实现了常用的增删改查等接口。

三、分类

1、静态顺序表

2、动态顺序表

四、动态顺序表的实现

1、创立文件

2、顺序表的初始化和销毁

【SeqList.h】
#pragma once#include<stdio.h>#include<stdlib.h>#include<assert.h>//定义动态顺序表结构typedef int SLDatatype;struct SeqList{SLDatatype* arr;int capacity;   //空间大小int size;      //有效数据个数};typedef struct SeqList SL;  //给结构体SeqList改个名字SL//顺序表的初始化void SLInit(SL* ps);//顺序表的销毁void SLDestory(SL* ps);
【SeqList.c】
#define _CRT_SECURE_NO_WARNINGS 1#include<stdio.h>#include"SeqList.h"//顺序表的初始化void SLInit(SL* ps){ps->arr = NULL;ps->size = ps->capacity = 0;}//顺序表的销毁void SLDestory(SL* ps){if (ps->arr)  //相当于ps->arr != NULL{free(ps->arr);}ps->arr = NULL;ps->size = ps->capacity = 0;}
【test.c】
#include"SeqList.h"void SLtest01(){SL s;SLInit(&s);SLDestory(&s);}int main(){SLtest01();return 0;}

3、打印

【SeqList.c】
void SLPrint(SL* ps){for (int i = 0; i < ps->size; i++){printf("%d ", ps->arr[i]);}printf("\n");}
【test.c】
#include"SeqList.h"void SLtest01(){SL s;SLInit(&s);SLPrint(&s);SLDestory(&s);}int main(){SLtest01();return 0;}

4、判断空间是否足够

【SeqList.c】
//判断空间是否充足void SLCheckCapacity(SL* ps){//判断空间是否充足if (ps->size == ps->capacity){//增容  //0*2=0//若capacity为0,给个默认值,否则x2倍int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;SLDatatype* tmp = (SLDatatype*)realloc(ps->arr, newCapacity * sizeof(SLDatatype));if (tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity *= newCapacity;}}

5、头插

【SeqList.h】
//头插void SLPushFront(SL* ps,SLDatatype x);
【SeqList.c】
//头插void SLPushFront(SL* ps, SLDatatype x){assert(ps);//判断空间是否足够SLCheckCapacity(ps);//插入操作//数据整体后移一位for (int i = ps->size; i > 0; i--){ps->arr[i] = ps->arr[i - 1];}//下标为0的位置空出来了ps->arr[0] = x;ps->size++;}
【test.c】
#include"SeqList.h"void SLtest01(){SL s;SLInit(&s);//头插SLPushFront(&s, 1);SLPushFront(&s, 2);SLPushFront(&s, 3);SLPushFront(&s, 4);SLPrint(&s);   //4 3 2 1SLDestory(&s);}int main(){SLtest01();return 0;}

6、尾插

【SeqList.h】
//尾插void SLPushBack(SL* ps,SLDatatype x);
【SeqList.c】
//尾插void SLPushBack(SL* ps, SLDatatype x){//方式1if (ps == NULL){return;}//方式2   粗暴--断言//assert(ps); //等价于assert(ps != NULL)SLCheckCapacity(ps);ps->arr[ps->size++] = x;}
【test.c】
//尾插SLPushBack(&s, 1);SLPushBack(&s, 2);SLPushBack(&s, 3);SLPushBack(&s, 4);SLPrint(&s);   //1 2 3 4

7、头删

【SeqList.h】
//头删void SLPopFront(SL* ps);
【SeqList.c】
//头删(将第一个以后的数据整体向前挪动一位)void SLPopFront(SL* ps){assert(ps);assert(ps->size);for (int i = 0; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];  //i = size-2}ps->size--;}
【test.c】
//头删SLPopFront(&s);SLPrint(&s);   //2 3 4

8、尾删

【SeqList.h】
//尾删void SLPopBack(SL* ps);
【SeqList.c】
//尾删void SLPopBack(SL* ps){assert(ps);assert(ps->size);//ps->arr[ps->size-1] = -1  //多余了ps->size--;}
【test.c】
//尾删SLPopBack(&s);SLPrint(&s);  //1 2 3

10、在指定位置之前插入数据

【SeqList.h】
//在指定位置之前插入数据void SLInsert(SL* ps, SLDatatype x, int pos);
【SeqList.c】
//在指定位置之前插入数据//空间足够才可以直接插入void SLInsert(SL* ps, SLDatatype x, int pos){assert(ps);//           头插         尾插assert(pos >= 0 && pos <= ps->size);//检查空间是否足够,是否可以直接插入SLCheckCapacity(ps);//pos及之后的数据整体向后移动一位for (int i = ps->size; i > pos; i--){ps->arr[i] = ps->arr[i - 1];  //pos <-- pos+1}ps->arr[pos] = x;ps->size++;}
【test.c】
//SLInsert(&s, 11, 0);  //头插11//SLPrint(&s);     //11 1 2 3 4//SLInsert(&s, 22, s.size);  //尾插22//SLPrint(&s);    //1 2 3 4 22SLInsert(&s, 33, 2);  //指定位置后插入(2后面插入33)SLPrint(&s);      //1 2 33 3 4

11、删除指定位置的数据

【SeqList.h】
//删除指定位置的数据void SLErase(SL* ps, int pos);
【SeqList.c】
//删除指定位置的数据void SLErase(SL* ps, int pos){assert(ps);assert(pos >= 0 && pos < ps->size);//还有很多限制:如顺序表不可以为空...//pos之后的数据整体向前挪动一位(一个一个挪)for (int i = pos; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];  //size-1 --> size-2}ps->size--;}
【test.c】
//指定位置删除//SLErase(&s, 0);  //删除下标为0的那个数据//SLPrint(&s);  //2 3 4SLErase(&s, s.size-1);  //删除最后一个有效数据SLPrint(&s);  //1 2 3

12、查找

【SeqList.h】
//查找数据int SLFind(SL* ps, SLDatatype x);
【SeqList.c】
//查找数据int SLFind(SL* ps, SLDatatype x){assert(ps);for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x){return 1;}}//没有找到,就返回一个无效下标return -1;}
【test.c】
//查找数据int find = SLFind(&s, 21);    if (find < 0){printf("顺序表中不存在它!\n");}else{printf("find it!\n");}

13、整体代码

【SeqList.h】

#pragma once#include<stdio.h>#include<stdlib.h>#include<assert.h>//定义动态顺序表结构typedef int SLDatatype;struct SeqList{SLDatatype* arr;int capacity;   //空间大小int size;      //有效数据个数};typedef struct SeqList SL;  //给结构体SeqList改个名字SL//顺序表的初始化void SLInit(SL* ps);//顺序表的销毁void SLDestory(SL* ps);//头插void SLPushFront(SL* ps,SLDatatype x);//尾插void SLPushBack(SL* ps,SLDatatype x);//头删void SLPopFront(SL* ps);//尾删void SLPopBack(SL* ps);//在指定位置之前插入数据void SLInsert(SL* ps, SLDatatype x, int pos);//删除指定位置的数据void SLErase(SL* ps, int pos);//查找数据int SLFind(SL* ps, SLDatatype x);

【SeqList.c】

#include<stdio.h>#include"SeqList.h"//顺序表的初始化void SLInit(SL* ps){ps->arr = NULL;ps->size = ps->capacity = 0;}//顺序表的销毁void SLDestory(SL* ps){if (ps->arr)  //相当于ps->arr != NULL{free(ps->arr);}ps->arr = NULL;ps->size = ps->capacity = 0;}//打印void SLPrint(SL* ps){for (int i = 0; i < ps->size; i++){printf("%d ", ps->arr[i]);}printf("\n");}//判断空间是否充足void SLCheckCapacity(SL* ps){//判断空间是否充足if (ps->size == ps->capacity){//增容  //0*2=0//若capacity为0,给个默认值,否则x2倍int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;SLDatatype* tmp = (SLDatatype*)realloc(ps->arr, newCapacity * sizeof(SLDatatype));if (tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity *= newCapacity;}}//头插void SLPushFront(SL* ps, SLDatatype x){assert(ps);//判断空间是否足够SLCheckCapacity(ps);//插入操作//数据整体后移一位for (int i = ps->size; i > 0; i--){ps->arr[i] = ps->arr[i - 1];}//下标为0的位置空出来了ps->arr[0] = x;ps->size++;}//尾插void SLPushBack(SL* ps, SLDatatype x){//方式1if (ps == NULL){return;}//方式2   粗暴--断言//assert(ps); //等价于assert(ps != NULL)SLCheckCapacity(ps);ps->arr[ps->size++] = x;}//头删(将第一个以后的数据整体向前挪动一位)void SLPopFront(SL* ps){assert(ps);assert(ps->size);for (int i = 0; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];  //i = size-2}ps->size--;}//尾删void SLPopBack(SL* ps){assert(ps);assert(ps->size);//ps->arr[ps->size-1] = -1  //多余了ps->size--;}//在指定位置之前插入数据//空间足够才可以直接插入void SLInsert(SL* ps, SLDatatype x, int pos){assert(ps);//           头插         尾插assert(pos >= 0 && pos <= ps->size);//检查空间是否足够,是否可以直接插入SLCheckCapacity(ps);//pos及之后的数据整体向后移动一位for (int i = ps->size; i > pos; i--){ps->arr[i] = ps->arr[i - 1];  //pos <-- pos+1}ps->arr[pos] = x;ps->size++;}//删除指定位置的数据void SLErase(SL* ps, int pos){assert(ps);assert(pos >= 0 && pos < ps->size);//还有很多限制:如顺序表不可以为空...//pos之后的数据整体向前挪动一位(一个一个挪)for (int i = pos; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];  //size-1 --> size-2}ps->size--;}//查找数据int SLFind(SL* ps, SLDatatype x){assert(ps);for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x){return 1;}}//没有找到,就返回一个无效下标return -1;}

【test.c】

#include"SeqList.h"void SLtest01(){SL s;SLInit(&s);//头插/*SLPushFront(&s, 1);SLPushFront(&s, 2);SLPushFront(&s, 3);SLPushFront(&s, 4);SLPrint(&s);  */ //4 3 2 1//尾插SLPushBack(&s, 1);SLPushBack(&s, 2);SLPushBack(&s, 3);SLPushBack(&s, 4);SLPrint(&s);   //1 2 3 4//头删/*SLPopFront(&s);SLPrint(&s);*/   //2 3 4尾删//SLPopBack(&s);//SLPrint(&s);  //1 2 3//指定位置之后插入//SLInsert(&s, 11, 0);  //头插11//SLPrint(&s);     //11 1 2 3 4//SLInsert(&s, 22, s.size);  //尾插22//SLPrint(&s);    //1 2 3 4 22//SLInsert(&s, 33, 2);  //指定位置后插入(2后面插入33)//SLPrint(&s);      //1 2 33 3 4//指定位置删除//SLErase(&s, 0);  //删除下标为0的那个数据//SLPrint(&s);  //2 3 4//SLErase(&s, s.size-1);  //删除最后一个有效数据//SLPrint(&s);  //1 2 3//查找数据int find = SLFind(&s, 21);    if (find < 0){printf("顺序表中不存在它!\n");}else{printf("find it!\n");}SLDestory(&s);}int main(){SLtest01();return 0;}

五、顺序表算法题

【示例1】

int removeElement(int* nums, int numsSize, int val) {  int src = 0;    int dst = 0;  while(src < numsSize)  {    if(nums[src] == val)    {        src++;    }    else    {        nums[dst] = nums[src];        dst++;        src++;    }  }  //此时dst指向的位置就是要返回的有效个数  return dst;}
【示例2】

int removeDuplicates(int* nums, int numsSize) {    int dst = 0;    int src = dst + 1;    while(src <numsSize)    {       //nums[dst]  nums[src]       //相同(重复)src++       //不相同,dst++,赋值,src++        if(nums[dst] != nums[src])        {            dst++;            nums[dst] = nums[src];        }                    src++;           }    return dst+1;}
【示例3】

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {    int l1 = m-1;    int l2 = n-1;    int l3 = m+n-1;    while(l1 >= 0 && l2 >= 0)    {      if(nums1[l1]>nums2[l2])      {        nums1[l3] = nums1[l1];        l3--;        l1--;      }        else        {            //l1==l2要么l2>l1            nums1[l3] = nums2[l2];            l3--;            l2--;        }    }    //跳出while循环有两种情况    //要么l1<0 ; 要么l2<0    while(l2>=0)    {        nums1[l3] = nums2[l2];         l3--;        l2--;    }}
【思考】

感谢观看,未完待续...


点击全文阅读


本文链接:http://zhangshiyu.com/post/202838.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新文章

  • 她的记忆停留在了最爱初恋的那年许欣柔楚临川完本_她的记忆停留在了最爱初恋的那年(许欣柔楚临川)
  • 全书浏览假千金的实习生男友霸占我办公室,我反手让他们倾家荡产(顾家明)_假千金的实习生男友霸占我办公室,我反手让他们倾家荡产(顾家明)全书结局
  • 童养夫让我给他的新欢出修复费(林嘉芝林思雅)_童养夫让我给他的新欢出修复费林嘉芝林思雅
  • 全文资助生女婿让我给他白月光付三千万月子中心钱(宋清玉宋雅)列表_全文资助生女婿让我给他白月光付三千万月子中心钱
  • 碎在时光里的谎言喻景宴秦明月完本_碎在时光里的谎言(喻景宴秦明月)
  • 旧爱剜心吻成灰席鄢之岑秋全书免费旧爱剜心吻成灰席鄢之岑秋全书免费
  • 结婚六年丈夫不碰我谁知儿子亲爹是寡头(纪清言傅司砚),结婚六年丈夫不碰我谁知儿子亲爹是寡头
  • 老公想换掉我的男胎,我笑他自不量力(宋薇于继业)_老公想换掉我的男胎,我笑他自不量力宋薇于继业
  • 给太子下了噬心蛊后,皇后找上门(小夭赵劼)全书浏览_给太子下了噬心蛊后,皇后找上门全书浏览
  • 豪门绝嗣!带球跑的夫人回来了!(谢长宴慕清杳)_豪门绝嗣!带球跑的夫人回来了!谢长宴慕清杳
  • 完美身材(李朵林之晴)_完美身材李朵林之晴
  • 离婚后,我和快穿系统绑定(白意秋陈荣周立慧)_离婚后,我和快穿系统绑定(白意秋陈荣周立慧)

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1