计算机软件技术基础

1、计算机软件技术基础教 师：曾晓东电 话E_mail: 第三章 线性结构3.1 线性表3.2 顺序表3.3 线性链表3.4 栈3.5 队列3.6 数组计算机软件技术基础数据结构线性表3.1 线性表1、线性表概念定义： n(n0)个同类元素构成的有限线性序列，表示为L=（a1,a2,an）。n为线性表L的表长线性表的结构特性除第一个元素外，线性表中所有元素有唯一直接前驱除最后一个元素外，线性表中所有元素有唯一直接后继ai的直接前驱是ai-1，直接后继是ai+1计算机软件技术基础数据结构线性表3.1 线性表2、线性表运算1)初始化 initiate(L) 建立一个空线性表2

2、)求表长 length(L) 求表的数据元素个数3)取结点 get(L,i) 取第i个元素内容(或结点地址指针）4)定位 locate(L,x) 求元素x的下标或地址5)插入 insert(L,i,x) 将元素x插入到第i个元素之前6)删除 delete(L, i) 删除第i个元素7)遍历 getlist(L)读取线性表L的所有元素一次8)排序 sort(L)对L的元素重新排列，使其有序计算机软件技术基础数据结构线性表3.1 线性表3、线性表的分类按存储方式分类顺序表链表按可进行的操作的不同分类栈队列串数组计算机软件技术基础数据结构线性表3.2 顺序表1、顺序表的概念用一组地址连续的存储单元存

3、放线性表的数据元素，称为线性表的顺序存储结构，也称为向量式存储结构。该结构用高级语言中的一维数组类型表示。数组中的分量下标即为元素在线性表中的序号。例如：可用一维数组An来存储线性表：（a1, a2 ,.，an）。 这里需要声明：C语言中，数组下标从0开始。计算机软件技术基础数据结构线性表3.2 顺序表地址计算：设每个元素占L个单元，线性表在内存中的首地址为：Loc(a1)=b，则线性表中第i个元素的存储地址为： Loc(ai)=Loc(ai-1)+L=Loc(a1)+(i-1)*L=b+(i-1)*L特点：这种存储结构只要知道元素的序号，就很容易找到第i个数据元素，且无论序号i为何值，找到第

4、i个元素所需时间相同。所以，这种存储结构亦称为随机存储结构。计算机软件技术基础数据结构线性表顺序表的类型定义const int MAXSIZE 100;struct SequenList elemtype dataMAXSIZE;int length;顺序表类型的变量定义SequenList list, *L;约定表元素从数组的下标1处开始存放，下标0处不存放数据3.2 顺序表计算机软件技术基础数据结构线性表3.2 顺序表2、顺序表有关操作1) 顺序表初始化操作: 建立一个长度为零的空表接口： 入口和出口参数均为表头指针 L算法描述：令表长度字段 list.length为零 函数实现： voi

5、d initiate(SequenList &L) L.length = 0;计算机软件技术基础数据结构线性表3.2 顺序表2) 顺序表的插入 操作:从末尾至第i个结点将内容依次后挪将新结点放入第i个结点位置表长度加一 接口： 入口参数: 表头指针 L，位置 i，新结点x出口参数: 表头指针 L函数值：成功则返回1(用true表示),失败则返回0(用false表示)计算机软件技术基础数据结构线性表3.2 顺序表(3) 算法描述计算机软件技术基础数据结构线性表3.2 顺序表(4) 函数实现const int true = 1;const int false = 0;int sqlistInser

