《数据结构Java版》线性表之单链表的建立及操作

数据结构与算法——单链表的实现及原理1. 单链表的原理 链表是线性表的链式存储⽅式，逻辑上相邻的数据在计算机内的存储位置不必须相邻，那么怎么表⽰逻辑上的相邻关系呢？可以给每个元素附加⼀个指针域，指向下⼀个元素的存储位置。

如图所⽰： 从图中可以看出,每个结点包含两个域：数据域和指针域，指针域存储下⼀个结点的地址，因此指针指向的类型也是结点类型链表的核⼼要素：Ø 每个节点由数据域和指针域组成 Ø 指针域指向下⼀个节点的内存地址。

1.1 结构体定义1 Typedef struct LinkNode2 {3 ElemType data; //节点中存放数据的类型4struct LinkNode* next; //节点中存放下⼀节点的指针5 }LinkList, LinkNode;2. 单链表初始化链表的节点均单向指向下⼀个节点，形成⼀条单向访问的数据链1//单链表的初始化2 typedef struct _LinkNode3 {4int data; //结点的数据域5struct _LinkNode* next; //结点的指针域6 }LinkNode, LinkList; //链表节点、链表78bool InitList(LinkList*& L) //构造⼀个空的单链表 L9 {10 L = new LinkNode; //⽣成新结点作为头结点，⽤头指针 L 指向头结点11if(!L)return false; //⽣成结点失败12 L->next=NULL; //头结点的指针域置空13return true;14 }3. 单链表增加元素 - 单链表前插法插⼊节点的要素就是要找到要插⼊位置的前⼀个节点，将这个节点的Next赋值给新节点，然后将新节点的地址赋值给前⼀个节点的Next便可，任意位置插⼊和前插法均是如此。

1//前插法2bool ListInsert_front(LinkList * &L, LinkNode * node) //参数1 链表指针参数2 要插⼊的节点元素3 {4if (!L || !node) return false; //如果列表或节点为空返回 false5 node->next = L->next; //将头节点指向节点1的地址赋值给要插⼊节点的指针域，使要插⼊的节点先与后部相连6 L->next = node; //将插⼊节点的地址赋值给头结点的指针域，使要插⼊节点与头结点相连78return true;9 }4. 单链表增加元素 - 单链表尾插法1//尾插法2bool ListInsert_back(LinkList*& L, LinkNode* node)3 {4 LinkNode* last = NULL; //创建空指针，5if (!L || !node) return false; //如果列表或节点为空返回 false67 last = L;8while (last->next) last = last->next; //使⽤ last 找到最后⼀个节点910 node->next = NULL; //要插⼊节点由于在尾部，指针域置为 NULL11 last->next = node; //将要插⼊节点的地址赋值给之前的尾部节点的指针域，将要插⼊节点放置到尾部12return true;13 }5. 单链表增加元素 - 单链表任意位置插⼊插⼊节点的要素就是要找到要插⼊位置的前⼀个节点，将这个节点的Next赋值给新节点，然后将新节点的地址赋值给前⼀个节点的Next便可，任意位置插⼊和前插法均是如此。

数据结构-单链表基本操作实现（含全部代码）今天是单链表的实现，主要实现函数如下：InitList(LinkList &L) 参数：单链表L 功能：初始化时间复杂度 O(1)ListLength(LinkList L) 参数：单链表L 功能：获得单链表长度时间复杂度O(n)ListInsert(LinkList &L,int i,ElemType e) 参数：单链表L,位置i，元素e 功能：位置i后插时间复杂度O(n)[加⼊了查找]若已知指针p指向的后插 O(1)ListDelete(LinkList &L,int i) 参数：单链表L，位置i 功能：删除位置i元素时间复杂度O(n)[加⼊了查找]若已知p指针指向的删除最好是O(1),因为可以与后继结点交换数据域，然后删除后继结点。

最坏是O(n),即从头查找p之前的结点,然后删除p所指结点LocateElem(LinkList L,ElemType e) 参数：单链表L，元素e 功能：查找第⼀个等于e的元素，返回指针时间复杂度O(n)代码：/*Project: single linkeed list (数据结构单链表)Date: 2018/09/14Author: Frank YuInitList(LinkList &L) 参数：单链表L 功能：初始化时间复杂度 O(1)ListLength(LinkList L) 参数：单链表L 功能：获得单链表长度时间复杂度O(n)ListInsert(LinkList &L,int i,ElemType e) 参数：单链表L,位置i，元素e 功能：位置i后插时间复杂度O(n)[加⼊了查找]若已知指针p指向的后插 O(1)ListDelete(LinkList &L,int i) 参数：单链表L，位置i 功能：删除位置i元素时间复杂度O(n)[加⼊了查找]若已知p指针指向的删除最好是O(1),因为可以与后继结点交换数据域，然后删除后继结点。

单链表的操作方法一：package ch02;(1)建立结点类Node.javapublic class Node {public Object data;//存放结点数据值public Node next;//存放后继结点//无参构造函数public Node(){ this(null,null);}//只有结点值的构造函数public Node(Object data){ this(data,null);}//带有节点值和后继结点的构造函数public Node(Object data,Node next){ this.data=data;this.next=next;}}(2)建立链表及操作LinkList.javapackage ch02;import java.util.Scanner;public class LinkList implements IList{public Node head;//单链表的头指针//构造函数初始化头结点public LinkList(){head=new Node();}//构造函数构造长度为n的单链表public LinkList(int n,boolean Order) throws Exception{ this();if(Order)create1(n); //头插法顺序建立单链表elsecreate2(n); //尾插法逆序建立单链表}//头插法顺序建立单链表public void create1(int n) throws Exception{Scanner sc=new Scanner(System.in);System.out.println("请输入结点的数据(头插法)：”)；for(int i=0;i<n;i++){insert(0,sc.next());}}//尾插法逆序建立单链表public void create2(int n) throws Exception{Scanner sc=new Scanner(System.in);System. out.println("请输入结点的数据(尾插法)：");for(int i=0;i<n;i++){insert(length(),sc.next());}}//将链表置空public void clear(){head.data=null;head.next=null;}//判断链表是否为空public boolean isEmpty(){return head.next==null;}//返回链表长度public int length(){Node p=head.next;int length=0;while(p!=null){p=p.next;length++;//返回P不空长度length加1}return length;}//读取并返回第i个位置的数据元素public Object get(int i) throws Exception {Node p=head.next;int j;//从首结点开始向后查找，直到9指向第i个结点或者p为nullfor(j=0;j<i&&p!=null;j++){ p=p.next;}if(j>i||p==null)//i不合法时抛出异常throw new Exception("第"+i+”个数据元素不存在”)；return p.data;}//插入乂作为第i个元素public void insert(int i, Object x) throws Exception{ Node p=head;int j=-1;//寻找第i个结点的前驱i-1while(p!=null&&j<i-1){p=p.next;j++;}if(j>i-l||p==null)//i不合法时抛出异常throw new Exception("插入位置不合法”)；Node s=new Node(x);s.next=p.next;p.next=s;}//删除第i个元素public void remove(int i) throws Exception{ Node p=head;int j=-1;while(p!=null&&j<i-1){//寻找第i-1 个节点p=p.next;j++;}if(j>i-1||p.next==null)throw new Exception("删除位置不合法”)；p.next=p.next.next;}//返回元素x首次出现的位序号public int indexOf(Object x) {Node p=head.next;int j=0;while(p!=null&&!p.data.equals(x)){p=p.next;j++;if(p!=null)return j;elsereturn -1;}public void display(){Node p=head.next;while(p!=null){if(p.next==null)System.out.print(p.data);elseSystem.out.print(p.data+"f );p=p.next;}}}(3)建立测试类Test.javappublic class test {public static void main(String[] args) throws Exception { // TODO Auto-generated method stubScanner sc=new Scanner(System.in);boolean or;int xz,xx;System.out.println("请选择插入的方法：0、头插法，1、尾插法");xz=sc.nextInt();if(xz!=0)or=true;elseor=false;System. out.println("请插入的结点的个数：”)；xx=sc.nextInt();LinkList L=new LinkList(xx,or);System.out.println("建立的链表为：");L.display();System.out.println();System.out.println("链表的长度："+L.length());System. out.println(”请输入查找的结点的数据：”)；Object x=sc.next();int position=L.indexOf(x);System.out.println("结点的数据为："+x+"的位置为："+position); System. out.println("请输入删除的结点的位置：”)；int sr=sc.nextInt();L.remove(sr);L.display();System.out.println();System.out.println("链表的长度："+L.length()); }品P rob I em & J a vs d oc / Declaration Q Error Log 里Con sole-M、、■=：termin8ted> test [3] [Java Application] C U &ert\Ad im i n i st rat o r\Ap p Data\L o cs I请选择插入.的方法：0、头插法，lv星插法请插入的特点的个数：请愉入结点的颓据(尾插法)：A B C E D F建立的旌表为；A+B T C+E T D+F链表的长度：6请输入查找的结点的数据:结点的数据为：E的位置为：3请输入删除的结点的位置,R+B T E+DW道表的长度：S方法二(引入get和set方法)Package sy;import java.util.Scanner;//单链表的结点类public class Node {private Object data; //存放结点值private Node next; //后继结点的引用public Node() { //无参数时的构造函数this(null, null);}public Node(Object data) { // 构造值为data 的结点this(data, null);}public Node(Object data, Node next) {//构造值为data 和next 的结点构造函数this.data = data;this.next = next;}public Object getData() { return data;}public void setData(Object data) {this.data = data;}public Node getNext() { return next;public void setNext(Node next) { this.next = next;}}//实现链表的基本操作类public class LinkList {Node head=new Node();//生成一个带头结点的空链表//根据输入的一系列整数，以0标志结束，用头插法建立单链表public void creat() throws Exception {Scanner sc = new Scanner(System.in); //构造用于输入的对象for (int x=sc.nextInt(); x!=0; x=sc.nextInt()) //输入若干个数据元素的值(以0结束) insert(0, x);//生成新结点,插入到表头}//返回带头结点的单链表中第i个结点的数据域的值。

一、实验目的：1、通过单链表来理解链表的逻辑结构和存储结构，熟练掌握线性表的存储方式和一些基本的操作，如：线性表的建立、求表长操作、取元素操作、按值查找操作、插入及删除操作等。

2、将理论知识与实践相结合，提高自己的实际动手能力。

3、通过实践来及时发现自己的缺点与不足，以便为接下来更加有效的学习做铺垫。

二、实验内容：1、采用头插法或尾插法（此次课程设计我们以头插法为例）建立一个单链表。

2、对建立好的单链表进行一些基本的操作，如：a.单链表的类型定义。

b.求表长操作。

c.取元素操作。

d.按值查找操作。

e.显示元素操作。

f.插入操作。

g.删除操作。

h.显示元素操作。

三、基本要求：1.软件要求：Windows 2003、Microsoft Visual C++ 6.0、Microsoft Ward 2003等。

2.硬件要求：电脑、优盘及其它辅助设备。

四、算法设计思想：用一组任意的存储单元来存放线性表中的数据元素，这组存储单元既可以是连续的，也可以是不连续的，甚至可以是零散分布在内存中的任意位置上。

为了表示线性表中的数据元素之间的前后关系，每个数据元素在存储器中的结点除了存储其基本信息外（结点的数据域），还需附加存储其前驱和后继的位置（结点的指针域）。

这样线性表L=（a1，a2，…,an）在存储器上的n个结点就通过各自结点的指针域链接成一个“链子”，即链表。

如果只附加存储其后继的位置（后继指针）就为单链表。

五、算法流程图六、算法源代码#include <iostream.h>#include<stdlib.h>#include <stdio.h>typedef int Status;#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2#define NULL 0/*单链表的类型定义*/typedef struct LNode{int data;struct LNode *next;}LNode, *LinkList;/*头插法建立单链表*/LNode *createList(int n){LNode *p;int i;LinkList L;L=(LinkList)malloc(sizeof(LNode));L->next=NULL;for(i=1;i<=n;i++){p=(LNode*)malloc(sizeof(LNode));cout <<"输入值";cin>>p->data;p->next=L->next;L->next=p;}return L;}/*求表长操作*/int listLength(LinkList L){LNode *p=L;int j=0;while(p->next){p=p->next;j++;}return j;}/*取元素操作*/void getElem(LNode *L,int i){int e;LNode *p=L;int j=0;while(j<i && p->next){p=p->next;j++;}if(j==i){e=p->data;printf("取得元素为：%d\n",e);}else printf("无此元素\n");}/*按值查找*/int locateElem(LinkList L,int e){LNode *p=L->next;while(p->data!=e&&p!=NULL)p=p->next;if(p->data==e)return OK;else return ERROR;}/*单链表的插入*/int listInsert(LinkList L,int i,int e){LNode *p=L,*q;int j=0;while(j<i-1&&p->next){p=p->next;j++;}if(j==i-1){q=(LNode*)malloc(sizeof(LNode));if(!q) return OVERFLOW;q->data=e;q->next=p->next;p->next=q;return OK;}else return ERROR;}/*单链表的删除*/int listDelete(LNode* L,int i){LNode *p=L,*q;int j=0;while(j<i-1&&p->next){p=p->next;j++;}if(j==i-1&&p->next){q=p->next;p->next=q->next;free(q);return OK;}else return ERROR;}/*显示元素操作*/void display(LNode *L){LNode *p=L->next;while(p){ printf("%d",p->data);p=p->next; }}/*主函数*/void main (){cout<<"* * * * * * * * * * * * *"<<endl;cout<<" * 1:单链表的建立* "<<endl;cout<<"* * * * 2:求表长* * * * * *"<<endl;cout<<" * 3:取元素* * * "<<endl;cout<<"* * * * 4:按值查找* * * * *"<<endl;cout<<" * 5:插入* * * "<<endl;cout<<"* * * * 6:删除* * * * * *"<<endl;cout<<" * 7:显示* * * "<<endl;cout<<"* * * * 0:退出* * * * * *"<<endl;cout<<"* * * * * * * * * * * * *"<<endl;LNode *L;int n,flag=1,i;int h,m;while(flag){cout <<"请选择:";cin>>i;switch(i){ case 0: flag=0;break;case 1: cout<<"输入单链表长度:",cin>>n, L=createList(n);break;case 2: cout<<"求得表长为: "<<listLength(L)<<endl;break;case 3: cout <<"取第几个元素：",cin>>h, getElem(L,h);break;case 4: cout<<"输入要查找的值: ",cin>>m,cout<<locateElem(L,m);break;case 5: cout<<"插入位置和插入值分别为：",cin>>i>>m,cout<<listInsert(L,i,m)<<endl;break;case 6: cout<<"输入要删除的元素的位置：",cin>>i,cou t<<listDelete(L,i)<<endl;break;case 7: display(L);break;default: cout<<"输入错误,请重新输入！";}}}七、算法运行结果1、显示整个链表的功能选择：2、设置单链表的长度:3、求出并返回链表的长度：4、在链表中取出某个位置的元素并返回其值：5、给定一个值，查看链表中是否存在这个元素，若存在就返回TURE(即：返回数字1)，反之，返回ERROR（即：返回数字0）：6、显示链表中的元素：7、在链表的某个位置插入元素：8、删除链表中的某个元素：9、退出对链表的操作：10、链表所有功能效果图：八、收获及体会通过这次课程设计，我们小组成员对单链表的基本操作都更加熟悉了、对线性存储的认识也更加深刻了。

单向链表单向链表的基本操作,创建一个由6个节点组成的单向链表，显示链表中每个节点的数据，并且做增加、删除、查找节点以及计算单链表的长度等处理。

➢需求分析：1.功能（1）用尾插法创建一带头结点的由6个节点组成的单向链表：从键盘读入一组整数，作为单链表中的元素，输入完第6个结点后结束;将创建好的单链表元素依次输出到屏幕上。

（2）显示链表中每个节点的数据（3）从键盘输入一个数,查找在以上创建的单链表中是否存在该数；如果存在,显示它的位置，即第几个元素;如果不存在，给出相应提示如“No found node!”。

（4）在上述的单链表中的指定位置插入指定数据，并输出单链表中所有数据。

(5）删除上述单链表中指定位置的结点，并输出单链表中所有数据。

(6）求单链表的长度并输出.2．输入要求先输入单链表中结点个数n,再输入单链表中所有数据，在单链表中需查找的数据，需插入的数据元素的位置、值，要删除的数据元素的位置。

3。

测试数据单链表中所有数据：12，23,56，21，8，10在单链表中需查找的数据：56；24插入的数据元素的位置、值：1，28；7,28；0，28要删除的数据元素的位置:6➢概要设计：1.算法思想：由于在操作过程中要进行插入、删除等操作，为运算方便，选用带头结点的单链表作数据元素的存储结构.对每个数据元素，由一个数据域和一个指针域组成，数据域放输入的数据值，指针域指向下一个结点。

2.数据结构：单链表结点类型:typedef struct Liistnode ｛int data；struct Listnode *next;｝NODE;3.模块划分：a)用尾插法建立带头结点的单链表＊CreateList函数；b)显示链表中每个结点的数据PrintList函数;c)从键盘输入一个数，查找单链表中是否存在该数FoundList函数；d)在单链表中指定位置插入指定数据并输出单链表中所有数据InsertList函数;e)删除单链表中指定位置的结点并输出单链表中所有数据DeleteList函数；f)计算单链表的长度并在屏幕上输出LengthList函数;g)主函数main()，功能是给出测试数据值，建立测试数据值的带头结点的单链表,调用PrintList函数、FoundList函数、InsertList函数、DeleteList函数、LengthList函数实现问题要求。

