本章主要介绍下列内容1、线性表及其逻辑结构;2、线性表的顺序

1、本章主要介绍下列内容：1、线性表及其逻辑结构；2、线性表的顺序存储结构；3、线性表的链式存储结构；4、线性表的应用举例课时分配：1、2占2学时，3占2学时, 4占2学时，上机2学时重点、难点：线性表的顺序存储结构、链式存储结构、循环链表 线性表及其逻辑结构 线性表的定义线性表是由n（n0）个类型相同的数据元素组成的有限序列。通常表示成下列形式：L=( a1, a2,.,ai-1,ai,ai+1,.,an)其中：L为线性表名称，习惯用大写书写；ai为组成该线性表的数据元素，习惯用小写书写；线性表中数据元素的个数被称为线性表的长度，当n=0时，线性表为空，又称为空线性表。例2-1 线性表形式La=

2、（34，89，765，12，90，-34，22） 数据元素类型为int。Ls=(“Hello”,“World”, “China”, “Welcome”) 数据元素类型为string。Lb=(book1,book2,.,book100) 数据元素类型为下列所示的结构类型：struct bookinfoint No; /图书编号char *name; /图书名称char *author; /作者名称.; 线性表的抽象数据类型描述ADT List数据对象：Dai| 1=i=0, ai属ElemType类型数据关系：R1=| ai,ai+1D,i=1,n-1基本运算：（略介绍）（1）初始化线性表L I

3、nitList(L) （2）销毁线性表L DestoryList(L) （3）清空线性表L ClearList(L) （4）求线性表L的长度 ListLength(L)（5）判断线性表L是否为空 IsEmpty(L) （6）获取线性表L中的某个数据元素内容 GetElem(L,i,e) （7）检索值为e的数据元素 LocateELem(L,e) （8）返回线性表L中e的直接前驱元素 PriorElem(L,e) （9）返回线性表L中e的直接后继元素 NextElem(L,e) （10）在线性表L中插入一个数据元素 ListInsert(L,i,e)（11）删除线性表L中第i个数据元素 List

4、Delete(L,i,e) 线性表的顺序存储结构 线性表的顺序存储结构线性表的顺序存储结构是指用一组连续的存储单元依次存储线性表中的每个数据元素，也称为顺序表。如下图所示： 其中，L为每个数据元素所占据的存储单元数目。相邻两个数据元素的存储位置计算公式：LOC(ai+1)=LOC(ai)+L线性表中任意一个数据元素的存储位置的计算公式为：LOC(ai+1)=LOC(a1)+(i-1)*L顺序存储结构的特点：（1）利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结 构（物理结构）一致；（2）在访问线性表时，可以利用上述给出的数学公式，快速地计算出任何一个数据

5、元素的存储地址。因此，我们可以粗略地认为，访问每个数据元素所花费的时间相等。这种存取元素的方法被称为随机存取法，使用这种存取方法的存储结构被称为随机存储结构。在C语言中，实现线性表的顺序存储结构的类型定义：#define MAXSIZE 100 /* MAXSIZE 为线性表可能的最大长度 */#define ERROR -1typedef struct /* 线性表定义 */int elementsMAXSIZE;int last; /* last为线性表的长度 */ SqList; 注：为帮助学生考研，上课讲解用指针形式。 典型操作的算法实现：（1）初始化线性表Lvoid InitList

