赞
踩
零个或多个数据元素 组成的有限序列,除了头部元素和尾部元素之外,其他的所有元素只有一个前驱元素(前面那个数据)
线性表包括数据结构中的:数组,单链表,双链表 ,循环链表(尾部可以指向头部)等
也是一个线性表
用数组描述数据元素物理存储的连续性,实际上就是一个数组的操作
理解为数组的操作即可 ---> 用来封装数组的常规操作(增、删、改、查)
采用顺序存储描述的线性表叫做顺序表
要知道顺序表的长相,抽象结构体代码的根本
45只有一个前驱元素(45前面只有一个元素12)
对前驱节点 | 前驱元素无任何限制
深度的概念:看( )个数,不是看元素个数
了解广义表的表示方式:
空表 E = (); 深度0
L = (a,b) 或 L (a,b);两个元素的表,表示:表中有a,b两个元素,长度为2 深度1
A = (x,L) = (x,(a,b));广义表中还有一个表叫L表,A表中有2个元素(其中一个为正常的数据,称为原子,另一个还是一个表) 深度2
B = (A,L) = ((a,b),(a,b,c));其他的组合情况:有两个子表,A表中有2个元素,L表中有3个元素 深度2
用数组描述
maxSize:记录最大容量的变量
curSize:记录当前元素个数的变量(容器)
(顺序表中的定义需要有一个一级指针去做内存申请):定义一个数组指针 | 动态内存申请变成一个数组
sqlist.h
- #pragma once
- #include <stdio.h>
- #include <stdlib.h>
- #include <assert.h> //断言|用于判空处理|申请内存可能失败
- #define MAX 10 //最大元素个数
- typedef int DataType; //数据通用性处理|可以给数据类型定义别名
- //结构体的抽象->抽象长相
- enum INFO {OK=1,ERROR=-1}; //枚举变量类型 -1:错误信息
- typedef struct
- {
- DataType* dataMemory; //一级指针动态内存申请变成一维数组
- int maxSize; //最大元素个数->容量
- int curSize; //当前元素个数
- }Sqlist,*LPSqlist; //结构体的别名|结构体指针别名
用一个指针表示一个结构体变量,返回的是一个指针,创建过程就是初始化数据,有几个数据成员就给几个数据成员初始化即可
任何一种结构都是一个结构体变量,只是表达方式不一样
- //声明
- LPSqlist createSqlist(int maxSize);
-
- //实现
- LPSqlist createSqlist(int maxSize) //参数:最大值
- {
- //创建过程,就是初始化数据->动态内存申请把指针变成变量
- LPSqlist sqlist = (LPSqlist)malloc(sizeof(Sqlist));
- assert(sqlist); //断言处理
- //给变量中的东西初始化
- sqlist->curSize = 0;
- sqlist->maxSize = maxSize;
- //指针变成一个数组->数组的内存需要二次申请
- sqlist->dataMemory = (DataType*)malloc(sizeof(DataType)*maxSize);
- assert(sqlist->dataMemory);
- return sqlist;
- }
- //sqlist中的一级指针也需要做内存申请 申请为数组从而可以存放多个数据
- //声明
- int size(LPSqlist sqlist); //获取当前的元素个数(或者返回bool类型)
- int empty(LPSqlist sqlist); //判断是否为空
-
- //实现
- int size(LPSqlist sqlist)
- {
- if (sqlist == NULL) //大前提:sqlist不等于空
- return ERROR;
- return sqlist->curSize;
- }
- int empty(LPSqlist sqlist)
- {
- if (sqlist == NULL)
- return ERROR;
- return sqlist->curSize==0; //判断当前的curSize是不是为0
- }
参数:获取哪个顺序表中的元素
注意:表不能为空 & 下标是否满足要求
下标不合格的情况:当前元素个数 curSize < 要访问的下标 index
- //声明
- DataType getData(LPSqlist sqlist, int index);
-
- //实现
- //参数: LPSqlist sqlist:获取哪个顺序表中的元素 int index:通过下标去获取元素
- DataType getData(LPSqlist sqlist, int index)
- {
- if (sqlist == NULL||sqlist->curSize==0) //为空(短路)
- {
- printf("sqlist is empty,unable to get......\n"); //错误提示 无法获取
- return ERROR;
- }
- if (sqlist->curSize < index) //下标是否满足要求?
- {
- printf("index is invalid,unable to get......\n"); //错误提示 invalid无效
- return ERROR;
- }
- //注意:index是第几个元素 第1个元素,第2个元素...没有第0个元素的概念
- return sqlist->dataMemory[index-1]; //下标正确 直接返回
- }
元素不存在顺序,直接插到顺序表中即可
参数:插入的顺序表 插入的下标 插入的数据
顺序表的插入操作就是数组的插入操作
数组实现的数据结构,放进去要考虑满的状态(链表不需要),拿出来要考虑空的状态
方案1 (依次交换)
把要插入的元素放在最后面
让最后面的元素一直与前面的元素依次交换到指定的位置
- int insertSqlist(LPSqlist sqlist, int index, DataType data)
- {
- //大前提:无法插入
- if (sqlist == NULL)
- {
- printf("sqlist is empty,unable to insert......\n");
- return ERROR;
- }
- //满的情况:无法插入
- if (sqlist->curSize == sqlist->maxSize)
- {
- printf("sqlist is full,unbale to insert......\n");
- return ERROR;
- }
- //index==0 curSize==0 第一次插入特殊情况需要做判断
- if (index == 0)
- {
- sqlist->dataMemory[sqlist->curSize++] = data; //插入数据 后置++即可
- return OK;
- }
- //index为其他值,看下标是否满足要求 第一次插只能用index == 0的情况
- if (sqlist->curSize < 1 || sqlist->curSize < index)
- {
- printf("index is invalid,unable to insert......\n"); //下标无效 无法做插入
- return ERROR;
- }
- //其他情况正常插入
- int pos = sqlist->curSize; //pos==最后一个下标
- sqlist->dataMemory[pos] = data; //插在最后面 直接把元素插在当前下标下即可
- //调整位置
- while (pos != index)
- { //定义一个temp做交换
- DataType temp = sqlist->dataMemory[pos]; //第5个元素(index[0]-[4])
- sqlist->dataMemory[pos] = sqlist->dataMemory[pos - 1]; //交换pos和pos-1的位置
- sqlist->dataMemory[pos - 1] = temp; //把pos-1的值置为temp
- pos--;
- }
- sqlist->curSize++; //插入成功后curSize++
- }
- /*测试代码 参数:插入的下标 插入的元素 都是在第1个位置插入
- 第一次插入在下标[0]插入0 第一个元素
- 在第1个位置插入1
- 在第1个位置插入2
- 在第4个位置插入444
- ...*/
- LPSqlist sqlist = createSqlist(MAX);
- printf("test insert:\n");
- insertSqlist(sqlist, 0, 0); //0
- insertSqlist(sqlist, 1, 1); //1 0
- insertSqlist(sqlist, 1, 2); //2 1 0
- insertSqlist(sqlist, 1, 3); //3 2 1 0
- insertSqlist(sqlist, 4, 444); //3 2 1 444 0
- printSqlist(sqlist);
方案2 (挪位置)
先挪位置,再做插入 把最后一个元素999挪到curSize的位置,再把77挪到999的位置...
要从后面的元素开始挪(把k-1的值赋给k),如果从前面的元素开始挪,25会把77覆盖
- for (int k = sqlist->curSize; k >= index; k--)
- {
- sqlist->dataMemory[k] = sqlist->dataMemory[k - 1]; //把k-1的值赋给k
- }
- sqlist->dataMemory[index - 1] = data; //插入的第几个元素:在数组下标中一定是index-1
- sqlist->curSize++;
- return OK;
- void printSqlist(LPSqlist sqlist)
- {
- if (sqlist == NULL||sqlist->curSize==0) //两种为空的情况 无法打印
- {
- printf("sqlist is empty,unable to print......\n");
- return;
- }
- //能够打印
- for (int i = 0; i < sqlist->curSize; i++)
- {
- printf("%d\t", sqlist->dataMemory[i]); //打印数组
- }
- printf("\n");
- }
参数:要删除的表 要删除第几个元素(通过序号做删除)
25是要删除的位置,先把77挪到25的位置,再把999挪到77的位置
只是77把25给覆盖了(逻辑上的删除),没有处理999的内存,元素999还在
真正的删除是curSize从5变成了4,把记录大小的curSize做 - - 运算
- int deleteSqlist(LPSqlist sqlist, int index)
- {
- if (sqlist == NULL || sqlist->curSize == 0) //表为空无法删除
- {
- printf("sqlist is empty,unable to delete......\n");
- return ERROR;
- }
- if (sqlist->curSize < index) //判断下标是否满足规则
- {
- printf("index is invalid,unbale to delete......\n");
- return ERROR;
- }
- for (int k = index - 1; k < sqlist->curSize; k++)
- {
- sqlist->dataMemory[k] = sqlist->dataMemory[k + 1]; //把k+1的值挪到k的位置
- }
- sqlist->curSize--; //伪删除
- return OK;
- }
-
- //测试代码
- printf("test delete:\n"); //3 2 1 444 0
- deleteSqlist(sqlist, 4); //3 2 1 0
- printSqlist(sqlist);
- void push_front(LPSqlist sqlist, DataType data) //头部插入
- {
- insertSqlist(sqlist, 1, data); //在第一个位置插入数据
- }
- void push_back(LPSqlist sqlist, DataType data) //尾部插入
- {
- if (sqlist == NULL) //为空无法插入
- {
- printf("sqlist is empty,unable to pushback");
- return;
- }
- if (sqlist->curSize == sqlist->maxSize) //满了也无法做插入
- {
- printf("sqlist is full,unable to pushback");
- return;
- }
- sqlist->dataMemory[sqlist->curSize++] = data; //能够插入 插在最后面 后置++
- }
-
- //测试代码
- printf("test push:\n");
- push_front(sqlist, 666); //666 3 2 1 0
- push_back(sqlist, 999); //666 3 2 1 0 999
- printSqlist(sqlist);
- void pop_front(LPSqlist sqlist) //头部删除
- {
- deleteSqlist(sqlist, 1); //删除第一个位置
- }
- void pop_back(LPSqlist sqlist) //尾部删除
- {
- deleteSqlist(sqlist, sqlist->curSize); //删除最后一个位置
- }
-
- //测试代码
- pop_front(sqlist); //666 3 2 1 0 999
- pop_back(sqlist); //3 2 1 0 999
- printSqlist(sqlist); //3 2 1 0
按数据去查找,返回找到数据的下标
- int searchSqlist(LPSqlist sqlist, DataType data)
- {
- if (sqlist == NULL) //为空无法查找
- {
- printf("sqlist is empty,unable to search......\n");
- return ERROR; //数组下标没有-1
- }
- //遍历数组
- for (int i = 0; i < sqlist->curSize; i++)
- {
- if (sqlist->dataMemory[i] == data) //当前元素==data
- {
- return i; //返回下标
- }
- }
- return ERROR; //没找到返回ERROR
- }
-
- //测试代码
- int pos = searchSqlist(sqlist, 3); //查找元素:3
- printf("pos:%d\n", pos); //输出:元素3在数组下标[0]的位置 pos:0
插入后的序号由元素决定
直接插入元素,不需要根据序号做插入,会自动根据数据做排序
注意是在插入时做排序,不是先插完再排序
- void insert_sort(LPSqlist sqlist, DataType data)
- {
- if (sqlist == NULL) //为空无法插入
- {
- printf("sqlist is empty,unable to insert......\n");
- return;
- }
- if (sqlist->curSize == sqlist->maxSize) //满的情况无法插入
- {
- printf("sqlist is full,unable to insert......\n");
- return;
- }
- if (sqlist->curSize == 0) //直接插入
- {
- sqlist->dataMemory[sqlist->curSize++] = data;
- } //不等于0的情况 直接插在最后面
- /* int pos = sqlist->curSize; */
- sqlist->dataMemory[sqlist->curSize/* pos */] = data;
- for (int k = sqlist->curSize;k > 0; k--) //k 等于最后一个下标 k <= 0 也要退出循环
- {
- if (sqlist->dataMemory[k] < sqlist->dataMemory[k - 1]) //交换
- {
- DataType temp = sqlist->dataMemory[k];
- sqlist->dataMemory[k] = sqlist->dataMemory[k - 1];
- sqlist->dataMemory[k - 1] = temp;
- }
- else
- {
- break; //其他情况:大于|等于的情况 直接break即可
- }
- }
- sqlist->curSize++; //插入成功后++
- }
- //测试代码
- LPSqlist sortSqlist = createSqlist(MAX);
- insert_sort(sortSqlist, 1);
- insert_sort(sortSqlist, 100);
- insert_sort(sortSqlist, 77);
- insert_sort(sortSqlist, -1);
- printSqlist(sortSqlist); //-1 1 1 77 100
- void destroySqlist(LPSqlist* sqlist)
- {
- if (*sqlist == NULL)
- {
- printf("sqlist is empty, unable to destory......\n");
- return;
- }
- free((*sqlist)->dataMemory);
- free(*sqlist);
- *sqlist = NULL;
- }
- //测试代码
- destroySqlist(&sortSqlist);
- destroySqlist(&sqlist);
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。