荐 浙大-数据结构笔记-基本概念和线性结构

数据结构

1.抽象数据类型（Abstract Data Type）

数据类型

• 数据对象集
• 数据集合相关联的操作集

抽象：描述数据类型的方法不依赖于具体实现

• 与存放数据的机器无关
• 与数据结构的物理结构无关
• 与实现操作的算法和编程语言无关

Ps：只关心是什么，不关心怎么做到，

2.算法：

• 算法（Algorithm）

  • 一个有限指令集
  • 接收一些输入（有些情况下不需要输入）
  • 产生输出
  • 一定在有限步骤之后终止（不同于程序，比如操作系统程序一直跑）
  • 每一条指令
    • 有充分明确的目标，不可以有歧义
    • 计算机能处理的范围之内
    • 描述应不依赖于任何一种计算机语言以及具体的实现手段

• 什么是好的算法

  • 空间复杂度S（n）----根据算法写成的程序在执行时占用存储单元的长度。这个长度往往与输入数据的规模有关。空间复杂度过高的算法可能导致使用的内存超限，造成程序的非正常中断。
  • 时间复杂度T（n）----根据算法写成的程序在执行时耗费时间的长度。这个长度往往也与输入数据的规模有关。时间复杂度过高的低效算法可能导致我们在有生之年都等不到运行结果。

• 分析算法效率一般关心下面两种复杂度

  • 最坏情况复杂度T_worst（n）
  • 平均复杂度T_avg（n）
  • T_avg（n）<= T_worst（n）(分析平均复杂度很难，一般用最坏情况复杂度)

• 复杂度的渐进表示方法

  • T(n)=O(f(n))表示存在常数C>0,n₀>0使得当n>=n₀时有T（n）<=C*f（n）上界（一般取最小上界）

  • T(n)=Ω(g(n))表示存在常数C>0,n₀>0使得当n>=n₀时有T（n）>=C*g（n）下界 （一般取最大下界）

  • $T(n)=\Theta (h(n))$表示同时有T(n)=O(h(o))和T(n)=Ω(h(n))

ps：一般遇到O(n²)算法想办法转换为O($nlog n$)

• 若两段算法分别有复杂度$T_1(n)=O(f_1(n))$和$T_2(n)=O(f_2(n))$,则
  • $T_1(n)+T_2(n)=max(O(f_1(n)),O(f_2(n)))$
  • $T_1(n)\times T_2(n)=O(f_1(n)\times f_2(n))$
• 若T(n)是关于n的k阶多项式，那么$T(n)=\Theta (n^k)$
• 一个for循环的时间复杂度等于循环次数乘以循环体代码的复杂度
• if-esle结构的复杂度取决于if的条件判断复杂度和两个分支部分的复杂度，总体复杂度取三者中最大
• 算法效率高可能有副作用，比如说正确性不是特别明显

线性结构

线性表

线性表：由同类型数据元素构成的有序序列的线性结构

• 表中元素个数称为线性表的长度
• 线性表没有元素时，称为空表
• 表起始位置称表头，表结束位置称表尾

线性表的抽象数据类型描述

• 数据名称:线性表（List）
• 数据对象集：线性表是n（>=0）个元素构成的有序序列（a₁，a₂，…a_n）
• 操作集：线性表L∈List,整数i表示位置，元素X∈ElementType,线性表基本操作主要有:
  • List MakeEmpty():初始化一个空线性表L;
  • ElementType FindKth( int K, ListL):根据位序K，返回相应元素;
  • int Find( ElementType X, ListL ):在线性表L中查找X的第一次出现位置;
  • 4、void Insert( ElementType X, int i, List L):在位序i前插入-一个新元素X;
  • 5、void Delete( int i, ListL ):删除指定位序i的元素:
  • 6、int Length( ListL ):返回线性表L的长度n.

线性表的存储

顺序存储实现：利用数组的连续存储空间存放线性表的各元素

typedef struct LNode *List;
struct LNode{
ElementType Data[MAXSIZE];
int Last;//最后一个元素所在的位置
};
struct LNode L;
List PtrL;
L.Data[i]或Ptrl->Data[i]//访问下标为i的元素
L.Last+1或PtrL->Last+1//线性表的长度

1.初始化（建立空的顺序表）

List MakeEmpty( )
List PtrL;
PtrL = (List ) malloc( sizeof (struct LNode) ) ;
PtrL- >Last = -1;
return PtrL;
}