《数据结构》课程实验指导《数据结构》实验教学大纲课程代码：0806523006 开课学期：3 开课专业：信息管理与信息系统总学时/实验学时：64/16 总学分/实验学分：3.5/0.5一、课程简介数据结构是计算机各专业的重要技术基础课。

在计算机科学中，数据结构不仅是一般程序设计的基础，而且是编译原理、操作系统、数据库系统及其它系统程序和大型应用程序开发的重要基础。

数据结构课程主要讨论各种主要数据结构的特点、计算机内的表示方法、处理数据的算法以及对算法性能的分析。

通过对本课程的系统学习使学生掌握各种数据结构的特点、存储表示、运算的原理和方法，学会从问题入手，分析研究计算机加工的数据结构的特性，以便为应用所涉及的数据选择适当的逻辑结构、存储机构及其相应的操作算法，并初步掌握时间和空间分析技术。

另一方面，本课程的学习过程也是进行复杂程序设计的训练过程，通过对本课程算法设计和上机实践的训练，还应培养学生的数据抽象能力和程序设计的能力。

二、实验的地位、作用和目的数据结构是一门实践性较强的基础课程，本课程实验主要是着眼于原理和应用的结合，通过实验，一方面能使学生学会把书上学到的知识用于解决实际问题，加强培养学生如何根据计算机所处理对象的特点来组织数据存储和编写性能好的操作算法的能力，为以后相关课程的学习和大型软件的开发打下扎实的基础。

