数据结构线性表

数据结构第二章 线性表思维导图：一、线性表的定义和基本操作、线性表是具有相同数据类型的n个数据元素的有限序列。、二、线性表的顺序表示(顺序表)、三、线性表的链式表示等等

第二章 线性表

• 一、线性表的定义和基本操作
  • 线性表的定义
    • 线性表是具有相同数据类型的n个数据元素的有限序列。
    • 概念：表头元素，表尾元素，直接前驱，直接后继。
  • 线性表的基本操作
    • 建立InitList(&L)也就是初始化、销毁DestroyList(&L) 增ListInsert(&L,i,e)插入 删ListDelete(&L,i,e) 查LocateElem(L,e),GetElem(L,e) Length(L)表长，PrintList(L)输出，Empty(判空)
• 二、线性表的顺序表示(顺序表)
  • 顺序表的定义
    • 用顺序存储的方式实现线性表； 顺序存储：把逻辑上相邻的元素存储在物理位置也相邻的存储单元中，元素之间 的关系由存储单元的邻接关系来体现。
  • 顺序表的实现
    • 静态分配
      • //静态分配定义顺序表，存储空间是静态的的，大小刚开始就固定了 #define MaxSize 10//定义最大长度 typedef struct{ ElemType data[MaxSize]; //用静态“数组”存放数据元素 int length; //顺序表当前长度 }SqList; //顺序表的类型定义（静态分配方式） ElemType是指自己定义的数据类型，比如int、double //初始化顺序表 #include<stdio.h> #define MaxSize10 typedef struct{ int data[MaxSize]; int length; }SqList; void InitList(SqList &L){ for(int i=0;i<MaxSize;i++) L.data[i]=0; //将所有数据元素设置为默认初始值 L.length=0; //将顺序表初始长度设置为0 } int main(){ SqList L; //声明一个顺序表 InitList(L): //初始化顺序表 ...... return 0; } //动态分配实现顺序表，大小可以改变 #include<stiod.h> #define InitSize 10 //默认的最大长度 tyedef struct{ int *data; //指示动态分配数组的指针 int MaxSize; //顺序表的最大容量 int length; //顺序表当前长度 }SeqList; //顺序表的定义 int main(){ SeqList L; //声明一个顺序表 InitList(L): //网顺序表中随意插入几个元素 IncreaseSize(L,5); return 0; } void InitList(SeqList &L){ //用malloc函数申请一篇连续的存储空间 L.data(int *)malloc(InitSize*sizeof(int)); L.length=0; L.MaxSize=InitSize; } //增加动态数组的长度 void IncreaseSize(SeqList &L,int len){ int *p=L.data; L.data(int *)malloc((L.MaxSize+len)*sizeof(int)): for(int i=0;i<L.length;i++){ L.data[i]=p[i]; //将数据复制到新区域 } L.MaxSize=L.MaxSize+len; //顺序表最大长度增加len free(p); //释放原来的内存空间 }
    • 动态分配
      • L.data=(ElemType *)malloc(sizeof ElemType *InitSize) malloc函数返回一个指针，需要强制转型为你定义的数据元素类型指针
    • 顺序表特点：①随机访问 ②存储密度高 ③拓展容量不便 ④插入删除操作不方便，需要移动大量元素
  • 顺序表的插入删除
    • 顺序表的插入
      • ListInsert(&L,I,e),在第i个位置上插入指定元素e
      • //顺序表元素插入 #define MaxSize 10 typedef struct{ ElemType data[MaxSize]; int length; }SqList; void ListInsert(SqList &L,int I,int e){ 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 } int main(){ SqList L; InitList(L): //此处省略，可以插入一系列元素 ListInsert(L,3,3); return 0; } //为了避免插入元素没有反馈，比如说内存满了，要修改Insert函数，要有返回值 bool ListInsert(SqList &L,int I,int e){ if(i<1 || i>L.length+1) return false; if(L.length>=MaxSize) return false; for(int j=L.length;j>i;j--) L.data[j]=L.data[j-1]; L.data[i-1]=e; L.length++; return false; }
    • 插入的时间复杂度：最好O(1)，最坏O(n),平均O（n)
    • 顺序表的删除
      • ListDelete(SqList &L,int i,int &e),删除表L中第i个位置的元素并返回该元素的值
      • //顺序表的删除 bool ListDelete(SqList &L,int i,int &e){ if(i<1 || i>L.length+1) //判断i的范围是否有效 return false; e=L.data[i-1]; for(int j=1;j<L.length;j++) L.data[j-1]=L.data[j]; L.length--; return true; } int main(){ SqList L; InitList(L); int e=-1; if(ListDelete(L,3,e)) printf("删除第3个元素，删除元素值为=%d/n",e); else pprintf("位序i不合法，删除失败\n"); return 0; }
    • 删除的时间复杂度:最好O(1)，最坏O(n)，平均O(n)
  • 顺序表的查找
    • 按位查找
      • GetElem(L,i),获取表L中的第ｉ个位置的元素的值
      • //按位查找 //静态分配 #define MaxSize typedef struct{ ElemType data[MaxSize]; //用静态的“数组”存放数据元素 int length; //顺序表当前长度 }SqList; //顺序表的类型定义（静态分配方式） ElemType GetElem(SqList L,int i){ return L.data[i-1]; //调用GetElem()函数返回第i个位置元素的值 } //动态分配 #define InitSize typedef struct{ ElemType *data; int MaxSize; int length; }SeqList; ElemType GetElem(SeqList L,int i){ return L.data[i-1]; }
    • 按值查找
      • LocateElem(L,e),在表L中查找给定关键字值的元素
      • //按值查找 #define InitSize 10 typedef struct{ ElemType *data; int MaxSize; int length; }SeqList; //在顺序表L中查找第一个元素值等于e的元素，并返回其位序 int LocateElem(SeqList L,ElemType e){ for(int i=0;i<L.length,i++) if(int i=0;o<L.length;i++) return i+1; //数组洗标为i的元素值等于e，返回其位序i+1 return 0; //退出循环，说明查找失败 }
      • 时间复杂度：最好O(1),最坏O(n),平均O(n)
    • 结构类型比较
