数据结构
时间复杂度(时间复杂度及空间复杂度)
摩尔定律(每18个月运行内存都会更新,空间复杂度不再特变关注)
- 用常数1取代运行时间中所有加法常数
- 在修改后的运行次数函数中,只保留最高阶项
- 如果最高阶项存在且不是1,则去除与这个项目相乘的常数。得到的结果就是大O阶
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
|
x=0; for(i=1;i<=n;i++) for(j=1;j<=n-i;j++) x++;
i=1; while(i<=n) i=i*3;
void Func4(int N) { int count=0; for(int k=00;k<100;++k) { ++count; } printf("%d\n",count); }
const char * strchr(const char * str ,int character)
while(*str) { if(*str==character) return str; else ++str; }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| 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; } } }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
| int BnarySearch(int* a,int n,int x) { assert(a); int begin=0; int end=n; while(begin<end) { int mid=begin+((end-begin)>>1); if(a[mid]<x) begin=mid+1; else if(a[mid]>x) end=mid; else return mid; } return -1; }
|
1 2 3 4 5 6 7 8
| long long Fib(size_t N) { if(N<3) return 1; return Fib(N-1)+Fib(N-2); }
|
消失的数字
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
|
int missingNumber(int* nums,intt numsSize) { int x=0; for(int i=0;i<=numsSize;++i) { x^=i; } for(int i=0;i<numsSize;++i) { x^=num[i]; } return x; }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
|
int[]arr={1,2,3,4,5,6,7,6,5,4,3,2,1}; int x=0; for(int i=0;i<arr.length;i++) { x=x^arr[i]; }
int []arr={1,2,3,4,5,6,7,3};
int x=0; for(int i=0;i<arr.length;i++) { x=x^arr[i]; } for(int i=1;i<=7;i++) { x=x^i; } return x;
|
旋转数组
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
|
void Reverse(int* nums,int left,int right) { while(left<right) { int temp=num[left]; num[left]=num[right]; num[right]=temp; ++left; --right; } } void rotate(int* num,int numsSize,int k) { if(k>=numsSize) k%=numsSize; Reverse(nums,0,numsSize-k-1); Reverse(num,numsSize-k,numsSize-1); Reverse(nums,0,numsSize-1); }
|
顺序表
本质就是数组,但是存储的数据不能跳跃要连续
缺陷:
1.空间不够了需要增容,需要付出代价
2.为避免频繁扩容,我们基本都是扩2倍,空间浪费
3.顺序表要求数据从开始位置连续存储,那么我们在头部或者中间位置插入删除数据就需要挪动数据
realloc扩容有两种方式
- 原地扩容,后面如果有足够大的内存空间,返回原空间地址,代价小
- 异地扩容 ,如果后面没有足够大的内存空间,会找一块足够大的空间,将原空间内容拷贝过来并释放原空间,返回的是新空间地址,代价大
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| #prama once #define N 100 typedef SLDataTpye;
typedef struct SeqList { SLDataType* a; int size; int capasity; }SL;
void SeqListInit(SL* ps); void SeqListPushBack(SL* ps,SLDataType x); void SeqListPopBack(SL* ps); void SeqListPushFront(SL* ps,SLDataType x); void SeqListCheckCapacity(SL* ps); void SeqListPopFront(SL* ps);
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
|
void SeqListInit(SL* ps) { ps.a=NULL; ps.size=ps.capacity=0; }
void SeqListCheckCapacity(SL* ps); { if(ps->size==ps->capasity) { int capasity=ps->capasity==0? 4:ps->capasity; SLDataType* tmp=(SLDataType*)realloc(ps->a,newcapacity*sizeof(SLDataType)); if(tmp==NULL) { printf("realloc fail\n") exit(-1); } ps->a=tmp; ps->capacity=newcapacity; } }
void SeqListPushBack(SL* ps,SLDataType x) { SeqListCheckCapacity(ps); ps->a[ps->size]=x; ps->size++; }
void SeqListPushBack(SL* ps,SLDataType x); void SeqListPopBack(SL* ps); void SeqListPushFront(SL* ps,SLDataType x); void SeqListPopFront(SL* ps);
|
1 2 3 4 5 6 7 8 9 10 11 12
| #include "SeqList.h" void SeqListInit() { SL s1; SeqListInit(s1); } int main() { TestSeqList2(); return 0; }
|
1 2 3 4 5 6 7 8 9 10 11 12
| #include "SeqList.h" void TestSeqList1() { SL s1; SeqListInit(&s1); SeqListPushBack(&s1,1); SeqListPushBack(&s1,2); SeqListPushBack(&s1,3); SeqListPushBack(&s1,4); SeqListPrint(&s1); }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102
| void SeqListPushFront(SL* ps,SLDataType x) { SeqListCheckCapacity(ps); int end=ps->size-1; while(endl>=0) { ps->a[end+1]=ps->a[end]; --end; } ps->a[0]=x; ps->size++; }
void TestSeqList2() { SL s1; SeqListInit(&s1); SeqListPushBack(&s1,1); SeqListPushBack(&s1,2); SeqListPushBack(&s1,3); SeqListPushBack(&s1,4); SeqListPrint(&s1); SeqListPushFront(&s1,10); SeqListPushFront(&s1,20); SeqListPushFront(&s1,30); SeqListPrint(&s1); SeqListPopFont(&s1); }
void SeqListPopFont(SL*) { assert(ps->size>0); int begin=1; while(begin<size) { ps->a[begin-1]=ps->a[begin]; ++begin; } }
int SeqListFind(SL* ps,SLDataType x) { for(int i=0;i<ps->size;i++) { if(ps->a[i]==x) { return i; } } return -1; }
void SeqListInsert(SL* ps,int pos,SLDataType x); {
assert(pos>=0&&pos<=ps->size) SeqListCheckCapacity(ps); int end=ps->size-1; while(end>=pos) { ps->a[end+1]=ps->a[end]; end--; } ps->a[pos]=x; ps->size++; }
void SeqListEarse(SL* ps,int pos); { assert(pos>=0 && pos<ps->size); int begin=pos+1; while(begin<ps->size) { ps->a[begin-1]=ps->a[begin]; ++begin; } ps->size--; }
|
链表
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147
| void SListPrint(SLTNode* phead) { SLTNode* cur=phead; while(cur!=NULL) { printf("%d->",cur->data); cur=cur->next; } }
void SListPushBack(SLTNode** pphead,SLTDateType x) { SLTNode* newnode=(SLTNode*)malloc(sizeof(SLNode)); newnode->data=x; newnode->next=NULL; if(*pphead==NULL) { *pphead=newnode; } else { SLTNode* tail=*pphead; while(tail->next!=NULL) { tail=tail->next; } tail->next=newnode; } }
void SListPushFront(SLTNode** pphead,SLTDateType x) { SLTNode* newnode=BuyListNode(x);
newnode->next=*pphead; *pphead=newnode; }
void SListPopBack(SLTNode**pphead) { if(*pphead==NULL) { return; } if((*pphead)->next==NULL) { free(*pphead); *pphead=NULL; } else { SLTNode* prev=NULL; SLTNode* tail=*pphead; while(tail->next!=NULL) { prev=tail; tail=tail->next; } free(tail); tail=NULL; prev->next=NULL; } }
void SListPopFront(SLTNode** pphead) { if(*pphead==NULL) return; SLTNode* next=(*pphead)->next; free(*pphead); *pphezd=next; }
SLTNode* SListFind(SLTNode* phead,SLTDateType x) { SLTNode* cur=phead; while(cur) { if(cur->data==x) { return cur; } else { cur=cur->next; } } return NULL; }
SLTNode* SListInsert(SLTNode* phead,STNode* pos,SLTDateType x) { SLTNode* newnode=BuyListNode(x); newnode->next=pos->next; pos->next=newnode; }
void SListEraes(SLTNode** pphead,SLTNode* pos) { if(*pphead==pos) { *pphead=pos->next; free(pos); } else { SListNode* prev=*pphead; while(prev->next!=pos) { prev=prev->next; } prev->next=pos->next; free(pos) } }
|
prev图如上
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| #pragma once #include<stdio.h> #include<stdlib.h> typedef int SLDataType typedef struct SListNode { SLDataType data; struct SListNode* next; }SLTNode;
void SListPrint(SLTNode* phead); void SListPushBack(SLTNode** pphead,SLTDateType x);
void SListPushFront(SLTNode** pphead,SLTDateType x);
SLTNode* SListFind(SLTNode* phead,SLTDataType x);
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
| #include"SList.h" void TestSList1() { SListNode* plist=NULL; SListPushBack(&plist,1); SListPushBack(&plist,2); SListPushBack(&plist,3); SListPushBack(&plist,4); SListPrint(plist); SListPushFront(&plist,1); SListPushFront(&plist,2); SListPushFront(&plist,3); SListPushFront(&plist,4); }
void TestSList2() { SListPushFront(&plist,1); SListPushFront(&plist,2); SListPushFront(&plist,3); SListPushFront(&plist,4); SListPopBack(&plist); SListPrint(plist); }
void TestSList3() { SListPushFront(&plist,1); SListPushFront(&plist,2); SListPushFront(&plist,3); SListPushFront(&plist,2); SListPushFront(&plist,4); SListPushFront(&plist,2); SLTNode* pos=SListFind(plist,2); int i=1; while(pos) { printf("第%d个pos节点:%p->%d\n",i++,pos,pos->data); pos=SListFind(pos->next,2) } pos=SListFind(plist,3) if(pos) { pos->data=30; } SListPrint(plist); }
int main() { return 0; TestSList1(); TestSList2(); }
|
二级指针(通过指针去改变指向空间的内容传一级指针,改变指针的指向传二级指针)
哨兵位的头节点不需要存储有效数据
head=tail=(ListNode*)malloc(sizeof(ListNode));
但是不能直接返回head哨兵位头节点
带头的循环链表
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
| void ListPushBack(LTNode* phead,LTDataType x) { assert(phead); LTNode* tail=phead->prev; LTNode* newnode=(LTNode*)malloc(sizeof(LTNode)); newnode->data=x; tail->next=newnode; newnode->prev=tail; newnode->next=phead; phead->prev=newnode }
void ListpopBack(LTNode* phead) { assert(phead); assert(phead->next!=phead); LTNode* tail=phead->prev; LTNode* tail->prev; free(phead->prev); tailPrev->next=phead; phead->prev=tailPrev; }
void ListPushFront(LTNode* phead,LTDateType x) { assert(phead); LTNode* newnode=BuyistNode(x); LTNode* next=phead->next; phead->next=newnode; newnode->prev=phead; newnode->next=next; next->prev=newnode; }
void ListPopFront() { assert(phead); assert(phead->next!=phead); LTNode* next=phead->next; LTNode* nextNext=next->next; phead->next=nextNext; nextNext->prev=phead; free(next); }
LTNode* ListFind(LTNode* phead,LTDateType x) { assert(phead); LTNode* cur=phead->next; while(cur!=phead) { if(cur->data==x) { return cur; } cur=cur->next; } return NULL; }
void ListInsert(LTNode* pos,LTDateType x) { assert(pos); LTNode* posPrev=pos->prev; LTNode* newnode=BuyListNode(x); posPrev->next=newnode; newnode->prev=posPrev; newnode->next=pos; pos->prev=newnode; }
|
在pos位置插入
下图相当于头插尾插
相比于顺序表链表cup命中率不高,有可能造成缓存污染(连续的物理空间造成的)
访问存储数据的内存位置,先看这个地址在不在缓存中,在就直接访问,不在就先加载到缓存再访问(加载到缓存不只加载着一个数据位置,而是预加载就近原则的一片数据内存位置)
栈
进行数据的插入和删除操作的一端称为栈顶,另一端为栈底
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| typedef int STDateType; typedef struct Stack { STDataType* a; int top; int capacity; }ST;
void StackInit(ST* ps); void StackDestory(ST* ps); void StackPush(ST* ps,STDataType x); void StackPop(ST* ps); STDataType StackTop(ST* ps); int StackSize(ST* ps); bool SackEmpty(ST* ps);
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80
|
void StackInit(ST* ps) { assert(ps); ps->a=NULL; ps->top=0; ps->capacity=0; }
void StackPush(ST* ps,STDataType x) { if(ps->pop==ps->capacity) { int newCapacity=ps->capacity==0?4:ps->capacity*2; STDataType* tmp=realloc(ps->a,sizeof(STDataType)*newCapacity); if(tmp==NULL) { printf("realloc fail\n"); exit(-1); } ps->a=tmp; ps->capacity=newCapacity; } assert(ps); ps->a[ps->top]=x; }
void StackDestory(ST* ps) { assert(ps); free(ps->a); ps->a=NULL; ps->capacity=0; }
void StackPop(ST* ps) { assert(ps); assert(ps->top>0); ps->top--; }
STDataType StackTop(ST* ps) { assert(ps); assert(!StackEmpty(ps)); return ps->a[ps->top-1]; }
bool StackEmpty(ST* ps) { assert(ps); if(ps->top==0) { return true; } else { return false; } }
int StackSize(ST* ps) { assert(ps); return ps-> }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| void TextStack() { ST st; StackInit(&st); StackPush(&st,1); StackPush(&st,2); StackPush(&st,3); StackPush(&st,4); while(!StackEmpty(&st)) { printf("%d",StackTop(&st)); StackPop(&st); } }
|
队列
只允许再一端进行插入操作,在另一端就进行删除数据的操作(先进先出)。进行插入操作的一端称为队尾,进行删除一端的操作称为队头。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
| typedef int QDataType; typedef struct QueueNode //队列用的是链表结构,这个结构体代表一个新节点 { struct QueueNode* next; QDataType data; }QueueNode;
typedef struct Queue { QueueNode* head; QueueNode* tail; }Queue;
void QueueInit(Queue* pq); void QueueDestory(Queue* pq); void QueuePush(Queue* pq,QDataType x); void QueuePop(Queue* pq); QDataType QueuFront(Queue* pq); QDataType QueuBack(Queue* pq); int QueueSize(Queue* pq); bool QueueEmpty(Queue* pq);
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80
|
void QueueInit(Queue* pq) { arrert(pq); qp->head=NULL; pq->tail=NULL; }
void QueueDestory(Queue* pq) { assert(pq); QueueNode* cur=pq->head; while(cur!=NULL) { QueueNode* next=pq->next; free(cur); } }
void QueuePush(Queue* pq,QDataType x) { assert(pq); QueueNode* newnode=(QueueNode*)malloc(sizeof(QueueNode)); newnode->data=x; newnode->next=NULL; if(pq->head==NULL) { pq->head=pq->tail=newnode; } else { pq->tail->next=newnode; pq->tail=newnode; } }
void QueuePop(Queue* pq) { assert(pq); assert(QueueEmpty(pq)); QueueNode* next=pq->head->next; free(pq->head); pq->head=next; if(pq->head==NULL) { pq->tail=NULL; } }
bool QueueEmpty(Queue* pq) { assert(pq); return pq->head==NULL; }
int QueueSize(Queue* pq) { assert(pq); int n=0; QueueNode* cur=pq->head; while(cur) { ++n; cur=cur->next; } return n; }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| void TextQueue1() { Queue q; QueueInit(&q); QueuePush(&q,1); QueuePush(&q,2); QueuePush(&q,3); QueuePush(&q,4); while(!=QueueEmpty(&q)) { QDataType front=QueueFront(&q); printf("%d",front); QueuePop(&q); } }
int main() { void TextQueue1(); return 0; }
|
串数组和广义表
子串:一个串中任意个连续字符组成的子序列称为子串
子串:子串第一个字符在主串中的位置
串相等:当且仅当两个串的长度相等并且各个对应位置上的字符都相同时,这两个串才是相等的 所有的空串都是相等的