数据结构第二周笔记——线性结构(慕课浙大版本--XiaoYu)上

2.1.1 引子：多项式表示

例子：一元多项式及其运算

主要运算：多项式相加、相减、相乘等

分析--如何表示多项式

多项式的关键数据：

1. 多项式项数n
   
2. 各项系数ai以及指数i(这里的ai的i是指a的下标)
   方法1：顺序存储结构直接表示
   
   网络异常，图片无法展示

   |
   
   

注解：其实这个的意思就是从头加到尾，不管中间的答案有没有像0这种可以直接省略掉的值都会占一个位置。

所以上方那个问题中如何表示多项式的答案是：需要占2001个位置，首选他是顺序存储结构，然后下标从0开始，所以是2001而不是2000

方法2：顺序存储结构表示非零项(按照指数大小有序存储，比如说指数大的排在前面，指数小的排在后面)

多项式相加过程：从头开始，比较两个多项式当前对应项的的指数  =>这样就能够做到指数递降运算

这里的(11，8)是(15，8)与(-4，8)的结合结果，因为指数一样，所以可以结合为一个

这种方法可以有效节省空间，操作效率也不算差

方法3：链表结构存储非零项

1. 链表中每个节点存储多项式中的一个非零项，包括系数和指数两个数据域以及一个指针域
   
2. coef：指数  expon：系数  link：指针域
   
3. 用指针域将不同的项串起来，同样可以做到指数递降的顺序进行排序
   

//代码演示

typedefstructPolyNode*Polynomial;

structPolyNode{

   intcoef;

   intexpon;

   Polynomiallink;

}

分别指向多项式的头，然后比较指数大小，大的输出；相等的话，系数相加

2.1.2 线性表及顺序存储

什么是线性表:由同类型数据元素构成有序列表的线性结构

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

多项式表示问题的启示：

1. 同一个问题可以有不同的表示(存储)方法  =>通常来说的话是使用链表或者数组来进行存储
   
2. 有一类共性问题：有序线性序列的组织和管理
   

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

类型名称：线性表(List)

数据对象集：线性表是n(>=0)个元素构成的有序列表(a1,a2,...,an)

操作集：线性表L属于List，整数i表示位置，元素X属于ElementType(这个类型可以是整型也可以是实型又或者是个结构，这里统称ElementType)

1. List MakeEmpty()：初始化一个空线性表L
   
2. ElementType FindKth(int K,ListL)：根据位序K，返回相应元素;
   
3. int Find(ElementType X,int i, List L)：在线性表L中查找X的第一次出现位置;
   
4. void Insert(ElementType X,int i,List L)：在位序i前插入一个新元素X;
   
5. void Delete(int i,List L)：删除指定位序i的元素;
   
6. int Length(List L)：返回线性表L的长度n
   

线性表的顺序存储实现

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

typedefstructLNode*List;

structLNode{

   ElementTypeData [MAXSIZE];//定义了一个数组，数组的分类类型是ElementType

   intList;//代表线性表的最后一个元素，这样的一个结构就可以抽象的实现一个线性表

};

structLNodeL;//定义一个变量L

ListPtrL;//还有一个变量PtrL

   //访问下标为i的元素：L.Data[i]或PtrL->Data[i]

   //线性表的长度：L.Last+1或PtrL->Last+1

“->”是一个整体，它是用于指向[结构体]子数据的指针，用来取子数据。

换种说法，如果我们在C语言中定义了一个结构体，然后申明一个指针指向这个结构体，那么我们要用指针取出结构体中的数据，就要用到“->”。

主要操作的实现

1. 初始化MakeEmpty(建立空的顺序表)

ListMakeEmpty()

{

   ListPtrL;

   PtrL= (List)malloc(sizeof(structLNode));//通过malloc申请这样子一个结构

   PtrL->Last=-1;//Last设置为-1，因为Last是代表最后一个元素。Last为0是代表这个表有一个元素放在第一个位置，没元素就设置为-1，然后把这个结构的指针返还回来

   returnPtrL;

}

1. 查找

//科普小知识

find函数用于查找数组中的某一个指定元素的位置。

比如：有一个数组[0, 0, 5, 4, 4]；

问：元素5的在什么位置，find函数返回值为2；

find（数组名+起始查找元素的位置，数组名+结束查找的元素位置，想要查找的元素）