• 三、线性表的链式表示
  • 单链表
    • 单链表的定义
      • 每个结点除了存放数据元素外，还要存储指向下一个结点的指针
    • 单链表代码表示
      • struct LNode{ ElemType data; //定义单链表结点类型 struct LNode *next;//每个结点存放以一个数据元素 } struct LNode *p=(struct LNode *)malloc(sizeof(struct LNode)); //每增加一个新结点，向内存申请一个结点空间，并用指针p指向这个结点 也可以使用typedef struct LNode LNode;代替LNode *p=(LNode *)maloc(sizeof(LNode)); 这样的话就不用struct LNode来增加结点了
      • //课本，定义一个单链表 typedef struct LNode{} //定义单链表结点类型 ElemType data; //数据域 struct LNode *next; //指针域 LNode,*LinkList; //LNode是重命名，*LinkList是指向这个结点的指针 使用LNode *强调这是一个结点 使用LinkList强调这是一个单链表
    • 两种实现
      • 带头结点
        • //带头结点的单链表 typedef struct LNode{ ElemType data; strut LNode *next; }LNode,*LinkLst; //初始化一个空的单链表 bool InitList(LinkList &L){ L=NULL; //空表，放置脏数据 return true; } void test(){ LinkList L; //声明一个指向单链表的指针 //初始化一个空表 InitList(L); //....后续代码 } //判断单链表是否为空 bool Empty(LinkList L){ return (L=NULL); }
      • 不带头结点
        • //不带头节点的单链表 typedef struct LNode{ ElemType data; struct LNode *next; }LNode,*LinkList; //初始化一个带表头结点单链表 bool InitList(LinkList &L){ L=(LNode *)malloc(sizeof(LNode));//分配一个头结点 if(L==NULL) return false; L->next=NULL; return true; } void test(){ LinkList L; //声明一个指向单链表的指针 //初始化一个空表 InitList(L); //...后续代码 } //判断单链表是否为空(带表头) bool Empty(LinkList L){ if(L->next==NULL) return true; else return false; }
    • 单链表的插入删除
      • 插入
        • 按位序插入
          • //按位序在第i个位置插入元素e(带头结点) ListInsert(&L,int i,ElemType e){ if(i<1) return false; LNode *p; //指针p指向当前扫描到的结点 int j=0; //当前p指向的是第几个结点 p=L; //L指向头节点，头节点是第0个结点（不存数据） while(p!=NULL&&j<i-1){ //循环找到第i-1个结点 p=p->next; j++; } if(p=NULL) //i的值不合法 return false; LNode *s =(LNode *)malloc(sizeof(LNode));//申请一个新的结点空间存放新的元素 s->data=e; //新结点的数据域存放新的元素内容 s->next=p->next; //新结点的next指针指向i-1个结点指向的next指针，称为第i个元素 p->next=s; //新结点的前一个结点next指向新节点 return true; } typedef struct LNode{ ElemType data; struct LNode *next; }LNode,*LinkList;
          • ////按位序在第i个位置插入元素e(不带头结点) bool ListInsert(LinkList &L,int i,ElemType e){ if(i<1) return false; if(i==1){ //插入在第1个结点操作与其它结点操作不同 LNode *s=(LNode *)malloc(sizeof(LNode)); s->data=e; s->next=L; L=s; //头指针指向新结点 return true; } LNode *p; int j=1; p=L; while(p!=NULL && j<i-1){ p=p->next; j++; } if(p==NULL) return false; s->data=e; s->next=p->next; p->next=s; return true; //插入成功 } typedef struct LNode{ ElemType data; struct LNode *next; }LNode,*LinkList;
        • 指定节点的后插操作
          • //后插操作，在p结点之后插入元素e bool InsertNextNode(LNode *p,ElemType e){ if(p==NULL) LNode *s=(LNode *)malloc(sizeof(LNode)); if(s==NULL) //内存分配不足 return false; s->data=e; //用结点s保存数据元素e s->next=p->next; p->next=s; //将结点s连到p之后 return true; } typedef struct LNode{ ElemType data; struct LNode *next; }LNode,*LinkList;
        • 指定结点的前插操作
          • InsertPriorNode(LinkList L,LNode *p,ElemType e),给定头结点，然后遍历整个表，查找p的前结点，为了方便，直接复制这个结点，改变这个结点的内容，使时间复杂度为O(n)
          • //前插操作，在p结点之前插入结点s bool InsertPriorNode(LNode *p,LNode *s){ if(p==NULL || s==NULL) return false; s->next=p->next; p->next=s; ElemType temp=p->data; p->data=s->data; s->data=temp; return true; }
      • 删除
        • 按位序删除
          • ListDelete(&L,i,&e):删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。
          • //单链表按位序删除 bool ListDelete(LinkList &L,int I,ElemType &s){ if(i<1) return false; LNode *p; //指针p指向当前扫描到的结点 int j=0; //j表示当前p指向的是第几个结点 p=L; //L指向头结点，头结点是第0个结点（不存数据） while(p!=NULL&&j<j-1){ //循环找到第i-1个结点 p=p->next; j++; } if(p==NULL) //i值不合法 return false; if(p->next==NULL) //第i-1个结点之后已无其它结点 return false; LNode *q=p->next; //令q指向被删除结点 e=q->data; //用e返回元素的值 p->next=q->next; //将*q结点从链中“断开” free(q); //释放结点的存储空间 return true; //删除成功 } typedef struct LNode{ ElemType data; struct LNode *next; }LNode,*LinkList;
        • 指定节点的删除
          • DeleteNode(LNode *p)，删除指针p
          • //单链表删除指定结点p bool DeleteNode (LNode *p){ if(p==NULL) return false; LNode *q=p->next; //令q指向*p的后继结点 p->data=p->next->data; //和后继结点交换数据域 p->next=q->next; //将*q结点从链中“断开” free(q); //释放后继结点的存储空间 return true; }
    • 单链表的查找
      • 按位查找
        • //单链表按位查找 LNode *GetElem(LinkList L,int i){ if(i<0) return NULL; LNode *p; int j=0; p=L; while(p!=NULL&&j<1){ p=p->next; j++; } return p; }
      • 按值查找
        • LocateElem(LinkList L,ElemType e),查找数据域为e的结点的位置
        • //单链表按值查找，找到数据域返回==e的结点 LNode * LocateElem(LinkList L,ElemType e){ LNode *p = L->next; //从第1个结点开始查找数据域为e的结点 while(p != NULL&&p->data!=e) p=p->next; return p; //找到后返回该结点指针，否则返回NULL }
      • 求表的长度
        • //求表长度 int length(LinkList L){ int len=0; LNode *p=L; while(p->next != NULL){ p=p->next; len++; } return len; }
    • 单链表的建立
      • step1:初始化一个单链表 step2:每次去一个数据元素，插入到表头/表尾
      • 尾插法
        • 初始化单链表、设置变量length记录链表长度、设置表尾指针、每次取一个数据元素插入到表尾
        • //尾插法建立单链表 LinkList List_TailInsert(LinkList &L){ //正向建立单链表 int x; //设置ElemType为整型 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; }
      • 头插法
        • //头插法建立单链表 LinkList List_HeadInsert(LinkList &L){ //逆向建立单链表 LNode *s; int x; L=(LinkList)malloc(sizeof(LNode)); //创建头结点 L->next=NULL; //初始为空链表 scanf(“%d”,&x); //输入结点的值 while(x!=9999){ //输入9999表示结束 s=(LNode*)malloc(sizeof(LNode)); //创建新结点 s->data=x; s->next=L->next; L->next=s; //将新结点插入表中，L为头指针 scanf(“%d”,&x); } return L; }
  • 双链表
    • 双链表的初始化
      • 单链表：单链表无法逆向检索，有时不太方便。 双链表：可进可退，存储密度更低
      • //双链表的初始化（带头结点） bool InitDLinkList(DLinklist &L){ L=(DNode *)malloc(sizeof(DNode)); if(L==NULL) return flase; L->prior=NULL; L->next=NULL; return true; } void testDLinkList(){ //初始化双链表 DLinklist L; InitDLinkList(L); //…后续代码 } typedef struct DNode{ ElemType data; struct DNode *prior,*next; }DNode,*DLinklist; //判断双链表是否为空（带头结点） bool Empty(DLinklist L){ if(L->next==NULL) return true; else return false; }
    • 双链表的插入
      • //双链表的插入 bool InsertNextDNode(DNode *p,DNode *s){ s->next=p->next; //将结点*s插入到结点*p之后 p->next->prior=s; s->prior=p; p->next=s; }
    • 双链表的删除
      • //双链表的删除 bool DeleteNextDNode(DNode *p){ if(p==NULL) return flase; DNode *q=p->next; //找到p的后继结点q if(q==NULL) return false; //p没有后继结点 p->next=q->next; if(q->next!=NULL) //q结点不是最后一个结点 q->next->prior=p; free(q); //释放结点空间 return true; } void DestoryList(DLinklist &L){ //循环释放各个数据结点 while(L->next!=NULL) DeleteNextDNode(L); free(L); //释放头结点 L=NULL; //头指针指向NULL }
    • 双链表的遍历
      • //双链表的遍历 while(p!=NULL){ //后向遍历 //对结点p做相应处理 p=p->next; } while(p!=NULL){ //前向遍历 p=p->prioe; } while(p->prioe!=NULL){ //前向遍历，跳过头结点 p=p->prior; }
  • 循环链表
    • 循环单链表
      • 单链表：从一个结点出发只能找到后续各个结点，但是前面的结点是未知的。 循环单链表：从一个结点出发可以找到其它任何一个结点。
      • //定义循环单链表 typedef struct LNode{ //定义单链表结点类型 ElemType data; //每个结点存放一个数据元素 struct LNode *next; //数据指向下一个结点 }LNode,*LinkList; //初始化一个循环单链表 bool InitList(LinkList &L){ L=(LNode *)malloc(sizeof(LNode)); //分配一个头结点 if(L==NULL) //内存不足，分配失败 return false; L->next = L; //头结点Next指向头结点 return true; } //判断循环单链表是否为空 bool Empty(LinkList L){ if(L->next==L) return true; else return flase; } //判断结点p是否为循环单链表的表尾结点 bool isTail(LinkList L,LNode *p){ if(p->next==L) return true; else return false; }
    • 循环双链表
      • //初始化空的循环双链表 bool InitDLinkList(DLinklist &L){ L=(DNode *)malloc(sizeof(DNode)); //分配一个头结点 if(L==NULL) //内存不足，分配失败 return false; L->prior=L; //头结点的prior指向头结点 L->next=L; //头结点的next指向头结点 return true; } void testDLinkList(){ //初始化循环双链表 DLinklist L; InitDLinkList(L); //…后续代码 } //判断循环双链表是否为空 bool Empty(DLinklist){ if(L->next==L) return true; else return false; } //判断结点p是否为循环双链表的表尾结点 bool isTail(DLinklist L,DNode *p){ if(p->next==L) return true; else return false; } typedef struct DNode{ ElemType data; struct DNode *prior,*next; }DNode,*DLinklist;
  • 静态链表
    • 定义
      • 单链表：各个结点在内存中随意分配。 静态链表：分配一整片连续的内存空间，各个结点集中安置。
    • 代码表示
      • //定义静态链表 #define MaxSize 10 typedef sreuct{} ElemType data; int next; } void testSLinkList(){ struct Node a[MaxSize]; //……后续代码 } //也可以下面的代码建立静态链表 #define MaxSize 10 //静态链表最大长度 typedef struct{ //静态链表结构类型的定义 ElemType data; //存储数据元素 int next; //下一个元素的数组下标 } SLinkList[MaxSize]; void testSLinkLst(){} SLinkList a; //…后续代码 }
    • 基本操作的实现
  • 顺序表和链表的实现
    • 逻辑结构
      • 都属于线性表，都是线性结构
    • 物理结构/存储结果
      • 顺序表优点：支持随机存取、存储密度高。 缺点：大片连续空间分配不方便，改变容量不方便。 链表优点：离散的小空间分配方便，改变容量方便。 缺点：不可随机存取，存储密度低。
    • 数据的运算/基本操作
      • 创建、销毁、增删改查 创建： 需要预分配大片连续空间。若分配空间过小，则之后不方便拓展容量；若分配空间过大，则浪费内存资源 静态分配：静态数组，容量不可变 动态分配：动态数组(malloc、free)，容量可改变，但需要移动大量元素，时间代价高。 销毁：修改length=0,静态分配的空间会自动回收，动态分配malloc申请的需要手动free 插入/删除元素都要将后续元素后移/前移。时间复杂度O(n),时间开销主要来自于移动元素。移动元素大，则移动时间代价高。 查找：按位查找：O(1)。按值查找：O(n)，若表内元素有序，可在O(log2n)时间内找到。 创建： 只需要分配一个头结点（也可以不要头节点，只声明一个头指针），之后方便拓展。 销毁：依次删除各个结点（free） 插入/删除元素都只需修改指针即可。时间复杂度O(n)，时间开销主要来自于查找目标元素。查找元素的时间代价更低。 查找：按位查找：O(n)。按值查找：O(n)。 用顺序表or链表：表长难以预估、经常要增减/删除元素，用链表。 表长可预估、查询（搜索）操作较多，用顺序表。 问题：请描述顺序表和链表……实现用顺序表还是链表好？ 顺序表和链表的逻辑结构都是线性结果，都属于线性表。但是二者存储结构不同，顺序表采用顺序存储…(特点，带来的优点，缺点)；链表采用链式存储……(优点缺点)。由于采用不同存储方式实现，因此基本操作的实现效率也不同。当初始化时…插入一个数据元素时…删除一个数据元素时候…查找一个数据元素时…
      • 顺序表创建： 需要预分配大片连续空间。若分配空间过小，则之后不方便拓展容量；若分配空间过大，则浪费内存资源 静态分配：静态数组，容量不可变 动态分配：动态数组(malloc、free)，容量可改变，但需要移动大量元素，时间代价高。 销毁：修改length=0,静态分配的空间会自动回收，动态分配malloc申请的需要手动free 插入/删除元素都要将后续元素后移/前移。时间复杂度O(n),时间开销主要来自于移动元素。移动元素大，则移动时间代价高。 查找：按位查找：O(1)。按值查找：O(n)，若表内元素有序，可在O(log2n)时间内找到。
      • 链表创建： 只需要分配一个头结点（也可以不要头节点，只声明一个头指针），之后方便拓展。 销毁：依次删除各个结点（free） 插入/删除元素都只需修改指针即可。时间复杂度O(n)，时间开销主要来自于查找目标元素。查找元素的时间代价更低。 查找：按位查找：O(n)。按值查找：O(n)。
      • 用顺序表or链表：表长难以预估、经常要增减/删除元素，用链表。 表长可预估、查询（搜索）操作较多，用顺序表。 问题：请描述顺序表和链表……实现用顺序表还是链表好？ 顺序表和链表的逻辑结构都是线性结果，都属于线性表。但是二者存储结构不同，顺序表采用顺序存储…(特点，带来的优点，缺点)；链表采用链式存储……(优点缺点)。由于采用不同存储方式实现，因此基本操作的实现效率也不同。当初始化时…插入一个数据元素时…删除一个数据元素时候…查找一个数据元素时…

附页

• 顺序表
  • 存储结构
    • 逻辑上相邻的数据元素物理上也相邻
  • 实现方式
    • 静态分配
      • 使用“静态数组”实现
      • 大小一旦确定就无法改变
    • 动态分配
      • 使用“动态数组”实现
      • L.data=(ElemType *)malloc (sizeof(El;emType)* size)
      • 顺序表存满时，可再用malloc动态拓展顺序表的最大通量
        • 注意malloc、free函数
      • 需要将数据元素复制到新的存储区域，并用free函数释放原区域
  • 特点
    • 随机访问
      • 能在O(1)时间内找到第i个元素
    • 存储密度高
    • 拓展容量不方便
    • 插入、删除数据元素不方便
• 线性表
  • 逻辑结构
  • 基本运算/操作
  • 存储/物理结构
    • 顺序表（顺序存储）
      • 定义（如何用代码实现）
      • 基本操作的实现
    • 链表（链式存储）
      • 单链表
        • 定义（如何用代码实现）
        • 基本操作的实现
      • 双链表
      • 循环链表
      • 静态链表
• 顺序表的插入和删除
  • 插入
    • ListInsert(&L,i,e)
      • 将元素e插入到L的第i个位置
    • 插入位置之后的元素都要后移,表的长度加1
    • 时间复杂度
      • 最好O(1),最坏O(n),平均O(n)
  • 删除
    • ListDelete(&L,i,&e)
      • 将L的第i个元素删除，并用e返回
    • 删除位置之后的元素都要前移，表长度减1
    • 时间复杂度
      • 最好O(1)，最坏O（n)，平均O（n）
  • 代码要点
    • 注意位序i和数组下标的区别
    • 算法要具有健壮性，判断i的合法性
    • 注意移动元素是移动靠前的元素还是表尾元素开始
    • 分析为何要有'&'
