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

1、数学与信息技术学院 20162017（下）学年计科专业 2015 级数据结构实验报告 2 学号：2015201018 姓名：汪继超实验名称 线性表的链式存储结构 完成时间一 .实验目的1 掌握单链表的概念及其各种运算的原理。2 通过对单链表的建立及几种基本运算等的算法实现，掌握线性表的链式存储结构、各种运算和指针的表示及应用等内容。初步掌握运用链式结构的编程和调试程序的能力。3 用 C 语言实现并上机调试通过，认真填写实验报告二 .实验要求4采用链式存储结构完成。5注意类 C 和 C 的转换。6上机调试通过，认真书写实验报告。三 .实验原理 链表是一种动态存储结构。线性表的链式存储结构的特点是

2、用一组任意的存储单元（可以是连续的，也可以是不连续的）存放线性表的数据元素。线性表的一个结点由两个域组成：存放自身的数据和存放直接后继结点存储位置的指针域 。用指针相连接的结点序列称为链表，若逻表中每个结点只包含一个指针域，则此链表为线性链表或单链表。通常链表中的每个结点可以有若干个数据域 和多个链域 。我们常用 C 语言中的“指针”类型来描述线性链表。四 .实验内容（1） 定义函数 create_linklist(): 建立一个具有 n 个结点的单向链表 L，要求返回表头指针；（2） 定义函数 count_node():统计结点个数，要求以表头指针作为调用函数，返回结点个数；（3） 定义函数

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, *

4、LinkList; void print_node(LinkList L);void color(const unsigned short color1)/颜色函数if(color1=0color(13); printf(“n 请输入您要创建的数据条数：“);scanf(“%d“,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(LinkLis

5、t 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

6、;count=count_node(L);color(13); printf(“n 链表当前数据：“);print_node(L);color(10); printf(“n 请输入插入的位置和元素，以空格隔开：“);scanf(“%d%d“,color(13); /*先判断位置是否合法，合法执行插入操作，反之则不执行。*/if(kcount-1)printf(“n 插入元素的位置不合法！n“);elseprintf(“n 链表插入元素前：“);print_node(L);p=(LinkList)malloc(sizeof(Lnode); /为插入元素开辟新空间p-data=s;for(q=L;

7、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“,color(13); if(kcount) printf(“n 您输入的

8、元素位置不合法！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(

9、“n 请输入要查找的元素：“);scanf(“%d“,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)

10、;color(10);printf(“n 请输入要修改的元素：“);scanf(“%d“,color(13);while(p)if(p-data=e1)flag=1;printf(“n 找到元素:%d 位置为%d n“,p-data,j);printf(“nn 1.修改 2.不修改 请输入: “);scanf(“%d“,if(n!=1) break;if(n=1)printf(“n 元素%d 改为: “,e1);scanf(“%d“,p-data=e2;printf(“n 修改成功！n “);printf(“n 修改后链表的数据：“);print_node(L);break;color(10)

11、;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

12、 *L;L=(LinkList)malloc(sizeof(Lnode);color(10);start:do Menu();printf(“n 请选择你需要操作的步骤(0-7): “);fflush(stdin); /*清空在此前输入缓冲区*/scanf(“%d“,if(n=0 break;elseflag=0;system(“cls“);printf(“您输入有误，请重新选择!n“);while(flag=0);while(flag=1)switch(n)case 1:create_linklist(L);break; /*建表*/case 2:count_node(L);break; /

13、*统计*/case 3:insert_node(L,i,e,c);break; /*插入*/case 4:delete_node(L,i,c);break; /*删除*/case 5:printf(“n 链表当前数据：“);print_node(L);break; /*打印*/case 6:modify_node(L,e1,e2);break; /*修改*/case 7:LocateElem_node(L,e);break; /*查找*/case 0:free(L);exit(0);break;default:system(“cls“);goto start;printf(“n 是否继续进行(y or n): “);fflush(stdin);/清空在此前输入缓冲区a=getchar();if(a=y|a=Y)flag=1;system(“cls“); /*清屏*/Menu(); /*调用菜单函数*/printf(“请再次选择你需要操作的步骤(0-7): “);fflush(stdin); /清空在此前输入缓冲区scanf(“%d“,elsefree(L);/释放链表exit(0);实验结果：1. 建表：注：若以空格键隔开数据，多输入无影响，计算机读取完指定数目数据后，自动结束读取。2.统计：3-1.插入位置合法：3-2.插入位置不合法：4-1.删除位置合法：