第2章线性表_2

1、数据结构数据结构2015-2016-2渭南师范学院渭南师范学院 2015级级第第2章章 线性表线性表n2.3 线性表的链式存储线性表的链式存储n小结小结2.3 线性表的链式存储线性表的链式存储n线性表中的元素呈线性关系（逻辑结构）：在顺序存储结构中，以内存单元的连续表示元素之间的顺序关系。（物理结构1：顺序映象）还可以以另外一种方式表示元素之间的先后次序关系，即链的形式。 （物理结构2 ：非顺序映象）采用链式存储的线性表称。从链接方式的角度看，链表分为单链表、循环链表和双链表。从实现角度看，链表分为静态链表和动态链表。2.3 线性表的链式存储线性表的链式存储n2.3.1 单链表单链表n单链表的

2、结点单链表的结点(数据元素数据元素)包括两个域：包括两个域：数据域数据域用来存储结点的值；用来存储结点的值；指针域指针域用来存储数据元素的直接后继的地址（或位置）。用来存储数据元素的直接后继的地址（或位置）。 图图2.5 单链表的结点结构单链表的结点结构 datanext数据域指针域2.3 线性表的链式存储线性表的链式存储n2.3.1 单链表单链表n单链表单链表：通过通过每个结点的每个结点的一个指针一个指针域域将线性表的将线性表的n个结点按其个结点按其逻辑顺序链接在一起逻辑顺序链接在一起。n头指针头指针：指向第一个结点的指针。：指向第一个结点的指针。线性表中最后一个结点的指针域为线性表中最后一

3、个结点的指针域为“空空”（NULL）。）。对于整个链表的存取必须从头指针开始。对于整个链表的存取必须从头指针开始。2.3 线性表的链式存储线性表的链式存储n2.3.1 单链表单链表存储地址存储地址数据域数据域指针域指针域1 1D D43437 7B B13131313C C1 11919H HNULLNULL2525F F37373131A A7 73737G G19194343E E2525头指针头指针H H3131图图2.6 单链表示意图单链表示意图2.3 线性表的链式存储线性表的链式存储n2.3.1 单链表单链表图图2.7 单链表的逻辑状态单链表的逻辑状态 ABCDEFGHH2.3 线性

4、表的链式存储线性表的链式存储n2.3.1 单链表单链表为了操作统一方便，可在单链表的第一个结点之前附设一个头结点，此时头指针指向头结点。当线性表为空时，只有一个头结点，且头结点的指针域为空。图图2.8 带头结点单链表图示带头结点单链表图示 (a) 带头结点的空单链表HHa1a2an(b) 带头结点的单链表2.3 线性表的链式存储线性表的链式存储n2.3.1 单链表单链表单链表的存储结构定义如下：单链表的存储结构定义如下：typedef struct Node / * 结点类型定义结点类型定义 * / ElemType data； struct Node *next； Node, *LinkLi

