数据结构之线性表和树

1、2022-5-111065865姓名姓名 学号学号 成绩成绩 班级班级 李红李红 9761059 95 机机97.6 ABCDEFG2022-5-12 1数据的逻辑结构 2、数据的存储结构 3、数据的运算：检索、排序、插入、删除、修改等。 A线性结构 B非线性结构A 顺序存储 B 链式存储 线性表栈队树形结构图形结构数据结构的三个主要问题 2022-5-13线性结构线性结构 A , B , C , ，X ,Y , Z学 生 成 绩 表86胡孝臣986110395刘忠赏9861107100张卓9861109成绩姓名学号线性表线性表结点间是以线性关系联结结点间是以线性关系联结2022-5-14 1

2、数据的逻辑结构 2、数据的存储结构 3、数据的运算：检索、排序、插入、删除、修改等。 A线性结构 B非线性结构A 顺序存储 B 链式存储 线性表栈队树形结构图形结构数据结构的三个方面 2022-5-15树形结构树形结构全校学生档案管理的组织方式全校学生档案管理的组织方式2022-5-16ABCDEFGH树形结构 结点间具有分层次的连接关系HBCDEFGA2022-5-172.5 树树2.5.1 树的定义：由一个或多个结点组成的有限集合树的定义：由一个或多个结点组成的有限集合。仅有仅有一个根结点，结点间有明显的层次结构关系。一个根结点，结点间有明显的层次结构关系。 A C G T2D H I T

3、3J M B E L KT1 F现实世界中，能用树的结构表示的例子：现实世界中，能用树的结构表示的例子：学校的行政关系、书的层次结构、人类的家族血缘关学校的行政关系、书的层次结构、人类的家族血缘关系等。系等。2022-5-18介绍几个概念：介绍几个概念：结点（结点（Node）：树中的元素，包含数据项及若干指向其）：树中的元素，包含数据项及若干指向其子树的分支。子树的分支。结点的度（结点的度（Degree）：结点拥有的子树数。）：结点拥有的子树数。结点的层次：从根结点开始算起，根为第一层。结点的层次：从根结点开始算起，根为第一层。叶子（叶子（Leaf）：度为零的结点，也称端结点。）：度为零的结点

4、，也称端结点。孩子（孩子（Child）：结点子树的根称为该结点的孩子结点。）：结点子树的根称为该结点的孩子结点。兄弟（兄弟（Sibling）：同一双亲的孩子。）：同一双亲的孩子。双亲（双亲（Parent）：孩子结点的上层结点，称为这些结点的）：孩子结点的上层结点，称为这些结点的双亲。双亲。深度（深度（Depth)： 树中结点的最大层次数。树中结点的最大层次数。森林（森林（Forest）：）：M棵互不相交的树的集合。棵互不相交的树的集合。 A C G T2D H I T3J M B E L KT1 F2022-5-192.5.2 二叉树二叉树 （Binary Tree）1 、二叉树的定义及其性质

5、、二叉树的定义及其性质 (1) 二叉树的定义二叉树的定义二叉树的五种基本形态二叉树的五种基本形态二叉树一种特殊的树型结构，特点是树中每个结点只有两棵二叉树一种特殊的树型结构，特点是树中每个结点只有两棵子树，且子树有左右之分，次序不能颠倒。子树，且子树有左右之分，次序不能颠倒。 空二叉树空二叉树 仅有仅有根结点根结点 右子树右子树为空为空 左子树左子树为空为空左右子树左右子树均非空均非空因为树的每个结点的度不同，存储困难，使对树的处理算法因为树的每个结点的度不同，存储困难，使对树的处理算法很复杂。所以引出二叉树的讨论。很复杂。所以引出二叉树的讨论。2022-5-110 二叉数是二叉数是n(nn(

6、n 0)0)个结点的有限集合。它或为空个结点的有限集合。它或为空数数(n=0),(n=0),或由一个根结点和两棵分别称为根的左子或由一个根结点和两棵分别称为根的左子树和右子树的互不相交的二叉数组成。树和右子树的互不相交的二叉数组成。 特别要注意：特别要注意：二叉数不是树的特殊情况。二叉数不是树的特殊情况。a aa ab bb b两棵不同的二叉数两棵不同的二叉数2022-5-111A、 二叉树的第i层上至多有2 i-1（i 1）个结点。(2) 二叉树的基本性质二叉树的基本性质423167891011121314155第三层上第三层上(i=3)(i=3)，有，有2 23-13-1=4=4个节点。个

