文档介绍：第十七讲高级数据结构
第十七讲高级数据结构
动态数据结构
自引用的结构体
动态内存分配
链表
程序设计举例
C语言程序设计
2
动态数据结构
Dynamic data structures(动态数据结构)
在程序的执行过程中可以增长和缩短的数据结构。
Linked lists(链表)
在任何地方进行插入和删除。
Stacks(栈)
在栈的顶端进行插入和删除。
Queues(对列)
在队列的末尾插入,在队列的前面删除。
高级数据结构
3
自引用的结构体
自引用的结构体
包含指向相同结构类型的指针成员
可以链接到一起,构成有用的数据结构:
链表
栈
队列
树
高级数据结构
struct node {
int data;
struct node *nextPtr;
};
20
42
数据成员
指针
结点(node)
空指针
链
头指针
4
动态内存分配
动态内存分配
在程序执行期间获取或释放内存
相关的函数()
malloc()
free()
相关的运算符
sizeof
高级数据结构
5
动态内存分配
malloc()函数
void* malloc(size_t size)
参数size :表示要分配的内存的字节数
size_t为sizeof返回的整数类型
一般用 sizeof 运算符确定对象的大小
返回值:指向分配内存的 void* 类型的指针
void* 类型的指针可以被赋值给任何类型的指针变量
如果没有可用内存,则返回 NULL
高级数据结构
int *array, n=30;
array = (int*)malloc(n*sizeof(int));
struct node *sPtr;
sPtr = malloc(sizeof(struct node));
6
动态内存分配
free()函数
void free(void* aPtr)
释放aPtr指向的内存空间
aPtr指向的应该是用 malloc 分配的内存空间
如果不调用free释放array指向的空间,则程序结束后array消失了,但其所指的该段内存仍旧存在且不能被使用(其地址丢失了),即出现内存泄露。
高级数据结构
int *array, n=30;
array = (int*)malloc(n*sizeof(int));
…
free(array);
7
链表
链表
用指针链接的自引用结构的线性集合,这些结构称为结点。
通过指向链表的第一个结点的指针访问链表。
后续的结点通过存储在每个结点中的链接指针成员来访问。
链表中最后一个结点的链接指针被设置为NULL,以标志链表的结尾。
什么时候用链表替代数组
数据成员的数目无法事先确定。
对数据进行快速的排序。
高级数据结构
20
35
42
8
案例分析:链表
链表
问题
输入任意个整数创建链表。
实现常用的操作:遍历,插入,删除,空表判断。
实现()
高级数据结构
#include <>
#include <>
struct listNode {
int data;
struct listNode *nextPtr;
};
typedef struct listNode ListNode;
typedef ListNode* ListNodePtr;
9
案例分析:链表
链表
实现
高级数据结构
void insert(ListNodePtr*, int);
int delete(ListNodePtr*, int);
int isEmpty(ListNodePtr);
void printList(ListNodePtr);
void menu(void);
10