5、st； /* LinkList为结构体指针类型为结构体指针类型 */单链表的结点类型名是单链表的结点类型名是Node ，单链表类型名是，单链表类型名是LinkList若有：若有：LinkList L; 则则L表示指向单链表的头指针，即表示单链表。表示指向单链表的头指针，即表示单链表。2.3 线性表的链式存储线性表的链式存储n2.3.2 单链表上的基本运算单链表上的基本运算1. 初始化单链表【算法2.5 初始化单链表】/* 将单链表L初始化为一个空表 */void InitList(LinkList *L) /* 注意参数*/ *L=(LinkList)malloc(sizeof(Node);

6、/* 建立头结点*/ (*L)-next=NULL;2.3 线性表的链式存储线性表的链式存储n2.3.2 单链表上的基本运算单链表上的基本运算2. 建立单链表建立单链表（1）头插法建立单链表）头插法建立单链表图图2.9 头插法建立单链表图示头插法建立单链表图示 2.3 线性表的链式存储线性表的链式存储n2.3.2 单链表上的基本运算单链表上的基本运算2. 建立单链表建立单链表（1）头插法建立单链表）头插法建立单链表图图2.9 头插法建立单链表图示头插法建立单链表图示 2.3 线性表的链式存储线性表的链式存储【算法算法2.6 用头插法建立单链表用头插法建立单链表】/* L是带头结点的空单链表，通

7、过键盘输入元素，用头插法建立单链表是带头结点的空单链表，通过键盘输入元素，用头插法建立单链表 */void CreateFromHead(Linklist L) Node *s; char c; int flag=1; while(flag) /* flag初值为初值为1，当输入，当输入“$”时，将时，将flag置为置为0，建表结束，建表结束 */ c=getchar(); if(c! =$) s=(Node*)malloc(sizeof(Node); /* 建立新结点建立新结点s */ s-data=c; s-next=L-next; /* 将将s插入表头插入表头 */ L-next=s;

8、else flag=0; 2.3 线性表的链式存储线性表的链式存储n2.3.2 单链表上的基本运算单链表上的基本运算（2） 尾插法建表尾插法建表图图2.10 尾插法建表图示尾插法建表图示 2.3 线性表的链式存储线性表的链式存储【算法算法2.7 尾插法建立单链表尾插法建立单链表】 void CreateFromTail(LinkList L) Node *r, *s; char c; int flag=1; /* flag初值为初值为1，当输入，当输入“$”时，时，flag为为0，建表结束，建表结束 */ r=L; /* r指向链表的当前表尾，指向链表的当前表尾， 便于做尾插入，初始指向附加便

9、于做尾插入，初始指向附加 头结点头结点 */ while(flag) c=getchar( ); if(c! =$) s=(Node*)malloc(sizeof(Node); s-data=c; r-next=s; r=s; elseflag=0; r-next=NULL; /* 将最后一个结点的将最后一个结点的next链域置为空链域置为空*/ 2.3 线性表的链式存储线性表的链式存储n为了验证单链表的插入算法，设计一个输出单链表的算法【算法 输出单链表】 void output(LinkList L)Node *p;p=L-next;while(p!=NULL) printf(%d ,p-

10、data); /*格式符由数据类型确定*/ p=p-next;2.3 线性表的链式存储线性表的链式存储建立单链表的算法实现建立单链表的算法实现 #include#includetypedef char ElemType;typedef struct Node /* 结点类型定义结点类型定义 */ElemType data;struct Node *next;Node,*LinkList; /* LinkList为结构体指针类型为结构体指针类型 */void InitList(LinkList *L) /* 初始化一个空单链表初始化一个空单链表 */ *L=(LinkList)malloc(si

11、zeof(Node); /* 建立头结点建立头结点*/ (*L)-next=NULL;2.3 线性表的链式存储线性表的链式存储void CreateFromTail(LinkList L) Node *r, *s; char c; int flag=1; /* flag初值为初值为1，当输入，当输入“$”时，时，flag为为0，建表结束，建表结束 */ r=L; /* r指向链表的当前表尾，指向链表的当前表尾， 便于做尾插入，初始指向头结点便于做尾插入，初始指向头结点 */ while(flag) c=getchar(); if(c!=$) s=(Node*)malloc(sizeof(Nod

12、e); s-data=c; r-next=s; r=s; else flag=0; r-next=NULL; /* 将最后一个结点的将最后一个结点的next链域置为空链域置为空*/ 2.3 线性表的链式存储线性表的链式存储void output(LinkList L)Node *p;p=L-next;while(p!=NULL) printf(%c ,p-data); p=p-next;printf(n);void main() LinkList H; /* 定义单链表定义单链表H */InitList(&H); /* 初始化单链表初始化单链表H为空表为空表 */CreateFromT

13、ail(H); /* 尾插法建立单链表尾插法建立单链表H */output(H); /* 输出表输出表H */ 2.3 线性表的链式存储线性表的链式存储n2.3.2 单链表上的基本运算单链表上的基本运算3. 查找查找 (1) 按序号查找在单链表中，由于每个结点的存储位置都放在其前一结点的next域中，因而即使知道被访问结点的序号i，也不能像顺序表那样直接按序号i访问一维数组中的相应元素，实现随机存取，而只能从链表的头指针出发，顺链域next逐个结点往下搜索，直至搜索到第i个结点为止。2.3 线性表的链式存储线性表的链式存储n2.3.2 单链表上的基本运算单链表上的基本运算3. 查找查找 (1)

14、 按序号查找算法描述：算法描述：要查找表中第i个结点，则需要从单链表的头指从单链表的头指针针L出发出发，从头结点开始顺着链域（L-next）扫描，用指针p指向当前扫描到的结点, 初值指向头结点，用用j做计数器，累计当做计数器，累计当前扫描过的结点数（初值为前扫描过的结点数（初值为0），当），当j = i 时，指针时，指针p所指的结所指的结点就是要找的第点就是要找的第i个结点个结点。2.3 线性表的链式存储线性表的链式存储【算法算法2.8 在单链表在单链表L中查找第中查找第i个结点个结点】 /* 在带头结点的单链表在带头结点的单链表L中查找第中查找第i个结点，个结点， 若找到若找到(1in)，

15、则返回该结点的指针则返回该结点的指针; 否则返回否则返回NULL */ Node *Get(LinkList L, int i) int j； Node *p； if(inext! =NULL)& (jnext； /* 扫描下一结点扫描下一结点 */ j+； /* 已扫描结点计数器已扫描结点计数器 */ if(i=j) return p； /* 找到了第找到了第i个结点个结点 */ else return NULL； /* 找不到，找不到， i0或或in */ /* Get */ 2.3 线性表的链式存储线性表的链式存储n2.3.2 单链表上的基本运算单链表上的基本运算3. 查找查找(

16、2) 按值查找算法描述算法描述：按值查找是指在单链表中查找是否有结点值等于e的结点，若有的话，则返回首次找到的其值为e的结点的地址，否则返回NULL。查找过程从单链表的头指针指向的头结点出发，顺着链逐个将结点的值和给定值e作比较。2.3 线性表的链式存储线性表的链式存储【算法算法2.9 在单链表在单链表L中查找值等于中查找值等于key的结点的结点】/* 在带头结点的单链表在带头结点的单链表L中查找其结点值等于中查找其结点值等于key的结点，的结点， 若找到则返回该若找到则返回该结点的位置结点的位置p；否则返回；否则返回NULL */ Node *Locate( LinkList L, ElemType key) Node *p; p=L-next; /* 从表中第一个结点比较从表中第一个结点比较 */ while (p!=NULL) if (p-data!=key) /* 未找到结点未找到结点