中南大学计算机科学与技术专业

数据结构实验报告

创建单链表和单链表操作

班级：计科1202班

姓名：

学号：0909120629

时间：2013.10.17

实验内容：

1. 创建单链表；

2．在单链表上进行插入、删除操作；

3．设计一个程序，用两个单链表分别表示两个集合，并求出这两个集合的并集。

实验目的：

1.掌握线性表的基本操作：插入、删除、查找等；

2.掌握线性表合并等操作在顺序存储结构和链式存储结构上的实现。

概要设计：

1. 单链表的创建：

在抽象数据类型ADT LIST中，可以使用Initlist()函数初始化一个空表，然再使用CreatList（）函数创建新的链表。 2. 单链表的插入：

在单链表的插入操作中，主要调用该函数：ListInsert_L(Sqlist &L,int i,ElemType e)。函数原型为一个ADT LIST中的基本操作。在该操作中，首先要找到要插入位置的前一个元素的起始地址，然后再利用相关链表的知识解决。最后再将链表的长度加一；

3. 单链表的删除：

在单链表的删除操作中，相比之下，要比插入简单，虽然函数原型类似： ListDelete_L(Sqlist &L,int i)但在具体操作中要方便许多，只需将要删除元素后面的其他数据全部提前一位即可。最后再将链表的长度减掉一。 3. 单链表的合并：

在单链表的合并操作中，主要就是数据的查找和比较，不仅要找到每个表单 的元素，而且要比较它们的大小之后再确定需要把哪个元素放到需要的位置。最后还要把没有参与比较的元素直接放到后面。

详细设计：

详细设计见附录源代码即可；

测试结果：

1. 首先创建一个链表L1；

2. 可以向链表L1中插入元素

3．这时，还可以删除其中的数据，比如12

4 . 到现在为止，链表L1的基本操作：创建，插入，删除 已经完成，现在可以再创建一个链表L2，和L3，使L3为L1和L2的合并后的结果，如下所示

5． L3的显示结果如下：

就是L1：23 ，34， 45， 56和L2：12,67,78的并集。

实验心得：

1. 通过本次实验，首先最重要的是让我对抽象数据类型有了一个大体的了解。 知道了线性表这种类型的结构，也懂得了如何利用顺序存储或者是链式存储来创建一个新的链表，以及对链表的插入，删除和合并。

2. 在线性表的顺序操作中，需要注意一下动态的分配存储是怎样实现的，和链 式存储有什么不同。

3. 在链式存储结构中，要注意头结点的存在与否。特别是在双向链表中，这点 尤为重要。

4. 最后要注意的就是，在各种算法中，每种情况的时间复杂度和空间复杂度。

附录：

源代码如下： #include "malloc.h" #include "stdio.h"

#define OVERFLOW 0 #define OK 1 #define ERROR 0

#define LIST_INIT_SIZE 50 #define LISTINCREMENT 10 typedef int ElemType; typedef int Status; typedef struct {

ElemType *elem; int length; int listsize; } Sqlist;

Status InitList_L(Sqlist &L) {

L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!L.elem) exit(OVERFLOW); L.length=0;

L.listsize=LIST_INIT_SIZE; return OK; }

void CreateList_L(Sqlist &L) {

ElemType *p=L.elem;

int i;

printf("\n请输入顺序表的长度："); scanf("%d",&L.length); if(L.length==0) {

printf("\n此表为空表"); return; }

printf("\n请输入%d个元素：",L.length); for(i=1; i<=L.length; i++) scanf("%d",p++); }

void PrintList_L(Sqlist &L) {

printf("\n新建的顺序表为："); for(int i=1; i<=L.length; i++) printf("%d ",L.elem[i-1]); }

Status ListInsert_L(Sqlist &L,int i,ElemType e) {

ElemType *newbase ,*p,*q;

if(i<1||i>L.length+1) return ERROR; if(L.length>=L.listsize) {

newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType)); if(!newbase) exit(OVERFLOW); L.elem=newbase;

L.listsize+=LISTINCREMENT; }

q=&(L.elem[i-1]);

for(p=&(L.elem[L.length-1]);p>=q;--p) *(p+1)=*p; *q=e;

++L.length; return OK; }

Status ListDelete_L(Sqlist &L,int i) {

ElemType *p,*q;

if((i<1)||(i>L.length)) return ERROR;

p=&(L.elem[i-1]); q=L.elem+L.length-1; for(++p;p<=q;++p) *(p-1)=*p; --L.length; return OK; }

Status MergeList_L(Sqlist La,Sqlist Lb,Sqlist &Lc) {

ElemType *pa,*pb,*pc,*pa_last,*pb_last; pa=La.elem; pb=Lb.elem;

Lc.listsize=Lc.length=La.length+Lb.length;

pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType)); if(!Lc.elem) exit(OVERFLOW); pa_last=La.elem+La.length-1; pb_last=Lb.elem+Lb.length-1;

while(pa<=pa_last&&pb<=pb_last) {

if(*pa<*pb)

*pc++ = *pa++; else

*pc++ = *pb++; }

while(pa<=pa_last) *pc++ = *pa++; while(pb<=pb_last) *pc++ = *pb++; }

int main() {

Sqlist L1,L2,L3;

InitList_L(L1); InitList_L(L2);InitList_L(L3);//初始化线性表L printf("\t\t\t构建第一个线性表：\n"); CreateList_L(L1); PrintList_L(L1);

int shuju,weizi;

printf("\n\n请输入你要插入的数据："); scanf("%d",&shuju);

printf("\n请输入你要插入的位置："); scanf("%d",&weizi);

L …… 此处隐藏：1371字，全部文档内容请下载后查看。喜欢就下载吧 ……