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

单链表1 题目 编写一个程序，实现链表的各种基本运算，包括：链表操作：初始化链表、输出链表、输出链表长度和释放链表链表元素操作：插入元素、删除元素、输出元素（注意元素的位置）2 目标 熟悉单链表的定义及其基本操作的实现3 设计思想链表由多个结点通过next指针连接成一个完整的数据结构，每个几点包括一个数据域和一个指向下一个结点的next指针。通过对指针的改写与结点的增减，我们可以实现单链表的插入、删除、输入、输出、求长等操作。4 算法描述（1） 初始化链表：输入元素个数n，分配n个结点空间，输入元素值，按元素顺序初始化next指针，使之连接成串，尾指针赋值NULL。（2） 输出链表：从表头开始沿next指针遍历各结点，每次访问结点输出结点数据值，直至next为空。（3） 输出链表长度：从表头开始沿next指针遍历各结点，每次访问结点计数器加一，直至next为空，返回计数器值。（4） 释放链表：沿next指针从前向后依次释放结点，直至next指空。（5） 插入元素：指针沿next指向移动指定位，新分配一个空间并存入数据，其next赋值为当前指针指向结点的next，修改当前指针指向结点的next指向新加结点。（6） 删除元素：指针沿next指向移动指定位，修改待删结点的前一结点的next指针指向待删结点的下一结点，保存数值，释放删除结点。（7） 输出元素：指针沿next指向移动指定位，指针指向结点数据区，读出数值返回。5 程序结构图主程序main初始化InitList(LinkList *&L)释放单链表DstroryList(LinkList *&L)判断单链表是否为空ListEmpty(LinkList *L)返回单链表的元素个数ListLength(LinkList *L)输出单链表DispList(LinkList *L)获取单链表的第i个元素GetList(LinkList *L,int,i,ElemType &e)查找单链表的元素e LocateList(LinkList *L, ElemType e)在单链表中第i个位置上插入元素e ListInsert(LinkList * &L,int,i,ElemType e)删除单链表中的第i个元素ListDelete(LinkList *&L,int,i,ElemType &e)6 源程序#include #include 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; while(p) p=p-next; i+; printf(链表长为： %dn,i);void ListInsert_Link(LinkList L) int i; int e; LinkList s; LinkList p = L; int j = 0; printf(输入插入位置:); scanf(%d,&i); printf(输入插入值:); scanf(%d,&e); while(p & j next; +j; if( !p | j i-1 ) printf(Errorn); return; s = (LinkList)malloc(sizeof(LNode); s-data = e; s-next = p-next; p-next = s; printf(成功地在 %d 位置插入“ %d” n,i,e); L-data+;void GetElem_Link(LinkList L) LinkList p = L-next; int i; int j = 1; printf(输入元素位置:); scanf(%d,&i); while( p & j next; +j; if ( !p | ji ) printf(Over); return; printf(位置 %d 的元素是： %dn,i,p-data);void ListDelete_Link(LinkList L) LinkList p = L; LinkList q; int i; int temp; int j=0; printf(输入待删除元素位置:); scanf(%d,&i); while( p-next & j next; +j; if(!(p-next)|ji-1) printf(删除不成功d); return; q = p-next; p-next = q-next; temp = q-data; free(q); L-data-; printf(已删除位置 %d 元素： %d n,i,temp);void LocateElem_Link(LinkList L) LinkList p = L-n