数据结构课件 (特详细).ppt

《数据结构课件 (特详细).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、要求有三个人要被关进监狱三年，监狱长给他们三个一人一个要求。　　美国人爱抽雪茄，要了三箱雪茄。　　法国人最浪漫，要一个美丽的女子相伴。　　而犹太人说，他要一部与外界沟通的电话。　　三年过后，第一个冲出来的是美国人，嘴里鼻孔里塞满了雪茄，大喊道：“给我火，给我火！”原来他忘了要火了。　　接着出来的是法国人。只见他手里抱着一个小孩子，美丽女子手里牵着一个小孩子，肚子里还怀着第三个。　　最后出来的是犹太人，他紧紧握住监狱长的手说：“这三年来我每天与外界联系，我的生意不但没有停顿，反而增长了200％，为了表示感谢，我送你一辆劳施莱斯！”这个故事告诉我们，什么样的

2、选择决定什么样的生活。今天的生活是由三年前我们的选择决定的，而今天我们的抉择将决定我们三年后的生活。我们要选择接触最新的信息，了解最新的趋势，从而更好的创造自己的将来。1第1章绪论第2章线性表第3章栈和队列第4章串第5章数组和广义表第6章树和二叉树第7章图第9章查找第10章排序目录2课堂讨论：顺序表各种操作算法的“通式”该如何书写？———采用抽象数据类型来表示顺序表的存储结构是一维数组，如果插入的元素个数超过数组定义的长度怎么办？———采用动态分配的一维数组3动态数组简介先为顺序表空间设定一个初始分配量，一旦因插入元素而空间不足时，可为顺序表增加一个固定长度的空间增

3、量。#defineLIST_INIT_SIZE100//存储空间的初始分配量#defineLISTINCREMENT10//存储空间的分配增量Typedefstruct{ElemType*elem;//表基址(用指针*elem表示）intlength;//表长度（表中有多少个元素）intlistsize;//当前分配的表尺寸（字节单位）}SqList;注：三个分量可简写为：L.elemL.lengthL.listsize存储结构描述如下（见教材P22）：4sizeof(x)算符的意思是：计算变量x的长度(字节数)malloc(m)函数的意思是：新开一片大小为m字节的

4、连续空间，并把该区首址作为函数值。StatusInitList_Sq(SqList&L)//创建一个空线性表{L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));If(!L.elem)exit(OVERFLOW);//分配失败，结束程序L.length=0;//暂无元素放入，空表L.listsize=LIST_INIT_SIZE;//表尺寸=初始分配量ReturnOK;}//InitList_Sq动态创建一个空顺序表的算法：5realloc(*p,newsize)函数的意思是：新开一片大小为newsiz

5、e的连续空间，并把以*p为首址的原空间数据都拷贝进去。动态顺序表的插入算法StatusListInsert_Sq(SqList&L,inti,ElemTypee){//在顺序线性表中第i个位置之前插入新的元素eif(i<1ori>L.length+1)returnERROR;//检验i值的合法性if(L.length≥L.listsize)//若表长超过表尺寸则要增加尺寸{newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));if(newbase=NULL)exi

6、t(OVERFLOW);//分配失败则退出并报错L.elem=newbase;//重置新基址L.listsize=L.listsize+LISTINCREMENT;}//增加表尺寸6q=&L.elem[i-1];//q为插入位置。这是没有头结点的情况for(p=L.elem[L.length-1];p>=q;--p)*(p+1)=*p;//插入位置及之后的元素统统后移,p为元素位置*q=e;//插入e++L.length;//增加1个数据元素，则表长+1returnOK;}//ListInsert_Sq动态数组的核心是realloc(void*ptr,newsize

7、)函数！7动态顺序表的删除算法StatusListDelete_Sq(SqList&L,inti,ElemType&e){//在顺序表L中删除第i个元素，用e返回其值if(i<1ori>L.length)returnERROR;//i值不合法，返回p=&L.elem[i-1];//p是被删除元素的位置e=*p;//被删除元素的值赋给eq=L.elem+L.length-1;//q是表尾的位置for(++p;p<=q;p++)*(p-1)=*p;//待删元素后面的统统前移--L.length;//表长-1returnOK;}//ListDelete_Sq8链式存储