由于考研重新开始复习数据结构,学习过程中手撸代码是必不可少的,于是在这里记录一些实现过的数据结构,参考了王道书和严蔚敏C语言版数据结构。由于是自用,注释并没有写的很详细,仅供参考。
在考虑实现一个数据结构时,首先该考虑的是数据结构的三要素:逻辑结构、存储结构和数据的基本运算。以这次实现的动态顺序表为例,其逻辑结构是线性表(线性结构),存储结构是顺序存储,数据的基本运算包括增删改查等等。以这样的思路去实现数据结构就会非常清晰,即,通过逻辑结构和存储结构确认数据结构的定义,然后再在这个基础上完成一系列基本运算。基本运算中最基础的 *** 作有创销、增删改查,首先我们要对数据结构进行初始化,还要能对其进行销毁以防内存泄露;增删改查中,增删查是最值得研究的,改只要能查到就能改所以一般不需要考虑;此外还可以实现判空判满 *** 作,方便一些边界条件的确认。
下面是动态顺序表的实现代码,使用ide为vs2019。
SeqList.h
#define _CRT_SECURE_NO_WARNINGS
#include
#include
#define ElemType int
#define InitSize 10
typedef struct{
ElemType* data;
int length, MaxSize;
}SeqList; //动态顺序表
void InitList(SeqList &l); //初始化顺序表
void ExtendList(SeqList &l, int size); //扩展动态顺序表大小
bool isEmpty(SeqList l); //顺序表判空
void DestroyList(SeqList &l); //销毁顺序表
bool ListInsert(SeqList& l, int i, ElemType e); //在位序i处插入元素e
bool ListDelete(SeqList& l, int i, ElemType &e); //在位序i处删除元素e
ElemType GetElem(SeqList l, int i); //按位序查找元素,返回元素e
int LocateElem(SeqList l, ElemType e); //按值查找元素,返回位序i
SeqList.c
#include "SeqList.h"
//初始化顺序表
void InitList(SeqList &l) {
l.data = (ElemType*)malloc(sizeof(ElemType) * InitSize);
l.MaxSize = InitSize;
l.length = 0;
}
//扩展动态顺序表大小
void ExtendList(SeqList &l, int len) {
ElemType* p = l.data;
l.data = (ElemType*)malloc(sizeof(ElemType) * (l.MaxSize+ len));
l.MaxSize = l.MaxSize + len;
for (int i = 0; i < l.length; i++) {
l.data[i] = p[i];
}
free(p);
}
//顺序表判空
bool isEmpty(SeqList l) {
return (l.length == 0);
}
//销毁顺序表
void DestroyList(SeqList &l) {
free(l.data);
l.data = NULL;
l.MaxSize = 0;
}
//在位序i处插入元素e (即第i个元素前)
//思路:从后往前每个元素往后移一位,直到把位序i处的元素往后移至i+1处,再把元素e赋值到位序i处
//注:位序i,在数组的位置为i-1
bool ListInsert(SeqList& l, int i, ElemType e) {
if (i > l.length + 1 || i < 1)
return false;
for (int j = l.length; j >= i; j--) {
l.data[j] = l.data[j - 1];
}
l.data[i - 1] = e;
l.length++;
return true;
}
//在位序i处删除元素e
bool ListDelete(SeqList& l, int i, ElemType& e) {
if (i > l.length || i < 1)
return false;
e = l.data[i - 1];
for (int j = i; j < l.length; j++) {
l.data[j - 1] = l.data[j];
}
l.length--;
}
//按位序查找元素,返回元素e
//O(1)
ElemType GetElem(SeqList l, int i) {
return(l.data[i-1]);
}
//按值查找元素,返回位序i
//O(n)
int LocateElem(SeqList l, ElemType e) {
for (int i = 0; i < l.length; i++) {
if (l.data[i] == e)
return i+1;
}
return 0;
}
main.c
#include "SeqList.h"
void PrintList(SeqList l) {
for(int i = 0; i < l.length; i++){
printf("%d\t", l.data[i]);
}
}
//测试
int main() {
SeqList l;
InitList(l);
l.length = 5;
for (int i = 0; i < l.length; i++) {
l.data[i] = i;
}
PrintList(l);
/*
ListInsert(l, 3, 8);
printf("\n Insert \"%d\": ", 8);
PrintList(l);
*/
/*
int e;
ListDelete(l, 1, e);
printf("\n Delete \"%d\": ", e);
PrintList(l);
*/
printf("\n GetElem(l, i): \"%d\"", GetElem(l, 3));
printf("\n LocateElem(l, 4): \"%d\"", LocateElem(l, 4));
DestroyList(l);
return 0;
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)