单链表的定义及基本操作

1、百度文库单链表的定义及基本操作一、实验目的、意义（ 1）理解线性表中带头结点单链表的定义和逻辑图表示方法。（ 2）熟练掌握单链表的插入，删除和查询算法的设计与实现。（ 3）根据具体问题的需要， 设计出合理的表示数据的链表结构， 并设计相关算法。二、实验内容及要求说明 1：本次实验中的链表结构均为带头结点的单链表。说明 2:学生在上机实验时，需要自己设计出所涉及到的函数，同时设计多组输入数据并编写主程序分别调用这些函数，调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果，加深对有关算法的理解。具体要求：建立单链表，完成链表（带表头结点）的基本操作：建立链表、插入、删除、查找、

2、输出；其它基本操作还有销毁链表、将链表置为空表、求链表的长度、获取某位置结点的内容、搜索结点。三、实验所涉及的知识点数据结构、 C 语言语法函数、结构体类型指针、单链表（建表、初始化链表、求表长、插入、删除、查询算法）等。四、实验结果及分析（所输入的数据及相应的运行结果，运行结果要有提示信息，运行结果采用截图方式给出。）1百度文库五、总结与体会（调试程序的心得与体会，若实验课上未完成调试，要认真找出错误并分析原因等。）调试程序时，出现了许多错误。如：结构体类型指针出错，忽略了释放存储空间，对头插法建表、尾插法建表不熟悉等。另外还有一些语法上的错误。由于对所学知识点概念模糊，试验课上未能完成此次

3、上机作业。后来经过查阅教材，浏览网页等方式，才完成试验。这次试验出现错误最重要的原因就是对课本知识点理解不深刻以及编写代码时的粗心。以后要都去练习、实践，以完善自己的不足。六、程序清单 ( 包含注释 )/单链表#include<>#include<>#define OK 12百度文库#define ERROR 0typedef char ElemType;typedef int Status;/线性表的单链表的存储结构typedef struct LNodeElemType data;struct LNode *next;LNode,*LinkList;/LinkLis

4、t为结构体类型的指针，可以直接定义变量，比如LinkList p ；/建表（头插法）void CreatListF(LinkList &L,ElemType a,int n)/初始化线性表L=(LinkList)malloc(sizeof(LNode);/分配内存空间L->next=NULL;/在表中插入元素LinkList S;int i;/头插法for(i=0;i<n;i+)S=(LinkList)malloc(sizeof(LNode);/生成新结点S->data=ai;/ 数据域S->next=L->next;L->next=S;/建表（尾插

5、法）void CreatListR(LinkList &L,ElemType a,int n)3百度文库L=(LinkList)malloc(sizeof(LNode);L->next=NULL;LinkList p;p=L;LinkList S;int i;/尾插法for(i=0;i<n;i+)S=(LinkList)malloc(sizeof(LNode);S->data=ai;p->next=S;p=S;p->next=NULL;/初始化线性表void InitList(LinkList &L)L=(LinkList)malloc(sizeo

6、f(LNode);L->next=NULL;/获得链表元素Status GetElem(LinkList L,int i,ElemType &e)/L 为带头结点的单链表的头指针LinkList p;int j;/初始化， p 指向第一个结点4百度文库p=L->next;/j 为计数器j=1;/顺指针往后查找，直到p 指向第 i 个元素或p 为空while(p && j<i)p=p->next;j+;/第 i 个元素不存在if(!p | j>i)return ERROR;/取第 i 个元素e=p->data;return OK;/插入

7、Status ListInsert(LinkList &L,int i,ElemType e)int j=0;LinkList p;p=L;while(p!=NULL && j<i-1)/找第 i-1 个结点p=p->next;j+;if(!p | j>i-1)return ERROR;LinkList S;5百度文库S=(LinkList)malloc(sizeof(LNode);/生成新结点S->data=e;S->next=p->next;p->next=S;return OK;/删除Status ListDelete(L

8、inkList &L,int i,ElemType &e)LinkList p;LinkList q;int j=0;p=L;while(p->next)!=NULL && j<i-1)/找第 i 个结点p=p->next;j+;/!(p->next)：指向第 i 个结点的指针为空（第i 个元素不存在）if(!(p->next) | j>i-1)return ERROR;q=p->next;p->next=q->next;e=q->data;free(q);return OK;/求表的长度int Lis

9、tLength(LinkList L)6百度文库LinkList p;p=L;int j=0;/线性链表最后一个结点的指针为空while(p->next)!=NULL)j+;p=p->next;return j;/输出void visit(LinkList L)LinkList p;p=L->next;while(p!=NULL)printf("%c ",p->data);p=p->next;/销毁 :要销毁的话从头结点开始依次free 但要先得到下一个节点再freevoid DestroyList(LinkList &L)LinkLi

10、st p;LinkList q;p=L;q=p->next;while(p!=NULL)7百度文库free(p);p=q;q=p->next;/ free(p);/ 判空int ListEmpty(LinkList L)/为空表则执行该语句，否则返回return 0；return (L->next=NULL);/查找int ListSearch(LinkList L,ElemType e)LinkList p;p=L->next;int i=1;while(p!=NULL && p->data!=e)p=p->next;i+;if(p=NUL

11、L)return 0;return i;int main()8百度文库ElemType e;ElemType a6='a','b','c','d','e','f'LinkList L;/ 链表的头指针printf(" 头插法建表：");CreatListF(L,a,6);visit(L);printf("nn");/初始化InitList(L);printf(" 初始化后的表：");visit(L);printf("nn"

12、;);printf(" 尾插法建表：");CreatListR(L,a,6);visit(L);printf("nn");/初始化后表为空，此时不要调用GetElem()GetElem(L,3,e);printf(" 表中第 3 个元素为： ");printf("%cnn",e);/在第 5 个位置插入字符'k'ListInsert(L,5,'k');printf(" 在表中第5 个位置插入字符'k'后： ");visit(L);printf("nn");9百度文库printf("