指针典型数据结构简介

第2-6讲指针2——

典型数据结构简介线性表栈队列动态内存分配链表二叉树16.1线性表简介一、线性表的基本概念线性表（linearlist）是最简单、最常用的一种数据结构。线性表由一组数据元素构成一个n维向量英文字母表矩阵学生信息……2线性表是一种线性结构，对于一个非空的线性表，有如下结构特征：有且只有一个头（根）结点，无前继；有且只有一个尾（终端）结点，无后续；其它结点有且只有一个前继，一个后续。线性表中结点的个数n称为线性表的长度。当n=0时，称为空表。线性表的存储结构顺序存储（数组）表中所有元素所占的空间是连续的表中各数据元素在存储空间中是按逻辑顺序依次存放的。链式存储结构（链表，结点）每个结点由两部分组成：数据域和指针域存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致数据元素之间的逻辑关系由指针域来完成3二、线性表的基本运算表的建立线性表的插入顺序存储下的操作注意表的溢出线性表的删除删除操作注意空线性表的查找查找操作注意未找到线性表的排序线性表的分解线性表的合并线性表的复制线性表的逆转4三、栈栈（stack）是一种特殊的线性表，限定在一端进行插入与删除操作。在栈中允许插入、删除的一端称为栈顶(top)，不允许插入、删除的一端称为栈底(bottom)。栈是按照“先进后出”(FILO:firstinlastout)或“后进先出”(LIFO:lastinfirstout)原则组织数据的。a1a2┋an入栈出栈topbottom5栈的基本运算入栈出栈，读栈顶元素1.建立一个栈的存储空间获取栈的容量，maxStack设栈顶top=062.入栈运算是指在栈顶位置插入一个新元素基本操作：栈顶top（指针）加1新元素插入到栈顶指针指向的位置异常操作：栈满溢出73.出栈，栈顶数据的弹出读出栈顶元素值，将其赋给一个指定的变量。栈顶指针top减1异常：栈空(top<0)8四、队列队列(equeue)也是一种特殊的线性表，它允许在一端进行插入，而在另一端进行删除。队列中允许插入的一端称为队尾(rear)，允许删除的一端称为队头(front)。在队列中，最先插入的元素将最先被删除，最后插入的元素最后才能被删除。因此队列又称为“先进先出”(FIFO:firstinfirstout)或“后进后出”(LILO:lastinlastout)FEDCBA出队入队frontrear9队列运算入队列出队列，读出队列数据FEDCBA出队入队frontrearrearAEDCB出队入队frontrearAfront10顺序存储1.建立队列2.入队列在队尾加入一个新元素队尾指针rear加1异常：队列满，溢出113.出队列读出队头元素值，将其赋给一个指定的变量。队头指针front加1异常：队空(front==rear)12136.2动态内存分配与链表一、动态内存分配动态数据结构可以在运行时灵活地添加、删除或重排数据项。动态内存管理则允许在运行时分配更多的内存空间或释放掉不再需要的空间，因而可以优化存储空间的使用。在运行时分配内存空间的过程就称为动态内存分配。

程序内存空间

代码区(codearea)全局数据区(dataarea)堆区(heaparea)栈区(stackarea)存放程序的代码全局数据和静态数据程序的动态数据程序的局部数据14C语言提供了4个“内存管理函数”，以用来在程序运行时分配和释放内存函数任务malloc分配所需的字节大小，并返回指向所分配空间的第一个字节的指针calloc为元素数组分配空间，并初始化为零，然后返回指向该内存的指针free释放前面已分配的空间realloc修改前面已分配空间的大小15用malloc函数分配一块内存malloc函数将保留指定大小的内存块，并返回void类型的指针。

ptr=(cast-type*)malloc(byte-size);ptr为cast-type类型的指针。malloc函数返回一个指向大小为byte-size的内存区的指针（其类型为cast-type）。malloc函数分配的是连续的字节块。如果堆的空间不能满足要求，则分配失败。如果失败，将返回NULL。例如：x=(intx)malloc(100*sizeof(int));分配一个大小为100倍的int类型的内存空间，该内存的第一个字节的地址赋值给类型为int的指针xcptr=(char*)malloc(10);给char类型的指针分配10个字节的空间st_var=(structstudent*)malloc(sizeof(structsdudent));动态分配的存储空间没有名称，因此只能通过指针来访问其内容。

