配套资源下载
第二章 线性表
2.1 应用实例
应用实例一 约瑟夫环问题(Josephus problem)
约瑟夫环问题是由古罗马的史学家约瑟夫提出的。问题描述为:编号为1,2.,n的n个人按顺时针方向围坐在一张圆桌周围,每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始报数,报到m时停止报数,报m的那个人出列,将其密码作为新的m值,并从其顺时针方向的下一个人开始重新从1报数,数到m的那个人又出列;如此下去,直至圆桌周围的人全部出列为止。这个游戏的实现只需将每个人的信息什 为一个结点,结点中存放每个人的编号和密码。由于要反复做删除操作,所以采用单向循环链表实现比较方便,详见本章2.6节。
应用实例二 一元多项式运算器
要实现一元多项式运算器,首先要设计表示一元多项式P=p0+p1x+p2x^2+…+pn x^n"的合适的 数据结构,并支持多项式的下列运算。
- 建立多项式。
- 输出多项式。
- +,两个多项式相加,建立并输出和多项式。
- -,两个多项式相减,建立并输出差多项式。
- *,多项式乘法。
- (),求多项式的值。
- derivative(),求多项式导数。
这个问题看起来很复张,但只要用本章将要学习的带头结点的单链表来存储多项式，头结点中存放多项式的参数(如项数等),问题就可以迎刃而解。详细的实现分析及算法见本章2.6节。
2.2 线性表的概念及运算
2.2.1线性表的逻辑结构
线性表是n(n>=0)个数据元素的有限序列。在表中，元素存在线性的逻辑关系：表中有且仅有一个开始结点;有且仅有一个终端结点；除开始结点外，表中的每个结点均只有一个前驱结点(predecessor);除终端结点外，表中的每个结点均只有一个后继结点(successor)。根据它们之间的关系可以排成一个线性序列,记作（a1,a2,…,an）
2.2.2 线性表的运算
基本操作
① InitList(L) 线性表初始化,构造一个空的线性表L。 ② ListLength(L) 求线性表的长度,返回线性表L中数据元素的个数 ③ GetElem(L,i,x) 用x返回线性表中的第i个数据元素的值。 ④ locaionElem(L,x) 按值查找,确定数据元素x在表中的位置。 ⑤ ListInsert(L,i,x) 插入操作,在线性表L中第i个位置之前插入一个新元素。L的长度加1。 ⑥ ListDelete(L,i) 删除操作,删除线性表L中的第i个元素,L的长度减1。 ⑦ ListEmpty(L) 判断线性表L是否为空,空表返回TRUE,非空表返回FALSE。 ⑧ ClearList(L) 将已知的线性表L置为空表。 ⑨ DestroyList(L) 销毁线性表L。
其他操作：合并、分拆、复制、排序等等。
2.3 线性表的顺序存储
2.3.1 顺序表
顺序存储是指在内存中用一块地址连续的存储空间按顺序存储线性表的各个数据元素。采用顺序存储结构 的线性表称为“顺序表”顺序表中逻辑上相邻的数据元素在物理存储位置上也是相邻的。
#define MAXSIZE <线性表可能达到的最大长度> typedef int ElemType; typedef struct { ElemType elem[MAXSIZE]; int length;//线性表长度 } SeqList;
2.3.2 顺序表的基本运算
相关代码请看配套资源
1-顺序表.c
int main(){ SeqList _L; SeqList *L=&_L; //初始化 Init(&_L); //创建 CreateList(L,4); Output(L); //插入 printf("在1处插入1\n"); Insert(L,1,1); printf("在2处插入2\n"); Insert(L,2,2); printf("插入之后"); Output(L); printf("表长:%d\n",ListLength(L)); //删除 printf("删除1\n"); ElemType d=-1; Delete(L,1,&d); printf("删除之后"); Output(L); //查询 printf("查询1\n"); ElemType x=1; int i=Location(L,x); printf("序号%d\n",i); printf("按索引i查询\n"); ElemType y; GetElem(L,i,&y); printf("值%d",y); }
运行结果如下
[例 2-1] 两个顺序表合并
有两个顺序表LA和LB，其元素均为非递减有序排列, 编写一个算法，将它们合并成一个顺序表LC，要求LC也是非递减有序排列。
算法思路:依次扫描A和B的元素，比较当前元素的值，将较小值的元素赋给C,如此直到一个线性表扫描完毕,然后将未外理完的顺序表的余下部分元麦连在表C的后面即可。表C的容量要能够容纳A、B两个线性表中的所有元素。
[算法2-5] 两个顺序表合并
void merge(SeqList* A, SeqList* B,SeqList* C) { int i,j,k; i=1;j=1;k=1; while (i<=A->length && j<= B->length) if (A->elem[i]<=B->elem[j]) C->elem[k++]=A->elem[i++]; else C->elem[k++]=B->elem[j++]; while (i<=A->length) C->elem[k++]=A->elem[i++]; while (j<=B->length) C->elem[k++]=B->elem[j++]; C->length=A->length+B->length; }
算法的时间复杂度是0(m+n),其中m是A的表长,n是B的表长。
2.4 线性表的链式存储
链式存储，通过“链”建立起数据元素之间的逻辑关系，这种用链接方式存储的线性表简称链表（link list）。
2.4.1 单链表
链表中的每一个结点都至少包括两个与，一个域存储数据元素信息，称为“数据域”；另一个域存储之间后继元素的地址，称为“指针域”。
结点定义如下：
typedef struct code { DataType data;//数据域 struct node * next;//指针域 }LNode，*LinkList;
n个元素的线性表通过每个结点的指针域连 接成了一条“链子”,故形象地称之为“链表”。因为每个结点中只有一个指向其直接后继的指针所以称其为单链表。
2.4.2 单链表基本运算
相关代码请看配套资源
2-单链表.c
void main(){ //建立 LinkList h=CreatByBear(); OutPut(h); //插入 printf("在1处插入1\n"); Insert(h,1,1); printf("在2处插入2\n"); Insert(h,2,2); printf("插入之后\n"); OutPut(h); //删除 printf("删除2\n"); Delete(h,2); printf("删除之后\n"); OutPut(h); //按序号查询 LNode *p; p=Get(h,1); printf("按序号查找到的信息如下：\n"); printf("%d\n",p->data); //按值查询 LNode *s; s=Locate(h,1); printf("按值查找到的信息如下：\n"); printf("%d\n",s->data); }
运行结果如下
[例]
有两个单链表LA和LB，其元素均为非递减有序排列, 编写一个算法，将它们合并成一个单链表LC，要求LC也是非递减有序排列。
要求:新表LC利用原表的存储空间。
[解]
LinkList MergeLinkList(LinkList LA,LinkList LB) { LNode *pa,*pb; LinkList LC; pa=LA->next; pb=LB->next LC=LA; LC->next=NULL; r=LC; while(pa&&pb) { if(pa->data<=pb->data) { r->next=pa; r=pa; pa=pa->next; } else { r->next=pb; r=pb; pb=pb->next; } if(pa) r->next=pa; else r->next=pb; free(LB); return(LC); }
