《计算机软件基础：第2章线性数据结构 - 2链表》由会员分享，可在线阅读，更多相关《计算机软件基础：第2章线性数据结构 - 2链表（85页珍藏版）》请在金锄头文库上搜索。
1、第第2 2章章 线性数据结构线性数据结构 2.2 线线 性性 表表 2.2.1 线性表的定义及操作 定义2-1 线线性性表表(Linear-list)是n(n0)个数据元素的有限序列（一对一）。记为： (a1，a2, ., an) 其中，数据元素个数n称为表表的长长度，n = 0时，称此线性表为空表空表。第第2 2章章 线性数据结构线性数据结构 线性表的结构仅涉及诸元素的线线性性相对位置，即第i个元素ai处在第i-1个元素ai-1的后面和第i+1个元素ai+1的前面，这种位置上的有序性就是一种线性关系，所以线性表是一种线性结构。 线性表中每个数数据据元元素素a ai i的的具具体体含含义义，在
2、不同情况下各不相同，它可以是一个数，或是一个符号，也可以是一页书，甚至是其它更复杂的信息。但在同一个线性表中的数据元素必须具有相同的特性(或者说具有相同的类型)。 第第2 2章章 线性数据结构线性数据结构 线线性性表表的的逻逻辑辑结结构构：若线性表是非空表，则第一个元素a1无前驱（前件）（只有一个根结点或首结点），最后一个元素an无后继（后件），其它元素ai(1in)均只有一个直接前驱ai-1和一个直接后继ai+1。 下面给出几个线性表的例子： 例例2-1 26个大写的英文字母表：(A，B，C，.，Z) 例例2-2 某校从1996年到2002年各种型号计算机拥有量的变化情况，可以用线性表给出：
3、 (200，220，250，300，400，700，1200)第第2 2章章 线性数据结构线性数据结构 例例2-3 某单位职工政治面貌登记表如表2-2所示，每个职工的情况为一条记录，它由职工号、姓名、性别、职称、工龄、政治面貌六个数据项组成。 在表2-2中，一个数据元素由若干个数据项组成。在这种情况下，常把数据元素称为记记录录，含有大量记录的线性表又称为文件文件。第第2 2章章 线性数据结构线性数据结构 表2-2 职工政治面貌登记表 职工号姓 名性 别职 称工 龄政治面貌 0001 0002 0003 张 忠王 平李 林男女男工程师助 工助 工1222党员团员团员第第2 2章章 线性数据结构线
4、性数据结构 线性表是一个相当灵活的数据结构，它的长度可以根据需要增减，操作也比较灵活方便。线线性性表表的的基基本本操操作作有以下几种： (1) INITIATE(L)。初始化初始化操作操作，设定一个空的线性表L。 (2) LENGTH(L)。求求表表长长，求出线性表L中数据元素个数。 (3) GET(L，i)。取元取元素函数素函数，若1iLENGTH(L)， 则函数值为给定线性表L中第i个数据元素，否则为空元素NULL。第第2 2章章 线性数据结构线性数据结构 (4) PRIOR(L，elm)。求前求前趋函数趋函数，若elm的位序大于1，则函数值为elm的前趋，否则为空元素。 (5) NEXT
5、(L，elm)。求后求后继函数继函数，若elm的位序小于LENGTH(L)，则函数值为elm的后继，否则为空元素。 (6) LOCATE(L，x)。定定位位函函数数，返回元素x在线性表L中的位置。若L中有多个x，则只返回第一个x的位置，若在L中不存在x，则返回0。 (7) INSERT(L，i，x)。插插入入操操作作，在线性表L中的第i个位置上插入元素x，运算结果使得线性表的长度增加1。第第2 2章章 线性数据结构线性数据结构 (8) DELETE(L，i)。删除删除操作操作，若1iLENGTH(L)，删除给定线性表L中的第i个数据元素，使得线性表的长度减1。 (9) EMPTY(L)。判判空
6、空表表函函数数，若L为空表，则返回布尔值“true”，否则返回布尔值“false”。 对线性表还有一些更为复复杂杂的的操操作作，如将两个线性表合合并并成一个线性表；把一个线性表拆拆分分成两个或两个以上的线性表；重新复复制制一个线性表；对线性表中的元素按值的大小重新排排序序等。这些运算都可以通过上述基本运算来实现。第第2 2章章 线性数据结构线性数据结构 2.2.2 线性表的线性表的顺序顺序存储结构存储结构 在计算机内可以用不同的方式来表示线性表，其中最简单和最常用的方式是用一组地址连续的存储单元依次存储线性表中的元素。第第2 2章章 线性数据结构线性数据结构 线线性性表表的的顺顺序序存存储储结
7、结构构就是将线性表的元素按其逻辑次序依次存放在一组地址连续的存储单元里。 (1) 设有线性表(a1，a2，.，an)，若1个数据元素只占1个存储单元，则这种分配方式如图2-2所示。 若用Loc表示某元素的地址，则线性表中第i个数据元素的存储地址为： Loc(ai)= Loc(a1)+(i-1) 其中，Loc(a1)是线性表第一个数据元素的存储地址，通常称做线性表的起始地址起始地址或者基地址基地址。 第第2 2章章 线性数据结构线性数据结构 图2-2 线性表顺序存储结构示意图(设每个数据元素占有1个存储单元) 第第2 2章章 线性数据结构线性数据结构 (2) 若1个数据元素占d个存储单元，则有
8、Loc(ai)= Loc(a1)+(i-1)*d Loc(ai+1)= Loc(ai)+ d 可见，线性表中每个元素的存储地址是该元素在表中序号的线性函数。只要确定了线性表的起始地址，线性表中任一数据元素都可以随机存取，所以线线性性表表的的顺顺序序存存储储结结构构是一种随随随随机机机机存存存存取取取取的存储结构。第第2 2章章 线性数据结构线性数据结构 顺顺序序存存储储结结构构是以元素在计算机内“物理位置相邻”来表示线性表中数据元素之间相邻的逻辑关系。即顺序存储结构线性表的逻辑关系的存储是隐含的隐含的。 线性表的顺序存储结构通常称为向向量量(Vector)。可用字母V来表示，用Vi表示向量V的
9、第i个分量，设向量下界为1，上界为线性表的长度n（i=1n），则可以用此向量来表示长度为n的线性表。向量的第i个分量Vi是线性表的第i i个数据元素a ai i在计算机内存中的映像。 在在C C语语言言中中，向向量量即一维数组，所以可用一一维维数数组组来描述顺序存储结构。第第2 2章章 线性数据结构线性数据结构 #define maxlen 100 typedef int datatype;struct sqlisttp int elemmaxlen; datatype elemmaxlen; int last; ; 其中， maxlenmaxlen是线性表的最大长度，它可以根据实际需要而修改
10、。这里假设线性表的数据元素是假设线性表的数据元素是整数整数，当然当然也可以根据需要取也可以根据需要取其它类型其它类型, 甚至还可以是一种甚至还可以是一种结构结构(即每个数据元素有多个数据项)。第第2 2章章 线性数据结构线性数据结构 数据域elemelem描述了线性表中数据元素占用的数组空间，线性表的各个元素a1，a2，an依次存放在一维数组elem的各个分量elem1，elem2，elemn中。 数据域lastlast指示最后一个数据元素在数组中的相对位置。 在这种存储结构中，线性表的某些操作很容易实现。如线性表的长度即为last域的值等。 下面着重讨论线性表的插入插入和删除删除两种操作。第
11、第2 2章章 线性数据结构线性数据结构 算法算法2-1 线性表的插入算法插入算法。 已知线性表的当前状态是(a1，a2，ai-1，ai，an)，要在第i个位置插入一个元素x，线性表变为(a1，a2，ai-1，x，ai，an)。 其实施步骤实施步骤为： (1) 将第n至第i个元素后移后移一个存储位置； (2) 将x插入插入到第i个位置； (3) 线性表的长度加加1 1。第第2 2章章 线性数据结构线性数据结构 .a2a1an.ai+1ai01i-1in-1在在线线性性表表的的第第i i个个元元素素之之前前插插入入一一个个新新的的元元素素，先先移移动动，后插入。后插入。ai-1.a2a1alast
12、 ai+1ai x ai-1. a2 a1 ai ai+1 alast alast ai+1 ai x第第2 2章章 线性数据结构线性数据结构 #define maxlen 100struct sqlisttp /*定义了sqlisttp型的结构int elemmaxlen; /* maxlen=n, elem=a */int last; /* last=length */;sqlisttp v; /*定义了sqlisttp型的结构对象vvoid insert(sqlisttp v, int i, int x) int k; if (iv.last+1) printf( 插入位置不合适！n )
13、;第第2 2章章 线性数据结构线性数据结构 else if (v.last=maxlen)printf( 线性表已满！n );else for( k = v.last-1; k = i-1; k- )v.elemk+1 = v.elemk; v.elemi-1 = x; v.last+;第第2 2章章 线性数据结构线性数据结构 算法算法2-2 线性表的删除删除算法。 已知线性表的当前状态是(a1，a2，ai-1，ai，ai+1，an)，若要删除第i个元素ai，则线性表成为(a1，a2，ai-1，ai+1，an)。 具体实施步骤实施步骤为： (1) 若i值合法，则将第i+1至第n个位置上的元素依
14、次向前移前移动一个存储单位； (2) 将线性表的长度减减1。第第2 2章章 线性数据结构线性数据结构 .a2a1an.ai+1ai01i-1in-1删除线性表的第删除线性表的第i i个元素，后面所有元素前移。个元素，后面所有元素前移。ai-1.a2a1alastai+1ai ai-1. a2 a1 ai ai+1 alast删除删除结点结点a ai i ai+1 alast第第2 2章章 线性数据结构线性数据结构 #define maxlen 100struct sqlisttpint elemmaxlen;int last;sqlisttp v;void delete(sqlisttp v,
15、 int i) int k; if (iv.last) /*存取v的结构成员last printf( 删除位置不合适！n );第第2 2章章 线性数据结构线性数据结构 else for( k = i; k next; /*通过指针访问结构的成员时必须使用操作符- while ( p!=NULL) & (counter next; counter+;第第2 2章章 线性数据结构线性数据结构 if ( p!= NULL) & (counter = i ) /* 找到,1=in或inext = p-next；p-next = s。 插入结点s后单链表的逻辑状态如图2-7所示。第第2 2章章 线性数据
16、结构线性数据结构 图2-7 在单链表中插入结点S 第第2 2章章 线性数据结构线性数据结构 算法算法2-4void insert(NODE *head, int i, int x)NODE *p, *s;int j=0;p = head;while ( p!=NULL) & (j next; j+;第第2 2章章 线性数据结构线性数据结构 if (p = NULL) | (j i-1)printf( i值不合法 n); /* 找不到,in或i data = x; /* */ s - next = p - next; /* */ p - next = s; /* */ 如果事先告之p指针所指的位
17、置，则这种在p指针后后插插入一个元素算法法的时间复杂度T(n)=O(1)，否则平均时间复杂度T(n)=O(n)。第第2 2章章 线性数据结构线性数据结构 3) 单链表的删除单链表的删除 删除操作和插入操作一样， (1) 首首先先要搜索单链表以找到指定删除结点的前趋结点(假设为p)； (2) 然然后后改变链接，即只要将待删除结点的指针域内容赋予p结点的指针域即可。 设有线性表(a1，a2，.，ai-1，ai，ai+1，.，an)，用带头结点的单链表存储，删除前的逻辑状态如图2-8所示。 删除元素ai所在的结点之后，单链表的逻辑状态如图2-9所示。第第2 2章章 线性数据结构线性数据结构 图2-8
18、 带头结点的单链表图2-9 在单链表中删除一个结点第第2 2章章 线性数据结构线性数据结构 算法算法2-5void delete(NODE *head, int i)NODE *p, *s;int j=0;p = head;while ( p-next != NULL) & (j next; j+; 第第2 2章章 线性数据结构线性数据结构 if (p-next = NULL) | (j i-1)printf(“i值不合法 n”); /* 找不到,in或i next; p - next = s - next; free(s); 如果事先告之p指针所指的位置，则这种在p指针后后删删除一个元素算法
19、法的时间复杂度T(n)=O(1)，否则平均时间复杂度T(n)=O(n)。第第2 2章章 线性数据结构线性数据结构 4) 动态建立单链表的算法动态建立单链表的算法 要对单链表进行操作，首先要掌握怎样建建立立单单链链表表。链表是一种动态存储结构，所需的存储空间只有在程序执行malloc之后，才可能申请到一个可用结点空间；free(p)的作用是系统回收一个结点，回收后的空间可以备作再次生成结点时用。 整个可用存储空间可为多个链表共同享用，每个链表占用的空间不需预先分配划定，而是由系统应需求即时生成。因此，建建立立线线性性表表的的链链式式存存储储结结构构的的过过程程就是一个动态生成链表的过程。即从“空
20、表”的初始状态起，依次建立各元素结点，并逐个插入链表。第第2 2章章 线性数据结构线性数据结构 动态建立线性表的链式存储结构有两两种种基本方法，分别适用于不同的场合。可根据所建链表结点的顺序要求选择采用一种方法。 单链表建立方法一：单链表建立方法一：反向反向建立链表（头插法）建立链表（头插法）。 思思想想：若线性表的元素已顺序存放在一维数组AN中，建表方法是从线性表的最后一个元素开始，从从后后向前向前依次插入到当前链表的第一个结点之前。第第2 2章章 线性数据结构线性数据结构 算法算法2-6#define N m /* m为链表中数据元素的个数,如m=10 */int AN;NODE * cr
21、eatlink1( )NODE *head, *s;int i;head = (NODE *)malloc(sizeof(NODE); /*生成头结点*/head - next = NULL; /* 置空表 */for(i=N-1; i=0; i-) /* 插入10个数据 */第第2 2章章 线性数据结构线性数据结构 s = (NODE *)malloc(sizeof(NODE); /*生成新结点*/ s - data = Ai; /*将输入数据放入新结点数据域*/ s - next = head - next; /*新结点与原首结点链接*/ head - next = s; /* 将新结点插
22、入到表头 */ return head; /* 返回单链表头指针 */算法法的时间复杂度为：T(n)=O(n)第第2 2章章 线性数据结构线性数据结构 单链表建立方法二：正向建立单链表（尾插法）。单链表建立方法二：正向建立单链表（尾插法）。 思思想想：依次读入线性表的元素，从从前前往往后后依次将元素插入到当前链表的最后一个结点之后。图B 新结点*s插入到单链表head的尾上第第2 2章章 线性数据结构线性数据结构 算法2-7NODE * creatlink2( )NODE *head, *p, *s;int num;head = (NODE *)malloc(sizeof(NODE); /*生
23、成头结点*/scanf(“%d”, &num); /* 读入第一个结点值*/p = head; /* 头指针=尾指针 */while (num!=0) /* 输入为0为输入结束符*/第第2 2章章 线性数据结构线性数据结构 s = (NODE *)malloc(sizeof(NODE);/*生成新结点*/ s - data = num; /* 新结点上填入输入值 */ p - next = s; /* 新结点*s插入到尾结点*p之后 */ p = s; /* 尾指针p指向新的表尾 */ scanf(“%d”, &num); /* 读入下一个结点值 */ p - next = NULL; /*
24、将尾结点的指针置空 */return head; /* 返回单链表头指针 */算法法的时间复杂度：T(n)=O(n)第第2 2章章 线性数据结构线性数据结构 3. 线性链表算法示例线性链表算法示例 例例2-5 求求不带头结点的头指针为head的单链表中的结点数目结点数目。 解： int length(NODE *head) NODE *p; int j; p = head; j = 0;第第2 2章章 线性数据结构线性数据结构 while ( p != NULL ) p = p - next; j+; return j;算法法的平均时间复杂度：T(n)=O(n)第第2 2章章 线性数据结构线性
25、数据结构 例例2-6 设计算法：将一个带头结点的单链表A分分解解为两个带头结点的单链表A和B，使得A表中含有原表中序号为奇奇数数的元素，B表中含有原表中序号为偶偶数数的元素，且保持其相对顺序。第第2 2章章 线性数据结构线性数据结构 解：void disA(NODE *A, NODE *B)NODE *r, *p, *q;B = (NODE *)malloc(sizeof(NODE); /*建立单链表B的头结点*/r = B;p = A-next;while (p!=NULL) & (p-next!=NULL)第第2 2章章 线性数据结构线性数据结构 q = p-next; p-next =
26、q-next; r-next = q; r = q; p = p-next;r-next = NULL;p-next = NULL;第第2 2章章 线性数据结构线性数据结构 例例2-7 已知两个不带头结点的单链表A、B分别表示两个集合，其元素递增有序。试设计算法求出A与B的交交集集C。要求C另外开辟存储空间，并同样以元素值递增的带头结点的单链表形式存储。第第2 2章章 线性数据结构线性数据结构 解：void intersectionset(NODE *A, NODE *B, NODE *C)NODE *r, *p, *q, *s;C = (NODE *)malloc(sizeof(NODE);
27、r = C;p = A;q = B;while (p!=NULL) & (q!=NULL) if (p-data data)第第2 2章章 线性数据结构线性数据结构 p = p-next;else if (p-data q-data)q = q-next;else if (p-data = q-data) s = (NODE *)malloc(sizeof(NODE); s-data = p-data;第第2 2章章 线性数据结构线性数据结构 r-next = s; r = s; p = p-next; q = q-next;r-next = NULL;第第2 2章章 线性数据结构线性数据结构
28、 2.2.4 循环链表和双向链表循环链表和双向链表 1. 循环链表循环链表 如果链表最后一个结点的指针域指向头结点，整个链表形成一个环，这样的链表称为循环链表循环链表。 这样，从表中任一结点出发均可找到表中其它结点，其逻辑状态图如图2-10。第第2 2章章 线性数据结构线性数据结构 图2-10 循环单链表第第2 2章章 线性数据结构线性数据结构 循环链表一般设设表表头头结结点点，这样链表将永不为空，这将使空表和非空表的逻辑状态及运算统一起来。 循环链表的操作和线性链表基本一致，差别仅在于算法中的循环条件不是p p或或p-nextp-next是是否否为为空空，而是它们是否等于头指针。 与单链表比
29、较，循环链表循环链表有以下特点特点： (1) 在循环单链表中，从表中任何一个结点出发都能访问到其它所有的结点；而单链表一般把头指针作为入口点，从某一结点出发，只能访问到其所有后继结点。 (2) 循环单链表的空表判定条件空表判定条件是： head-next=head。第第2 2章章 线性数据结构线性数据结构 2双向链表双向链表 前面讨论的链式存储结构中只只有有一一个个指指示示直直接接后后继继的的指指针针域域，所以从某结点出发只只能能顺顺指指针针往往后后查查找找其它结点。若要查找结点的直接前趋，则应从头指针出发(或在循环单链表中从p结点出发)一直往后找，直到结点q满足q-next=p，那么q是p的
30、前趋结点。为克服链表这种单向性的缺点，为有更大的灵活性来操作线性链表，可采用双向双向链表存储结构链表存储结构。第第2 2章章 线性数据结构线性数据结构 在每个结点上增增加加另另一一个个指指向向线线性性表表中中每每个个元元素素的的前前趋趋结结点点的的指指针针域域priorprior，就得到双双向向链链表表。其结点的结构如图2-11所示。 其中，prior是指向前趋结点的指针域；data是数据域；next是指向后继结点的指针域。 图2-11 双向链表结点结构第第2 2章章 线性数据结构线性数据结构 图2-12 带头结点的空双向链表 和循环单链表类似，也可将双向链表的头结点和尾结点链接起来组成双向循
31、环链表。 双向链表的几种不同状态如图2-12，图2-13，图2-14和图2-15所示。图2-13 带头结点的非空双向链表 第第2 2章章 线性数据结构线性数据结构 图2-14 空的双向循环链表 图2-15 非空双向循环链表第第2 2章章 线性数据结构线性数据结构 在非非空空双双向向循循环环链链表表中，设p是指向链表中任一结点的指针，则有： p-next-prior = p-prior-next = p 这个等式反映了这种链表的本质，在此链表上进行插入或删除操作是十分方便的。双向链表虽然多花了存储空间，但却换得了操作上的更大灵活性。 双双向向链链表表的的运运算算如LENGTH(Head)，GET
32、(Head, i)，LOCATE(Head, x)等操作，仅涉及一个方向的指针，操作类似单链表。但插入INSERT、删除DELETE时要同时修改两个方向的指针。第第2 2章章 线性数据结构线性数据结构 (1) 插入插入。在链表中第i个结点前插入元素x。 步步骤骤：首首先先搜索插入位置，找到第i个结点用指p指示，然然后后申请新结点并改变链接。插入结点时指针变化状况如图2-16所示。第第2 2章章 线性数据结构线性数据结构 图2-16 在双向链表中插入结点 插入时相关操作序列为： s-prior = p-prior; (p-prior)-next = s; s-next = p; p-prior
33、= s。第第2 2章章 线性数据结构线性数据结构 (2) 删除删除。在链表中删除第i个结点。 步步骤骤：首首先先找到删除位置P，然然后后改变链接，最最后后释放被删结点P。删除结点时指针变化状况如图2-17所示。 第第2 2章章 线性数据结构线性数据结构 图2-17 在双向链表中删除结点删除时相关操作序列为： (p-prior)-next = p-next; (p-next)-prior = p-prior; 第第2 2章章 线性数据结构线性数据结构 例例2-8 设计算法：判判断断带头结点的循环双向链表head按元素值是否对对称称(所谓对称，就是在线性表中a1=an，a2=an-1，.)。 in
34、t symmetry(DNODE *head) DNODE *p, *q; p = head-next; /* p指向首元素 */ q = head-prior; /* q指向尾元素 */ while (p-data = q-data) if (p = q) | (p-next = q) /* 0个或1个元素*/第第2 2章章 线性数据结构线性数据结构 return 1;else p = p-next; /* p向左扫描 */ q = q-prior; /* q向右扫描 */ return 0;第第2 2章章 线性数据结构线性数据结构 第第2 2章章 线性数据结构线性数据结构 第第2 2章章 线性数据结构线性数据结构 第第2 2章章 线性数据结构线性数据结构
