数据结构实验二：单链表

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

1 实验目的

领会单链表存储结构和掌握单链表中的各种基本运算算法设计。

2 实验内容

编写一个程序linklist.cpp，实现单链表的各种基本运算和整体建表算法（假设单链表的元素类型ElemType为char），并在此基础上设计一个程序exp2-2.cpp完成以下功能。

1. 初始化单链表h。

2. 依次采用尾插法插入a、b、c、d、e元素。
3. 输出单链表h。
4. 输出单链表h的长度。
5. 判断单链表h是否为空。
6. 输出单链表h的第3个元素。
7. 输出元素a的位置。
8. 在第4个元素位置上插入f元素。
9. 输出单链表h。
10. 删除单链表h的第3个元素。
11. 输出单链表h。
12. 释放单链表h。

3 软件程序

#include "stdafx.h"  
#include <stdio.h>  
#include <stdlib.h>  
#include <malloc.h>  
  
typedef int ElemType;  
  
typedef struct LNode  
{  
    ElemType data;  
    struct LNode * next;  
}LinkNode;  
  
void InitList(LinkNode * &L)  
{  
    L=(LinkNode *)malloc(sizeof(LinkNode));  
    L ->next = NULL;  
}  
void DestoryList(LinkNode * &L)  
{  
    LinkNode * pre=L,* p=L->next;  
    while(p!=NULL)  
    {  
        free(pre);  
        pre = p;  
        p = pre->next;  
    }  
    free(pre);  
}  
bool ListEmpty(LinkNode *L)  
{  
    return(L->next==NULL);  
}  
int ListLength(LinkNode * L)  
{  
    int n=0;  
    LinkNode * p = L;  
    while(p!=NULL){  
        n++;  
        p = p->next;  
    }  
    return (n);  
}  
void DispList(LinkNode * L)  
{  
    LinkNode * p = L->next;  
    while (p!=NULL)  
    {  
        printf("%c",p->data);  
        p = p->next;  
    }  
    printf("\n");  
}  
bool GetElem(LinkNode * L,int i,ElemType & e)  
{  
    int j=0;  
    LinkNode *p=L;  
    if(i<=0)return false;  
    while(j<i && p!=NULL)  
    {  
        j++;  
        p = p->next;  
    }  
    if(p==NULL)  
        return true;  
    else  
    {  
        e = p->data;  
        return true;  
    }  
}  
  
int LocateElem(LinkNode * L,ElemType e)  
{  
    int i = 1;  
    LinkNode * p=L->next;  
    while(p!=NULL && p->data!=e)  
    {  
        p = p->next;  
        i++;  
    }  
    if(p==NULL)  
        return (0);  
    else  
        return(i);  
}  
  
  
bool ListInsert(LinkNode * &L,int i,ElemType e)  
{  
    int j=0;  
    LinkNode *p=L,*s;  
    if(i<=0)  
        return false;  
    while(j<i-1 && p!= NULL)  
    {  
        j++;  
        p=p->next;  
    }  
    if(p==NULL)  
        return false;  
    else  
    {  
        s=(LinkNode *)malloc(sizeof(LinkNode));  
        s->data=e;  
        s->next=p->next;  
        p->next=s;  
        return true;  
    }  
}  
bool ListDelete(LinkNode * &L,int i,ElemType &e)  
{  
    int j=0;  
    LinkNode *p=L,*q;  
    if(i<=0)  
        return false;  
    while(j<i-1 && p!=NULL)  
    {  
        j++;  
        p=p->next;  
    }  
    if(p==NULL)  
        return false;  
    else  
    {  
        q=p->next;  
        if(q==NULL)  
            return false;  
        e = q->data;  
        p->next = q->next;  
        free(q);  
        return true;  
    }  
}  
  
int main()  
{  
    LinkNode *h;  
    ElemType e;  
    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。\n");  
    DispList(h);  
    printf("(4)输出单链表 h 的长度。\n");  
    printf("单链表 h 的长度为：%d\n",ListLength(h));  
    printf("(5)判断单链表 h 是否为空。\n");  
    if(ListEmpty(h)){  
        printf("单链表 h 为空。\n");  
    }else  
    {  
        printf("单链表 h 不为空。\n");  
    }  
    printf("(6)输出单链表 h 的第 3 个元素。\n");  
    if(GetElem(h,3,e)){  
        printf("单链表 h 的第 3 个元素为：%c\n",e);  
    }else  
    {  
        printf("单链表 h 中不存在第 3 个元素。\n");  
    }  
    printf("(7)输出元素 a 的位置。\n");  
    printf("元素 a 的位置在：%d\n",LocateElem(h,'a'));  
    printf("(8)在第 4 个元素位置上插入 f 元素。\n");  
    if(ListInsert(h,4,'f')){  
        printf("元素插入成功。\n");  
    }else  
    {  
        printf("元素插入失败。\n");  
    }  
    printf("(9)输出单链表 h。\n");  
    DispList(h);  
    printf("(10)删除单链表 h 的第 3 个元素。\n");  
    if(ListDelete(h,3,e)){  
        printf("单链表 h 中的第 3 个元素：%c 已被删除。\n",e);  
    }else  
    {  
        printf("单链表 h 中的第 3 个元素删除失败。\n",e);  
    }  
    printf("(11)输出单链表 h。\n");  
    DispList(h);  
    printf("(12)释放单链表 h。\n");  
    DestoryList(h);  
    return (0);  
}  

4 实验结果