数据结构链表C语言实现.doc

数学与信息技术学院20162017（下）学年计科专业2015级数据结构实验报告 2 学号：2015201018 姓名：汪继超实验名称线性表的链式存储结构完成时间一.实验目的1 掌握单链表的概念及其各种运算的原理。2 通过对单链表的建立及几种基本运算等的算法实现，掌握线性表的链式存储结构、各种运算和指针的表示及应用等内容。初步掌握运用链式结构的编程和调试程序的能力。3 用C语言实现并上机调试通过，认真填写实验报告二.实验要求4 采用链式存储结构完成。5 注意类C和C的转换。6 上机调试通过，认真书写实验报告。三.实验原理 链表是一种动态存储结构。线性表的链式存储结构的特点是用一组任意的存储单元（可以是连续的，也可以是不连续的）存放线性表的数据元素。线性表的一个结点由两个域组成：存放自身的数据和存放直接后继结点存储位置的指针域 。用指针相连接的结点序列称为链表，若逻表中每个结点只包含一个指针域，则此链表为线性链表或单链表。通常链表中的每个结点可以有若干个数据域 和多个链域 。我们常用C语言中的“指针”类型来描述线性链表。四.实验内容（1） 定义函数create_linklist(): 建立一个具有n个结点的单向链表L，要求返回表头指针；（2） 定义函数count_node():统计结点个数，要求以表头指针作为调用函数，返回结点个数；（3） 定义函数insert_node():在链表L的第I个结点前插入一个结点，要求以表头指针作为调用函数，无返回值；（4） 定义函数delete_node():删除链表L的第I个元素，要求以表头指针作为调用函数，无返回值；（5） 定义函数print_node():输出单链表;（6） 以上每次操作结束，输出单链表，要求以表头指针作为调用函数，无返回值。实验过程：#include#include#include#includetypedef int ElemType;typedef struct LnodeElemType data; struct Lnode *next;Lnode, *LinkList; void print_node(LinkList L);void color(const unsigned short color1)/颜色函数 if(color1=0&color1next=NULL;color(13); printf(n请输入您要创建的数据条数：);scanf(%d,&n);printf(n请输入数据：);for(i=0;idata);q-next=p;q=p;fflush(stdin);/清空在此前输入缓冲区q-next=NULL;printf(n已创建数据：);print_node(L);color(10);return L;void print_node(LinkList L)/打印Lnode *p;p=L-next;while(p)printf(%5d,p-data);p=p-next;printf(n);int count_node(LinkList L)/统计int count=0;Lnode *p;p=L-next;while(p)p=p-next;count+;color(13);printf(n统计得总共记录为：%d条n,count);color(10);return count;void insert_node(Lnode *L,int i,ElemType x,int count)/插入；Lnode *p,*q;int k,s;count=count_node(L);color(13); printf(n链表当前数据：);print_node(L);color(10); printf(n请输入插入的位置和元素，以空格隔开：);scanf(%d%d,&k,&s);color(13); /*先判断位置是否合法，合法执行插入操作，反之则不执行。*/if(kcount-1)printf(n插入元素的位置不合法！n);elseprintf(n链表插入元素前：);print_node(L);p=(LinkList)malloc(sizeof(Lnode); /为插入元素开辟新空间p-data=s;for(q=L;k1;k-)q=q-next;p-next=q-next;q-next=p;count+;printf(n链表插入元素后：);print_node(L);color(10);void delete_node(Lnode *L,int i,int count)Lnode *p,*q;p=L;count=count_node(L);int k;color(13); printf(n链表当前数据：);print_node(L);color(10);printf(n请输入删除元素的位置：);scanf(%d,&k);color(13); if(kcount) printf(n您输入的元素位置不合法！n);elseprintf(n链表删除元素前：);print_node(L);while(-k0) p=p-next;q=p-next;p-next=p-next-next;free(q);count-;printf(n链表删除元素后：);print_node(L);color(10); void LocateElem_node(Lnode *L,ElemType x)/查找操作Lnode *p;p=L-next;int j=1,flag=0;color(13);printf(n链表当前数据：);print_node(L);color(10);printf(n请输入要查找的元素：);scanf(%d,&x);color(13);while(p)if(p-data=x)flag=1;printf(n找到元素:%d 位置为%d n,p-data,j);color(10);j+;p=p-next;if(flag=0) printf(n没有找到该元素n);color(10);void modify_node(Lnode *L,ElemType e1,ElemType e2) /修改操作Lnode *p;p=L-next;int j=1,n,flag=0;color(13);printf(n链表当前数据：);print_node(L);color(10);printf(n请输入要修改的元素：);scanf(%d,&e1);color(13);while(p)if(p-data=e1)flag=1;printf(n找到元素:%d 位置为%d n,p-data,j);printf(nn 1.修改 2.不修改 请输入: ); scanf(%d,&n);if(n!=1) break; if(n=1)printf(n元素%d改为: ,e1);scanf(%d,&e2);p-data=e2;printf(n修改成功！n );printf(n修改后链表的数据：);print_node(L);break;color(10);j+;p=p-next;if(flag=0) printf(n没有找到该元素n);color(10);void Menu() printf( 线性表的链式存储结构 nn);printf( *菜单*n); printf( * 1.建表 2.统计 *n); printf( * 3.插入 4.删除 *n); printf( * 5.打印 6.修改 *n);printf( * 7.查找 0.退出 *n);printf( *n); void main()int e1=0,e2=0,c=0,e=0,i=0,n,flag; /*c=count*/char a;Lnode *L;L=(LinkList)malloc(sizeof(Lnode);color(10);start:do Menu();printf(n请选择你需要操作的步骤(0-7): );fflush(stdin); /*清空在此前输入缓冲区*/scanf(%d,&n);if(n=0 & nnext-next改为p-next =p-next-next2. 链表长度统计与调用中，注意各函数与统计函数的关系。例如：插入函数、删除函数等。问题讨论与结论：（1） 插入、删除操作时同时增减已统计的链表长度（2） 每次需用到链表长度时，重新调用统计函数统计链表长度注：文件名为：学号+（次数）