一.数据结构

1.定义

数据结构=数据+结构

1.数据元素是数据的基本单位，数据元素包括数据项和数据对象。

2.数据的逻辑结构：由数据元素之间的逻辑关系构成；数据的存储结构：数据元素及其关系在计算机存储器中的存储表示；数据的运算：施加在该数据上的操作。

2.逻辑结构

逻辑结构可以通过图表或者二元组表示，类型包括集合、线性结构、树形结构、图形结构。

3.存储结构

存储结构类型有顺序存储结构、链式存储结构、索引存储结构、哈希存储结构。

4.数据类型和抽象数据类型

1.数据类型是一族性质相同的值的集合和定义在此集合上的一组操作的总称，是某种程序设计语言中以实现的数据结构。例如C/C++语言中常用的数据类型，结构体类型，共同体类型。

2.抽象数据类型是指用户进行软件系统设计是从问题的数学模型中抽象出来的逻辑数据结构和逻辑数据结构上的运算。格式如下：

ADT 抽象数据类型名

{ 数据对象：数据对象的声明

​ 数据关系：数据关系的声明

​ 基本运算：基本运算的声明

}

数据类型和抽象数据类型是与数据结构密切相关的两个概念，容易混淆。

5.算法

1.目标：正确性、可使用性、可读性、健壮性、高效率和低存储量需求。

2.算法分析可以从两个维度去分析，分别是时间性能和空间性能。

3.时间性能的分析有两种方法事后统计法和事前估算法，可以通过时间复杂度的分析。

4.空间性能分析可以通过空间复杂度的分析。

二.线性表

一.定义

线性表是一个具有相同特性的数据元素的有限序列。

相同特性：所有元素属于同一数据类型。

有限：数据元素个数是有限的。

序列：数据元素由逻辑序号唯一确定。一个线性表中可以有相同值的元素。

基本运算：

1.初始化线性表InitList(&L)：构造一个空的线性表L。

2.销毁线性表DestroyList(&L)：释放线性表L占用的内存空间。

3.判线性表是否为空表ListEmpty(L)：若L为空表，则返回真，否则返回假。

4.求线性表的长度ListLength(L)：返回L中元素个数n。

5.输出线性表DispList(L)：线性表L不为空时，顺序显示L中各结点的值域。

6.求线性表L中指定位置的某个数据元素GetElem(L，i，&e)：用e返回L中第 i(1≤i≤n)个元素的值 。

7.定位查找LocateElem(L，e)：返回L中第一个值域与e相等的逻辑位序。若这样的元素不存在，则返回值为0 。

8.插入一个数据元素ListInsert(&L，i，e)：在L的第i(1≤i≤n)个元素之前插入新的元素e，L的长度增1 。

9.删除数据元素ListDelete(&L，i，&e)：删除L的第i(1≤i≤n)个元素，并用e返回其值，L的长度减 1 。

二.普通线性表

1.顺序表

​ 线性表的顺序存储结构：把线性表中的所有元素 按照顺序存储方法进行存储。

typedef struct 
 {     ElemType data[MaxSize];
        int length;
} SqList;    //顺序表类型

​ 其中data成员存放元素，length成员存放线性表的实际长度。优点

存储密度大：无须为表示线性表中元素之间的逻辑关系而增加额外的存储空间。

具有随机存取特性。

缺点

插入和删除操作需要移动大量元素。

初始空间大小分配难以掌握。

2.链表

线性表的链式存储结构：线性表中每个结点最多只有一个的前驱结点和一个后驱结点。

设计链式存储结构时，每个逻辑结点存储单独存储，为了表示逻辑关系，增加指针域。

优点

由于采用结点的动态分配方式，具有良好的适应性。

插入和删除操作只需修改相关指针域，不需要移动元素。

缺点

存储密度小：为表示线性表中元素之间的逻辑关系而需要增加额外的存储空间(指针域)。

不具有随机存取特性。

(1) 单链表

每个物理结点增加一个指向后继结点的指针域 –>单链表。

typedef struct LNode     	   //定义单链表结点类型
{      ElemType data;
        struct LNode *next;     //指向后继结点
}  LinkNode;

头插法：

void CreateListF(LinkNode *&L，ElemType a[]，int n)
{    LinkNode *s;
     int i;
     L=new LNode;
     L->next=NULL;		//创建头结点，其next域置为NULL
     for (i=0;i<n;i++)		//循环建立数据结点
     {	
     	s=new LNode;
	s->data=a[i];		//创建数据结点*s
	s->next=L->next;	//将*s插在原开始结点之前，头结点之后
	L->next=s;
      }
}

尾插法：

