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

《数据结构与算法问题分析及源代码之单链表.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、单链表1题目编写一个程序，实现链表的各种基本运算，包括：链表操作：初始化链表、输出链表、输出链表长度和释放链表链表元素操作：插入元素、删除元素、输出元素（注意元素的位置）2目标熟悉单链表的定义及其基本操作的实现3设计思想链表由多个结点通过next指针连接成一个完整的数据结构，每个几点包括一个数据域和一个指向下一个结点的next指针。通过对指针的改写与结点的增减，我们可以实现单链表的插入、删除、输入、输出、求长等操作。4算法描述（1）初始化链表：输入元素个数n，分配n个结点空间，输入元素值，按元素顺序初始化next指针，使之连接成串，尾指针赋值NULL。（2）输出链表：从表头开始沿next指针遍

2、历各结点，每次访问结点输出结点数据值，直至next为空。（3）输出链表长度：从表头开始沿next指针遍历各结点，每次访问结点计数器加一，直至next为空，返回计数器值。（4）释放链表：沿next指针从前向后依次释放结点，直至next指空。（5）插入元素：指针沿next指向移动指定位，新分配一个空间并存入数据，其next赋值为当前指针指向结点的next，修改当前指针指向结点的next指向新加结点。（6）删除元素：指针沿next指向移动指定位，修改待删结点的前一结点的next指针指向待删结点的下一结点，保存数值，释放删除结点。（7）输出元素：指针沿next指向移动指定位，指针指向结点数据区，读出数

3、值返回。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)查找单链表的元素eLocateList(LinkList*L,ElemTypee)在单链表中第i个位置上插入元素eListInsert(LinkList*&L,int,i,ElemTypee)

4、删除单链表中的第i个元素ListDelete(LinkList*&L,int,i,ElemType&e)6源程序#include#includetypedefstructLNode{intdata;structLNode*next;}LNode,*LinkList;LinkListInitList_Link(LinkListL){L=(LinkList)malloc(sizeof(LNode));L->data=0;L->next=NULL;returnL;}voidCreatelist(LinkListL){intn;inti;inttemp;LinkL

5、istT;printf("输入链表元素个数:");scanf("%d",&n);L->data=n;printf("输入元素值:");T=L;for(i=n;i>0;i--){LinkListp=(LinkList)malloc(sizeof(LNode));scanf("%d",&temp);p->next=T->next;p->data=temp;T->next=p;T=p;L->data++;}printf("成功建立链表");}voidDestroyList_Link(LinkListL){LinkListp=L,q=L;while(p){p=p->next;free(q);q=p

6、;}printf("成功释放!");}voidDisplayList_Link(LinkListL){LinkListp=L->next;if(ListEmpty_Link(L)==1)return;printf("链表为：");while(p){printf("%d",p->data);p=p->next;}}intListEmpty_Link(LinkListL){if(L->data==0){printf("链表为空");return1;}elsereturn0;}voidMainListEmpty_Link(LinkListL){if(L->data==0)printf("链表

7、为空");elseprintf("链表非空");}voidListLength_Link(LinkListL){LinkListp=L->next;inti=0;while(p){p=p->next;i++;}printf("链表长为：%d",i);}voidListInsert_Link(LinkListL){inti;inte;LinkLists;LinkListp=L;intj=