intFind(ElementTypeX, ListPtrL)//List PtrL是线性表结构的指针

{

   inti=0;

   while(i<=PtrL->Last&&PtrL->Data[i]!=X )

       i++

   if(i>PtrL->Last)  return-1;//如果没找到，返回-1

   elsereturni;//找到后返回的是存储位置

}

查找成功的平均比较次数为(n+1)/2,平均时间性能为O(n)

1. 2.1.3顺序存储的插入和删除
   插入(第i(1<=i<=n+1)个位置上插入一个值为X的新元素)   其实就是决定什么时候插入线性表
2. 下标是从0开始的，所以新插入的元素X放到i-1这个位置的话，首先需要把i-1之后的元素往后挪一位给i-1留出位置
   
3. 也就是先移动再插入，每个元素往后挪使用一个循环就可以解决了
   
4. 网络异常，图片无法展示

   |
   
   
5. 从后往前算(挪)，如果从前往后的话算法是不对的

//插入操作实现

voidInsert(ElementTypeX,inti,ListPtrL)

{

   intj;

   if(PtrL->Last==MAXSIZE-1){//表空间已满，不能插入

       printf("表满");

       return;

   }

   if(i<1||i>PtrL->Last+2){//检查插入的位置的合法性。超出这个范围就不行噢

       printf("位置不合法");

       return;

   }

   for(j=PtrL->Last; j>=i-1;j--)//List是最后一个元素的位置

       PtrL->Data[j+1] =PtrL->Data[j];//将a1~an倒序向后移动

   PtrL->Data[i-1] =X;//新元素插入

   PtrL->Last++;//Last仍指向最后元素

   return;

}

//平均移动次数为n/2，平均时间性能为O(n)

接下来我们来介绍一下另外一个操作：删除

如果把后移数组元素的循环

  for ( j=PtrL->Last; j>=i-1; j-- )

      PtrL->Data[j+1]=PtrL->Data[j];

改为

  for ( j=i-1; j<=PtrL->Last; j++ )

      PtrL->Data[j+1]=PtrL->Data[j];

那会是什么后果？

   

分量Data[i-1]到Data[Ptrl->Last+1]都是同一个值，即移之前Data[i-1]的值

1. 删除(删除表中的第i(1 <= i <= n)个位置上的元素)

//删除掉这个元素后就空出来一个位置了，这种时候就需要从左往右的顺序往前挪

//删除操作实现

voidDetele(inti,ListPtrL)//已知PtrL这个线性表

{

   intj;

   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];//将a的下标(i+1)~an顺序往前移动

   PtrL->Last--;//Last仍指向最后元素

   return;

}

//平均移动次数为(n-1)/2,平均时间性能为O(n)

2.1.4 链式存储及查找

线性表的链式存储实现

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

1. 插入、删除不需要移动数据元素，只需要修改"链"
   

typedefstructLNode*List;

structLNode{

   ElementTypeData;

   ListNext;

};

structLnodeL;

ListPtrL;

主要操作的实现

1. 求表长

intLength(ListPtrL)//链表的头指针，并且是单向链表

{

   Listp=PtrL;//p指向表的第一个结点

   intj=0;

   while(p){

       p=p->Next;//这步操作相当于让指针往后挪一位

       j++;//当前p指向的是第j个结点

   }

   returnj;

}

//时间性能为O(n)

1. 查找

//(1)按序号查找：FindKth;采用类似链表的遍历方法

ListFindKth(intK,ListPtrL)

{

   Listp=PtrL;//首先把p这个临时变量设置为链表的表头

   inti=1;

   while(p!=NULL&&i<K){

       p=p->Next;//让指针往后挪一位

       i++;

   }

   if( i==K ) returnp;//找到第K个，返回指针

   elsereturnNULL;//否则返回空

}

//(2)按值查找：Find

ListFind(ElementTypeX,ListPtrL)

{

   Listp=PtrL;

   while(p!=NULL&&p->Data!=X)

       p=p->Next;

   returnp;

}

//返回的是两种结果，不是p就是NULL，调用Find函数，发现它返回值等于NULL，就说明没找着

1. 2.1.5链式存储的插入和删除
2. 插入(在第i-1(1 <=  i <= n+1)个结点后插入一个值为X的新结点)

//(1)先构造一个新结点，用s指向;  这个时候可以用malloc这个函数来申请一块空间

