当前位置：文档之家› 数据结构单链表及其应用

数据结构单链表及其应用

课程上机实验二

一、上机题目：线性表及其应用

二、上机目的

1、深入复习C 语言程序设计课程中所学的指针等相关知识；

2、进一步掌握在TurboC2.0环境下调试程序的基本方法；

3、掌握线性表的链式存储结构（单链表）的基本操作。

三、上机内容

1、建立单链表的存储结构；

2、建立一个带头结点的单链表，并输出其元素值；

3、完成带头结点的单链表插入、删除一个数据元素操作

四、基本思想和算法描述（包括主要存储结构和程序流程图）

线性表的链式存储结构是指用一组任意的、连续的或不连续的内存单元存储线性表中逻辑上连续的数据。

在链式存储结构中，为了反映数据元素i a 与其直接后继元素1+i a 或者直接前驱元素1-i a 之间的关系，每个数据元素除了存储自身的信息外，还要存储指向后继元素或者直接前驱元素位置的指针。这两部分信息组成了数据元素的存储映像，称为结点。其中表示数据元素内容的部分称为数据域，表示直接后继元素或直接前驱元素位置的部分称为指针域。用链式存储结构的线性表也称为链表。在链表中插入或者删除数据时，只需要修改指针即可，从而避免了顺序存储中数据元素的大量移动问题。

链表是一种动态存储结构，在需要插入一个结点时，按结点类型向系统申请一个结点的存储空间；当删除一个结点时，就将这个结点的存储空间释放，它比顺序表的静态存储方式更加灵活高效。

程序的主要过程流程图如下：

五、测试用例及测试结果

测试用例：XXXXXX

测试结果：

六、调试分析（遇到哪些问题，都是如何解决的）

XXXXXXXXXXXXXX

七、心得体会（本次上机实验的收获）

八、源程序清单

#include "stdafx.h"

#include "stdio.h"

#include "stdlib.h"

typedef struct node

{

int data;

struct node *next;

}NODE;

NODE *createlink() //初始化单链表

{

int len;

printf("输入想要建立的链表的长度：\n");

scanf("%d",&len);

NODE *h,*p,*s;

p=h=(NODE*)malloc(sizeof(NODE));

h->next=NULL;

printf("请输入链表各元素值：\n");

for(int i=1;i<=len;i++)

{

s=(NODE*)malloc(sizeof(NODE));

scanf("%d",&s->data);

s->next=0;

p->next=s;

p=s;

}

return h;

}

void display(NODE *h) //输出单链表

{

NODE *p;

p=h->next;

printf("链表各元素的值为：\n");

while(p!=0)

{

printf("%d,",p->data);

p=p->next;

}

printf("\n");

}

void insertelement(NODE *h) //插入元素{

int i,t;

printf("请输入插入链表元素的位置：\n");

scanf("%d",&i);

printf("输入要插入的元素：\n");

scanf("%d",&t);

NODE *p=h,*s;

int j=0;

while(p->next!=0 && j

{

p=p->next;

j++;

}

s=(NODE *)malloc(sizeof(NODE));

s->data=t;

s->next=p->next;

p->next=s;

return;

}

void deleteelement(NODE *h) //删除节点{

int i,e;

printf("请输入想要删除节点的位置：\n");

scanf("%d",&i);

NODE *p=h->next,*q;

int j=1;

while(p!=0&&j

{

p=p->next;

j++;

}

q=p->next;

p->next=q->next;

e=q->data;

free(q);

return;

}

void main()

{

NODE *h;

h=createlink(); display(h); insertelement(h); display(h); deleteelement(h); display(h);

}

数据结构单链表基本操作代码