7、节点。第四层上第四层上(i=4)(i=4)，有，有2 24-14-1=8=8个节点。个节点。2022-5-112A、 二叉树的第i层上至多有2 i-1（i 1）个结点。 B、 深度为h的二叉树中至多含有2h-1个结点。(2) 二叉树的基本性质二叉树的基本性质423167891011121314155此树的深度此树的深度h=4h=4，共有，共有2 24 4-1=15-1=15个节点。个节点。2022-5-113A、 二叉树的第i层上至多有2 i-1（i 1）个结点。B、 深度为h的二叉树中至多含有2h-1个结点。C、 若在任意一棵二叉树中，有n0个叶子结点， 有n2个度为2的结点，则：n0=n2

8、+1(2) 二叉树的基本性质二叉树的基本性质423167891011121314155n n0 0=8=8n n2 2=7=72022-5-114（3）满二叉树）满二叉树423167891011121314155特点：每一层上都含有最大结点数。特点：每一层上都含有最大结点数。2022-5-1154231678910 11125 非完全二叉树非完全二叉树（4）完全二叉树4231678910 11125 完全二叉树完全二叉树特点：除最后一层外，每一层都取最大结点数，特点：除最后一层外，每一层都取最大结点数，最后一层结点都集中在该层最左边的若干位置。最后一层结点都集中在该层最左边的若干位置。2022

9、-5-116（5）树与二叉树的区别）树与二叉树的区别A树的结点个数至少为树的结点个数至少为1，而二叉树的结点个数可以为，而二叉树的结点个数可以为0。B树中结点的最大度数没有限制，二叉树结点最大度数为树中结点的最大度数没有限制，二叉树结点最大度数为2。C树的结点无左、右之分，二叉树的结点子树有明确的左、右之分。树的结点无左、右之分，二叉树的结点子树有明确的左、右之分。 树 二叉树2022-5-117性质性质1：二叉树的第二叉树的第i层上至多有层上至多有2 i-1（i 1）个结点。个结点。证明：根据二叉树的特点，结论是显然的。证明：根据二叉树的特点，结论是显然的。性质性质2：深度为深度为h的二叉树

10、中至多含有的二叉树中至多含有2h-1个结点。个结点。证明：深度为证明：深度为m的二叉树最多有的二叉树最多有m层，根据性质层，根据性质1，只要将第，只要将第1层到第层到第m层的最大结点数相加，就可得到整个二叉树中结点的层的最大结点数相加，就可得到整个二叉树中结点的最大值。最大值。21-1 + 2 2-1+ 2 m-1 = 2 m-1 性质性质3：度为：度为0的结点总比度为的结点总比度为2的结点多一个。的结点多一个。设：有设：有n0个叶子结点，有个叶子结点，有n1个度为个度为1的结点，有的结点，有n2个度为个度为2的结点，的结点， 则二叉树中结点总数为则二叉树中结点总数为：n=n0+n1+ n2

11、设所有进入分支的总数为设所有进入分支的总数为m,则总的结点个数为：则总的结点个数为：n=m+1总的射出分支与总的进入分支数相等：总的射出分支与总的进入分支数相等：m= n1+2 n2 因此：因此： n0+n1+ n2 = n1+2 n2 +1 所以：所以： n0= n2+1 2022-5-118（5）树与二叉树的区别）树与二叉树的区别A 树的结点个数至少为树的结点个数至少为1，而二叉树的结点个数可以为而二叉树的结点个数可以为0。B树中结点的最大度数没有限制，二叉树结点最大度数为树中结点的最大度数没有限制，二叉树结点最大度数为2。C树的结点子树无左、右之分，二叉树的结点子树有明确的左、树的结点子

12、树无左、右之分，二叉树的结点子树有明确的左、 右之分。右之分。 二叉树二叉树树树2022-5-1192、二叉树的存储结构、二叉树的存储结构 (2) 链式存储结构链式存储结构T16若父结点在数组中若父结点在数组中i下标处，其左孩子在下标处，其左孩子在2*i处，右孩子在处，右孩子在2*i+1处。处。11 A B c F E D 1 2 4 8 910 5 6 3 712131415(1) 顺序存储结构顺序存储结构(1) 顺序存储结构顺序存储结构2h-1= 24-1 = 15用一组连续的存储单元存放二叉树用一组连续的存储单元存放二叉树的数据元素。结点在数组中的相对的数据元素。结点在数组中的相对位置蕴

