1.线性表
线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就是说连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
线性表最经典的两种形式：一种就是数组，另一种就是链表。
2.顺序表的实现
顺表作为最简单的数据结构，作用就是把数据存储起来。比如所我们玩的QQ中的联系人、或者通讯录等等。
概念及结构
顺序表是一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储，在数组上完成数据的增删查改。
顺序表一般可以分为：
1.静态顺序表：使用定长数组存储。（即长度是固定的）
2.动态顺序表：使用动态开辟的数组存储。
完整代码
SeqList.h
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int SLDataType; typedef struct Seqlist { SLDataType* a; int size; int capacity; }SL; void SeqListInit(SL* ps); void SeqListPrint(SL* ps); void CheckCapacity(SL* ps); void SeqListPushBack(SL* ps, SLDataType x); void SeqListPopBack(SL* ps); void SeqListPushFront(SL* ps, SLDataType x); void SeqListPopFront(SL* ps); void SeqListInsert(SL* ps, int pos, SLDataType x); void SeqListErase(SL* ps, int pos); void SeqListDestroy(SL* ps);
SeqList.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"Seqlist.h" void SeqListInit(SL* ps) { assert(ps); ps->a = NULL; ps->size = 0; ps->capacity = 0; } void SeqListPrint(SL* ps) { for (int i = 0; i < ps->size; i++) { printf("%d ", ps->a[i]); } } void CheckCapacity(SL* ps) { if(ps->size==ps->capacity) { if (ps->capacity == 0) { ps->a = (SLDataType*)malloc(sizeof(SLDataType) * 4); ps->capacity = 4; } else { SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * ps->capacity * 2); if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } ps->a = tmp; ps->capacity *= 2; } } } void SeqListPushBack(SL* ps, SLDataType x) { assert(ps); CheckCapacity(ps); ps->a[ps->size] = x; ps->size++; } void SeqListPopBack(SL* ps) { assert(ps); assert(ps->size > 0); ps->size--; } void SeqListPushFront(SL* ps, SLDataType x) { assert(ps); CheckCapacity(ps); for (int i = ps->size; i >= 1; i--) { ps->a[i] = ps->a[i - 1]; } ps->a[0] = x; ps->size++; } void SeqListPopFront(SL* ps) { assert(ps); assert(ps->size > 0); for (int i = 0; i < ps->size - 1; i--) { ps->a[i] = ps->a[i + 1]; } ps->size--; } void SeqListInsert(SL* ps, int pos, SLDataType x) { assert(ps); CheckCapacity(ps); assert(pos >= 1 && pos <= ps->size); for (int i = ps->size; i >= pos; i--) { ps->a[i] = ps->a[i - 1]; } ps->a[pos - 1] = x; ps->size++; } void SeqListErase(SL* ps, int pos) { assert(ps); assert(pos >= 1 && pos <= ps->size); for (int i = pos - 1; i <= ps->size - 1 - 1; i++) { ps->a[i] = ps->a[i + 1]; } ps->size--; } void SeqListDestroy(SL* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->capacity = ps->size = 0; }
test.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"Seqlist.h" //测试尾插尾删 void SeqListTest1() { SL sl; SeqListInit(&sl); SeqListPushBack(&sl, 2); SeqListPushBack(&sl, 1); SeqListPushBack(&sl, 6); SeqListPushBack(&sl, 59); SeqListPushBack(&sl, 1); SeqListPushBack(&sl, 6); SeqListPrint(&sl); printf("\n"); SeqListPopBack(&sl); SeqListPopBack(&sl); SeqListPopBack(&sl); SeqListPopBack(&sl); SeqListPopBack(&sl); SeqListPrint(&sl); SeqListDestroy(&sl); } //测试头插头删 void SeqListTest2() { SL sl; SeqListInit(&sl); SeqListPushFront(&sl, 1); SeqListPushFront(&sl, 2); SeqListPushFront(&sl, 3); SeqListPushFront(&sl, 4); SeqListPushFront(&sl, 5); SeqListPrint(&sl); printf("\n"); SeqListPopFront(&sl); SeqListPopFront(&sl); SeqListPrint(&sl); printf("\n"); SeqListDestroy(&sl); } //测试任意位置插入 void SeqListTest3() { SL sl; SeqListInit(&sl); SeqListPushFront(&sl, 1); SeqListPushFront(&sl, 2); SeqListPushFront(&sl, 3); SeqListPushFront(&sl, 4); SeqListPushFront(&sl, 5); SeqListPrint(&sl); printf("\n"); SeqListInsert(&sl, 1, 4); SeqListPrint(&sl); printf("\n"); SeqListInsert(&sl, 2, 100); SeqListPrint(&sl); printf("\n"); SeqListDestroy(&sl); } //测试任意位置删除 void SeqListTest4() { SL sl; SeqListInit(&sl); SeqListPushFront(&sl, 1); SeqListPushFront(&sl, 2); SeqListPushFront(&sl, 3); SeqListPushFront(&sl, 4); SeqListPushFront(&sl, 5); SeqListPrint(&sl); printf("\n"); SeqListErase(&sl, 1); SeqListPrint(&sl); printf("\n"); SeqListErase(&sl, 4); SeqListPrint(&sl); printf("\n"); } int main() { //SeqListTest1(); //SeqListTest2(); //SeqListTest3(); //SeqListTest4(); return 0; }
3.总结
说一下学这的建议吧，这块的内容还是比C语言那块稍微上一个档次的，首先要有比较好的C语言基础，才能在学习数据结构的过程中如鱼得水。多敲代码也是一个很重要的一点。勤思考，多理一下这里面的思路以及常见的一些思考方式。再次强调一下，学习的时候一定要思考，而不是在哪里刷时长感动自己。切记，思考思考再思考！！！
好了，就到这把。
再见啦！！！
