2012-2-24 《数据结构》读书笔记2 线性表

 

“软件只不过是人的思想产物，软件可能是人能造出来的最复杂的实体”这是昨天晚上UML（统一建模语言）老师的一句话，也更加坚定了我学习软件的决心，真的有这么复杂么，其实还是自己不够用心而已了，刚刚开完校青协会议回来，学校打算开启雷锋日系列活动，觉得这几个月又得忙了（还好青协有一群得力助手），每次办的爱心活动有一个好处，就是能够让自己回归原点，所有人性的劣根，社会的污垢，周围的琐事都感觉很微不足道，反而能够更加进下心来写写读书笔记了。

———————————————————————————————————————————————

 

由于一开始绪论没有学好，线性表学的有点唐突了，字面意思不过总的来讲线性表就是一组具有线性结构的表型形式，就像一条线一样的表格，里面顺序放着数据，也是最简单的一种数据结构，并且是一组有限的序列，不管学什么结构，人为定义的一些东西还是先了解为好，前驱后继说白了就是一个表的前后元素。

涉及的函数在实践应用中非常有用，不光要只会打include<list>，还要理解函数才能灵活运用下

19页的ADT代码我实现了并整理了下（将枯燥上升为艺术= =不然看的打瞌睡）：

 

 

 

 

部分代码说明：

     Malloc是c语言动态分配的，用c++来写就是L=new int (n) ，n是要分配的大小，删除是delete [] L.

     至于里面的一些英文应该在头文件中有所定义

     #define LIST_INIT_SIZE 10  

     #define LISTINCREMENT 2 

     typedef int ElemType;

     #define TRUE 1

     #define FALSE 0

     #define OK 1

     #define ERROR 0

     #define INFEASIBLE -1

     typedef int Status; 

     typedef int Boolean; 

 

     Return ok即return 1，因为前面有#define OK 1

有人会问return 0，return 1，return -1这些有什么用呢

其实，这里只是返回函数的一个值，1代表真，0代表假之类的

具体来言单个函数是没有什么用的，如果碰到某些要判断的函数的时候，比如判断函数是否为真，就可以直接if（函数）了，就方便多了，经string点拨了下我才明白这个，以前也困惑过。

 

 

 

这些线性表的基本操作完全可以用#include <list>来替代，list里面包含了这些全部的函数

说到这里，写线性表的题目最好用文件的封装比较方便，简单来说就是不同性质的代码放在不同文件里面，比如头文件里面就放#include什么的或者define什么的，头文件（后缀名为.h）里面还可以将函数数据用类的封装封装好，然后工具函数放在cpp文件里面（.cpp或.c）

但是在main文件里面要调用函数的时候还是要在头文件申明函数，工具文件实现函数代码，main文件用来调用。但是调用头文件的时候用#include "c1.h"(假设我创建的头文件是c1.h)，接下来我们直接看算法吧。

 

算法2.1

 

 void Union(SqList *La,SqList Lb) /* 算法2.1 */

 { /* 将所有在线性表Lb中但不在La中的数据元素插入到La中 */

   ElemType e;

   int La_len,Lb_len;

   int i;

   La_len=ListLength(*La); /* 求线性表的长度 */

   Lb_len=ListLength(Lb);

   for(i=1;i<=Lb_len;i++)

   {

     GetElem(Lb,i,&e); /* 取Lb中第i个数据元素赋给e */

     if(!LocateElem(*La,e,equal)) /* La中不存在和e相同的元素,则插入之 */

       ListInsert(La,++La_len,e);

   }

 }

 

ElemType 只不过是int ，用了重定义而已。

遍历Lb，中间值e，把b一个一个给e然后e和La的元素比较，比较后插入。

这里的La,Lb都是sqlist类型

即typedef struct

 {

   ElemType *elem; /* 存储空间基址 */

   int length; /* 当前长度 */

   int listsize; /* 当前分配的存储容量(以sizeof(ElemType)为单位) */

 }SqList;

这就是一个线性表的结构由三个部分组成，如解析。

其他算法也大同小异，只不过是函数不同，顺着语句读下去就可以明了。

 

 

着重谈下线性链表，既然是链表就要更加的灵活，他的存储结构是

struct LNode

 {

   ElemType data;

   struct LNode *next;

 }*Link ,*position;  (Link和position只是为了区别一个是头，而position是任意的指向,一个盒子里面左边放数据右边放指针—指向下一个结点的地址)

加上

Typedef struct{

   Link head,tail;

   Int len;

}LinkList;(盒子里面装了三样东西，头尾的指针，因为是Link型的，还有就是元素的个数len。)

链式表的函数与线性表没有本质的区别，只是在变量上面花了一些功夫而已。

以下也是线性链表有关的函数我整理了如下：

 

 

部分代码说明：

void CreateList(LinkList *L,int n) 生成链表是逆位序，是插在表头的，这里的代码要注意P和L的关系，之前定义的是LinkList *L，LinkList p，L是一个单链表，而p动态分配的为一个结点，即L中众多结点的一个，然后输入p->data是一个数据，接着p->next=(*L)->next; /* 插入到表头 */是指p的指针域接在L链表的下一个，最后再(*L)->next=p，这样又可以操作p来实现L链表了

