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

实验一 链表的建立及基本操作方法实现

一、【实验目的】

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是否为空。

数据结构之线性表---单链表的拆分

数据结构实验之链表五：单链表的拆分

Time Limit: 1000MS Memory limit: 65536K

题⽬描述

输⼊N个整数顺序建⽴⼀个单链表，将该单链表拆分成两个⼦链表，第⼀个⼦链表存放了所有的偶数，第⼆个⼦链表存放了所有的奇数。两

个⼦链表中数据的相对次序与原链表⼀致。

输⼊

第⼀⾏输⼊整数N;；

第⼆⾏依次输⼊N个整数。

输出

第⼀⾏分别输出偶数链表与奇数链表的元素个数；

第⼆⾏依次输出偶数⼦链表的所有数据；

第三⾏依次输出奇数⼦链表的所有数据。

⽰例输⼊

10

1 3 22 8 15 999 9 44 6 1001

⽰例输出

4 6

22 8 44 6

1 3 15 999 9 1001

没按照课本上的写法，⾃⼰有空再学吧！ ⽤的⾃⼰的对拆分的写法！

#include

#include

#include

#include

#include

#include

using namespace std;

struct node

{

int data;

struct node *next;

};

struct node *creat(int n)

{

int i;

struct node *head, *tail, *p;

head=new node;

head->next=NULL;

tail=head;

for(i=0; i

{

p=new node;

cin>>p->data;

p->next=NULL;

tail->next=p;

tail=p;

}

return head;

}

int main()

{

int n;

int len1, len2; int i, j;

cin>>n;

struct node *head, *w, *h1, *t1, *h2, *t2;

head = creat(n);

len1=0;

len2=0;

w=head->next;

delete head;

h1=new node; h1->next=NULL; t1=h1;

数据结构-单链表基本操作实现（含全部代码）

今天是单链表的实现，主要实现函数如下：

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/14

Author: Frank Yu

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)[加⼊了查找]

#include 〈stdio.h>

＃include

＃include 〈stdlib.h>

/＊

数据结构C语言版 线性表的单链表存储结构表示和实现

P28—31

编译环境：Dev-C++ 4。9。9。2

日期：2011年2月10日

＊/

typedef int ElemType;

// 线性表的单链表存储结构

typedef struct LNode

{

ElemType data; //数据域

struct LNode *next； //指针域

}LNode, ＊LinkList；

// typedef struct LNode *LinkList； // 另一种定义LinkList的方法

// 构造一个空的线性表L

int InitList（LinkList ＊L)

{

/＊

产生头结点L，并使L指向此头结点,头节点的数据域为空，不放数据的。

void ＊ malloc(size_t)

这里对返回值进行强制类型转换了,返回值是指向空类型的指针类型.

＊/

（＊L） = (LinkList）malloc（ sizeof（struct LNode) ）;

if( ！(＊L） )

exit（0）； // 存储分配失败

(＊L)-〉next = NULL； // 指针域为空

return 1；

}

// 销毁线性表L,将包括头结点在内的所有元素释放其存储空间。

int DestroyList（LinkList ＊L）

｛

LinkList q;

// 由于单链表的每一个元素是单独分配的，所以要一个一个的进行释放

while（ ＊L )

｛

q = (*L)—〉next;

free（ ＊L ）； //释放

*L = q;

}

return 1；

｝ /*

将L重置为空表,即将链表中除头结点外的所有元素释放其存