由于考研重新开始复习数据结构，学习过程中手撸代码是必不可少的，于是在这里记录一些实现过的数据结构，参考了王道书和严蔚敏C语言版数据结构。由于是自用，注释并没有写的很详细，仅供参考。
在考虑实现一个数据结构时，首先该考虑的是数据结构的三要素：逻辑结构、存储结构和数据的基本运算。以这次实现的动态顺序表为例，其逻辑结构是线性表（线性结构），存储结构是顺序存储，数据的基本运算包括增删改查等等。以这样的思路去实现数据结构就会非常清晰，即，通过逻辑结构和存储结构确认数据结构的定义，然后再在这个基础上完成一系列基本运算。基本运算中最基础的操作有创销、增删改查，首先我们要对数据结构进行初始化，还要能对其进行销毁以防内存泄露；增删改查中，增删查是最值得研究的，改只要能查到就能改所以一般不需要考虑；此外还可以实现判空判满操作，方便一些边界条件的确认。
下面是动态顺序表的实现代码，使用ide为vs。
SeqList.h
#define _CRT_SECURE_NO_WARNINGS#include <stdio.h>#include <stdlib.h>#define ElemType int#define InitSize 10typedef 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处插入元素ebool ListDelete(SeqList& l, int i, ElemType &e);//在位序i处删除元素eElemType GetElem(SeqList l, int i);//按位序查找元素,返回元素eint 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-1bool 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处删除元素ebool 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;}
