数据结构知识点总结（更新ing）

2019-10-04 本文已影响0人孟应杰

⭐ 我的网站: www.mengyingjie.com ⭐

1线性表

1.1线性表的基本操作

方法名	含义
InitList(&L)	初始化表。构造一个空的线性表。
Length(L)	求表长。返回线性表L的长度，即L中数据元素的个数。
LocateElem(L,e)	按值查找操作。在表L中查找具有给定关键字值的元素。
GetElem(L,i)	按位查找操作。获取表L中第i个位置的元素的值。
ListInsert(&L,i,e)	插入操作。在表L中的第i个位置上插入指定元素e.
ListDelete (&L,i, &e)	删除操作。刑除表L中第i个位置的元素，并用e返回删除元素的值。
PrintList(L)	输出操作。按前后顺序输出线性表L的所有元素值。
Empty(L)	判空操作。若L为空表，则返回true,否则返回false.
DestroyList (&L)	销毁操作。销毁线性表，并释放线性表L所占用的内存空间。

1.2线性表的顺序表示

1.2.1顺序表的定义

静态

#define MaxSize 50
typedef struct {
  ElemType data[MaxSize];
  int length;
}SeqList

动态

#define InitSize 100    //表长度的初始定义
typedef struct{
ElemType *data;         //指示动态分配数组的指针
  int MaxSi ze, length;   //数组的最大容量和当前个数
} SeqList;              //动态分配数组顺序表的类型定义
//初始化分配语句
L. data= (ElemType* ) malloc (sizeof (ElemType) *InitSize) ;
//C++的初始动态分配语句为
L.data=new ElemType [InitSize] ;

1.2.2顺序表上基本基本操作的实现

插入操作

bool ListInsert (SqList &L, int i, ElemType e) {
//本算法实现将元素e插入到顺序表L中第i个位置
  if(i<1I li>L. length+1)  //判断 i的范围是否有效
    return false;
  if (L. length>=MaxSize)  //当前存储空间已满，不能插入
    return false;
  for (int j=L. length;j>=i;j--) //将第 i个元素及之后的元素后移
    L.data[j]=L.data[j-1] ;
  L.data[i-1]=e;  //在位置i处放入e
  L. length++;  //线性表长度加1
    return true;
}

时间复杂度：
好 O(1) 坏 O(n) 平均 O(n)

删除操作

bool ListDelete (SqList &L,int i,Elemtype &e) {
//本算法实现删除顺序表L中第i个位置的元素
  if(i<1lli>L.length)  //判断i的范围是否有效
    return false;
  e=L.data[i-1];  //将被删除的元素赋值给e
  for(int j=i;j<L. length;j++)  //将第i个位置后的元素前移
    L.data[j-1]=L.data[j];
  L. length--;  //线性表长度减 1
  return t rue ;
}

时间复杂度：
好O(1) 坏(n) 平均O(n)

按值查询

