数据结构与算法问题分析及源代码之单链表.doc

单链表 1 题目 编写一个程序，实现链表的各种基本运算，包括： 链表操作：初始化链表、输出链表、输出链表长度和释放链表 链表元素操作：插入元素、删除元素、输出元素（注意元素的位置） 2 目标 熟悉单链表的定义及其基本操作的实现 3 设计思想 链表由多个结点通过next指针连接成一个完整的数据结构，每个几点包括一个数据域和一个指向下一个结点的next指针。通过对指针的改写与结点的增减，我们可以实现单链表的插入、删除、输入、输出、求长等操作。 4 算法描述 初始化链表：输入元素个数n，分配n个结点空间，输入元素值，按元素顺序初始化next指针，使之连接成串，尾指针赋值NULL。 输出链表：从表头开始沿next指针遍历各结点，每次访问结点输出结点数据值，直至next为空。 输出链表长度：从表头开始沿next指针遍历各结点，每次访问结点计数器加一，直至next为空，返回计数器值。 释放链表：沿next指针从前向后依次释放结点，直至next指空。 插入元素：指针沿next指向移动指定位，新分配一个空间并存入数据，其next赋值为当前指针指向结点的next，修改当前指针指向结点的next指向新加结点。 删除元素：指针沿next指向移动指定位，修改待删结点的前一结点的next指针指向待删结点的下一结点，保存数值，释放删除结点。 输出元素：指针沿next指向移动指定位，指针指向结点数据区，读出数值返回。 5 程序结构图 6 源程序 #include stdio.h #include stdlib.h typedef struct LNode { int data; struct LNode *next; }LNode,*LinkList; LinkList InitList_Link(LinkList L) { L=(LinkList)malloc(sizeof(LNode)); L-data = 0; L-next = NULL; return L; } void Createlist(LinkList L) { int n; int i; int temp; LinkList T; printf(输入链表元素个数:); scanf(%d,n); L-data=n; printf(输入元素值:\n); T=L; for (i=n;i0;i--) { LinkList p=(LinkList)malloc(sizeof(LNode)); scanf(%d,temp); p-next=T-next; p-data = temp; T-next=p; T=p; L-data++; } printf(成功建立链表); } void DestroyList_Link(LinkList L) { LinkList p = L,q = L; while(p) { p = p-next; free(q); q = p; } printf(成功释放!); } void DisplayList_Link(LinkList L) { LinkList p=L-next; if(ListEmpty_Link(L)==1) return; printf(链表为：\n); while(p) { printf(%d ,p-data); p=p-next; } } int ListEmpty_Link(LinkList L) { if(L-data==0) { printf(链表为空\n); return 1; } else return 0; } void MainListEmpty_Link(LinkList L) { if(L-data==0) printf(链表为空\n); else printf(链表非空\n); } void ListLength_Link(LinkList L) { LinkList p = L-next; int i=0; w