13、含着结点之间的关系。位置蕴含着结点之间的关系。0000FE000DC0BA15141312111098765432100一般二叉树必须按完全二叉树的形式存储，将造成存储的浪费。一般二叉树必须按完全二叉树的形式存储，将造成存储的浪费。2022-5-120(2) 链式存储结构链式存储结构lchildDatarchildADBCEF图为一般二叉图为一般二叉树的二叉链表树的二叉链表结构结构AECBDF每个结点由数据域、左指针域和右指针域组成。每个结点由数据域、左指针域和右指针域组成。2022-5-121链式存储结构的描述：链式存储结构的描述：Typedef struct BiTNode int dat

14、a; Struct BiTNode *lchild, *rchild; BiTNode, * BiTree;lchildDatarchildlchildDatarchildlchildDatarchild2022-5-1223、将树和森林转换为二叉树、将树和森林转换为二叉树 由于二叉树可以用二叉链表表示，为了使一般树也能由于二叉树可以用二叉链表表示，为了使一般树也能用二叉链表表示，必须找出树与二叉树之间的关系。用二叉链表表示，必须找出树与二叉树之间的关系。 这样，给定一棵树，可以找到唯一的一棵二叉树与之这样，给定一棵树，可以找到唯一的一棵二叉树与之对应。对应。（1）树转换为二叉树）树转换为二叉

15、树方法：方法： 对每个孩子进行从左到右的排序；对每个孩子进行从左到右的排序； 在兄弟之间加一条连线；在兄弟之间加一条连线； 对每个结点，除了左孩子外，去除其与其余孩子对每个结点，除了左孩子外，去除其与其余孩子之间的联系；之间的联系； 以根结点为轴心，将整个树顺时针转以根结点为轴心，将整个树顺时针转45度。度。2022-5-123 I A B C DE F G H(b) A B CD E G H FI(a)树转换为二叉树树转换为二叉树ABEFCDGHI(d)ABCDEFGHI(c)2022-5-124 （2） 森林转换为二叉树森林转换为二叉树ADCBEFHIGJEFADCBHIGJADCBEFH

16、IGJADCBEFHIGJ方法：方法： 将各棵树分别转成二叉树；将各棵树分别转成二叉树； 把每棵树的根结点用线连起来；把每棵树的根结点用线连起来； 以第一棵树的根结点作为二叉树以第一棵树的根结点作为二叉树的根结点，按顺时针方向旋转。的根结点，按顺时针方向旋转。2022-5-1254、 二叉树的遍历二叉树的遍历 查找某个结点，或对二叉树中全部结点进行某种处理，就需要遍查找某个结点，或对二叉树中全部结点进行某种处理，就需要遍历。历。（1）遍历定义及遍历算法）遍历定义及遍历算法 遍历是指按某条搜索路线寻访树中每个结点，且每个结点只被访遍历是指按某条搜索路线寻访树中每个结点，且每个结点只被访问一次。问

17、一次。 按先左后右的原则，一般使用三种遍历：按先左后右的原则，一般使用三种遍历：先序遍历先序遍历(D L R): 访问根结点，按先序遍历左子树，按先序遍历右子树。访问根结点，按先序遍历左子树，按先序遍历右子树。中序遍历中序遍历(L D R): 按中序遍历左子树，访问根结点，按中序遍历右子树。按中序遍历左子树，访问根结点，按中序遍历右子树。后序遍历后序遍历(L R D): 按后序遍历左子树，按后序遍历右子树，访问根结点。按后序遍历左子树，按后序遍历右子树，访问根结点。 二叉树为空时，执行空操作，即空二叉树已遍历完。二叉树为空时，执行空操作，即空二叉树已遍历完。2022-5-126 （2）遍历算法

18、遍历算法先序遍历：先序遍历：D L R中序遍历：中序遍历：L D R后序遍历：后序遍历：L R DADBCT1T2T3D L RAD L RD L RBDCD L R以先序遍历以先序遍历D L RD L R为例演示遍历过程为例演示遍历过程 ABDCBDAC DBCA2022-5-127Void PreOderTraverse(BiTree T)if(T! =NULL) printf (T-data); PreOrderTraverse(T-lchild); PreOrderTraverser(T-rchild); /*先序遍历先序遍历*/主程序主程序Pre( T )返回返回pre(T R);返

