初阶数据结构的实现1 顺序表和链表

1.线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…

相同特性
逻辑结构：人为想象出来的数据的组织形式
物理结构：数据在想象出来的数据的组织形式。

1.1顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

1.1.1静态顺序表（不去实现）

#define N 5
typedef int SLdatatype;
typedef struct SeqList {SLdatatype array [N];int size;
};

1.1.2动态顺序表

typedef int SLdatatype;
typedef struct SeqList {SLdatatype *arr;int capacity;//容量int size;//有效数据个数
}SL

1.1.2.1 定义程序目标

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef struct SeqList {SLDatatype *arr;int capacity;//容量int size;//有效数据个数
}SL;//初始化
void SLInitialize(SL*s);//销毁
void SLDestroy(SL*s );//打印顺序表
void SLPrint(SL* ps);//插入数据
//尾插
void SLPushBack(SL*s, SLDatatype x);//头插
void SLPushFront(SL*s, SLDatatype x);//尾删
void SLPopBack(SL* s);//头删
void SLPopFront(SL* s);//在指定位置插入数据
void SLInsert(SL* s, SLDatatype x, int pos);//在指定位置删除数据
void SLErase(SL* s,int pos);//查找数据
int SLFind(SL* s, SLDatatype x);

1.1.2.2 设计程序

面向程序员自身的，能实现包括顺序表的结构定义、初始化、插入、删除、查找、遍历、排序等操作

1.1.2.3编写代码

void SLInitialize(SL* ps)
{ps->arr = NULL;ps->capacity = ps->size = 0;
}void SLDestroy(SL* ps)
{if (ps->arr){free(ps->arr);}ps->arr = NULL;ps->capacity = ps->size = 0;
}void SLCheckCapacity(SL* ps)
{//判断空间是否充足if (ps->size == ps->capacity){//增容//若capacity为0，给个默认值，否则×2倍int NewCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;SLDatatype* tmp = (SLDatatype*)realloc(ps->arr, NewCapacity * sizeof(SLDatatype));if (tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = NewCapacity;}
}void SLPrint(SL* ps)
{for (int i = 0; i < ps->size; i++){printf("%d ", ps->arr[i]);}printf("\n");
}void SLPushBack(SL*ps, SLDatatype x)
{assert(ps);SLCheckCapacity(ps);ps->arr[ps->size++] = x;
}void SLPushFront(SL* ps, SLDatatype x)
{assert(ps);SLCheckCapacity(ps);//数据整体后移for (int i = ps->size; i > 0; i--){ps->arr[i] = ps->arr[i-1];}ps->arr[0] = x;ps->size++;
}void SLPopBack(SL* ps)
{assert(ps && ps->size);ps->size--;
}
void SLPopFront(SL* ps)
{assert(ps && ps->size);for (int i = 0; i < ps->size-1; i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}void SLInsert(SL* ps, SLDatatype x, int pos)
{assert(pos >= 0 && pos <= ps->size);SLCheckCapacity(ps);for (int i = ps->size; i >pos; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[ps->size] = x;ps->size++;}void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size&& ps->size);for (int i=pos; i < ps->size-1; i++){ps->arr[i] = ps->arr[i+1];}ps->size--;
}int SLFind(SL* ps, SLDatatype x)
{assert(ps);for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x)return i;}return -1;
}

1.1.2.3测试和调试代码

#include"Seqlist.h"
void SLtest01()
{SL s;SLInitialize(&s);SLPushBack(&s, 1);SLPushBack(&s, 2);SLPushBack(&s, 3);SLPushBack(&s, 4);SLPushBack(&s, 5);SLPushBack(&s, 6);/*SLPushBack(NULL , 6);*/SLPushFront(&s, 1);SLPushFront(&s, 2);SLPushFront(&s, 3);SLPushFront(&s, 4);SLPrint(&s); //4 3 2 1SLPopBack(&s);SLPrint(&s);SLPopBack(&s);SLPrint(&s);SLPopBack(&s);SLPrint(&s);SLPopBack(&s);SLPrint(&s);SLPopFront(&s);SLPrint(&s);SLPopFront(&s);SLPrint(&s);SLPopFront(&s);SLPrint(&s);SLPopFront(&s);SLPrint(&s);SLPopFront(&s);SLPrint(&s);SLInsert(&s, 11, 0);SLPrint(&s);SLInsert(&s, 22, s.size);SLPrint(&s);SLInsert(&s, 33, 1);SLPrint(&s);SLDestroy(&s);
}int main()
{SLtest01();return 0;
}

