一：表

1.1顺序表

实现-动态分配

image.png

  1. #include<stdlib.h>
  2. #define InitSize 10
  3. typedef struct(){
  4.     int *data;
  5.     int MaxSize;
  6.     int length;
  7. }SeqList
  9. int main(){
  10.     SeqList(L);
  11.     InitList(L);
  12.     IncreaseList(L,5);
  13.     return 0;
  14. }
  16. void InitList(SeqList &L){
  17.     L.data = (int *)malloc(InitSize*sizeof(int))
  18.     L.length=0;
  19.     L.maxSize=InitSIze;
  20. }
  22. void IncreaseSize(SeqList &L,int len){
  23.     int *p = L.data;
  24.     L.data=(int *)malloc((L.MaxSize+len)*sizeof(int));
  25.     for(i=0; i<L.lenght; i++){
  26.         L.data[i]=p[i];
  27.     }
  28.     L.MaxSize=L.MaxSize+len;
  29.     free(p)
  30. }

增加

  1. #include<stlibs>
  2. #define MaxSize 10
  3. typedef sturct{
  4.     int data[MaxSize];
  5.     int length;
  6. }SqeList;
  8. int mian()}{
  9.     SqeList L;
  10.     InitList(L);
  11.     InsertList(L, 3, 3);
  12.     return 0;
  13. }
  15. bool InsertList(SqeList &L, int n, int e){
  16.     if(i<1||i>L.length+1)
  17.         return false;
  18.     if(L.length>=MaxSize)
  19.         return false;
  20.     for(int j=L.length;j>=i;j--)
  21.         L.data[j]=L.data[j-1];
  22.     L.data[i-1]=e;
  23.     L.length++;
  24.     return ture;
  25. }

删除

  1. int mian(){
  2.     SeqList L;
  3.     InitList(L);
  4.     int e =-1;
  5.     if(DeleteList(L,3,e))
  6.         print("success=%d\n",e)
  7.     else
  8.         print("fail\n")
  9.     return 0;
  10. }
  11. bool DeleteList(SqeList &L,int i,int &e){
  12.     if(i<1||i>L.length)
  13.         retrun false;
  14.     e=L.data[i-1];
  15.     for(int j=i;j<L.length;j++){
  16.         L.data[j-1]=L.data[j];
  17.     }
  18.     L.length--;
  19.     return true;
  20. }

按位查找

  1. //静态分配
  2. #define MaxSize 10
  3. typedef struct{
  4.     int data[MaxSize];
  5.     int length;
  6. }
  7. //动态分配
  8. #define InitSize 10
  9. typedef struct{
  10.     ElemType *data;
  11.     int MaxSize;
  12.     int lenght;
  13. }
  14. ElemType GETElem(SeqList &L, int i){
  15.     return L.date[i-1];
  16. }

按值查找

  1. typedef struct{
  2.     int 
  3. }

1.2单链表

定义

  1. typedef struct LNode{
  2.     ElemType data;
  3.     struct LNode *next;
  4. }LNode, *LinkList;
  6. #没有头节点的单链表
  7. typedef struct LNode{
  8.     Elemtype data;
  9.     struct LNode *next;
  10. }LNode, *LinkList;
  11. bool InitList(LinkList &L){
  12.     L = NULL;
  13.     return true;
  14. }
  15. void test(){
  16.     LinkList L;
  17.     InitList(L);
  18. }
  19. bool Empty(LinkList L){
  20.     if(L==NULL)
  21.         return true;
  22.     else 
  23.         return false;
  24. }
  25. bool Empty(LinkList L){
  26.     return (L==NULL)
  27. }
  29. #有头节点的单链表
  30. #1.1
  31. typedef struct LNode{
  32.     ElemType data;
  33.     struct LNode *next
  34. }LNode, *LinkList;
  35. #1.2
  36. bool InitList(LinkList &L){
  37.     L = (LNode *) malloc(sizeof(LNode));
  38.     if (L==null)
  39.         return false;
  40.     L->next = NULL;
  41.     return ture;
  42. }
  43. #0
  44. #
  45. void test(){
  46.     LinkList L;
  47.     InitList(L);
  48. }
  49. #2 判断空表
  50. bool Empty(LinkList L){
  51.     return (L->next==NULL)
  52. }

