当前位置：网站首页>02_线性表_顺序表
02_线性表_顺序表
2022-07-02 12:00:00 【听*雨声】
2 线性表
线性表：（顺序表，单链表，静态链表，栈，队列，串）
有唯一的头，有唯一的尾；其他任意一个节点都有一个直接前驱和一个直接后继
顺序表： 逻辑相邻物理也相邻（类似一维数组）但是和数组有区别
顺序表与数组的区别：
数组只支持2个操作：向数组中放数据，从数组中取数据，一维数组是一个特殊的顺序表
顺序表支持多种操作：插入，删除…
问题： 向顺序表中插入数据需要挪动其位置后的数据，但是如何判断其位置后有没有数据
普通解决方法： C语言中只能判断变量中是否有值，不能判断是否是有效值；
(1) ’ \0’ 是字符串结束的标志，故只能用来判断字符串
(2) arr[i] ! = 0 ;若用此方法，则’ 0 '表示无效值，数组中不能存放有效值 ‘ 0 ’
正确解决方法： 此时需要人为的加入一个标记：定义一个计算器，记录有效数据的个数
2.1 顺序表：适合查询
2.1.1 定长顺序表
//顺序表，固定长度：非常简单，但是不实用
typedef struct SQList//把一种数据类型起一种新的别名为SQList
{
int elem[10];//存放数据，固定长度为10
int length;//有效数据的个数;此时插入数据时物理位置必须连续，无论插入多少个数据,length始终为一个数字，故空间复杂度为O(1);
//若插入数据时不连续，则每插入一个数据都要有标记。此时空间复杂度为O（n）;
}SQList,
*PSQList;//结构体指针：
//等价于 typedef struct SQList* PSQList;结构体指针起个别名叫PSQList
//初始化
void InitSqList(PSQList ps)//PSQList==SQList *
{
assert(ps != nullptr);//断言只在Debug模式下有效：Debug是程序员开发版本，有调试信息
if (ps == nullptr) //在Release模式下依然有效：Release是发行版本，代码优化过，编译器自动删除了所有调试信息
{
return;
}
ps->length = 0;//有效数据个数为0，故不需要将数组中10个元素初始化为0；
}
//判断被插入数组是否满
static bool IsFul(PSQList ps)
{
return ps->length == 10;
}
//在ps顺序表的pos位置标插入数据val
//插入的数据必须左边连续
void Insert(PSQList ps, int pos, int val)
{
assert(ps != nullptr);//断言只在Debug模式下有效：Debug是程序员开发版本，有调试信息
if (ps == nullptr) //在Release模式下依然有效：Release是发行版本，代码优化过，编译器自动删除了所有调试信息
{
return ;
}
if (pos<0 || pos>ps->length|| IsFul(ps))
{
return ;
}
//移动后面的数据
for (int i = ps->length - 1;i >= pos;i--)
{
ps->elem[i + 1] = ps->elem[i];
}
//插入新的数据
ps->elem[pos] = val;
//有效数据个数+1；
ps->length += 1;
}
//输出顺序表
void Show(PSQList ps)
{
for (int i = 0;i < ps->length;++i)
{
printf("%d", ps->elem[i]);
printf(" ");
}
printf("\n");
}
//判空
bool IsEmpty(PSQList ps)
{
return ps->length == 0;
/*if (ps->length == 0) { return true; }*/
}
//在ps中查找第一个key,找到了返回下标，没有找到返回-1
int Search(PSQList ps, int key)
{
for (int i = 0;i < ps->length;i++)
{
if (key == ps->elem[i])
{
return i;
}
return -1;
}
}
//在ps中查找第一个key,找到了返回下标，没有找到返回-1
int Search(PSQList ps, int key)
{
/*for (int i = 0;i < ps->length;i++) { if (key == ps->elem[i]) { return i; } return -1; }*/
/*int pos = -1; int i = 0; while (i < ps->length && key != ps->elem[i]) { i++; } if (i < ps->length) { pos = i; } return pos;*/
int pos = ps->length - 1;
while (pos>=0 && key != ps->elem[pos])
{
--pos;
}
return pos;
}
//删除pos位置的值
bool DelPos(PSQList ps, int pos)
{
//判断pos位置是否合法
if (pos < 0 || pos >= ps -> length)
{
return false;
}
//将后面的数据前移
//for (int i = pos;i < ps->length;i++)
for (int i = pos;i < ps->length-1;i++)
{
ps->elem[i] = ps->elem[i + 1];//遇见i+1需要考虑越界
}
ps->length--;
return true;
}
//删除第一个val值
bool DelVal(PSQList ps, int val)
{
int i = Search(ps, val);
if (i < 0)
{
return false;
}
return DelPos(ps, i);
}
//返回key的前驱下标，如果不存在返回-1；
int GetPrio(PSQList ps, int key)
{
int i = Search(ps, key);
if (i <= 0)//注意头没有前驱
{
return-1;
}
return i - 1;
}
//返回key的后继下标，如果不存在返回-1；
int GetNext(PSQList ps, int key)
{
int i = Search(ps, key);
if (i< 0 || i==ps->length - 1)//注意尾巴也没有后继
{
return-1;
}
return i + 1;
}
//清空数据
void Clear(PSQList ps)
{
ps->length = 0;
}
//销毁整个内存(动态内存)
void Destory(PSQList ps)
{
Clear(ps);//此例子没有开辟动态内存
}
2.1.2 不定长顺序表
类型改变如下：
顺序表冒泡排序
代码优化：若数据本身就有序，直接退出循环
//顺序表，长度不固定（容量满了可以自动增长）
typedef struct DSQList//把一种数据类型起一种新的别名为SQList
{
int* elem;//动态内存的地址，因为用malloc,所以返回就是一个地址，想存一个整型值，数组存放整型值，所以返回一个整型的指针
//书上定义的是ElemType*elem;目的是为了解决泛型（int，char...)
//C语言解决泛型用：函数指针；C++解决泛型用：模板
int length;//有效数据的个数;
int listsize;//总容量
}DSQList,
* DPSQList;//结构体指针：
//等价于 typedef struct DSQList* DPSQList;结构体指针起个别名叫DPSQList
//初始化,动态创建初始容量
void InitDSqList(DPSQList ps)
{
assert(ps != nullptr);
if(ps==nullptr)
{
return;
}
ps->elem = (int*)malloc(INIT_SIZE * sizeof(int));//对比STL中容器的初始化为0
ps->length = 0;//有效数据个数
ps->listsize = INIT_SIZE;//总容量
}
//判断被插入数组是否满
static bool IsFul(DPSQList ps)//内部使用不对外提供服务故为静态函数
{
return ps->length == INIT_SIZE;
}
//容量增长函数，容量变为原来的2倍（STL中有可能是2倍或1.5倍）
//1.5倍更好。因为当前面的空间释放之后，后面重新申请空间时可以利用到前面释放的空间
// 10 15 23 35 53 ... 当第2次扩容申请23个空间时就可以利用前面释放的10+15=25个空间（如果空间连续的话）
//10 20 40 ... 如果扩容2倍，前面释放的空间无法重新利用
static bool Inc(DPSQList ps)
{
ps->elem = (int*)realloc(ps->elem, ps->listsize * 2 * sizeof(int));
assert(ps->elem != NULL);
ps->listsize *= 2;
//ps->length;不变
return true;
}
//在ps顺序表的pos位置标插入数据val
bool Insert(DPSQList ps, int pos, int val)
{
if (pos<0 || pos> ps->length)
{
return false;
}
if (IsFul(ps))
{
Inc(ps);
}
//移动后面的数据
for (int i = ps->length - 1;i >=pos;i--)
{
ps->elem[i + 1] = ps->elem[i];
}
//插入新的有效数据
ps->elem[pos] = val;
//有效数据个数+1
ps->length++;
return true;
}
//判空
bool IsEmpty(DPSQList ps)
{
return ps->length == 0;
}
//在ps中查找第一个key,找到了返回下标，没有找到返回-1
int Search(DPSQList ps, int key)
{
for (int i = 0;i < ps->length;i++)
{
if (key == ps->elem[i])
{
return i;
}
}
return -1;
}
//删除pos位置的值
bool DelPos(DPSQList ps, int pos)
{
//判断pos位置是否合法
if (pos < 0 || pos >= ps->length)
{
return false;
}
//将后面的数据前移
//for (int i = pos;i < ps->length;i++)
for (int i = pos;i < ps->length - 1;i++)
{
ps->elem[i] = ps->elem[i + 1];//遇见i+1需要考虑越界
}
ps->length--;
return true;
}
//删除第一个val值
bool DelVal(DPSQList ps, int val)
{
int i = Search(ps, val);
if (i < 0)
{
return false;
}
return DelPos(ps, i);
}
//删除所有val值
bool Del_All_Val(PDSQList ps, int val)
{
int i, j = 0;
while (j < ps->length)
{
if (ps->elem[j] != val)
{
ps->elem[i] = ps->elem[j];
++i;
}
++j;
}
ps->length = i;
}
//返回key的前驱下标，如果不存在返回-1；
int GetPrio(DPSQList ps, int key)
{
int i = Search(ps, key);
if (i <= 0)//注意头没有前驱
{
return-1;
}
return i - 1;
}
//返回key的后继下标，如果不存在返回-1；
int GetNext(DPSQList ps, int key)
{
int i = Search(ps, key);
if (i < 0 || i == ps->length - 1)//注意尾巴也没有后继
{
return-1;
}
return i + 1;
}
//输出顺序表
void Show(DPSQList ps)
{
for (int i = 0;i < ps->length;++i)
{
printf("%d", ps->elem[i]);
printf(" ");
}
printf("\n");
}
//清空数据
void Clear(DPSQList ps)
{
ps->length = 0;
}
//销毁整个内存
void Destory(DPSQList ps)
{
free(ps->elem);
ps->elem = NULL;//ps->elem==(*ps).elem
ps->length = 0;
ps->listsize = 0;
ps = NULL;//无效代码
}
ps = NULL;为何为无效代码
因为将 ps 置空，仅仅改变了ps指向，并没有解引用（* ps）,所以指针 elem 指向的顺序表并没有销毁
顺序表的特点：
1.插入数据的时间复杂度是O（n);如果是尾插时间复杂度是O（1）
for (int i = ps->length - 1;i >=pos;i--)
{
ps->elem[i + 1] = ps->elem[i];
}
2.删除数据的时间复杂度是O（n);如果是尾删时间复杂度为O（1）
3.通过下标访问数据，时间复杂度为O（1）
4.简单
边栏推荐
- taobao. trade. Get (get some information of a single transaction), Taobao store order interface, Taobao oauth2.0 interface, Taobao R2 interface code docking and sharing
- C语言实现N皇后问题
- Arithmetic operations and related exercises in C language
- SQL 后计算的利器 SPL
- Tmall product details interface (APP, H5 end)
- 华为面试题： 没有回文串
- CDN 在游戏领域的应用
- Mfc a dialog calls B dialog function and passes parameters
- 05_队列
- TiDB跨数据中心部署拓扑
猜你喜欢
随机推荐
tmall. product. schema. Get (product information acquisition schema acquisition), Taobao store upload commodity API interface, Taobao commodity publishing interface, Taobao commodity upload API interf
MFC A对话框调用B对话框函数并传参
【题解】Educational Codeforces Round 82
LeetCode 209. Minimum length subarray
Topology architecture of the minimum deployment of tidb cluster
Advanced C language (learn malloc & calloc & realloc & free in simple dynamic memory management)
Map介绍
LeetCode - 搜索二维矩阵
[noi simulation] Elis (greedy, simulation)
N皇后问题的解决
taobao. logistics. dummy. Send (no logistics delivery processing) interface, Taobao store delivery API interface, Taobao order delivery interface, Taobao R2 interface, Taobao oau2.0 interface
07_哈希
Introduction to mathjax (web display of mathematical formulas, vector)
C ＃ delay, start the timer in the thread, and obtain the system time
TiDB 环境与系统配置检查
HUSTPC2022
C code audit practice + pre knowledge
如何用 Sysbench 测试 TiDB
LeetCode_字符串_简单_412.Fizz Buzz
kibana 基础操作