2.数据结构顺序表（自留笔记）

文章目录

一.静态顺序表：长度固定
二.动态顺序表
- ==1.下面证明原地扩容和异地扩容代码如下：==
- ==2.下面是写一段Print，打印数字看看：==
- ==3.头插==
- ==4.尾删==
- ==5.头删==
- ==6.越界一定会报错吗==
- ==7.下标插入==
- ==8.下标删除==
- ==9.查找数字==
- ==10.应用：利用顺序表写一个菜单==

顺序表就是数组，特殊要求：顺序表只能从头开始连续存储，分为静态存储和动态存储

一.静态顺序表：长度固定

在这里插入图片描述
里面是静态数组，size表示存的多少个数据。
弊端：不知道需要多少，N给小了不够用，N给大了浪费。

二.动态顺序表

在这里插入图片描述
尾插法，size++

扩容时用到realloc
在这里插入图片描述

区分realloc原地扩容和异地扩容
原地扩容返回的是和原来一样的地址
异地扩容返回的是和原来不同的地址，并且把原来的空间free掉

http://t.csdnimg.cn/CKsJs

在这里插入图片描述

先用malloc开辟空间。
注意：在使用malloc函数之前我们一定要计算字节数，malloc开辟的是用户所需求的字节数大小的空间。

写个程序通过地址变化判断是原地扩还是异地扩时
在这里插入图片描述

1.下面证明原地扩容和异地扩容代码如下：

❗SeqList.h如下：

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//作用是为一种数据类型定义一个新名字。这里的数据类型包括内部数据类型（int,char等）和自定义的数据类型（struct等）
typedef int SLDataType;//定义顺序表
typedef struct SeqList
{//定义指针SLDataType* a;//记录有效数据个数int size;//记录空间大小int capacity;}SL;//初始化函数
void SLInit(SL* ps1);
void SLDestroy(SL* ps1);
void SLCheckCapacity(SL* ps1);//写一个公共逻辑
//尾插
void SLPushBack(SL* ps1, SLDataType x);

❗SeqList.c如下：

#include"SeqList1.h"
void SLInit(SL* ps1)
{assert(ps1);ps1->a = NULL;ps1->size = 0;ps1->capacity = 0;
}void SLDestroy(SL* ps1)
{assert(ps1);if (ps1->a!=NULL){free(ps1->a);ps1->a = NULL;ps1->size = 0;ps1->capacity = 0;}
}void SLCheckCapacity(SL* ps1)//写一个公共逻辑
{assert(ps1);if (ps1->size == ps1->capacity){int newCapacity = ps1->capacity == 0 ? 4 : ps1->capacity * 2;//如果ps1->capacity == 0为真则newCapacity=4，如果为假，则newCapacity=ps1->capacity*2SLDataType* tmp = (SLDataType*)realloc(ps1->a, sizeof(SLDataType) * newCapacity);if (tmp == NULL){perror("realloc fail");return;}ps1->a = tmp;ps1->capacity = newCapacity;}
}
void SLPushBack(SL* ps1, SLDataType x)
{SLCheckCapacity(ps1);//调用ps1->a[ps1->size] = x;ps1->size++;}