void CreateListR(LinkNode *&L，ElemType a[]，int n)
{     LinkNode *s，*r;
       int i;
       L=new LNode;  //创建头结点
       r=L;			//r始终指向尾结点，开始时指向头结点   
       for (i=0;i<n;i++)	//循环建立数据结点
       {	
       		s=new LNode;
		s->data=a[i];	//创建数据结点*s
		r->next=s;	//将*s插入*r之后
		r=s;
        }
        r->next=NULL;	//尾结点next域置为NULL
}

(2) 双链表

在线性表的链式存储结构中，每个物理结点增加一个指向后继结点的指针域和一个指向前驱结点的指针域 –>双链表。

优点

从任一结点出发可以快速找到其前驱结点和后继结点.

从任一结点出发可以访问其他结点。

typedef struct DNode       	//双链表结点类型
  {     ElemType data;
         struct DNode *prior;    	//指向前驱结点
         struct DNode *next;     	//指向后继结点
 }   DLinkNode;

插入：

s->next = p->next
p->next->prior = s
s->prior = p
p->next = s

删除：

p->next->next->prior = p
p->next = p->next->next

(3) 循环链表

循环单链表：将表中尾结点的指针域改为指向表头结点，整个链表形成一个环。由此从表中任一结点出发均可找到链表中其他结点。

循环双链表：形成两个环。优点

可以循环查找。

可以通过头结点快速找到尾结点。

删除尾结点、在尾结点前后插入一个结点的时间均为O(1)。

(4) 有序表

**所谓有序表，是指这样的线性表，其中所有元素以递增或递减方式有序排列。

可提高算法效率。

插入：

void ListInsert(SqList *&L，ElemType e)
{     int i=0，j;
      while (i<L->length && L->data[i]<e)
          i++;			//查找值为e的元素
      for(j=ListLength(L);j>i;j--)	//将data[i..n]后移一个位置
          L->data[j]=L->data[j-1]; 
      L->data[i]=e;
      L->length++;		//有序顺序表长度增1
}

void ListInsert(LinkNode *&L，ElemType e)
{     LinkNode *pre=L，*p;

      while (pre->next!=NULL && pre->next->data<e)
          pre=pre->next; 	//查找插入结点的前驱结点*pre

      p=new LNode;
      p->data=e;		//创建存放e的数据结点*p
      p->next=pre->next;	//在*pre结点之后插入*p结点
      pre->next=p;

}

二路归并：

void UnionList(SqList *LA，SqList *LB，SqList *&LC)
{     int i=0，j=0，k=0;//i、j分别为LA、LB的下标，k为LC中元素个数
      LC=(SqList *)malloc(sizeof(SqList)); 		//建立有序顺序表LC
      while (i<LA->length && j<LB->length)
      {		
      		if (LA->data[i]<LB->data[j])
		{     
			LC->data[k]=LA->data[i];
	       		i++;k++;
		}
		else	//LA->data[i]>LB->data[j]
		{     
			LC->data[k]=LB->data[j];
	      		j++;k++;
		}
       }   
       while (i<LA->length)		//LA尚未扫描完，将其余元素插入LC中
       {	
       		LC->data[k]=LA->data[i];
			i++;k++;
     	}
     	while (j<LB->length)		//LB尚未扫描完，将其余元素插入LC中
     	{	
     		LC->data[k]=LB->data[j];
			j++;k++;
        }
    	LC->length=k;
}

三.栈

1.定义

栈是一种只能在一端进行插入或删除操作的线性表。

栈只能选取同一个端点进行插入和删除操作。

先进后出

2.基本运算

InitStack&s)：初始化栈。构造一个空栈s。

DestroyStack(&s)：销毁栈。释放栈s占用的存储空间。

StackEmpty(s)：判断栈是否为空:若栈s为空，则返回真；否则返回假。

Push(&S，e)：进栈。将元素e插入到栈s中作为栈顶元素。

Pop(&s，&e)：出栈。从栈s中退出栈顶元素，并将其值赋给e 。

GetTop (s，&)：取栈顶元素。返回当前的栈顶元素，并将其值赋给e。

顺序栈

typedef struct 
{      ElemType data[MaxSize]； 
        int top；		//栈顶指针
}  SqStack

栈空条件：top= – 1

栈满条件：top=MaxSize – 1

进栈e操作：top++;将e放在top处

退栈操作：从top处取出元素e top –=

链栈

typedef struct linknode
{     ElemType data;		//数据域
      struct linknode *next;	//指针域
}  LinkStNode;

栈空条件：s ->next=NULL

栈满条件：不考虑

进栈e操作：将包含e的结点插入到头结点之后

退栈操作：取出头结点之后结点的元素并删除之

应用：

1. 简单表达式求值

2. 将算术表达式转换成后缀表达式

