数据结构(一)顺序表和链表

目录

1. 时间复杂度和空间复杂度

2. 顺序表

3. 链表

---

1. 时间复杂度和空间复杂度

         如何估算一个算法的效率高低一般就是使用到时间复杂度和空间复杂度; 时间复杂度是评价一个算法运行快慢的, 而空间复杂度是算法额外需要空间大小.

1.1 时间复杂度的计算:

        准确来说时间复杂度是一个函数, 如何计算有对应的规则的(大o渐进法).

大o渐进法:只要求计算大概运行次数即可, (1)对于常数直接取o(1);  (2)只保留最高阶项

(3) 乘数前面的常数直接省略. 而且一般都是算最坏的运行情况.

 1.2 计算练习:

 下面计算时间复杂度: f(N) =  N*N + 2*N + M --> N^2 + 2N + 10

使用上面的规则: f(N) = N^2 + N 运用(1)+(3)  ---> f(N) = N^2 运用(2);

#include <stdio.h>void Func1(int N)
{int count = 0;for (int i = 0; i < N; ++i){for (int j = 0; j < N; ++j){++count;}}for (int k = 0; k < 2 * N; ++k){++count;}int M = 10;while (M--){++count;}printf("%d\n", count);
}

计算: F(N) = 2*N + M ---> F(N) = N;

void Func2(int N)
{int count = 0;for (int k = 0; k < 2 * N; ++k){++count;}int M = 10;while (M--){++count;}printf("%d\n", count);
}

F(N) = M + N; M和N大小未知.

void Func3(int N, int M)
{int count = 0;for (int k = 0; k < M; ++k){++count;}for (int k = 0; k < N; ++k){++count;}printf("%d\n", count);
}

F(N) = 100  ---> F(N) = 1;

void Func4(int N)
{int count = 0;for (int k = 0; k < 100; ++k){++count;}printf("%d\n", count);
}

计算:  F(N) = N; 可能执行一次或者N次.

const char * strchr ( const char * str, int character );

 计算: F(n) = n * ((n-1) + (n-2) + (n-3) + ... + 1))  ----> n * (n-1) ---> n^ 2;

void BubbleSort(int *a, int n)
{assert(a);for (size_t end = n; end > 0; --end){int exchange = 0;for (size_t i = 1; i < end; ++i){if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);exchange = 1;}}if (exchange == 0)break;}
}

计算折半查找, 设数据总量为x, x/2/2/2/2.../2 =  --->x = 2 * 2 * 2 * ... * 2; ---> x = 2 * N;

N = log2 ^ x --> F(N) = logN;

int BinarySearch(int *a, int n, int x)
{assert(a);int begin = 0;int end = n - 1;// [begin, end]：begin和end是左闭右闭区间，因此有=号while (begin <= end){int mid = begin + ((end - begin) >> 1);if (a[mid] < x)begin = mid + 1;else if (a[mid] > x)end = mid - 1;elsereturn mid;}return -1;
}

计算: F(N) = (N-1) + (N-2) + (N-3) + ... + 1 ---> F(N) = N;

long long Fac(size_t N)
{if (0 == N)return 1;return Fac(N - 1) * N;
}

计算: F(N) = 2^N

long long Fib(size_t N)
{if (N < 3)return 1;return Fib(N - 1) + Fib(N - 2);
}

1.3空间复杂度:

计算: 没有使用额外空间: F(N) = 1;

void BubbleSort(int *a, int n)
{assert(a);for (size_t end = n; end > 0; --end){int exchange = 0;for (size_t i = 1; i < end; ++i){if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);exchange = 1;}}if (exchange == 0)break;}
}

计算: F(N) = n + 1 -> F(N) = n;

long long *Fibonacci(size_t n)
{if (n == 0)return NULL;long long *fibArray = (long long *)malloc((n + 1) * sizeof(long long));fibArray[0] = 0;fibArray[1] = 1;for (int i = 2; i <= n; ++i){fibArray[i] = fibArray[i - 1] + fibArray[i - 2];}return fibArray;
}