• 顺序表的查找
  • 按位查找
    • GetElem(L,i)
      • 获取表L中第i个位置的元素的值
      • 用数组下标即可得到第i个元素 L.data[i-1]
    • 时间复杂度分析
      • 最好/最坏/平均时间复杂度都是O(1)
  • 按值查找
    • LocateElem(L,e)
      • 在顺序表L中查找第一个元素值等于e的元素，并返回其位序
      • 从第一元素开始依次往后检索
    • 时间复杂度分析
      • 最好时间复杂度O(1)
      • 最坏时间复杂度O(n)
      • 平均时间复杂度O(n)
• 单链表的定义
  • 什么是单链表
    • 用“链式存储”（存储结构）是实现了“线性结构”（逻辑结构）
    • 一个结点存储一个数据元素
    • 各结点间的先后关系用一个指针表示
  • 用代码定义一个单链表
    • typedef struct LNode{ //定义单链表结点类型 ElemType data; //数据域 struct LNode *next; //指针域 }LNode ,*LinkList;
  • 两种实现
    • 带头结点
      • 空表判断：L==NULL
      • 写代码方便
    • 不带头结点
      • 空表判断：L->next==NULL;
      • 写代码不方便
  • 其它注意点
    • typedef关键字的用方法
    • LinkList等价于LNode LinkList强调是链表；LNode强调是结点
• 单链表插入和删除
  • 插入
    • 按位序插入
      • 带头结点
      • 不带头结点
    • 指定结点的后插操作
    • 指定结点的前插操作
  • 删除
    • 按位序删除
    • 指定结点的删除
• 单链表的查找
  • 按位查找
    • 注意与“顺序表”对比
    • 单链表不具备“随机访问”的特性，只能依次扫描
  • 按值查找
  • 求单链表长度
  • Key
    • 三种基本操作的时间复杂度都是O(n)
    • 如何写循环扫描各个结点的代码逻辑
    • 注意边界条件的处理
• 单链表的建立
  • step1:初始化一个单链表 step2:每次取一个数据元素，插入到表头/表尾
  • 尾插法
  • 头插法
• 双链表
  • 初始化
    • 头节点的prior、next都指向NULL
  • 插入（后插）
    • 注意新插入结点、前驱结点、后继结点的指针修改
    • 边界情况：新插入结点在最后一个位置，需特殊处理
  • 删除（后删）
    • 注意删除结点的前驱节点、后继节点的指针修改
    • 边界情况：如果被删除结点是最后一个数据结点，需特殊处理
  • 遍历
    • 从一个给定结点开始，后向遍历、前向遍历的实现（循环的终止条件）
    • 链表不具备随机存取特性，查找操作只能通过顺序遍历实现
• 循环链表
  • 循环单链表
    • 空表
    • 非空表
  • 循环双链表
    • 空表
    • 非空表
  • 代码问题
    • 如何判空
    • 如何判断结点p是否为表头/表尾结点
• 循环链表
  • 什么是静态链表
    • 集中分配一整片连续的地址存储数据元素
  • 如何定义一个静态链表
  • 简述基本操作的实现