[计算机软件及应用]第2章线性表ppt课件

1、线性表线性表【学习目的】【学习目的】 1. 了解线性表的逻辑构造特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储构造是顺序存储构造和链式存储构造。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。 2. 熟练掌握这两类存储构造的描画方法以及线性表的根本操作在这两种存储构造上的实现。 3. 可以从时间和空间复杂度的角度综合比较线性表两种存储构造的不同特点及其适用场所。 4. 结合线性表类型的定义加强对笼统数据类型的了解。【重点和难点】【重点和难点】 链表是本章的重点和难点。扎实的指针操作和内存动态分配的编程技术是学好本章的根本要求，分清链表中指针 p 和结点

2、*p 之间的对应关系，区分链表中的头结点、头指针和首元结点的不同所指以及循环链表、双向链表的特点等。【知识点】【知识点】线性表、顺序表、链表、有序表线性表、顺序表、链表、有序表线性构造的根本特征为线性构造的根本特征为: :1集合中必存在独一的一个集合中必存在独一的一个“第一元素；第一元素；2集合中必存在独一的一个集合中必存在独一的一个 “最后元素最后元素 ；3除最后元素在外，均有除最后元素在外，均有 独一的后继；独一的后继；4除第一元素之外，均有除第一元素之外，均有 独一的前驱。独一的前驱。 线性构造线性构造 是是 一个数据元素的有序次序集一个数据元素的有序次序集线性表是一种最简单的线性构造线

3、性表是一种最简单的线性构造1 线性表的类型定义线性表的类型定义3 线性表类型的实现线性表类型的实现 链式映象链式映象4 一元多项式的表示一元多项式的表示2 线性表类型的实现线性表类型的实现 顺序映象顺序映象线性表的类型定义线性表的类型定义l定义：一个线性表是具有一样类型的nn0个数据元素的有限序列，通常记为：niaaaaai11i,21a,例 英文字母表A,B,C,.Z)例学号 姓名 年龄 001 张三 18 002 李四 19 数据元素l特征：li为元素的序号l元素个数n表长度，n=0空表l1in时lai的直接前驱是ai-1，a1无直接前驱lai的直接后继是ai+1，an无直接后继1 线性表

4、的定义 数据对象：D ai | ai D0, i=1,2,.,n, n0 称 n 为线性表的表长; 称 n=0 时的线性表为空表。数据关系：数据关系：R |ai-1 ,aiD, i=2,.,n 设线性表为 (a1，a2, . . . ，ai，. . . ，an), 称 i 为 ai 在线性表中的位序。线性表的根本运算置空表setnull(L)：将线性表L置为空表。求长度length(L)：计算线性表L中数据元素的个数。取元素get(L,i)：取出线性表L中第i个数据元素；要求ilength(L)。取前趋prior(L,x)：取出线性表L中值为x的元素的前趋元素；要求x的位序大于1。取后继nex

5、t(L,x)：取出线性表L中值为x的元素的后继元素；要求x的位序小于length(L)。定位序locate(L,x)：确定元素x在线性表L中的位置，并给出位置序号；假设L中无x前往0。线性表的根本运算续插入insert(L,x,i)：在线性表L中第i个位置上插入值为x的新元素，使表长增1；要求1ilength(L)+1。删除delete(L,i)：删除线性表L中的第i个元素，使表长减1；要求1ilength(L)。利用上述定义的线性表 可以实现其它更复杂的操作例例 2-2例例 2-1求两个集合的并，即A=AB例例 2-1 2-1 要求对线性表作如下操作：扩展线性表 LA，将存在于线性表LB 中

