攀枝花市三线建设博物馆网站,如何看网站是用什么程序做的,成都网站建设方法数码,福州网站改版顺序表 一.数据结构1.逻辑结构2.物理结构 二.顺序表的分类1.静态顺序表2.动态顺序表 三.顺序表的实现1.创建顺序表2.初始化顺序表3.判断是否扩容4.打印顺序表5.插入操作1.头插2.尾插3.按照下标插入 6.删除操作1.头删2.尾删3.按照下标删除 7.查找数据8.修改数据9.清空顺序表10.销… 顺序表 一.数据结构1.逻辑结构2.物理结构 二.顺序表的分类1.静态顺序表2.动态顺序表 三.顺序表的实现1.创建顺序表2.初始化顺序表3.判断是否扩容4.打印顺序表5.插入操作1.头插2.尾插3.按照下标插入 6.删除操作1.头删2.尾删3.按照下标删除 7.查找数据8.修改数据9.清空顺序表10.销毁顺序表 四.模块化源代码1.SeqList.h2.SeqList.c3.test.c 五.顺序表必做OJ题 前言相信大家在学完C语言后对于指针结构体以及动态内存管理有了一定的见解那么数据结构像是检验真理的唯一标椎它考察了你掌握这三种语法的程度如果掌握的不是很理想的友友们建议看看鄙人主页总结的文章好啦数据结构之旅就正式开始啦。
一.数据结构
数据结构计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。数据结构反映数据的内部构成即数据由那部分构成以什么方式构成以及数据元素之间呈现的结构。
1.逻辑结构
逻辑结构数据对象中数据元素之间的相互关系。 逻辑结构分为集合结构线性结构树形结构和图形结构。
2.物理结构
物理结构数据的逻辑结构在计算机中的存储形式。 物理结构分为顺序存储结构和链式存储结构。
二.顺序表的分类
顺序表实际属于线性表这个大家族那么什么是线性表呢
线性表是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构常见的线性表顺序表、链表、栈、队列、字符串…线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构上并不一定是连续的线性表在物理上存储时通常以数组和链式结构的形式存储。
1.静态顺序表
#define MAXSIZE 100 //静态顺序表的容量
typedef int SLDataType; //增强程序的可维护性typedef struct SeqList
{SLDataType arr[MAXSIZE];//定长数组int size; //有效的数据个数
}SeqList;也许有人会问这个静态顺序表说的这么神秘本质上不就是一个数组吗
答没错顺序表的低层就是数组逻辑结构与物理结构都是连续的。不过顺序表对数组进行了封装提供了大量常用的接口所谓接口就是调用函数方便完成数据进行增删查改等一系列的操作。
静态顺序表的缺点程序一但运行数组的大小就确定了不能被修改。数组大小给小了空间就不够用数组大小给大了空间就白白的浪费掉了
为了方便对静态顺序表进行扩容于是动态顺序表便应运而生。
2.动态顺序表
typedef int SLDataType;//增强程序的可维护性typedef struct SeqList
{SLDataType* arr; //动态的可以扩容int size; //有效的数据个数int capacity; //容量
}SL;动态顺序表通过堆区的动态内存管理控制顺序表空间的大小即容量。
以下介绍的是基于动态顺序表的实现。
三.顺序表的实现
1.创建顺序表
创建一个顺序表结构包含指向这块空间的起始地址顺序表中存储数据的个数以及顺序表的最大容量。
typedef int SLDataType;//增强程序的可维护性改变数据类型只需改变int即可typedef struct SeqList
{SLDataType* arr; //指向顺序表的起始位置方便扩容int size; //顺序表的有效的数据个数int capacity; //顺序表的容量大小
}SL;//类型的重命名
//等价于typedef struct SeqList SL;2.初始化顺序表
一般初始化我们都习惯赋值为0指针赋值为NULL。
void SeqListInit(SL* ps)
{assert(ps);//断言操作等价于assert(ps ! NULL);ps-arr NULL;ps-size 0;ps-capacity 0;
}3.判断是否扩容
当我们想要增加数据的时候会遇到容量不够用的问题。所以在此之前应该检查容量与有效数据之间的关系判断是否要扩容接着插入数据。
void SeqListCheckCapacity(SL* ps)
{assert(ps);if (ps-size ps-capacity)//顺序表已满进行扩容操作{//判断顺序表容量是否为0若为0开辟储存4个数据大小的空间若不为0则容量翻倍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;//修改容量}
}注意若传入realloc的指针为空指针(NULL)则realloc函数等价于malloc函数。
4.打印顺序表
循环遍历顺序表数据即可。
void SeqListPrint(SL* ps)
{assert(ps);for (int i 0; i ps-size; i){printf(%d , ps-arr[i]);}printf(\n);
}5.插入操作
1.头插
头插的思想将数据整体向后挪动一位。注意为了防止覆盖原先的数据采用从后向前挪动。再进行头部插入最后有效数据个数1。
void SeqListPushFront(SL* ps, SLDataType x)
{assert(ps);SeqListCheckCapacity(ps);//检查容量int end ps-size;while (end 0){ps-arr[end] ps-arr[end - 1];//将数据整体向后挪动一位。end--;}ps-arr[0] x;//头插ps-size;//有效数据个数1//等价于在下标为0处插入SeqListInsert(ps, 0, x);
}2.尾插
尾插的思想直接在尾部插入有效数据个数1即可。
void SeqListPushBack(SL* ps, SLDataType x)
{assert(ps);SeqListCheckCapacity(ps);//检查容量ps-arr[ps-size] x;//尾插采用后置//等价于在下标为ps-size处插入SeqListInsert(ps, ps-size, x);
}3.按照下标插入
按照下标插入的思想与头插的思想相同只不过是要挪动数据的起始位置不同而已。
void SeqListInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos 0 pos ps-size);//判断下标的合法性SeqListCheckCapacity(ps);int end ps-size;while (end pos){ps-arr[end] ps-arr[end - 1];end--;}ps-arr[pos] x;ps-size;
}6.删除操作
1.头删
头删的思想不是真正意义上的删除数据而是将头部之后的数据整体向前挪动一位覆盖头部数据达到与头删相同的效果最后有效数据个数-1。注意为了防止覆盖原先的数据采用从前向后挪动这里与头插不同。
void SeqListPopFront(SL* ps)
{assert(ps);assert(ps-size 0);//前提顺序表存在数据int start 0;while (start ps-size - 1){ps-arr[start] ps-arr[start 1];start;}ps-size--;//有效数据个数-1//等价于在下标为0处删除SeqListErase(ps, 0);
}2.尾删
尾删的思想有效数据个数-1即可。
void SeqListPopBack(SL* ps)
{assert(ps);assert(ps-size 0);//前提顺序表存在数据ps-size--;//有效数据个数-1//等价于在下标为ps-size - 1处删除SeqListErase(ps, ps-size - 1);
}3.按照下标删除
按照下标删除的思想与头删的思想相同只不过是要挪动数据的起始位置不同而已。
void SeqListErase(SL* ps, int pos)
{assert(ps);assert(ps-size 0);//前提顺序表存在数据assert(pos 0 pos ps-size);//判断下标的合法性int start pos;while (start ps-size - 1){ps-arr[start] ps-arr[start 1];start;}ps-size--;
}7.查找数据
查找的思想遍历数据找到了返回下标未找到返回-1即可。
int SeqListFind(SL* ps, SLDataType x)
{assert(ps);for (int i 0; i ps-size; i){if (ps-arr[i] x){return i;//找到该数据返回下标}}return -1;//未找到返回-1
}8.修改数据
修改的思想利用下标确定位置直接修改就行。较为简单。
void SeqListModify(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos 0 pos ps-size);ps-arr[pos] x;
}9.清空顺序表
清空的思想将有效数据个数与容量赋值为0。
void SeqListClear(SL* ps)
{assert(ps);ps-size 0;ps-capacity 0;
}
10.销毁顺序表
销毁的思想由于空间是利用动态内存函数 realloc 在堆区开辟的所以要及时释放避免内存泄漏。
void SeqListDestory(SL* ps)
{assert(ps);if (ps-arr ! NULL){free(ps-arr);}ps-arr NULL;//置为NULL防止野指针SeqListClear(ps);//清空顺序表
}四.模块化源代码
1.SeqList.h
//#pragma once防止头文件被重复包含
#ifndef __SEQLIST_H__
#define __SEQLIST_H__#includestdio.h
#includestdlib.h
#includestring.h
#includeassert.htypedef int SLDataType;//增强程序的可维护性typedef struct SeqList
{SLDataType* arr; //动态的可以扩容int size; //有效的数据个数int capacity; //容量
}SL;void SeqListInit(SL* ps);//顺序表初始化void SeqListCheckCapacity(SL* ps);//检查顺序表的容量void SeqListPrint(SL* ps);//打印顺序表void SeqListPushBack(SL* ps, SLDataType x);//顺序表尾部插入void SeqListPushFront(SL* ps, SLDataType x);//顺序表头部插入void SeqListPopBack(SL* ps);//顺序表尾部删除void SeqListPopFront(SL* ps);//顺序表头部删除void SeqListInsert(SL* ps, int pos, SLDataType x);//顺序表按照位置下标插入void SeqListErase(SL* ps, int pos);//顺序表按照位置下标删除int SeqListFind(SL* ps, SLDataType x);//顺序表查找元素值返回下标void SeqListModify(SL* ps, int pos, SLDataType x);//顺序表按位置下标修改void SeqListClear(SL* ps);//清空顺序表void SeqListDestory(SL* ps);//销毁顺序表#endif2.SeqList.c
#define _CRT_SECURE_NO_WARNINGS 1#includeSeqList.hvoid SeqListInit(SL* ps)
{assert(ps);//等价于assert(ps ! NULL);ps-arr NULL;ps-size 0;ps-capacity 0;
}void SeqListCheckCapacity(SL* ps)
{assert(ps);if (ps-size ps-capacity){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 SeqListPrint(SL* ps)
{assert(ps);for (int i 0; i ps-size; i){printf(%d , ps-arr[i]);}printf(\n);
}void SeqListPushBack(SL* ps, SLDataType x)
{assert(ps);SeqListCheckCapacity(ps);ps-arr[ps-size] x;//SeqListInsert(ps, ps-size, x);
}void SeqListPushFront(SL* ps, SLDataType x)
{assert(ps);SeqListCheckCapacity(ps);int end ps-size;while (end 0){ps-arr[end] ps-arr[end - 1];end--;}ps-arr[0] x;ps-size;//SeqListInsert(ps, 0, x);
}void SeqListPopBack(SL* ps)
{assert(ps);assert(ps-size 0);ps-size--;//SeqListErase(ps, ps-size - 1);
}void SeqListPopFront(SL* ps)
{assert(ps);assert(ps-size 0);int start 0;while (start ps-size - 1){ps-arr[start] ps-arr[start 1];start;}ps-size--;//SeqListErase(ps, 0);
}void SeqListInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos 0 pos ps-size);SeqListCheckCapacity(ps);int end ps-size;while (end pos){ps-arr[end] ps-arr[end - 1];end--;}ps-arr[pos] x;ps-size;
}void SeqListErase(SL* ps, int pos)
{assert(ps);assert(ps-size 0);assert(pos 0 pos ps-size);int start pos;while (start ps-size - 1){ps-arr[start] ps-arr[start 1];start;}ps-size--;
}int SeqListFind(SL* ps, SLDataType x)
{assert(ps);for (int i 0; i ps-size; i){if (ps-arr[i] x){return i;}}return -1;
}void SeqListModify(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos 0 pos ps-size);ps-arr[pos] x;
}void SeqListClear(SL* ps)
{assert(ps);ps-size 0;ps-capacity 0;
}void SeqListDestory(SL* ps)
{assert(ps);if (ps-arr ! NULL){free(ps-arr);}ps-arr NULL;SeqListClear(ps);
}3.test.c
#define _CRT_SECURE_NO_WARNINGS 1#includeSeqList.henum//匿名枚举
{EXIT,PUSHBACK,PUSHFRONT,POPBACK,POPFRONT,INSERT,ERASE,FIND,MODIFY,PRINT,CLEAR
};void Menu()
{printf(*************顺序表************\n);printf(****1.尾插 2.头插****\n);printf(****3.尾删 4.头删****\n);printf(****5.插入 6.删除****\n);printf(****7.查找 8.修改****\n);printf(****9.打印 10.清空****\n);printf(****0.退出 ******\n);printf(*******************************\n);
}int main()
{SL sl;SeqListInit(sl);int select 0; //菜单选项SLDataType value; //插入的值int pos 0; //插入或删除的下标do{Menu();printf(请选择您的操作);scanf(%d, select);switch (select){case EXIT:printf(退出顺序表!);break;case PUSHBACK:printf(请输入您要尾插的值(输入-1代表结束));while ((scanf(%d, value), value ! -1)) //逗号表达式{SeqListPushBack(sl, value);}break;case PUSHFRONT:printf(请输入您要头插的值(输入-1代表结束));do{scanf(%d, value);if (value ! -1){SeqListPushFront(sl, value);}} while (value ! -1);break;case POPBACK:SeqListPopBack(sl);break;case POPFRONT:SeqListPopFront(sl);break;case INSERT:printf(请输入要插入的《下标》与《值》);scanf(%d %d, pos, value);SeqListInsert(sl, pos, value);break;case ERASE:printf(请输入要删除的《下标》);scanf(%d, pos);SeqListErase(sl, pos);break;case FIND:printf(请输入要查找的《值》);scanf(%d, value);int ret SeqListFind(sl, value);if (ret ! -1){printf(找到了下标为%d\n, ret);}else{printf(找不到!);}break;case MODIFY:printf(请输入要修改的《下标》以及修改后的《值》:);scanf(%d %d, pos, value);SeqListModify(sl, pos, value);break;case PRINT:SeqListPrint(sl);break;case CLEAR:SeqListClear(sl);break;default:printf(您输入的值错误请重新选择!\n);break;}} while (select);SeqListDestory(sl);return 0;
}五.顺序表必做OJ题
原地移除元素合并两个有序数组
创作不易如果能帮到你的话能赏个三连吗感谢啦