19、回返回pre(T R);ACBDTBprintf(B);pre(T L);BTAprintf(A);pre(T L);ATDprintf(D);pre(T L);DTCprintf(C);pre(T L);C返回T左是空返回左是空返回pre(T R);T左是空返回左是空返回T右是空返回右是空返回T左是空返回左是空返回T右是空返回右是空返回pre(T R);2022-5-128中序遍历二叉树的递归算法：中序遍历二叉树的递归算法： void inOrderTraverse(BiTree T) if(T!=NULL) inOrderTraverse(T-lchild); printf(T-data)

20、; inOrderTraverse(T-rchild); 后序遍历二叉树的递归算法：后序遍历二叉树的递归算法： void PostOrderTraverse(BiTree T) if(T!=NULL) PostOrderTraverse(T-lchild); PostOrderTraverse(T-rchild); printf(T-data); 2022-5-129 （3）遍历二叉树的应用）遍历二叉树的应用 1) 建立一棵二叉树建立一棵二叉树 (在遍历过程生成结点，建立二叉在遍历过程生成结点，建立二叉树的存储结构，用链式存储结构）树的存储结构，用链式存储结构）BiTree CreatBiTr

21、ee() BiTree T; scanf(&ch); if(ch= = ) T=NULL; else T=(BiTNode )malloc(sizeof(BiTNode); T-data=ch; /*生成根结点生成根结点*/ T-lchild= CreatBiTree( ); /*构造左子树构造左子树*/ T-rchild= CreatBiTree(); /*构造右子树构造右子树*/ return (T) ;ADBCA B D CA B D C 按先序遍历按先序遍历2022-5-130ch=ATTAcreat(T L)T= , Creat(T) 返回creat(T R)Tch=D|=返

22、回creat(T R)D=Tch=返回ch=DTTDcreat(T L)=|creat(T R)ch=CTTCcreat(T L)+ch=BTTBcreat(T L)Tch=BTCch=+返回creat(T R)TCch=+返回ATABABD|=ABDABDC+BAABDC2022-5-131（2）统计二叉树中叶子结点的个数）统计二叉树中叶子结点的个数 方法：对二叉树进行遍历，判断被访问的结点是否叶方法：对二叉树进行遍历，判断被访问的结点是否叶子结点，若是叶子结点，则将计数器加子结点，若是叶子结点，则将计数器加1。实现算法：实现算法：int countleaf(BiTree) int n1,n

23、2; if (T= =NULL) return(0); else if (T-lchild= =NULL) & (T-rchild= =NULL) return(1); else n1=countleaf (T-lchild); n2=countleaf (T-rchild); return( n1+n2); 2022-5-132作业：作业：P77第第2925题题第第27题、第题、第29题题2022-5-133 A C G D H I J M B E L K F作业作业20解解AK、L、F、G、M、I、J CE、FE、F、G、H、I、J42022-5-134ABCDEFKLGHIJM2

24、022-5-135 void change(NODE *T)NODE *m; if(T!=NULL) m=T-L T-L=T-R; T-R=m; change(T-L); change(T-R);typedef struct nodeint data；struct node *L，*R；NODE；ABCDACBDACBD21.试以二叉链表作为存储结构，将二试以二叉链表作为存储结构，将二叉树中所有结点的左右子树进行交换。叉树中所有结点的左右子树进行交换。2022-5-13623. n24. 12 i-125. CDBFGEA27. 82022-5-137第第2525题题: :先序遍历中的第一个元

25、素必为二叉树的根结点。先序遍历中的第一个元素必为二叉树的根结点。中序遍历中的根结点恰为左、右子树的分界点。中序遍历中的根结点恰为左、右子树的分界点。先序遍历先序遍历:ABCDEFG :ABCDEFG 中序遍历中序遍历:CBDAFEG:CBDAFEGC D B F G E AC D B F G E A2022-5-138int AA（R，e） P=R；int n=1； while（P-data!=e | p-next=NULL) p=p-next; n=n+1; if(p-next=NULL & P-data!=e) printf(“ERRORn”); return(n);关系运算符：关

26、系运算符： = = = !=逻辑运算符：逻辑运算符： & | !错在哪？错在哪？2022-5-139 阅读程序并回答问题：（1） 程序执行了什么功能？（2） 针对右面的图，写出程序的运行结果。 typedef struct BiTNode int data; struct BiTNode *lchild,*rchild;BiTNode,*BiTree; int preprn(BiTtree T) if(T-lchild!=NULL)&（T-rchild!=NULL）) printf(T-data);preprn(T-lchild);preprn(T-rchild); else

