實驗一

實驗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中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;

}/*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;

}

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;

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;