另一方面使书上的知识变活，起到深化理解和灵活掌握教学内容的目的。

三、实验方式与基本要求实验方式是上机编写完成实验项目指定功能的程序，并调试、运行，最终得出正确结果。

具体实验要求如下：1.问题分析充分地分析和理解问题本身，弄清要求，包括功能要求、性能要求、设计要求和约束，以及基本数据特性、数据间联系等等。

2.数据结构设计针对要解决的问题，考虑各种可能的数据结构，并且力求从中选出最佳方案（必须连同算法实现一起考虑），确定主要的数据结构和全程变量。

对引入的每种数据结构和全程变量要详细说明其功用、初值和操作的特点。

线性表的创建和操作//对顺序表的操作#include<stdio.h>#include <stdlib.h>#include<malloc.h>#define MAXSIZE 1000typedef char ElemType;typedef struct{ElemType data[MAXSIZE];int length;}SqList;//初始化线性表void InitList(SqList*&L){L=(SqList*)malloc(sizeof(SqList));L->length=0;}//销毁线性表void DestoryList(SqList*&L){free(L);}//判断线性表是否为空int ListEmpty(SqList*L){return(L->length==0);}//插⼊数据元素，起始位置为1int ListInsert(SqList*&L,int Position,ElemType item){int j;if(Position<1||Position>L->length+1){printf("元素插⼊失败，请检查输⼊的位置是否有错！\n");return 0;}Position--;for(j=L->length;j>Position;j--){L->data[j]=L->data[j-1];}L->data[Position]=item;L->length++;printf("元素插⼊成功\n");return 1;}//替换第Position个元素的值int ListReplace(SqList*&L,int Position,ElemType item){if(Position<1||Position>L->length){printf("元素位序号错误！ \n");return 0;}Position--;L->data[Position]=item;printf("元素存放成功！\n");return 1;}//删除数据元素int ListDelete(SqList*&L,int Position,ElemType &item){int j;if(Position<1||Position>L->length){printf("输⼊的位号有误！\n");return 0;}Position --;item=L->data[Position];for(j=Position;j<L->length-1;j++){L->data[j]=L->data[j+1];}L->length--;return 1;}//输出线性表void DispList(SqList *L){int i;if(ListEmpty(L)){printf("表空!\n");return;}for(i=0;i<L->length;i++)printf("%c ",L->data[i]);printf("\n");}//求线性表中某个数据元素值int GetElem(SqList*L,int Position,ElemType&item) {if(Position<1||Position>L->length){return 0;}item=L->data[Position-1];return 1;}//求线性表的长度int ListLength (SqList*L){return(L->length);}//按元素值查找int LocateElem(SqList*L,ElemType item){int i=0;while(i<L->length&&L->data[i]!=item)i++;if(i>=L->length)return 0;elsereturn i+1;}void clear(){system("pause");system("cls");}void showmenu(){printf("\n\n\n");printf(" --线性表的基本运算-- \n");printf("********************************************\n"); printf("* 1---插⼊⼀个新元素到第i个位置 *\n"); printf("* 2---删除第i个位置的元素 *\n");printf("* 3---存⼀个新元素到第i个位置 *\n"); printf("* 4---显⽰顺序表中所有元素的值 *\n"); printf("* 5---检索表中第i个元素 *\n");printf("* 6---求表的长度 *\n");printf("* *\n");printf("* 0---退出 *\n");printf("********************************************"); printf("\n请选择菜单号(0--6):");}void Charu(){SqList*L;InitList(L);//创建⼀个顺序表char choice='N';ElemType item;int Position;printf("请输⼊⼀个新元素的值：");flushall();scanf("%c",&item);printf("请输⼊插⼊的位置：");scanf("%d",&Position);ListInsert(L,Position,item);}void Shanchu(){char choice='N';ElemType item;int Position;SqList*L;InitList(L);//创建⼀个顺序表printf("请输⼊要删除的元素的位置序号：");scanf("%d",&Position);if(ListDelete(L,Position,item)){printf("删除的元素为%c\n",item);}}void Xiugai(){char choice='N';ElemType item;int Position;SqList*L;InitList(L);//创建⼀个顺序表printf("请输⼊⼀个新元素的值：");flushall();scanf("%c",&item);printf("请输⼊该元素的存放位置：");scanf("%d",&Position);ListReplace(L,Position,item);}void Jiansuo(){char choice='N';ElemType item;int Position;SqList*L;InitList(L);//创建⼀个顺序表printf("请输⼊元素的位序号：");scanf("%d",&Position);if(GetElem(L,Position,item)){printf("第%d个元素为：%c\n",Position,item); }else{printf("输⼊的位序号有误！\n");}}void LineOP(){char choice='N';ElemType item;int Position;SqList*L;InitList(L);//创建⼀个顺序表while(choice!='0'){showmenu();flushall();scanf("%c",&choice);switch(choice){case'1':Charu();clear();break;case'2':Shanchu();clear();break;case'3':Xiugai();clear();break;case'4':DispList(L);clear();break;case'5':Jiansuo();clear();break;case'6':printf("线性表的长度为%d",ListLength(L)); clear();break;case'0':printf("\n\t程序结束！\n");DestoryList(L);break;default:printf("\n\t选择错误，请重新输⼊！\n"); break;}}}int main(){LineOP();return 0;}。