//(2)再找到链表的第i-1个结点，用p指向;

//(3)然后修改指针，插入结点(p之后插入新结点是s)

//下图中的操作步骤：让s指向下一个结点，p的Next附给s的Next

//如果修改指针的两个步骤交换了一下哎，会发生什么？(语句执行顺序为：(1) p->Next=s;  (2) s->Next=p->Next;)

//答案：s->Next指向s,从而不能正确完成插入

1. 网络异常，图片无法展示

   |

//malloc复习区域

#include或者#include//两者的内容是完全一样的

如果分配成功：则返回指向被分配内存空间的指针

不然返回指针NULL

同时，当内存不再使用的时候，应使用free()函数将内存块释放掉。

关于：void*,表示未确定类型的指针，c,c++规定void*可以强转为任何其他类型的指针，关于void还有一种说法就是其他任何类型都可以直接赋值给它，无需进行强转，但是反过来不可以

malloc:

malloc分配的内存大小至少为参数所指定的字节数

malloc的返回值是一个指针，指向一段可用内存的起始位置，指向一段可用内存的起始地址，多次调用malloc所分配的地址不能有重叠部分，除非某次malloc所分配的地址被释放掉malloc应该尽快完成内存分配并返回（不能使用NP-hard的内存分配算法）实现malloc时应同时实现内存大小调整和内存释放函数（realloc和free）

malloc和free是配对的，如果申请后不释放就是内存泄露，如果无故释放那就是什么也没做，释放只能释放一次，如果一块空间释放两次或者两次以上会出现错误（但是释放空指针例外，释放空指针也等于什么也没做，所以释放多少次都是可以的。）

2、malloc和new

new返回指定类型的指针，并且可以自动计算所需要的大小。

   int*p;

p=newint;//返回类型为int* ，分配的大小是sizeof(int)

p=newint[100];//返回类型是int*类型，分配的大小为sizeof(int)*100

而malloc需要我们自己计算字节数，并且返回的时候要强转成指定类型的指针。

   int*p;

p= (int*)malloc(sizeof(int));

1）malloc的返回是void*,如果我们写成了：p=malloc(sizeof(int));间接的说明了（将void转化给了int*，这不合理）

（2）malloc的实参是sizeof(int)，用于指明一个整型数据需要的大小，如果我们写成p=(int*)malloc(1),那么可以看出：只是申请了一个一个字节大小的空间。

（3）malloc只管分配内存，并不能对其进行初始化，所以得到的一片新内存中，其值将是随机的。一般意义上：我们习惯性的将其初始化为NULL，当然也可以使用memset函数。

简单的说：

malloc函数其实就是在内存中找一片指定大小的空间，然后将这个空间的首地址给一个指针变量，这里的指针变量可以是一个单独的指针，也可以是一个数组的首地址，这要看malloc函数中参数size的具体内容。我们这里malloc分配的内存空间在逻辑上是连续的，而在物理上可以不连续。我们作为程序员，关注的是逻辑上的连续，其他的操作系统会帮着我们处理。

下面就来看看malloc具体是怎么实现的。

首先要了解操作系统相关的知识：

虚拟内存地址和物理内存地址

为了简单，现代操作系统在处理物理内存地址时，普遍采用虚拟内存地址技术。即在汇编程序层面，当涉及内存地址时，都是使用的虚拟内存地址。采用这种技术时，每个进程仿佛自己独享一片2N字节的内存，其中N是机器位数。例如在64位CPU和64位操作系统下每个进程的虚拟地址空间为264Byte。

这种虚拟地址空间的作用主要是简化程序的编写及方便操作系统对进程间内存的隔离管理，真实中的进程不太可能如此大的空间，实际能用到的空间大小取决于物理内存的大小。

由于在机器语言层面都是采用虚拟地址，当实际的机器码程序涉及到内存操作时，需要根据当前进程运行的实际上下文将虚拟地址转化为物理内存地址，才能实现对内存数据的操作。这个转换一般由一个叫MMU的硬件完成。

1. 插入实现操作

ListInsert(ElementTypeX,inti,ListPtrL)