计算: F(N) = N  因为调用了n次函数栈帧.

long long Fac(size_t N)
{if (N == 0)return 1;return Fac(N - 1) * N;
}

---

2. 顺序表

2.1 线性表:

        n个具有同种性质的数据元素的有限序列, 例如顺序表, 链表, 栈, 队列, 字符串等....

2.2 顺序表概念:

        一段物理地址连续的存储单元一次存储数据元素的线性结构, 一般用数组存储. 而且一般采用动态增长空间的顺序表.

 2.3 顺序表实现:

(1) 顺序表结构:

        a使用来进行顺序表的动态扩容的, size是记录顺序表的个数, capacity是记录顺序表的容量不够进行扩容.

typedef int SLDataType;typedef struct SeqList
{SLDataType* a;int size;int capacity;
}SeqList;

(2) 顺序表初始化: 

        将SqlList里面的元素进行全部初始化.

void SeqListInit(SeqList* psl)
{assert(psl);psl->a = nullptr;psl->size = 0;psl->capacity = 0;
}

 (3) 顺序表扩容:

        检测顺序表的元素是否需要扩容, 一般采用二倍扩容比较合适, 使用到realloc函数进行将原先顺序表的大小进行物理扩容, 函数细节自行去看cplusplus看看文档.

void SqlCheckCapacity(SeqList* psl)
{if(psl->size == psl->capacity){int newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;SLDataType* newA = (SLDataType*)realloc(psl->a, newcapacity * sizeof(SLDataType));if(newA == nullptr){printf("realloc fail!\n");exit(1);}psl->a = newA;psl->capacity = newcapacity;}
}

 (4)尾插:

        在尾部直接插入即可.也可以调用下面函数.

void SeqListPushBack(SeqList* psl, SLDataType x)
{// assert(psl);// SqlCheckCapacity(psl);// psl->a[psl->size] = x;// psl->size++;SeqListInsert(psl, psl->size, x);
}

 (5)尾删:

        将数据数量直接减少即可.

void SeqListPopBack(SeqList* psl)
{// assert(psl);// assert(psl->size > 0);// psl->size--;SeqListErase(psl, psl->size-1);
}

 (6) 头插:

         将数据进行后移动一位, 给头空出来进行插入.也可以调用下面封装好的函数.

void SeqListPushFront(SeqList* psl, SLDataType x)
{// assert(psl);// SqlCheckCapacity(psl);// for(int i = psl->size; i >= 0; i--)// {//     psl->a[i] = psl->a[i-1];// }// psl->a[0] = x;// psl->size++;SeqListInsert(psl, 0, x);
}

 (7) 头删:

        直接覆盖即可, 后面将前面数据进行覆盖, 或者调用函数.

void SeqListPopFront(SeqList* psl)
{// assert(psl);// assert(psl->size > 0);// for(int i = 0; i < psl->size-1; i++)// {//     psl->a[i] = psl->a[i+1];// }// psl->size--;SeqListErase(psl, 0);
}

 (8) 在pos位置插入x:

        将pos之后的数据进行移动后一位, 然后再进行插入.

void SeqListInsert(SeqList* psl,int pos, SLDataType x)
{assert(psl);assert(pos >= 0 && pos <= psl->size);SqlCheckCapacity(psl);for(int i = psl->size; i > pos; i--){psl->a[i] = psl->a[i-1];}psl->a[pos] = x;psl->size++;
}

 (9) 在pos位置删除x:

        也是将pos后面的数据直接向前覆盖即可.

void SeqListErase(SeqList* psl, int pos)
{assert(psl);assert(psl->size > 0);assert(pos >= 0 && pos < psl->size);for(int i = pos; i < psl->size-1; i++){psl->a[i] = psl->a[i+1];}psl->size--;
}

 (10)查找: 

        遍历即可.