string帮我分析了下，最好画图来理解每一个量的意义，把内存地址和数据实物分开来体现会比较直观

正序位插入也大同小异，定义了两个备用结点p,q，然后q=*L，输入p->data p的数据，然后q->next=p， q=q->next;实现重用。注意这个问题上有个关键要理解，就是头结点是没有数据域的，string提醒了我这点，不然整个链表就不好理解了头结点和第一个结点要予以区分，第一个结点就是头结点的指针域指向的结点。

   至于其他代码，只要理解每个量的数据包括那几块然后照这样分析，就应该没有问题了。 

 

     

   例如算法2.20

   已知单链线性表La和Lb的元素按值非递减排列，合并排列到Lc中，定义ha，hb，pa，pb，q为LNode类型，La和Lb为LinkList表单类型，即存了头结点尾结点和链表长度的结构体，要予以区分它们的类型是关键，里面用到的函数我就没有打出来了，具体的与线性表大同小异，只是改为链式结构。

    Status MergeList_L(LinkList La,LinkList Lb,LinkList  *Lc,int(*compare)(ElemType,ElemType))

 { /* 已知单链线性表La和Lb的元素按值非递减排列。归并La和Lb得到新的单链 */

   /* 线性表Lc，Lc的元素也按值非递减排列。（不改变La、Lb）算法2.21 */

   Link ha,hb,pa,pb,q;

   ElemType a,b;

   if(!InitList(Lc))

     return ERROR; /* 存储空间分配失败 */

   ha=GetHead(La); /* ha和hb分别指向La和Lb的头结点 */

   hb=GetHead(Lb);

   pa=NextPos(ha); /* pa和pb分别指向La和Lb的第一个结点 */（这里指出，头结点和第一个结点是有区别的，头结点是一个结点但是没有数据域，只有指针域，而第一个结点是在头结点之后的）

   pb=NextPos(hb);

   while(!ListEmpty(La)&&!ListEmpty(Lb)) /* La和Lb均非空 */

   {

     a=GetCurElem(pa); /* a和b为两表中当前比较元素 */

     b=GetCurElem(pb);

     if(compare(a,b)<=0)

     {

       DelFirst(&La,ha,&q);

       InsFirst(Lc,(*Lc).tail,q);

       pa=NextPos(ha);

     }（这是一个插入结点的语句）

     else /* a>b */

     {

       DelFirst(&Lb,hb,&q);   

       InsFirst(Lc,(*Lc).tail,q);

       pb=NextPos(hb);

     }

   }

   if(!ListEmpty(La))

     Append(Lc,pa);

   else

     Append(Lc,pb);  （这里的意思是将表剩下的部分插入）

   FreeNode(&ha);

   FreeNode(&hb);

   return OK;

 }

 

 

 

说下静态链表，静态链表就是在不改变整体的情况下删减线性表中的元素

比如我们之前删减线性表的元素如果是插入就要求插入到该位置后面的额所有元素都要后移一位然后插入，删除某个元素就后面元素前移一位，而静态链表是这样实现的

  

 

 

 

如上表，将shi插入表中但是整体表没有变化只是改变了第二个指针域中的指针指向达到插入的需求，所以这种不改变整体状态变化的表叫做静态链表。

 

当然有人会问了，线性表的顺序存储和链式存储有何优缺点？

   顺序表优点很显著，比如方法简单，数组之类的容易实现，第二就是不会为了结点之间的逻辑顺序而烦恼，第三就是查找速度快，因为元素都是顺序下来的。缺点也有，插入删除都要移动元素比较麻烦，静态分配的时候预先分配的空间比较大。

   链式存储表的话优点是插入删除容易实现，还可以采取动态内存分配不会浪费太大空间。缺点也有有些不支持指针的语言中不容易实现，并且不能随机访问，只能从头指针开始。

   

 

由链式表引申出了循环链表，循环双向链表，后两者都是在不用的场合下发挥着作用

循环链表的特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。 　　

比如在链表上实现将两个线性表（a1，a2，…，an）和（b1，b2，…，bm）连接成一个线性表（a1，…，an，b1，…bm）的运算。 　　

分析：若在单链表或头指针表示的单循环表上做这种链接操作，都需要遍历第一个链表，找到结点an，然后将结点b1链到an的后面，其执行时间是O(n)。若在尾指针表示的单循环链表上实现，则只需修改指针，无须遍历，其执行时间是O(1)。 

   而双向链表，双向循环链表就是多了个指向前面的指针，这样会给查找或者排序带来很多方便的地方。

 

   特别注意：数组中访问任意的A[i]时间复杂度都为O（1），因为数组是随机访问的。

                    单链表的插入时间复杂度为O（n），因为需要遍历一遍链表。

                    单项循环链表判空的条件是head->next==head而不是head->next==0

               

 

相对来说线性表的题目没什么特别经典的例题，只是作为一个基础工具而言具有重要意义，好吧，以后此文会随时更新，有了新的想法就会记录下来。