课件第1部分3单向链表VIP

1、C单向链表单向链表知识回顾知识回顾顺序表的缺点：顺序表的缺点：连续的存储模式使得插入和删除运算不方便连续的存储模式使得插入和删除运算不方便, ,需要需要移动大量的数据元素。移动大量的数据元素。由于要求占用连续的存储空间，存储分配只能预先由于要求占用连续的存储空间，存储分配只能预先进行进行解决的办法：解决的办法：改变连续存储模式改变连续存储模式单向链表单向链表单向链表单向链表数据域数据域指针域指针域结点结点头指针头指针空指针空指针130Aheada0 1475130Aa1 10CB1475a2 10CB 数据元素的逻辑顺序是通过链表中的指针连接次序来实现的。 为了把插入和删除都统一为后插和后删，

2、增加一个不含数据的链表头结点何谓头指针、头结点和数据首结点？头指针是指向链表中第一个结点（或为头结点头指针是指向链表中第一个结点（或为头结点或为数据首结点）的指针。或为数据首结点）的指针。 单链表可由一个头指针唯一确定。单链表可由一个头指针唯一确定。头结点是在链表的数据首结点之前附设的一个头结点是在链表的数据首结点之前附设的一个结点；不存数据结点；不存数据;数据首结点是指链表中存储第一个数据元素的数据首结点是指链表中存储第一个数据元素的结点。结点。 头指针头指针头结点头结点 数据首结点数据首结点a0不带头结点的单链表130Aheada0 1475130Aa1 10CB1475a2 10CB不带

3、头结点的空单链表headhead=NULL头指针头指针数据首结点数据首结点带头结点的单链表12EFhead130A12EFa0 1475130Aa1 10CB1475a2 10CB带头结点的空单链表 headhead-next=NULL头指针头指针头结点头结点数据首结点数据首结点 结点结点datadatanextnext数据域数据域指针域指针域 struct Node struct NodeType data; Type data; struct Node struct Node * *next;next; ；typedef struct Node Nodetypedef struct Nod

4、e Node；单向链表单向链表结点的定义结点的定义单项链表定义如下： 顺序表的结构顺序表的结构/node.h#ifndef NODE_H#define NODE_HStruct Node Type data; /存储数据 Struct Node *next; /存储“关系” ;Typedef struct Node Node;Node* GetNode (Type item); /创建值为item的动态结点void IniNode(Node *h); /初始化函数void InsertAfter( Node *p, Node* nextptr )；/尾插void ListInsert(Node

5、 *head, Type item)；/顺序插入Node* DeleteAfter (Node *p)； /后删void ListClear (Node *h)； /清表#endif（1 1）指针后移操作）指针后移操作 p=p-next p=p-next130Apa0 1475130Aa1 160014751475（2 2）指向指针的指针）指向指针的指针 Node Node * * *h;h;130A*ha0 1475130A*h1000h1000一级指针一级指针二级指针二级指针void IniNode( Node void IniNode( Node * * *h)h) * *h=(Node

6、h=(Node* * )malloc(sizeof(Node); )malloc(sizeof(Node); ( (* *h) - next=NULL;h) - next=NULL; （1）初始化函数）初始化函数单向链表基本运算的实现单向链表基本运算的实现head*hNULL头结点头结点12EFh（2）创建动态结点）创建动态结点NodeNode* * GetNode( Type item ) GetNode( Type item )NodeNode* * newnode=(Node newnode=(Node* * )malloc(sizeof(Node); )malloc(sizeof(No

7、de); if(newnode=NULL) if(newnode=NULL) printf(“overflow!”); printf(“overflow!”); exit(1); exit(1); newnode-data=item; newnode-data=item; newnode-next=NULL; newnode-next=NULL; return (newnode); return (newnode); xP (1) 步骤步骤: :（1 1）找插入位置，指针）找插入位置，指针p p指向插入结点，即指向插入结点，即ai-1ai-1 （2 2）nextptrnextptr指向要插入的

8、结点指向要插入的结点 （3 3）插入：）插入：1 1、 nextptr-next=p-next; nextptr-next=p-next; 2 2、p-next=nextptr;p-next=nextptr;(2)(3.1)(3.2)（3）后插运算）后插运算nextptrheada0ai-1aian-1不可以！（3.1）和（）和（3.2）可）可不可以交换？为什么？不可以交换？为什么？heada0ai-1aian-1p (1) xnextptr x？void InsertAfter( Node void InsertAfter( Node * *p, Nodep, Node* * nextptr

9、 ) nextptr ) nextptr-next=p-next; nextptr-next=p-next; p-next=nextptr; p-next=nextptr; （4）顺序插入（按增序把数据插入链表）顺序插入（按增序把数据插入链表） 步骤：步骤： 用一个指针指向链表头结点。用一个指针指向链表头结点。 用另一个指针指向新创建的数据结点用另一个指针指向新创建的数据结点 寻找插入位置寻找插入位置 插入新的数据结点插入新的数据结点 an-11614itemnewpheada0ai-1aipppvoid ListInsert(Node *head, Type item) Node *p, *

10、newp; p=head; newp=GetNode(item); /新新创创建建结结点点 while(p-next!=NULL) if(p-next-datanext; else break; InsertAfter(p, newp); 搜索链表，寻搜索链表，寻找插入位置找插入位置（5）后删（删除）后删（删除Ptr结点的后继结点）结点的后继结点）130A12EFa0 1475130Aai-1 10CB1800ai 150010CB1800ptrai+1 1600150010CBt12EFhead1500t=ptr-next;t=ptr-next;ptr-next=t-next;ptr-nex

11、t=t-next;Node* DeleteAfter (Node *ptr) Node *t=ptr-next; if(t!=NULL) ptr-next=t-next; return (t);（6）查找（查找数据）查找（查找数据）Node* FindNode (const Node *h, Type item) Node *p=h-next; while(p!=NULL) if(p-data=item) break; p=p-next; return(p);（7）清表（执行清表操作后结果为空表）清表（执行清表操作后结果为空表）void ListClear (Node *h) Node *p=

12、DeleteAfter(h); /删删除除数数据首据首结结点点 while(p!=NULL) free(p); /释释放放结结点空点空间间 p=DeleteAfter(h); /继续删继续删除下一除下一个结个结点点 将单向链表中的数据逆置。步骤如下：将单向链表中的数据逆置。步骤如下：1 1）令指针）令指针rearrear指向链表头结点。指向链表头结点。2 2）如果链表非空，令指针）如果链表非空，令指针rearrear指向数据首结点。指向数据首结点。3 3）如果）如果* *rearrear有后继结点，就删除其后继结点，有后继结点，就删除其后继结点，并把删除的结点插到链表头结点之后，否则算法并把删除的结点插到链表头结点之后，否则算法结束。结束。(7) 逆置逆置单链表的就地逆置单链表的就地逆置bcdeaheadheadedcabrearrearheadabcdedelabcderearheadvoid Revert(Node void Revert(Node * *head)head) Node Node * *rear=head,rear=head,* *del;del; if(head-next! = NULL) i