16例6-1，请编写一个程序，使用一个整数表，其大小在运行时交互地指定。17用calloc函数分配多个内存块分配多个存储块，每个块大小相等，并把所有字节都初始化为零。ptr=(cast-type*)calloc(n，elem-size);18用free函数释放已用的空间变量的编译时存储空间是由系统及其存储类来分配和释放的。对于运行时的内存分配，当不再需要时，由程序员来负责释放。当不再需要保存在内存块中的数据时，且不打算用它来存储任何其他信息时，可用free函数来释放掉内存块。free函数形式为：

free(ptr);释放由ptr指向的内存区，该内存块由malloc或calloc创建的，是最近一次调用的返回的值。在该函数调用中，使用非法的指针可能产生问题或引起系统崩溃。注意：所释放的不是指针本身，而是它所指向的内容。要释放由calloc分配的内存数组，只需要释放该指针一次即可。19用realloc函数改变内存块的大小改变已分配内存块的大小的过程——内存重分配(reallocation)。已分配内存不够；已分配内存太大。realloc函数的形式ptr=realloc(ptr,newsize);该函数把大小为newsize的新内存空间分配给指针变量ptr，并返回一个指向新内存块的第一个字节的指针。新内存块的开始位置可以与旧的相同，也可以不同。该函数保证九数据的完整性。即：旧内存块中的内容将移到新块中。如果函数没有成功分配更多的空间，将返回一个空指针，就块被丢失。例6-2，请编写一个程序，把一个字符串保存在由malloc创建的内存块中，然后修改它以存储更大的字符串。2021二、链表的概念链表是一种常见的重要的数据结构。其大小可以在程序运行时增大或缩小，可按需决定。它是一种动态数据结构。链表是用指针表示两个元素之间的先后顺序关系，在逻辑上不要求两个链表元素在物理上一定相邻，且链表元素可根据需要开辟内存单元。链表中的每一个元素称为“结点”，每个结点都应包含两部分：用户需要用的实际数据指向下一个结点的指针nodeitemnext22链表的一般形式例如：structlink_list{floatdata;

structlink_list*next;}；structlist_linknode1,node2;node1.next=&node2;node1.data=35.6;node2.data=45.5;node2.next=0;node1node1.datanode1.nextnode2node2.datanode2.nextXXXX35.645.5023链表是由指向下一个结点的指针(next)链接而成的。next指针具有与结点相同的类型。该指针由一个特殊的标志(head)开始，由另一个特殊的标志(NULL)结束。学生结点的定义&stu295.5Zhang10010&stu388.5Wang10011NULL88.5Wang10020&stu1head24链表提供的灵活性允许高效地重排数据项。通过重排链接，就可以很容易地插入或删除数据项。item1

item2

item3

x

要插入的项item1

item2

item3

要删除的项25链表的种类线性链表环形链表双向链表双向环形链表

item1

item20item3

item1

item2

item3

item10

item2

0item3

item1

item2

item3

26三、创建链表把链表看作是一种抽象数据类型，并可以执行以下基本操作：创建链表遍历链表计算链表中的数据项数目显示链表查找某数据项，用于编辑或显示插入一个数据项删除一个数据项连接两个链表27链表的建立（初始化）链表的建立就是要建立结点间的链接关系方法就是将每一结点中的next指针分别赋以它要指向（链接）的结点的地址28例6-3，建立一个由三个学生数据结点组成的简单链表，并输出各结点数据29例6-4，建立一个单向动态链表3031链表的结点的插入、删除操作插入结点原来链表为空表原来链表不为空在头结点前插入在当前结点后插入在链表尾插入3233删除结点要删的是第一个结点要删的结点不存在要删的结点存在，且不是头结点346.3二叉树二叉树的基本概念是一种非线性的结构树结构中最简单的一种外形像一棵倒立的树；最上层有一个“根结点”；每个结点都是一个结构，一个成员存放元素的值，另两个成员是指针，分为左指针L和右指针R；根结点的左指针指向左子树，右指针指向右子树；左子树或右子树本身又是一棵二叉树，又有它们自己的左子树和右子树……二叉树是递归定义的，处理时常用递归算法356LR4LR8LR3LR5LR7LR9LRrootcode1code2code3code4code5code6code736二叉树的建立树中的每个结点有一个整数，数据名为data；有两个指针（左指针Left，右指针Right），分别指向这个结点的左子树和右子树。structTreeNode{ intdata; structTreeNode*Left,*Right;};二叉树的建立规则：第一个数据是这棵树的根数据；之后再输入的数据，每一个都要与根中的数据比较，以便确定其插入的位置；假定，待插入的数据如果比根结点小，则将其插至左子树，否则插入右子树。3784122720

insertTree(pRoot,temp)

根结点为空root==NULL新结点作为根结点