实验报告数据结构

1. 上机题目

题目：编制一个演示单链表的建立、打印、查找、插入、删除等操作的程序。

内容：给出下面操作的实现： InitList(LinkList *&L)：单链表初始化 ListEmpty(LinkList *L)：单链表是否为空 ListLength(LinkList *L)：计算单链表的长度 DispList(LinkList *L)：打印单链表中的元素

GetElem(LinkList *L,int i,ElemType &e)：读取单链表中第i个元素值 LocateElem(LinkList *L,ElemType e)：定位元素e在单链表中的位置 ListInsert(LinkList *&L,int i,ElemType e)：在单链表中第i个位置上插入元素e

ListDelete(LinkList *&L,int i,ElemType &e)：删除单链表中第i个元素，用e返回其值

2. 需求分析

明确说明程序的开发环境和功能要求。针对主要功能，给出如下说明：

（1） 输入参数的格式和合法取值范围 （整数；大于1的整数） （2） 输出的格式 （整数）

（3） 测试数据 （1.建立单链表：1 2 3 ；2.打印单链表：3 2 1；3.

查找第3个位置的元素：输入3，查找结果为1；4.查找元素的位置：输入3，查找结果为第1个位置；5.插入元素：在第2个位置插入4，3 4 2 1；6.删除元素：删除第3个位置的元素,3 2）

3. 概要设计

（1） 给出所用抽象数据类型的逻辑定义。 ADTList{

数据对象:D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0} 数据关系:R1＝{|ai-1,ai∈D,i=2,...,n} 基本操作：

InitList(LinkList *&L)：单链表初始化 ListEmpty(LinkList *L)：单链表是否为空 ListLength(LinkList *L)：计算单链表的长度 DispList(LinkList *L)：打印单链表中的元素

GetElem(LinkList *L,int i,ElemType &e)：读取单链表中第i个元素值 LocateElem(LinkList *L,ElemType e)：定位元素e在单链表中的位置 ListInsert(LinkList *&L,int i,ElemType e)：在单链表中第i个位置上插入元素e

ListDelete(LinkList *&L,int i,ElemType &e)：删除单链表中第i个元素，用e返回其值

（2） 画出各模块之间的调用关系图。

ListDelete ListCreatDispList ListEmpt

main ListInsert ListLengt

GetElem LocateEle

（3） 用伪码给出主程序的主要处理过程。 void main() {

LinkList L; int k;

InitList(L);

k = menu();

while(k){

switch( k) {

case 1:

ListCreate(L); break; case 2:

DispList(L); break; case 3:

ListEmpty(L); break; case 4:

printf(\"\\nThe length of list is %d\\n.\ break; case 5:

GetElem(L); //按位置查找 break; case 6:

LocateElem(L,ListLength(L)); //按内容查找 break; case 7:

ListInsert(L); break; case 8:

ListDelete(L); break; case 0:

exit(0);

}

}

printf(\"\\n请输入选项：\"); scanf(\"%d\}

4. 详细设计

（1） 确定存储结构，并给出所用抽象数据类型的数据结构定义 #include #include #include #define OK 1 #define ERROR 0

typedef int ElemType; typedef int Status;

（2） 给出所用抽象数据类型中每个操作的伪码算法 Status ListInsert(LinkList &L，int i，ElemType e) {

j=0;p=L;

while (jnext;j++;}

if (p==NULL||j>i-1) /*未找到第i-1个结点*/ return ERROR;

s=(LinkList)malloc(sizeof(LNode)); /*创建新结点*s*/ s->data=e;

s->next=p->next; /*将*s插入到*p之后*/ p->next=s; return OK; }//ListInsert_L

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

j=0;p=L;

while (jnext) { p=p->next;++j;}

if (!(p->next)||j>i-1) /*未找到第i-1个结点*/ return ERROR; q=p->next; /*q指向要删除的结点*/ p->next=q->next; /*从单链表中删除*q结点*/ e=q->data;

free(q); /*释放*q结点*/ return OK;

}

}//ListDelete_L

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

p=L;j=0;

while( p && jnext;j++;} if(!p||j>i)

return ERROR; e=p->data;

return OK; }

（3） 给出其他模块的伪码算法

5. 调试分析

（1） 调试过程中主要遇到哪些问题？是如何解决的？ 循环和if语句的条件和内容，检查不细致，思路不清晰，容易出问题。 还有括号不匹配的时候，也有问题，不过这个问题比较容易解决。

根据伪代码换成C语言时，一定要注意很多细节，比如“等于”，C语言中表达为“==”，伪代码则不需要如此，表达“=”，把意思表清即可，但是C语言不可以，有一点小问题都无法运行程序。 （2） 核心算法的时空复杂度分析和改进设想 （3） 经验和体会

