网站建设移动网络,小型玩具企业网站建设初期阶段任务,快站建站教程,公司网站建设教程目录
线性表顺序表练习 线性表(Linear list)是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构#xff0c;常见的线性表#xff1a;顺序表、链表、栈、队列、字符串。。。
线性表在逻辑上时线性结构#xff0c;是连续的一条直线。但在物理结…目录
线性表顺序表练习 线性表(Linear list)是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构常见的线性表顺序表、链表、栈、队列、字符串。。。
线性表在逻辑上时线性结构是连续的一条直线。但在物理结构上不一定是连续的存储时通常以数组和链式结构的形式存储 2. 顺序表
2.1 概念和结构
顺序表是一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。在数组上完成数据的增删查改
顺序表一般可以分为 静态顺序表使用定长数组存储元素 使用动态开辟的数组 2.2 接口实现
静态顺序表只适用于确定知道存多少数据的场景.静态顺序表的定长数组导致N定大了,空间开多了浪费,开少了不够用.所以现实中基本都是使用动态顺序表,根据需要动态的分配空间大小,所以下面我们实现动态顺序表
头文件
#pragma once
#include stdio.h
顺序表的静态存储
//#define N 7
//typedef int SLDataType;
//
//typedef struct _SeqList
//{
// SLDataType array[N]; //定长数组
// size_t size; //有效数据的个数
//}SeqList;//顺序表的动态存储
typedef int SLDataType;typedef struct _SeqList
{SLDataType *array; //动态开辟的数组size_t size; //有效数据的个数size_t capacity; //容量大小
}SeqList;//接口
//初始化
void SLInit(SeqList* psl);//增加
//头插
void SLPushFront(SeqList* psl, SLDataType data);
//尾插
void SLPushBack(SeqList* psl, SLDataType data);
//中间插
void SLInsert(SeqList* psl, int pos, SLDataType data);//打印
void SLPrint(SeqList* psl);
//头删
void SLPopFront(SeqList* psl);
//尾删
void SLPopBack(SeqList* psl);
//中间删
void SLEarse(SeqList* psl, int pos);//查询
int SLFind(SeqList* psl, SLDataType data);
// 修改
void SLModify(SeqList* psl, int pos, SLDataType data);
//销毁
void SLDestory(SeqList* psl);
实现文件
#include SeqList.h
#include stdio.h
#include stdlib.h
#include assert.hvoid SLInit(SeqList* psl)
{assert(psl);psl-array (SLDataType*)malloc(sizeof(SLDataType) * 4);if (psl-array NULL){perror(malloc fail);return;}psl-capacity 4;psl-size 0;
}//检查容量
void CheckCapc(SeqList* psl)
{assert(psl);if (psl-size psl-capacity){SLDataType* temp (SLDataType*)realloc(psl-array, sizeof(SLDataType) * psl-capacity * 2);if (temp NULL){perror(realloc fail);return;}psl-array temp;psl-capacity psl-capacity * 2;}}void SLPushFront(SeqList* psl, SLDataType data)
{assert(psl);/*CheckCapc(psl);int end psl-size - 1;while (end 0){psl-array[end 1] psl-array[end];end--;}psl-array[0] data;psl-size;*///调用中间插入SLInsert(psl, 0, data);
}void SLPushBack(SeqList* psl, SLDataType data)
{assert(psl);/*CheckCapc(psl);psl-array[psl-size] data;psl-size;*///调用中间插入SLInsert(psl, psl-size, data);
}void SLInsert(SeqList* psl, int pos, SLDataType data)
{assert(psl);assert(pos 0 pos psl-size);CheckCapc(psl);int end psl-size - 1;while (end pos){psl-array[end 1] psl-array[end];end--;}psl-array[pos] data;psl-size;
}void SLPrint(SeqList* psl)
{assert(psl);for (int i 0; i psl-size; i){printf(%d , psl-array[i]);}printf(\r\n);
}void SLPopFront(SeqList* psl)
{assert(psl);assert(psl-size 0);/*int start 0;while (start psl-size - 1){psl-array[start] psl-array[start 1];start;}psl-size--;*/SLEarse(psl, 0);
}void SLPopBack(SeqList* psl)
{assert(psl);assert(psl-size 0);psl-size--;
}void SLEarse(SeqList* psl, int pos)
{assert(psl);assert(psl-size 0);int start pos 1;while (start psl-size){psl-array[start - 1] psl-array[start];start;}psl-size--;
}int SLFind(SeqList* psl, SLDataType data)
{assert(psl);int i 0;for (; i psl-size; i){if (psl-array[i] data)return i;}return -1;
}void SLModify(SeqList* psl, int pos, SLDataType data)
{assert(psl);assert(pos 0 pos psl-size);psl-array[pos] data;
}void SLDestory(SeqList* psl)
{assert(psl);if (psl-array ! NULL){free(psl-array);psl-array NULL;}psl-capacity 0;psl-size 0;psl NULL;
}
主文件
#define _CRT_SECURE_NO_WARNINGS 1
#include stdio.h
#include string.h
#include stdlib.h
#include SeqList.hint main()
{SeqList array;SLInit(array);//增加SLPushBack(array, 1);SLPushBack(array, 2);SLPushBack(array, 3);SLPushBack(array, 4);SLPushBack(array, 5);SLPushFront(array, 6);SLPrint(array);//删除SLPopBack(array);SLPrint(array);SLPopFront(array);SLPrint(array);SLInsert(array, 4, 4);SLPrint(array);//删除指定元素SLEarse(array, 2);SLPrint(array);SLInsert(array, 4, 8);SLPrint(array);int pos SLFind(array, 8);if (pos ! -1){SLModify(array, pos, 10);}SLPrint(array);SLDestory(array);return 0;
}
传入顺序表指针的函数都需要检查一下指针是否为空用断言直接报错的好处在于运行的时候哪里出问题报错提示很明显
菜单界面在调试阶段最好别加影响调试效率菜单界面也不是必须的
菜单项在添加数据的时候如何判断输入数据结束了。用-1或某个值也可能遇到用户刚好需要存入-1的情况。这时可以先输入插入数据的数量再逐个输入数据
当scanf接收输入失败的时候会卡住下次输入如果不清空缓冲区可能会无限读入可以通过判断scanf返回值看是否输入成功
3. 练习
移除元素: https://leetcode.cn/problems/remove-element/ 第一种: 暴力求解遍历数组遇到和值一样的将后面的往前覆盖继续查找 时间复杂度O(N2) 空间复杂度: O(1)
第二种: 新建一个数组遇到值和给定值不一样的放入新数组里 时间复杂度O(N) 空间复杂度: 开辟了新数组, O(N)
第三种: 和第二种思路相似但不开辟新数组在原数组上修改。用两个下标一个des一个src遇到和给定值不一样的将des处值改为src的值两个下标都增加1遇到一样的只增加src下标。当src遍历完数组返回长度 int removeElement(int* nums, int numsSize, int val) {int sign1 0;int sign2 0;for(int i 0; i numsSize; i){if(nums[sign1] ! val){nums[sign2] nums[sign1];sign1;sign2;}else{sign1;}}return sign2;
}