2.查找

/*平均比较次数（n+1）/2,平均性能O（n）*/
int Find( ElementType X，List PtrL )
int i=0;
while( i <= PtrL->Last && PtrL- >Data[i]!= X )
i++;
if (i > PtrL->Last) return -1; /*如果没找到，返回-1 */
else return i;/*找到后返回的是存储位置*/

3.插入（第$i(l\leq i\leq n+1)$个位置上插入一个值为X的新元素）

void Insert( ElementType X, int i, List PtrL )
{
int j;
if( PtrL->Last == MAXSIZE-1 ){/*表空间已满，不能插入*/
printf("表满" );
return;
}
if(i<1||i> PtrL->Last+2) {/*检查插入位置的合法性*/
printf("位置不合法" );
return;
}
for(j= PtrL->Last; j>= i-1;j--)
PtrL->Data[j+1] = PtrL->Data[j]; /*将 ai- an倒序向后移动*/
PtrL->Data[i-1] = X;/*新元素插入*/
PtrL->Last++;/*Last仍指向最后元素*/
return;

4.删除（删除表第i(l<=i<=n)个位置上的元素）

/*平均移动次数（n-1）/2,O(n)*/
void Delete( int i, List PtrL )
{ int j;
if(i<1 ||i> PtrL->Last+1 ) {/*检查空表及删除位置的合法性*/
printf (“不存在第%d个元素”, i);
return ;
for(j=i;j<= PtrL>Last; j++ )
PtrL->Data[j-1] = PtrL->Data[j];/*将 ai+1~ an顺序向前移动*/
PtrL->Last--;/*Last仍指向最后元素*/
return; 
}

线性表的链式存储实现

不要求逻辑上相邻的两个元素物理上也相邻；通过“链”建立起数据元素之间的逻辑关系

• 插入、删除 不需要移动数据元素，只需要修改“链”。

typedef struct LNode *List;
struct LNode{
ElementType Data;
List Next;
};
struct Lnode L;
List PtrL;

• 主要操作的实现

  • 1.求表长

  //时间性能为O(n)
  int Length ( List PtrL )
  { List p= PtrL;
  /* p指向表的第-一个结点*/
  int j= 0;
  while (p){
  p= p->Next;
  j++;/*当前p指向的是第j个结点*/ 
  return j;
  

  • 2.查找

    • (1).按序号查找：FindKth；

      List FindKth( int K, List PtrL )
      {
      List p= PtrL;
      int i= 1;
      while (p !=NULL &&i< K){
      p = p->Next;
      i++;
      if(i== K) return p;/*找到第K个，返回指针*/
      else return NULL;/*否则返回空*/
      }
      

    • （2).按值查找：Find

      List Find( ElementType X, List
      PtrL )
      {
      List p= PtrL;
      while ( p!=NULL && p->Data != X )
      p= p->Next;
      return p; 
      

  • 3.插入（在第i-1(1<=i<=n+1)个结点后插入一个值为X的新结点）

    • （1）先构造一个新结点，用s指向；
    • （2）再找到链表的第i-1个结点，用p指向
    • （3）然后修改指针，插入结点（p之后插入新结点是s）

    //平均时间复杂性，O(n/2)
    List Insert( ElementType X, int i, List PtrL )
    {
    List p, s;
    if(i==1){/*新结点插入在表头*/
    s = (List)malloc(sizeof(struct LNode)); /*申请、 填装结点*/
    s->Data = X;
    s->Next= PtrL; .
    return s;/*返回新表头指针*/
    }
    p = FindKth( i-1, PtrL );/*查找第i-1个结点*/
    if(p== NULL){/*第i-1个不存在，不能插入*/ 
    printf( "参数i错" );
    return NULL;
    }else {
    s = (List)malloc(sizeof(struct LNode);/*申请、填装结点*/
    s->Data= X;
    s->Next = p->Next;
    /*新结点插入在第i-1个结点的后面*/
    p->Next= S;
    return PtrL;
    }
    

  • 4.删除（删除链表的第i（l<=i<=n）个位置上的结点）

    • （1）先找到链表的第i-1个结点，用p指向；
    • （2）再用指针s指向要被删除的结点（p的下一个结点）
    • （3）然后修改指针，删除s所指结点
    • （4）最后释放s所指结点的空间

    //平均时间复杂性 O(n/2)
    List Delete( int i, List PtrL )
    { List p, s;
    if(i==1){/*若要删除的是表的第一个结点*/
    s= PtrL;/*s指向第1个结点*/
    if (PtrL!=NULL) PtrL = PtrL->Next;/*从链表中删除*/
    else return NULL;
    free(s);/*释放被删除结点*/
    return PtrL; .
    }
    p = FindKth( i-1, PtrL );/*查找第i-1个结点*/
    if(p== NULL){
    printf(“第%d个结点不存在”，i-1); return NULL;
    } else if( p->Next == NULL ){
    printf(“第%d个结点不存在”, i);
    return NULL;
    }else {
    s = p->Next;/*s指向第i个结点*/
    p->Next= s->Next;/*从链表中删除*/
    free(s);/*释放被删除结点*/
    return PtrL;
    

广义表

• 广义表是线性表的推广
• 对于线性表而言，n个元素都是基本的单元素
• 广义表中，这些元素不仅可以是单元素也可以是另一个广义表

typedef struct GNode *GList;
struct GNode{
int Tag;/*标志域: 0表示结点是单元素，1表示结点是广义表*/
union {/*子表指针域Sublist与单元素数据域Data复用，即共用存储空间*/
ElementType Data;
GList SubList;
} URegion;
GList Next;/*指向后继结点*/
};

多重链表

• 多重链表
  • 多重链表中结点的指针域会有多个，如前面例子包含了Next和SubList两个指针域；
  • 但包含两个指针域的链表并不一定是多重链表，比如在双向链表不是多重链表
  • 例如：十字链表（存储矩阵）
• 多重链表有广泛的用途：基本上如树，图这样相对复杂的数据结构都可以采用多重链表方式实现存储

堆栈

• 堆栈的抽象数据类型描述

  • 堆栈（Stack）：具有一定操作约束的线性表
  • 只在一端（栈顶，Top）做插入、删除
    • 插入数据：入栈（Push）
    • 删除数据：出栈（Pop）
    • 后入先出：Last In First Out（LIFO）

• 类型名称:堆栈(Stack)

• 数据对象集: 一个有0个或多个元素的有穷线性表。

• 操作集:长度为MaxSize的堆栈S ∈Stack,堆栈元素item∈ElementType

  • 1、Stack CreateStack( int MaxSize ): 生成空堆栈，其最大长度

    为MaxSize;

  • 2、int IsFull( Stack S, int MaxSize ):判断堆栈S是否已满;

  • 3、void Push( Stack s, ElementType item ):将元素item压入堆栈;

  • 4、int IsEmpty ( StackS); 判断堆栈S是否为空;

  • 5、ElementType Pop( StackS):删除并返回栈顶元素;

栈的顺序存储实现

• 栈的顺序存储结构通常由一个一维数组和一个记录栈顶元素位置的变量组成

#define MaxSize <储存 数据元素的最大个数>
typedef struct SNode *Stack;
struct SNode{
ElementType Data[MaxSize];
int Top;
};

• (1)入栈

  void Push( Stack PtrS,ElementType item)
  if ( PtrS->Top == MaxSize-1 ) {
  printf(“堆栈满”): return:
  }else {
  PtrS->Data[++(PtrS- >Top)] = item;
  return;
  

• (2)出栈

  ElementType Pop( Stack PtrS )
  {
  if(PtrS->Top==-1 ){
  printf(“堆栈空");
  return ERROR;/* ERROR是ElementType的特殊值，标志错误*/
  } else
  return ( PtrS->Data[(PtrS-> Top)--]);
  }
  

• [例]请用一个数组实现两个堆栈，要求最大地利用数组空间，使
  数组只要有空间入栈操作就可以成功。

• [分析]一种比较聪明的方法是使这两个栈分别从数组的两头开始
  向中间生长;当两个栈的栈项指针相遇时，表示两个栈都满了。

  #define MaxSize <存储数据元素的最大个数>
  struct DStack {
  ElementType Data[MaxSize];
  int Top1; /* 堆栈1的栈项指针*/
  int Top2;
  /* 堆栈2的栈项指针*/
  }S;
  S.Top1 = -1;
  S.Top2 = MaxSize;
  
  void Push( struct DStack *PtrS, ElementType item, int Tag )
  { /* Tag作为区分两个堆栈的标志，取值为1和2 */
  if ( PtrS->Top2 - PtrS->Top1 == 1) { /*堆栈满*/
  printf ("堆栈满") ;return ;
  }
  if ( Tag == 1 )/*对第一个堆栈操作*/
  PtrS->Data [++ (PtrS->Top1)] = item; 
  else
  /*对第二个堆栈操作*/
  PtrS->Data[--(PtrS->Top2)] = item; 
  }
  
  ElementType Pop( struct DStack *PtrS, int Tag ) 
  { /* Tag作为区分两个堆栈的标志，取值为1和2 */
  if( Tag==1){ /*对第一个堆栈操作 */
  if ( Ptrs->Top1 == -1 ) { /*堆栈1空*/
  printf (“堆栈1空") ;
  return NULL;
  } else return PtrS->Data [ (PtrS->Top1)--] ;
  } else { /*对第二个堆栈操作*/
  if ( PtrS->Top2 == MaxSize ) { /*堆栈2空*/
  printf (“堆栈2空") ; return NUlL;
  } else return PtrS->Data[ (PtrS->Top2)++] ; 
  }
  

堆栈的链式存储实现

栈的链式存储结构实际上就是一个单链表，叫做链栈。插入和删除操作只能在链栈的栈顶进行。

ps：链尾不能做Top，链头才会做Top

typedef struct SNode *Stack;
struct SNode{
ElementType Data;
struct SNode *Next;
};

Stack CreateStack ()
{ /*构建一个堆栈的头结点，返回指针*/
Stack S;
S = (Stack) malloc (sizeof (struct SNode) )
S->Next = NULL;
return S ;
    
int IsEmpty (Stack S)
{ /*判断堆栈s是否为空，若为空函数返回整数1,则返回0 */
return ( S->Next == NULL ) ;

void Push ( ElementType item, Stack S)
{ /*将元素item压入堆栈S */
//S是堆栈的头结点，链表实现不存在满的情况
struct SNode *TmpCell ;
TmpCell= (struct SNode *)malloc (sizeof (struct SNode)) ;
TmpCell->Element = item;
TmpCell->Next = S->Next;
s->Next = TmpCell;
}
    
ElementType Pop (Stack S)
{ /*删除并返回堆栈s的栈项元素*/
struct SNode *FirstCell ;
ElementType TopElem ;
if( IsEmpty( S ) ) {
printf("堆找空”) ; return NULL;
} else {
FirstCell = S->Next;
S->Next = FirstCell->Next;
TopElem = FirstCell ->Element ;
free (FirstCell) ;
re turn TopElem ;
}

中缀表达式转换为后缀表达式

➢从头到尾读取中缀表达式的每个对象，对不同对象按不同的情况处理。
①运算数:直接输出;
②左括号:压入堆栈;
③右括号:将栈项的运算符弹出并输出，直到遇到左括号(出栈，不输出) ;
④运算符:

• 若优先级大于栈顶运算符时， 则把它压栈;
• 若优先级小于等于栈项运算符时，将栈项运算符弹出并输出;再比
  较新的栈项运算符，直到该运算符大于栈顶运算符优先级为止，然
  后将该运算符压栈;

⑤若各对象处理完毕，则把堆栈中存留的运算符一并输出。

堆栈的其他应用

• 函数调用及递归实现
• 深度优先搜索
• 回溯算法
• …

队列

队列：具有一定操作约束的线性表

• 插入和删除操作：只能在一端插入，而在另一端删除
  • 数据插入：入队列（AddQ）
  • 数据删除：出队列（DeleteQ）
  • 先来先服务
  • 先进先出：FIFO

队列的抽象数据类型描述

• 类型名称：队列（Queue）
• 数据对象集：一个有0个或多个元素的有穷线性表
• 操作集：长度为MaxSize的队列Q∈Queque，队列元素item∈ElementType
  • 1、Queue CreatQueue( int MaxSize ): 生成长度为MaxSize的空队列;
  • 2、int IsFulIQ( Queue Q, int MaxSize ): 判断队列Q是否已满;
  • 3、void AddQ( Queue Q, ElementType item): 将数据元素item插入队列Q中;
  • 4、int IsEmptyQ( Queue Q): 判断队列Q是否为空;
  • 5、ElementType DeleteQ( Queue Q):将队头数据元素从队列中删除并返回。

队列的顺序存储实现

队列顺序存储结构通常由一个一维数组和一个记录队列头元素位置的变量front以及一个记录队列尾元素位置的变量rear组成

#define MaxSize <储存数据元素的最大个数>
struct QNode {
ElementType Data[ MaxSize ];
int rear;
int front;
};
typedef struct QNode *Queue;

顺环队列

无法区分空和满（rear和front相等无法区分空和满，）

• （1）使用额外标记，Size或者tag域（记录最后一次操作是插入还是删除，以此区分空还是满）
• （2）仅使用n-1个数组空间(一般采用这个)

//(1)入队列
void AddQ( Queue PtrQ, ElementType item)
if ( (PtrQ->rear+1) % MaxSize == PtrQ->front ) {
printf(“队列满");
return;
}
PtrQ->rear = (PtrQ->rear+1)% MaxSize;
PtrQ->Data[PtrQ->rear] = item;
       
//(2)出队列
ElementType DeleteQ ( Queue PtrQ )
{
if ( PtrQ->front == PtrQ->rear){
printf(“队列空");
return ERROR;
} else {
PtrQ->front = (PtrQ->front+1)% MaxSize;//front指向队列头的前一个
return PtrQ->Data[PtrQ->front];
}

队列的链式存储实现

队列的链式存储结构也可以用一个单链表实现。插入和删除操作分别在链表的两头进行：队列指针front（出队操作）和rear（进行插入操作）应该分别指向链表的头和尾（链表的末尾进行删除操作不行，链表的头进行插入和删除都可以）

struct Node{
ElementType Data;
struct Node *Next;
};
struct QNode{/*链队列结构*/
struct Node *rear;/*指向队尾结点*/
struct Node *front; /* 指向队头结点*/
};
typedef struct QNode *Queue;
Queue PtrQ;

//不带头结点的链表队列出队操作的一个示例
ElementType DeleteQ ( Queue PtrQ )
{ struct Node *FrontCell;
ElementType FrontElem;
if ( PtrQ->front == NULL) {
printf(“队列空"); return ERROR;
}
FrontCell = PtrQ->front;
if ( PtrQ->front == PtrQ->rear) /* 若队列只有一个元素*/
PtrQ->front = PtrQ->rear= NULL; /* 删除后队列置为空*/
else
PtrQ->front = PtrQ->front->Next;
FrontElem = FrontCell->Data;
free( FrontCell );/*释放被删除结点空间*/
return FrontElem;

链表实现多项式加法

算法思路:两个指针P1和P2分别指向这两个多项式第一~个结点， 不断循环:

• P1->expon==P2->expon:系数相加，若结果不为0，则作为结果多项式对应项
  的系数。同时，P1和P2都分别指向下一项;
• P1->expon>P2->expon:将P1的当前项存入结果多项式，并使P1指向下一项;
• P1->exponexpon: 将P2的当前项存入结果多项式，并使P2指向下一项;

Polynomial PolyAdd (Polynomial P1, Polynomial P2)
Polynomial front, rear, temp;
int sum;
rear = (Polynomial) malloc(sizeof(struct PolyNode));
front= rear; /*由front记录结果多项式链表头结点*/
while (P1 &&P2) /*当两个多项式都有非零项待处理时*/
switch ( Compare(P1->expon, P2->expon) ) {
        case 1:
            Attach( P1->coef, P1->expon, &rear);
            P1 = P1->link;
            break;
        case -1:
            Attach(P2->coef, P2->expon, &rear);
            P2= P2->link;
            break;
        case 0:
            sum = P1->coef+ P2->coef;
            if ( sum ) Attach(sum, P1->expon, &rear);
            P1 = P1->link;
            P2 = P2->link;
        break;
}
/*将未处理完的另一个多项式的所有节点依次复制到结果多项式中去*/
for(;P1; P1 = P1->link ) Attach(P1->coef, P1->expon, &rear);
for(;P2; P2 = P2->link )Attach(P2->coef, P2->expon, &rear);
rear->link = NULL;
temp = front;
front = front->link; /*令front指向結果多项式第一个非零项*/
free(temp); /* 释放临时空表头结点*/
return front;

void Attach( int C, int e, Polynomial *pRear )
Polynomial P;
P = (Polynomial)malloc(sizeof(struct PolyNode));
P->coef=c; /* 对新结点赋值*/
P->expon= e;
P->link= NULL;
(*pRear)->link= P;
*pRear= P; /* 修改pRear值*/ 

本文地址：https://blog.csdn.net/weixin_42117120/article/details/107318593