数据结构实验指导书——线性表的操作

一、实验目的

(1) 掌握线性表的逻辑特征；

(2) 掌握线性表顺序存储结构的特点，熟练掌握顺序表的基本运算；

(3) 熟练掌握线性表的链式存储结构定义及基本操作；

(4) 理解循环链表和双链表的特点和基本运算；

(5 )加深对顺序存储数据结构的理解和链式存储数据结构的理解，逐步培养解决实际问题的编程能力；

二、实验内容

1、创建有若干个元素（可以是整型数值）的顺序表，实现对顺序表的初始化，对已建立的顺序表插入操作、删除操作、遍历输出顺序表。

     要求各个操作均以函数的形式实现，在主函数中调用各个函数实现以下操作：

    （1）从键盘上依次输入21、18、30、75、42、56，创建顺序表，并输出顺序表中的各元素值。

    （2）分别在单链表的第3个位置插入67，给出插入成功或失败的信息，并输出此时顺序表中的各元素值。

    （3）删除顺序表中的第6个数据元素，给出删除成功或失败的信息，并输出此时顺序表中的各元素值。

    （4）查找顺序表中是否有75这个元素，如果有返回该元素在顺序表中的位序。

2、创建有若干个元素（可以是整型数值）的单链表，实现对单链表的初始化，对已建立的顺序表插入操作、删除操作、查找操作、遍历输出单链表表。

    要求各个操作均以函数的形式实现，在主函数中调用各个函数实现以下操作：

   （1）从键盘上依次输入21、18、30、75、42、56，创建单链表，并输出单链表中的各元素值。

   （2）分别在单链表的第4个位置，给出插入成功或失败的信息，并输出单链表中的各元素值。

   （3）删除单链表中的第2个数据元素，给出删除成功或失败的信息，并输出单链表中的各元素值。

   （4）查找顺序表中的第五个元素并输出该元素的值。

三、参考代码

(1) 顺序表的操作

#include

#include

#define TRUE  1

#define FALSE  0

#define OK 1

#define ERROR 0

#define OVERFLOW -2

typedef int Status;

#define INIT_SIZE 100 

  /*初始分配空间的大小*/

/*分配增量*/

typedef int ElemType;

typedef struct{

 int listsize;

}SqList;

/*ElemType elem[INIT_SIZE],注两者区别。存储空间的起始地址。*/

/*线性表中数据元素个数，即表长*/

/*线性表所申请的存储空间的大小*/

SqList CreateList_Sq(SqList L)

/*创建一个空的线性表*/

{

    if (!L.elem)    exit(ERROR);

    L.length=0;   /*表长为0*/

    L.listsize=INIT_SIZE;   

 /*申请的空间为初始大小*/

    return   L;

}

  Status InsertList_Sq(SqList *L, int i, ElemType e)

/*在线性表的第i个位置前插入元素e*/

{  int * newbase,*q,*p;

 值不合法!\\n");exit(ERROR);}

 当前空间已满，增加分配空间*/

}

SqList  DeleteList_Sq(SqList *L, int i, ElemType *e)

/* 删除线性表中的第i个元素，并获得所删元素的值*/

 值不合法!\\n");exit(ERROR);}

}

void Print_Sq(SqList L)

/*遍历顺序线性表*/

}

int GetLength(SqList L)

{

}

int equal(ElemType e1,ElemType e2)

/*判两个元素是否相等*/

{

}

int LocateElem_Sq(SqList L,ElemType e, int (* compare)(ElemType e1,ElemType e2))

}

void Getelem(SqList L,int i,ElemType *e)

{

}

int ListEmpty(SqList L)

{

  if (L.length==0) return 1;

else return 0;

}

{  int i;

}

（2）单链表的操作

/*定义结点类型*/

typedef struct  Node

    ElemType data;            /*单链表中的数据域 */

    struct Node *next;         /*单链表的指针域*/

}Node,*LinkedList;

/*单链表的初始化*/

    Node *L;   

    L = (Node *)malloc(sizeof(Node));   /*申请结点空间*/

    if(L == NULL)                       /*判断是否有足够的内存空间*/

 申请内存空间失败

 将next设置为NULL,初始长度为0的单链表*/

return L;

/*单链表的建立2，尾插法建立单链表*/

 int x;

    L = (Node *)malloc(sizeof(Node));   /*申请头结点空间  */

 初始化一个空链表  */

    r = L;                          /*r始终指向终端结点，开始时指向头结点*/

    {   

        Node *p;   

        p = (Node *)malloc(sizeof(Node));   /*申请新的结点 */

 结点数据域赋值 */

 将结点插入到表头L-->|1|-->|2|-->NULL */

        r = p;    

    }   

    return L;      

/*单链表的插入，在链表的第i个位置插入x的元素*/

    int tempi;                     /*pre为前驱结点*/

    pre = L;   

 查找第i个位置的前驱结点*/

 插入的结点为p*/

    p = (Node *)malloc(sizeof(Node));   

    return L;                              

/*单链表的删除，在链表中删除值为x的元素*/

    Node *p,*pre;                   /* pre为前驱结点，p为查找的结点*/

 查找值为x的元素

    {      

        pre = p;    

    }   

 删除操作，将其前驱next指向其后继。*/

    free(p);   

    return L;   

int GetElem_L(LinkedList L, int i, ElemType e) {

 /*L是带头结点的链表的头指针，以 e 返回第 i 个元素 */

 指向第一个结点，j为计数器 */

 顺指针向后查找，直到 p 指向第 i 个元素  */

 或 p 为空（P=最后一个元素内的指针域值）*/

    return 0;     /* 第 i 个元素不存在

 取得第 i 个元素

}

    LinkedList list,start;   

    list = LinkedListCreatT();   

    printf("\\n");   

    LinkedListInsert(list,i,x);   

    printf("\\n");   

    LinkedListDelete(list,x);    

    printf("\\n");   

}