6、t(SequenList &L, int i, elemtype x) int j;if(iL.length+1) return(false); for(j=L.length;j=i;j-） L.dataj+1 = L.dataj;/ 元素后移L.datai = x;L.length+ ;return(true);计算机软件技术基础数据结构线性表3.2 顺序表计算机软件技术基础数据结构线性表3.2 顺序表(5) 时间复杂度分析计算机软件技术基础数据结构线性表3.2 顺序表3）顺序表的删除 操作:从第i个结点至末尾将内容依次前挪表长度减一 接口： 入口参数：表头指针 L，位置 i出口参数: 表头

7、指针 L函数值：成功则返回 1 (用true表示),失败则返回 0 (用false表示)计算机软件技术基础数据结构线性表3.2 顺序表(3)算法描述计算机软件技术基础数据结构线性表3.2 顺序表 (4)函数实现int sqlistDelete(SequenList &L,int i) int j;if(iL.length) return(false); for(j=i+1;jL.length;j+）L.dataj-1=L.dataj;/ 元素前移L.length-; return (true);计算机软件技术基础数据结构线性表3.2 顺序表计算机软件技术基础数据结构线性表3.2 顺序表(5)

8、时间复杂度分析计算机软件技术基础数据结构线性表3.2 顺序表3、 顺序表的特点按序号访问结点，存取时间与位置无关，快可进行效率较高的折半查找操作插入和删除结点要挪动大量元素，时间长短与位置有关要求存放元素的存储单元连续；有时会造成空间浪费或溢出。适用范围一旦建立，则插入、删除操作较少，经常进行查询操作的线性表计算机软件技术基础数据结构线性表3.2 顺序表4、 归并算法la、lb为两个递增有序顺序表，试设计一个算法, 将这两个有序顺序表合并成一个递增有序的顺序表lc。其中lc为新生成的顺序表。例如：la中的数据元素为1,3,7,9,10，lb中的数据元素为2,4,5,6,8，则生成的lc应为1,

9、2,3,4,5,6,7,8,9,10设变量 i 和 j 分别是表la和lb的当前元素的下标，初始均为1。变量 k 是结果表当前元素的下标，初始为0，表示结果表初始为空。计算机软件技术基础数据结构线性表3.2 顺序表4、 归并算法当 i 和 j 都在两个表的表长内变化时, 根据对应项的大小,依次把较小者放至新表 k 所指位置中；当 i 与 j 中有一个已经超出表长时，将另一个表中的剩余部分照抄到新表中。la137910lb24568ijlc12345678910kiiiijjjjkkkkkkkkk3.2 顺序表4、 归并算法接口：入口参数： la、lb：源表出口参数： lc：结果表计算机软件技术

10、基础数据结构线性表3.2 顺序表4、 归并算法SequenList merg_list(SequenList &la, SequenList &lb) SequenList lc; initiate(lc); / 初始化结果链表 int i=1,j=1,k=0; / la、lb、lc当前元素的下标 while(i=la.length & j=lb.length) k+; if(la.datailb.dataj) lc.datak=la.datai; i+; / i所指元素放入结果表 3.2 顺序表4、 归并算法else lc.datak=lb.dataj; j+; / j所指元素放入结果表 w

11、hile(i=la.length) / la剩余元素放入结果表 k+; lc.datak=la.datai; i+; 3.2 顺序表4、 归并算法 while(jnext = NULL; return (h);hhead空NULL计算机软件技术基础数据结构线性表3.3 线性链表2) 单链表的建立算法：先建立一个空链表，然后不断插入新结点按插入位置有三种方法：每次插入结点在链首每次插入结点在链尾按数据域值大小排序我们介绍第2种方法。计算机软件技术基础数据结构线性表3.3 线性链表每次插在链尾的单链表建立方法 操作: 输入数据 x（为简化起见，我们假设结点的数据域仅为一个简单变量data） 若 x

12、=结束标志，结束 找到链尾 在链尾结点后插入一个新结点，返回 接口：入口/出口参数：表头指针 h计算机软件技术基础数据结构线性表3.3 线性链表（3）算法描述计算机软件技术基础数据结构线性表3.3 线性链表(4)函数实现void rcreate(LinkList &h) LinkList p=h;/ 指向链表当前结点的指针LinkList px;/ 新结点的指针elemtype x;/ 待插入元素while(p-next != NULL) p=p-next; / 将指针移至表尾x=pread();/ 读入元素，根据x的类型编写 while(x != -1)/ 只要x不是结束标志，就继续读入px

13、=new LNode;px-data=x; px-next=NULL;/ 生成新结点 p-next=px;/ 新结点链入至表尾 p=p-next ;/ 链表当前指针后移 x=pread();/ 继续读入下一结点计算机软件技术基础数据结构线性表3.3 线性链表3) 线性链表的插入在链表L中q结点后插入结点s要涉及两个指针的修改：新结点s的指针域指向原结点q的后继结点p：s-next = q-next 原结点q的指针域指向新结点s：q-next = s计算机软件技术基础数据结构线性表3.3 线性链表算法一：在线性表的第i个结点前插入新结点 操作: 在链表L中找到第 i-1 个结点 动态分配一个新结

14、点 新结点指针域赋值指向 i 结点 i-1 结点指针域改指向新结点 接口： . 入口参数：表头指针h，序号 i ，数据变量x . 出口参数: 表头指针h计算机软件技术基础数据结构线性表3.3 线性链表算法描述计算机软件技术基础数据结构线性表3.3 线性链表（4）函数实现LinkList insert(LinkList &h,int i,elemtype x) LinkList p=h,t ; int j=0;while(p!=NULL & jnext ; j+; if(j!=i-1) return(NULL); /表长小于i-1，插入失败t = new LNode;t-data = x ; /

15、 生成新结点t-next = p-next ; p-next = t; / 新结点链入至p结点之后return(h);计算机软件技术基础数据结构线性表3.3 线性链表(5)算法分析本算法的主要运算为单链表指针的后移，共需移动i次与前面对顺序表的分析类似，可得此算法的时间复杂度为O(n)但此算法不需移动数据元素，故在数据元素较大时，此算法为优计算机软件技术基础数据结构线性表3.3 线性链表算法二：在线性链表中的p结点后面插入一个值为x的新结点 操作: 动态分配一个新结点 新结点数据域赋值 x 新结点指针域指向原后继结点 原结点指针域指向新结点 接口：入口参数：链表头结点head，结点指针p ，数

16、据变量x出口参数: 链表头结点head计算机软件技术基础数据结构线性表3.3 线性链表（3）算法描述计算机软件技术基础数据结构线性表3.3 线性链表（4）函数描述LinkList insert(LinkList &head,LinkList p,datatype x)LinkList s;if(head=NULL)/ 如果表为空，则对其初始化head=initiate(); p=head;s = new LNode;s-data = x;/ 生成新结点s-next = p-next;p-next = s;/ 新结点链入至p结点之后return(head);/ 返回链表的头结点计算机软件技术基础

17、数据结构线性表3.3 线性链表4) 线性链表的删除只涉及一个指针的修改：i结点前驱的指针域指向i结点后继结点：pi-1next = pinext 释放i结点pqhead a计算机软件技术基础数据结构线性表3.3 线性链表 操作: 在链表L中找到第 i-1 个结点 i结点指针域赋给i-1结点的指针域 释放i结点 接口： 入口参数：表头指针 h，序号 i出口参数: 无计算机软件技术基础数据结构线性表3.3 线性链表(3)算法描述计算机软件技术基础数据结构线性表3.3 线性链表(4)函数实现void delete(LinkList &h, int i) LinkList p=h, s; int j=

18、0;while(p != NULL & j next ; j+; / 查找第i-1个结点if(j != i-1) return;/ 表长小于i-1，删除失败s = p-next;/ 第i个结点if(s=NULL) return;/ 表长小于i，删除失败p-next = s-next; / 将i结点从链表中移除delete(s);/ 释放i结点计算机软件技术基础数据结构线性表3.3 线性链表3、线性链表的特点优点：内存利用好，插入删除方便，效率较高缺点：元素访问不方便不能进行效率较高的折半查找适用范围变动较大（删除、插入频繁）的线性表计算机软件技术基础数据结构线性表3.3 线性链表4、循环链表特

19、点：表中最后一个结点的指针域不为空，而是指向表头，整个链表形成一个环。与一般链表不同之处在于只要给定循环链表中任一结点的地址，就可以查遍表中所有的结点，而不必从头指针开始。head非空表head空表计算机软件技术基础数据结构线性表4、循环链表表尾元素的next指针不为NULL判断表是否为空的方法是判断头结点的next指针是否指向头结点好处：从链表中任何一个节点都可以找到其它的节点。计算机软件技术基础数据结构线性表四、循环链表与双向链表2) 采用尾指针的循环链表rear-next-next非空表rear空表rearrear-next-next非空表rear空表rear计算机软件技术基础数据结构线

20、性表四、循环链表与双向链表3) 两个循环链表的链接rbrap存储池计算机软件技术基础数据结构线性表四、循环链表与双向链表两循环链表的链接LinkList CONNECT(LinkList ra,LinkList rb) LinkList p;/*1*/pra-next;/ 获取ra的头结点/*2*/ra-nextrb-next-next;/ 将rb链入ra中/*3*/delete (rb-next);/ 释放rb的头结点/*4*/rb-nextp;/ rb的尾结点的后继为ra的头结点return(rb);/ 返回链表的尾指针 计算机软件技术基础数据结构线性表3.3 线性链表5、双向链表特点表中

