数据结构PPT(第2章线性表)剖析.ppt

建立链表（头插法建表） 已知线性表（20，17，40，60，34），头插法创建带有头结点的单链表。 L p 20 17 40 60 34 ∧ p p p p 建立链表（头插法建表） 在链表表头插入新结点，结点次序与输入次序相反。 void CreateList_L(LinkList L, int n) { LinkList p; L=(LinkList)malloc(sizeof(LNode)); L-next = NULL; for (i=1;i=n;++i) { p=(LinkList)malloc(sizeof(LNode)); scanf(%d,p-data); p-next = L-next; L-next=p; } } 建立链表（尾插法建表） 已知线性表（20，17，40，60），尾插法创建带有头结点的单链表。 L p 20 17 ∧ p q 40 p 60 p ∧ 建立链表（尾插法建表） 将新结点插到链表尾部，须增设一个尾指针last，使其始终指向当前链表的尾结点，结点次序与输入次序相同。 void CreateList_L(LinkList L, int n) { LinkList p，last; L=(LinkList)malloc(sizeof(LNode)); last = L; for (i=1;i=n;++i) { p=(LinkList)malloc(sizeof(LNode)); scanf(%d,p-data); last-next = p; last=p; } last-next=NULL; } 合并有序链表 void MergeList_L(LinkList La,LinkList Lb,LinkList Lc) { LinkList pa,pb,pc; pa = La-next; pb= Lb-next; Lc = pc = La; while (pa pb) { if (pa-data = pb-data){ pc-next=pa; pc=pa; pa=pa-next;} else {pc-next=pb;pc=pb;pb=pb-next;} } pc-next=pa?pa:pb; free(Lb); } 合并有序链表 例如：LA＝（3,5,8,11） LB＝（2,6,9,15,20） LA 11 8 5 3 LB 20 15 9 6 2 pc pb pa ∧ ∧ LC 静态链表 静态链表的概念：用数组实现的线性链表，称为静态链表。 静态链表的类型定义 #define MAXSIZE 1000 // 链表的最大长度typedef struct{ ElemType data;  int cur; } component, SLinkList[MAXSIZE]; SLinkList是数组的类型名，该类型的数组变量是结构数组，每一数组分量包括两个域： data：用于存储线性表中结点的内容； cur： 用于存储直接后继元素在数组中的位置（下标）。 静态链表图示 设一个线性表A=(a1,a2,a3,a4) 静态链表图示 0 1 2 3 4 5 6 7 8 9 10 7 3 a4 0 5 a3 2 6 8 a1 9 10 a2 4 1 线性链表图示 NULL 1010 1024 1014 1010 1012 1014 1016 1018 1020 1022 1024 1026 a4 a3 a1 a2 静态链表与线性链表的区别？ 静态链表的有关说明 便于在不设指针类型高级程序设计中使用链表结构。 数组的一个分量表示一个结点，同时用游标代替指针指示结点在数组中的相对位置。 零分量相当于头结点，其游标指示链表第一个结点。 作插入、删除操作时不需移动元素，仅需修改游标。