实验1 线性表的链表设计与实现
| 院 、系 |
海师计教系 |
班级 |
计本二班 |
| 学 号 |
200624101101 |
姓名 |
杨振平 |
| 完成日期 |
2007-9-23 |
源程序名 |
Xianxingbiao.cpp |
一、题目
编制一个演示单链表插入、删除、查找等操作的程序。
二、需求分析
本程序在Windows环境下用用Visual C++编写，完成单链表的生成，任意位置的插入、删除，以及确定某一元素在单链表中的位置。
① 输入的形式和输入值的范围：插入元素时需要输入插入的位置和元素的值；删除元素时输入删除元素的位置；查找操作时需要输入元素的值。在所有输入中，元素的值都是整数
② 输出的形式：在所有三种操作中都显示操作是否正确以及操作后单链表的内容。其中删除操作后显示删除的元素的值，查找操作后显示要查找元素的位置。
③ 程序所能达到的功能：完成单链表的生成（通过插入操作）、插入、删除、查找操作 ④ 测试数据：
A． 插入操作中依次输入11，12，13，14，15，16，生成一个单链表
B． 查找操作中依次输入12，15，22返回这3个元素在单链表中的位置
C． 删除操作中依次输入2，5，删除位于2和5的元素
二、概要设计
1）为了实现上述程序功能，需要定义单链表的抽象数据类型：
ADT LinkList {
数据对象：D={ai|ai∈IntegerSet,i=0,1,2,…,n,n≥0}
数据关系：R={<ai,ai+1>|ai,ai+1 ∈D}
基本操作：
InitLinkList(&L)
操作结果：构造一个空的单链表L.
InsLinkList(&L,pos,e)
初始条件：单链表L已存在
操作结果：将元素e插入到单链表L的pos位置
DelLinkList(&L,pos,&e)
初始条件：单链表L已存在
操作结果：将单链表L中pos位置的元素删除，元素值置入e中返回
LocLinkList(L,e)
初始条件：单链表L依存在
操作结果：单链表L中查找是否元素e，若存在，返回元素在表中的位
置；若不存在，返回-1.
2）本程序包含7个函数：
① 主函数main()
② 初始化单链表函数InitLinkList()
③ 显示操作菜单函数menu()
④ 显示单链表内容函数dispLinkList()
⑤ 插入元素函数InsLinkList()
⑥ 删除元素函数DelLinkList()
⑦ 查找元素函数LocLinkList()
各函数间关系如下：
三、详细设计
为了实现概要设计中定义的所有的数据类型，对每个操作伪码算法；对主程序和其他模块也都需要写出伪码算法；画出系统结构图
1) 结点类型和指针类型
Type int ElemType
typedef struct Node {
ElemType data;
struct node *next;
}Node,*LinkListl;
2) 为了方便，在单链表中设头结点，其data域没有意义
单链表的基本操作如下：
void InitLinkList(LinkList &L)
void DispLinkList(LinkList L)
void InsLinkList(LinkList &L,int i,int e)
void DelLinkList(LinkList &L,int i,int &e)
int LocLinkList(LinkList L,int e)
void menu()
四、测试结果
1） 建立单链表：选择1，分别输入11，12，13，14，15。得到单链表（15，14，13，12，11）
2） 插入：
① 选择1输入（1，100），得到单链表（15，100，14，13，12，11）
② 选择1输入（-1，2），显示输入错误
③ 选择1输入（7，2），显示输入错误
④ 选择1输入（6，2），得到单链表（15，100，14，13，12，11，2）
3） 删除：
① 选择2，输入1。返回e=100，得到单链表（15，14，13，12，11，2）
② 选择2，输入0。返回e=15，得到单链表（14，13，12，11，2）
③ 选择2，输入4。返回e=2，得到单链表（14，13，12，11）
④ 选择2，输入5。返回输入错误
4） 查找
① 选择3，输入14。返回pos=0
② 选择3，输入100。返回输入错误
五、调试分析
通过链表的实现体会链表在数据结构中的思想，
调试过程中初始化是关键而简单的一部分，
经过反复的调试终于成功了！
六、 源程序（带注释）
# include "malloc.h"
# include "iostream.h"
# include "process.h"
# include "conio.h"
# include "stdlib.h"
# include "stdio.h"
# define LIST_INIT_SIZE 100
# define LIST_INIT_LENGTH 10
# define LISTINCREMENT 10
# define OK 1
# define ERROR 0
typedef int Status;
typedef int ElemType; /* 定义ElemType为int类型 */
typedef struct LNode /* 单链表的结点类型 */
{ ElemType data;
struct LNode *next;
}LNode,*LinkList;
Status InitLinkList(LinkList &L) /*初始化链表 */
{
L=(LinkList)malloc(sizeof(LNode));
if(!L) exit(ERROR);
L->next=NULL;
return OK;
}/*init */
Status InsLinkList(LinkList &L,int i,ElemType e)
{ /*时间复杂度为表长*/
LinkList p,s;
int j;
p=L;j=0;
while(p->next && j<i-1) /*寻找第i个结点,p是指向i的前驱指针*/
{
p=p->next;
++j;
}
if(!p ||j >i-1) return ERROR; /*i小于1或大于表长，则退出*/
/*插入操作可以在最后一个元素后面再插入一个元素，所以P的后继可以为空*/
s=(LinkList)malloc(sizeof(LNode)); /*生成新结点*/
if(!s) exit(ERROR);
s->data=e;
s->next=p->next; /*插入到L中*/
p->next=s;
return OK;
}/*ListInsert Before i */
Status DelLinkList(LinkList &L,int i,ElemType &e)
{
LinkList q,p;
p=L;
int j=0;
while(p->next && j<i-1)
{
p=p->next;
++j;
}
if(!(p->next) || j>i-1) return ERROR;
q=p->next;
p->next=q->next;
e=q->data;free(q);
return OK;
}
Status ListEmpty_L(LinkList L)
{
LinkList p;
p=L;
if(!(p->next))
return ERROR;
else
return OK;
}
void dispLinkList(LNode *head)
{
LNode *p=head->next;
printf("输出该链表:");
while(p)
{
printf("%-5d--->",p->data);
p=p->next;
}
if(p==NULL)
{
printf("^/n/n/n");
}
}
Status LocLinkList(LinkList L,int i,ElemType &e)
{
LinkList p; int j;
p=L->next;j=1;
while(p&&j<i){
p=p->next;++j;
}
if(!p||j>1) return ERROR;
e=p->data;
return OK;
}
int menu()
{ int d;
printf("请选择所要进行的操作/n");
printf("1. 初始化链表 2. 链表插入/n ");
printf("3. 遍历链表 4.从链表中删除元素/n");
printf("5.检查链表是否为空 6.从链表中查找元素/n");
printf("0. 退出....../n");
cin >> d;
return d;
}
void main()
{
int quit=0;
int i,e;
LinkList L;
while(!quit)
switch(menu())
{
case 1: cout << InitLinkList(L)<<endl;break;
case 2: cin >> i >> e;
cout<<InsLinkList(L,i,e)<<endl;break;
case 3: dispLinkList(L);break;
case 4: cin >> i;
cout<<DelLinkList(L,i,e)<<endl<<e<<endl;break;
case 5:cout<<ListEmpty_L(L)<<endl;break;
case 6:cin >> i;
cout<<LocLinkList(L,i,e)<<endl<<e<<endl;break;
case 0: quit = 1;
}
