实验三+线性表的链式存储

1、实验三 线性表的链式存储【实验目的】1. 掌握基本线性链式存储的类型定义及C语言实现；2. 掌握基本线性表在链式存储结构中的各种基本操作。【实验要求】1. 学会定义一个链式存储结构体 LNode；2. 学会链式存储结构的初始化、清空、求线性表的长度、遍历、改值、 插入(头插、尾插、固定位置插入)、删除(删头、删尾、固定位置删除) ；3. 学会用 main 函数调用定义的各个函数；【实验环境】VC+运行的环境【实验步骤及代码 】一、创建VC工程环境二、编写、调试程序/一、包含库文件和类型定义#include #include typedef charElemType;/二、定义结构typedef

2、 struct LNodeElemType data;struct LNode *next;LNode,* LinkList ;/三、基本操作函数的定义/(1)创建一个带头结点的链表LinkList CreateList_L(int n)逆序输入如n个元素的值，建立一个带表头结点的单链表LinkList L=( LinkList )malloc(sizeof(LNode);L-next=NULL;char ch;for(int i=n;i0;-i)LinkList p=(LinkList )malloc(sizeof(LNode); scanf(%c,&ch); p-data=ch;p-nex

3、t=L-next; L-next=p;return L; /(2)链表的遍历函数 void travel_L( LinkList s)LinkList p=s-next;while(p) printf(%c,p-data); p=p-next;printf(n);返回链表L的第i个元素的值ElemType GetElem_L(LinkList L,int i)LNode *p=L-next;int j=1;while (p&jnext; +j;if (!p|ji) printf(i 越界！ );exit(1);else return p-data;(4)链表的i个位置插入一个值为e的节点voi

4、d ListInsert_L(LinkList L,int i, ElemType e)LinkList p=L;int j=0;while (p&jnext; +j;if (!p|ji-1) exit(1);elseLNode *s=(LinkList )malloc(sizeof(LNode); s-data=e;s-next=p-next;p-next=s;return;/(5)链表中删除第 i 个元素void ListDelete_L( LinkList L,int i)LNode *p=L;int j=0;while (p-next&jnext;+j;if(!(p-next)|ji-

5、1) exit(1);LNode *q=p-next;p-next=q-next;free(q);return;/(6)删除链表的第一个节点void ListDeleteFist_L( LinkList L)ListDelete_L(L,1);/(7)求一个链表的长度int ListLength_L( LinkList L)LNode *p=L;int j=0;while (p-next) p=p-next;+j;return j;(8)在一个链表的尾部查入一个值为e的节点void ListInsertLast_L( LinkList L,ElemType e) ListInsert_L(L,

6、ListLength_L(L)+1,e);/(9)删除链表的尾节点void ListDeleteLast_L(LinkList L) ListDelete_L(L,ListLength_L(L);(10)把链表的第i个值改为evoid Listchange(LinkList L,int i, ElemType e)LNode *p=L;int j=0;while (p-next&jnext;+j;if(!(p-next)|ji) exit(1);p-data=e;return;(11)链表中找值为e的节点的位置int ListFind( LinkList L, ElemType e)LNode

7、 *p=L;int j=0;while (p-next&(p-data!=e) p=p-next;+j;if(!(p-next)|jListLength_L(L) exit(1);elsereturn j;/(12)清空一个链表void ListClear_L(LinkList L)while (L-next) ListDeleteLast_L(L);/四、主调函数void main()LinkList L=CreateList_L(6); travel_L(L);printf(链表的第2个元素是：); printf(%cn,GetElem_L(L,2);printf(链表的第2个位置插入值为

8、w后的链表：);ListInsert_L(L,2,w);travel_L(L);printf( 删除链表的第 2个位置上的节点后的链表： ); ListDelete_L(L,2);travel_L(L);printf( 删除链表的头节点后的链表： );ListDeleteFist_L(L);travel_L(L);printf(n);printf( 当前链表的长度为： ); printf(%d,ListLength_L(L); printf(n);printf(链表的尾部插入z后：)；ListInsertLast_L(L,z);travel_L(L)；printf(n)；printf( 删除链

9、表的尾节点后： )；ListDeleteLast_L(L)；travel_L(L)；printf(n)；printf(把第二个节点的值改为丫后：)；Listchange(L,2,Y)；travel_L(L)；printf(n)；printf(找链表中值为丫的位置：)； prin tf(%d丄 istFi nd(L,Y);printf(n)；printf(清空链表：);ListClear_L(L)；travel_L(L)；printf(n)；【实验结果】输入abcdef六个元素时的运行结果：CA *E:教学数据结构3实鲨程序LinkListDe可Xabcdeffedcba勺寰2个元案是：e勺第2个位置插入值为讨后的链表：fw