数据结构实验报告-实验⼀顺序表、单链表基本操作的实现实验⼀顺序表、单链表基本操作的实现l 实验⽬的1、顺序表（1）掌握线性表的基本运算。

（2）掌握顺序存储的概念，学会对顺序存储数据结构进⾏操作。

（3）加深对顺序存储数据结构的理解，逐步培养解决实际问题的编程能⼒。

l 实验内容1、顺序表1、编写线性表基本操作函数：（1）InitList(LIST *L,int ms)初始化线性表；（2）InsertList(LIST *L,int item,int rc)向线性表的指定位置插⼊元素；（3）DeleteList1(LIST *L,int item)删除指定元素值的线性表记录；（4）DeleteList2(LIST *L,int rc)删除指定位置的线性表记录；（5）FindList(LIST *L,int item)查找线性表的元素；（6）OutputList(LIST *L)输出线性表元素；2、调⽤上述函数实现下列操作：（1）初始化线性表；（2）调⽤插⼊函数建⽴⼀个线性表；（3）在线性表中寻找指定的元素；（4）在线性表中删除指定值的元素；（5）在线性表中删除指定位置的元素；（6）遍历并输出线性表；l 实验结果1、顺序表（1）流程图（2）程序运⾏主要结果截图（3）程序源代码#include<stdio.h>#include<stdlib.h>#include<malloc.h>struct LinearList/*定义线性表结构*/{int *list; /*存线性表元素*/int size; /*存线性表长度*/int Maxsize; /*存list数组元素的个数*/};typedef struct LinearList LIST;void InitList(LIST *L,int ms)/*初始化线性表*/{if((L->list=(int*)malloc(ms*sizeof(int)))==NULL){printf("内存申请错误");exit(1);}L->size=0;L->Maxsize=ms;}int InsertList(LIST *L,int item,int rc)/*item记录值；rc插⼊位置*/ {int i;if(L->size==L->Maxsize)/*线性表已满*/return -1;if(rc<0)rc=0;if(rc>L->size)rc=L->size;for(i=L->size-1;i>=rc;i--)/*将线性表元素后移*/L->list[i+=1]=L->list[i];L->list[rc]=item;L->size++;return0;}void OutputList(LIST *L)/*输出线性表元素*/{int i;printf("%d",L->list[i]);printf("\n");}int FindList(LIST *L,int item)/*查找线性元素，返回值>=0为元素的位置，返回-1为没找到*/ {int i;for(i=0;i<L->size;i++)if(item==L->list[i])return i;return -1;}int DeleteList1(LIST *L,int item)/*删除指定元素值得线性表记录，返回值为>=0为删除成功*/ {int i,n;for(i=0;i<L->size;i++)if(item==L->list[i])break;if(i<L->size){for(n=i;n<L->size-1;n++)L->list[n]=L->list[n+1];L->size--;return i;}return -1;}int DeleteList2(LIST *L,int rc)/*删除指定位置的线性表记录*/{int i,n;if(rc<0||rc>=L->size)return -1;for(n=rc;n<L->size-1;n++)L->list[n]=L->list[n+1];L->size--;return0;}int main(){LIST LL;int i,r;printf("list addr=%p\tsize=%d\tMaxsize=%d\n",LL.list,LL.size,LL.Maxsize);printf("list addr=%p\tsize=%d\tMaxsize=%d\n",LL.list,LL.list,LL.Maxsize);while(1){printf("请输⼊元素值，输⼊0结束插⼊操作:");fflush(stdin);/*清空标准输⼊缓冲区*/scanf("%d",&i);if(i==0)break;printf("请输⼊插⼊位置：");scanf("%d",&r);InsertList(&LL,i,r-1);printf("线性表为：");OutputList(&LL);}while(1){printf("请输⼊查找元素值，输⼊0结束查找操作：");fflush(stdin);/*清空标准输⼊缓冲区*/scanf("%d ",&i);if(i==0)break;r=FindList(&LL,i);if(r<0)printf("没有找到\n");elseprintf("有符合条件的元素，位置为：%d\n",r+1);}while(1){printf("请输⼊删除元素值，输⼊0结束查找操作：");fflush(stdin);/*清楚标准缓存区*/scanf("%d",&i);if(i==0)break;r=DeleteList1(&LL,i);if(i<0)printf("没有找到\n");else{printf("有符合条件的元素，位置为：%d\n线性表为：",r+1);OutputList(&LL);}while(1){printf("请输⼊删除元素位置，输⼊0结束查找操作：");fflush(stdin);/*清楚标准输⼊缓冲区*/scanf("%d",&r);if(r==0)break;i=DeleteList2(&LL,r-1);if(i<0)printf("位置越界\n");else{printf("线性表为：");OutputList(&LL);}}}链表基本操作l 实验⽬的2、链表（1）掌握链表的概念，学会对链表进⾏操作。