插入(按位插入)

bool 

  1. #现在要在位序为i的地方插入数据e(带头节点)
  2. #找到位置i-1,在后面插入数据
  3. bool ListInsert(LinkList &L, int i, ElemType e){
  4.     if(i<1)
  5.         return false;
  6.     LNode *p;
  7.     ********************************
  8.     #循环找到第i-1个节点
  9.     int j=0;
  10.     p = L;
  11.     while(!p=NULL && j<i-1){
  12.         p = p->next;
  13.         j++;
  14.     }
  15.     ********************************
  16.     if(p==NULL)
  17.         return false;
  18.     LNode *s=(LNode *)malloc(sizeof(LNode));
  19.     s->data = e;
  20.     s->next=p->next;
  21.     p->next=s;
  22.     return true;  
  23. }
  25. #不带头节点
  26. #插入第一个节点的操作与其他节点不同
  27. bool ListInsert(LinkList &L, int i, ElemType e){
  28.     if(i<1)
  29.         retrun false;
  30.     if(i == 1){
  31.         LNode *s = (LNode *)malloc(sizeof(LNode));
  33.     }
  34.     #j=1代表是
  35.     int j=1;
  37. }
  40. #指定结点的后插操作
  41. bool InsertNextNode(LNode *p, ElemType e){
  42.     if (p == NULL)
  43.         return false;
  44.     LNode *s = (LNode *)malloc(sizeof(LNode));
  45.     if (s==NULL)
  46.         return false;
  47.     s->date = e;
  48.     s->next = p->next;
  49.     p->next = s;
  50.     return true;
  51. }
  53. bool InsertPriorNode(LNode *p,ElemType e){
  54.     if(p==NULL)
  55.         return false;
  56.     LNode *s = (LNode *)malloc(sizeof(LNode));
  57.     if(s==NULL)
  58.         return false;
  59.     s->next = p->next;
  60.     p->next = s;
  61.     s->data=p->data;
  62.     p->date = e;
  63.     return true;
  64. }
  65. bool InserPriorNode(LNode *p, LNode *s){
  66.     if(p==NULL || s == NULL)
  67.         return false;
  68.     s->next = p->next;
  69.     p->next = s;
  70.     ElemType temp = s->data;
  71.     s->data = p->data;
  72.     p->data = temp;
  73.     return true;
  74. }
  1. bool ListDelte(LinkList &L, int i, ElemType &e){
  2.     int j = 0;
  3.     LNode * p;
  4.     p =L;
  5.     if(p!=NULL && j<i-1){
  6.         p =p->next;
  7.             j++;
  8.     }
  9.     if (p==NULL)
  10.         return false;
  11.        if(p->next == NULL)
  12.         return false;
  13.     LNode * q = p->next;
  14.     p->next =q->next;
  15.     e = q->data;
  16.     free(q);
  17.     return true;
  18. }

新建

  1. #尾插法
  4. #头插法

二：栈LIFO(只在一端进出)

联想记忆：坑
2.1基本操作
初始化(两种实现1.top=-1 2.top=0)

  • top=0,栈满为top==MaxSize
  • top=-1,栈满为top==MaxSize-1(下面代码top=-1) ```cpp

    define MaxSize 10

    typedef struct{ Elemtype data[Maxsize]; int top; }SeStack; void InitStack(SqStack &S){ S.top=-1; } void testStack(){ SqStack S; InitStack(S); }

bool StackEmpty(SqStack S){ if S.top==-1 return true; else return false; }

  1. 入栈
  2. ```cpp
  3. #把指针+1，再把e数据进栈
  4. #栈满要报错
  5. bool Push(SqStack &S, Elemtype e){
  6.     #top0为第一个数
  7.     if(S.top==MaxSize-1)
  8.         return false;
  9.     S.data[++S.top]=e;
  10.     return true;
  11. }