int SeqListFind(SeqList* psl, SLDataType x)
{assert(psl);for(int i = 0; i < psl->size; i++){if(psl->a[i] == x)return i;}return -1;
}

 (11) 销毁: 

        将SqlList里面的元素进行销毁以及size和capacity进行置零.

void SqlListDestory(SeqList* psl)
{assert(psl);free(psl->a);psl->a = nullptr;psl->size = psl->capacity = 0;
}

 (12) 打印:

        循环打印顺序表中的数据元素.

void SqlListPrint(SeqList* psl)
{assert(psl);for(int i =  0; i < psl->size; i++){printf("%d ", psl->a[i]);}printf("\n");
}

(13) 修改: 

void SeqListModify(SeqList* psl, int pos, SLDataType x)
{assert(psl);assert(pos >= 0 && pos < psl->size);psl->a[pos] = x;
}

2.4 C++版本:

        上面是C语言版本, 现在用C++版本写一些.

template<class T>
class SeqList
{
public://使用构造函数和析构函数进行初始化和销毁SeqList():_a(nullptr), _size(0), _capacity(0){}~SeqList(){delete(_a);_a = nullptr;_size = _capacity = 0;}void CheckCapacity(SeqList* psl){if (psl->_size == psl->_capacity){int newcapacity = psl->_capacity == 0 ? 4 : psl->_capacity * 2;T* newA = new[newcapacity];for (int i = 0; i < psl->_size; i++){newA[i] = psl->_a[i];}psl->_a = newA;delete newA;newA = nullptr;psl->_capacity = newcapacity;}}void SqlListPrint(SeqList* psl){assert(psl);for (int i = 0; i < psl->_size; i++){cout << psl->_a[i] << " ";}cout << "\n";}void SeqListInsert(SeqList* psl, int pos, T x){assert(psl);assert(pos >= 0 && pos <= psl->_size);for (int i = psl->_size; i > pos; i--){psl->_a[i] = psl->a[i - 1];}psl->_a[pos] = x;psl->_size++;}void SeqListPushFront(SeqList* psl, T x){SeqListInsert(psl, 0, x);}void SeqListPushBack(SeqList* psl, T x){SeqListInsert(psl, psl->_size, x);}void SeqListErase(SeqList* psl, int pos){assert(psl);assert(psl->_size > 0);assert(pos >= 0 && pos < psl->_size);for (int i = pos; i < psl->_size - 1; i++){psl->_a[i] = psl->_a[i + 1];}psl->_size--;}void SeqListPopFront(SeqList* psl){SeqListErase(psl, 0);}void SeqListPopBack(SeqList* psl){SeqListErase(psl, psl->_size - 1);}int SeqListFind(SeqList* psl, T x){assert(psl);for (int i = 0; i < psl->_size; i++){if (psl->_a[i] == x)return i;}return -1;}void SeqListModify(SeqList* psl, int pos, T x){assert(psl);assert(pos >= 0 && pos < psl->_size);psl->_a[pos] = x;}
private:T* _a;int _size;int _capacity;
};

 2.5 链表问题以及思考:

(1) 除了尾部删除/插入为0(1), 中间或者头部删除/插入效率为0(N);

(2) 扩容时候需要将原先数据拷贝新容器中并且释放旧空间, 消耗较多;

(3) 扩容2倍可能到一定程度会有很多使用不完, 浪费了.

3. 链表:

3.1 概念:

        物理存储结构不连续, 但是逻辑存储结构是连续的, 采用指针链接起来的结构.

包含单向/双向; 带头/不带头; 循环/不循环这几种链表;

3.2 结构:

        就是由数据和指向下一个链表的指针组成的.

3.3 实现:

(1) 打印:

        结点遍历即可打印每个结点的值.

void SListPrint(SListNode* plist)
{SListNode* cur = plist;while(cur != nullptr){printf("%d-> ", cur->data);cur = cur->next;}printf("NULL\n");
}