实验一单链表 #include "stdio.h" #include "stdlib.h" typedef int ElemType; typedef struct LNode { ElemType data; struct LNode *next; }LNode,*LinkList; void creatLNode(LinkList &head) { int i,n; LNode *p; head=(LNode*)malloc(sizeof(LNode)); head->next=NULL; printf("请输入链表的元素个数："); scanf("%d",&n); for(i=n;i>0;i--) { p=(LNode*)malloc(sizeof(LNode)); printf("第%d个元素：",i); scanf("%d",&p->data); p->next=head->next; head->next=p; } } void InsertLNode(LinkList &L) { LNode *p=L; int i,j=0,e; printf("请输入你要插入的位置（超过链表长度的默认插在最后！）："); scanf("%d",&i); printf("请输入你要插入的元素："); scanf("%d",&e); while (p->next&&jnext; ++j; }

LNode *s; s=(LNode*)malloc(sizeof(LNode)); s->data=e; s->next=p->next; p->next=s; } int DeleteLNode(LinkList &L,int i,int &e) { LNode *p; p=L; LNode *q; int j=0; while (p->next&&jnext; ++j; } if(!(p->next)||j>i-1) { printf("删除位置不合理!\n"); return 0; } q=p->next; p->next=q->next; e=q->data; free(q); return e; } void DeleteCF(LinkList &L) { LNode *p,*s,*r; p=L->next; while(p!=NULL) { r=p; s=r->next; while(s!=NULL) { if(p->data==s->data) { r->next=s->next; s=s->next;

数据结构课程设计单链表操作汇总

《数据结构课程设计》报告题目：单链表操作专业：计算机科学与技术班级：单链表操作针对带头结点的单循环链表，编写实现以下操作的算法函数。

实现要求： ⑴单链表建立函数create：先输入数据到一维数组A[M]中，然后根据一维数组A[M]建立一个单循环链表，使链表中个元素的次序与A[M]中各元素的次序相同，要求该函数的时间复杂度为O(m)； ⑵定位查找函数Locate：在所建立的单循环链表中查找并返回值为key的第1个元素的结点指针；若找不到，则返回NULL； ⑶求出该链表中值最大和次大的元素值，要求该算法的时间复杂度为O(m)，最大和次大的元素值通过指针变量带回，函数不需要返回值； ⑷将链表中所有值比key(值key通过形参传入)小的结点作为值为key的结点前驱，所有值比key大的结点作为值为key的结点后继，并尽量保持原有结点之间的顺序，要求该算法的时间复杂度为O(m); ⑸设计一个菜单，具有上述处理要求和退出系统功能。 ⒈本人完成的工作：一、定义结构体：LNode 二、编写以下函数：（1）建立单循环链表（2）建立定位查找函数（3）求出链表中最大和次大值（4）将链表中的值和输入的Key比较，小的作为key前驱结点，大的作为key 的后继结点三、设计具有上述处理要求和退出系统菜单 ⒉所采用的数据结构：单链表数据结构的定义： typedef struct Node //定义结点的结构体 { DataType data; //数据域 struct Node *next; //指针域

}LNode; //结点的类型 ⒊所设计的函数（1）Create(void) LNode *Create(void) //建立单循环链表，链表头结点head作为返回值{ int i,j,n,A[M]; //建立数组A【M】 LNode *head,*p,*move; head=(LNode*)malloc(sizeof(LNode)); //创建空单循环链表head->next=head; move=head; printf("请输入数组元素的个数："); //输入数组 scanf("%d",&n); printf("请输入数组："); for(i=0;idata=A[j]; p->next=move->next; move->next=p; move=move->next; } return head; //返回头指针

数据结构单链表详解

数据结构的概念：数据的逻辑结构+ 数据的存储结构+ 数据的操作；数据的数值：=====》数据===》数值型数据整形浮点数ASCII 非数值型数据图片声音视频字符 =====》数据元素=====》基本项组成（字段，域，属性）的记录。数据的结构：逻辑结构 ----》线性结构（线性表，栈，队列） ----》顺序结构 ----》链式结构 ----》非线性结构(树，二叉树，图) ----》顺序结构 ----》链式结构存储结构 -----》顺序存储 -----》链式存储 -----》索引存储 -----》哈希存储==散列存储数据的操作：增删改查 DS ====》数据结构===》DS = (D,R); 数据结构中算法： 1、定义：有穷规则的有序集合。 2、特性：有穷性确定性

输入输出 3、算法效率的衡量时间复杂度计算===》算法中可执行依据的频度之和，记为：T(n)。是时间的一种估计值不是准确值。计算结果的分析：1 将最终结果的多项式中常数项去掉 2 只保留所有多项式中最高阶的项 3 最后的最高阶项要去掉其常数项时间复杂度的量级关系：常量阶====》对数阶===》线性阶===》线性对数阶====》平方阶===》立方阶===》指数阶以上关系可以根据曲线图来判断算法对时间复杂度的要求空间复杂度计算====》算法执行过程中所占用的存储空间的量级，记为：D（n）。计算方法是在运行过程中申请的动态内存的量级计算。 ///////////////////////////////////////////////////////////////////////////////////////////////// 线性表顺序存储====》顺序表（数组）链式存储====》单链表特征：对于非空表，a0是表头没有前驱。 an-1 是表尾没有后继 ai的每个元素都有一个直接前驱和直接后继基本操作：创建表=====》增加元素====》删除元素====》改变元素值====》查询元素 1、顺序表的操作 1.1 创建顺序表=====》定义个指定类型的数组====》int a[100] ={0};

c数据结构单链表的建立与基本应用

#include"stdio.h" #include"stdlib.h" typedef struct node { int data; struct node *next; }Lnode,*Linklist; input(Lnode *p,int n)//实现用键盘顺序输入链表数据{ Lnode *s;int i,d; printf("请输入数据："); for(i=1;i<=n;i++) { if(i==1) { scanf("%d",&d); p->data=d; continue; } if(n==1)break; scanf("%d",&d);

s=(Linklist)malloc(sizeof(Lnode)); s->data=d; p->next=s; s->next=NULL; p=s;//使当前指针指向链表尾部节点 } } output(Lnode *p,int n)//实现输出当前链表所有数据 { int i=1; printf("当前链表的值为："); while(p->next!=NULL) { printf("%d ",p->data); p=p->next; i++; } if(i==n)//当是最后一个节点时，其next已经是空，所以最后一个节点数据无法用while循环写出，所以另用了一个计数器i printf("%d",p->data); }

insert(Lnode *p,int i,int e)//实现在第i个元素之后插入新元素{ int j=0;Lnode *s; while(p&&jnext;++j;}if(!p||j>i-1)return 0; s=(Linklist)malloc(sizeof(Lnode)); s->data=e;s->next=p->next;p->next=s; return 1; } delet(Lnode *p,int i)//实现删除链表中第i+1个元素 { int j=0;Lnode *q; while(p->next&&jnext;++j; } if(!(p->next)||j>i-1)return 0; q=p->next;p->next=q->next; free(q); return 1; } search(Lnode *p,int e,int n) {

数据结构课程设计单链表

目录 1 选题背景 (2) 2 方案与论证 (3) 2.1 链表的概念和作用 (3) 2.3 算法的设计思想 (4) 2.4 相关图例 (5) 2.4.1 单链表的结点结构 (5) 2.4.2 算法流程图 (5) 3 实验结果 (6) 3.1 链表的建立 (6) 3.2 单链表的插入 (6) 3.3 单链表的输出 (7) 3.4 查找元素 (7) 3.5 单链表的删除 (8) 3.6 显示链表中的元素个数（计数） (9) 4 结果分析 (10) 4.1 单链表的结构 (10) 4.2 单链表的操作特点 (10) 4.2.1 顺链操作技术 (10) 4.2.2 指针保留技术 (10) 4.3 链表处理中的相关技术 (10) 5 设计体会及今后的改进意见 (11) 参考文献 (12) 附录代码： (13)

1 选题背景陈火旺院士把计算机60多年的发展成就概括为五个“一”：开辟一个新时代----信息时代，形成一个新产业----信息产业，产生一个新科学----计算机科学与技术，开创一种新的科研方法----计算方法，开辟一种新文化----计算机文化，这一概括深刻影响了计算机对社会发展所产生的广泛而深远的影响。数据结构和算法是计算机求解问题过程的两大基石。著名的计算机科学家P.Wegner指出，“在工业革命中其核心作用的是能量，而在计算机革命中其核心作用的是信息”。计算机科学就是“一种关于信息结构转换的科学”。信息结构（数据结构）是计算机科学研究的基本课题，数据结构又是算法研究的基础。

2 方案与论证 2.1 链表的概念和作用链表是一种链式存储结构，链表属于线性表，采用链式存储结构，也是常用的动态存储方法。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。以“结点的序列”表示线性表称作线性链表（单链表）单链表是链式存取的结构，为找第 i 个数据元素，必须先找到第 i-1 个数据元素。因此，查找第 i 个数据元素的基本操作为：移动指针，比较 j 和 i 单链表 1、链接存储方法链接方式存储的线性表简称为链表（Linked List）。链表的具体存储表示为： ① 用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的） ② 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针（pointer）或链(link)）注意：链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示各种非线性的数据结构。 2、链表的结点结构 ┌───┬───┐ │data │next │ └───┴───┘ data域--存放结点值的数据域 next域--存放结点的直接后继的地址（位置）的指针域（链域）注意： ①链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的。 ②每个结点只有一个链域的链表称为单链表（Single Linked List）。

单链表的建立及其基本操作的实现(完整程序)

#include "stdio.h"/*单链表方式的实现*/ #include "malloc.h" typedef char ElemType ; typedef struct LNode/*定义链表结点类型*/ { ElemType data ; struct LNode *next; }LNode,*LinkList;/*注意与前面定义方式的异同*/ /*建立链表，输入元素，头插法建立带头结点的单链表(逆序)，输入0结束*/ LinkList CreateList_L(LinkList head) { ElemType temp; LinkList p; printf("请输入结点值(输入0结束)"); fflush(stdin); scanf("%c",&temp); while(temp!='0') { if(('A'<=temp&&temp<='Z')||('a'<=temp&&temp<='z')) { p=(LinkList)malloc(sizeof(LNode));/*生成新的结点*/ p->data=temp; p->next=head->next; head->next=p;/*在链表头部插入结点，即头插法*/ } printf("请输入结点值(输入0结束)："); fflush(stdin); scanf("%c",&temp); } return head; } /*顺序输出链表的内容*/ void ListPint_L(LinkList head) { LinkList p; int i=0; p=head->next; while(p!=NULL) { i++; printf("单链表第%d个元素是：",i);

数据结构单链表输入输出(c++)

#include template class link { public: T date; link *next; link(const T info, link *nextvalue=NULL) { date=info; next=nextvalue; } link(link *nextvalue) { next=nextvalue; } }; templateclass inklist{ private: link *head,*tail; link *setpos(const int p); public: inklist(); ~inklist(); bool append(const T value); bool insert(const int p,const T value); bool remove(const int p); void print(); }; template inklist::inklist() { head=tail=new link(NULL); } template inklist::~inklist() { link *tmp; while(head!=NULL) { tmp=head; head=head->next; delete tmp; }

} template link *inklist::setpos(int i) { int count=0; if(i==-1) return head; link *p=new link(head->next); while( p!=NULL && countnext; count++; } return p; } template bool inklist::insert(const int i,const T value) { link *p,*q; if((p=setpos(i-1))==NULL){ cout<<"非法插入点"<(value,p->next); p->next=q; if(p==tail) tail=q; return true;} template bool inklist::remove(const int i) { link *p,*q; if((p=setpos(i-1))==NULL||p==tail) { cout<<"非法删除点"; return false; } q=p->next; if(q==tail) { tail=p; p->next=NULL; delete q; }

数据结构-单链表实验报告

单链表实验报告一、实验目的 1、帮助读者复习C++语言程序设计中的知识。 2、熟悉线性表的逻辑结构。 3、熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉链表的操作为侧重点。二、实验内容 [问题描述] 实现带头结点的单链表的建立、求长度，取元素、修改元素、插入、删除等单链表的基本操作。 [基本要求] （1）依次从键盘读入数据，建立带头结点的单链表；（2）输出单链表中的数据元素（3）求单链表的长度；（4）根据指定条件能够取元素和修改元素；（5）实现在指定位置插入和删除元素的功能。三、算法设计（1）建立带表头结点的单链表；首先输入结束标志，然后建立循环逐个输入数据，直到输入结束标志。（2）输出单链表中所有结点的数据域值；首先获得表头结点地址，然后建立循环逐个输出数据，直到地址为空。（3）输入x,y在第一个数据域值为x的结点之后插入结点y，若无结点x，则在表尾插入结点y;建立两个结构体指针，一个指向当前结点，另一个指向当前结点的上一结点，建立循环扫描链表。当当前结点指针域不为空且数据域等于x的时候，申请结点并给此结点数据域赋值为y，然后插入当前结点后面，退出函数；当当前结点指针域为空的时候，申请结点并给此结点数据域赋值为y，插入当前结点后面，退出函数。（4）输入k，删除单链表中所有的结点k，并输出被删除结点的个数。建立三个结构体指针，一个指向当前结点，另一个指向当前结点的上一结点，最后一个备用；建立整形变量l=0；建立循环扫描链表。当当前结点指针域为空的时候，如果当前结点数据域等于k，删除此结点，l++，跳出循环，结束操作；如果当前结点数据域不等于k，跳出循环，结束操作。当当前结点指针域不为空的时候，如果当前结点数据域等于k，删除此结点，l++，继续循环操作；如果当前结点数据域不等于k，指针向后继续扫描。循环结束后函数返回变量l的值，l便是删除的结点的个数。

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

《数据结构Java》线性表之单链表的建立及操作 package sjjg3; //单链表结点类，T指定结点的元素类型 public class Node { public T data;//数据域，存储数据元素 public Node next;//地址域，引用后继结点 public Node(T data,Node next) {//构造结点，data指定数据元素，next指定后继结点 this.data=data;//T对象引用赋值 this.next=next;//Node对象引用赋值 } public Node() { this(null, null); } public String toString() {//返回结点数据域的描述字符串 return this.data.toString(); } } package sjjg3; //单链表类，实现ADT List声明方法，T表示数据元素的数据类型 public class SinglyList extends Object{ public Node head;//头指针，指向单链表的头结点 //（1）构造方法 public SinglyList() {//构造空单链表 this.head=new Node();//创建头结点，data和next值均为null } public SinglyList(T[] values) {//构造单链表，由values数组提供元素this();//创建空单链表，只有头结点 Node rear=this.head;//rear指向单链表最后一个结点 for(int i=0;i(values[i],null);//尾插入，创建结点链入rear结点之后 rear=rear.next;//rear指向新的链尾结点 } } public boolean isEmpty() {//判断单链表是否空，O(1) return this.head.next==null; } //（2）存取 public T get(int i) {//返回第i个元素，0<=i<表长度。若i越界，则返回null。O(n) Node p=this.head.next; for(int j=0;p!=null && j

数据结构单链表实验报告

一、设计人员相关信息 1.设计者姓名、学号和班号：12地信李晓婧12012242983 2.设计日期：2014. 3.上机环境：VC++6.0 二、程序设计相关信息 1.实验题目：编写一个程序，实现单链表的各种基本运算（假设单链表的元素类型为 char），并在此基础上设计一个程序，完成如下功能：（1）初始化单链表；（2）采用尾插法依次插入元素a,b,c,d,e; （3）输出单链表（4）输出单链表长度（5）判断单链表是否为空（6）输出单链表第3个元素（7）输出元素a的位置（8）在第4个元素位置上插入元素f （9）输出单链表（10）删除第三个元素（11）输出单链表（12）释放单链表 2.实验项目组成：（1）插入和删除节点操作（2）建立单链表尾插法建表（3）线性表基本运算在单链表中的实现初始化线性表销毁线性表判断线性表是否为空表求线性表的长度

3.实验项目的程序结构（程序中的函数调用关系图）： Main LinkList InitList CreateListR DispList ListLength ListEmpty GetElem LocateElem ListInsert ListDelete DestroyList 4.实验项目包含的各个文件中的函数的功能描述： ●尾插法建表CreateListR：将新节点插到当前链表的表尾上，为此必须增加一个尾指针 r，使其始终指向当前链表的尾节点。 ●初始化线性表InitList：该运算建立一个空的单链表，即创建一个头节点； ●销毁线性表DestroyList：释放单链表占用的内存空间，即逐一释放全部节点的空间； ●判断线性表是否为空表ListEmpty：若单链表没有数据节点，则返回真，否则返回假； ●求线性表的长度ListLength：返回单链表中数据节点的个数； ●输出线性表DispList：逐一扫描单链表的每个数据节点，并显示各节点的data域值；

数据结构与算法单链表的实现

单链表的实现实现单链表的基本操作，必须包括初始化链表(元素为空)、销毁链表、求表长、查找、插入、删除、遍历（打印）等操作。请编写程序，实现上述单链表的基本操作。注意：1.元素类型可以自定义 2.可以是带头结点的单链表或不带头结点的单链表 #include #include #include typedef int datatype; typedef struct node { datatype data; struct node *next; }LNode,*LinkList; /* //创建不带头结点的单链表 Linklist Create_LinkList() { return NULL; } */ //创建带头结点的单链表 LinkList Create_LinkList() { LinkList L=NULL; L=(LinkList)malloc(sizeof(LNode)); if(L) L->next=NULL; return L; } //打印单链表

void Print_LinkList(LinkList H) { if(H == NULL) { printf("?????????\n"); } else { printf("head-->"); LinkList p=H->next; while(p!=NULL) { printf("%d",p->data); printf("-->"); p=p->next; } printf("\n"); } } //销毁单链表 void Destroy_LinkList(LinkList *H) { LinkList p, q; p = *H; while(p) { q = p; p = p->next; free(q); } *H = NULL; if(*H==NULL) printf("销毁成功，请退出\n"); else printf("销毁失败\n"); }

数据结构___头插法和尾插法建立链表(各分有无头结点)

实验一链表的建立及基本操作方法实现一、【实验目的】 1、理解和掌握单链表的类型定义方法和结点生成方法。 2、掌握利用头插法和尾插法建立单链表和显示单链表元素的算法。 3、掌握单链表的查找（按序号）算法。 4、掌握单链表的插入、删除算法。二、【实验内容】 1、利用头插法和尾插法建立一个无头结点单链表，并从屏幕显示单链表元素列表。 2、利用头插法和尾插法建立一个有头结点单链表，并从屏幕显示单链表元素列表。 3、将测试数据结果用截图的方式粘贴在程序代码后面。重点和难点：尾插法和头插法建立单链表的区别。建立带头结点和无头结点单链表的区别。带头结点和无头结点单链表元素显示方法的区别三、【算法思想】 1) 利用头插法和尾插法建立一个无头结点单链表链表无头结点，则在创建链表时，初始化链表指针L=NULL。当用头插法插入元素时，首先要判断头指针是否为空，若为空，则直接将新结点赋给L,新结点next指向空，即L=p,p->next=NULL，若表中已经有元素了，则将新结点的next指向首结点，然后将新结点赋给L即（p->next=L,L=p）。当用尾插法插入元素时，首先设置一个尾指针tailPointer以便随时指向最后一个结点，初始化tailPointer和头指针一样即tailPointer=L。插入元素时，首先判断链表是否为空，若为空，则直接将新结点赋给L即L=p，若不为空，else将最后一个元素的next指向新结点即tailPointer->next=p，然后跳出这个if,else语句，将新结点next指向空，并且将tailPointer指向新结点即p->next=NULL,tailPointer=p。 2) 利用头插法和尾插法建立一个有头结点单链表链表有头结点，则在创建链表时，初始化链表指针L->next = NULL。与无头结点区别在于，判断链表为空是根据L->next是否为空。用头插法插入元素时，要判断链表是否为空，若为空则将新结点next指向空，作为表尾，若不为空，则直接插入，将新结点next指向头结点next的指向，再将头结点next指向新结点即p->next=L->next,L->next=p。用尾插法插入元素时，首先也要设置一个尾指针tailPointer以便随时指向最后一个结点，初始化tailPointer=L，与无头结点区别就只是插入第一个元素时有区别。插入元素时，不需要判断链表是否为空，直接进行插入，代码tailPointer->next=p,p->next=NULL,tailPointer=p。 3）带头结点和无头结点单链表元素显示方法的区别：区别在于，显示时带头结点是从头结点next开始即p=L->next，而无头结点链表是直接从L开始即p=L。

数据结构课程设计单链表

目录 1 选题背景 (1) 2 方案与论证 (2) 2.1 链表的概念和作用 (2) 2.3 算法的设计思想 (3) 2.4 相关图例 (4) 2.4.1 单链表的结点结构 (4) 2.4.2 算法流程图 (4) 3 实验结果 (5) 3.1 链表的建立 (5) 3.2 单链表的插入 (5) 3.3 单链表的输出 (6) 3.4 查找元素 (6) 3.5 单链表的删除 (7) 3.6 显示链表中的元素个数（计数） (8) 4 结果分析 (9) 4.1 单链表的结构 (9) 4.2 单链表的操作特点 (9) 4.2.1 顺链操作技术 (9) 4.2.2 指针保留技术 (9) 4.3 链表处理中的相关技术 (9) 5 设计体会及今后的改进意见 (10) 参考文献 (11) 附录代码： (12)

数据结构上机报告：编写一个程序,实现单链表的各种基本运算

《数据结构》上机报告 _2011_年_ 3 _月_ 9 _日姓名_____ 学号_ _ 同组成员 __ _无_ __ 1.实验题目及要求编写一个程序，实现单链表的各种基本运算 2.需求分析建立一个单链表，实现单链表的初始化，插入、删除节点等功能，以及确定某一元素在单链表中的位置。（1）初始化单链表；（2）依次采用尾插入法插入a,b,c,d,e元素；（3）输出单链表L；（4）输出单链表L的长度；（5）判断单链表L是否为空；（6）输出单链表L的第三个元素；（7）输出元素a的位置；（8）在第4个元素位置上插入f元素；（9）输出单链表L；（10）删除L的第3个元素；（11）输出单链表L；（12）释放单链表。

3.概要设计（1）为了实现上述程序功能，需要定义一个简化的线性表抽象数据类型：ADT LinearList { 数据对象：D={ a i|a i∈IntegerSet,i=0,1,2,…,n,n≥0} 结构关系：R={|a i,a i+1 ∈D} 基本操作： InitList_L(L) 操作前提：L是一个未初始化的线性表操作结果：将L初始化为一个空的线性表 CreateList_L(L) 操作前提：L是一个已初始化的空表操作结果：建立一个非空的线性表L ListInsert_L(L,pos,e) 操作前提：线性表L已存在操作结果：将元素e插入到线性表L的pos位置 ListDelete_L(L,pos,e) 操作前提：线性表L已存在操作结果：将线性表L中pos位置的元素删除，删除的元素值通过e返回 LocateList_L(L,e) 操作前提：线性表L已存在操作结果：在线性表L中查找元素e，若存在，返回元素在表中的序号位置；