《029数据结构》

《《029数据结构》》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、网络游戏开发语言基础-C++程序设计专业教程理论讲解部分Ver3.1第029课数据结构概述：链表的引入链表的基本运算和使用堆栈的定义堆栈的基本运算重点：难点：链表的创建,插入,查找与删除链表的操作9数据结构9.1.1链表的引入与概念第029课数据结构线性表是计算程序设计中最常遇到的一种操作对象,也是数据结构最重要的数据结构形式之一,这种结构的特点是数据元素之间存在着一对一的关系.线性表的存储方式可分为:顺序存储和链式存储.9.1链表的使用第029课数据结构9数据结构线性表的顺序存储结构是用一组地址连续的存储单元依次存储线性表

2、的数据元素。优点:可以随机存取线性表中任意位置的数据元素,数据元素的存储位置可以用一个简单直观的解析式表示.缺点:线性表的插入和删除运算要移动大量其他元素,效率较低,占用大量空间.9数据结构第029课数据结构线性表的链式存储结构是用一组任意的存储单元来存储线性表的各个数据元素.优点:运算效率高,节省空间.如图：第029课数据结构9数据结构structstu{//数据域成员intnum;//数据域成员intscore;//指向stu类型结构的指针变量structstu*next;}如：一个存放学生学号和成绩的结点应为以下结构:

3、9.1.2.链表的基本操作第029课数据结构9数据结构//通过循环依次加入n个结点for(i=0;inum,&pb->age);1）、链表的创建在这里程序在for语句内，用malloc函数建立长度与stu长度相等的空间作为一结点，首地址赋予pb。然后输入结点数据。第029课数据结构9数据结构//如果学号不等于n并且结

4、点指针域不等于空while(p->num!=n&&p->next!=NULL)//不是要找的结点后移一步p=p->next;//如果数据域等于nif(p->num==n)//返回指针preturn(p);2）、链表中结点的查找在这里使用while语句，逐个检查结点的num成员是否等于n，如果不等于n且指针域不等于NULL(不是最后结点),则后移一个结点，继续循环，如找到该结点则返回结点指针。第029课数据结构9数据结构//结点数据域不等于n并且结点指针域为空if(p->num!=n&&p->next==NULL)//结点没

5、有找到输出printf("Node%dhasnotbeenfound!",n)如果循环结束仍未找到该结点则输出“未找到”的提示信息。第029课数据结构9数据结构head=pb->next3）、删除一个结点a）、被删除结点是第一个结点。这种情况只需使head指向第二个结点即可第029课数据结构9数据结构pf->next=pb->nextb）、被删结点不是第一个结点，这种情况使被删结点的前一结点指向被删结点的后一结点即第029课数据结构9数据结构4）、插入一个结点a）、原表是空表，只需使head指向被插结点即可。如图：第02

6、9课数据结构9数据结构if(head==NULL){//指针指向头结点head=pi;//结点的指针域设为空pi->next=NULL;}代码实现如下：第029课数据结构9数据结构pi->next=pb;head=pi;例如：假设开始表中包含整数60，65，74和82，b）、被插结点值最小，应插入第一结点之前第029课数据结构9数据结构在表中插入50，则因为60是表中第一个比50大的结点，所以将50插入到表头位置：第029课数据结构9数据结构pi->next=pb;pf->next=pi；c）、在其它位置插入。这种情况下，

7、使插入位置的前一结点的指针域指向被插结点，使被插结点的指针域指向插入位置的后一结点。即为：第029课数据结构9数据结构例如：假设开始表中包含整数60，65，74和82，在表中加入元素70，则：第029课数据结构9数据结构pb->next=pi;pi->next=NULL;d）、在表末插入。这种情况下使原表末结点指针域指向被插结点，被插结点指针域置为NULL。即：第029课数据结构9数据结构例如：假设开始表中包含整数60，65，74和82，在表中加入元素90，则：第029课数据结构9数据结构栈（stack）是一种只允许在一端

8、进行插入和删除的线性表，它是一种操作受限的线性表。在表中只允许进行插入和删除的一端称为栈顶（top），另一端称为栈底(bottom)。9.2.1．栈的定义9.2堆栈的概念与使用第029课数据结构9数据结构栈的插入操作通常称为入栈或进栈(push)，而栈的删除操作则称为出栈或退栈(pop)。