第二章 线性表,知识教学目标,线性表的逻辑结构 线性表的顺序存储结构及其基本操作 线性表的链式存储结构及其基本操作 循环单链表和双向链表 顺序表和链表的比较 线性表基本运算的时间复杂度,能力培养目标,单链表上的各种操作实现 单向循环链表的基本操作实现 顺序表上的插入、删除和查找运算 单链表上的插入、删除和查找运算 单向循环链表上查找等基本运算 双向链表的定义和运算特点,2.1 线性表及其逻辑结构,2.1.1 线性表的定义 线性表（Linear List）是一种线性数据结构，其特点是数据元素之间存在“一对一”的关系。在一个线性表中每个数据元素的类型都是相同的，即线性表是由同一数据类型的n（n=0）个数据元素的有限序列。,2.1.2 线性表的运算,1) 置空表 2) 求长度 3) 取表中第i个结点 4) 按值查找 5) 插入结点 6) 删除结点 7) 判空表,2.2 线性表的顺序存储,2.2.1 顺序表 用顺序存储方法存储的线性表称为线性表的顺序存储结构，简称为顺序表。它是将线性表中的结点按其逻辑次序依次存储在一组地址连续的存储单元中。 假设线性表L中初始结点a1的内存地址为LOC(a1)，而每个结点在计算机中占用c个存储单元，则第i个结点ai的地址LOC(ai)可通过以下公式计算： LOC(ai) = LOC(a1) + （i1）* c 1in,因此我们用结构体类型来定义顺序表。其定义如下： typedef int DataType； /DataType的类型可根据实际情况而定，这里假设为int define MaxSize 100 /MaxSize顺序表可能的最大长度 typedef struct DataType dataMaxSize; /数组data用于存放表结点 int length; /变量length表示表的长度 SeqList；,2.2.2 顺序表的基本操作,【算法2.1】 置空表InitList（L）。 顺序表的初始化操作，将顺序表的当前长度置为0。算法如下： void InitList (SeqList *L) L-length=0; ,【算法2.2】 求长度LengthList（L）。 求顺序表中结点的个数。算法如下： int LengthList (SeqList *L) return L-length; ,【算法2.3】 取结点GetNode（L，i）。 DataType GetNode (SeqList *L , int i) if (iL-length) return NULL; /i的值非法，返回空类型 else return L-datai-1; /返回第i个结点（下标是i-1）的值 ,【算法2.4】 判空表IsEmpty(L)。 int IsEmpty(SeqList *L) if (L-length = 0) return TRUE; else return FALSE; ,1. 查找操作,【算法2.5】 顺序表结点的定位算法。 int LocateNode (SeqList *L , DataType x) int i; for ( i=0; ilength; i+ ) if ( L-datai = x ) return i; /返回x所在的下标 else return -1; /返回-1作为查找失败的标志 该算法的时间复杂度为O(n)。,2. 插入操作,【算法2.6】 顺序表插入结点算法。 int InsertList (SeqList *L , int i , DataType x) int j; if ( L-length=MaxSize) /表满溢出 printf(“顺序表已满！”); return (-1); if (iL-length+1) /i为非法位置 printf(“位置出错！”); return (0); for (j=L-length ; j=i-1 ; j-) /结点依次后移 L-dataj+1=L-dataj; L-datai-1=x; L-length+; /表长增加1 return (1); ,3. 删除操作,【算法2.8】 顺序表删除结点算法。 int DeleteList (SeqList *L , int i ) /删除顺序表中第i个结点（下标为i-1） int j; if (iL-length) printf(“不存在第i个元素！”); return (0); /非法位置，终止操作 for ( j=i ; jlength-1；j+) L-dataj-1=L.dataj; /从第i+1个结点（下标为i）逐个向前移动 L-length-; return (1); ,顺序表的优点： 1）无需为表示表中元素之间的逻辑关系而增加额外的存储空间； 2）随机存取：可以快速地存取表中任一位置的元素。 顺序表的缺点： 1）插入和删除操作需要移动大量元素； 2）表的容量难以确定，表的容量难以扩充； 3）造成存储空间的碎片。,2.3 线性表的链式存储,2.3.1 单链表结构 在链表结构中，是用一组任意的存储单元来存放线性表的结点，这组存储单元既可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上。因此，链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址信息，这个信息称为指针（pointer）或链（link）。,在C语言中，存储每个数据元素的结点结构描述如下： struct node int data; struct node *next; ; typedef struct node NODE;,2.3.2 单链表的基本操作,需要为p申请一个结点，方法为： p = (NODE *)malloc(sizeof(NODE) ； 同样，当p所指向结点不再需要时，要释放该结点空间，方法为： free(p) ；,1. 建立单链表,【算法2.10】 建立有n个结点的线性单链表的算法。 NODE *create_link ( int n ) /建立带有头结点，且数据元素为1到n的单链表，首指针为head NODE *head,*p,*q; int i,m; p=(NODE *)malloc(sizeof(NODE); p-next=NULL; head=p ; /建立头结点 for(i=1;idata=m; q-next=NULL; p-next=q; p=q ; return(head); ,2. 单链表中结点的查找,【算法2.11】 单链表中按位置查找算法。 NODE *SearchList1 (NODE *L , int i ) NODE *p=L; int j=0; while ( p-next!=NULL ,【算法2.12】 单链表的按值查找算法。 NODE *SearchList2 (NODE *L, DataType x ) NODE *p=L-next; while ( p!=NULL ,3. 单链表中结点的插入,【算法2.13】 单链表的插入算法。 int InsertLink (NODE * head , DataType x , int i ) NODE *p , *s ; int j=0; p=head; while ( (p!=NULL) ,【算法2.14】 单链表结点的删除算法。 int DeleteLink (NODE * head , int i ) NODE *p , *q ; int j=0; p=head; while ( (p!=NULL) ,5. 单链表求长度操作 【算法2.15】 求以head 为头指针的单链表的长度。 int length(NODE *head) int n=0; NODE *p，*q; p=head; while(p-next!=NULL) /p结点的后续结点不为空 n+; p=p-next; return n; /返回单链表的长度，即其中结点的个数 ,2.4 单向循环链表,单向循环链表(Circular Linked List)是线性表另一种形式的链式存储结构。其特点是表中最后一个结点的指针域指向其首结点，整个链表形成一个环。由此，从表中任一个结点出发均可以找到表中其他结点。,2.5 双向循环链表,2.5.1 双向链表 为克服单链表的缺点，引入了双向链表，在双向链表中每个结点有两个指针域，一个指向其直接后继，另一个指向其直接前驱，用C语言描述其结构如下: struct node int data; struct node *llink,*rlink; ; typedef struct node DNODE; data为结点的数据域，rlink右方向指针域，指向结点的直接后续，llink为左方向指针域，指向结点的直接前驱。,2.5.2 双向循环链表 在双向链表中，使表首结点的左方向指针(llink)指向表尾结点，并使表尾结点的右方向指针(rlink)指向表首结点，这时就构成双向循环链表。图2.8为双向循环链表逻辑状态。,1. 插入 在p所指的结点之后插入q所指的结点的过程如下： q=(DNODE *)malloc(sizeof(DNODE); q-data=x; q-rlink=p-rlink; q-llink=p; p-rlink=q; (q-rlink)-llink=q; 2. 删除 删除p所指的结点的过程如下： (p-llink)-rlink=p-rlink; (p-rlink)-llink=p-llink;,2.6 本章小结,线性表是一种比较简单的数据结构，它是n个结点的有限序列。线性表常用的存储方式有两种：顺序存储结构和链式存储结构。 在线性表的顺序存储结构中，是利用结点的存储位置来反映结点的逻辑关系，结点的逻辑次序与存储空间中的物理次序一致，因而只要确定了线性表中起始结点的存储位置，即可方便地计算出任一结点的存储位置，所以可以实现结点的随机访问。 而在线性表的链式存储结构中，结点之间的逻辑次序与存储空间中的物理次序不一定相同，是通过给结点附加一指针域来表示结点之间的逻辑关系。 在循环链表中，所有的结点构成了一个环，所以从任一结点开始都可以扫描此线性表的每个结点。双向链表既有指向直接后继的指针，又有指向直接前趋的指针，从而便于查找结点的前趋。 线性表的运算主要有查找、插入和删除，应熟练掌握线性表在不同存储方式下各种运算的实现方法。,