6、(SqList *L) /*初始化操作，将线性表L置空*/L-last = 0;（2）销毁线性表Lvoid DestroyList(SqList *L) if (L-elem) free(L-elem); /释放线性表占据的所有存储空间（3）清空线性表Lvoid Clear(SqList *L) /* 清空线性表L */InitList( L );（4）求线性表L的长度int GetLength(SEQLIST L) return (L.length); （5）判断线性表L是否为空bool IsEmpty( SqList L) /*判断表是否为空。如果L是空表，返回true，否则返回false

7、*/if( L.last = 0 ) return true;else return false;（6）获取线性表L中的某个数据元素的内容int GetElem(SqList L,int i) /* 取表中第i元素。*/if(i=L.last) return ERROR;else return L.elementsi; /*C语言中数组的下标从0开始*/（7）在线性表L中检索值为e的数据元素int LocateElem(SqList L,int x) /*定位函数。返回L中第1个与x相等的数据元素的位置（从0算起）。*/ /*否则返回值为0。*/int k; k=0; while (kL.la

8、st & L.elementsk!=x) k+; if(kL.last) return k; else return ERROR;（8）在线性表L中第i个数据元素之前插入数据元素e int Insert(SqList *L,int x,int i) /*在线性表L中第i（0iL.last）个数据元素之前插入一个数据元素x*/int k; if(iL-last | L-last = MAXSIZE) return ERROR; else for( k=L-last; k=i; k- ) L-elementsk= L-elementsk-1; L-elementsi=x; L-last=L-las

9、t+1;return true;（9）将线性表L中第i个数据元素删除int Dlete(SqList *L,int i) /*删除线性表L中第i（0IL.last）个数据元素*/int k;if( i=L-last ) /* 下标越界 */ return ERROR;else /* 移动后面的元素 */ for(k=i;klast;k+) L-elementsk= L-elementsk+1; L-last-;return true;插入算法的分析：设Pi是在第i个元素之前插入一个元素的概率，假定在顺序表中任何位置插入元素的机会相等，即设Pi，则在长度为n的线性表中插入一个元素时所需移动元素的

10、平均次数为E（n）=删除算法的分析：设qi是删除第i个元素的概率，假定在顺序表中删除元素的机会相等，即设qi，则在长度为n的线性表中删除一个元素时所需移动元素的平均次数为E（n）=结论：在顺序表中插入或删除一个数据元素，平均大约移动表中一半元素。当线性表的长度较大，且插入和删除操作的频度较高时，则花费时间较多，不宜采用顺序存储结构。但是顺序表存储结构简单，便于顺序存储，存储空间的利用率高。顺序表应用举例：例21 清除顺序表中的重复数据元素。例如，顺序表（2，3，3，4，3，5，4）清除后变为（2，3，4，5）。注：清除重复元素是指删除重复元素，只保留序号最小的一个。解：具体的算法实现思路是：从

11、顺序表中依次取出每一个元素ai，并检查ai+1到an-1中是否有元素与ai值相等，有就删除重复元素。void ClearList(SqList *L) /* 清除顺序表中的重复数据元素 */int i = 0, j;while( i last ) j = i + 1;while(jlast) /* 找重复数据元素并删除 */if( L-elementsi = L-elementsj ) Dlete(L,j); /* 下一个元素自动向前移动过来 */else j+; /* 指针向下移动一个位置 */ i+; 2.3 线性表的链式存储结构 线性表的链式存储结构链表线性表顺序存储结构的特点： （1）

12、 简单、方便，要求表中数据元素依次存放在连续的存储单元中，利用数据元素的存储顺序表示相应的逻辑顺序，属于静态存储形式；（2） 在做插入或删除元素的操作时，会产生大量的数据元素移动；（3） 对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常又得不到充分的利用；（4） 线性表的容量难以扩充。线性表的链式存储结构 线性表的链式存储结构是指用一组任意的存储单元（可以连续，也可以不连续）存储线性表中的数据元素。为了反映数据元素之间的逻辑关系，对于每个数据元素不仅要表示它的具体内容，还要附加一个表示它的直接后继元素存储位置的信息。假设有一个线性表（a,b,c,d），可用下图所示的形式存

13、储：可以形象地描述为：abcdhead链式存储结构的特点：（1）线性表中的数据元素在存储单元中的存放顺序与逻辑顺序不一定一致；（2）在对线性表操作时，只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，这样就会造成寻找第一个结点和寻找最后一个结点所花费的时间不等，具有这种特点的存取方式被称为顺序存取方式。用C语言描述单链表的结点结构如下：typedef struct node /* 单链表结点结构 */DataType data; /*DataType可以是任何相应的数据类型如int,char等*/struct node *next; LinkList; 典型操作的算法实现（1）初