二章线性表线性表是最简单、最基本、也是最常用的一种线性结构。

它有两种存储方法：顺序存储和链式存储，它的主要基本操作是插入、删除和检索等。

2.1 线性表的逻辑结构2.1.1 线性表的定义线性表是一种线性结构。

线性结构的特点是数据元素之间是一种线性关系，数据元素“一个接一个的排列”。

在一个线性表中数据元素的类型是相同的，或者说线性表是由同一类型的数据元素构成的线性结构。

在实际问题中线性表的例子是很多的，如学生情况信息表是一个线性表：表中数据元素的类型为学生类型; 一个字符串也是一个线性表：表中数据元素的类型为字符型，等等。

综上所述，线性表定义如下：线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列，通常记为：(a1，a2，… a i-1，a i，a i+1，…a n)其中n为表长，n＝0 时称为空表。

表中相邻元素之间存在着顺序关系。

将a i-1 称为a i 的直接前趋，a i+1 称为a i 的直接后继。

就是说：对于a i，当i=2，...，n 时，有且仅有一个直接前趋a i-1.，当i=1，2，...，n-1 时，有且仅有一个直接后继a i+1，而a1 是表中第一个元素，它没有前趋，a n 是最后一个元素无后继。

需要说明的是：a i为序号为i 的数据元素（i=1,2,…,n），通常我们将它的数据类型抽象为datatype，datatype根据具体问题而定，如在学生情况信息表中，它是用户自定义的学生类型; 在字符串中，它是字符型; 等等。

