单链表的创建和逆置单链表的建和逆置创建和逆置.ppt

操作接口：LNode *Creat(ElemType a[ ], int n) 头插法：将待插入结点插在头结点的后面 。 算法描述： first= malloc (sizeof (LNode)); first-next=NULL; 单链表的实现 数组a 35 12 24 33 42 初始化 first ∧ 操作接口：LNode *Creat(ElemType a[ ], int n) 头插法：将待插入结点插在头结点的后面 。 单链表的实现 数组a 35 12 24 33 42 算法描述： s= malloc (sizeof (LNode)); s-data=a[0]; s-next=first-next; first-next=s; 插入第一个元素结点 first ∧ 35 s ∧ 操作接口：LNode *Creat(ElemType a[ ], int n) 头插法：将待插入结点插在头结点的后面 。 单链表的实现 数组a 35 12 24 33 42 算法描述： s= malloc (sizeof (LNode)); s-data=a[1]; s-next=first-next; first-next=s; 依次插入每一个结点 12 s first 35 ∧ LNode *Creat(ElemType a[ ], int n) { first=malloc (sizeof (LNode)); first-next=NULL; for (i=0; in; i++) { s=malloc (sizeof (LNode)); s-data=a[i]; s-next=first-next; first-next=s; } } 单链表的实现 算法描述： 尾插法：将待插入结点插在终端结点的后面。 单链表的实现 操作接口：LNode *Creat(ElemType a[ ], int n) 算法描述： first= malloc (sizeof (LNode)); rear=first; 数组a 35 12 24 33 42 初始化 first rear 尾插法：将待插入结点插在终端结点的后面。 单链表的实现 操作接口：LNode *Creat(ElemType a[ ], int n) 算法描述： s=malloc (sizeof (LNode)); s-data=a[0]; rear-next=s; rear=s; 数组a 35 12 24 33 42 插入第一个元素结点 first rear 35 s rear 尾插法：将待插入结点插在终端结点的后面。 单链表的实现 操作接口：LNode *Creat(ElemType a[ ], int n) 算法描述： s=malloc (sizeof (LNode));; s-data=a[1]; rear-next=s; rear=s; 数组a 35 12 24 33 42 依次插入每一个结点 first rear 35 rear 12 s rear 尾插法：将待插入结点插在终端结点的后面。 单链表的实现 操作接口：LNode *Creat(ElemType a[ ], int n) 算法描述： rear-next=NULL; 数组a 35 12 24 33 42 最后一个结点插入后 first rear 35 rear 42 s rear ∧ LNode *Creat(ElemType a[ ], int n) { first=malloc (sizeof (LNode)); ; rear=first; for (i=0; in; i++) { s=malloc (sizeof (LNode)); ; s-data=a[i]; rear-next=s; rear=s; } rear-next=NULL; } 单链表的实现 算法描述： 启示：算法设计的一般过程 算法设计的一般步骤： 第一步：确定入口（已知条件）、出口（结果）； 第二步：根据一个小实例画出示意图； 第三步：① 正向思维：选定一个思考问题的起点，逐步提出问题、解决问题；② 逆向思维：从结论出发分析为达到这个结论应该先有什么；③ 正逆结合； 第四步：写出顶层较抽象算法，分析边界情况； 第五步：验证第四步的算法； 第六步：写出具体算法； 第七步：进一步验证，手工运行。 * *