第2章 线性表课件

1、第第 2 2 章章 线线 性性 表表线性结构：线性结构：是是 n（0）个结点的有穷序列）个结点的有穷序列，表示为（表示为（a1，a2，an）；）；起始结点起始结点: 线性结构中的第一个结点，即线性结构中的第一个结点，即a1；终端结点终端结点: 线性结构中的最后一个结点线性结构中的最后一个结点,即即an；直接前趋：对线性结构中的任意一对相邻的直接前趋：对线性结构中的任意一对相邻的结点结点ai和和ai+1，称结点，称结点ai是结点是结点ai+1的直接前趋。的直接前趋。直接后继：对线性结构中的任意一对相邻的直接后继：对线性结构中的任意一对相邻的结点结点ai和和ai+1，称结点，称结点ai+1是结点是

2、结点ai的直接后继；的直接后继；2.1 线性表的基本概念线性表的基本概念2.1.1 线性结构线性结构空表：不含任何结点的线性结构，记空表：不含任何结点的线性结构，记为为（）或（）或 。线性结构的基本特征：若至少含有一线性结构的基本特征：若至少含有一个结点，则除起始结点没有直接前趋外，个结点，则除起始结点没有直接前趋外，其它结点有且仅有一个直接前趋；除终其它结点有且仅有一个直接前趋；除终端结点没有直接后继外，其它结点有且端结点没有直接后继外，其它结点有且仅有一个直接后继。仅有一个直接后继。 线性表的逻辑结构是线性结构。线性表的逻辑结构是线性结构。表长：线性表的长度，即表中所含结点的表长：线性表的

3、长度，即表中所含结点的个数；个数；线性表的基本运算有如下几种：线性表的基本运算有如下几种：（1）初始化）初始化 INITIATE（head）: 建立一个建立一个空线性表。空线性表。（2）求表长）求表长 LENGThead（head）: 计算线计算线性表性表 head的表长，即求表中的结点数。的表长，即求表中的结点数。（3）读表元）读表元 GET（head，i）: 取线性表取线性表head中第中第 i 个元素的值。个元素的值。2.1.2 线性表线性表（4）定位）定位 LOCATE（head，X）: 找出线找出线性表性表head中与值中与值X相符合的第一个元素的地相符合的第一个元素的地址。址。（5

4、）插入）插入 INSERT（head，X，i）: 在线性在线性表表head中第中第 i 个元素处插入值为个元素处插入值为X的新元素。的新元素。（6）删除）删除 DELETE（head，i）: 删除线性删除线性表表head中第中第 i 个元素个元素 。2.2 2.2 线性表的顺序实现线性表的顺序实现2.2.1 2.2.1 顺序表顺序表顺序表是线性表的顺序存储结构顺序表是线性表的顺序存储结构。顺序存储的线性表中，每个元素都相邻排顺序存储的线性表中，每个元素都相邻排列，因此它们的逻辑顺序与物理顺序是一致列，因此它们的逻辑顺序与物理顺序是一致的，也可以说顺序表元素间的逻辑关系是由的，也可以说顺序表元素

5、间的逻辑关系是由它们的位置关系体现出来的。它们的位置关系体现出来的。 假定顺序表中的假定顺序表中的数据元素的类型数据元素的类型为为datatype, 则则顺序表的类型顺序表的类型可定义为：可定义为： const int maxsize = 顺序表的容量顺序表的容量;（或：（或： #define MAXSIZE 顺序表的容量顺序表的容量 ） typedef struct datatype datamaxsize; /* 顺序表元素存放在数组顺序表元素存放在数组data中中 */ int last; /* 顺序表的当前长度顺序表的当前长度*/ sqlist; /* 顺序表的类型名为顺序表的类型名为