6. 使用说明

列出每一个操作步骤，说明每一步的具体操作要求和注意事项。

1.建立单链表：1 2 3 ； 2.打印单链表：3 2 1；

3.查找第3个位置的元素：输入3，查找结果为1； 4.查找元素的位置：输入3，查找结果为第1个位置； 5.插入元素：在第2个位置插入4，3 4 2 1； 6.删除元素：删除第3个位置的元素,3 2

7. 测试结果

采用测试数据，列出实际的输入、输出结果。

8. 附件

带详细注释的源程序。

//文件名:algo2-2.cpp #include #include #include #define OK 1 #define ERROR 0

typedef int ElemType; typedef int Status;

typedef struct LNode //定义单链表结点类型 { ElemType data;

struct LNode *next; } *LinkList;

void InitList(LinkList &L) { L=(LinkList)malloc(sizeof(LNode)); /*创建头结点*/ L->next=NULL; }

ListEmpty(LinkList &L) { if(L->next==NULL) printf(\"链表为空\"); else printf(\"链表不为空\"); }

int ListLength(LinkList &L) { int i; LinkList p; p = L->next; for(i=0;p!=NULL;i++) p = p->next; return i; }

void DispList(LinkList &L) { LinkList p; p=L->next; while(p!=NULL) { printf(\"%d\ p=p->next; } printf(\"\\n\");

}

void GetElem(LinkList &L) { int j=0,i; LinkList p; p=L; printf(\"您查找的位置为;\\n\"); scanf(\"%d\ while( p && jp=p->next; j++; } if(!p||j>i)

printf(\"第i个元素不存在\\n\"); else

printf(\"第%d个位置的值为%d!\}

void ListCreate(LinkList &L) { int n,i; LinkList p; printf(\"请输入单链表长度：\\n\"); scanf (\"%d\ L=(LinkList)malloc(sizeof(LNode)); L->next=NULL; printf(\"请输入%d个数据\\n\ for(i=n;i>0;--i) { p=(LinkList)malloc(sizeof(LNode)); scanf(\"%d\ p->next=L->next; L->next=p; } }

Status ListInsert(LinkList &L) { ElemType e; int i,j=0; LinkList p=L,s; printf(\"请输入位置和数值\\n\"); scanf(\"%d,%d\

if (p==NULL||j>i-1) /*未找到第i-1个结点*/ { printf(\"Error! 插入位置不在合理范围内\\n\"); return ERROR; } while (jnext; j++; } s=(LinkList)malloc(sizeof(LNode)); /*创建新结点*s*/ s->data=e; s->next=p->next; /*将*s插入到*p之后*/ p->next=s; return OK;

}//ListInsert_L

Status ListDelete(LinkList &L) { ElemType e; int i,j=0; LinkList p=L,q; printf(\"请输入所要删除元素的位置:\"); scanf(\"%d\ while (jnext) { p=p->next; ++j; } if (!(p->next)||j>i-1) /*未找到第i-1个结点*/ { printf(\"Error! 删除位置不合理\\n\"); return ERROR; } else /*找到第i-1个结点*p*/ { q=p->next; /*q指向要删除的结点*/ p->next=q->next; /*从单链表中删除*q结点*/ e=q->data; free(q); /*释放*q结点*/ return OK; } }

int menu() { int k; printf(\"\\n 主菜单\"); printf(\"\\n**************************************\"); printf(\"\\n1.建立单链表 2.显示单链表\"); printf(\"\\n3.测试链表是否为空 4.计算表长\"); printf(\"\\n5.按位置查找 6.按内容查找\"); printf(\"\\n7.插入 8.删除\"); printf(\"\\0.退出\\n\"); printf(\"\\n**************************************\\n\"); printf(\"\\n请输入选项：\"); scanf(\"%d\ return k; }

int LocateElem(LinkList &L,int m) { ElemType e; int i=0; LinkList p=L->next; printf(\"请输入要查找的内容\"); scanf(\"%d\ while(p) {

i++;

if(p->data==e) /* 找到这样的数据元素 */ printf(\"要查找的内容是第%d个元素\ p=p->next; } return OK; }

void main() { LinkList L; int k; InitList(L); k = menu();

while(k){ switch( k) { case 1: ListCreate(L); break; case 2: DispList(L); break; case 3: ListEmpty(L); break; case 4: printf(\"\\nThe length of list is %d\\n.\ break; case 5: GetElem(L); //按位置查找 break; case 6: LocateElem(L,ListLength(L)); //按内容查找 break; case 7: ListInsert(L); break; case 8: ListDelete(L); break; case 0: exit(0); } printf(\"\\n请输入选项：\"); scanf(\"%d\ } }