27、return OK;abdecgfhia b c g2022-5-14011月月20日上机作业：日上机作业：作业作业1： 用用C语言编写递归和非递归语言编写递归和非递归计算计算n!程序。程序。2022-5-141递归算法递归算法 ：int F(int n) int m; if(n=0) m=1; else m=n*F(n-1); return (m);非递归算法：非递归算法：int F(int n) int f1=1,s=1; if(n=0) return 1; while(sdata data)if (pb-data data)q-data = pb-data;q-data = pb-dat

28、a;p pq qai-1a1aianPab2b1Pb2022-5-147合并算法如下：合并算法如下：JD JD * * comlink(JD comlink(JD * *pa,JD pa,JD * *pb)pb) JD JD * *p,p,* *q,q,* *pc;pc; pc=(JD pc=(JD* *)malloc(sizeof(JD);)malloc(sizeof(JD);pcpcp=pc;p=pc;While(pa!=NULL & pb!=NULL)While(pa!=NULL & pb!=NULL)q=(JDq=(JD* *)malloc(sizeof(JD);)ma

29、lloc(sizeof(JD);if (pb-data data)if (pb-data data)q-data = pb-data;q-data = pb-data;p pq qai-1a1aianPab2b1Pbb12022-5-148合并算法如下：合并算法如下：JD JD * * comlink(JD comlink(JD * *pa,JD pa,JD * *pb)pb) JD JD * *p,p,* *q,q,* *pc;pc; pc=(JD pc=(JD* *)malloc(sizeof(JD);)malloc(sizeof(JD);pcpcp=pc;p=pc;While(pa!=N

30、ULL & pb!=NULL)While(pa!=NULL & pb!=NULL)q=(JDq=(JD* *)malloc(sizeof(JD);)malloc(sizeof(JD);if (pb-data data)if (pb-data data)q-data = pb-data;q-data = pb-data;p pq qb1pb=pb-link;pb=pb-link;ai-1a1aianPab2b1Pb2022-5-149合并算法如下：合并算法如下：JD JD * * comlink(JD comlink(JD * *pa,JD pa,JD * *pb)pb) JD

31、JD * *p,p,* *q,q,* *pc;pc; pc=(JD pc=(JD* *)malloc(sizeof(JD);)malloc(sizeof(JD);pcpcp=pc;p=pc;While(pa!=NULL & pb!=NULL)While(pa!=NULL & pb!=NULL)q=(JDq=(JD* *)malloc(sizeof(JD);)malloc(sizeof(JD);if (pb-data data)if (pb-data data)q-data = pb-data;q-data = pb-data;p pq qb1pb=pb-link;pb=pb-l

32、ink;ai-1a1aianPab2b1Pb2022-5-150pcpcElse q-data = pa-data;Else q-data = pa-data;pa=pa-link;pa=pa-link;p pq qai-1a1aianPab2b1Pba12022-5-151pcpcElse q-data = pa-data;Else q-data = pa-data;pa=pa-link;pa=pa-link;if (pa-data= =pb-data)if (pa-data= =pb-data)pb = pb-link;pb = pb-link;p pq qai-1a1aianPab2b1

33、Pba12022-5-152pcpcElse q-data = pa-data;Else q-data = pa-data;pa=pa-link;pa=pa-link;p-link=q;p-link=q;if (pa-data= =pb-data)if (pa-data= =pb-data)pb = pb-link;pb = pb-link;p pq qai-1a1aianPab2b1Pba12022-5-153pcpcElse q-data = pa-data;Else q-data = pa-data;pa=pa-link;pa=pa-link;p-link=q;p-link=q;if (

34、pa-data= =pb-data)if (pa-data= =pb-data)pb = pb-link;pb = pb-link;p pq qai-1a1aianPab2b1Pba1p=q;p=q; 2022-5-154pcpcElse q-data = pa-data;Else q-data = pa-data;pa=pa-link;pa=pa-link;p-link=q;p-link=q;if (pa-data= =pb-data)if (pa-data= =pb-data)pb = pb-link;pb = pb-link;p pq qai-1a1aianPab2b1Pba1p=q;p

35、=q; 2022-5-155pcpcElse q-data = pa-data;Else q-data = pa-data;pa=pa-link;pa=pa-link;p-link=q;p-link=q;if (pa-data= =pb-data)if (pa-data= =pb-data)pb = pb-link;pb = pb-link;p pq qai-1a1aianPab2b1Pba1p=q;p=q; 2022-5-156pcpcElse q-data = pa-data;Else q-data = pa-data;pa=pa-link;pa=pa-link;p-link=q;p-li

36、nk=q;if (pa-data= =pb-data)if (pa-data= =pb-data)pb = pb-link;pb = pb-link;p pq qai-1a1aianPab2b1Pba1p=q;p=q; a22022-5-157pcpcElse q-data = pa-data;Else q-data = pa-data;pa=pa-link;pa=pa-link;p-link=q;p-link=q;if (pa-data= =pb-data)if (pa-data= =pb-data)pb = pb-link;pb = pb-link;p pq qai-1a1aianPab2

37、b1Pba1p=q;p=q; a22022-5-158pcpcElse q-data = pa-data;Else q-data = pa-data;pa=pa-link;pa=pa-link;p-link=q;p-link=q;if (pa-data= =pb-data)if (pa-data= =pb-data)pb = pb-link;pb = pb-link;p pq qai-1a1aianPab2b1Pba1p=q;p=q; a22022-5-159pcpcElse q-data = pa-data;Else q-data = pa-data;pa=pa-link;pa=pa-lin

38、k;p-link=q;p-link=q;if (pa-data= =pb-data)if (pa-data= =pb-data)pb = pb-link;pb = pb-link;p pq qai-1a1aianPab2b1Pba1p=q;p=q; a22022-5-160pcpcElse q-data = pa-data;Else q-data = pa-data;pa=pa-link;pa=pa-link;p-link=q;p-link=q;if (pa-data= =pb-data)if (pa-data= =pb-data)pb = pb-link;pb = pb-link;p pq

39、qai-1a1aianPab2b1Pba1p=q;p=q; a22022-5-161pcpcElse q-data = pa-data;Else q-data = pa-data;pa=pa-link;pa=pa-link;p-link=q;p-link=q;if (pa-data= =pb-data)if (pa-data= =pb-data)pb = pb-link;pb = pb-link;p pq qai-1a1aianPab2b1Pba1p=q;p=q; a2b12022-5-162pcpcElse q-data = pa-data;Else q-data = pa-data;pa=

40、pa-link;pa=pa-link;p-link=q;p-link=q;if (pa-data= =pb-data)if (pa-data= =pb-data)pb = pb-link;pb = pb-link;p pq qai-1a1aianPab2b1Pba1p=q;p=q; a2b12022-5-163pcpcElse q-data = pa-data;Else q-data = pa-data;pa=pa-link;pa=pa-link;p-link=q;p-link=q;if (pa-data= =pb-data)if (pa-data= =pb-data)pb = pb-link

41、;pb = pb-link;p pq qai-1a1aianPab2b1Pba1p=q;p=q; a2b12022-5-164While (pa!=nNULLWhile (pa!=nNULL)/)/* *如果如果papa链表还未到表尾，复制剩余部分链表还未到表尾，复制剩余部分* */ /q=(JD q=(JD * *)malloc(sizeof(JD);)malloc(sizeof(JD); q-data = pa-data; q-data = pa-data; pa=pa-link; pa=pa-link; p-link=q; p-link=q; p=q; p=q; 2022-5-165Wh

42、ile (pb!=nNULLWhile (pb!=nNULL)/)/* *如果如果pbpb链表还未到表尾，复制剩余部分链表还未到表尾，复制剩余部分* */ /q=(JD q=(JD * *)malloc(sizeof(JD);)malloc(sizeof(JD); q-data = pb-data; q-data = pb-data; pb=pb-link; pb=pb-link; p-link=q; p-link=q; p=q; p=q; 2022-5-166pcpcp-link=NULL;p-link=NULL;p pq qa1a2b12022-5-167pcpcp-link=NULL;p

43、-link=NULL;p=pc;p=pc;p pq qa1a2b12022-5-168pcpcp-link=NULL;p-link=NULL;p=pc;p=pc;pc=p-link;pc=p-link;p pq qa1a2b12022-5-169pcpcp-link=NULL;p-link=NULL;p=pc;p=pc;pc=p-link;pc=p-link;free(p);free(p);p pq qa1a2b12022-5-170pcpcp-link=NULL;p-link=NULL;p=pc;p=pc;return(pc);return(pc); pc=p-link;pc=p-link;

44、free(p);free(p);q qa1a2b12022-5-171合并算法程序如下：合并算法程序如下：JD JD * * comlink(JD comlink(JD * *pa,JD pa,JD * *pb)pb) JD JD * *p p，* *q q，* *pcpc； pc=(JDpc=(JD* *)malloc(sizeof(JD)malloc(sizeof(JD)；p=pcp=pc；While(pa!=NULL & pb!=NULL)While(pa!=NULL & pb!=NULL)q=(JDq=(JD* *)malloc(sizeof(JD)malloc(siz

45、eof(JD)；if (pb-data data)if (pb-data data)q-data = pb-dataq-data = pb-data； pb = pb-link pb = pb-link； Else q-data = pa-dataElse q-data = pa-data；pa=pa-linkpa=pa-link；p-link=qp-link=q；if (pa-data= =pb-data) pb = pb-linkif (pa-data= =pb-data) pb = pb-link； p=qp=q； 2022-5-172While (pa!=nNULLWhile (pa!

46、=nNULL)/)/* *如果如果papa链表还未到表尾，复制剩余部分链表还未到表尾，复制剩余部分* */ /q=(JD q=(JD * *)malloc(sizeof(JD);)malloc(sizeof(JD); q-data = pa-data; q-data = pa-data; pa=pa-link; pa=pa-link; p-link=q; p-link=q; p=q; p=q; 2022-5-173While (pb!=nNULLWhile (pb!=nNULL)/)/* *如果如果pbpb链表还未到表尾，复制剩余部分链表还未到表尾，复制剩余部分* */ /q=(JD q=(J

47、D * *)malloc(sizeof(JD);)malloc(sizeof(JD); q-data = pb-data; q-data = pb-data; pb=pb-link; pb=pb-link; p-link=q; p-link=q; p=q; p=q; 2022-5-174p-link=NULL;p-link=NULL;p=pc;p=pc;return(pc);return(pc); pc=p-link;pc=p-link;free(p);free(p);2022-5-175下面介绍链表的创建。下面介绍链表的创建。2022-5-176Linklist creat()Linklis

48、t creat()linklist head,p1,p2;linklist head,p1,p2;n=0n=0；p1=p2=(struct lnodep1=p2=(struct lnode* *)malloc(LEN)malloc(LEN)；scanf(“%d”,&p1-data)scanf(“%d”,&p1-data)；head-next=NULL;head-next=NULL;while(p1-data!0)while(p1-data!0) n=n+1 n=n+1； if(n=1) head-next=p1if(n=1) head-next=p1； else p2-next

49、=p1else p2-next=p1； p2=p1p2=p1；p1=(struct lnodep1=(struct lnode* *)malloc(LEN)malloc(LEN)； scanf(%d”,&p1-data)scanf(%d”,&p1-data)；p2-next=NULLp2-next=NULL； return(head)return(head)； 创立具有头指针的链表创立具有头指针的链表2022-5-177Linklist creat()Linklist creat() linklist head,p1,p2linklist head,p1,p2; ;n=0n=0

50、；p1=p2=(struct lnodep1=p2=(struct lnode* *)malloc(LEN)malloc(LEN)；scanf(“%d”,&p1-data)scanf(“%d”,&p1-data)；head-next=NULL;head-next=NULL;while(p1-data!0)while(p1-data!0) n=n+1 n=n+1； if(n=1) head-next=p1if(n=1) head-next=p1； else p2-next=p1else p2-next=p1； p2=p1p2=p1；p1=(struct lnodep1=(stru

51、ct lnode* *)malloc(LEN)malloc(LEN)； scanf(%d”,&p1-data)scanf(%d”,&p1-data)；p2-next=NULLp2-next=NULL； return(head)return(head)； HeadHeadp1p1p2p22022-5-178Linklist creat()Linklist creat() linklist head,p1,p2linklist head,p1,p2; ;n=0n=0；p1=p2=(struct lnodep1=p2=(struct lnode* *)malloc(LEN)mallo

52、c(LEN)；scanf(“%d”,&p1-data)scanf(“%d”,&p1-data)；head-next=NULL;head-next=NULL;while(p1-data!0)while(p1-data!0) n=n+1 n=n+1； if(n=1) head-next=p1if(n=1) head-next=p1； else p2-next=p1else p2-next=p1； p2=p1p2=p1；p1=(struct lnodep1=(struct lnode* *)malloc(LEN)malloc(LEN)； scanf(%d”,&p1-data)

53、scanf(%d”,&p1-data)；p2-next=NULLp2-next=NULL； return(head)return(head)； HeadHeadp1p1p2p2n=0n=02022-5-179Linklist creat()Linklist creat() linklist head,p1,p2linklist head,p1,p2; ;n=0n=0；p1=p2=(struct lnodep1=p2=(struct lnode* *)malloc(LEN)malloc(LEN)；scanf(“%d”,&p1-data)scanf(“%d”,&p1-dat

54、a)；head-next=NULL;head-next=NULL;while(p1-data!0)while(p1-data!0) n=n+1 n=n+1； if(n=1) head-next=p1if(n=1) head-next=p1； else p2-next=p1else p2-next=p1； p2=p1p2=p1；p1=(struct lnodep1=(struct lnode* *)malloc(LEN)malloc(LEN)； scanf(%d”,&p1-data)scanf(%d”,&p1-data)；p2-next=NULLp2-next=NULL； ret

55、urn(head)return(head)； HeadHeadp1p1p2p2n=0n=02022-5-180Linklist creat()Linklist creat() linklist head,p1,p2linklist head,p1,p2; ;n=0n=0；p1=p2=(struct lnodep1=p2=(struct lnode* *)malloc(LEN)malloc(LEN)；scanf(“%d”,&p1-data)scanf(“%d”,&p1-data)；head-next=NULL;head-next=NULL;while(p1-data!0)whil

56、e(p1-data!0) n=n+1 n=n+1； if(n=1) head-next=p1if(n=1) head-next=p1； else p2-next=p1else p2-next=p1； p2=p1p2=p1；p1=(struct lnodep1=(struct lnode* *)malloc(LEN)malloc(LEN)； scanf(%d”,&p1-data)scanf(%d”,&p1-data)；p2-next=NULLp2-next=NULL； return(head)return(head)； HeadHeadp1p1p2p2n=0n=015152022

57、-5-181Linklist creat()Linklist creat() linklist head,p1,p2linklist head,p1,p2; ;n=0n=0；p1=p2=(struct lnodep1=p2=(struct lnode* *)malloc(LEN)malloc(LEN)；scanf(“%d”,&p1-data)scanf(“%d”,&p1-data)；head-next=NULLhead-next=NULL; ;while(p1-data!0)while(p1-data!0) n=n+1 n=n+1； if(n=1) head-next=p1if

58、(n=1) head-next=p1； else p2-next=p1else p2-next=p1； p2=p1p2=p1；p1=(struct lnodep1=(struct lnode* *)malloc(LEN)malloc(LEN)； scanf(%d”,&p1-data)scanf(%d”,&p1-data)；p2-next=NULLp2-next=NULL； return(head)return(head)； HeadHeadp1p1p2p215n=0n=02022-5-182Linklist creat()Linklist creat() linklist he

59、ad,p1,p2linklist head,p1,p2; ;n=0n=0；p1=p2=(struct lnodep1=p2=(struct lnode* *)malloc(LEN)malloc(LEN)；scanf(“%d”,&p1-data)scanf(“%d”,&p1-data)；head-next=NULLhead-next=NULL; ;while(p1-data!0)while(p1-data!0) n=n+1n=n+1； if(n=1) head-next=p1if(n=1) head-next=p1； else p2-next=p1else p2-next=p1；

60、 p2=p1p2=p1；p1=(struct lnodep1=(struct lnode* *)malloc(LEN)malloc(LEN)； scanf(%d”,&p1-data)scanf(%d”,&p1-data)；p2-next=NULLp2-next=NULL； return(head)return(head)； HeadHeadp1p1p2p215n=1n=12022-5-183Linklist creat()Linklist creat() linklist head,p1,p2linklist head,p1,p2; ;n=0n=0；p1=p2=(struct lnodep1=p2=(struct lnode* *)malloc(LEN)malloc(LEN)；scanf(“%d”,&p1-data)scanf(“%d”,&p1-data)；head-next=NULL;head-next=NULL;while(p1-data!0)while(p1-data!0) n=n+1 n=n+1； if(if(n= =1n= =1) ) head-next=