(2) 增加结点:

        申请创建一个结点, 然后添加数据.

SListNode* BuySListNode(SLTDataType x)
{SListNode* node = (SListNode*)malloc(sizeof(SListNode));if(node == nullptr){printf("malloc fail\n");exit(-1);}node->data = x;node->next = nullptr;return node;
}

(3) 单链表头插:

        为啥要SListNode**类型做形参呢? 要修改头指针的指向, 所以使用到二级指针.

void SListPushFront(SListNode** pplist, SLTDataType x)
{SListNode* newnode = BuySListNode(x);newnode->next = *pplist;*pplist = newnode;
}

(4) 单链表尾插:

        找到尾部, 然后进行插入即可.

void SListPushBack(SListNode** pplist, SLTDataType x)
{SListNode* newnode = BuySListNode(x);if(*pplist == nullptr){*pplist = newnode;}else{SListNode* tail = *pplist;while(tail->next != nullptr){tail = tail->next;}tail->next = newnode;}
}

 (5) 给定位置之后插入:

        先将pos->next的那个结点用newnode指向, 再改变pos的指向newnode.

void SListInsertAfter(SListNode* pos, SLTDataType x)
{assert(pos);SListNode* newnode = BuySListNode(x);newnode->next = pos->next;pos->next = newnode;
}

(6) 在给定位置之前插入:

        先找到指定位置的之前位置, 然后改变之前结点的下一个结点指向, 在插入newnode结点. 如果插入是头结点的话也要注意头结点处理.

void SListInsertBefore(SListNode** pplist, SListNode* pos, SLTDataType x)
{assert(pos);SListNode* newnode = BuySListNode(x);if(pos == *pplist){newnode->next = pos;*pplist = newnode;}else{SListNode* prev = *pplist;while(prev->next != pos){prev = prev->next;}newnode->next = prev->next;prev->next = newnode;}
}

(7) 头删:

        将头结点先变成头的下一个结点, 然后再释放结点.

void SListPopFront(SListNode** pplist)
{if(*pplist == nullptr){return;}else{SListNode* tmp = *pplist;*pplist = (*pplist)->next;free(tmp);tmp = nullptr;}
}

(8) 尾删:

        先找到尾结点, 和次尾结点, 之后就将结点进行尾删除, 然后将次尾结点下一个结点置空. 