6、sqlist */ sqlist L; /* 定义一个顺序表定义一个顺序表L */ 例如，若顺序表的数据元素的类型为例如，若顺序表的数据元素的类型为float,顺序表容量为顺序表容量为100，则该顺序表的类型定义为：，则该顺序表的类型定义为：#define MAXSIZE 100 typedef struct float dataMAXSIZE; int last; sqlist;sqlist L；表空时，表空时，L.last = 0 ；表长为；表长为 L.last 。 数据域数据域 dataMAXSIZE 是一个一维数组，其中是一个一维数组，其中 MAXSIZE 是根据问题定义的足够大的整数

7、，顺序表是根据问题定义的足够大的整数，顺序表中的数据从中的数据从 data0 开始顺序存放。但当前顺序表的开始顺序存放。但当前顺序表的实际元素可能未达到实际元素可能未达到MAXSIZE个，因此还应该用一个，因此还应该用一个变量个变量last来记录当前顺序表中最后一个元素在数组来记录当前顺序表中最后一个元素在数组中的位置（下标）。中的位置（下标）。 a1a2ai-1aiai+1an01i-2i-1i last-1 MAXSIZE-1data数组数组图图2-1 顺序表顺序表 示意图示意图空闲空闲2.2.2 2.2.2 基本操作在顺序表上的实现基本操作在顺序表上的实现在顺序表中，很容易实现线性表的在

8、顺序表中，很容易实现线性表的一些操作。注意：一些操作。注意：C C语言中的数组下标语言中的数组下标从从“0”0”开始，因此，顺序表中第开始，因此，顺序表中第 i i 个个元素是元素是 L.datai-1L.datai-1。1.1.插入插入 线性表的插入运算是指在表的第线性表的插入运算是指在表的第i i个个位置上，插入一个值为位置上，插入一个值为 x x 的新结点。的新结点。 使长度为使长度为 n n 的线性表：的线性表：(a(a1 1，a a2 2， ，a ai-1i-1，a ai i，a an n) )变成长度为变成长度为 n+1 n+1 的线性表：的线性表：(a(a1 1，a a2 2，

9、，a ai-1i-1，x x，a ai i，a an n) )a1a2aiai+1an01i-1数组下标数组下标n-1ina1a2aiai+1an01i-1数组下标数组下标n-1inan-1x图图2-3 顺序表的插入顺序表的插入L.lastL.last插入操作算法插入操作算法void insert_sqlist (sqlist L,datatype X, int i ) int j; if（L.last=maxsize）error(“表满表满”); if（i L.last+1） error（“非法位置）非法位置）; /* 插入在表外，出错插入在表外，出错 */ for（j= L.last; j

10、=i; j-）L.dataj= L.dataj-1; /* 依次后移依次后移*/ L.datai -1=X; /* 插入新元素插入新元素X */ L.last= L.last+1; /* 表长增一表长增一 */ 2.2.删除删除 线性表的删除运算是指将表的第线性表的删除运算是指将表的第i(1in) i(1in) 个结点删除，使长度为个结点删除，使长度为 n n 的的线性表：线性表： (a(a1 1，a ai-1i-1，a ai i，a ai+1 i+1 ，a an n) )变成长度为变成长度为 n-1 n-1 的线性表的线性表: : (a (a1 1，a ai-1i-1，a ai+1i+1，a

11、 an n) )a1a2aiai+1an-101i-1数组下标数组下标n-2in-1a1a2ai+201i-1数组下标数组下标n-2ian图图2-4 顺序表的删除顺序表的删除ai+1ani-2ai-1i-2ai-1删除操作算法删除操作算法void delete_sqlist ( sqlist L ，int i ) int j; if ( iL.last+1 ) printf( 非法位置非法位置 ); for( j=i+1 ; j=L.last; j+ ) L.data j-2 = L.data j-1 ; L.last = L.last -1 ;3.3.定位定位( (按值查找按值查找) )顺序

