实验一

简介: 实验1  线性表的链表设计与实现   院 、系  海师计教系  班级 计本二班 学   号  200624101101  姓名  杨振平 完成日期  2007-9-23     源程序名  Xianxingbiao.cpp   一、题目 编制一个演示单链表插入、删除、查找等操作的程序。

实验线性表的链表设计与实现

 

院 、系

 海师计教系

 班级

计本二班

  

 200624101101

 姓名

 杨振平

完成日期

 2007-9-23    

源程序名

 Xianxingbiao.cpp

 

一、题目

编制一个演示单链表插入、删除、查找等操作的程序。

二、需求分析      

本程序在Windows环境下用用Visual C++编写,完成单链表的生成,任意位置的插入、删除,以及确定某一元素在单链表中的位置。

输入的形式和输入值的范围:插入元素时需要输入插入的位置和元素的值;删除元素时输入删除元素的位置;查找操作时需要输入元素的值。在所有输入中,元素的值都是整数

输出的形式:在所有三种操作中都显示操作是否正确以及操作后单链表的内容。其中删除操作后显示删除的元素的值,查找操作后显示要查找元素的位置。

程序所能达到的功能:完成单链表的生成(通过插入操作)、插入、删除、查找操作  测试数据:

    A. 插入操作中依次输入111213141516,生成一个单链表

    B. 查找操作中依次输入121522返回这3个元素在单链表中的位置

    C. 删除操作中依次输入25,删除位于25的元素

二、概要设计

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插入到单链表Lpos位置

       DelLinkList(&L,pos,&e)

            初始条件:单链表L已存在

            操作结果:将单链表Lpos位置的元素删除,元素值置入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,分别输入1112131415。得到单链表(1514131211

2) 插入:

 选择1输入(1100),得到单链表(1510014131211

 选择1输入(-12),显示输入错误

 选择1输入(72),显示输入错误

 选择1输入(62),得到单链表(15100141312112

3) 删除:

 选择2,输入1。返回e=100,得到单链表(15141312112

 选择2,输入0。返回e=15,得到单链表(141312112

 选择2,输入4。返回e=2,得到单链表(14131211

 选择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;  /* 定义ElemTypeint类型 */

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;

}

目录
相关文章
|
关系型数据库 MySQL 索引
我做了一天的实验!
对记录加锁时,加锁的基本单位是 next-key lock,它是由记录锁和间隙锁组合而成的,next-key lock 是前开后闭区间,而间隙锁是前开后开区间。但是,next-key lock 在一些场景下会退化成记录锁或间隙锁。 那到底是什么场景呢?今天,我们就以下面这个表来进行实验说明。
我做了一天的实验!
|
小程序 程序员
ass3实验
1.自我情况 2.使用过程 3.心得体会
|
算法 C++
实验四
实验四  图的基本操作   院 、系  海师计教系  班级 计本二班 学   号  200624101101  姓名  杨振平 完成日期  2007-11-19   源程序名 1.      cpp和222.cpp和图.cpp   一、题目 编制一个演示用邻接矩阵和邻接表存储结构实现的图的深度优先遍历和广度优先遍历算法的程序。
1267 0
|
缓存 Linux
我做了个实验!
这次我们就以 malloc 动态内存分配为切入点,我在文中也做了小实验: • malloc 是如何分配内存的? • malloc 分配的是物理内存吗? • malloc(1) 会分配多大的内存? • free 释放内存,会归还给操作系统吗? • free() 函数只传入一个内存地址,为什么能知道要释放多大的内存?
我做了个实验!
|
C++
C++程序设计实验1
C++程序设计实验1
120 0
实验3遇到的问题
ElemType是抽象数据类型的定义啊你想定义什么就定义什么了ElemType *是定义指向这种类型的指针p=(ElemType *)malloc(8*sizeof(ElemType))开辟8个ElemType大小的内存空间,把地址分配给指向ElemType的指针p   通俗的说,ElemType就...
1012 0
|
网络架构 iOS开发 内存技术
|
Linux
实验六
实验6  进程间通信 一、实验目的: 1.      了解进程与程序的区别,加深对进程概念的理解加; 2. 掌握进程并发执行的原理,及其所引起的同步、互斥问题的方法 二、实验要求:     完成实验内容并写出实验报告,报告应具有以下内容:    1. 实验目的。
1312 0
|
C++ iOS开发
实验八
1.实验名称:实验八 文件拷贝 2.实验时间:2008-6-13 3.实验目的:编程用面向对象设计思想分析、设计并实现实验八的内容。 4.实验内容:利用c++文件操作函数实现文件,将text1.txt中的内容拷贝到text2.txt中。
816 0

热门文章

最新文章