一.顺序表:
1.线性表：线性表是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使 用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的， 线性表在物理上存储时，通常以数组和链式结构的形式存储。
2.顺序表：顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存 储。在数组上完成数据的增删查改。
3.顺序表的分类：
(1)静态顺序表：使用定长数组存储元素。
(2)动态顺序表：使用动态开辟的数组存储。
4.顺序表的实现
#include#include typedef int SLDataType; typedef struct SeqList { SLDataType* a; int size; int capacity; }SL; //打印数据 void SLPrint(SL* ps) { for (int i = 0; i < ps->size; i++) { printf("%d ", ps->a[i]); } printf("n"); } //初始化数据 void SLInit(SL* ps) { ps->a = NULL; ps->size = ps->capacity = 0; } //判断扩容 void SLCheckCapacity(SL* ps) { if (ps->size == ps->capacity) { int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType)); if (tmp== NULL) { perror("REALLOC:n"); return; } ps->a = tmp; ps->capacity=newcapacity; } } //尾插 void SLPushBack(SL* ps,SLDataType x) { SLCheckCapacity(ps); ps->a[ps->size] = x; ps->size++; } //头插 void SLPushFront(SL* ps, SLDataType x) { SLCheckCapacity(ps); int end = ps->size - 1; //向前移动数据 while (end >= 0) { ps->a[end + 1] = ps->a[end]; end--; } ps->a[0] = x; ps->size++; } //指定位置插入数据 void SLInsert(SL* ps, int pos, SLDataType x) { assert(ps); assert(pos >= 0 && pos <= ps->size); SLCheckCapacity(ps); int end = ps->size - 1; while (end >= pos) { ps->a[end + 1] = ps->a[end]; end--; } ps -> a[pos] = x; ps->size++; } //查找数据 int SLFind(SL* ps, SLDataType x) { assert(ps); for (int i = 0; i < ps->size; i++) { if (ps->a[i] == x) { return i; } return -1; } } // void SLModify(SL* ps, int pos, SLDataType x) { assert(ps); assert(pos >= 0 && pos < ps->size); ps->a[pos] = x; } //删除数据 void SLErase(SL* ps, int pos) { assert(ps); assert(pos >= 0 && pos < ps->size); int begin = pos + 1; while (begin < ps->size) { ps->a[begin - 1] = ps->a[begin]; begin++; } ps->size--; } void SLPopBack(SL* ps) { SLErase(ps, 0); } TestSeqList1() { SL s1; SLInit(&s1); //尾插 SLPushBack(&s1, 1); //头插 SLPushFront(&s1, 2); //删除 SLErase(&s1, 1); //查找 SLFind(&s1, 0); //打印 SLPrint(&s1); } int main() { TestSeqList1(); return 0; }
二.链表
1. 链表的概念及结构 概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表 中的指针链接次序实现的 。
2.链表的分类
(1).单项或者双向
(2).带头或者不带头
(3).循环或者非循环
(4). 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结 构的子结构，如哈希桶、图的邻接表等等。
(5). 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都 是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带 来很多优势，实现反而简单了
3.单链表的实现
#include#include #include typedef int SLTDateType; //单链表结构体 typedef struct SListNode { SLTDateType data; struct SListNode* next; }SListNode; //动态申请一个节点 SListNode* BuySListNode(SLTDateType x) { SListNode* node = (SListNode*)malloc(sizeof(SListNode)); node->data = x; node->next = NULL; return node; } //打印 void SListPrint(SListNode* plist) { SListNode* cur = plist; while (cur) { printf("%d->", cur->data); cur = cur->next; } printf("NULLn"); } //尾插 void SListPushBack(SListNode** pplist, SLTDateType x) { SListNode* newnode = BuySListNode(x); if (*pplist == NULL) { *pplist = newnode; } else { SListNode* tail = *pplist; while (tail->next != NULL) { tail = tail->next; } tail->next = newnode; } } //尾删 void SListPopBack(SListNode** pplist) { SListNode* prev = NULL; SListNode* tail = *pplist; if (tail == NULL || tail->next == NULL) { free(tail); *pplist = NULL; } else { while (tail->next) { prev = tail; tail = tail->next; } free(tail); tail = NULL; prev->next = NULL; } } //头插 void SListPushFront(SListNode** pplist, SLTDateType x) { assert(pplist); SListNode* newnode = BuySListNode(x); if (*pplist == NULL) { *pplist = newnode; } else { newnode->next = *pplist; *pplist = newnode; } } //头删 void SListPopFront(SListNode** pplist) { SListNode* first = *pplist; if (first == NULL) { return; } else if (first->next == NULL) { free(first); *pplist = NULL; } else { SListNode* next = first->next; free(first); *pplist = next; } } //查找 SListNode* SListFind(SListNode* plist, SLTDateType x) { SListNode* cur = plist; while (cur) { if (cur->data == x) return cur; cur = cur->next; } return NULL; } //在pos之后插入x void SListInsertAfter(SListNode* pos, SLTDateType x) { assert(pos); SListNode* next = pos->next; SListNode* newnode = BuySListNode(x); pos->next = newnode; newnode->next = next; } //删除pos之后的值 void SListEraseAfter(SListNode* pos) { assert(pos); SListNode* next = pos->next; if (next != NULL) { SListNode* nextnext = next->next; free(next); pos->next = nextnext; } } //在pos前面插入一个值 void SListInsert(SListNode** pphead, SListNode* pos, SLTDateType x) { if (pos == *pphead) { SListPushFront(pphead, x); } } int main() { //尾插 SListNode* plist = NULL; SListPushBack(&plist, 1); SListPushBack(&plist, 2); SListPushBack(&plist, 3); SListPushBack(&plist, 4); SListPrint(plist); //尾删 SListPopBack(&plist); SListPrint(plist); //头插 SListPushFront(&plist, 0); SListPrint(plist); //头删 SListPopFront(&plist); //查找pos SListNode* str = SListFind(plist, 2); if (str) { printf("找到了n"); } else { printf("不存在n"); } //修改pos的值 SListNode* ret = SListFind(plist, 2); if (ret) { ret->data = 10; } SListPrint(plist); //在pos前面插入一个值 SListNode* pos = SListFind(plist, 1); if (pos) { SListInsert(&plist, pos, 20); } SListPrint(plist); // SListNode* p = SListFind(plist, 1); SListEraseAfter(p); SListPrint(plist); return 0; }
4.双向链表的实现
#include#include #include typedef int LTDataType; typedef struct ListNode { struct ListNode* next; struct ListNode* prev; LTDataType data; }ListNode; //动态申请一个结点 ListNode* BuyListNode(LTDataType x) { ListNode* node = (ListNode*)malloc(sizeof(ListNode)); if (!node) { perror("malloc:"); exit(-1); } node->data = x; node->next = NULL; node->prev = NULL; return node; } // 创建返回链表的头结点. ListNode* ListInit() { ListNode* head = (ListNode*)malloc(sizeof(ListNode)); head->next = head; head->prev = head; return head; } // 双向链表销毁 void ListDestroy(ListNode* pHead) { ListNode* cur = pHead->next; while (cur != pHead) { ListNode* next = cur->next; free(cur); cur = next; } free(pHead); } // 双向链表打印 void ListPrint(ListNode* phead) { assert(phead); ListNode* cur = phead->next; while (cur != phead) { printf("%d ", cur->data); cur = cur->next; } printf("n"); } // 双向链表在pos的前面进行插入 void ListInsert(ListNode* pos, LTDataType x) { assert(pos); ListNode* prev = pos->prev; ListNode* newnode = BuyListNode(x); prev->next = newnode; newnode->prev = prev; newnode->next = pos; pos->prev = newnode; } // 双向链表删除pos位置的节点 void ListErase(ListNode* pos) { assert(pos); ListNode* prev = pos->prev; ListNode* next = pos->next; prev->next = next; next->prev = prev; free(pos); pos = NULL; } // 双向链表尾插 void ListPushBack(ListNode* phead, LTDataType x) { assert(phead); ListInsert(phead, x); } // 双向链表头插 void ListPushFront(ListNode* phead, LTDataType x) { assert(phead); ListInsert(phead->next,x); } // 双向链表尾删 void ListPopBack(ListNode* phead) { assert(phead); ListErase(phead->prev); } // 双向链表头删 void ListPopFront(ListNode* phead) { assert(phead); ListErase(phead->next); } // 双向链表查找 ListNode* ListFind(ListNode* phead, LTDataType x) { assert(phead); ListNode* cur = phead->next; while (cur != phead) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; } int main() { ListNode* lin = ListInit(); ListPushBack(lin, 1); ListPushBack(lin, 2); ListPushBack(lin, 3); ListPushBack(lin, 4); ListPushFront(lin, 0); ListPrint(lin); ListPopFront(lin); ListPopBack(lin); ListPrint(lin); return 0; }
5.顺序表与链表之间的优缺点：
(1)顺序表（优点）：内存空间连续，可以随机访问，CPU高速缓存的命中率高
(2)顺序表（缺点）：空间限制，空间不足时需要增容，会产生性能上的消耗，在ralloc扩容时也可能会出现一定的空间碎片不能很好利用的形式，头部或者中间插入/删除数据需要挪动数据，效率低。
(3)链表（优点）：按需分配内存空间，不会存在空间浪费，只需修改指针指向，可以在任意位置插入和删除数据，且效率高
(4)链表（缺点）：不支持随机访问。可能导致缓存污染，命中率低
(5)总结：顺序表与链表相辅相成，各有各的优缺点，顺序表适宜做查找这样的静态操作，链表适用于做插入、删除这样的动态操作，不同类型的场景下，选择合适的存储结构会使解决问题效率成倍地提高。
