《C语言2动态数据结构(二级C的内容可参考)》由会员分享，可在线阅读，更多相关《C语言2动态数据结构(二级C的内容可参考)（72页珍藏版）》请在金锄头文库上搜索。
1、1121.结构体概述 2.结构体类型和结构体变量的定义 3.结构体类型变量的引用 4.结构体与数组 5.结构体和指针 6.动态链表动态数据结构本节开始介绍动态数据结构，主要介绍链表结构 的建立、在链表中查找指定元素、插入一个新元 素、删除一个元素等操作。学完本节内容后，要求深刻理解动态存储结构的 概念，并正确运用。36 动态链表6.1 从静态数据结构到动态数据结构 6.2 动态内存分配（4个函数） 6.3 链 表 6.4 小 结6.1 从静态数据结构到动态数据结构在此之前，我们涉及到的都是静态数据结构，像数 组、简单类型(int、float)等。静态数据结构的特点是由系统分配固定大小的存储 空
2、间，以后在程序运行的过程中，存储空间的位置 和容量都不会再改变。而实际生活中常常有这样的问题，数据量的多少是 动态变化的。56.1 从静态数据结构到动态数据结构例如，图书馆的藏书量，在图书馆初建时，假设有 10000本，随着时间的推移，藏书的数量必定要增加。有人可能会想，在定义一个静态变量时，预留出一 部分空间，但这也会引起一些问题，首先多出的那部分空间不知何时才能使用，在没 有被使用之前一直被闲置；其次，谁又能保证增加的空间就足够呢？而且图 书馆藏书也有减少的可能。66.1 从静态数据结构到动态数据结构问题的关键在于，此问题的数据本身就是变化的， 而且是不确定的变化，什么时候变、怎么变都是未
3、 知的。对这样的问题用静态存储结构来描述和存放显然捉 襟见肘，存在隐患。76.1 从静态数据结构到动态数据结构动态数据结构不确定总的数据存储量，而是为现有 的每一个数据元素定义一个确定的初始大小的空间 ，若干个数据元素分配若干个同样大小的空间；当 问题的数据量发生变化时，数据的存储空间的大小 也发生变化。如果数据量增加，就重新向系统申请新的空间；如 果数据量减少，就将现有的多余的空间归还给系统 。86.2 动态内存分配 使用计算机解决问题的所有方法都是通过使用系统提供 给我们的基本命令或函数来实现的。所以首先让我们来 看看，c的标准函数中有哪些是用于动态内存分配的，怎样使用。 ANSI C 中
4、动态内存操作标准函数 ANSI C中提供了若干个动态内存操作标准函数，它们 的名称分别是malloc、calloc、realloc、free等。这 些函数可以使用在任何的C环境中。 c+ 中为进行动态操作提供了运算符new和delete91malloc函数malloc函数是 C的标准函数之一。原型定义在malloc.h文件中。原型为：void *malloc(unsigned int size);其作用是向系统申请一个确定大小(size 个字节)的存储 空间，返回值为一个指向void类型的分配域起始地址的指针值。如果此函数操作失败，返回值为空。使用格式： 指针型变量 =(基类型*)malloc
5、(需要的存储空间的字节数);101malloc函数 malloc函数是 C的标准函数之一。原型定义在malloc.h文件中。 原型为： void *malloc(unsigned int size); 其作用是向系统申请一个确定大小(size 个字节)的存储空 间，返回值为一个指向void类型的分配域起始地址的指针值。如果此函数操作失败，返回值为空。 使用格式： 指针型变量 =(基类型*)malloc(需要的存储空间的字节数);指针有确定的数据类型，如果想把其他类型赋 给某个类型指针，编译器会发出警告。为了解决这 个问题，C语言引用了void *类型，即表示malloc函 数的返回值可以指向任
6、何类型。为什么malloc函数返回值是void * 而不是其它类型？11例：为一个整数申请一个存储空间 需要的语句为： 在文件的头部：#include 在说明部分： int *p; 在程序中：p = ( int * ) malloc ( sizeof ( int ) ) ; 说明： 动态管理内存的标准函数的说明在malloc.h中。 动态管理内存的标准函数的返回值都是指向void 类型的指针类型。在程序中需要的是指向具体类型的指针变量， 应该进行强制类型转换，使得到的指针为指向确定类型的 指针值。12测试malloc的程序举例：13测试malloc的程序举例：142calloc函数calloc
7、函数是 C的标准函数之一。原型定义在malloc.h文件中。原型为： void *calloc(unsigned int n , unsigned int size);其作用是向系统申请 n 个大小为size 个字节的连续 存储空间，返回值为一个指向void类型的分配域起始地址的指针值。如果此函数操作失败，返回值为 空。可以为一维数组开辟一片连续的动态存储空间 。15例：为一个有10个整数的一维数组分配存储空间使用格式：指针型变量 =(数组元素类型*)calloc(n , 每一个数组 元素的存储空间的字节数)；需要的语句为： 在文件的头部：#include 在说明部分： int *p; 在程序
8、中：p = (int *)calloc( 10 , sizeof(int) ; 16程序：#include #include #include void main() int *p; int x,i; p =(int *)calloc(10, sizeof(int); if(!p) et(0) ; printf(“p=%ldn“, p); for(i=0;i #include #include void main() int *p; int x,i; p =(int *)calloc(10, sizeof(int); if(!p) et(0) ; printf(“p=%ldn“, p); fo
9、r(i=0;i #include #include void main() int *p; int x,i; /*p =(int *)calloc(10, sizeof(int); */ /* if(!p) et(0) ; */ printf(“p=%ldn“, p); for(i=0;i 在说明部分： int *p2; 在程序中：p2 = ( int * )realloc( p1, sizeof( int ) * 20 ); 23程序 ：#include #include #include void main()int *p1,*p2; int i; p1 =(int *)malloc(si
10、zeof(int)*10); if(!p1) et(0) ; for(i=0;i 在说明部分： int *p; 在程序中：free( p )25程序举例 ：#include #include #include void main()int *p1; int i; p1 =(int *)malloc(sizeof(int)*10); if(!p1) et(0) ; for(i=0;idata , p-next4.说明：本章的所有程序都是基于以上类型定义。363 链表的建立 1. 构造一个空线性链表 L ：为了描述方便，通常将链表的第一个结点空置，不存 放数据元素，只是作为链表的开始标志，称为头结
11、点 。数据元素从链表的第二个结点开始存放。空的线性表定义为没有数据元素的表。一个空的线性链表就规定为，只有一个头结点的链表 。所以，构造一个空的线性链表就是建立只有一个头结 点的链表。37 算法描述: 申请一个结点的空间； 将该结点作为线性链表的头结点； 将该结点的 next 域置空； 完整程序 void InitList ( LinkList L ) L=(LNode*)malloc(sizeof(LNode);if ( !L) et ( 0 );L-next = NULL;384逆序输入 n 个数据元素，建立带表头结 点的单线性链表 L现在开始建立一个非空的线性链表。我们这里所建的链 表的
12、第一个结点都是头结点。数据元素从链表的第二个 结点开始存放。一个非空的线性链表是除了头结点以外至少有一个数据 元素的链表。线性链表由若干个数据元素结点组成。那 么，构造一个非空的线性链表的过程就是逐个建立数据 元素结点，并将它们依次插入到链表中的过程。39所谓头插入，即每次将数据元素结点插入到表头结点的之后，第一个数据元素结点之前。 插入过程如图所示：初始状初始状态态态态：插入第一个结点之后：an40插入第二个结点之后：n插入第三个结点之后：n插入最后一个结点之后：an-1anan-1an-2anan-1a1an 41完整程序：#include #include #include typede
13、f struct LNodeint data;struct LNode *next;LNode,*LinkList;42void CreateList ( LinkList L, int n )int i; LNode *p; printf(“现在建立链表：n“); for ( i = n;i 0;i-) printf(“请输入第%d个结点的元素值：n“,i); p=(LNode*)malloc(sizeof(LNode);if ( !p ) et (0); scanf(“%d“, p-next = L-next ; L-next = p ;43void main()LNode *L,*p;
14、int n; printf(“请输入链表中的元素个数：“); scanf(“%d“,printf(“现在建立链表的头结点：n“); L = (LNode*) malloc( sizeof ( LNode ) ); if ( !L ) et ( 0); L-next = NULL; printf(“现在开始建立链表：n“); CreateList(L,n);printf(“链表建立结束，开始输出链表中的元素值！n“); for(p=L;p;p=p-next) if(p=L) printf(“头结点的地址值：%u “, p);else printf(“当前结点的地址值：%u “, p);print
15、f(“tp-data=%d n“, p-data);printf(“n“); 44以上的算法只是建立链表的一种方法，它的 核心是新的数据元素结点插在链表的第一个 数据元素的位置；我们也可以将新建立的数据元素结点每次都 插在链表的尾部。大家可以思考一下，以尾插入的方式建立链 表，程序怎样编写？485 链表结点的插入将一个数据元素插入到链表中，有三种情况：头插入：将一个新元素插入在链表的头结点的后面，其 它的所有结点之前称为头插入。尾插入：将一个新元素插入在链表的尾结点的后面，使 得新插入的结点成为尾结点称为尾插入。 在链表中的第i个数据元素的位置处插入：将一个新元 素插入在链表中的第i个数据元素的位置处，即插入在 第i个数据元素结点之前，使得新插入的结点成为链表 中的第i个结点。49例：已有链表L 如图所示,链表中的元素按 递增有序排列： 其中每个结点中存放的值为学生的考试成绩。现在有另 外三个学生的的成绩分别为65、82、90。将他们插入 到链表L中，要求插入之后链表依然递增有序。807085链表的插入过程L50头插入过程 将 65 插入到链表L中: 为65申请一个结点空间，首地址
