数据结构 第二章 线性表.

Presentation on theme: "数据结构 第二章 线性表."— Presentation transcript:

1 数据结构 第二章 线性表

2 本章内容 2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 一元多项式的表示及相加

3 线性结构分类 直接访问型( direct access ) 顺序访问型(sequential access)
目录索引型(directory access) 2-3

4 线性结构分类 2-4

5 2.1 线性表的逻辑结构 性质：线性表（N , r）： 线性表所包含的结点个数称为线性表的长度，长度为0的线性表称为空表；
定义：线性表(Linear List)是由n个数据元素的有限序列组成。其中数据元素的个数n 定义为表的长度。当 n=0 时称为空表，常常将非空的线性表(n>0)记作： (a1，a2，…an) 这里的数据元素ai(1≤i≤n)只是一个抽象的符号，其具体含义在不同的情况下可以不同。 性质：线性表（N , r）： 结点集N中有唯一的开始结点，它没有前驱，但有唯一的后继； 有限集N它存在唯一的终止结点，该结点有唯一的前驱而没有后继； 其它的结点皆称为内部结点，每一个内部结点既有一个唯一的前驱，也有一个唯一的后继； 线性表所包含的结点个数称为线性表的长度，长度为0的线性表称为空表； 线性表的关系r，简称前驱关系，应具有反对称性和传递性。 2-5

6 2.1 线性表的逻辑结构 例1、26个英文字母组成的字母表 (A，B，C、…、Z) 是一个线性表，其中的元素是单个字母字符。
例2、某校从1978年到1983年各种型号的计算机拥有量的变化情况，可以用线性表的形式给出： （6，17，28，50，92，188） 更为复杂的线性表中，一个数据元素可以有若干个数据项(item)组成。在这种情况下，长把数据元素称为记录(record)，含有大量记录的线性表又称为文件(file)。 2-6

7 2.1 线性表的逻辑结构 例3、学生健康情况登记表如下表。表中每一个学生的情况为一个记录，它由姓名、学号、性别、年龄和班级等5个数据项组成。
王小林 790631 男 18 计算机08 陈红 790632 女 20 刘建平 790633 21 张立立 790634 17 …… 2-7

8 2.1 线性表的逻辑结构 以上几个例子都是线性表的例子，都满足线性表的性质。 线性表是一种典型的线性结构。
数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。 抽象数据类型的定义为：P19 2-8

