C语言开发基础教程第11章 常见的数据结构 教学PPT181127.pptxVIP

第11章 常见的数据结构· 链表· 栈· 队列11.1 链表链表是线性表的一种。线性表是由具有相同特性的数据元素组成的一个有限序列，在C语言中，线性表有顺序存储和链式存储两种结构，其中以顺序形式存储的线性表称为顺序表，以链式存储的线性表称为链表。11.1 链表C语言中的数组、字符串都可视为存储简单数据的顺序表，顺序表必须占用一整块事先分配好的、大小固定的存储空间，这不利于内存空间管理，因此在对数据灵活性要求较高的程序中，一般会使用链表存储数据。11.1.1 链表概述根据其逻辑结构，链表通常被分为单链表、双向链表、循环链表等，其中单链表的结构最为简单。11.1.1 链表概述链表的每个节点都包含两个部分：存储元素本身的数据域和存储下一个结点地址的指针域。如果节点中只有指向后继节点的指针，那么这些节点组成的链表称为单向链表。11.1.1 链表概述链表可进行的基本操作如下：● 创建-createList ()：创建链表，并将链表初始化为空；● 插入-insertNode()：向链表中插入一个节点；● 删除-delNode()：删除链表其中的某一个节点；● 遍历-printList()：获取定义链表中存数的数据。11.1.2 链表的结构左侧代码以结构体的形式声明了链表节点ListNode、pHead，该节点包含两个成员，其中成员data为数据域，可用于存储整型数据；成员next为指针域，用于存储指向下一个节点的指针。使用此结构定义的链表头指针pHead的数据域可用于存储链表长度。链表节点声明如下：typedef struct linkNode{ int data; struct linkNode *next;}ListNode, pHead;11.1.3 链表的实现1、创建链表若要使用链表，需在声明节点之后先创建链表，并对链表初始化。链表的创建实质上就是头节点的创建，若创建一个空链表，则链表头节点的指针应指向NULL，数据域存储的链表长度应为0。11.1.3 链表的实现pHead *createList(){ //创建头指针 pHead *ph = (ListNode *)malloc(sizeof(ListNode)); ph-data = 0;//初始化链表长度 ph-next = NULL;//初始化头指针指向 return ph;}11.1.3 链表的实现2、插入节点单链表通过节点的指针域来记录下一个节点的位置，从而实现所有节点的连接，因此，当插入一个新元素时，修改节点指针域的指向关系，再修改链表头节点中链表的长度，使其值加1即可。向链表中插入节点的常用方式有头插法和尾插法两种。11.1.3 链表的实现（1）头插法头插法是向链表头部插入新元素，即将新元素插入链表头节点之后。11.1.3 链表的实现（1）头插法此操作分为如下两步：①使新节点的指针指向头节点之后的节点（空链表中即指向NULL，非空链表中指向head-next）；②使头节点指针指向新节点。11.1.3 链表的实现int insertHead(pHead *ph, int data){ //创建新节点 ListNode *newNode = (ListNode *)malloc(sizeof(ListNode)); if (NULL == newNode) return -1; newNode-data = data; newNode-next = ph-next;//插入新节点 ph-next = newNode; ph-data++; //链表长度加1 return 0;}11.1.3 链表的实现（2）尾插法尾插法即将待插入节点插入到最后一个节点之后，使得插入节点成为尾节点。11.1.3 链表的实现（2）尾插法与头插法不同的是，使用尾插法向链表中插入新节点时，需先找到链表的尾节点，之后才能执行插入操作。使用尾插法插入新元素的链表如下图。11.1.3 链表的实现int insertTail(pHead *ph, int data){ pHead *p = ph; while (p-next != NULL){//找到尾节点 p = p-next; } ListNode *newNode = (ListNode *)malloc(sizeof(ListNode)); if (NULL == newNode) return -1; newNode-data = data; newNode-next = NULL; //插入新节点 p-next = newNode; ph-data++; //链表长度加1 return 0; }11.1.3 链表的实现3、删除节点要删除单链表中的元素，只需要使该元素前驱节