徐州人才网官方网站,设计一个网站页面需要多少钱,17我们一起做网站,c语言精品网站开发的教学前言
本文将一一介绍顺序表基本功能的接口实现#xff0c;帮助大家提高编程能力#xff0c;加深对数据结构的理解
本文将以动态顺序表为主进行解释
基本接口功能
#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#includestdio.h
#includestdlib.h
#inc…前言
本文将一一介绍顺序表基本功能的接口实现帮助大家提高编程能力加深对数据结构的理解
本文将以动态顺序表为主进行解释
基本接口功能
#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#includestdio.h
#includestdlib.h
#includeassert.htypedef int SLDataType;
typedef struct SeqList
{SLDataType* a;int size;int capacity;
}SeqList;//常用接口
//顺序表初始化
void SeqListInit(SeqList* psl);
// 检查空间如果满了进行增容
void CheckCapacity(SeqList* psl);
// 顺序表尾插
void SeqListPushBack(SeqList* psl, SLDataType x);
// 顺序表尾删
void SeqListPopBack(SeqList* psl);
// 顺序表头插
void SeqListPushFront(SeqList* psl, SLDataType x);
// 顺序表头删
void SeqListPopFront(SeqList* psl);
// 顺序表查找
int SeqListFind(SeqList* psl, SLDataType x);
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);
// 顺序表删除pos位置的值
void SeqListErase(SeqList* psl, size_t pos);
// 顺序表销毁
void SeqListDestory(SeqList* psl);
// 顺序表打印
void SeqListPrint(SeqList* psl);顺序表初始化
将顺序表结构体里的成员变量该置0置0该置空置空因为在创建初成员变量存放的都是随机值整型存放的是随机数指针指向的是随机地址如果不初始化就进行调用的话容易导致内存错误。
同时将顺序表指针断言一下以免传入空指针。
void SeqListInit(SeqList* psl)
{assert(psl);psl-a NULL;psl-size 0;psl-capacity 0;
}
检查容量函数
动态顺序表的好处就是我们可以根据需要判断是否需要扩容因为扩容函数方便。设想一下如果是静态顺序表的话用数组存储的顺序表就得一开始创建好定好容量后就不能改变了过多且不说万一少了咋办而且多了话还会浪费不必要的内存。
实现原理
当顺序表内元素个数等于最大容量就扩容且每次是双倍扩容但是当最大容量为0时创建初将最大容量设置为4即可这是考虑到了0*任何数都等于0的情况。
动态顺序表利用动态内存管理相关的函数relloc申请内存分配。
这里提一下因为relloc的功能是在已经通过动态申请的内存上进行扩大或缩小但当创建初顺序的表的指针为空则此时realloc的功能就等于malloc。
void CheckCapacity(SeqList* psl)
{assert(psl);if (psl-size psl-capacity){int newcapacity psl-capacity 0 ? 4 : psl-capacity * 2;//双倍扩容SLDataType* ptr (SLDataType*)realloc(psl-a, sizeof(SLDataType) * newcapacity);if (ptr NULL){perror(return fail);return;}psl-a ptr;psl-capacity newcapacity;}
}
顺序表尾插
这是顺序表插入元素最简单的方法但每次插入前记得使用一下检查容量函数插入后个数size记得加1.
void SeqListPushBack(SeqList* psl, SLDataType x)
{assert(psl);CheckCapacity(psl);psl-a[psl-size] x;
} 顺序表尾删
直接size--就行被剪掉的那个元素会被丢弃
void SeqListPopBack(SeqList* psl)
{assert(psl);assert(psl-size ! 0);psl-size--;
}
顺序表头插
头插有讲究不能直接像尾插那样直接放数据进去那样第一个元素就被覆盖掉了所以就得将整个数组的元素位置向后移一个将数组按照从后往前的顺序整体往后移避免覆盖丢失数据这样数组的头一个元素就空出来了此时才能往里放数据。
和尾插一样检查一下容量size。
void SeqListPushFront(SeqList* psl, SLDataType x)
{assert(psl);CheckCapacity(psl);int end psl-size - 1;for (int i end; i 0; i--){psl-a[i 1] psl-a[i];}psl-a[0] x;psl-size;
}
顺序表头删
头删和头插一样有讲究将数组头后面的元素整体向前移完成覆盖从头往后的顺序向前移移完后记得将size--。
void SeqListPopFront(SeqList* psl)
{assert(psl);assert(psl-size ! 0);int begin 1;while (begin psl-size){psl-a[begin - 1] psl-a[begin];begin;}psl-size--;
}
顺序表查找
没什么好说的就是简单的数组查找
int SeqListFind(SeqList* psl, SLDataType x)
{assert(psl);for (int i 0; i psl-size; i){if (psl-a[i] x){return i1;}}return 0;
}
顺序表在pos位置插入x
不管是什么插入都要检查一下容量。
先找到对应的pos位置将pos后面的所有数组按照从后往前的顺序向后移之后再进行插入记得size。
void SeqListInsert(SeqList* psl, int pos, SLDataType x)
{assert(psl);assert(pos 0 pos psl-size);CheckCapacity(psl);int end psl-size - 1;while (end pos){psl-a[end 1] psl-a[end];end--;}psl-a[pos] x;psl-size;}
顺序表删除pos位置的值
和上面的一个原理但不一样的是将pos后面的数组按从前往后的顺序往前移实现覆盖记得size--。
void SeqListErase(SeqList* psl, size_t pos)
{assert(psl);assert(pos 0 pos psl-size);int begin pos 1;int end psl-size - 1;while (begin end){psl-a[begin - 1] psl-a[begin];begin;}psl-size--;
}
顺序表销毁
该置0置0该freefree记得将free后的指针置空。
void SeqListDestory(SeqList* psl)
{assert(psl);if (psl-a ! NULL){free(psl-a);psl-capacity 0;psl-size 0;}
}
顺序表打印
void SeqListPrint(SeqList* psl)
{assert(psl);for (int i 0; i psl-size; i){printf(%d , psl-a[i]);}printf(\n);
}
以上这些就是顺序表的基本功能实现细节虽然都一一列了出来但还是希望各位能够去根据每一个功能的思想自己写出来加深印象。
