数据结构知识点(5)

}

p=polya->next; q=polyb->next; tail=polya;

while(p!=NULL&&q!=NULL) { if(p->expexp) { tail->next=p; tail=p; p=p->next; } else if(p->exp==q->exp) { sum=p->coef+q->coef; if(sum==0) { temp=p;p=p->next;free(p); temp=q;q=q->next;free(q); } else { p->coef=sum; tail->next=p; tail=p; p=p->next; temp=q; q=q->next; free(temp); } } else { tail->next=q; tail=q; q=q->next; } }

if(p!=NULL) tail->next=p; else tail->next=q; return polya;

假设A多项式有M项，B多项式有N项，则上述算法的时间复杂度为O(M?N)。

2.5 顺序表和链表的综合比较

2.5.1 顺序表和链表的比较

(课本P66~P67)

2.5.2 线性表链式存储方式的比较

2.6 总结与提高

2.6.1主要知识点 线性表的特征

线性表中每个数据元素有且仅有一个直接前驱和直接后继，第一个结点无前驱，最后一个结点无后继。 线性表的存储方式

线性表在计算机中的存储方式有顺序存储和链式存储。 线性表的顺序存储(顺序表)：采用静态分配方式，借助于C语言的数组类型，申请一组连续的地址空间，依次存放表中元素，其逻辑次序隐含在存储顺序中。

线性表的链式存储(链表)：采用动态分配方式，借助于C语言的指针类型，动态申请与动态释放地址空间，故链表中的各结点的物理存储可以是不连续的。 单链表的操作特点

（1）顺链操作技术：从“头”开始，访问单链表L中结点i(p指向该结点)时，由于第i个结点的地址在第i-1个结点(pre指向该结点，为p的前驱)的指针域中存放，查找必须从单链表的“首结点”开始(p=L);通过p=p->next并辅助计数器来实现。

（2）指针保留技术：通过对第i个结点进行插入、删除等操作时，需要对第i-1个结点的指针域进行链址操作(pre->next)，因此在处理过程中始终需要维持当前指针p与其前驱指针pre的关系，将这种技术简称为“指针保留技术”。 链表处理中的相关技术

（1）单链表与多重链表的差别在于指针域的个数。

（2）一般链表与循环链表的差别在于是否首尾相接，将非空表、空表等多种情况统一处理，以方便运算。

（3）判断当前结点p是否是表尾。一般链表中，p结点是表尾结点的条件是：该结点的后继指针值为空指针，即p->next==NULL;循环链表中，p结点是表尾结点的条件是：该结点的后继指针值为头指针值，即p->next==head.

（4）链表的表长度并未显示保存。由于链表是动态生成的结构，其长度要通过顺链查找到表尾得到。因此在处理链表时，往往是以当前处理位置是否是表尾作为控制条件，而不是以表长度n作为控制条件。

2.6.2 典型例题

例1：分解顺序表为奇偶两部分

已知顺序表L中的数据元素类型为int。设计算法将其调整为左右两部分，左边的元素(即排在前面的)均为奇数，右边的所有元素(即

排在后面的)均为偶数，并要求算法的时间复杂度为O(n),空间复杂度为O(1). 问题分析：

将位于表尾左半部分的偶数与位于表右半部分的奇数通过一个辅助变量进行交换。

设置两个位置指示器i和j，i的初值为0，j的初值为L->last. 当L->elem[i]为偶数，L->elem[j]为奇数是，则将L->elem[i]与L->elem[j]交换

否则，L->elem[i]为奇数，i++，L->elem[j]为偶数，j--。 这样既可以保证算法时间复杂度为0（n），亦可以保证空间复杂度为0（1）。 算法：

#define MaxSize 100 typedef struct {

int elem[MaxSize];

int last;/*记录线性表中最后一个元素在数组elem[]中的位置(下标值)*/ }SeqList;

void AdjustSqlilst(SeqList *L) {

int i=0,j=L->last,t; while(ielem[i]%2!=0&&ielem[j]%2==0&&ielem[i]; L->elem[i]=L->elem[j]; L->elem[j]=t; } } }