1.1.2 顺序表的问题与思考

1. 中间/头部的插入删除，时间复杂度为O(N)
2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们
   再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
   思考：如何解决以上问题呢？下面给出了链表的结构来看看。

1.2链表

1.2.1链表的概念及结构

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链
接次序实现的 。

1.2.1.1 定义程序目标

实现

define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int SLTDataType;//定义结点结构;
typedef struct SListNode {SLTDataType data;struct SListNode* next;
}SLTNode;//链表的打印
void SLTPrint(SLTNode*);
//申请新结点
SLTNode* SLTBuyNode(SLTDataType);
//尾插
void SLTPushBack(SLTNode**, SLTDataType);
//头插
void SLTPushFront(SLTNode** , SLTDataType );//删除//尾删
void SLTPopBack(SLTNode**);
//头删
void SLTPopFront(SLTNode**);//查找
SLTNode* SLTFind(SLTNode*, SLTDataType);//在指定位置之前插⼊数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//在指定位置之后插⼊数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);//删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos);//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos);//销毁链表
void SListDestroy(SLTNode** pphead);

1.2.1.2 设计程序

面向程序员自身的，能实现包括链表的结构定义、初始化、插入、删除、查找、遍历、排序等操作

1.2.1.3编写代码

#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
void SLTPrint(SLTNode* phead)
{SLTNode* pcur = phead;while (pcur){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));if (node == NULL){perror("malloc fail");exit(1);}node->data = x;node->next = NULL;return node;
}void SLTPushBack(SLTNode**pphead, SLTDataType x)
{//申请新结点SLTNode*NewNode = SLTBuyNode(x);if (*pphead == NULL){*pphead = NewNode;}//尾结点->新结点//找尾结点else{SLTNode* pcur = *pphead;while (pcur->next){pcur = pcur->next;}pcur->next = NewNode;}
}void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);//申请新结点SLTNode* NewNode = SLTBuyNode(x);//进行头插NewNode->next = *pphead;*pphead = NewNode;
}void SLTPopBack(SLTNode** pphead)
{//链表为空不可以删除assert(pphead && *pphead);//处理链表只有一个结点的情况if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{//找prev和ptailSLTNode* ptail = *pphead;SLTNode* prev = NULL;while (ptail->next){prev = ptail;ptail = ptail->next;}prev->next = NULL;free(ptail);ptail = NULL;}
}void SLTPopFront(SLTNode** pphead)
{//链表为空不可以删除assert(pphead && *pphead);SLTNode* next = (*pphead)->next;free(*pphead);*pphead = NULL;*pphead = next;
}SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* pcur = phead;while (pcur){if (pcur->data == x){return pcur;}else{pcur = pcur->next;}}return NULL;
}void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);if (*pphead == pos)SLTPushBack(pphead, x);else{SLTNode* prev = *pphead;SLTNode* NewNode = SLTBuyNode(x);while (prev->next != pos){prev = prev->next;}prev->next = NewNode;NewNode->next = pos;}
}void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* NewNode = SLTBuyNode(x);NewNode->next = pos->next;pos->next = NewNode;
}void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead&&*pphead);assert(pos);if (*pphead = pos)SLTPopBack(pphead);else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}void SLTEraseAfter(SLTNode* pos)
{assert(pos && pos->next);SLTNode* del = pos->next;pos->next = pos->next->next;free(del);del = NULL;
}void SListDestroy(SLTNode** pphead)
{SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

1.1.2.3测试和调试代码

#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"void SListTest01()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPrint(plist);//1->2->3->4->NULLSLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPushFront(&plist, 4);SLTPrint(plist); //4->3->2->1->NULLSLTPopBack(&plist);SLTPrint(plist);SLTPopBack(&plist);SLTPrint(plist);SLTPopBack(&plist);SLTPrint(plist);SLTPopBack(&plist);SLTPrint(plist);SLTPopBack(&plist);SLTPrint(plist);SLTPopFront(&plist);SLTPrint(plist);SLTPopFront(&plist);SLTPrint(plist);SLTNode* find = SLTFind(plist, 4);if (find == NULL){printf("未找到！\n");}else{printf("找到了！\n");}SLTInsert(&plist, plist, 11);//4->3->2->11->1->NULLSLTInsertAfter(plist, 11);SLTPrint(plist);1->11->2->3->4->NULLSLTErase(&plist, plist);// 1->2->3->NULLSLTEraseAfter(plist);SLTPrint(plist);SListDestroy(&plist);SLTPrint(plist);
}
int main()
{SListTest01();return 0;
}