14、始化链表Lvoid InitList1( LinkList *head ) /* 初始化不带头结点的链表头指针 */*head = NULL;（2）销毁链表L void DestoryList(LINK_LIST *L)LINKLIST *p;while (L-head) /依次删除链表中的所有结点p=L-head; L-head=L-head-next;free(p);（3）清空链表L void ClearList(LINK_LIST *L)LINKLIST *p;while (L-head-next)p=L-head-next; /p指向链表中头结点后面的第一个结点L-head-next=

15、p-next; /删除p结点free(p); /释放p结点占据的存储空间（4）求链表L的长度int Length(LinkList *head)/* 在带头结点的单链表中求表的长度 */LinkList *p=head; int j=0;while (p-next!=NULL) j+;p=p-next; /* p右移一个结点 */return j;（5）判链表L空否。int IsEmpty(LINK_LIST L) if (L.head-next=NULL) return TRUE;else return FALSE;（6）通过e返回链表L中第i个数据元素的内容void GetElem(LIN

16、K_LIST L,int i,Elemtype *e) LINKLIST *p;int j;if (iListLength(L) exit ERROR; /检测i值的合理性for (p=L.head,j=0; j!=i;p=p-next,j+); /找到第i个结点*e=p-elem; /将第i个结点的内容赋给e指针所指向的存储单元中（7）在链表L中检索值为e的数据元素LinkList *LocateNode(LinkList *head, int x)/* 在带头结点的单链表中查找值为x的结点，找到返回结点指针，否则返回NULL */LinkList *p = head-next;while(

17、 p & p-data != x ) p=p-next;return p;（8）返回链表L中结点e的直接前驱结点LINKLIST *PriorElem(LINK_LIST L,LINKLIST* e)LINKLIST *p;if (L.head-next=e) return NULL; /检测第一个结点for (p=L.head;p-next&p-next!=e;p=p-next); if (p-next=e) return p;esle return NULL; （9）返回链表L中结点e的直接后继结点LINKLIST *NextElem(LINK_LIST L,LINKLIST* e)LIN

18、KLIST *p;for(p=L.head-next;p&p!=e;p=p-next);if (p) p=p-next; return p;（10）在链表L中第i个数据元素之前插入数据元素e void AddHead1(LinkList *head, int x )/* 向头指针为head的链表中插入一个结点，其值为x */LinkList *p;p=( LinkList *)malloc(sizeof(LinkList);p-data = x;p-next = *head;*head = p; /* 调整链表头指针head */（11）将链表L中第i个数据元素删除，并将其内容保存在e中。vo

19、id DeleteNode（LinkList *head, int i）/* 在带头结点的单链表中删除第i个结点 */LinkList *p,*q； p=GetNode(head,i-1); /*找到第i-1个结点 */if（(p!=NULL)&(p-next!=NULL)） q=p-next; /*对应图2.8 */p-next=q-next; /*对应图2.8 */ free(q); /*对应图2.8 */else printf(“结点未找到！n”); 循环链表若将单链表中最后一个结点的指针指向链表的第一个结点，那么整个链表就形成了一个环形结构，故称为单链形式的循环链表，并简称为单循环链表

20、。（a） 非空循环链表heada1a2anhead头结点(b) 空循环链表头结点循环链表的特点：从表中任一结点出发均可访问其他所有结点。实现循环链表的类型定义与单链表完全相同，它的所有操作也都与单链表类似。只是判断链表结束的条件有所不同。 双向链表可以在单链表的每个结点内再增加一个指向其直接前驱的链域，这样形成的链表中就有两条方向不同的链，故称为双向链表（Double linked list）。双向链表的结点结构C语言描述：typedef struct dnode /* 双向链表结点结构 */DataType data; /*DataType可以是任何相应的数据类型如int,char等*/st

21、ruct dnode *prior,*next; DLinkList;双链表的*p结点之前插入值为x的结点插入的过程：pq对应算法如下：void InsertDNode(DLinkList *p, int x)/* 在双链表的*p结点之前插入值为x的结点 */DLinkList *q; q=( DLinkList *)malloc(sizeof(DLinkList);q-data=x;q-prior=p-prior; /*对应图2.11 */q-next=p; /*对应图2.11 */p-prior-next=q; /*对应图2.11 */p-prior=q; /*对应图2.11 */在双链表

22、中删除p指针指向的结点的过程：p对应算法如下：void DeleteDNode(DLinkList *p)/* 在双链表中删除p指针指向的结点 */p-prior-next=p-next; /*对应图2.12 */p-next-prior=p-prior; /*对应图2.12 */free(p); 线性表的应用举例例22 有一个不带头结点的单链表L（至少有1个结点），第一个结点指针为head，编写算法将L逆置，即最后一个结点变成第一个结点，倒数第二个结点变成第二个结点，如此等等。解：逆置的方法是：从头到尾扫描单链表L，将第一个结点的next域设置为NULL，将第二个结点的next域指向第一个结

23、点，将第三个结点的next域指向第二个结点，如此进行直到最后一个结点，用head指向它。其算法如下：void Invert1( LinkList *head ) /* 将不带头指针的单链表倒置 */LinkList *p = *head, *r;LinkList *q = NULL;/* q始终指向当前插入点 */while( p ) /* 还有剩余元素时 */r = p-next; /* r缓存下一个待插入元素指针 */p-next = q; /* 插入当前的待插元素到新表中 */q = p; p = r; /* 调整 */*head = q;/* 更新头指针 */例23 有两个带头结点的单

24、循环链表L1和L2，编写算法将链表L2链接到链表L1之后成为一个单循环链表。解决本题的具体方法是：如果在用头指针指向的单循环链表上做这个操作，都需要先找到两链表的尾指针，要找尾指针就必须遍历整个链表，找到后将第二个链表的尾指针与第一个链表的头结点链接起来，使之成为循环的链表。若在用尾指针指向的单循环链表上做这个操作，则只需修改指针，操作过程如下图所示。其算法如下：a1a2anrear1a1a2anrear2pqLinkList *InsertOrder(LinkList *rear1, Node *rear2) /* 在有序单链表L中插入值为x的结点，插入后仍然有序 */*/*/*/*/fre

25、e(q);return( rear2 );2.5 线性表的应用约瑟夫（Joseph）问题：编号为1，2，n的n个人按顺时针方向围坐在一张圆桌旁，每个人手中持有一个密码（正整数）。首先输入一个正整数作为报数上限值m，然后，从第一个人开始按顺时针方向自1开始顺序报数，报到m的人离开桌旁，并将他手中的密码作为新的m值，从顺时针方向的下一个就坐在桌旁的人人开始重新从1报数，如此下去，直至所有人全部离开桌旁为止。 解： 假设有7个人，编号从1到7，他们手中的密码分别是3，1，7，2，4，8，4，最初的m=2，通过报数，这7个人离开桌旁的顺序应该是：2，3，5，4，7，6，1。数据结构的分析：这个问题的主

26、角是n个人，每个人需要描述的信息有：编号、密码和是否在桌旁的状态。假设有7个人，他们的信息可以表示成下面的形式。算法描述：让n个人围坐在一张圆桌旁；for (i=1;i=n;i+)从1开始报数，报到m停止；报到m的人离开桌子；代码实现一（顺序存储方式）：#define LIST_MAX_LENGTH 7#define n LIST_MAX_LENGTHtypedef int Elemtype; /将Elemtype定义为int类型void Joseph(int code,int n) /通过一维数组code带入n个人手中的密码，n是开始就坐在桌旁的人数 SqList people; int temp,m;