2.1.2 线性表的基本操作在第一章中提到，数据结构的运算是定义在逻辑结构层次上的，而运算的具体实现是建立在存储结构上的，因此下面定义的线性表的基本运算作为逻辑结构的一部分，每一个操作的具体实现只有在确定了线性表的存储结构之后才能完成。

线性表上的基本操作有：⑴线性表初始化：Init_List(L)初始条件：表L不存在操作结果：构造一个空的线性表⑵求线性表的长度：Length_List(L)初始条件：表L存在操作结果：返回线性表中的所含元素的个数⑶取表元：Get_List(L,i)初始条件：表L存在且1<=i<=Length_List(L)操作结果：返回线性表L中的第ｉ个元素的值或地址⑷按值查找：Locate_List(L,x)，ｘ是给定的一个数据元素。

实验报告
课程名称数据结构
实验项目线性表的实现及应用
实验仪器PC机一台
学院_____ 专业
班级/学号
姓名
实验日期
成绩
指导教师
北京信息科技大学
信息管理学院
（数据结构课程上机）实验报告
3.
1.实验名称、实验目的、实验内容、实验要求由教师确定，实验前由教师事先填好，然后作为实验报告模
版供学生使用；
2.实验准备由学生在实验或上机之前填写，教师应该在实验前检查；
3.实验过程由学生记录实验的过程，包括操作过程、遇到哪些问题以及如何解决等；
4.实验总结由学生在实验后填写，总结本次实验的收获、未解决的问题以及体会和建议等；
5.源程序、代码、具体语句等，若表格空间不足时可作为附录另外附页。

