乐趣区

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

jiezi

⭐ 我的网站: 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.2 线性表的链式表示

1.2.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.2.4 双链表的操作的实现

双链表的定义 

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 栈的链式存储结构

实现方法

定义 

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

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

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

退出移动版