线性表第二章

2.8已知由单链表表示的线性表中，含有三类字符的数据元素( 2.8已知由单链表表示的线性表中，含有三类字符的数据元素(如：字母字符、数字字符 已知由单链表表示的线性表中，含有三类字符的数据元素 和其它字符) 和其它字符)，试编写算法构造三个以循环链表表示的线性表，使每个表中只含同一类 的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。
2.8 已知由单链表表示的线性表中，含有三类 字符的数据元素( 字符的数据元素(如：字母字符、数字字符和 其它字符) 其它字符)，试编写算法构造三个以循环链表 表示的线性表，使每个表中只含同一类的字 符，且利用原表中的结点空间作为这三个表 的结点空间，头结点可另辟空间。 2.9 假设在长度大于1的单循环链表中，既无 假设在长度大于1 头结点也无头指针。s 头结点也无头指针。s为指向链表中某个结 点的指针，试编写算法删除结点* 点的指针，试编写算法删除结点*s的直接前 趋结点。 2.10设顺序表L 2.10设顺序表L是一个递增有序表，试写一算 法，将x插入L中，并使L 法，将x插入L中，并使L仍是一个有序表。
Status locatenode(dullinklist &L,elemtype x) {dulnode *p,*q; p=q=Lp=q=L->next; while(p) (pp=p{if (p->data!=x) p=p->next; else {p->freq++; break;} } {pwhile(q) {if(q->freq>pq=q{if(q->freq>p->freq) q=q->next; {p->prior->next=pp->next->prior=pelse {p->prior->next=p->next; p->next->prior=p->prior; p->prior=qp->next=q; p->prior=q->prior; q->prior->next=p; q->prior=p} >priorq} return ok; }

}
4.判线性表是否为空表ListEmpty(L)
若单链表L没有数据结点,则返回1,否则返回0。
int ListEmpty(LinkList *L)
{
return(L->next==NULL); }
5.求线性表的长度ListLength(L)
返回单链表L中数据结点的个数。
int ListLength(LinkList *L) { LinkList *p=L->next;int i=0; while (p!=NULL)
第三步：尾插法链接结点
r->next=s; r=s;
• 再循环23步骤直到n个结点完成插入
r
L
s
r
头结点
a
void CreateListR(LinkList *L,ElemType a[],int n) { LinkList *s,*r;int i; r=L; for (i=0;i<n;i++) { s=(LinkList *)malloc(sizeof(LinkList)); /*创建新结点*/ s->data=a[i]; r->next=s; /*将*s插入*r之后*/ r=s; } r->next=NULL; /*终端结点next域置为NULL*/ }
存储结点包含 数据域：所有存元素本身的信息；
指针域：元素之间逻辑关系的信息；包含有后 继结点的地址信息。
2个问题 如何构造链表数据类型？ 链表上可进行什么基本操作？
解决第一个问题---如何构造链表数据类型
在每个结点中除包含有数据域外,只设置一个指针域, 用以指向其后继结点,这样构成的链接表称为线性单 向链接表,简称单链表；
{ s=(LinkList *)malloc(sizeof(LinkList));

第二章线性表一、描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。

并说明头指针和头结点的作用。

答：头指针是一个指针变量，里面存放的是链表中首结点的地址，并以此来标识一个链表。

如链表H，链表L等，表示链表中第一个结点的地址存放在H、L中。

头结点是附加在第一个元素结点之前的一个结点，头指针指向头结点。

当该链表表示一个非空的线性表时，头结点的指针域指向第一个元素结点，为空表时，该指针域为空。

开始结点指第一个元素结点。

头指针的作用是用来惟一标识一个单链表。

头结点的作用有两个：一是使得对空表和非空表的处理得以统一。

二是使得在链表的第一个位置上的操作和在其他位置上的操作一致，无需特殊处理。

二、填空题1、在顺序表中插入或删除一个元素，需要平均移动（表中一半）元素，具体移动的元素个数与（表长和该元素在表中的位置）有关。

2、顺序表中逻辑上相邻的元素的物理位置（必定）相邻。

单链表中逻辑上相邻的元素的物理位置（不一定）相邻。

3、在单链表中，除了首元结点外，任一结点的存储位置由（其直接前驱结点的链域的值）指示。

4、在单链表中设置头结点的作用是（插入和删除元素不必进行特殊处理）。

三、何时选用顺序表、何时选用链表作为线性表的存储结构为宜?答：在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以下几方面的考虑：1.基于空间的考虑。

当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。

2.基于时间的考虑。

若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之，若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。

并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。

十一、设顺序表中的数据元素递增有序，试写一算法，将X插入到顺序表的适当位置上，以保持该表的有序性。

【例2】巳知有两个按元素值递增有序的顺序表La和 Lb，设计一个算法将表La和表Lb的全部元素归并 为一个按元素值递增有序的顺序表Lc。

算法思路：用i扫描顺序表La，用j扫描顺序表Lb。 当表La和表Lb都未扫描完时，比较两者的当前元 素，将较小者插入表Lc的表尾，若两者的当前元 素相等，则将这两个元素依次插入表Lc的表尾。 最后，将尚为扫描完的顺序表的余下部分元素依 次插入表Lc的表尾。算法如下： void MergeList_Sq(SqList La, SqList Lb, SqList &Lc)

表中ai-1领先于ai，称ai-1是ai的直接前驱，ai+1是 ai的直接后继。

线性表的抽象数据类型定义 （参见教材）
返回本章目录
2.2 线性表的顺序存储结构

线性表的顺序存储是指在内存中用地址连续的一块存储空间 依次存放线性表的数据元素，用这种存储形式存储的线性表 称其为顺序表。 假设每个数据元素占d个存储单元，且将ai的存储地址表示为 Loc(ai)，则有如下关系： Loc(ai)=Loc(a1)+(i-1)*d Loc(a1)是线性表的第一个数据元素a1的存储地址，通常 称作线性表的基地址。

【例1】 编写一算法，从顺序表中删除自第i个元素开 始的k个元素。 算法思路： 为保持顺序表的逻辑特性，需将i+k ~ n位 置的所有元素依次前移k个位置。算法如下：

int deleteK(Sqlist &sq,int i,int k)
{ if (i<1||k<1||i+k-1>sq.len) return 0; for (j=i+k-1;j<=sq.len-1;j++) sq.data[j-k]=sq.data[j]; sq.len-=k; return 1; }// deleteK