3. 用栈求解迷宫问题

   三.队列

一.定义

队列只能选取一个端点进行插入操作，另一个端点进行删除操作。

先进先出

二.基本运算

InitQueue(&q)：初始化队列。构造一个空队列q。

DestroyQueue(&q)：销毁队列。释放队列q占用的存储空间。

QueueEmpty(q)：判断队列是否为空。若队列q为空，则返回真；否则返回假。

enQueue(&q,e)：进队列。将元素e进队作为队尾元素。

deQueue(&q,&e)：出队列。从队列q中出队一个元素，并将其值赋给e。

顺序队

typedef struct 
{     ElemType data[MaxSize]； 
      int front,rear；      //队首和队尾指针
}   SqQueue

队空条件：front = rear

队满条件：(rear+1)%MaxSize= front

进队e操作：rear=(rear+1)%MaxSize，将e放在rear处

出队操作：front=(front+1)%MaxSize，取出front处元素e

链队

typedef struct qnode
{      ElemType data;	//数据元素
        struct qnode *next;
}  DataNode;

typedef struct
{      DataNode *front;	//指向单链表队头结点
        DataNode *rear; 	//指向单链表队尾结点
}  LinkQuNode;

队空条件：front=rear=NULL

队满条件：不考虑。

进队e操作：将包含e的结点插入到单链表表尾

出队操作：删除单链表首数据结点应用：
求解迷宫问题

四.串

一.定义

串(或字符串)是由零个或多个字符组成的有限序列。

二.基本运算

StrAssign(&s，cstr)：将字符串常量cstr赋给串s，即生成其值等于cstr的串s。

StrCopy(&s，t)：串复制。将串t赋给串s。

StrEqual(s，t)：判串相等。若两个串s与t相等则返回真；否则返回假。

StrLength(s)：求串长。返回串s中字符个数。

Concat(s，t)：串连接:返回由两个串s和t连接在一起形成的新串。

SubStr(s，i，j)：求子串。返回串s中从第i(1≤i≤n)个字符开始的、由连续j个字符组成的子串。

InsStr(s1，i，s2)：插入。将串s2插入到串s1的第i(1≤i≤n+1)个字符中，即将s2的第一个字符作为s1的第i个字符，并返回产生的新串。

DelStr(s，i，j)：删除。从串s中删去从第i(1≤i≤n)个字符开始的长度为j的子串，并返回产生的新串。

RepStr(s，i，j，t)：替换。在串s中，将第i(1≤i≤n)个字符开始的j个字符构成的子串用串t替换，并返回产生的新串。

DispStr(s)：串输出。输出串s的所有元素值。

顺序串

#define MaxSize 100
typedef struct
{      char data[MaxSize];
        int length;
}  SqString;

链串

typedef struct snode 
{      char data;
       struct snode *next;
}  LinkStrNode;

模式匹配

BF算法

1.算法的思路是从s的每一个字符开始依次与t的字符进行匹配。

2.算法在字符比较不相等，需要回溯(即i=i-j+1)：即退到s中的下一个字符开始进行继续匹配。

3.最好情况下的时间复杂度为O(m)。

4.最坏情况下的时间复杂度为O(n×m)。

5.平均的时间复杂度为O(n×m)。

KMP算法

1.该算法较BF算法有较大改进，主要是消除了主串指针的回溯，从而使算法效率有了某种程度的提高。

2.设串s的长度为n，串t长度为m。

在KMP算法中求next数组的时间复杂度为O(m)，在后面的匹配中因主串s的下标不减即不回溯，比较次数可记为n，所以KMP算法平均时间复杂度为O(n+m)。

最坏的时间复杂度为O(n× m)。

void GetNext(SqString t,int next[])	 
{     int j, k;
      j=0;  k=-1;  next[0]=-1;
      while (j<t.length-1)
      {	
          if (k==-1 || t.data[j]==t.data[k])
          {      j++; k++;
	       	 next[j]=k;
	  }
	  else  
              k=next[k];
      }
}

void GetNext(SqString t,int nextval[])	 
{     int j, k;
      j=0;  k=-1;  nextval[0]=-1;
      while (j<t.length-1)
      {	
          if (k==-1 || t.data[j]==t.data[k])
	  {      j++; k++;
	         if(t.data[j]!=t.data[k])
                     nextval[j]=k;
     		 else
                     nextval[j]=nextval[k];
	  }
	  else  
               k=nextval[k];
      }
}

三.总结

1. 在学习栈、队列和串的过程中，会遇到许多困难，我都是通过看源码，然后画出过程，慢慢理解。2. 在编程实践中，总是遇到能运行，但是答案错误，看自己的代码也看不出来问题，我就只能通过设置断点，一步一步的地调试，发现出问题。