6、而不存在于线性表 LA 中的数据元素插入到线性表 LA 中去。上述问题可演绎为：1从线性表从线性表LB中依次察看每个数据元素中依次察看每个数据元素;2依值在线性表依值在线性表LA中进展查访中进展查访; 3假设不存在，那么插入之。假设不存在，那么插入之。get (LB, i)e locate (LA, e) insert(LA, n+1, e)操作步骤：操作步骤： e =get(Lb, i); / 取Lb中第i个数据元素赋给e if (!locate (La, e) ) insert(La, +La_len, e); / La中不存在和 e 一样的数据元素，那么插入之void union(La,

7、 Lb) La_len = length(La); / 求线性表的长度求线性表的长度 Lb_len = length(Lb); for (i = 1; i = Lb_len; i+) / union 知一个非纯集合知一个非纯集合 B，试构造一个纯，试构造一个纯集合集合 A，使，使 A中只包含中只包含 B 中一切值各不中一切值各不相相 同的数据元素。同的数据元素。仍选用线性表表示集合。例例 2-2集合集合 B集合集合 A从集合 B 取出物件放入集合 A要求集合A中同样物件不能有两件以上因此，算法的战略应该和例2-1一样void union(List &La, List Lb) La_le

8、n=length(La); Lb_len=length(Lb); / union e=get(Lb, i); / 取Lb中第 i 个数据元素赋给 e if (!locate(La, e) ) insert(La, +La_len, e); / La中不存在和 e 一样的数据元素，那么插入之for (i = 1; i = Lb_len; i+) setnull(La); / 构造构造(空的空的)线性表线性表LA假设线性表中的数据元素相互之间可以比较，并且数据元素在线性表中依值非递减或非递增有序陈列，即 aiai-1 或 aiai-1(i = 2,3, n)，那么称该线性表为有序表(Ordered

9、 List)。我们再来看看有序表表示的集合。例如：例如：LA=(3,5,8,11)LB=(2,6,8,9,11,15,20)对集合LA和LB 而言， 值一样的数据元素必定相邻。要求生成一个新表LC，使LC中的数据元素仍按值非递减有有序陈列。void MergeList(List La, List Lb, List &Lc) / 本算法将非递减的有序表本算法将非递减的有序表 La 和和 Lb 归并为归并为 Lc / merge_listwhile (i = La_len) & (j = Lb_len) / La 和和 Lb 均不空均不空 while (i=La_len) / 假设

10、假设 La 不空不空while (j=Lb_len) / 假设假设 Lb 不空不空setnull(Lc); / 构造空的线性表 Lci = j = 1; k = 0;La_len = length(La);Lb_len = length(Lb);例例 2-3 while (i = La_len) / 当当La不空时不空时 ai= get(La, i+); insert(Lc, +k, ai); / 插入插入 La 表中剩余元素表中剩余元素 while (j = Lb_len) / 当Lb不空时 bj= get(Lb, j+); insert(Lc, +k, bj); / 插入 Lb 表中剩余元