9 线性表类模板 template<class ELEM> class list //线性表类模板list，模板参数ELEM
{ //1. 线性表的取值类型： //元素的类型为ELEM，是本list类模板的模板参数ELEM。 //本线性表用的最大长度为Max_length； //2. 名字空间，使用变量访问线性表的方法： //用curr ++或 curr--控制线性表游标curr的前后游走。 //用公共变量curr_len指示线性表的尾部， //并导出表的当前长度，…等。 // 3. 运算集：请参看下面的成员函数 private: //私有变量，线性表的存储空间 //Max_length线性表的最大长度 public: int curr_len; //线性表的当前长度 int curr; //线性表的当前指针 list(); // 创建一个空的新线性表 ~list(); //从计算机存储空间删去整个线性表 //将该线性表的全部元素清除，成为空表 void clear() ; // 尾附算子，在表的尾部添加一个新元素，参 //数value作为元素内容（数据类型为 //ELEM），表的长度加1 void append(ELEM value) ; //插入算子，整数i指出第i号位置，参数value //作为元素内容（数据类型为T），该位置上 //插入一个新结点，表的长度加1。第i号位置后 //的元素后移 void insert(int i, ELEM value) ; //删除算子，删去第i号元素，表的长度减1，其后元素前移 void remove(int i); //读取，返回第i个元素的值 ELEM fetch(int i); } 2-9

10 2.1 线性表的逻辑结构 算法2.1 例2-1 利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A=A∪B。
[合并线性表] 对于LB中的每一个元素x做如下操作： 若(x不属于LA） 则将x插入到LA的末尾 [算法结束] void union(List &La，List Lb) { La_len = Listlength(La); Lb_len = Listlength(Lb); for (i=1;i<=Lb_len;i++) { GetElem(Lb，i，e); if (!LocateElem(La，e，equal)) ListInsert(La，++La_len，e); } 2-10

11 2.1 线性表的逻辑结构 算法2.2 例2-2 巳知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。 此问题的算法： [初值] 获取线性表LA和LB，并构造空线性表LC [选择插入元素] 对于线性表LA和LB，都从其第一个元素开始做如下操作直到其中一个线性表元素全部遍历完毕： 若 （LA的元素a<=LB的元素b） 则 将元素a插入到LC的末尾，并选择LA中的下一个元素a 否则 将元素b插入到LC的末尾，并选择LB中的下一个元素b [补充剩下的元素] 若 （LA还有剩余元素） 则 将LA的剩余元素全部插入到LC末尾 若 （LB还有剩余元素） 则 将LB的剩余元素全部插入到LC末尾 [算法结束] 2-11

12 2.1 线性表的逻辑结构 void MergeList(List La, List Lb, List &Lc){ InitList(Lc);
i=j=1;k=0; La_len=ListLength(La); Lb_len=ListLength(Lb); while ( (i<=La_len) && (j<=Lb_len) ) { GetElem(La, i, ai); GetElem(Lb, j, bj); if (ai<=bj) { ListInsert(Lc, ++k, ai);++i; } else { ListInsert (Lc, ++k, bj); ++j; } } while (i<=La_len) { //若（LA还有剩余元素）则 将LA的剩余元素全部插入到LC末尾 GetElem(La, i++, ai); ListInsert(Lc, ++k, ai); while (j<=Lb_len) { //若 （LB还有剩余元素） 则 将LB的剩余元素全部插入到LC末尾 GetElem(Lb, j++, bj); ListInsert(Lc, ++k, bj); 2-12

13 算法复杂性分析 算法2.1 外重循环为ListLength(LB)
循环内语句LocateElem()的时间复杂度为O(ListLength(LA)) 总为O(ListLength(LA)*ListLength(LB)) 算法2.2 根据算法的执行过程，算法访问LA和LB的每个元素有仅只有一次 O(ListLength(LA)+ListLength(LB)) 2-13

14 2.2 线性表的顺序存储结构 线性表 把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。 假设线性表的每个元素需占用l个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第I+1个数据元素的存储位置LOC( a i+1)和第i个数据元素的存储位置LOC(ai)之间满足下列关系： LOC(a i+1)=LOC(a i)+l 线性表的第i个数据元素ai的存储位置为： LOC(ai)=LOC(a1)+(i-1)*l 2-14

15 2.2 线性表的顺序存储结构 由于C语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表。又因为顺序表还应该用一个变量来表示线性表的长度属性，所以我们用结构类型来定义顺序表类型。 #define LIST_INIT_SIZE 100 //初始分配量 #define LISTINCREMENT 10　//分配增量 typedef int ElemType; typedef struct{ ElemType *elem; //基址 int length; //当前长度 int listsize; //当前分配的存储容量 } Sqlist; 2-15

16 2.2 线性表的顺序存储结构 初始化操作： Status InitList_Sq(Sqlist &L){ L.elem =
2.2 线性表的顺序存储结构 初始化操作： Status InitList_Sq(Sqlist &L){ L.elem = (ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if (!L.elem) exit(OVERFLOW); L.length=0; L.listsize=LIST_INIT_SIZE; return OK; } 2-16

17 2.2 线性表的顺序存储结构 2.2.2 顺序表上实现的基本操作
2.2 线性表的顺序存储结构 顺序表上实现的基本操作 在顺序表存储结构中，很容易实现线性表的一些操作，如线性表的构造、第i个元素的访问。 注意：C语言中的数组下标从“0”开始，因此，若L是Sqlist类型的顺序表，则表中第i个元素是L.elem[i-1]。 以下主要讨论线性表的插入和删除两种运算。 1、插入 线性表的插入运算是指在表的第i(1≦i≦n+1个位置上，插入一个新结点x，使长度为n的线性表 (a1, …a i-1, ai,, …，an) 变成长度为n+1的线性表 (a1, …a i-1, x，ai, … , an) 见P23图2.3 2-17

18 2.2 线性表的顺序存储结构 [初值] 获取线性表L，插入位置i，插入元素e [检查参数] 若 （插入位置超出线性表长度范围） 则 输出错误
2.2 线性表的顺序存储结构 [初值] 获取线性表L，插入位置i，插入元素e [检查参数] 若 （插入位置超出线性表长度范围） 则 输出错误 [检查空间] 若 （线性表空间不足） 则 分配新空间 若 （分配成功） 则 修改线性表的容量 否则 输出溢出错误 [插入元素] 将插入位置 i 以及其后的 L 中的元素全部后移一格 将元素e插入位置I, 线性表长度增加1 [算法结束] 2-18

19 2.2 线性表的顺序存储结构 算法的复杂度分析 这里的问题规模是表的长度，设它的值为n。该算法的时间主要花费在循环的结点后移语句上，该语句的执行次数（即移动结点的次数）是n-i+1。由此可看出，所需移动结点的次数不仅依赖于表的长度，而且还与插入位置有关。 当i=n+1时，由于循环变量的终值大于初值，结点后移语句将不进行；这是最好情况，其时间复杂度O(1)； 当i=1时，结点后移语句将循环执行n次，需移动表中所有结点，这是最坏情况，其时间复杂度为O（n）。 2-19

20 2.2 线性表的顺序存储结构 由于插入可能在表中任何位置上进行，因此需分析算法的平均复杂度。在长度为n的线性表中第i个位置上插入一个结点，令Eis(n)表示移动结点的期望值（即移动的平均次数），设pi是在第i个位置插入元素的概率，则在第i个位置上插入一个结点的移动次数为n-i+1。故 不失一般性，假设在表中任何位置(1≦i≦n+1)上插入结点的机会是均等的，则 p1=p2=p3=…=p n+1=1/(n+1) 因此，在等概率插入的情况下， 2-20

21 2.2 线性表的顺序存储结构 也就是说，在顺序表上做插入运算，平均要移动表上一半结点。当表长 n较大时，算法的效率相当低。虽然Eis(n)中n的系数较小，但就数量级而言，它仍然是线性阶的。因此算法的平均时间复杂度为O(n)。 2-21

22 2.2 线性表的顺序存储结构 [初值] 获取线性表L，删除位置i； [检查参数] 若 （删除位置超出线性表长度范围） 则 输出错误
2.2 线性表的顺序存储结构 2、删除 线性表的删除运算是指将表的第i(1≦i≦n)结点删除，使长度为n的线性表： (a1，…a i-1，ai，a i+1…，an) 变成长度为n-1的线性表 (a1，…a i-1，a i+1，…，an) [初值] 获取线性表L，删除位置i； [检查参数] 若 （删除位置超出线性表长度范围） 则 输出错误 [删除元素] 获取删除位置i的元素e 将删除位置i之后的L中的元素全部前移一格 线性表长度减1 [算法结束] 2-22

23 2.2 线性表的顺序存储结构 该算法的时间分析与插入算法相似，结点的移动次数也是由表长n 和位置i决定。
2.2 线性表的顺序存储结构 该算法的时间分析与插入算法相似，结点的移动次数也是由表长n 和位置i决定。 若i=n，则由于循环变量的初值大于终值，前移语句将不执行，无需移动结点； 若i=1，则前移语句将循环执行n-1次，需移动表中除开始结点外的所有结点。这两种情况下算法的时间复杂度分别为O(1)和O(n)。 删除算法的平均性能分析与插入算法相似。在长度为n的线性表中删除一个结点，令Ede(n)表示所需移动结点的平均次数，删除表中第i个结点的移动次数为n-i，故 式中，qi表示删除表中第i个结点的概率。 2-23

24 2.2 线性表的顺序存储结构 在等概率的假设下， p1=p2=p3=…=pn=1/n 由此可得：
2.2 线性表的顺序存储结构 在等概率的假设下， p1=p2=p3=…=pn=1/n 由此可得： 即在顺序表上做删除运算，平均要移动表中约一半的结点，平均时间复杂度也是O(n)。 2-24

25 2.3 线性表的链式表示和实现 线性表的顺序表示的特点是用物理位置上的邻接关系来表示结点间的逻辑关系，这一特点使我们可以随机存取表中的任一结点，但它也使得插入和删除操作会移动大量的结点.为避免大量结点的移动，我们介绍线性表的另一种存储方式，链式存储结构，简称为链表(Linked List)。 线性链表 链表是指用一组任意的存储单元来依次存放线性表的结点，这组存储单元即可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。因此，链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息，这个信息称为指针(pointer)或链(link)。这两部分组成了链表中的结点结构： 2-25

26 2.3 线性表的链式表示和实现 data next 其中:data域是数据域，用来存放结点的值； next是指针域，用来存放结点的直接后继的地址（或位置）。 链表正是通过每个结点的链域将线性表的n个结点按其逻辑次序链接在一起。由于上述链表的每一个结只有一个链域，故将这种链表称为单链表（Single Linked)，或线性链表。 显然，单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。同时，由于 终端结点无后继，故终端结点的指针域为空，即null（图示中也可用^表示)。 例1、线性表:(bat，cat，eat，fat，hat，jat，lat，mat) 2-26

27 单链表示意图如下： 165 …… lat jat 110 fat bat mat eat 135 cat ……. 200 hat 130
160 165 170 205 头指针 165

28 bat cat eat mat ^ … Head 单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。
例如：若头指针名是head，则把链表称为表head。 用C语言描述的单链表如下： typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList;

29 2.3 线性表的链式表示和实现 LNode *p; LinkList head;
注意区分指针变量和结点变量这两个不同的概念。指针变量P（其值为结点地址）和结点变量*P之间的关系。P为动态变量，它是通过标准函数生成的，即 p=(LNode*)malloc(sizeof(LNode)); 函数malloc分配了一个类型为LNode的结点变量的空间，并将其首地址放入指针变量p中。一旦p所指的结点变量不再需要了，又可通过标准函数 free(p) 释放所指的结点变量空间。 2-29

30 2.3 线性表的链式表示和实现 在这样的结构里，第一个结点，有别于其他结点，它的生成与删除都要进行特殊的处理。有时，我们在单链表的第一个结点之前附设一个结点，称之为头结点，那么会带来以下两个优点： 由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就和在表的其它位置上的操作一致，无需进行特殊处理； 无论链表是否为空，其头指针是指向头结点 的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就统一了。 头结点的数据域可以不存储任何信息，也可以存放线性表的长度信息。 2-30

31 2.3 线性表的链式表示和实现 查找运算 在链表中，即使知道被访问结点的序号i，也不能象顺序表中那样直接按序号i访问结点，而只能从链表的头指针出发，顺链域next逐个结点往下搜索，直到搜索到第i个结点为止。因此，链表不是随机存取结构。 设单链表的长度为n，要查找表中第i个结点，仅当1≦i≦n时，i的值是合法的。但有时需要找头结点的位置，故我们将头结点看做是第0 个结点。 2-31

32 2.3 线性表的链式表示和实现 算法2.8的基本操作是比较j和i并后移指针，while循环体中的语句频度与被查元素在表中位置有关，若1<=i<=n，则频度为i-1，否则频度为n，因此该操作的时间复杂度为O(n)。 Status GetElem_L(LinkList L , int i, ElemType &e) { p=L->next; j=1; while(p && j<i) p=p–>next; j++; } if (!p || j> i) return ERROR; e= p->data; return OK; 2-32

33 2.3 线性表的链式表示和实现 插入运算 插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，我们必须首先找到ai-1的存储位置，然后生成一个数据域为x的新结点s，并令新结点s的指针域指向结点ai ，结点　ai-1的指针域指向新结点s。从而实现三个结点ai-1，s和ai之间的逻辑关系的变化。具体算法如下: Status ListInsert _L(LinkList &L, int i, ElemType e) { p=L; j=0; while (p && j<i-1) { p=p->next; ++j; } if (!p||j>i-1) return ERROR; s=(LinkList)malloc(sizeof(LNode)); s–>data=e; s–>next=p–>next; p–>next=s; return OK; } 2-33

34 2.3 线性表的链式表示和实现 设链表的长度为n，合法的插入位置是1≦i≦n+1。注意当i=1时，找到的是头结点，当i=n+1时，找到的是结点an。算法的时间主要耗费在查找操作while语句上，故时间复杂度为O(n)。 2-34

35 2.3 线性表的链式表示和实现 删除运算 删除运算是将表的第i个结点删去。因为在单链表中结点ai的存储地址是在其直接前趋结点a i-1的指针域next中，所以我们必须首先找到a i-1的存储位置p。然后令p–>next指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间，将其归还给“存储池”。此过程见书P30算法2.10。具体算法如下： Status ListDelete_L(LinkList &L, int i, ElemType &e) { p=L; j=0; while ((p->next) && j< i-1 ) { p=p->next; ++j; } if( !( p–>next) || j> i-1) return ERROR; q=p–>next; p–>next=q–>next; e=q->data; free( q ) ; return OK; } 2-35

36 2.3 线性表的链式表示和实现 设单链表的长度为n，则删去第i个结点仅当1≦i≦n时是合法的。注意，p是指向待删结点的前一个结点。当i=n+1时，虽然被删结点不存在，但其前趋结点却存在，它是终端结点。因此被删结点的直接前趋*p存在并不意味着被删结点就一定存在，仅当　　　（p–>next!=NULL）时，才能确定待删结点存在。 显然，此算法的时间复杂度也是O(n)。 从上面的讨论可以看出，链表上实现插入和删除运算，无须移动结点，仅需修改指针。 2-36

37 2.3 线性表的链式表示和实现 建立单链表 动态地建立单链表的常用方法有如下几种： 1、头插法建表（无头结点）
该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。 Status CreateList(LinkList ＆L) //输入创建线性链表 { char ch; LNode *p; L=NULL; ch=getchar( ); while (ch!=‵\n′) { p=(LNode*)malloc(sizeof(LNode)); p–>data=ch; p–>next=L; L=p; ch=getchar( ); } return OK; 2-37

38 2.3 线性表的链式表示和实现 Status CreateList(ListLink ＆L, int n) //创建n个元素的线性链表 {
LNode *p; L=NULL; for (i=n; i>0; --i ) { p=(LNode*)malloc(sizeof(LNode)); scanf(“%d”，&p–>data); p–>next=L; L=p; } return OK; 2-38

39 2.3 线性表的链式表示和实现 2、尾插法建表（无头结点）
头插法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。该方法是将新结点插入到当前链表的表尾上，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。 Status CreateList(ListLink ＆L ) { char ch;　LNode *p，*r; L=NULL;　r=NULL; while( (ch=getchar( ) ) !=‵\n′) { p=(LNode *) malloc(sizeof(LNode)); p–>data=ch; if　(L==NULL) //生成第一个结点 { L=p;　r=p; } else 　　　　　//生成其他结点 { r–>next=p; r=p; } } if (r!=NULL) r–>next=NULL; //生成结点时，为r–>next赋空值 return OK; 2-39

40 2.3 线性表的链式表示和实现 3、建带头结点链表 逆序输入n个数据创建带头结点链表的算法：
Status CreateList_L(LinkList &L, int n){ L=(LinkList) malloc(sizeof(LNode)); L->next=NULL; //先建立头结点 for (i=n; i>0; --i) { p=(LinkList) malloc(sizeof(LNode)); scanf(&p->data); p–>next = L->next; L–>next = p; } 2-40

41 2.3 线性表的链式表示和实现 有时候，也可以用一维数组来描述链表，这种链表称为静态链表。它的形式定义为
#define MAXSIZE 1000 typedef struct { ElemType data; //数据 int cur; //指示下一项的数组索引 } component, SLinkList[MAXSIZE]; 如图2.10，数组的第一个分量可以看成头结点，假设S为SLinkList型变量，则i=S[i].cur相当于指针的后移。定位函数见算法2.13，类似可以写出插入和删除的操作。所不同的是，用户必须自己实现malloc和free两个函数。为了辨明数组中哪些分量未被使用，解决的办法是建立一个备用结点链表，每当进行插入操作时从备用链表上取得第一个结点作为新结点，在删除时将被删除的结点链接到备用链表上。 2-41

42 2.3 线性表的链式表示和实现 void InitSpace_SL(SlinkList &space)
{ // space为备用链表，space[0].cur为头指针 for (i=0; i<MAXSIZE-1; ++i) space[i].cur=i+1; space[MAXSIZE-1].cur=0; } int Malloc_SL(SlinkList &space) { //若备用链表非空，则返回分配的结点下标，否则返回0 i=space[0].cur; if (space[0].cur) space[0].cur=space[i].cur; return i; void Free_SL(SLinkList &space, int k) { //将下标为k的空闲结点回收到备用链表的头部 space[k].cur=space[0].cur; space[0].cur=k; 2-42

43 2.3 线性表的链式表示和实现 算法2.17 计算 (A-B)∪(B-A)
例2-3 先由输入建立集合A的静态链表S，然后在输入B元素的同时查找S表，若存在和B相同的元素，则从S表中删除之，否则将此元素插入S表。 1.[初值] 　 输入集合A元素建立链表S 2.[计算(A-B)∪(B-A)] 对于B中的每一个元素x做如下操作： 若 （x不属于S） 则 将x插入到S的末尾 若 （x属于S） 则 将x从S中删除 3.[算法结束] 算法复杂度为：O（m*n），例子见P34图2.11 2-43

44 2.3 线性表的链式表示和实现 2.3.2 循环链表 循环链表是一种头尾相接的链表。其特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。 单循环链表：在单链表中，将终端结点的指针域NULL改为指向表头结点或开始结点，就得到了单链形式的循环链表，并简单称为单循环链表。 为了使空表和非空表的处理一致，循环链表中也可设置一个头结点。这样，空循环链表仅有一个自成循环的头结点表示。如下图所示： ⑴ 非空表 a1 an … head ⑵ 空表 head 2-44

45 2.3 线性表的链式表示和实现 在用头指针表示的单链表中，找开始结点a1的时间是O(1)，然而要找到终端结点an，则需从头指针开始遍历整个链表，其时间是O(n) 在很多实际问题中，表的操作常常是在表的首尾位置上进行，此时头指针表示的单循环链表就显得不够方便.如果改用尾指针rear来表示单循环链表，则查找开始结点a1和终端结点an都很方便，它们的存储位置分别是(rear–>next) —>next和rear，显然，查找时间都是O(1)。因此，实际中多采用尾指针表示单循环链表。 由于循环链表中没有NULL指针，故涉及遍历操作时，其终止条件就不再像非循环链表那样判断p或p—>next是否为空，而是判断它们是否等于某一指定指针，如头指什或尾指针等。 2-45

46 2.3 线性表的链式表示和实现 例、在链表上实现将两个线性表(a1，a2，a3，…an)和(b1，b2，b3，…bn)链接成一个线性表的运算。 LinkList Connect(LinkList reara，LinkList rearb) { LinkList p=reara—>next; reara—>next=(rearb—>next)—>next free(rearb—>next); rearb—>next=p; return (rearb); } 2-46

47 2.3 线性表的链式表示和实现 2.3.3 双链表 双向链表(Double linked list):在单链表的每个结点里再增加一个指向其直接前趋的指针域prior。这样就形成的链表中有两个方向不同的链，故称为双向链表。形式描述为： typedef struct DuLNode{ ElemType data; struct DuLNode *prior，*next; } DuLNode, *DuLinkList; 2-47

48 (p—>prior)—>next=(p—>next)—>prior =p
2.3 线性表的链式表示和实现 和单链表类似，双链表一般也是由头指针唯一确定的，增加头指针也能使双链表上的某些运算变得方便，将头结点和尾结点链接起来也能构成循环链表，并称之为双向链表。 设指针p指向某一结点，则双向链表结构的对称性可用下式描述： (p—>prior)—>next=(p—>next)—>prior =p 即结点*p的存储位置既存放在其前趋结点*(p—>prior)的直接后继指针域中，也存放 在它的后继结点*(p—>next)的直接前趋指针域中。 2-48

49 2.3 线性表的链式表示和实现 插入操作 Status ListInsert_DuL(DuLinkList p，ElemType e) {
DuLinkList s=malloc(sizeof(DuLNode)); s—>data=e; s—>prior=p—>prior; p—>prior—>next=s; s—>next=p; p—>prior=s; return OK; } 2-49

50 2.3 线性表的链式表示和实现 删除p指针所指的结点 { p–>prior–>next=p–>next;
p–>next–>prior=p–>prior; free(p); } 2-50

51 Pn(x)=p0+p1x+p2x2+…+pnxn
2.4 一元多项式的表示及相加 一元多项式按升幂可以表示为 Pn(x)=p0+p1x+p2x2+…+pnxn 　 多项式的几种存储结构 12.3X7 -4.5X5 +4X -33.2 4 2 -4.5 5 12.3 7 系数 指数 2-51

52 2.4 一元多项式的表示及相加 结构定义（以链表实现的线性表为例） struct PolyNode { double c; int e;
PolyNode *next; }; typedef PolyNode *Poly; 2-52

53 2.4 一元多项式的表示及相加 ２．多项式相加算法的实现 设：1）多项式采用非零系数单链表结构；
2）多项式A(x)和B(x)相加，“和多项式”C(x)的结点不另外申请存储空间； 3）p,q分别指向A(x)和B(x)中的某结点。 运算规则：指数相同，系数相加。 若p->exp < q->exp，则p结点为C(x)的一项，移动p； 若p->exp > q->exp，则q结点插入在p结点之前，移动q； 若p->exp = q->exp，则p->coef:= p->coef+ q->coef; 释放q结点; 当和为０时，释放p结点; 移动p和q； 2-53

54 2.4 一元多项式的表示及相加 例 A(x) = 7 + 3x + 9x8 + 5x17 - 8x100 B(x) = 8x + 22x7 - 9x8 + C(x) = A(x)+ B(x) = x + 22x7 + 5x17- 8x100 存储方式的选择－－以单链表存储多项式系数和指数 headA 7 3 1 9 8 5 17 -8 ^ 100 headB 8 1 22 7 -9 ^ 2-54

55 2.4 一元多项式的表示及相加 qa 7 3 1 9 8 5 17 -8 ^ 100 qb 8 1 22 7 -9 ^ qc ^ headA
一元多项式的相加实现 headA 7 3 1 9 8 5 17 -8 ^ 100 qb headB 8 1 22 7 -9 ^ qc headC ^ 2-55

56 2.4 一元多项式的表示及相加 qa qa 7 3 1 9 8 5 17 -8 ^ 100 qb 8 1 22 7 -9 ^ qc qc ^
一元多项式的相加实现 headA 7 3 1 9 8 5 17 -8 ^ 100 qb headB 8 1 22 7 -9 ^ qc qc headC ^ 7 ^ 2-56

57 2.4 一元多项式的表示及相加 7 3 1 9 8 5 17 -8 ^ 100 qa qa 8 1 22 7 -9 ^ qb qb ^ 7
headA 7 3 1 9 8 5 17 -8 ^ 100 qa qa 一元多项式的相加实现 headB 8 1 22 7 -9 ^ qb qb headC ^ 7 qc qc 11 ^ 1 2-57

58 2.4 一元多项式的表示及相加 7 3 1 9 8 5 17 -8 ^ 100 qa 8 1 22 7 -9 ^ qb qb ^ 7 11
headA 7 3 1 9 8 5 17 -8 ^ 100 qa 一元多项式的相加实现 headB 8 1 22 7 -9 ^ qb qb headC ^ 7 11 1 qc qc 22 ^ 7 2-58

59 2.4 一元多项式的表示及相加 7 3 1 9 8 5 17 -8 ^ 100 qa qa 8 1 22 7 -9 ^ qb qb ^ 7
headA 7 3 1 9 8 5 17 -8 ^ 100 qa qa 一元多项式的相加实现 headB 8 1 22 7 -9 ^ qb qb headC ^ 7 11 1 22 qc 2-59

60 2.4 一元多项式的表示及相加 7 3 1 9 8 5 17 -8 ^ 100 qa qa 8 1 22 7 -9 ^ qb ^ 7 11
headA 7 3 1 9 8 5 17 -8 ^ 100 qa qa 一元多项式的相加实现 headB 8 1 22 7 -9 ^ qb headC ^ 7 11 1 22 qc qc 5 ^ 17 2-60

61 2.4 一元多项式的表示及相加 7 3 1 9 8 5 17 -8 ^ 100 qa qa 8 1 22 7 -9 ^ qb ^ 7 11
headA 7 3 1 9 8 5 17 -8 ^ 100 qa qa 一元多项式的相加实现 headB 8 1 22 7 -9 ^ qb headC ^ 7 11 1 22 5 17 qc qc -8 ^ 100 2-61

62 约瑟夫环(Joseph Circle) 问题描述：
　　编号为1,2,...,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。现在给定一个随机数m>0，从编号为1的人开始，按顺时针方向1开始顺序报数，报到m时停止。报m的人出圈，同时留下他的密码作为新的m值，从他在顺时针方向上的下一个人开始，重新从1开始报数，如此下去，直至所有的人全部出列为止。 　　请编写程序求出圈的顺序。 2-62

63 约瑟夫环(Joseph Circle) k：计数 m：密码 例： 2 k=1 1 5 start 8 3 3 7 1 15 4 6 22 9
出队序列： 2-63

64 约瑟夫环(Joseph Circle) k：计数 m：密码 5 k=2 例： 2 1 start 8 3 3 7 1 15 4 6 22 9
出队序列： 2-64

65 约瑟夫环(Joseph Circle) k：计数 m：密码 例： 2 1 start 8 3 k=3 3 5 7 1 15 4 6 22 9
出队序列： 2-65

66 约瑟夫环(Joseph Circle) k：计数 m：密码 例： 2 1 start 8 3 3 7 1 15 k=4 4 5 6 22 9
出队序列： 2-66

67 约瑟夫环(Joseph Circle) k：计数 m：密码 例： 2 1 start 8 3 7 15 6 22 9 k=5 5 4
存入密码 出队序列： 2-67

68 约瑟夫环(Joseph Circle) k：计数 m：密码 例： 8 2 3 1 start 1 3 15 7 22 4 k=1 4 9 6
出队序列： 5 2-68

69 约瑟夫环(Joseph Circle) k：计数 m：密码 4 k=4 例： 2 1 start 8 3 3 7 1 15 4 6 22 9
出队序列： 5 2-69

70 约瑟夫环(Joseph Circle) k：计数 m：密码 例： 3 1 start k=1 1 3 8 15 7 22 4 9 6
出队序列： 5 2 2-70

71 约瑟夫环(Joseph Circle) k：计数 m：密码 例： 3 1 start 1 3 15 7 22 4 k=8 8 9 6
出队序列： 5 2 2-71

72 约瑟夫环(Joseph Circle) k：计数 m：密码 例： 3 1 start 1 3 k=1 9 15 7 22 4 出队序列： 5
6 2-72

73 约瑟夫环(Joseph Circle) k：计数 m：密码 例： 3 1 start 1 3 k=9 9 15 7 22 4 出队序列： 5
6 2-73

74 约瑟夫环(Joseph Circle) k：计数 m：密码 例： k=1 15 3 1 start 1 3 22 4 出队序列： 5 2 6
7 2-74

75 约瑟夫环(Joseph Circle) k：计数 m：密码 例： 3 1 start 1 3 k=15 22 4 15 出队序列： 5 2
6 7 2-75

76 约瑟夫环(Joseph Circle) k：计数 m：密码 例： k=1 22 3 1 start 1 3 出队序列： 5 2 6 7 4
2-76

77 约瑟夫环(Joseph Circle) k：计数 m：密码 例： 3 1 start 1 3 k=22 22 出队序列： 5 2 6 7 4
2-77

78 约瑟夫环(Joseph Circle) k：计数 m：密码 例： k=1 1 3 1 start 出队序列： 5 2 6 7 4 3
2-78

79 约瑟夫环(Joseph Circle) k：计数 例： k=1 3 m：密码 start 出队序列： 5 2 6 7 4 3 1 2-79

80 约瑟夫环(Joseph Circle) 存储结构 p 2 tail 1 8 pre 3 7 15 6 22 5 9 4 需要的变量：
k：计数 p: 指向当前结点 pre：指向p的前驱结点 上机实现提示： ① 编制建立循环链表算法 ②编制结点输出算法(带输入参数k) ③编制主程序 4 5 9 6 15 7 3 1 8 2 22 tail p pre 2-80

81 作业 * 2-81

82 本章小结 本章应掌握的内容 线性表的基本概念 线性表的顺序存储及其特点 线性表的链式存储及其特点
链表、结点、指针（链）、单链表、双向链表、循环链表 2-82