{

   Listp,s;

   if(i==1){//新结点插入在表头

       s= (List)malloc(sizeof(structLNode));//申请、填装结点

       s->Data=X;

       s->Next=PtrL;

       returns;//返回新表头指针

   }

   p=FindKth(i-1.PtrL);//查找第i-1个结点

   if( p==NULL){//第i-1个不存在，不能插入

       printf("参数i错");

       returnNULL;

   }else{

       s= (List)malloc(sizeof(structLNode));//申请、填装结点

       s->Data=X;

       s->Next=p->Next;//新结点插入在第i-1个结点的后面

       p->Next=s;

       returnPtrL; //这种情况下链表的头指针是不会变的

   }

}

//平均查找次数是n/2

1. 删除(删除链表的第i(1 <=  i  <= n)个位置上的结点)

//(1)先找到链表的第i-1个结点，用p指向;

//(2)再用指针s指向要被删除的结点(p的下一个结点);

//(3)然后修改指针，删除s所指结点;

//(4)删除的结点(s)的空间要记得free释放掉(重要)，这样内存空间才不会泄漏

ListDelete(inti,ListPtrL)

{

   Listp,s;

   if( i==1 ){//若要删除的是表的第一个结点

       s=PtrL;//s指向第一个结点

       if(PtrL!=NULL) PtrL=PtrL->Next;

       elsereturnNULL;

       free(s);//释放掉被删除结点

       returnPtrL;

   }

   p=FindKth(i-1,PtrL); //查找第i-1个结点，就是要删除结点的前一个结点在哪里

   if(p==NULL){

       printf("第%d个结点不存在",i-1); returnNULL;

   }elseif(p->Next==NULL){

       printf("第%d个结点不存在",i); returnNULL;

   }else{

       s=p->Next;//s指向第i个结点

       p->Next=s->Next;//从链表中删除

       free(s);//释放被删除结点

       returnPtrL;

   }

}

//平均时间复杂度也是n/2

1. 网络异常，图片无法展示

   |

2.1.6 广义表与多重链表

原本a,b,c所在的位置变成了指针，指向另一个一元多项式。这种就是广义表

广义表(Generalized List)

1. 广义表是线性表的推广
   
2. 对于线性表而言，n个元素都是基本的单元素;
   
3. 广义表中，这些元素不仅可以是单元素也可以是另一个广义表
   
4. 广义表可能会碰到的问题：一个域有可能不能分解的单元，有可能是一个指针(C语言的解决方法是使用union(联合))
   
5. union(联合)：可以把不同类型的数据组合在一起，可以把这个空间理解成某种类型，也可以理解为另外一种类型
   
6. 区分类型的方法：再弄个标记
   

typedefstructGNode*GList;

structGNode{

   intTag;//标志域：0表示结点时单元素，1表示结点是广义表   这个Tag就是标志

   union{//子表指针域Sublist与单元素数据域Data复用，即共同存储空间

       ElementTypeData;

       GListSubList;

   }URegion;

   GListNext;//指向后续结点

};

1. 网络异常，图片无法展示

   |

多重链表

多重链表：链表中的节点可能同时隶属于多个链

1. 多重链表中结点的指针域会有多个，如前面例子包含了Next和SubList两个指针域;
   
2. 但包含两个指针域的链表并不一定是多重链表，比如在双向链表不是多重链表。
   

多重链表有广泛的用途：基本上如树，图这样相对复杂的数据结构都可以采用多重链表的方式实现存储

多重链表指的是它里面的这个链表的结点可能同时隶属于多个链表(意思就是表中的指针会有多个)

稀疏矩阵：矩阵中的0很多，会造成空间浪费

二维数组可以用来表示选课的一种记录

上图中就是用多重链表来表示稀疏矩阵的一种方法

上图中的行与列相互穿插在一起形成十字链表

Head是作为行这个链表的头结点，也作为列这个链表的头结点

Tem：代表稀疏矩阵里面的非零的项

上图：4代表这个稀疏矩阵共有4行，总共有5列，非零项个数总共有7项

通过上图那个指针就可以找到所有列的头节点

在矩阵的多重链表表示中，第i行的head和第i列的head实际上是同一个结点(正确)

1. 用一个标识域Tag来区分头结点和非0元素结点
   
2. 头节点的标识值为"Head"，矩阵非0元素结点的标识值为"Term"
   
   网络异常，图片无法展示

   |
   
   

经过union的串联在一起，他们共性都是有两个指针：一个Down，一个Right。他们不一样的地方在中间部分。所有我们可以把他们union在一起，形成(a)这个结构

以上就是稀疏矩阵用十字链表解决的一种基本思路