出栈

  1. #栈顶数据出栈（用e返回），再把指针-1;
  2. #栈空要报错
  3. bool POP(SqStack &s, Elemtype &e){
  4.     if(S.top==-1)
  5.         return false;
  6.     e = S.data[S.top];
  7.     top--;
  8.     return true;
  9. }

读栈顶

  1. bool ReadTop(SqStack &S, ElemType &e){
  2.     if(S.top==-1)
  3.         return false;
  4.     e = S.data[S.top];
  5.     return true;
  6. }

链栈（按照上面链的定义自己敲一遍基础操作的代码）

三：队列FIFO(一端进另一端出)

3.1顺序存储

联想记忆：排队
定义
image.pngimage.png

  1. #因为rear指向下一个应该插入的位置，故初始化的时候rear=front=0
  2. #define MaxSize 10
  3. typedef struct {
  4.     ElemType data[maxsize];
  5.     int front, rear;
  6. }SqQueue;
  8. void InitQueue(SqQueue &Q){
  9.     Q.rear=Q.front=0;
  10. }
  12. void testQueue(){
  13.     SeQueue Q;
  14.     InitQueue(Q);
  15. }
  17. bool QueueEmpty(SqQueue Q){
  18.     if(Q.rear=Q.front)
  19.         return true;
  20.     else
  21.         return false;
  22. }

入队

  1. #往队尾添加数据，并让rear+1，考虑到前面可能有空位置，故应让(rear+1)%MaxSize从而变为循环队列
  2. #队列已满则错误
  3. bool QueuePush(SqQueue &q, int i, Elemtype e){
  4.     if((Q.rear+1)%MaxSize==Q.front)
  5.         return false;
  6.     Q.data[Q.rear]=e;
  7.     Q.rear=(Q.rear+1)%MaxSize;
  8.     return ture;
  10. }

判断队列满
1.一般
image.png
2.设置一个size记录队列长度

3.设置一个tag记录上一次的动作是删除还是添加

出队

  1. #把队头的数据用x返回，并把front+1，考虑到循环性，让（front+1）%MaxSize
  2. #队列空则出错
  3. bool QueuePop(SqQueue &Q,Elemtype &e){
  4.     if(Q.rear==Q.front)
  5.         return false;
  6.     e=Q.data[Q.front];
  7.     Q.front=(Q.front+1)%MaxSize;
  8.     return ture;
  9. }

3.2链式存储

初始化

  1. #带头节点：申请一个头结点，并让front(头节点)和rear都指向它；接着让头节点next为NULL
  2. typedef struct LinkNode{
  3.     ElemType data;
  4.     struct LinkNode *next;
  5. }LinkNode;
  6. typedef struct {
  7.     LinkNode *front,*rear;
  8. }LinkQueue;
  9. void InitQueue(LinkQueue &Q){
  10.     Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));
  11.     Q.front->next=NULL;
  12. }
  13. void testLinkQueue(){
  14.     LinkQueue Q;
  15.     InitQueue(Q);
  16. }
  17. #判断为空：Q.front==Q.rear || front->next=NULL
  18. bool IsEmpty(LinkQueue &Q){
  19.     if(Q.front==Q.rear)
  20.         return true;
  21.     else
  22.         return false;
  23. }
  25. #不带头节点:front和rear全部指向NULL
  26. void InitQueue(LinkQueue &Q){
  27.     Q.front=NULL;
  28.     Q.rear=NULL;
  29. }
  30. #判断为空：front=NULL || rear=NULL
  31. bool IsEmpty(LinkQueue &Q){
  32.     if(Q.front==NULL)
  33.         return true;
  34.     else 
  35.         return false;
  36. }