21、每个结点有两个指针域：一个指向直接后继，一个指向直接前驱，那么从表中任一结点都可以随意向前或向后查找。但在作插入、删除运算时，需同时修改两个方向上的指针。(1)带头结点的双向循环链表（空表）head头结点(2)带头结点的双向循环链表（非空表）head计算机软件技术基础数据结构线性表5、双向链表2）初始化（1）结点构成数据域 data前趋指针域 prior后继指针域 nextdatanextprior(1) 结点结构（2）类型定义:struct DuLNode elemtype data ；/ 数据域 DuLNode *prior, *next;/ 前趋后继指针;typedef DuLnode*

22、 DuLinkList；计算机软件技术基础数据结构线性表5、双向链表3)双向链表逻辑结构.h. priora1 next。priorai next。prior an 。pi结点后继结点为 p-next；前趋结点为 p-prior满足关系：(p-next)-prior = p (p-prior)-next = p4)操作对仅需涉及一个方向指针的操作与单链表相同，如：求表长 LENGTH(L)、取元素 GET(L,i)、定位LOCATE(L, x) 在插入、删除时不同，需同时修改两个方向上的指针计算机软件技术基础数据结构线性表5、双向链表(1) 双向链表的后插操作将数据x插入到以head为表头指针

23、的双向链表中的p结点的后面void duInsert(DuLinkList &head,DuLinkList p,elemtype x)DuLinkList s;snew DuLNode; s-datax; s-nextp-next; s-priorp; p-next-priors; p-nexts;psabx计算机软件技术基础数据结构线性表5、双向链表(2) 双向链表的删除操作删除以head为头结点的双向链表中的结点pvoid DuDelete(DuLinkList &head,DuLinkListp p)p-prior-next = p-next;p-next-prior = p-prio