11、素While( (i = La_len)& (j = Lb_len) / 当当La,Lb都不都不空时空时 ai =get(La, i); bj= get(Lb, j); if(ailast = 0;线性表的根本操作在顺序表中的实现线性表的根本操作在顺序表中的实现Locate(L, x) / 查找查找例如：顺序表的查找操作23 75 41 38 54 62 17L.dataL.lastMAXSIZEx =38pppppi 1 2 3 4 1 850p可见，根本操作是：将顺序表中的元素逐个和给定值 x 相比较。 int locate (sequenlist L, elemtype x) /

12、 在顺序表中查询第一个满足断定条件的数据元素， / 假设存在，那么前往它的位序，否那么前往 0 O( ListLength(L) )算法的时间复杂度为：算法的时间复杂度为：int i = 1; / i 的初值为第 1 元素的位序while (i = L.last & (L.datai!=x) +i;if (i = L.last) return i;else return 0;线性表操作insert(L, i, x)的实现：首先分析首先分析:插入元素时，线性表的逻辑构造发生什么变化？ (a1, , ai-1, ai, , an) 改动为 (a1, , ai-1, x, ai, , an)

13、a1 a2 ai-1 ai ana1 a2 ai-1 ai xan, 表的长度添加算法的思想 进展合法性检查i 检查线性表能否已满 讲第n个至第i个元素逐一后移一个单位 在第i个位置上插入 表的长度+1插入运算的算法描画 void insert(sequenlist *L; elemtype x; int i) int j; if(i(L-last+1) printf(“插入位置不正确n); else if(L-last=MAXSIZE) printf(“表已满，发生上溢n); else for(j=L-last;j=i;j-) L-dataj+ 1 = L -dataj; L-datai=x

14、; L-last=L-last+1; /*insert*/思索插入算法的时间复杂度思索插入算法的时间复杂度: :线性表操作 delete(&L, i)的实现：首先分析：删除元素时，线性表的逻辑构造发生什么变化？ (a1, , ai-1, ai, ai+1, , an) 改动为 (a1, , ai-1, ai+1, , an)ai+1 an, 表的长度减少a1 a2 ai-1 ai ai+1 ana1 a2 ai-1 算法的思想 进展合法性检查，i能否满足要求 断定线性表能否为空 将第i+1至第n个元素逐一往前挪动一个位置 将表的长度减少1删除运算的算法描画 void delete(se

15、quenlist *L，int i) int j; if(iL-last) printf(“删除位置不正确n); else for(j=i+1;jlast;j+) L - d a t a j -1=L-dataj; L-last=L-last-1; /*delete*/思索删除算法的时间复杂度思索删除算法的时间复杂度: :举例删除顺序表中的反复元素 一个顺序表中能够含有一些值一样的反复元素，标题要求对于值一样的反复元素只保管位序最小的一个而删除其它多余的元素。如5，2，2，3，5，2经删除反复元素后变为 5，2，3 删除顺序表中的反复元素的算法描画 void Purge(L) sequenli

16、st *L; int i,j,k; i=1; while(ilast) j=i+1; while(jlast) if(L-dataj=L-datai) for(k=j+1;klast;k+) L - d a t a k - 1 = L -datak; L-last=L-last-1; else j+; i+; /*Purge*/举例有序表的合并顺序表A和B的元素均按由小到大的升序陈列，编写算法将它们合并成为顺序表C，要求C中元素也是从小到大的升序陈列。算法思绪：依次扫描A和B中元素，比较当前两个元素值，将较小的元素赋给C，直到其中一个顺序表扫描终了，然后将另一个顺序表中剩余元素赋给C即可。 有

17、序表的合并的算法描画 void merge(C,A,B) sequenlist *C,*A,*B; int i,j,k; i=1;j=1;k=1; while(ilast&jlast) if(A-dataidataj) C-datak+=A-datai+; else C-datak+=B-dataj+; While(ilast) C-datak+=A-datai+; While(jlast) C-datak+=B-dataj+; C-last=k-1; /*merge*/ 用一组地址恣意的存储单用一组地址恣意的存储单元存放线性表中的数据元素。元存放线性表中的数据元素。一、单链表一、单链

18、表以数据域(数据元素的信息) + 指针(指示后继元素存储位置) = 结点以“结点的序列表示线性表 称作链表 以线性表中第一个数据元素 的存储地址作为线性表的地址，称作线性表的头指针。1a a1 a2 . an 头指针空指针 typedef struct node elemtype data; / 数据域数据域 struct node *next; / 指针域指针域 LinkList; 二、结点和单链表的二、结点和单链表的 C C 言语描画言语描画LinkList *H,*P； / H,P为单链表的头指针为单链表的头指针头结点头结点 a1 a2 . an 头指针头指针 有时为了操作方便，在第一个

19、结点之前虚加一个“头结点，以指向头结点的指针为链表的头指针。空指针线性表为空表时，头结点的指针域为空 1.元素的查找 按序号查找L 线性表的操作 GetLinkList(L,i)在单链表中的实现(找到第3个元素):211830754256pppj1 2 3 因此，查找第因此，查找第 i 个数据元素的根本个数据元素的根本操作为：挪动指针，比较操作为：挪动指针，比较 j 和和 i 。 单链表不是一种顺序存取的构造，为找第单链表不是一种顺序存取的构造，为找第 i 个数据元素，必需先找到第个数据元素，必需先找到第 i-1 个数据元素。个数据元素。 令指针令指针 p p 一直指向线性表中第一直指向线性表

20、中第 j j 个数据元素。个数据元素。 LinkList * getLinkList(LinkList *L，int i) LinkList *P; int j=0; P=L; while(jnext!=NULL) P=P-next; j+; if(j=i) return P; else return NULL; elemtype GetLinkList(LinkList *L，int i) LinkList *P; int j=0; P=L; while(jnext!=NULL) P=P-next; j+; if(j=i) return P-data; else return 0; int

21、GetLinkList(LinkList *L，int i,elemtype *e) LinkList *P; int j=0; P=L; while(jnext!=NULL) P=P-next; j+; if(j=i) *e=P-data; return 1; else return 0; p = L; j = 0; / p指向头结点，j为计数器while (jnext!=NULL) p = p-next; +j; 这两种情况有六种组合1. p-next=NULL且j0或者i表长，异常2. p-next =NULL且j=i 空表且i=0或者i=表长3. p-next =NULL且ji 空表且

22、inext !=NULL且jnext !=NULL且j=i 确定第i个结点 正常出循环6. p-next! =NULL且ji 异常出循环1.元素的查找 按值查找L211830754256pLocateLinkList(L,x) LinkList LinkList * *LocateLinkList(LinkList LocateLinkList(LinkList * *L L， elemtype x) elemtype x) LinkList LinkList * *P;P; P=L-next; P=L-next; while(P!=NULL)&(P-data!=x) while(P!

23、=NULL)&(P-data!=x) P=P-next; P=P-next; return P; / return P; /* *前往找到的结点位置或前往找到的结点位置或NULLNULL* */ / 假设要前往位序，程序怎样修正2.插入操作ai-1 线性表的操作 insertLinkList(L, x ,i)在单链表中的实现： 有序对 改动为 和 xaiai-1s-data = e; s-next = p-next; p-next = s; / 插入 eai-1aiai-1sp 因此，在单链表中第因此，在单链表中第 i 个结点之前进个结点之前进展插入的根本操作为展插入的根本操作为: 找

24、到线性表中第找到线性表中第i-1个结点，然后修正个结点，然后修正其指向后继的指针。其指向后继的指针。 可见，在链表中插入结点只需求修正可见，在链表中插入结点只需求修正指针。但同时，假设要在第指针。但同时，假设要在第 i 个结点之个结点之前插入元素，修正的是第前插入元素，修正的是第 i-1 个结点的个结点的指针。指针。插入算法描画 void insertLinkList(LinkList *L, elemtype x, int i) LinkList *P,*S; P=getLinkList(L,i-1);/*查找第i-1个结点*/ if(P=NULL) Printf(“第i-1个元素不存在，参

25、数i有错n); else S=(LinkList *)malloc(sizeof(LinkList); S-data=x; S-next=P-next; P-next=S; int insertLinkList (LinkList *L, ElemType e, int i) LinkList *p = L; int j = 0;while (p & j next; +j; / 寻觅第 i-1 个结点if (!p | j i-1) return 0; / i 大于表长或者小于1 s = (LinkList*) malloc ( sizeof (node); / 生成新结点s-data

26、= e; s-next = p-next; p-next = s; / 插入return 1; eai-1aiai-1sp循环条件的分析第一次循环p!=NULL,j有三种能够1.ji-1 i1不合法1.p=!NULL且ji-1 继续循环2.p=!NULL且j=i-1 曾经定位 正常出循环3.p=NULL且j=表长+2，出循环第二次循环后，p有能够NULL,但是ji-1不能够，出现的各种能够情况：3.删除操作线性表的操作deleteLinkList (L, i)在链表中的实现:有序对有序对 和和 ai, ai+1 改动为改动为 ai-1aiai+1ai-1 在单链表中删除第 i 个结点的根本操作

27、为:找到线性表中第i-1个结点，修正其指向后继的指针。ai-1aiai+1ai-1q = p-next; p-next = q-next; e = q-data; free(q);pq删除单链表L中的第i个结点算法 void deleteLinkList(LinkList *L, int i) LinkList *P,*S; P=getLinkList(L,i-1);/*查找第i-1个结点*/ if(P=NULL) Printf(“第i-1个元素不存在，参数i 有错n); else S=P-next; P-next=S-next; free (S); int deleteLinkList (L

28、inkList *L, int i, ElemType &e) LinkList *p = L; int j = 0;while (p-next!=NULL & j next; / 寻觅第 i 个结点，并令 p 指向其前趋 +j; if (!(p-next) | j i-1) return 0; / 删除位置不合理q = p-next; p-next = q-next; / 删除并释放结点删除并释放结点e = q-data; free(q);return 1;删除算法讨论： 删除范围为1,表长，不能删除头结点 出循环的五种能够情况： p-next=NULL且j表长 p-next

29、=NULL且j=i-1 空表且i=1，或i=表长+1 p-next=NULL且ji-1 空表且inext!=NULL且j=i-1 非空表且定位 p-next!=NULL且ji-1 非空表且inext!=NULL) P=P-next; j+; return j; /*前往表长*/ 该算法扫描整个单链表，时间复杂度为O(n)。 5.建立单链表如何从得到单链表？如何从得到单链表？链表是一个动态的构造，它不需求链表是一个动态的构造，它不需求予分配空间，因此生成链表的过程予分配空间，因此生成链表的过程是一个结点是一个结点“逐个插入逐个插入 的过程。的过程。例如：逆位序输入例如：逆位序输入 n n 个数据

30、元素的值，个数据元素的值， 建立带头结点的单链表。建立带头结点的单链表。( (头插法头插法) )操作步骤：操作步骤：一、建立一个一、建立一个“空表；空表；二、输入数据元素二、输入数据元素anan， 建立结点并插入；建立结点并插入；三、输入数据元素三、输入数据元素an-1an-1， 建立结点并插入；建立结点并插入；ananan-1四、依次类推，直至输入四、依次类推，直至输入a1a1为止。为止。adcbi=0 i=1 i=2 i=3head采用头插法建立单链表的过程采用头插法建立单链表的过程headaheaddaheadcdaheadbcda第第1 1步步: :建头结点建头结点第第2 2步步:i:

31、i0,0,新建新建a a结点结点, ,插入到头结点之后插入到头结点之后第第3 3步步:i:i1,1,新建新建d d结点结点, ,插入到头结点之后插入到头结点之后第第4 4步步:i:i2,2,新建新建c c结点结点, ,插入到头结点之后插入到头结点之后第第5 5步步:i:i3,3,新建新建b b结点结点, ,插入到头结点之后插入到头结点之后void CreateList (LinkList *&L, int n) / 逆序输入逆序输入 n 个数据元素，建立带头结个数据元素，建立带头结点的单链表点的单链表算法的时间复杂度为算法的时间复杂度为:O(Listlength(L)L = (Link

32、List*) malloc (sizeof (node);L-next = NULL; / 先建立一个带头结点的单链表for (i = n; i 0; -i) p = (LinkList*) malloc (sizeof (node); scanf(“%d,&p-data); / 输入元素值输入元素值 p-next = L-next; L-next = p; / 插入插入正序插法详细的算法描画如下：LinkList *CreateLinkList() char ch; int x; LinkList *head; LinkList *r,*P; h e a d = ( L i n k

33、L i s t *)malloc(sizeof(LinkList); head-next=NULL; r=head; /*尾指针初始化*/ch=getchar(); while(ch!=*) /“*为输入 数据终了符号*/ scanf(“%d,&x); P=(LinkList*)malloc(sizeof(LinkList); P-data=x; P-next=NULL; r-next=P; r=r-next; ch=getchar();return head;单链表建立过程例如线性表25，45，18，76，29的单链表动态建立过程如以下图：LinkList * CreateList(

34、int n) /* 正位序(插在表尾)输入n个元素的值，建立带表头构造的单链线性表 */int i;LinkList *L;LinkList * p,*r;L=(LinkList *)malloc(sizeof(LinkList); /* 生成头结点 */L-next=NULL;r=L;printf(请输入%d个数据n,n);for(i=1;idata);p-next=NULL;r-next=p;r=p;return L 归并两个有序表Lb26891115 La35811 LinkList LinkList * * MergeList ( LinkList MergeList ( LinkLi

35、st * *&La, LinkList &La, LinkList * *&Lb )&Lb )pa=La-next; pb=Lb-next;pa=La-next; pb=Lb-next;Lc=pc=La;Lc=pc=La;While( pa & pb ) While( pa & pb ) if( pa-data data ) if( pa-data data ) pc-next=pa; pc=pa; pa= pa -next; pc-next=pa; pc=pa; pa= pa -next; else else pc-next=pb; pc=pb

36、; pb=pb-next;pc-next=pb; pc=pb; pb=pb-next; if(pa) pc-next=pa;if(pa) pc-next=pa;else pc-next=pb; else pc-next=pb; free(Lb); return Lcfree(Lb); return Lc 。 例例 设设C=a1,b1,a2,b2,an,bn为一线性表为一线性表,采采用带头结点的用带头结点的hc单链表存放单链表存放,编写一个算法编写一个算法,将 其 拆 分 为 两 个 线 性 表将 其 拆 分 为 两 个 线 性 表 , 使 得使 得 : A=a1,a2,an,B=b1,b2,b

37、n 解解:设拆分后的两个线性表都用带头结点的设拆分后的两个线性表都用带头结点的单链表存放。先建立两个头结点单链表存放。先建立两个头结点*ha和和*hb,它们它们用于存放拆分后的线性表用于存放拆分后的线性表A和和B, ra和和rb分别指分别指向这两个单链表的表尾。向这两个单链表的表尾。用用p指针扫描单链表指针扫描单链表hc,将当前结点将当前结点*p链到链到ha未尾未尾, p沿沿next域下移一个结点域下移一个结点,假设不为空假设不为空, 那么当前结点那么当前结点*p链到链到hb未尾未尾, p沿沿next域下移一域下移一个结点个结点, 如此这样如此这样, 直到直到p为空。最后将两个尾结为空。最后将

38、两个尾结点的点的next域置空。域置空。 void fun(LinkList *hc, LinkList *&ha, LinkList *&hb) LinkList *p=hc-next,*ra,*rb; ha=hc; /*ha的头结点利用的头结点利用hc的头结点的头结点*/ ra=ha; /*ra一直指向一直指向ha的末尾结点的末尾结点*/ hb=(LinkList *)malloc(sizeof(LinkList); /*创建创建hb头结点头结点*/ rb=hb; /*rb一直指向一直指向hb的末尾结点的末尾结点*/ 本算法实践上是采用尾插法建立两个新本算法实践上是采用尾插

39、法建立两个新表。所以表。所以, ,尾插法建表算法是很多类似习题尾插法建表算法是很多类似习题的根底！的根底！ while (p!=NULL) ra-next=p;ra=p; /*将将*p链到链到ha单链表未尾单链表未尾*/ p=p-next; if (p!=NULL) rb-next=p; rb=p; /*将将*p链到链到hb单链表未尾单链表未尾*/ p=p-next; ra-next=rb-next=NULL; /*两个尾结点的两个尾结点的next域置空域置空*/举例将单链表H逆置 所谓逆置是指结点间的关系相反，即前趋变后继而后继变前趋。如图(a)的单链表逆置后成为图(b)的单链表。算法思绪：

40、依次从原链表中取出每个结点，每次都把它作为第一个结点插入到新链表中去。为此要借用两个指针变量P和q，P用来指向原链表中的当前第一个结点，q用来指向从原表取出的每一个结点并利用它插入到新链表中去，当P为空时完成逆置。 将单链表H逆置的算法描画 void reverse(H) LinkList *H; LinkList *P,*q; P=H-next; H-next=NULL; while(P!=NULL) q=P; P=P-next; q-next=H-next; H-next=q; *reverse*/该算法没有开辟新的存储空间，对链表顺序扫描一遍就完成了逆置，时间开销为O(n)。作业： 1.

41、给定一个单链表L，编写一个删除L中值为x的结点的直接前驱结点算法。 2.有一个单链表不同的结点的数据域值能够一样，其头指针为head,编写一个函数计算数据域为x的结点个数。作业2： 1.给定一个单链表L，编写一个删除L中值为x的结点的算法。 2.设计一个算法，在一个单链表中值为y的结点前面插入一个值为x的结点。 优点 逻辑相邻，物理相邻 可随机存取任一元素 存储空间运用紧凑 缺陷 插入、删除操作需求挪动大量的元素 预先分配空间需按最大空间分配，利用不充分 表容量难以扩展顺序存储构造的优缺陷 单链表特点 它是一种动态构造，整个存储空间为多个链表共用 不需预先分配空间 指针占用额外存储空间 不能随

42、机存取，查找速度慢 循环链表是表中最后一个结点的指针指向头结点，使链表构成环状h空表循环链表(circular linked list)v特点：从表中任一结点出发均可找到表中其他结点，提高查找效率v操作与单链表根本一致,循环条件不同v单链表p或p-next=NULLv循环链表p或p-next=Hhr空表设置尾指针的循环链表设置尾指针的循环链表，在对两个单循环链表进展衔接使可以提高效率。r2b1bnr1a1anr1-next=r2-next-next;r2-next=p;rpp=r1-next;单链表具有单向性的缺陷，找前驱不方便！结点定义typedef struct dupnode elemt

43、ype data; struct dupnode *prior,*next;duplinklist;priordatanextL空双向循环链表：非空双向循环链表： LABbcapp-prior-next= p= p-next-proir;双向链表double linked list双向链表的操作特点：双向链表的操作特点：“查询 和单链表一样。“插入插入 和和“删除时需求同时修删除时需求同时修正两个方向上的指针。正两个方向上的指针。void ins_dlinklist(duplinklist * p,int x)duplinklist *s; s=(duplinklist *)malloc(si

44、zeof(duplinklist ); s-data=x; s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s; 算法描画 算法评价：T(n)=O(1)xSbaP 插入p-prior-next=s;s-prior=p-prior;s-next=p;p-prior=s;ai-1aies-next = p-next; p-next = s;s-next-prior = s; s-prior = p;psai-1ai插入插入bcvoid del_dlinklist(duplinklist *p) p-prior-next=p-next; p-ne

45、xt-prior=p-prior; free(p); 删除 算法描画 算法评价：T(n)=O(1)p-prior-next=p-next;p-next-prior=p-prior;ai-1删除删除aiai+1p-next = p-next-next;p-next-prior = p;pai-1用上述定义的单链表实现线性表的操作时，用上述定义的单链表实现线性表的操作时，存在的问题：存在的问题： 改良链表的设置改良链表的设置1单链表的表长是一个隐含的值；单链表的表长是一个隐含的值； 1添加“表长、“表尾指针 和 “当前位置的 指针 三个数据域；2在单链表的最后一个元素之后插入元素时，在单链表的最后

46、一个元素之后插入元素时， 需遍历整个链表；需遍历整个链表；3在链表中，元素的在链表中，元素的“位序概念淡化，结点的位序概念淡化，结点的 “位置概念加强。位置概念加强。2将根本操作中的将根本操作中的“位序位序 i 改动为改动为“指针指针 p 。一个带头结点的线性链表类型一个带头结点的线性链表类型typedef struct node / 结点类型结点类型 ElemType data; struct node *next; Link;typedef struct / 链表类型链表类型 Link * head, *tail; / 分别指向头结点和分别指向头结点和 /最后一个结点的指针最后一个结点的指

47、针 int len; / 指示链表长度指示链表长度 Link* current; / 指向当前被访问的结点指向当前被访问的结点 /的指针，初始位置指向头结点的指针，初始位置指向头结点 LinkList;nnnxpxpxppxp.)(2210在计算机中，可以用一个线性表来表示在计算机中，可以用一个线性表来表示: : P = (p0, p1, P = (p0, p1, ，pn)pn)一元多项式一元多项式但是对于形如但是对于形如 S(x) = 1 + 3x10000 2x20000的多项式，上述表示方法能否适宜？的多项式，上述表示方法能否适宜？ 普通情况下的一元稀疏多项式可写成 Pn(x) = p1xe1 + p2xe2 + + pmxem其中：pi 是指数为ei 的项的非零系数， 0 e1 e2 expexp ,那么p为结点C(x)的一项，挪动p 2. p-expq-exp,那么q结点插入到p结点之前，挪动q 3. p-exp=q-exp,那么，系数相加，释放q结点一元多项式的数据类型定义假设是多项式的运算问题如相加和相乘等，思索到会产生新的项和系数为零项减少这两种情况，宜思索采用链式存储构造即单链表实现。