1,为什么要用到链表
数组作为存放同类数据的集合,给我们在程序设计时带来很多的方便,增加了灵活性。但数组也同样存在一些弊病。如数组的大小在定义时要事先规定,不能在程序中进行调整,这样一来,在程序设计中针对不同问题有时需要3 0个大小的数组,有时需要5 0个数组的大小,难于统一。我们只能够根据可能的最大需求来定义数组,常常会造成一定存储空间的浪费。
我们希望构造动态的数组,随时可以调整数组的大小,以满足不同问题的需要。链表就是我们需要的动态数组。它是在程序的执行过程中根据需要有数据存储就向系统要求申请存储空间,决不构成对存储区的浪费。
链表是一种复杂的数据结构,其数据之间的相互关系使链表分成三种:单链表、循环链表、双向链表,下面将逐一介绍。
2,单向链表
单链表有一个头节点head,指向链表在内存的首地址。链表中的每一个节点的数据类型为结构体类型,节点有两个成员:整型成员(实际需要保存的数据)和指向下一个结构体类型节点的指针即下一个节点的地址(事实上,此单链表是用于存放整型数据的动态数组)。链表按此结构对各节点的访问需从链表的头找起,后续节点的地址由当前节点给出。无论在表中访问那一个节点,都需要从链表的头开始,顺序向后查找。链表的尾节点由于无后续节点,其指针域为空,写作为NULL。
如图所示:
上图还给出这样一层含义,链表中的各节点在内存的存储地址不是连续的,其各节点的地址是在需要时向系统申请分配的,系统根据内存的当前情况,既可以连续分配地址,也可以跳跃式分配地址。
3,单向链表程序的实现
(1),链表节点的数据结构定义
struct node { int num; struct node *p; } ;
在链表节点的定义中,除一个整型的成员外,成员p是指向与节点类型完全相同的指针。
在链表节点的数据结构中,非常特殊的一点就是结构体内的指针域的数据类型使用了未定义成功的数据类型。这是在C中唯一规定可以先使用后定义的数据结构。
(2),链表的创建、输出步骤
单链表的创建过程有以下几步:
1 ) 定义链表的数据结构;
2 ) 创建一个空表;
3 ) 利用malloc ( )函数向系统申请分配一个节点;
4 ) 将新节点的指针成员赋值为空。若是空表,将新节点连接到表头;若是非空表,将新
节点接到表尾;
5 ) 判断一下是否有后续节点要接入链表,若有转到3 ),否则结束;
单链表的输出过程有以下几步
1) 找到表头;
2) 若是非空表,输出节点的值成员,是空表则退出;
3 ) 跟踪链表的增长,即找到下一个节点的地址;
4) 转到2 ).
(3),程序代码例子:
创建一个存放正整数单链表,输入0或小于0的数,结束创建链表,并打印出链表中的值,程序如下:
#include <stdlib.h> /*含ma l l o c ( ) 的头文件*/ #include <stdio.h> //①定义链表数据结构 struct node { int num; struct node *next; }; //函数声明 struct node *creat(); void print(); main( ) { struct node *head; head=NULL; //②建一个空表 head=creat(head);/*创建单链表*/ print(head);/*打印单链表*/ } /******************************************/ struct node*creat(struct node *head)/*返回的是与节点相同类型的指针*/ { struct node*p1,*p2; int i=1; //③利用malloc ( )函数向系统申请分配一个节点 p1=p2=(struct node*)malloc(sizeof(struct node));/*新节点*/ printf("请输入值,值小于等于0结束,值存放地址为:p1_ADDR= %d\n",p1); scanf("%d",&p1->num);/*输入节点的值*/ p1->next=NULL;/*将新节点的指针置为空*/ while(p1->num>0)/*输入节点的数值大于0*/ { //④将新节点的指针成员赋值为空。若是空表,将新节点连接到表头;若是非空表,将新节点接到表尾; if(head==NULL) head=p1;/*空表,接入表头*/ else p2->next=p1;/*非空表,接到表尾*/ p2=p1; p1=(struct node*)malloc(sizeof(struct node));/*下一个新节点*/ i=i+1; printf("请输入值,值小于等于0结束,值存放地址为:p%d_ADDR= %d\n",i,p2); scanf("%d",&p1->num);/*输入节点的值*/ //⑤判断一下是否有后续节点要接入链表,若有转到3 ),否则结束; } //==============原来程序更正部分:(多谢@daling_datou提醒)================================ free(p1); //申请到的没录入,所以释放掉 p1=NULL; //使指向空 p2->next = NULL; //到表尾了,指向空 printf("链表输入结束(END)\n"); //============================================== return head;/*返回链表的头指针*/ } /*******************************************/ void print(struct node*head)/*出以head为头的链表各节点的值*/ { struct node *temp; temp=head;/*取得链表的头指针*/ printf("\n\n\n链表存入的值为:\n"); while(temp!=NULL)/*只要是非空表*/ { printf("%6d\n",temp->num);/*输出链表节点的值*/ temp=temp->next;/*跟踪链表增长*/ } printf("链表打印结束!!"); }
在链表的创建过程中,链表的头指针是非常重要的参数。因为对链表的输出和查找都要从链表的头开始,所以链表创建成功后,要返回一个链表头节点的地址,即头指针。
程序执行流程:
4,单链表操作基础示例
#include <stdio.h> #include <malloc.h> #define LEN sizeof(NODE) typedef struct _NODE//节点声明 { int val; struct _NODE* next; } NODE, *PNODE; void print(PNODE head){//打印所有节点 while (head) { printf("%3d",head->val); head = head->next; } printf("\n"); } void insertHead(PNODE *pHead, int val){//头插法 PNODE n = (PNODE)malloc(LEN); n->val = val; n->next = *pHead; *pHead = n; } void insertTail(PNODE *pHead, int val){//尾插法 PNODE t = *pHead; PNODE n = (PNODE)malloc(LEN); n->val = val; n->next = NULL; if (*pHead == NULL) { n->next = *pHead; *pHead = n; }else{ while (t->next) { t = t->next; } t->next = n; } } void deleteHead(PNODE *pHead){//删除头 if (*pHead == NULL) { return; } else { PNODE t = *pHead; *pHead = (*pHead)->next; free(t); } } void deleteTail(PNODE *pHead){//删除尾 PNODE t = *pHead; if (t == NULL) { return; } else if (t->next == NULL) { free(t); *pHead = NULL; } else{ while (t->next->next != NULL) { t = t->next; } free(t->next); t->next = NULL; } } PNODE findByVal(PNODE head, int val){//根据值找到满足条件的第一个节点 while (head != NULL && head->val != val) { head = head->next; } return head; } PNODE findByIndex(PNODE head, int index){//根据索引找节点 if (index == 1) { return head; } else { int c = 1; while (head != NULL && index != c) { head = head->next; c++; } } return head; } void insertByIndex(PNODE *pHead, int index, int val){//根据索引插入节点 if (index == 1) { insertHead(pHead, val); } else { PNODE t = findByIndex(*pHead,index - 1); if (t == NULL) { return; } else { PNODE n = t->next; t->next = (PNODE)malloc(LEN); t->next->next = n; t->next->val = val; } } } void deleteByIndex(PNODE *pHead, int index)//根据结点索引删除结点 { if (index == 1) { deleteHead(pHead); } else { PNODE t= findByIndex(*pHead, index - 1); if (t == NULL || t->next == NULL) { return; }else{ PNODE n = t->next->next; free(t->next); t->next = n; } } } void deleteByVal(PNODE *pHead, int val)//根据值删掉第一个满足条件的 { if (*pHead == NULL)//如果空表退出 { return; } else { if ((*pHead)->val == val)//如果第一个就是,删头 { deleteHead(pHead); } else { PNODE t = *pHead; while (t->next != NULL && t->next->val != val)//遍历,若t的next为空或者next是要找的节点则退出 { t = t->next; } if (t->next)//如果t指向要找的结点的上一个节点 { PNODE n = t->next->next;//删除要找的结点 free(t->next); t->next = n; } } } } void clear(PNODE *pHead)//清除链表 { while ((*pHead) != NULL) { deleteHead(pHead);//从头删除 } } void main() { PNODE head = NULL; insertTail(&head,1); deleteHead(&head); insertTail(&head,2); insertTail(&head,3); insertTail(&head,4); insertTail(&head,5); insertTail(&head,6); print(head); insertByIndex(&head, 6, 9); print(head); //deleteByIndex(&head,3); deleteByVal(&head, 2); print(head); clear(&head); print(head); insertByIndex(&head,1,12); print(head); }
本文向大家介绍C语言实现数据结构和双向链表操作,包括了C语言实现数据结构和双向链表操作的使用技巧和注意事项,需要的朋友参考一下 数据结构 双向链表的实现 双向链表中的每一个结点都含有两个指针域,一个指针域存放其后继结点的存储地址,另一个指针域则存放其前驱结点的存储地址。 双向链表结点的类型描述: 其中,prior域存放的是其前驱结点的存储地址,next域存放的是其后继结点的存储地址。 双
本文向大家介绍数据结构 C语言实现循环单链表的实例,包括了数据结构 C语言实现循环单链表的实例的使用技巧和注意事项,需要的朋友参考一下 数据结构 C语言实现循环单链表的实例 实例代码: 如图: 感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!
本文向大家介绍C语言数据结构之循环链表的简单实例,包括了C语言数据结构之循环链表的简单实例的使用技巧和注意事项,需要的朋友参考一下 C语言数据结构之循环链表的简单实例 实例代码: 第二种方法: 感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!
本文向大家介绍C++语言数据结构 串的基本操作实例代码,包括了C++语言数据结构 串的基本操作实例代码的使用技巧和注意事项,需要的朋友参考一下 C语言数据结构 串的基本操作实例代码 输出结果: 实现代码:
本文向大家介绍C语言数据结构 链表与归并排序实例详解,包括了C语言数据结构 链表与归并排序实例详解的使用技巧和注意事项,需要的朋友参考一下 C语言数据结构 链表与归并排序实例详解 归并排序适合于对链表进行原址排序,即只改变指针的连接方式,不交换链表结点的内容。 归并排序的基本思想是分治法:先把一个链表分割成只有一个节点的链表,然后按照一定顺序、自底向上合并相邻的两个链表。 只要保证各种大小的子链表
本文向大家介绍C语言简单的数据结构,包括了C语言简单的数据结构的使用技巧和注意事项,需要的朋友参考一下 示例 结构数据类型是打包相关数据并使它们的行为像单个变量一样有用的方法。 声明一个struct包含两个int成员的简单对象: x并y称为struct的成员(或字段)point。 定义和使用结构: 可以在定义时初始化结构。以上等同于: 还可以使用指定的初始化程序来初始化结构。 也可以使用.运算符来