实现单链表中的各种算法运算

一、 实验目的

1、 掌握单链表存储结构的类型定义； 2、 实现单链表各种基本运算的算法。

二、 实验环境

1、 Windows操作系统； 2、 Visual C++ 6.0

三、 实验内容

实现单链表各种基本运算的算法。

四、 概要设计

1、 存储结构的类型定义：

typedef struct LNode {

ElemType data;

struct LNode *next; } LinkList;

2、 单链表示意图：

head 3、 项目组成图:

a 1 a 2 a 3 ……

∧ a n

4、algo2_2.cpp的程序文件包含的函数原型及功能:

InitList(LinkList *&L) 初始化单链表L DestroyList(LinkList *&L) 释放单链表L ListEmpty(LinkList *L)判断单链表L是否为空表 ListLength(LinkList *L)返回单链表L的元素个数

DispList(LinkList *L)输出单链表L

GetElem(LinkList *L,int i,ElemType &e)获取单链表L的第i个元素

LocateElem(LinkList *L,ElemType e)在单链表L中查找元素e

ListInsert(LinkList *&L,int i,ElemType e)在单链表L中的第i个位置上插入元素e ListDelete(LinkList *&L,int i,ElemType &e)在单链表L中删除第i个元素

5、 exp2_2.cpp程序文件简介： (1)初始化单链表h: InitList(h);

(2)依次采用尾插法插入a,b,c,d,e元素：

ListInsert(h,1,'a'); ListInsert(h,2,'b'); ListInsert(h,3,'c'); ListInsert(h,4,'d');

ListInsert(h,5,'e'); (3)输出单链表h: DispList(h); (4)单链表h长度：ListLength(h)

(5)判断单链表h 是否为空：ListEmpty(h)?\"空\":\"非空\" (6)查找单链表h的第3个元素：GetElem(h,3,e); (7)查找元素f的位置：LocateElem(h,'f')

(8)在第4个元素位置上插入f元素：ListInsert(h,4,'f'); (9)输出单链表h：DispList(h);

(10)删除h的第3个元素：ListDelete(h,3,e); (11)输出单链表h：DispList(h); (12)释放单链表h：DestroyList(h); 6、 oj2-2的项目的模块结构： 在文件algo2-2中，

1.定义单链表结构类型；

2.初始化单链表

3.定义释放单链表的函数

4.定义判断单链表是否为空的函数 5.定义返回单链表元素个数的函数 6.定义输出单链表的函数 7.定义获取第i个元素的函数 8.定义查找元素的函数 9.定义插入元素的函数 10.定义删除元素的函数

在文件exp2-2中分别调用algo2-2中所定义的函数

 函数调用关系图

。

五、 详细设计

源代码清单见附录。

六、 测试、改进、界面

要求：逐一测试各个功能，包括正常测试（例如插入——i在合理范围的测试）、极端情况的测试（例如插入——i超出下限、上限的测试），并逐一做出结论，对出现异常的要给出改进方案。

1、 插入功能测试 i=4时 界面：i=-2时 界面：i=7时

界面：

结论：当元素插入位置在合理范围内，能够准确完成插入；当元素插入位置超出下限时，虽然能够完成插入，但是插入的位置却不是预期那样；当元素插入位置超出上限，元素不能够进行插入。 改进： 当i=-2，

界面：当i=7时

界面：

2、 查找功能测试 i=3时 界面：当i=8时 界面：当i=-2时 界面：

结论：在单链表的的实际长度内，可以查找到任何位置的元素；当i超出单链表的上限或者下限时，不能找到所要找的元素。 改进： i=8时 界面：i=-2时 界面：

3、查找功能测试 当元素在链表内 界面：

当元素不在链表内 界面：

结论：当元素在链表内时，能够找出其相对应的位置；否则，则不能查找其位置。 改进：

当元素不在链表内 界面：

3、 删除功能测试 i=3时 界面：i=8时 界面：i=-2时 界面：

结论：当i在合理范围内，可以删除任意元素；当i超出上限时，无法删除想要删除的元素；当i超出下限时，程序直接删除了第一个元素。 改进： i=8

界面：i=-2时

界面：

附录——源代码清单

/*文件名:algo2-2.cpp*/

#include #include typedef char ElemType;

typedef struct LNode /*定义单链表结点类型*/ {

ElemType data; struct LNode *next; } LinkList;