数据结构-单链表的创建及操作数据结构单链表的创建及操作在计算机科学中，数据结构是组织和存储数据的方式，以便能够高效地访问和操作数据。

单链表就是其中一种常见的数据结构，它在许多程序中都有着广泛的应用。

首先，让我们来理解一下什么是单链表。

想象一下，你有一串珠子，每个珠子（节点）都包含了一些数据，并且每个珠子除了自己的数据外，还有一个指针指向下一个珠子。

这就是单链表的基本概念。

单链表的节点通常包含两个部分：数据域和指针域。

数据域用于存储我们实际要处理的数据，而指针域则用于指向链表中的下一个节点。

如果指针域的值为 NULL ，则表示这是链表的末尾节点。

那么，如何创建一个单链表呢？我们可以从一个空链表开始，逐步添加节点。

下面是用 C 语言实现创建单链表的示例代码：｀｀｀cinclude ＜stdioh>include ＜stdlibh>／／定义单链表节点结构体typedef struct Node ｛int data;struct Node next;｝ Node;／／创建新节点Node createNode(int data) ｛Node newNode ＝（Node)malloc(sizeof(Node)）；if （newNode ＝＝ NULL) ｛printf(＂内存分配失败\n"）；return NULL;｝newNode>data ＝ data;newNode>next ＝ NULL;return newNode;｝／／向链表尾部添加节点void append(Node head, int data) ｛Node newNode ＝ createNode(data)；if （head ＝＝ NULL) ｛head ＝ newNode;return;｝Node curr ＝ head;while （curr>next!＝ NULL) ｛curr ＝ curr>next;｝curr>next ＝ newNode;｝／／打印链表void printList(Node head) ｛Node curr ＝ head;while （curr!＝ NULL) ｛printf(＂％d ＂， curr>data)；curr ＝ curr>next;｝printf(＂＼n"）；｝int main(）｛Node head ＝ NULL;append(＆head, 10)；append(＆head, 20)；append(＆head, 30)；printList(head)；return 0;｝｀｀｀在上述代码中，我们首先定义了一个`Node`结构体来表示链表节点。

链表1 定义链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。

由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)。

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。

但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

在计算机科学中，链表作为一种基础的数据结构可以用来生成其它类型的数据结构。

链表通常由一连串节点组成，每个节点包含任意的实例数据（data fields）和一或两个用来指向明上一个或下一个节点的位置的链接（"links"）。

链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的访问往往要在不同的排列顺序中转换。

而链表是一种自我指示数据类型，因为它包含指向另一个相同类型的数据的指针（链接）。

链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。

链表有很多种不同的类型：单向链表，双向链表以及循环链表。

2 结构2.1 单向链表链表中最简单的一种是单向链表，它包含两个域，一个信息域和一个指针域。

这个链接指向列表中的下一个节点，而最后一个节点则指向一个空值。

一个单向链表的节点被分成两个部分。

第一个部分保存或者显示关于节点的信息，第二个部分存储下一个节点的地址。

单向链表只可向一个方向遍历。

链表最基本的结构是在每个节点保存数据和到下一个节点的地址，在最后一个节点保存一个特殊的结束标记，另外在一个固定的位置保存指向第一个节点的指针，有的时候也会同时储存指向最后一个节点的指针。

一般查找一个节点的时候需要从第一个节点开始每次访问下一个节点，一直访问到需要的位置。

【线性表基础】顺序表和单链表的插⼊、删除等基本操作【Java版】本⽂表述了线性表及其基本操作的代码【Java实现】参考书籍：《数据结构 ——Java语⾔描述》/刘⼩晶，杜选主编线性表需要的基本功能有：动态地增长或收缩；对线性表的任何数据元素进⾏访问和查找；在线性表中的任何位置进⾏数据元素的插⼊和删除操作；求线性表中指定数据元素的前驱和后继等等。

⾸先描述线性表的抽象类型，我们使⽤Java接⼝interface：Ilist.java:package liner_list;public interface IList{public void clear();public boolean isEmpty();public int length();public Object get(int i) throws Exception;public void insertAt(int i,Object x) throws Exception;public void remove(int i) throws Exception;public int indexOf(Object x);public void display();}其次描述顺序表，其特点有：在线性表中的逻辑上相邻的数据元素，在物理存储位置上也是相邻的；存储密度⾼，但需要预先分配”⾜够应⽤“的存储空间，这可能将会造成存储空间的浪费；便于随机存储；不便于插⼊和删除，因为在顺序表中进⾏插⼊和删除操作会引起⼤量数据元素的移位。

我们⽤SqList类描述顺序表：SqList.java：package liner_list;// 规定⽅法中的参数i都为顺序表元素的索引（下标）public class SqList implements IList{public Object[] listItem; // 顺序表存储空间public int curLen; // 线性表的当前长度public SqList(int maxSize){listItem = new Object[maxSize]; // 为顺序表分配maxSize个存储单元curLen = 0; // 置当前长度为0}public void clear(){curLen = 0; // 置当前长度为0，即规定为清空顺序表，但是内存中还有数据存在}public boolean isEmpty(){return curLen == 0;}public int length(){return curLen; // 返回当前长度}public Object get(int i) throws Exception // 得到下标为i的元素，同时判断异常{if (i >= curLen || i < 0) // 索引越界，0<=index<=curLen{throw new Exception("Argument 'i' is out of range!");}return listItem[i];}public void insertAt(int i, Object x) throws Exception // 在下表为i的位置插⼊元素x，同时判断异常{if (curLen == listItem.length) // 判断表满{throw new Exception("SqList is full!");}if (i > curLen || i < 0) // 索引越界，可以在curLen的位置进⾏插⼊{throw new Exception("Argument 'i' is out of range!");}for (int j = curLen; j > i; j--) // j从curLen的位置开始，即当前表最后⼀个元素的后⼀个位置，从⽽使得i位置及以后位置上的元素向后移⼀位{listItem[j] = listItem[j - 1];}listItem[i] = x; // 将x元素插⼊i位置curLen++; // 插⼊后表长加⼀}public void remove(int i) throws Exception{if (i >= curLen || i < 0) // i⼩于0或者⼤于等于表长时抛出异常{throw new Exception("Argument 'i' is out of range!");}for (int j = i; j < curLen - 1; j++) // 从i位置开始向后，不能从最后开始，否则最后⼀个元素将覆盖所有元素，若想从后向前，必须将被覆盖的元素保留给下⼀个元素 {listItem[j] = listItem[j + 1];}curLen--; // 删除完后curLen减⼀}public int indexOf(Object x) // 规定返回-1表⽰未找到元素x{for (int i = 0; i < curLen; i++){if (listItem[i].equals(x)){return i;}}return -1;// 书本代码，效果相同// int j = 0;// while (j < curLen && !listItem[j].equals(x))// {// j++;// }// if (j < curLen)// {// return j;// } else// {// return -1;// }}public void display() // 输出顺序表中全部元素{System.out.println("****** SqList ******");for (int i = 0; i < curLen; i++){System.out.print(listItem[i] + " ");}System.out.println();System.out.println("********************");}}接着测试我们的顺序表，使⽤SqListTest类来做测试：SqListTest.java：package liner_list;import java.util.Scanner;public class SqListTest{public static void main(String[] args) throws Exception{SqList sq1 = new SqList(10);sq1.insertAt(0, "a0");sq1.insertAt(1, "a1");sq1.insertAt(2, "a2");sq1.insertAt(3, "a3");sq1.insertAt(4, "a4");sq1.insertAt(5, "a5");int index = sq1.indexOf("a2");if (index != -1){System.out.println("a2's index is " + index + "!");} else{System.out.println("a5 is not in this SqList!");}sq1.display();sq1.remove(2);System.out.println("After remove:");sq1.display();SqList sq2 = new SqList(10);Scanner sc = new Scanner(System.in);System.out.println("Please input element:");for (int i = 0; i < 8; i++){sq2.insertAt(i, sc.next());}sc.close();sq2.display();}}运⾏我们的测试类，得到以下测试结果：然后描述单链表，注意：我们推荐使⽤带头结点的单链表。