入出

  1. #申请一个节点，把节点赋值后让它next为空(因为一定是添加到队尾的)；把队尾指针next给s，
  2. #                                                            并移动队尾指针到s上
  3. bool LinkQueuePush(LinkQueue &Q,Elemtype e){
  4.     LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
  5.     s.data = e;
  6.     s->next=NULL;
  7.     Q.rear->next=s;
  8.     Q.rear=s;
  9. }
  10. bool LinkQueuePop

四：串

4.1基本操作实现

4.1.1求子串

image.png

  1. #遍历pos到pos+len-1,依次赋值给Sub串，记得让Sun长度变为len
  2. #记得判断字串范围是否越界
  3. SubString(&Sub, S, pos, len)
  4. bool SubString(SString &Sub, SString S, int pos, int len){
  5.     if(pos+len-1>S.length)
  6.         return false;
  7.     for(int i = pos; i<pos+len;i++)
  8.         Sub.ch[i-pos+1]=S.ch[i];
  9.     Sub.length = len;
  10.     return true;
  11. }

4.1.2比较大小

image.png

  1. #同时遍历两个串，比较第一个不相同字符的大小。
  2. #若扫描过的所有字符都相同，则长度长的串更大
  3. StrCompare(S,T)
  4. int StrCompare(SString S, SString T){
  5.     for(int i=1;i<=S.length&&i<=T.length;i++){
  6.         if(S.ch[i]!=T.ch[i])
  7.             return S.ch[i]-T.ch[i];
  8.     }
  9.     return S.length-T.length;
  10. }

4.1.3定位操作

image.png

  1. #对主串从头到尾依次取出长度为3的字串，再比较子串
  2. int Index(SString S, SString T){
  3.     int i=1, n=StrLength(S), m= StrLength(T);
  4.     SString Sub;
  5.     while(i<=n-m+1){
  6.         SubString(sub, S, i, m)
  7.             if(StrCompare(Sub,T)!=0) ++i;
  8.         else return i;
  9.     }
  10.     return 0;
  11. }

4.2朴素模式匹配算法：(不用基本操作完成字符匹配)

image.pngimage.pngimage.png

  1. #用i,j逐个比较两串，并定义k作为主串匹配开始的标志符.ruo匹配失败，则继续下一个
  2. int Index(SString S, SString T){
  3.     int k=1,i=1,j=1;
  4.     while(i<=S.Length&&i<=T.Length){
  5.         if(S.ch[i]==T.ch[j]){
  6.             i++;
  7.             j++;
  8.         }else{
  9.             k++;
  10.             i=k;
  11.             j=1;
  12.         } 
  13.     }
  14.     if(j>T.length)
  15.         return k;
  16.     else 
  17.         return 0;
  18. }
  1. #课本代码没有另外定义一个k，而是用i，j之间的逻辑关系来表示（指针后退重新开始匹配）

4.3KMP算法**

image.png
image.png
image.png

  1. #和朴素匹配基本一样，只是不匹配时，不回溯i，只回溯j
  2. int KMP(SString S, String T){
  3.     int i=1,j=1;
  4.     int next[T.length+1];             #看上图
  5.     get_next(T, next);
  6.     while(i<=S.Length&&i<=T.Length){
  7.         if(j==0||S.ch[i]==T.ch[i]){   #j=0是特殊情况
  8.             i++;
  9.             j++;
  10.         }else{
  11.             j=next[j];
  12.         }
  13.     }
  14.     if(j>T.length)
  15.         return i-T.length;
  16.     else
  17.         return 0;
  18. }

4.3.1KMP算法的优化-nextval数组

g与l不匹配，next[4]=1,继续看g与l匹配，重复了
image.png
j=0时，i++；j++;所以l被跳过，匹配g与g
image.png