数据结构知识点总结

设 a1的存储地址为Loc(a1),每个数据元素占d个存储地址,则第i个数据元素的地址为:

Loc(ai)=Loc(a1)+(i-1)*d 1≤I≤n 顺序表插入运算时间主要消耗:数据的移动。

一般情况下,在第i(1<=i<=n)个元素之前插入一个元素时,需将第n至第i(共n-i+1)个元素向后移动一个位置。 (在第i个位置上插入 x ,从 ai 到 an 都要向下移动一个位置,共需要移动 n-i+1个元素。)

一般情况下,删除第i(1<=i<=n)个元素时,需从第i+1至第n(共n-i)个元素向前移动一个位置

i 的取值范围为 :1≤ i≤ n+1(即有 n+1个位置可以插入)。 设在第i个位置上作插入的概率为Pi: Ein??pi(n?i?1)i?1n?1在等概率情况下:

P=1/ (n+1) ,则平均移动数据元素的次数则为:E in ?i

?n?1i?11pi(n?i?1)?n?1?n?1(n?i?1)?i?1n2这说明:在顺序表上做插入操作需移动表中一半的数据元素。 显然顺序表上插入时间复杂度为O(n)。 int SeqlistInsert(A[],n,i,x) {

if(i<1 || i>n) //检查插入位置的正确性 {

Printf(“参数非法”);

return 0; //插入位置参数错,返回错误代码0 }

else {

for(k=n;k>=i;k--)

A[k-1]<=A[k]; //结点移动 A[i]<=x; //新元素插入

n<=n+1; // n指向新的最后元素

return n; //插入成功,返回成功代码 } }

线性表的删除运算是指将表中第 i 个元素从线性表中去掉。 SeqlistDelete(A[],n,i) {

if(i<1 OR i>n) //检查空表及删除位置的合法性 {

Printf(“参数非法”);

return 0; //不存在第i个元素,返回错误代码0 } else {

for(k=i+1;k

A[k-1]<=A[k]; //数据元素向前移动 n<=n -1; // n指向新的最后元素

return n; //删除成功,返回成功代码 }

删除算法的时间性能分析

与插入运算相同,其时间主要消耗在了移动元素上。

计算数据移动的次数:某次删除数据的移动次数与具体位置有关。求平均性能。 删除第i个元素时,其后面的元素 ai+1~an 都要向上移动一个位置,共移动了 n-i 个元素。

i 的取值范围为 :1≤ i≤ n(即有 n个位置可以删除)。 设在第i个位置上作删除的概率为Pi,平均移动数据元素的次数: 在等概率情况下:Pi=1/ n ,则平均移动数据元素的次数则为:

Ede??npi(n?i)i?11nn?1Ede???pi(n?i)??(n?i)?ni?12i?1n这说明顺序表上作删除运算时大约需要移动表中一半的元素。 显然该算法的时间复杂度为O(n)。

线性表链式存储结构,不要求逻辑上相邻的两个数据元素物理上也相邻,因此不需要用地址连续的存储单元来实现。

链表是通过一组任意的存储单元来存储线性表中的数据元素的,对每个数据元素ai,除了存放数据元素的自身的信息 ai 之外,还需要和ai一起存放其后继 ai+1 所在的存贮单元的地址,这两部分信息组成一个“结点”。

存放数据元素信息的称为数据域,存放其后继地址的称为指针域。

链表的表示:

链表是由一个个结点构成的。

结点的申请:p=new LNode; 结点的释放:delete p;

在某结点后面插入新结点:设p指向单链表中某结点,s指向待插入的值为x的新结点,将*s插入到*p的后面。 操作如下:

①s->next=p->next; ②p->next=s;

注意:两个指针的操作顺序不能交换。 在某结点前面插入新结点:

设p指向链表中某结点,s指向待插入的值为x的新结点,将*s插入到*p的前面。与后插不同的是:首先要找到*p的前驱*q,然后再完成在*q之后插入*s。

设单链表头指针为L,操作如下: q=L;

while (q->next!=p)

q=q->next; //找*p的直接前驱 s->next=q->next; q->next=s;

删除结点:设p指向单链表中某结点,删除*p。

作业1:线性表中元素为整型,以50为界,小于50在左,大于50在右。 作业讲解:x<=A[i];

while(A[j]>=x and i

联系客服:779662525#qq.com(#替换为@)