数据结构笔记（二）
数据结构笔记（二）
1、第二章：线性表
通过下面的思维导图来依次分享「线性表」里面重要知识点的笔记。
2、第一节：现象表的定义和基本操作
1. 线性表的定义：线性表是具有相同数据类型的n(n≥0)个数据元素的有限序列。其中n为表长，当n=0时该线性表是一个空表。若用L命名线性表，则其一般表示如下：
L=(a1,a2, ..., ai,ai+1, ... ,an)
其中，a1 是唯一的“第一个”数据元素，又称为表头元素；an是唯一的“最后一个”数据元素，又称为表尾元素。除第一个元素外，每个元素有且仅有一个直接前驱。除最后一个元素外，每个元素有且仅有一个直接后继。
2. 线性表的基本操作有：
①InitList(&L): 初始化表。构造一个空的线性表。
②Length(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所占用的内存空间。
3、第二节：线性表的顺序表示
1. 线性表的顺序存储又称为顺序表：它是用一组地址连续的存储单元，依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。
线性表的顺序存储类型描述有以下方法：
方法一：静态分配一维数组，数组的大小和空间事先已经固定。
1#define MaxSize 50 //定义线性表的最大长度
2typedef struct{
3 ElemType data[MaxSize]; //顺序表的元素
4 int length; //顺序表的当前长度
5}SqList; //顺序表的类型定义
方法二：动态分配一维数组，一旦数据空间占满，可以另外开辟一块更大的存储空间，用来替换原来的存储空间，从而达到扩充数组空间的目的。
1#define InitSize 100 //表长度的初始定义
2typedef struct{
3 ElemType *data; //指示动态分配数组的指针
4 int MaxSize,length; //数组的最大容量和当前个数
5} SeqList; //动态分配数组顺序表的类型定义
2. 顺序表的特点：随机访问，即通过首地址和元素序号可以在O(1)的时间内找到指定的元素。顺序表的存储密度高，每个结点只存储数据元素，插入和删除操作需要移动大量的元素。
3. 顺序表的插入操作操作的实现算法思想为：在顺序表L的第i(1≤ i ≤L.length+1)个位置插入新元素e。如果i的输入不合法，则返回false，表示插入失败；否则，将顺序表的第i个元素以及其后的所有元素右移一个位置，腾出一个空位置插入新元素e，顺序表长度增加1，插入成功，返回true。具体伪代码如下：
1//本算法实现将元素e插入到顺序表L中第i个位置
2bool ListInsert(SqList &L,int i,ElemType e){
3 if(i<1 || i>L.length+1) //判断i的范围是否有效
4 return false;
5 if(L.length >= MaxSize) //当前存储空间已满，不能插入
6 return false;
7 for(int j=L.length; j>=i;j--) //将第i个元素及之后的元素后移
8 L.data[j] = L.data[j-1];
9 L.data[i-1] = e; //在位置i处放入e
10 L.length++; //线性表长度加1
11 return true;
12}
4. 顺序表的删除操作的实现，删除顺序表L中第i(1≤ i ≤L.length+1)个位置的元素，成功则返回true，并将被删除的元素用引用变量e返回，否则返回false。具体伪代码如下：
1//本算法实现删除顺序表L中第i个位置的元素
2bool ListDelete(SqList &L, int i, Elemtype &e){
3 if(i<1 || i>L.length) //判断i的范围是否有效
4 return false;
5 e=L.data[i-1]; //减被删除的元素赋值给e
6 for(int j=i; j<L.length; j++) //将第i个位置之后的元素前移
7 L.data[j-1]=L.data[j];
8 L.length--; //线性表长度减1
9 return true;
10}
4、第三节：线性表的链式表示
1. 线性表的链式存储又称为单链表，是指通过一组任意的存储单元来存储线性表中的数据元素。为建立起数据元素之间的线性关系，对每一个链表结点，除了存放元素自身的信息之外，还需要存放一个指向其后继的指针。单链表中结点类型的描述如下：
1typedef struct LNode{ //定义单链表结点类型
2 ElemType data; //数据域
3 struct LNode *next; //指针域
4}LNode, *LinkList;
2. 头指针：用来标识一个单链表，如单链表L，头指针为“NULL”时则表示一个空表。
3. 头指针：为了方便操作，在单链表第一个结点之前附加一个结点，称为头结点，头结点的数据域可以不设任何信息，也可以记录长度的信息。头结点的指针域指向线性表的第一个元素结点。
4. 头结点与头指针的区别：不管带不带头结点，头指针始终指向链表的第一个结点，而头结点是带带头结点链表中的第一个结点，结点内通常不存储信息。
5. 引入头结点后的优点：
①由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作和在表的其他位置上的操作一致，无须进行特殊处理；
②无论链表是否为空。其头指针是指向头结点的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理就可以统一；
6. 单链表的建立方法有：
①头插法建立单链表：从一个空表开始，生成新结点，并将度取到的数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头，即头结点之后。具体伪代码如下：
1//从表尾到表头逆向建立单链表L，每次均在头结点之后插入元素
2LinkList CreatList1(LinkList &L){
3 LNode *s; int x;
4 L=(LinkList)malloc(sizeof(LNode)); //创建头结点
5 L->next = NULL; //初始为空链表
6 scanf("%d", &x); //输入结点的值
7 while(x!=9999){ //输入9999表示结束
8 s=(LNode*)malloc(sizeof(LNode)); //创建新结点
9 s->data=x;
10 s->next = L->next;
11 L->next=s; //将新结点插入表中，L为头指针
12 scanf("%d", &x); //while结束
13 }
14return L;
15}②尾插法建立单链表：将新结点插入到当前链表的表尾上，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。具体伪代码如下：
1//从表头到表尾正向建立单链表L，每次均在表尾插入元素
2LinkList CreatList2(LinkList &L){
3 int x; //设元素类型为整型
4 L=(LinkList)malloc(sizeof(LNode)); //创建头结点
5 LNode *s,*r=L; //r为尾指针
6 scanf("%d", &x); //输入结点的值
7 while(x!=9999){ //输入9999表示结束
8 s=(LNode*)malloc(sizeof(LNode)); //创建新结点
9 s->data = x;
10 s->next = s;
11 r = s; //r指向新的表尾结点
12 scanf("%d", &x);
13 }
14 r->next = NULL; //尾结点指针置空
15 return L;
16}
7. 单链表按序号查找结点值的实现伪代码如下：
1//本算法取出单链表L（带头结点）中第i个位置的结点指针
2LNode *GetElem(LinkList L, int i){
3 int j = 1; //计数，初始为1
4 LNode *p=L->next; //头结点指针赋给p
5 if(i==0)
6 return L; //若i无效，则返回头结点
7 if(i<1)
8 return NULL; //若i无效，则返回NULL
9 while(p&&j<i){ //从第1个结点开始找，查找第i个结点
10 p==p->next;
11 j++;
12 }
13 return p; //返回第i个结点的指针
14}
8. 单链表按值查找表结点的实现伪代码如下：
1//本算法查找单链表L(带头结点)中数据域值等于e的结点指针，否则返回NULL
2LNode *LocateElem(LinkList L, ElemType e){
3 LNode *p = L->next;
4 while(p!=NULL && p->data!=e) //从第1个结点开始查找data域为e的结点
5 p=p->next;
6 return p; //找到后返回该结点指针，否则返回NULL
7}
9. 单链表插入结点操作的实现：
①首先调用按序号查找算法GetElement(L, i-1),查找第i-1个结点。假设返回的第i-1个结点为*p，然后令新结点*s的指针域指向*p的后继结点，再令结点*p的指针域指向新插入的结点*s（即前插法）关键步骤伪代码如下。
1p = GetElem(L, i-1); //查找插入位置的前驱结点
2s->next = p->next;
3p->next = s;
②设待插入结点为*s，将*s插入到*p的前面。先将*s插入到*p的后面，然后将p->data与s->data交换即可（后插法），关键步骤伪代码如下。
1//将*s结点插入到*p之前的主要代码片段
2s->next = p->next; //修改指针域，不能颠倒
3p->next = s;
4temp = p->next; //交换数据域部分
5p->data = s->data;
6s->data = temp;
10. 单链表的删除结点操作的实现：
①给定位置删除结点，假设结点*p为找到的被删结点的前驱结点，则仅需修改*p的指针域，即将*p的指针域next指向*q的下一结点，关键步骤伪代码如下：
1p = GetElem(L, i-1); //查找删除位置的前驱结点
2q = p->next; //令q指向被删除结点
3p->next = q->next; //将*q结点从链中“断开”
4free(q); //释放结点的存储空间
②给点结点并删除，实质将其后继结点的值赋予其自身，然后删除后继结点，关键步骤伪代码如下：
1q = p->next; //令q指向*p的后继结点
2p->data = p->next->data; //和后继结点交换数据域
3p->next = q->next; //将*q结点从链中“断开”
4free(q); //释放后继结点的存储空间
11. 双链表：双链表的结点中有两个指针prior和next,分别指向其前驱结点和后继结点。双链表中结点类型的描述如下：
1typedef struct DNode{ //定义双链表结点类型
2 ElemType data; //数据域
3 struct DNode *prior,*next; //前驱和后继指针
4}DNode, *DLinkList;
12. 双链表的插入操作，在双链表中p所指的结点之后插入结点*s，插入操作关键伪代码如下：
1s->next = p->next; //将结点*p插入到结点*p之后
2p->next->prior = s;
3s->prior = p;
4p->next = s;
13. 双链表的删除操作，删除双链表中结点*p的后继结点*q，删除操作关键伪代码如下：
1p->next = q->next;
2q->next->prior = p;
3free(q); //释放结点空间
5、补充：顺序表和链表的比较
1. 顺序表可以顺序存取，也可以随机存取，链表只能从表头顺序存取元素。
2. 顺序表的插入、删除操作，平均需要移动半个表长的元素；链表的插入、删除操作，只需要修改相关结点的指针域即可。
通过博客将自己的学习笔记展现出来，也是对自己学习的一种记录。
扫一扫，关注公众号