数据结构实验报告线性表及其应用

姓名： 张惠荣        学号：  **********   专业班级：  计算机科学与技术153

实验目的：帮助学生掌握线性表的基本操作在顺序和链表这两种存储结构上的实现，尤以链表的操作和应用作为重点。

问题描述：

1、问题描述：构造一个空的线性表L。

2、在线性表L的第i个元素之前插入新的元素e；

3、在线性表L中删除第i个元素，并用e返回其值。

实验要求：

1、分别利用顺序和链表存储结构实现线性表的存储，并设计出在不同的存储结构中线性表的基本操作算法。

2、在实验过程中，对相同的操作在不同的存储结构下的时间复杂度和空间复杂度进行分析。

算法分析：

顺序结构算法：

#define LIST_INIT_SIZE 100 //线性存储空间的初始分配量

#define LISTINCREMENT 10 //线性表存储空间的分配增量

typedef  struct {

ElemType *elem;//存储空间基址

int length; /当前长度

int listsize;//当前分配的存储量

}Sqlist;

Status InitList_Sq( SqList &L ) 

{ // 操作结果：构造一个空的顺序线性表

   L.elem = (ElemType *) malloc( LIST_INIT_SIZE * sizeof( ElemType ) );

   if ( !L.elem )    exit( OVERFLOW );        // 存储分配失败

   L.length = 0;                 // 空表长度为0

   L.listsize = LIST_INIT_SIZE;    // 初始存储容量

   return OK;

 }//InitList_Sq

 Status ListInsert_Sq (SqList &L,int i ,ElemType e ){

//在顺序线性表L中第i个元素之前插入新的元素e，

//i的合法值为1<If(i<1 || i>ListLength(L)+1) return ERROR;//i值不合法

If（L.length>=L.listsize）{//当前存储空间已满，增加分配

newbase=(ElemType*)realloc(L.elem, (L.listsize+LISTINCREATMENT)*sizeof(ElemType);

if（！newbase）exit(OVERFLOW);//存储分配失败

L.elem= newbase;//新基址

L．listsize+=LISTINCREMENT;//增加存储容量

}

q=&(L.elem[i-1]);//q为插入位置

for(p=(&(L.elem[L.length-1]);p>=q;--p)

*(p+1)=*p;//插入位置及之后的元素后移

*q=e;//插入e

++L.length;//表长增1

return OK;

}//ListInsert_Sq

Status ListDelete_Sq (SqList & L,int i, ElemType e){

//在顺序表L中删除第i个元素，并用e返回其值

if(i<1 || i>ListLength(L)) return ERROR;//i值不合法

for(p=&(L.elem[i]) ;p<&(L.elem[L.length];++p)

*p=*(p+1);//删除位置之后的前移

--l.length;//表长减1

return OK;

}//ListDelete_Sq

链式结构算法：

typedef  struct  LNode{

   ElemType  data;//数据域

   struct  LNode  *next;//指针域

} LNode;

Status Init_L (LinkList &L)

{//构造一个空的线性链表

L=(Linklist*)malloc(sizeof(LNode));

if(!L) exit(OVERFLOW)//分配内存失败

L．next=NULL

return  OK;

}; Init_L

Status Insert_L(LinkList &L, int i, ,ElemType e )

{//在第i个元素之前插入e

q=(Linklist*)malloc(sizeof(LNode));//创建插入结点

if（！q）exit(OVERFLOW)//创建失败

q->data=e;

LNode *p;

p=L.next;

int j=1;

while((p!=NULL)&&(j{

p=p.next;

j++;}

p.next=q.next;

q=p.next;

return OK;}// Insert_L

Status Delete_L(LinkList &L,int i){

//删除第i个元素

p=L.next;

int j=1;

while((p!=NULL)&&(jp=p.next;

j++;}

q=p.next;

p.next=q.next;

e=q.data;

free(q);

return OK;}// Delete_L

实验内容和过程：

根据算法设计C语言程序，在visual stdio 上运行。

顺序结构程序：

#include

#include 

#define LIST_INIT_SIZE 100

#define LISTINCREMENT 10

#define OVERFLOW 1

#define OK 1

#define ERROR 0

typedef  int ElemType;

typedef  int Status;

typedef struct list {

    ElemType *elem;//存储空间基址 

    int length;//当前长度 

    int listsize;//当前分配存储量 

}Sqlist;

//构造一个空的线性表L

Status Initlist_Sq(Sqlist &L)

{

    L.elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType));

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

    L.length = 0;

    L.listsize = LIST_INIT_SIZE;

    return OK;

}

//插入操作函数 

Status insert_Sq(Sqlist &L, int i, int e)

{

    ElemType *p, *q, *newbase;

    if (i<1 || i>L.length + 1)

        return ERROR;

    if (L.length >= L.listsize)//当前存储空间已满，增加分配 

    {

        newbase = (ElemType*)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType));

        if (!newbase) exit(OVERFLOW);

        L.elem = newbase;

        L.listsize += LISTINCREMENT;

    }

    q = &L.elem[i - 1];

    for (p = (&L.elem[L.length - 1]); p >= q; --p)

    {

        *(p + 1) = *p;

    }

    *q = e;

    ++L.length;

    return OK;

}

//删除操作函数 

Status delete_Sq(Sqlist &L, int j)

{

    ElemType *p, *q;

    if (j<1 || j>L.length + 1)

        return ERROR;

    for (p = &(L.elem[j - 1]); p<&(L.elem[L.length]); ++p)

    {

        *p = *(p + 1);

    }

    --L.length;

    return OK;

}

void show_Sq(Sqlist L)

{

    for (int i = 0; i    {

        printf("%d\", L.elem[i]);

    }

}

int main()

{

    Sqlist L;

    int i;

    int a;//输入元素个数 

    printf("请输入要创建的元素个数:\");

    scanf("%d", &a);

    Initlist_Sq(L);

    L.length = a;

    printf("请输入线性表的元素:");

    getchar();

    for (i = 0; i    {

        scanf("%d", &L.elem[i]);

    }

    show_Sq(L);

loop:printf("\\n请输入要进行的操作:\\n 1.插入\\n 2.删除\\n");

    int k;

    scanf("%d", &k);

    switch (k)

    {

    case 1:    int j, e;

        printf("请输入第i个元素之前插入e:\");

        getchar();

        scanf("%d%d", &i, &e);

        insert_Sq(L, i, e);

        show_Sq(L);

        break;

    case 2: printf("请输入要删除第i个元素:\");

        getchar();

        scanf("%d", &i);

        delete_Sq(L, i);

        show_Sq(L);

        break;

    default:printf("输入的数字不正确\\n");

        break;

    }

    printf("\\n是否还要进行操作？(选择是按 1，选择否按 0):");

    scanf("%d", &i);

    if (i == 1)

    {

        goto loop;

    }

    return 0;

}

链式结构程序：

#include

#include 

#define LEN sizeof(struct LNode)

typedef  int ElemType;

typedef  struct LNode {

    ElemType data;//数据域 

    struct  LNode  *next;//指针域

}LNode;

struct LNode *Init_L()  //建立链表

{

    struct LNode *head;

    struct LNode *p, *q;

    head = (struct LNode*)malloc(LEN);

    if (!head) exit(0);//分配内存失败

head->data = 0;

head->next = NULL;

    return(head);

}

struct LNode *creat(struct LNode *head)

{

    LNode *p, *q;

    int a;//输入元素个数 

    printf("请输入要创建的元素个数:\");

    scanf("%d", &a);

    getchar();

    int i;

    for (i = 0; i    {

        p = (struct LNode*)malloc(sizeof(LNode));

        if (!p) exit(0);//分配内存失败

        printf("请输入线性表的第%d个元素:", i + 1);

        scanf("%d", &p->data);

     p->next = NULL;

        if (i == 0) {

            q = p;

            head->next = p;

        }

        else

        {

         q->next = p;

        }

        q = p;

    }

    return (head);

}

struct LNode *Insert_L(struct LNode *head, int i, ElemType e)//在第i个元素之前插入e 

{

    struct LNode *p, *q;

    q = (struct LNode*)malloc(LEN);//创建插入结点 

    if (!q) exit(0);//创建失败

q->data = e;

    p = head->next;

    int j = 1;

    while ((p != NULL) && (j    {

     p = p->next;

        j++;

    }

q->next = p->next;

p->next = q;

    return(head);

}

struct LNode *Delete_L(struct LNode *head, int i)//删除第i个元素 

{

    struct LNode *p, *q;

    ElemType e;

    p = head->next;

    int j = 1;

    while ((p != NULL) && (j    {

     p = p->next;

        j++;

    }

q = p->next;

p->next = q->next;

e = q->data;

    free(q);

    return(head);

}

void print(struct LNode *head)

{

    int i;

    LNode *p;

    p = head->next;

    while (p != NULL)

    {

        printf("%d\", p->data);

     p = p->next;

    }

    printf("\\n");

}

int main()

{

    struct LNode *head;

    head = Init_L();

    creat(head);

    print(head);

loop:printf("\\n请输入要进行的操作:\\n 1.插入\\n 2.删除\\n");

    int k;

    scanf("%d", &k);

    switch (k)

    {

    case 1:

        int i; ElemType e;

        printf("请输入插入位置及元素（空格隔开）");

        scanf("%d%d", &i, &e);

        Insert_L(head, i, e);

        print(head);

        break;

    case 2:

        int j;

        printf("删除第j个元素:\\n");

        scanf("%d", &j);

        Delete_L(head, j);

        print(head);

        break;

    }

    printf("\\n是否还要进行操作？(选择是按 1，选择否按 0):");

    int i;

    scanf("%d", &i);

    if (i == 1)

    {

        goto loop;

    }

    return 0;

}

实验结果：

顺序结构程序截图：

链式结构程序截图：

总结和感想：

经过这次实验，我们通过C语言程序实现了线性表的几个基本操作，对线性表有了更深入的理解。