void SListPopBack(SListNode** pplist)
{if(*pplist == nullptr){//头结点为空return;}else if((*pplist)->next == nullptr){//只要一个结点;free(*pplist);*pplist = nullptr;}else{SListNode* prev = *pplist;SListNode* tail = (*pplist)->next;while(tail->next != nullptr){prev = tail;tail = tail->next;}free(tail);tail = nullptr;prev->next = nullptr;}
}

(9) 删除给定位置之后的结点:

        找到pos后面一个结点after, 将pos下一个结点改变, 然后再将after释放.

        

void SListEraseAfter(SListNode* pos)
{assert(pos);if(pos->next == nullptr){return;}SListNode* after = pos->next;pos->next = after->next;free(after);after = nullptr;
}

(10) 删除给定位置的结点:

               先判断pos是否为pplist头结点, 头结点删除置空, 不是就要找到pos前一个结点然后进行结点改变, 删除pos结点.

void SListEraseCur(SListNode** pplist, SListNode* pos)
{assert(pos);if(pos == *pplist){*pplist = pos->next;free(pos);pos = nullptr;}else{SListNode* prev = *pplist;while(prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = nullptr;}
}

(11) 查找数据:

SListNode* SListFind(SListNode* plist, SLTDataType x)
{SListNode* cur = plist;while(cur != nullptr){if(cur->data == x)return cur;cur = cur->next;}return nullptr;
}

(12) 修改数据:

void SListModify(SListNode* pos, SLTDataType x)
{pos->data = x;
}

3.4 双链表实现:

(1) 双链表结构:

typedef int LTDataType;typedef struct ListNode
{LTDataType data;struct ListNOde* prev;struct ListNode* next;
}ListNode;

(2) 初始化结点和创建结点:

        初始化一个值为-1的结点, 然后进行结点处理, 由于头结点的前后指针都是指向自己的.

ListNode* BuyListNode(LTDataType x)
{ListNode* node = (ListNode*)malloc(sizeof(ListNode));if(node == nullptr){printf("malloc fail!");exit(-1);}node->data = x;node->prev = nullptr;node->next = nullptr;
}ListNode* ListInit()
{ListNode* phead = BuyListNode(-1);phead->prev = phead;phead->next = phead;return phead;
}

(3) 销毁链表:

        两个结点指针就可以删除, 进行迭代删除.

        

void ListDestory(ListNode* phead)
{assert(phead);ListNode* cur = phead->next;ListNode* next = cur->next;while(cur != phead){free(cur);cur = next;next = next->next;}free(phead);
}

(4) 打印:

void ListPrint(ListNode* phead)
{assert(phead);ListNode* cur = phead->next;while(cur != phead){printf("%d ", cur->data);cur = cur->next;}printf("\n");
}

(5) 查找元素:

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 nullptr;
}

(6) 头插结点:

        先找到头的后一个结点, 再进行插入;

void ListPushFront(ListNode* phead, LTDataType x)
{assert(phead);ListNode* newnode = BuyListNode(x);ListNode* front = phead->next;phead->next = newnode;newnode->prev = phead;newnode->next = front;front->next = newnode;
}

(7) 尾插结点:

        先找到最后一个结点; 就是第一个结点的prev结点. 

void ListPushBack(ListNode* phead, LTDataType x)
{assert(phead);ListNode* newnode = BuyListNode(x);ListNode* tail = phead->prev;newnode->next = phead;phead->prev = newnode;tail->next = newnode;newnode->prev = tail;
}

(8) 在指定位置插入结点:

        先找到要插入结点的前一个结点, 然后将头一个结点和newnode结点之间连接起来.

void ListInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* before = pos->prev;ListNode* newnode = BuyListNode(x);before->next = newnode;newnode->prev = before;newnode->next = pos;pos->prev = newnode;
}

(9) 头删:

        

void ListPopFront(ListNode* phead)
{assert(phead);//这里有哨兵位头结点;assert(phead->next != nullptr);ListNode* front = phead->next;ListNode* newfront = front->next;phead->next = newfront;newfront->prev = phead;free(front);
}

(10) 尾删:

void ListPopBack(ListNode* phead)
{assert(phead);assert(phead->next != nullptr);ListNode* tail = phead->prev;ListNode* newtail = tail->prev;newtail->next = phead;phead->prev = newtail;free(tail);
}

 (11) 删除指定位置结点:

     

void ListErase(ListNode* pos)
{assert(pos);ListNode* before = pos->prev;ListNode* after = pos->next;before->next = after;after->prev = before;free(pos);
}

(12) 链表判空:

        只要当phead->next对于phead那么就只要哨兵位的头结点, 直接为空.

bool ListEmpty(ListNode* phead)
{assert(phead);return phead->next == phead;
}

(13) 记录结点个数:

int ListSize(ListNode* phead)
{assert(phead);int count = 0;ListNode* cur = phead;while(cur != phead){count++;cur = cur->next;}return count;
}

3.5 C++版本单链表和双链表:

3.6 顺序表和链表的区别:

(1) 空间上顺序表的物理内存连续, 但是链表不连续;

(2) 顺序表支持随机访问, 但是链表不支持;

(3) 顺序表在任意插入删除效率比较低需要数据搬离, 但是链表只需要改变指针指向即可;

(4) 扩容顺序表需要空间申请和释放, 链表不需要.

(5) 顺序表主要运用需要大量查询, 链表就是随机删除插入的场景;

(6) 顺序表缓存利用高, 链表低等.