计算机软件基础(自考本科)(1.8).ppt

《计算机软件基础(自考本科)(1.8).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机软件基础第二篇　数据结构基础第八章线性表（linearlist）一、线性表的概念1.线性表的逻辑结构（1）线性表：是由n（n≥0）个数据节点a0，a1,…，an-1组成的有限序列。（2）线性表的逻辑结构特征：①对于非空线性表：有且仅有一个开始节点，该节点有且仅有一个直接的后继；有且只有一个终结节点，该节点有且仅有一个直接的前驱；其余内部节点有且仅有一个直接前驱和一个直接后继。一、线性表的概念（2）线性表的逻辑结构特征：②同一个线性表中的数据节点具有相同的属性。③线性表长度：线性表中数据节点的个数。2.线性表的存储结构（1）顺序存储结构：顺序表结构

2、；（2）链式存储结构：链表结构；二、顺序表1.顺序表（1）顺序表：把线性表中的数据节点按其逻辑顺序依次存放到计算机内存中的一连续空间中，将这一连续空间称为顺序表。（2）顺序表中数据节点地址的计算Loc(ai)=loc(a0)+i*d(0≤i≤n-1)二、顺序表1.顺序表（3）顺序表C语言描述：structsequenlist{datatypea[listsize];//表示线性表有（a0，a1，...，an-1）intlength;//length表示线性表的实际长度};二、顺序表2.顺序表的基本运算——查找structsequenlist/*构建se

3、quenlist型*/{datatypedata[listsize];intlength;};structsequenlistL;/*定义sequenlist变量L*/intfind(structsequenlistL,datatypex)/*定义find函数*/{inti=0;while(i#

4、definelistsize50structsequenlist/*构建sequenlist型*/{intdata[listsize];intlength;};structsequenlistL;/*定义sequenlist变量L*/intfind(structsequenlistL,intx)/*定义find函数*/{inti=0;while(i

5、uctsequenlista;scanf("%d",&a.length);/*输入实际表长*/scanf("%d",&j);/*输入要查找的数据*/for(i=0;i

6、运算——插入step1:判断表是否满？如果已满，则输出“表满”；否则进行第二步；step2:判断要插入的位置是否在表内？如果不在，则输出“位置不对”；否则进行第三步；step3:从第n-1个节点到第i个节点全部后移1位；step5:将顺序表的表长加1；step4:在顺序表的第i个位置插入x；二、顺序表插入运算的类C语言算法：voidinsert(structsequenlistL,datatypex,inti)/*定义insert函数*/{intj;if(L.length>=listsze)printf("overflow");elseif((i<

7、0)

8、

9、(i>L.length))printf("positionisnocorrect");else{for(j=L.length-1;j>=i;j--){L.data[j+1]=L.data[j];}L.data[i]=x;L.length++;}}二、顺序表一个完整的插入运算程序#include#definelistsze10structsequenlist/*构建sequenlist型*/{intdata[listsze];intlength;};structsequenlistL;二、顺序表一个完整的插入运算程序（续）v

10、oidinsert(structsequenlistL,intx,inti)/*定义inser