24、r;delete(p);abcp计算机软件技术基础数据结构线性表6、应用实例一元多项式相加 问题描述一个一元多项式可以表示为：其中每一项由系数Pi及x的指数i组成。若多项式按升幂排列，则它由n+1个系数唯一确定，因此可以用一个线性表P表示：其指数i隐藏在系数Pi的序号内。3.3 线性链表计算机软件技术基础数据结构线性表 问题分析1）存储结构：多项式相加时，常要合并同类项，由此就要改变多项式的系数和指数，而且在实际问题中，时常会出现多项式的次数很高但又存在大量零系数的项，因此宜采用带头结点的链式存储结构。2）结点结构：每一个非零项构成链表中的一个结点，结点由两个数据域（系数coef和指数exp）

25、和一个指针域构成，如下图：struct PolyNode double coef;int exp;PolyNode *next;typedef PolyNode * PolyList;coef exp nextpi6、应用实例3）链表结构：采用带头结点的线性链表表示多项式A(x)、B(x)，相加后结果在线性链表C(x)中。4）运算过程：设指针ha、hb、hc分别为多项式链表A(x)、B(x)、C(x）的头指针，指针pa、pb的初始位置分别指向A(x)、B(x)中的第一项。指针pc指向C(x)的最后一项，初始为hc6、应用实例计算机软件技术基础数据结构线性表过程为：循环比较pa、pb所指结点中的

26、指数项。若：pa-expexp，根据pa所指结点生成新结点，链入到结果链表中，即链入到pc之后，然后pa、pc后移；若：pa-exppb-exp，根据pb所指结点生成新结点，然后链入到pc之后，然后pb、pc后移；若：pa-exp=pb-exp，则将两个结点中的系数相加，当和不为零时，生成结点，将其链入到pc之后，pc后移。然后pa、pb后移 算法描述（一元多项式加法）6、应用实例计算机软件技术基础数据结构线性表PolyList AddPoly(PolyList ha, PolyList hb) PolyList pa=ha-next, pb=hb-next; PolyList hc=initiate(),pc=hc, p; while (pa!=NULL & pb!=NULL)/ 遍历两个链表 if (pa-expexp)/ pa的指数较小，将其链入至hc p = new PolyNode; p-coef=pa-coef;p-exp=pa-exp; p-next=NULL;/ 生成新结点pc-next=p; / 链入至pc后pc=pc-next;pa