int LocateElem (SqList L, ElemType e) {  
//本算法实现查找顺序表中值为e的元素，如果查找成功，返回元素位序，否则返回0
  int i;
  for(i=0; i<L. length; i++)
    if(L.data[i]==e)
      return i+1 ;  //下标为i的元素值等于e,返回其位序i+1
  return 0;  //退出循环，说明查找失败

时间复杂度：
好O(1) 坏O(n) 平均O(n)

1.3线性表的链式表示

1.3.1 单链表的基本操作的实现

单链表的定义

typedef struct LNode {
//定义单链表结点类型
  ElemType data;  //数据域
  struct LNode  *next ;  //指针域
}LNode, *LinkList;

采用头插法建立单链表

LinkList List_HeadInsert (LinkList &L) {
//从表尾到表头逆向建立单链表L,每次均在头结点之,后插入元素
  LNode *s;int x;
  L= (LinkList) malloc (sizeof (LNode)) ;  //创建头结点
  L->next=NULL;  //初始为空链表
  scanf ("&d", &X) ;  //输入结点的值
  while(x!=9999) {  //输入9999表示结束
    s= (LNode* ) malloc (si zeof (LNode) ) ;  //创建新结点
    s->data=x;
    s->next=L->next;
    L->next=s;  //将新结点插入表中，L为头指针
    scanf ("&d",&x) ;
  }
  return L;
}

每个结点时间复杂度为O(1) n个元素为O(n)

采用尾插法建立单链

LinkList List_TailInsert (LinkList &L) {
//从表头到表尾正向建立单链表L,每次均在表尾插入元素
  int x;  // 设元素类型为整型
  L= (LinkList) malloc (sizeof (LNode) ) ;
  LNode *s, r=L;//r为表尾指针
  scanf ("%d",&x) ;  //输入结点的值
  while (x!=9999) {  //输入9999表示结束
    s = (LNode *) malloc (sizeof (LNode)) ;
    s->data=x;
    r->next=s;
    r=S;  //r指向新的表尾结点
    scanf ("号d",&x) ;
    r->next =NULL;  //尾结 点指针置空
  }
  return L;
}

时间复杂度与头插法一样

按序号查找结点值

LNode *GetElem(LinkList L,int i) {
//本算法取出单链表L (带头结点)中第i个位置的结点指针
  int j=1;  //计数，初始为1
  LNode p=L->next;  //头结点指针赋给p
  if(i==0)
    return L;  //若i等于0，则返回头结点
  if(i<1)
    return NULL;  //若i无效，则返回NULL
  while (p&&j<i) {  //从第1个结点开始找，查找第i个结点
    p=p->next;
    j++;
  }
return p;  //返回第i个结点的指针，如果i大于表长，直接返回P即可

时间复杂度O(n)

按值查找表结点

LNode *LocateElem (LinkList L, ElemType e) {
//本算法查找单链表L (带头结点)中数据域值等于e的结点指针，否则返回NULL
  LNode *p=L->next;
  while (p!=NULL&&p->data!=e)   //从第 1个结点开始查找data域为e的结点
    p=p->next;
  return p;  //找到后返回该结点指针，否则返回NULL
}

时间复杂度O(n)

插入结点操作

p = GetElem(L,i-1);  //查找插入位置的前驱结点
s->next = p->next;  //图2.7中操作步骤1
p->next = s;  //图2.7中操作步骤2

删除结点操作

p = GetElem(L,i-1) ;  // 查找删除位置的前驱结点
q = p->next;  //令q指向被删除结点
p->next = q->next  //将*q结点从链中“断开
free (q) ;  //释放结点的存储空间

1.3.2双链表的操作的实现

双链表的定义

typedef struct DNode {
//定义双链表结点类型
  ElemType data;  //数据域
  struct DNode *prior, *next;  //前驱和后继指针
}DNode, *DLinklist;

双链表的插入操作

s->next=p->next;  //将结点*S 插入到结点*p之后
p->next- >prior=s;
s->prior=p;
p->next-s;

双链表的删除操作

p->next=q->next;
q->next->prior-p;
free (q) ;  //释放结点空间

2栈

2.1栈的基本操作

方法名	含义
InitStack(&S):	初始化-一个空栈S。
StackEmpty(S):	判断一个栈是否为空，若栈S为空则返回true,否则返回false.
Push(&S,x):	进栈，若栈S未满，则将x加入使之成为新栈顶。
Pop(&S,&x):	出栈，若栈s非空，则弹出栈顶元素，并用x返回。
GetTop(S,&x):	读栈项元素，若栈S非空，则用x返回栈顶元素。
ClearStack(&S):	销毁栈，并释放栈S占用的存储空间

(注意，符号“&”是C++特有的，用来表示引用调用，有的书上采用C语言中的指针类型“*”，也可以达到传址的目的)。

2.2栈的顺序存储结构

2.2.1顺序栈的基本方法

定义

#define MaxSize 50  //定义栈中元素的最大个数
typedef struct {
  Elemtype data [MaxSize] ;  //存放栈中元素
  int top;  //栈顶指针
} SqStack;

(1)初始化

void InitStack(SqStack &S) {
  S. top=-1;  //初始化栈顶指针
}

(2)判栈空

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

(3)进栈

bool Push (SqStack &S, ElemType x) {
if (S. top==MaxSize-1)  //栈满，报错
  return false;
  S.data[++S. top]=x;  //指针先加1，再入栈
  return true;
}

(4)出栈

bool Pop (SqStack &S,ElemType &X) {
  if (S. top=--1)  //栈空，报错
  return false;
  x=S.data[s.top--];  //先出栈，指针再减1
  return true;

(5)读栈顶元素

bool GetTop (SqStack S, ElemType &X) {
  if (S. top---1)  //栈空，报错
  return false;
  x=S.datals.top ;  //x记录栈顶元素
  return true;

2.3栈的链式存储结构

2.3.1栈的链式存储结构的实现方法

定义

typedef struct Linknode {
  ElemType data;  //数据域
  struct Linknode *next;  //指针域
} *LiStack;  //栈类型定义

3队列

3.1栈的基本操作

方法名	含义
InitQueue (&Q)	初始化队列，构造一个空队列Q.
QueueEmpty (Q)	判队列空，若队列Q为空返回true,否则返回false.
EnQueue(&Q,x)	入队，若队列Q未满，将x加入，使之成为新的队尾。
DeQueue (&Q, &x)	出队，若队列Q非空，删除队头元素，并用x返回。
GetHead (Q, &x)	读队头元素，若队列Q非空，则将队头元素赋值给X。

3.2队列的顺序存储结构

3.2.1顺序队列基本方法的实现

定义

#define MaxSize 50   //定义队列中元素的最大个数
typedef struct{
  ElemType data [MaxSize] ;  //存放队列元素
  int front, rear;  //队头指针和队尾指针
} SqQueue ;

3.2.2循环队列的基本方法

初始化

void InitQueue (SqQueue &Q) {
  Q.rear=Q.front=0;  //初始化队首、队尾指针
}

判队空

bool isEmpty (SqQueue Q) {
  if (Q.rear==Q.front)
    return true;  //队空条件
  else return  false;
}

入队

bool EnQueue (SqQueue &Q, ElemType x) {
  if( (Q.rear+1) SMaxSize==Q.front) return false;  //队满
  Q.data [Q.rear] = X;
  Q.rear= (Q.rear+1) MaxSize;  //队尾指针加1取模
  return true;
}

出队

bool DeQueue (SqQueue &Q， ElemType &x) {
  if (Q.rear==Q.front) return false;  //队空，报错
  x=Q.data[Q. front] ;
  Q.front= (Q.front+1) % MaxSize;  //队头指针加1取模
  return true;
}

3.3队列的链式存储结构

3.3.1链式队列基本方法的实现

定义

typedef struct {   //链式队列结点
  ElemType data;
  struct LinkNode *next ;
}LinkNode ;

typedef struct{  //链式队列
  LinkNode *front, * rear;  //队列的队头和队尾指针
}LinkQueue;

初始化

void InitQueue (LinkQueue &Q) {
  Q.front->Q.rear= (LinkNode* )malloc (sizeof(LinkNode) );  //建立头结点
  Q.front->next=NULL;  //初始为空
}

判队空

bool IsEmpty (LinkQueue Q) {
  if (Q.front==Q.rear) return true;
  else return false;
}

入队

void EnQueue (LinkQueue &Q, ElemType x) {
  LinkNode *s= (LinkNode *)malloc (sizeof (LinkNode)) ;
  s->data=x;  s->next=NULL; //创建新结点，插入到链尾
  Q.rear->next=s;
  Q.rear=s;
}

出队

bool DeQueue (LinkQueue &Q, ElemType &x) {
  if (Q.front==Q.rear) return false;//空队
  LinkNode *p=Q.front ->next;
  x=p->data;
  Q.front- >next=p->next;
  if (Q.rear==p)
  Q.rear=Q.front; //若原队列中只有一个结点，删除后变空
  free(p) ;
  return true;
}

ps:
1.给定两个单链表，编写算法找出两个链表的公共结点。
分析：勿用蛮力，从第一个公共结点以后全是公共结点。

遇到此类问题，但看了文章还是未解决，
评论或加 QQ：781378815