12、表的定位运算顺序表的定位运算( (按值查找按值查找) )是指在是指在表中查找与给定值表中查找与给定值 X X 相等的结点。相等的结点。a1a2aiai+1an-101i-1数组下标数组下标n-2in-1顺序表的顺序表的按值查找按值查找ani-2ai-1给定值为给定值为 x定位定位(按值查找按值查找)算法算法 int locate_sqlist ( sqlist L, datatype x ) int i=1 ; while( i= L.last & L.data i-1 !=x ) i+ ; if ( i datap-next图图2-6 申请一个结点申请一个结点2.3.2 2.3.2

13、单链表的简单操作单链表的简单操作带带“头结点头结点”的单链表的单链表在单链表中，第一个结点的处理与其在单链表中，第一个结点的处理与其它结点是不同的。原因是第一个结点的它结点是不同的。原因是第一个结点的地址是存放在头指针变量中，而其余结地址是存放在头指针变量中，而其余结点的地址是存放在其前趋结点的指针域点的地址是存放在其前趋结点的指针域中。中。“第一个结点第一个结点” ” 在单链表的很多操在单链表的很多操作（如插入、删除等）中都会遇到问题。作（如插入、删除等）中都会遇到问题。如插入结点时，插在第一个位置和其他如插入结点时，插在第一个位置和其他位置是不同的；删除结点时，删除第一位置是不同的；删除结

14、点时，删除第一个结点和其他结点也是不同的。个结点和其他结点也是不同的。为了方便操作，在单链表的为了方便操作，在单链表的第一个结点第一个结点前增设前增设一个类型相同的结点，称为一个类型相同的结点，称为“头结头结点点”，其它结点称为表结点其它结点称为表结点。表结点中的第一个结点称为表结点中的第一个结点称为首结点首结点。表结点中的最后一个结点称为表结点中的最后一个结点称为尾结点尾结点。头结点的数据域无定义头结点的数据域无定义，指针指针域中域中存放存放第一个结点（第一个结点（“首结点首结点”）的地址；当的地址；当单单链表为链表为空表时，该指针空表时，该指针域为域为NULLNULL。图图2-7 2-7

15、带带“头结点头结点”的单链表的单链表 head a1a2 an 空表空表头结点头结点首结点首结点尾结点尾结点表结点表结点head 带带“头结点头结点”的单链表有两个优点：的单链表有两个优点： a a、由于第一个结点的地址被存放在头、由于第一个结点的地址被存放在头结点的指针域中，所以在链表的第一个结点的指针域中，所以在链表的第一个结点上的操作就和在表的其它结点上的结点上的操作就和在表的其它结点上的操作一致，无需进行特殊处理；操作一致，无需进行特殊处理； b b、无论链表是否为空，其头指针总是、无论链表是否为空，其头指针总是指向头结点，因此空表和非空表的处理指向头结点，因此空表和非空表的处理也就统

16、一了。也就统一了。程序中与指针程序中与指针p有关的代码含义：有关的代码含义：(1) p- ：p 所指向的结点。所指向的结点。 (2) p-data : p 所指向结点的数据域。所指向结点的数据域。(3) p-next : p 所指向结点的指针域。所指向结点的指针域。 p 所指结点的下一个结点所指结点的下一个结点。(4) p = p-next : p 移动，指向下一个结移动，指向下一个结点。点。1. 初始化（建立空表）初始化（建立空表）算法如下：算法如下：lklist initiate_lklist( ) lklist t;t = malloc (size ); t-next = NULL ;

17、return t;t 2. 求单链表的表长求单链表的表长(1)求带头结点的单链表的表长求带头结点的单链表的表长 int Length_lklist ( lklist head ) lklist p = head; int j = 0; while ( p-next != NULL) p = p-next; j+ ; return j ; headp94516 程序段的运行示意图：程序段的运行示意图：j = 0;while ( p-next != NULL) p = p-next; j+; j0 1 2 3 4 5 ppppp94516 headp3. 3. 按序号查找按序号查找在链表中，即使知

18、道被访问结点的序在链表中，即使知道被访问结点的序号号i i，也不能象顺序表中那样直接按序号，也不能象顺序表中那样直接按序号i i访问结点，而只能从链表的头指针出发，访问结点，而只能从链表的头指针出发，沿着指针域沿着指针域 next next 逐个结点往下搜索，逐个结点往下搜索，直到搜索到第直到搜索到第i i个结点为止。因此，个结点为止。因此，链表链表不是随机存取结构不是随机存取结构。按序号查找算法按序号查找算法 如下：如下：pointer find_lklist(lklist head, int i) ; p = head ;j = 0 ; while ( p-next != NULL &am

19、p; jnext ; j+; if ( j= i ) return p; else return NULL; i3j0while ( p-next != NULL & jnext ; j+; ppppp94516 headp 2.3.3 基本运算在单链表上的实现基本运算在单链表上的实现 1.1.定位（按值查找）定位（按值查找） 按值查找是在链表中，查找是否有结按值查找是在链表中，查找是否有结点值等于给定值点值等于给定值 X X ，若有的话，则返回，若有的话，则返回首次找到的其值为首次找到的其值为 X X 的结点的地址；否的结点的地址；否则返回则返回 NULLNULL。查找过程从首结点出

20、发，。查找过程从首结点出发，顺着链表逐个将结点的值与给定值顺着链表逐个将结点的值与给定值 X X 作作比较。比较。定位（按值查找）算法定位（按值查找）算法 int Locate_lklist ( lklist head, datatype x ) p = head ; j=0; while ( p-next != NULL & p-data != x) p = p-next ; j+; if (p-data = x) return j; else return 0; 以以( 4,9,1,5,6 )为例，查找为例，查找 x=5 pppp94516 headp2.2.删除删除删除运算是将表

21、的第删除运算是将表的第 i 个结点删去。因个结点删去。因为在单链表中结点为在单链表中结点 ai 的存储地址是在其的存储地址是在其前趋结点前趋结点 ai-1 的指针域的指针域 next 中，所以必须中，所以必须首先找到首先找到 ai-1 的存储位置的存储位置 p ；然后令；然后令 q = pnext 指向结点指向结点 ai ，再令，再令 pnext 指向指向 ai 的后继结点的后继结点 ai+1 ，最后把，最后把 ai 从链上摘下，从链上摘下，释放结点释放结点 ai的存储空间。的存储空间。pa i-1ai+1 heada iqp = Get_lklist ( head , i-1 ) ;q =

22、p-next ;p-next = q-next ;free(s) ;删除算法如下：删除算法如下：void delete_lklist( lklist head, int i ) p = find_lklist (head , i-1 ) ;if ( p = NULL & p-next = NULL) q = p-next ; p-next = q-next ; free(q) ; else error(不存在第不存在第i 个结点个结点）3.插入插入插入运算插入运算:在单链表在单链表 L 的第的第 i个位置上插个位置上插入值为入值为 x 的新元素。的新元素。pa i-1sa i head

23、x a 1插入算法插入算法 如下：如下：void insert_lklist (lklist head , datatype x , int i ) p = find_lklist ( head, i-1 ); if ( p = NULL ) error(不存在第不存在第i 个位置个位置） else s = malloc (size) ; s-data=x; s-next=p-next; p-next=s; 2.5 2.5 其它链表其它链表 2.5.1 2.5.1 循环链表循环链表循环链表：循环链表与单链表的区别循环链表：循环链表与单链表的区别仅仅在于其尾结点的链域值不是仅仅在于其尾结点的链域

24、值不是null，而，而是一个指向头结点的指针，使得链表的是一个指向头结点的指针，使得链表的头尾结点相接。头尾结点相接。循环链表的优点循环链表的优点: 从表中任一结点出发都能通从表中任一结点出发都能通过后移操作而扫描整个循环链表。但对单链表过后移操作而扫描整个循环链表。但对单链表来说来说, 只有从头结点开始才能扫描表中全部结点。只有从头结点开始才能扫描表中全部结点。在图在图2-13(a)中，为要找到尾结点，必须从头中，为要找到尾结点，必须从头指针出发扫描表中所有结点。改进的方法是不指针出发扫描表中所有结点。改进的方法是不设头指针而改设尾指针，设头指针而改设尾指针， 如图如图2-13(c)所示。这

25、所示。这样，无论是找头结点还是尾结点都很方便，它样，无论是找头结点还是尾结点都很方便，它们的存贮位置分别是们的存贮位置分别是rear-next-next和和rear。 由于在某些应用中链表的头结点和尾结点使用由于在某些应用中链表的头结点和尾结点使用频繁，在这种场合使用带尾指针的循环链表比频繁，在这种场合使用带尾指针的循环链表比较合适。较合适。 heada1an图图2-13（a）带头指针的）带头指针的循环链表循环链表reara1an图图2-13（b）带尾指针的）带尾指针的循环链表循环链表2.5.2 双链表双链表 在单链表中在单链表中,每个结点所含的指针指向每个结点所含的指针指向其后继结点，故从任

26、一结点找其后继很其后继结点，故从任一结点找其后继很方便。但要找前趋结点则比较困难，其方便。但要找前趋结点则比较困难，其时间消耗是时间消耗是O(n)。若在每个结点中增加。若在每个结点中增加一个指针域，所含指针指向前趋结点，一个指针域，所含指针指向前趋结点，则可克服上述困难。这样构成的链表中则可克服上述困难。这样构成的链表中有两有两 个方向不同的链，称为双链表。个方向不同的链，称为双链表。priordatanext双链表的结点形式为：双链表的结点形式为： 其中，指针其中，指针prior和和next分别指向数据域分别指向数据域datd所含数据所含数据data所含数据元素的直接前所含数据元素的直接前趋

27、和直接后继所在的结点。所有结点通趋和直接后继所在的结点。所有结点通过前趋指针和后继指针链接在一起，再过前趋指针和后继指针链接在一起，再加上起标识作用的头指针，就得到双向加上起标识作用的头指针，就得到双向循环链表，简称双链表。循环链表，简称双链表。 双链表一般也是由头指针唯一确双链表一般也是由头指针唯一确定的；增加头结点也能使双链表上定的；增加头结点也能使双链表上的某些运算变得方便；将头结点和的某些运算变得方便；将头结点和尾结点链接起来也能构成循环链表尾结点链接起来也能构成循环链表,称之为称之为双向循环链表双向循环链表。 a 1 a 2head图图2-14 2-14 带头结点的带头结点的双向循环

28、链表双向循环链表示意图示意图ana3双链表结点的类型定义为：双链表结点的类型定义为： typedef struct dnode datatype data; struct dnode *prior，*next; *dlklist; （1）双链表结点的摘除操作：设指针）双链表结点的摘除操作：设指针p指向某指向某结点，摘除结点，摘除*p。操作如下：。操作如下： p-prior-next = p-next； p-next-prior = p-prior； free(p)；p p图图 2-15 2-15 双链表上结点的摘除双链表上结点的摘除(2)(2)双链表结点的链入操作双链表结点的链入操作: 设设指

29、针指针p p指向某结指向某结点点,q,q指向待插入的新结点，将指向待插入的新结点，将 * *q q 插到插到* *p p的后面。的后面。pqX图图 2-16 2-16 双链表上结点的双链表上结点的链链入入双链表结点链入操作的代码如下：双链表结点链入操作的代码如下： q-prior = p; q-next = p-next; p-next-prior = q; p-next = q;pqX2.6 顺序实现与链接实现的比较顺序实现与链接实现的比较2.6.1 空间性能的比较空间性能的比较存储结点中数据域占用的存储量与整个存储存储结点中数据域占用的存储量与整个存储结点占用存储量之比称为结点占用存储量之

30、比称为存储密度存储密度。显然，。显然，顺顺序表的存储密度序表的存储密度(=1)高于高于链表的存储密度链表的存储密度(=0)。注意：空串和空格串是两个不同的串，前者注意：空串和空格串是两个不同的串，前者是长度为零的空串，后者是长度不为零的仅含是长度为零的空串，后者是长度不为零的仅含空格符的非空串。空格符的非空串。(2)两个串是相等的，当且仅当它们的长度相两个串是相等的，当且仅当它们的长度相等并且各个对应位置上的字符都相同。等并且各个对应位置上的字符都相同。一个串中任意个连续字符组成的子序列称为一个串中任意个连续字符组成的子序列称为该串的该串的子串子串，该串称为它的所有子串的，该串称为它的所有子串

31、的主串主串。例如，例如，D、A、AT和和DAT等等都是等等都是DATA的子串。的子串。 (3)空串是任意串的子串。任意串是其自身的空串是任意串的子串。任意串是其自身的子串。子串。 (4) 串变量和串常量。串变量和串常量。串常量在程序的说明部分加以命名，例如串常量在程序的说明部分加以命名，例如const s=data;或：或： #define s data定义定义s为了一个串常量，即在该程序中为了一个串常量，即在该程序中s将代表串将代表串data。这样，。这样， 在程序中每当需要用到串在程序中每当需要用到串data时，时，可以简单地用可以简单地用s代替，这就大大简化了程序的书写。代替，这就大大简

32、化了程序的书写。 语言规定，字符串常量按字符数组处理，它的值语言规定，字符串常量按字符数组处理，它的值在程序的执行过程中是不能改变的，而串变量与其他在程序的执行过程中是不能改变的，而串变量与其他变量不一样，不能由赋值语句对其进行整体赋值。变量不一样，不能由赋值语句对其进行整体赋值。2.7.2 串的基本运算串的基本运算赋值赋值ASSIGN(S,T)，加工型运算。其作用是将，加工型运算。其作用是将串变量或串常量串变量或串常量T的值的值(一个串一个串)传给串变量传给串变量S。判等判等EQUAL(S,T)，引用型运算。若，引用型运算。若S和和T的值的值相等则返回值相等则返回值(即运算结果即运算结果)为

33、为,否则返回值否则返回值.例如，例如，EQUAL( )返回值返回值true,EQUAL(A,B)返返回值回值false.求长求长LENGTH(S)，引用型运算。运算结果为串，引用型运算。运算结果为串S的长度。的长度。联接联接CONCAT(S,T)，引用型运算。运算结果为，引用型运算。运算结果为由由S和和T联接在一起形成的新串。联接在一起形成的新串。求子串求子串SUBSTR(S,i,j)，引用型运算。其结果是串，引用型运算。其结果是串S中从第中从第i个字符开始的、由连续个字符开始的、由连续j个字符组成的子串。个字符组成的子串。例如，例如，SUBSTR(ABBCA,2,2)=BB，SUBSTR(A

34、BBCA,3,0)=。插入插入INSERT(S1,i,S2)，加工型运算。其作用是将，加工型运算。其作用是将串串S2插到串插到串S1 的第的第i个字符之后而产生一个个字符之后而产生一个 新串。新串。INSERT(AAAB，2，CBC)=AACBCAB。删除删除DELETE(S,i,j)加工型运算。其作用是从中加工型运算。其作用是从中S中删去从第中删去从第i个字符开始的长度为个字符开始的长度为j的子串。的子串。例如，例如，DELETE(ACABA,3,3)=AC定位定位INDEX(S,T)，引用型运算。若在串，引用型运算。若在串S中存在中存在一个与一个与T相等的子串，则本运算的结果为相等的子串，则本运算的结果为S中第一个中第一个(即最左边的即最左边的)这样的子串中的第一个字符在