void InitList(LinkList *&L) { }

void DestroyList(LinkList *&L) { }

int ListEmpty(LinkList *L) { }

int ListLength(LinkList *L)

return(L->next==NULL); LinkList *p=L,*q=p->next; while (q!=NULL) { } free(p);

free(p); p=q; q=p->next;

L=(LinkList *)malloc(sizeof(LinkList)); L->next=NULL;

/*创建头结点*/

{ }

void DispList(LinkList *L) { }

int GetElem(LinkList *L,int i,ElemType &e) {

int j=1;

LinkList *p=L->next; if(i<1||i>ListLength(L)) { } else {

while(jp=p->next; j++;

printf(\"Error!超过合理范围\\n\"); return(0);

LinkList *p=L->next; while (p!=NULL) { }

printf(\"\\n\");

printf(\"%c\p=p->next; LinkList *p=L;int i=0; while (p->next!=NULL) { } return(i);

i++; p=p->next;

e=p->data; return 1; }

int LocateElem(LinkList *L,ElemType e) {

LinkList *p=L->next; int n=1;

while (p!=NULL && p->data!=e) }

}

{ }

if (p==NULL||n>ListLength(L)) { } else

return(n);

printf(\"Error!查找元素不存在!\\n\"); return 0;

p=p->next; n++;

int ListInsert(LinkList *&L,int i,ElemType e) { }

int ListDelete(LinkList *&L,int i,ElemType &e) {

int j=0;

LinkList *p=L,*q; while (jj++; p=p->next; int j=0;

LinkList *p=L,*s;

while (jif (p==NULL||j>i-1) /*未找到第i-1个结点*/ { printf(\"Error! 插入位置不在合理范围内\\n\"); } else { }

s=(LinkList *)malloc(sizeof(LinkList)); /*创建新结点*s*/ s->data=e; p->next=s; return 1;

s->next=p->next;

/*将*s插入到*p之后*/

/*找到第i-1个结点*p*/

return 0; j++; p=p->next;

}

if (p==NULL||j>i-1) } else { }

q=p->next; free(q); return 1;

return 0;

/*未找到第i-1个结点*/

{ printf(\"Error! 删除位置不合理\\n\");

/*找到第i-1个结点*p*/ /*q指向要删除的结点*/ /*从单链表中删除*q结点*/ /*释放*q结点*/

p->next=q->next;

/*文件名:exp2-2.cpp*/ /*文件名:exp2-2.cpp*/ #include #include typedef char ElemType; typedef struct LNode {

ElemType data; struct LNode *next; } LinkList;

/*定义单链表结点类型*/

extern void InitList(LinkList *&L); extern void DestroyList(LinkList *&L); extern int ListEmpty(LinkList *L); extern int ListLength(LinkList *L); extern void DispList(LinkList *L);

extern int GetElem(LinkList *L,int i,ElemType &e); extern int LocateElem(LinkList *L,ElemType e); extern int ListInsert(LinkList *&L,int i,ElemType e); extern int ListDelete(LinkList *&L,int i,ElemType &e); void main() {

LinkList *h; ElemType e; int i; char x;

printf(\"(1)初始化单链表h\\n\"); InitList(h);

printf(\"(2)依次采用尾插法插入a,b,c,d,e元素\\n\"); ListInsert(h,1,'a'); ListInsert(h,2,'b'); ListInsert(h,3,'c'); ListInsert(h,4,'d');

ListInsert(h,5,'e'); printf(\"(3)输出单链表h:\"); DispList(h);

printf(\"(4)单链表h长度=%d\\n\

printf(\"(5)单链表h为%s\\n\空\":\"非空\")); printf(\"(6)单链表的元素位置:\"); scanf(\"%d\ GetElem(h,i,e);

printf(\"对应元素=%c\\n\ printf(\"(7)元素k的位置:\"); printf(\"%d\\n\

printf(\"(8)元素插入位置,插入元素分别为:\"); scanf(\"%d,%c\ ListInsert(h,i,x);

printf(\"(9)输出单链表h:\"); DispList(h);

printf(\"(10)删除h的元素位置:\"); scanf(\"%d\ ListDelete(h,i,e);

printf(\"(11)输出单链表h:\"); DispList(h);

printf(\"(12)释放单链表h\\n\"); DestroyList(h);

}