第8讲 基础数据结构与算法

《第8讲 基础数据结构与算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1程序设计语言C/C++第8讲基础数据结构与算法河海大学物联网工程学院2013年9月2教学目标理解数组和链表结构的特点和主要用途；掌握数组和链表结构的基本操作；熟练使用数组和链表结构解决实际问题。3本讲内容1数组基本操作2链表结构及其基本操作3查找和排序算法4几个常用算法4本讲内容1数组基本操作2链表结构及其基本操作3查找和排序算法4几个常用算法1数组基本操作1.1求数组的长度算法描述：①使用sizeof运算符求得数组占用内存大小；②使用sizeof运算符求得每个数组元素占用内存大小；③用数组的

2、内存大小/数组元素的内存大小。1数组基本操作1.2在数组中顺序查找一个指定值开始流程图：输入待查找的值m（假定数组名为a，数组长下标变量i置为0度为len）Ni

3、023214532447890232145324787890232145324789090无效了1数组基本操作1.5动态数组动态数组是指在程序执行过程中数组长度可以动态变化的数组。•结合new和delete运算符，用指针实现。•一般设置一个初始长度的数组；•数组中增加或减少一个元素一般用函数实现。10本讲内容1数组基本操作2链表结构及其基本操作3查找和排序算法4几个常用算法112链表结构及其基本操作2.1什么是链表链表是一种物理上非连续、非顺序的存储结构，数据的逻辑顺序通过链表中的指针链接次序

4、实现。122链表结构及其基本操作2.1什么是链表链表中的元素称为结点。每一个结点都包含两类数据：一类数据称为结点的值域；另一类数据称为链域，它是与结点同类型的指针。结点类型定义structnode{intdata;node*next;};node*p1,*p2;132链表结构及其基本操作2.1什么是链表结点数据的访问形式设指针p指向某结点，可用p访问该结点数据域：（*p).data或p->data指针域：（*p).next或p->next142链表结构及其基本操作2.2创建一条无序链表（1）

5、置头指针head=0;（2）输入一个数据，如果该数据有效，则转步骤（3），否则转步骤（5）；（3）申请分配一个结点空间，并把该空间的地址存入指针变量p中，然后把输入的数据存入该结点；（4）若当前链表为空，即head为0，则直接把p赋给head，否则接入链表末尾。转步骤（2）；（5）如果head不为0，则置尾结点的指针域为0；（6）返回头指针head的值，程序结束。152链表结构及其基本操作2.2遍历输出链表各节点值voidPrint(constnode*head){constnode*p;p=h

6、ead;while(p!=0){cout<data<<'t';p=p->next;}cout<

7、echain(node*head){node*p1;while(head){p1=head;head=head->next;deletep1;}}182链表结构及其基本操作2.2把一个节点插入升序链表node*Insert(node*head,node*p){node*p1,*p2;if(head==0){head=p;p->next=0;returnhead;}if(head->data>=p->data){p->next=head;head=p;returnhead;}p2=p1=head;

8、while(p2->next&&p2->datadata){p1=p2;p2=p2->next;}if(p2->datadata){p2->next=p;p->next=0;}else{p->next=p2;p1->next=p;}returnhead;}192链表结构及其基本操作2.2建立一条有序链表node*Create_sort(void){node*p1,*head=NULL;inta;cout<<“产生一条有序链表，输入数据，以-1结束：";cin>>a;while