《数学数据结构.pptx》由会员分享，可在线阅读，更多相关《数学数据结构.pptx（101页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、图2.1 线性表的逻辑结构 2.1 线性表的概念及运算2.1.1 线性表的逻辑结构 第1页/共101页 例如：英文字母表(A,B,Z)就是一个简单的线性表，表中的每一个英文字母是一个数据元素，每个元素之间存在唯一的顺序关系，如在英文字母表字母B的前面是字母A，而字母B的后面是字母C。在较为复杂的线性表中，数据元素(data elements)可由若干数据项组成，如学生成绩表中，每个学生及其各科成绩是一个数据元素，它由学号、姓名、各科成绩及平均成绩等数据项(item)组成，常被称为一个记录(record)，含有大量记录的线性表称为文件(file)。数据对象（data object）是性质相同的数
2、据元素集合。第2页/共101页表2-1 车辆登记表 第3页/共101页 线性表(Linear List)是由n(n0)个类型相同的数据元素a1,a2,，an组成的有限序列，记作（a1,a2,，ai-1，ai，ai+1，an）。这里的数据元素ai(1in)只是一个抽象的符号，其具体含义在不同情况下可以不同，它既可以是原子类型，也可以是结构类型但同一线性表中的数据元素必须属于同一数据对象。此外，线性表中相邻数据元素之间存在着序偶关系，即对于非空的线性表（a1,a2,，ai-1,ai,ai+1,an），表中ai-1 领先于ai，称ai-1 是ai的直接前驱，而称ai是 ai-1的直接后继。除了第一个
3、元素a1外，每个元素ai有且仅有一个被称为其直接前驱的结点ai-1，除了最后一个元素an外，每个元素ai有且仅有一个被称为其直接后继的结点ai+1。线性表中元素的个数n被定义为线性表的长度，n=0时称为空表。第4页/共101页 线性表的特点可概括如下：同一性：线性表由同类数据元素组成，每一个ai必须属于同一数据对象。有穷性：线性表由有限个数据元素组成，表长度就是表中数据元素的个数。有序性：线性表中表中相邻数据元素之间存在着序偶关系。由此可看出，线性表是一种最简单的数据结构，因为数据元素之间是由一前驱一后继的直观有序的关系确定；线性表又是一种最常见的数据结构，因为矩阵、数组、字符串、堆栈、队列等
4、都符合线性条件。第5页/共101页2.1.2 线性表的抽象数据类型定义 ADT LinearList 数据元素：D=ai|aiD0,i=1,2,，n,n0，D0为某一数据对象 关系：|ai,ai+1D0，i=1,2,n-1 基本操作：（1）InitList（L）操作前提：L为未初始化线性表。操作结果：将L初始化为空表。第6页/共101页（2）DestroyList(L)操作前提：线性表L已存在。操作结果：将L销毁。（3）ClearList(L)操作前提：线性表L已存在。操作结果：将表L置为空表。（4）EmptyList（L）操作前提：线性表L已存在。操作结果：如果L为空表则返回真，否则返回假。
5、第7页/共101页 （5）ListLength（L）操作前提：线性表L已存在。操作结果：如果L为空表则返回0，否则返回表中的元素个数。（6）Locate(L,e)操作前提：表L已存在，e为合法元素值。操作结果：如果L中存在元素e，则将“当前指针”指向元素e所在位置并返回真，否则返回假。（7）GetData(L,i)操作前提：表L存在，且i值合法，即1iListLength（L）。操作结果：返回线性表L中第i个元素的值。第8页/共101页 （8）InsList(L,i,e)操作前提：表L已存在，e为合法元素值且1iListLength(L)+1。操作结果：在L中第i个位置插入新的数据元素e，L的
6、长度加1。（9）DelList(L,i,&e)操作前提：表L已存在且非空，1iListLength(L)。操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。ADT LinearList 第9页/共101页2.2 线性表的顺序存储2.2.1 线性表的顺序存储结构 线性表的顺序存储是指用一组地址连续的存储单元依 次存储线性表中的各个元素，使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。采用顺序存储结构的线性表通常称为顺序表。第10页/共101页 假设线性表中有n个元素，每个元素占k个单元，第一个元素
7、的地址为loc(a1)，则可以通过如下公式计算出第i个元素的地址loc(a-i)：loc(ai)=loc(a1)+(i-1)k其中loc(a-1)称为基地址。第11页/共101页图2.2 顺序表存储示意图 第12页/共101页 顺序存储结构可以借助于高级程序设计语言中的一堆数组来表示，一维数组的下标与元素在线性表中的序号相对应。线性表的顺序存储结构可用C语言定义如下：define MAXSIZE=线性表可能达到的最大长度typedef struct ElemType elemMAXSIZE；/*线性表占用的数组空间*/int last；/*记录线性表中最后一个元素在数组elem 中 的位置（下
8、标值），空表置为-1*/SeqList；第13页/共101页2.2.2 线性表顺序存储结构上的基本运算 1.查找操作 线性表有两种基本的查找运算。按序号查找GetData(L,i):要求查找线性表L中第i个数据元素，其结果是L.elemi-1或L-elemi-1。按内容查找Locate（L,e）:要求查找线性表L中与给定值e相等的数据元素，其结果是：若在表L中找到与e相等的元素，则返回该元素在表中的序号；若找不到，则返回一个“空序号”，如-1。查找运算可采用顺序查找法实现，即从第一个元素开始，依次将表中元素与e相比较，若相等，则查找成功，返回该元素在表中的序号；若e与表中的所有元素都不相等，则
9、查找失败，返回“-1”。第14页/共101页算法描述：int Locate(SeqList L，ElemType e)/*在顺序表L中依次存放着线性表中的元素，在表中查找与e相等的元素，若 Li=e，则找到该元素，并返回i值，若找不到，则返回“-1”*/i=0;/*i为扫描计数器，初值为0，即从第一个元素开始比较*/while(i=L.last)&(L.elemi!=e)/*顺序扫描表，直到找到值为key的元素,i+;或扫描到表尾而没找到*/if (ilast+1，i的合法取值范围是 1iL-last+2 */int k;if(iL-last+2)/*首先判断插入位置是否合法*/printf(
10、插入位置i值不合法)；return(ERROR);第18页/共101页if(L-last=maxsize-1)printf(表已满无法插入)；return(ERROR);for(k=L-last;k=i-1;k-)/*为插入元素而移动位置*/L-elemk+1=L-elemk;L-elemi-1=e;/*在C语言数组中，第i个元素的下标为i-1*/L-last+;return(OK);第19页/共101页【算法2.2 线性表的插入运算】可以看出，当i=L-last+2时，语句L-elemk+1=L-elemk将不会执行，因为循环的终值大于初值，此时不需要移动元素，可直接在表尾插入e。当i=1时
11、，语句L-elemk+1=L-elemk需执行n次，即将表中已存在的n个元素依次后移一个位置才能将e插入。因此，语句L-elemk+1=L-elemk的频度与插入位置i有关。第20页/共101页 3.删除操作 线性表的删除运算是指将表的第i(1in)个元素删去，使长度为n的线性表(e1，,ei-1，ei，ei+1，en)变成长度为n-1的线性表(e1，,ei-1，ei+1，en)。例如：线性表(4,9,15,21,28,30,30,42,51,62)删除第5个元素，则需将第6个元素到第10个元素依次向前移动一个位置，如图2.4所示。第21页/共101页图2.4 顺序表中删除元素 第22页/共1
12、01页算法描述：int DelList(SeqList*L,int i,ElemType*e)/*在顺序表L中删除第i个数据元素，并用指针参数e返回其值。i的合法取值为1iL.last+1*/int k;if(iL-last+1)printf(删除位置不合法！)；return(ERROR);第23页/共101页*e=L-elemi-1;/*将删除的元素存放到e所指向的变量中*/for(k=i;ilast;k+)L-elemk-1=L-elemk;/*将后面的元素依次前移*/L-last-;Return(OK);第24页/共101页【算法2.3 线性表的删除运算】与插入运算类似，在顺序表上实现删
13、除运算也必须移动结点，这样才能反映出结点间的逻辑关系的变化。若i=L-last+1，则移位语句L-elemk-1=L-elemk不执行，因为循环变量的初值大于终值，此时不需要移动元素，仅将表长度减1即可。显然，删除算法中移位语句L-elemk-1=L-elemk的执行频度也与删除位置i有关。第25页/共101页 在顺序表中插入或删除一个数据元素时，其时间主要耗费在移动数据元素上。对于插入算法而言，设Pi为在第i个元素之前插入元素的概率，并假设在任何位置上插入的概率相等，即Pi=1/(n+1),i=1,2,，n+1。设Eins为在长度为n的表中插入一元素所需移动元素的平均次数，则 同理，设Qi为
14、删除第i个元素的概率，并假设在任何位置上删除的概率相等，即Q i=1/n,i=1,2,，n。删除一个元素所需移动元素的平均次数Edel为 第26页/共101页 例2-1 有两个顺序表LA和LB，其元素均为非递减有序排列，编写一个算法，将它们合并成一个顺序表LC，要求LC也是非递减有序排列。例如LA=(2,2,3),LB=(1,3,3,4),则LC=(1,2,2,3,3,3,4)。算法思想：设表LC是一个空表，为使LC也是非递减有序排列，可设两个指针i、j分别指向表LA和LB中的元素，若LA.elemiLB.elemj，则当前先将LB.elem j 插 入 到 表 LC中;若 LA.elem i
15、 LB.elem j，则 当 前 先 将LA.elemi插入到表LC中，如此进行下去，直到其中一个表被扫描完毕，然后再将未扫描完的表中剩余的所有元素放到表LC中。第27页/共101页void merge(SeqList*LA,SeqList*LB,SeqList*LC)int i,j,k,l;i=0;j=0;k=0;while(ilast&jlast)if(LA-elemielemj)LC-elemk=LA-elemi;i+;k+;else 第28页/共101页 LC-elemk=LB-elemj;j+;k+;while(ilast)/*当表LA比表LB长时，则将表LA余下的元素赋给表LC*/
16、LC-elemk=LA-elemi;i+;k+;while(jlast)/*当表LB比表LA长时，则将表LB余下的元素赋给表LC*/LC-elemk=LB-elemj;j+;k+;LC-last=LA-last+LB-last;第29页/共101页【算法2.4 线性表的合并运算】由上面的讨论可知，线性表顺序表示的优点是：(1）无需为表示结点间的逻辑关系而增加额外的存储空间（因为逻辑上相邻的元素其存储的物理位置也是相邻的）；(2）可方便地随机存取表中的任一元素。其缺点是：(1）插入或删除运算不方便，除表尾的位置外，在表的其它位置上进行插入或删除操作都必须移动大量的结点，其效率较低；(2)由于顺序
17、表要求占用连续的存储空间，存储分配只能预先进行静态分配，因此当表长变化较大时，难以确定合适的存储规模。若按可能达到的最大长度预先分配表空间，则可能造成一部分空间长期闲置而得不到充分利用；若事先对表长估计不足，则插入操作可能使表长超过预先分配的空间而造成溢出。第30页/共101页2.3 线性表的链式存储 2.3.1 单链表 图2.5 单链表的结点结构 第31页/共101页 单链表包括两个域：数据域用来存储结点的值；指针域用来存储数据元素的直接后继的地址（或位置）。链表正是通过每个结点的指针域将线性表的n个结点按其逻辑顺序链接在一起。由于链表的每个结点只有一个指针域，故将这种链表又称为单链表。由于
18、单链表中每个结点的存储地址是存放在其前趋结点的指针域中的，而第一个结点无前趋，因而应设一个头指针H指向第一个结点。同时，由于表中最后一个结点没有直接后继，则指定线性表中最后一个结点的指针域为“空”（NULL）。这样对于整个链表的存取必须从头指针开始。第32页/共101页 例如：图2.6所示为线性表（A,B,C,D,E,F,G,H）的单链表存储结构，整个链表的存取需从头指针开始进行，依次顺着每个结点的指针域找到线性表的各个元素。图2.6 单链表的示例图 第33页/共101页图2.7 单链表的逻辑状态 图2.8 带头结点单链表图示 第34页/共101页单链表可以由头指针唯一确定。单链表的存储结构描
19、述如下：typedef struct Node /*结点类型定义*/ElemType data；struct Node *next；Node,*LinkList；/*LinkList为结构指针类型*/假设L是LinkList型的变量，则L是一个结构指针，即单链表的头指针，它指向表中第一个结点（对于带头结点的单链表，则指向单链表的头结点），若L=NULL（对于带头结点的单链表为L-next=NULL），则表示单链表为一个空表，其长度为0。若不是空表，则可以通过头指针访问表中结点，找到要访问的所有结点的数据信息。对于带头结点的单链表L，p=L-next指向表中的第一个结点a1，即p-data=a1
20、，而p-next-data=a2。其余依此类推。第35页/共101页2.3.2 单链表上的基本运算 1.建立单链表图2.9 头插法建立单链表图示 第36页/共101页用头插法建立单链表的算法：Linklist CreateFromHead()LinkList L;Node *s;char c;int flag=1;/*设置一个标志变量flag，初值为1，当输入“$”时，将flag置为0，建表结束*/L=(Linklist)malloc(sizeof(Node);/*为头结点分配存储空间*/L-next=NULL;While(flag)第37页/共101页c=getchar();if(c!=$)
21、s=(Node*)malloc(sizeof(Node);/*为读入的字符分配存储空间*/s-data=c;s-next=L-next;L-next=s;else flag=0;return L;=第38页/共101页【算法2.5 用头插法建立单链表】2）尾插法建表 图2.10 尾插法建表图示 第39页/共101页 该算法的实现与头插法建表的不同之处在于指针的变化，其具体实现如下：Linklist CreateFromTail()/*将新增的字符追加到链表的末尾*/LinkList L;Node*r,*s;int flag=1;/*设置一个标志，初值为1，当输入“$”时，flag为0，建表结束
22、*/L=(Node*)malloc(sizeof(Node);/*为头结点分配存储空间*/L-next=NULL;r=L;/*r指针始终动态指向链表的当前表尾，以便于做尾插入，其初值指向头结点*/while(flag)第40页/共101页 c=getchar();if(c!=$)s=(Node*)malloc(sizeof(Node);s-data=c;r-next=s;r=s；else flag=0;r-next=NULL;/*将最后一个结点的next链域置为空，表示链表 的结束*/*while*/return L;/*CreateFromTail*/第41页/共101页【算法2.6 尾插法
23、建表】2.查找 1）按序号查找 在单链表中，由于每个结点的存储位置都放在其前一结点的next域中，因而即使知道被访问结点的序号i，也不能像顺序表那样直接按序号i访问一维数组中的相应元素，实现随机存取，而只能从链表的头指针出发，顺链域next逐个结点往下搜索，直至搜索到第i个结点为止。第42页/共101页 算法描述：设带头结点的单链表的长度为n，要查找表中第i个结点，则需要从单链表的头指针L出发，从头结点（L-next）开始顺着链域扫描，用指针p指向当前扫描到的结点,初值指向头结点，用j做计数器，累计当前扫描过的结点数（初值为0），当j=i 时，指针p所指的结点就是要找的第i个结点。第43页/共
24、101页Node*Get(LinkList L,int i)/*在带头结点的单链表L中查找第i个结点，若找到(1in)，则返回该结点的存储位置;*/*否则返回NULL*/int j；Node *p；p=L；j=0；/*从头结点开始扫描*/while(p-next!=NULL&jnext；/*扫描下一结点*/j+；/*已扫描结点计数器*/if（i=j）return p；/*找到了第i个结点*/else return NULL；/*找不到，i0或in*/*Get*/第44页/共101页【算法2.7 在单链表L中查找第i个结点】2)按值查找 算法描述：按值查找是指在单链表中查找是否有结点值等于e的结
25、点，若有的话，则返回首次找到的其值为e的结点的存储位置，否则返回NULL。查找过程从单链表的头指针指向的头结点出发，顺着链逐个将结点的值和给定值e作比较。第45页/共101页Node*Locate(LinkList L,ElemType key)/*在带头结点的单链表L中查找其结点值等于key的结点，若找到则返回该结点的位置p；否则返回NULL*/Node*p;p=L-next;/*从表中第一个结点比较*/while(p!KG-*2=NULL)if(p-data!KG-*2=key)p=p-next;else break;/*找到结点key，退出循环*/return p;/*Locate*/第
26、46页/共101页【算法2.8 在单链表L中查找值等于key的结点】3.单链表插入操作 算法描述：要在带头结点的单链表L中第i个位置插入一个数据元素e，需要首先在单链表中找到第i-1个结点并由指针pre指示，然后申请一个新的结点并由指针s指示，其数据域的值为e，并修改第i-1个结点的指针使其指向s，然后使s结点的指针域指向原第i个结点。插入结点的过程如图2.11所示。第47页/共101页int InsList(LinkList L,int i,ElemType e)/*在带头结点的单链表L中第i个位置插入值为e的新结点 */Node*pre,*s;int k;pre=L;k=0;while(p
27、re!KG-*2=NULL&knext;k=k+1;第48页/共101页if(k!=i-1)/*即while循环是因为pre=NULL或idata=e;/*将待插入结点的值e赋给s的数据域*/s-next=pre-next;/*完成插入操作*/pre-next=s;return OK;第49页/共101页【算法2.9 单链表插入操作】图2.11 在单链表第i个结点前插入一个结点的过程 第50页/共101页4.删除 图2.12 单链表的删除过程 第51页/共101页int DelList(LinkList L,int i,ElemType*e)/*在带头结点的单链表L中删除第i个元素，并将删除的
28、元素保存到变量*e中*/Node*p,*r;int k;p=L;k=0;while(p-next!KG-*2=NULL&knext;k=k+1;ZK)第52页/共101页if(k!=i-1)/*即while循环是因为p-next=NULL或inext;p-next=p-next-next;/*删除结点r*/free(r);/*释放被删除的结点所占的内存空间*/return OK;第53页/共101页【算法2.10 单链表删除操作】说明：删除算法中的循环条件（p-next!=NULL&ki-1）与前插算法中的循环条件（p!=NULL&knext=NULL）。int ListLength(Link
29、List L)/*本算法用来求带头结点的单链表L的长度*/Node*p;p=L-next;j=0;/*用来存放单链表的长度*/while(p!KG-*2=NULL)p=p-next;j+;return j;/*End of function ListLength*/第55页/共101页【算法2.11 求单链表的长度】例2-3 如果以单链表表示集合，假设集合A用单链表LA表示，集合B用单链表LB表示，设计算法求两个集合的差，即A-B。算法思想：由集合运算的规则可知，集合的差A-B中包含所有属于集合A而不属于集合B的元素。具体做法是，对于集合A中的每个元素e，在集合B的链表LB中进行查找，若存在与
30、e相同的元素，则从LA中将其删除。第56页/共101页void Difference(LinkList LA,LinkList LB)/*此算法求两个集合的差集*/Node *pre;*p,*r;pre=LA;p=LA-next;/*p指向LA表中的某一结点，而pre始终指向p 的前驱*/while(p!=NULL)q=LB-next;/*依次扫描LB中的结点，看是否有与LA中*p结点的值相同的结点*/while(q!=NULL&q-data!=p-data)q=q-next;if(q!KG-*2=NULL)第57页/共101页r=p;pre-next=p-next;p=p-next;free
31、(r);else pre=p;p=p-next;/*while(p!=NULL)*/第58页/共101页【算法2.12 用单链表求两个集合的差集】2.3.3 循环链表 循环链表(Circular Linked List)是单链表的另一种形式，它是一个首尾相接的链表。其特点是将单链表最后一个结点的指针域由NULL改为指向头结点或线性表中的第一个结点，就得到了单链形式的循环链表，并称为循环单链表。类似地，还有多重链的循环链表。在循环单链表中，表中所有结点都被链在一个环上，多重循环链表则是将表中的结点链在多个环上。为了使某些操作实现起来方便，在循环单链表中也可设置一个头结点。这样，空循环链表仅由一个
32、自成循环的头结点表示。第59页/共101页图2.13 带头结点循环单链表 第60页/共101页 例2-4 有两个带头结点的循环单链表LA、LB，编写一个算法，将两个循环单链表合并为一个循环单链表，其头指针为LA。算法思想：先找到两个链表的尾，并分别由指针p、q指向它们，然后将第一个链表的尾与第二个表的第一个结点链接起来，并修改第二个表的尾Q，使它的链域指向第一个表的头结点。第61页/共101页LinkList merge-1(LinkList LA,LinkList LB)/*此算法将两个链表的首尾连接起来*/Node*p,*q;p=LA;q=LB;while(p-next!=LA)p=p-n
33、ext;/*找到表LA的表尾，用p指向它*/while(q-next!=LB)q=q-next;/*找到表LB的表尾，用q指向它*/q-next=LA;/*修改表LB 的尾指针，使之指向表LA 的头结点*/p-next=LB-next;/*修改表LA的尾指针，使之指向表LB 中的第一个结点*/free(LB);return(LA);第62页/共101页【算法2.13 循环单链表的合并算法(1)】采用上面的方法，需要遍历链表，找到表尾，其执行时间是O(n)。若在尾指针表示的单循环链表上实现，则只需要修改指针，无需遍历，其执行时间是 O(1)。LinkList merge-2（LinkList R
34、A,LinkList RB)/*此算法将两个链表首尾连接起来*/Node*p;p=RA-next;/*保存链表RA的头结点地址*/RA-next=RB-next-next;/*链表RB的开始结点链到链表RA的终端结点之后*/free(RB-next);/*释放链表RB的头结点*/RB-next=p;/*链表RA的头结点链到链表RB的终端结点之后*/return RB;/*返回新循环链表的尾指针*/第63页/共101页【算法2.14 循环单链表的合并算法(2)】2.3.4 双向链表 循环单链表的出现，虽然能够实现从任一结点出发沿着链能找到其前驱结点，但时间耗费是O(n)。如果希望从表中快速确定某
35、一个结点的前驱，另一个解决方法就是在单链表的每个结点里再增加一个指向其前驱的指针域prior。这样形成的链表中就有两条方向不同的链，我们可称之为双(向)链表(Double Linked List)。双链表的结构定义如下 typedef struct DNode ElemType data；struct DNode*prior，*next；DNode,*DoubleList；第64页/共101页图2.14 双链表的结点结构 第65页/共101页 由于在双向链表中既有前向链又有后向链，寻找任一个结点的直接前驱结点与直接后继结点变得非常方便。设指针p指向双链表中某一结点，则有下式成立：p-prior
36、-next=p=p-next-prior 第66页/共101页图2.15 双向循环链表图示 第67页/共101页1.双向链表的前插操作 图2.16 双向链表插入操作 第68页/共101页int DlinkIns(DoubleList L,int i,ElemType e)DNode *s,*p;./*先检查待插入的位置i是否合法（实现方法同单链表的前插操作）*/./*若位置i合法，则让指针p指向它*/s=(DNode*)malloc(sizeof(DNode);if(s)s-data=e;s-prior=p-prior;p-prior-next=s;s-next=p;p-prior=s;ret
37、urn TRUE;else return FALSE;第69页/共101页【算法2.15 双向链表的插入操作】2.双向链表的删除操作 算法描述：图2.17 双向链表的删除操作 第70页/共101页int DlinkDel(DoubleList L,int i,ElemType*e)DNode *p;./*首先检查待插入的位置i是否合法（实现方法同单链表的删除 操作）*/./*若位置i合法，则让指针p指向它*/*e=p-data;p-prior-next=p-next;p-next-prior=p-prior;free(p);return TRUE;第71页/共101页【算法2.16 双向链表的
38、删除操作】例2-5 设一个循环双链表L=（a,b,c,d）,编写一个算法,将链表转换为L=（b,a,c,d）。算法思想：本题实际上是交换表中前两个元素的次序。第72页/共101页void swap(DLinkList L)DNode *p,*q,*h;h=L-next;/*h指向表中的第一个结点，即a*/p=h-next;/*p指向b结点*/q=h-prior;/*保存a 结点的前驱*/h-next=p-next;/*a结点的后继指向c结点*/p-next-prior=h;/*c结点的前驱指向a结点*/p-prior=q;/*将b结点插入，作为表的第一个结点*/p-next=h;L-next=
39、p;/*将表的头结点的next 域指向b结点*/第73页/共101页【算法2.17 交换循环双链表中前两个元素的次序】*2.3.5 静态链表 静态链表同样可以借助一维数组来描述：define Maxsize=链表可能达到的最大长度typedef struct ElemType data;int cursor;Component,StaticListMaxsize;第74页/共101页图2.18 静态链表的插入和删除操作示例 第75页/共101页 1.初始化 所谓初始化操作,是指将这个静态单链表初始化为一个备用静态单链表。设space为静态单链表的名字，av为备用单链表的头指针，其算法如下：vo
40、id initial(StaticList space,int*av)int k;space0-cursor=0;/*设置已用静态单链表的头指针指向位置0*/for(k=0;kcursor=k+1;/*连链*/spaceMaxsize-1=0;/*标记链尾*/*av=1;/*设置备用链表头指针初值*/第76页/共101页【算法2.18 静态单链表初始化】2.分配结点int getnode(int*av)/*从备用链表摘下一个结点空间，分配给待插入静态链表中的元素*/int i;i=*av;*av=space*av.cur;return i;第77页/共101页【算法2.19 分配结点】3.结点
41、回收void freenode(int*av,int k)/*将下标为 k的空闲结点插入到备用链表*/spacek.cursor=*av;*av=k;第78页/共101页【算法2.20 空闲结点回收】4.前插操作 在已用静态单链表space的第i个数据元素之前插入一个数据元素x。算法描述：先从备用单链表上取一个可用的结点；将其插入到已用静态单链表第i个元素之前。第79页/共101页void insbefore(StaticList space,int i,int*av)int j,k,m;j=*av;/*j为从备用表中取到的可用结点空间的下标*/av=spaceav-cursor;/*修改备用
42、表的头指针*/spacej-data=x;k=space0-cursor;/*k 为已用静态单链表的第一个元素的下标值*/for(ZK(m=1;mcursor;spacej-cursor=spacek-cursor;/*修改游标域，实现插入操作*/spacek-cursor=j;第80页/共101页【算法2.21 在已用静态单链表的第i个元素之前插入元素x】5.删除 删除已用静态单链表中第i个元素。算法描述：寻找第i-1个元素的位置，然后通过修改相应的游标域进行删除；将被删除的结点空间链到可用静态单链表中，实现回收。第81页/共101页void delete(StaticList space;
43、int i;int*av )int j,k,m;k=space0-cursor;for(m=1,mcursor;j=spacek-cursor;spacek-cursor=spacej-cursor;/*从已用表中删除第i 个 元素*/spacej-cursor=*av;/*将第i 个元素占据的空间回收，即将其链 入备用表*/av=j;/*置备用表头指针以新值*/第82页/共101页【算法2.22 删除已用静态单链表中的第i个元素】2.3.6 顺序表和链表的比较 1.基于空间的考虑 在链表中的每个结点，除了数据域外，还要额外设置指针（或光标）域，从存储密度来讲，这是不经济的。所谓存储密度(St
44、orage Density),是指结点数据本身所占的存储量和整个结点结构所占的存储量之比，即 存储密度=结点数据本身所占的存储量/结点结构所占的存储总量 第83页/共101页 一般地，存储密度越大，存储空间的利用率就越高。显然，顺序表的存储密度为1，而链表的存储密度小于1。例如单链表的结点的数据均为整数，指针所占空间和整型量相同，则单链表的存储密度为50%。因此若不考虑顺序表中的备用结点空间，则顺序表的存储空间利用率为100%，而单链表的存储空间利用率为50%。由此可知，当线性表的长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表作为存储结构。第84页/共101页 2.基于时间
45、的考虑 顺序表是由向量实现的，它是一种随机存取结构，对表中任一结点都可以在O(1)时间内直接地存取，而链表中的结点，需从头指针起顺着链找才能取得。因此，若线性表的操作主要是进行查找，很少做插入和删除时，宜采用顺序表做存储结构。在链表中的任何位置上进行插入和删除，都只需要修改指针。而在顺序表中进行插入和删除，平均要移动表中近一半的结点，尤其是当每个结点的信息量较大时，移动结点的时间开销就相当可观。因此，对于频繁进行插入和删除的线性表，宜采用链表做存储结构。若表的插入和删除主要发生在表的首尾两端，则宜采用尾指针表示的单循环链表。第85页/共101页 3.基于语言的考虑 对于没有提供指针类型的高级语
46、言，若要采用链表结构，则可以使用光标实现的静态链表。虽然静态链表在存储分配上有不足之处，但它和动态链表一样，具有插入和删除方便的特点。值得指出的是，即使是对那些具有指针类型的语言，静态链表也有其用武之地。特别是当线性表的长度不变，仅需改变结点之间的相对关系时，静态链表比动态链表可能更方便。第86页/共101页2.4 一元多项式的表示及相加 对于符号多项式的各种操作，实际上都可以利用线性表来处理。比较典型的是关于一元多项式的处理。在数学上，一个一元多项式Pn(x)可按升幂的形式写成：它实际上可以由n+1个系数唯一确定。因此，在计算机内，可以用一个线性表P来表示：第87页/共101页 假设Qm(x
47、)是一个一元多项式，则它也可以用一个线性表Q来表示，即 若假设mcoef=c;s-exp=e;rear-next=s;/*在当前表尾做插入*/rear=s;scanf(%d,%d,&c,&e);rear-next=NULL;/*将表的最后一个结点的next置NULL，以示表结束*/return(head);第93页/共101页【算法2.23 用尾插法建立一元多项式的链表】（3）图 2.19 所 示 为 两 个 多 项 式 的 单 链 表，分 别 表 示 多 项 式A（x）=7+3x+9x8+5x17和多项式B(x)=8x+22x7-9x8。图2.19 多项式的单链表表示法 第94页/共101页
48、 多项式相加的运算规则是：两个多项式中所有指数相同的项的对应系数相加，若和不为零，则构成“和多项式”中的一项；所有指数不相同的项均复抄到“和多项式”中。以单链表作为存储结构，并且“和多项式“中的结点无需另外生成，则可看成是将多项式B加到多项式A中，由此得到下列运算规则（设p、q分别指向多项式A、B的一项，比较结点的指数项）：若p-expexp，则结点p所指的结点应是“和多项式”中的一项，令指针p后移；第95页/共101页 若p-expq-exp，则结点q所指的结点应是“和多项式”中的一项，将结点q插入在结点p之前，且令指针q在原来的链表上后移；若p-exp=q-exp，则将两个结点中的系数相加
49、，当和不为零时修改结点p的系数域，释放q结点；若和为零，则和多项式中无此项，从A中删去p结点，同时释放p和q结点。第96页/共101页void polyadd(Polylist polya;Polylist polyb)/*此函数用于将两个多项式相加，然后将和多项式存放在多项式polya中，并将多项式ployb删除*/Polynode *p,*q,*pre;*temp;int sum;p=polya-next;/*令p和q分别指向polya和polyb多项式链表中的第一个结点*/q=polyb-next;pre=polya;/*pre指向和多项式的尾结点*/while（p!=NULL&q!=N
50、ULL）/*当两个多项式均未扫描结束时*/第97页/共101页if （p-expexp）/*如果p指向的多项式项的指数小于q的指数，将p结点加入到和多项式中*/pre-next=p;pre=pre-next;p=p-next；else if(p-exp=q-exp）/*若指数相等，则相应的系数相加*/sum=p-coef+q-coef;if(sum!KG-*2=0)p-coef=sum;pre-next=p;pre=pre-next;p=p-next;else 第98页/共101页 temp=p-next;free(p);p=temp;/*若系数和为零，则删除结点p与q，并将指针指向下一个结点