数据结构线性表试验报告

1、实验报告课程数据结构实验名称实验一 线性表学号姓名实验日期：实验一线性表实验目的：1. 理解线性表的逻辑结构特性；2. 熟练掌握线性表的顺序存储结构的描述方法，以及在该存储结构下的基本操作；并能灵活运用；3. 熟练掌握线性表的链表存储结构的描述方法，以及在该存储结构下的基本操作；并能灵活运用；4. 掌握双向链表和循环链表的的描述方法，以及在该存储结构下的基本操作。实验原理：线性表顺序存储结构下的基本算法；线性表链式存储结构下的基本算法；实验内容：2 21设计单循环链表，要求：(1) 单循环链表抽象数据类型包括初始化操作、求数据元素个数操作、插入操作、删 除操作、取消数据元素操作和判非空操作。(

2、2) 设计一个测试主函数，实际运行验证所设计单循环链表的正确性。2 22 .设计一个有序顺序表，要求：(1) 有序顺序表的操作集合有如下操作：初始化、求数据元素个数、插入、删除和取数据元素。有序顺序表与顺序表的主要区别是：有序顺序表中的数据元素按数据元素值非递减有序。(2) 设计一个测试主函数，实际运行验证所设计有序顺序表的正确性。(3) 设计合并函数ListMerge (L1,L2,L3 )，功能是把有序顺序表 L1和L2中的数据元 素合并到L3,要求L3中的数据元素依然保持有序。 并设计一个主函数， 验证该合并函数的 正确性。程序代码：2 - 21 (1)头文件 LinList.h 如下：

3、typedef struct node(DataType data;struct node *next;SLNode;/* (1)初始化 ListInitiate(SLNode * * head)*/void ListInitiate(SLNode * * head)( /*如果有内存空间，申请头结点空间并使头指针head指向头结点*/if(*head=(SLNode *)malloc(sizeof(SLNode)=NULL)exit(1);(*head)->next=NULL; /* 置结束标记 NULL*/*(2)求当前数据元素个数ListLength(SLNode * head)*

4、/int ListLength(SLNode * head)(SLNode *p=head;int size=0;while(p->next!=head)(p=p->next;size+;return size;/*(3)插入 ListInsert(SLNode * head , int i, DataType x)*/*在带头结点的单链表的第i(0<=i<=size)个结点前*/*插入一个存放数据元素x的结点。插入成功时返回 1,失败返回0*/int ListInsert(SLNode * head, int i, DataType x)(SLNode *p, *q;

5、int j;p=head;j=-1;while(p->next!=head && j<i-1)/*最终让指针指向第i-1个结点*/(p=p->next;j+;if(j!=i-1)(printf("The inserted position is error!");return 0;/*生成新结点由指针q指示*/if(q=(SLNode *)malloc(sizeof(SLNode)=NULL) exit(1); q->data=x;q->next=p->next;p->next=q;return 1;/*(4)删除

6、ListDelete(SLNode * head , int i, DataType *x) */*删除带头结点的单链表head的第i(0<=i<=size)个结点前*/*被删除结点的数据元素域由x带回。删除成功时返回1,失败返回0*/int ListDelete(SLNode * head, int i, DataType *x)SLNode *p, *s;int j;p=head;j=-1;while(p->next!=head && p->next->next!=head && j<i-1)/*最终让指针指向第i-1个结

7、点*/p=p->next;j+;if(j!=i-1)printf("The deleted position of parameter is error!");return 0;s=p->next; /*指针s指指向ai结点*/*x=s->data;p->next=p->next->next; /* 删除 */free(s); /*释放指针s所指结点的内存空间*/return 1;/*(5)取数据元素 ListGet(SLNode * head , int i, DataType *x)*/int ListGet(SLNode * hea

8、d, int i, DataType *x) SLNode *p;int j;p=head;j=-1；while(p->next!=head && j<i)(p=p->next;j+;if(j!=i)(printf("The gotten position of parameter is error!");return 0; *x=p->data;return 1;/*(6)撤销单链表 Destroy(SLNode * * head)*/void Destroy(SLNode * * head) (SLNode *p, *p1;p=*

9、head;while(p!=NULL)(p1=p;p=p->next;free(p1);*head=NULL;/*包含printf()函数*/*包含exit()函数*/*包含 malloc()函数*/* 定义 DataType 为 int*/*包含单链表的头文件*/(2)测试主函数如下：#include <stdio.h>#include <stdlib.h>#include <malloc.h>typedef int DataType;#include "LinList.h"void main(void)/*定义头指针变量*/SL

10、Node *head;int i, x;ListInitiate(&head); /* 初始化 */for(i=0;i<10;i+)/* 插入 10 个数据元素 */(if(ListInsert(head, i, i+1)=0) (printf("error!n");return;if(ListDelete(head, 4, &x)=0) /*(printf("error!n");return;for(i=0; i<ListLength(head); i+)(if(ListGet(head, i, &x)=0)(pri

11、ntf("error!n");return;elseprintf("%d ", x);Destroy(&head);2 - 22设计一个有序顺序表头文件程序如下：#define NULL 0typedef struct(DataType ListMaxSize;int size;SeqList;删除第四个数据元素*/*显示当前数据元素*/*取数据元素*/*显示*/*撤销单链表*/void listInitiate(SeqList *L)/*初始化顺序表L */L->size=0;/*定义初始化数据元素个数*/void main(void)i

12、nt ListLength(SeqList L)(return L.size;int ListInsert(SeqList *L, int i, DataType x)(int j;if (L->size>=MaxSize)(printf("顺序表已满无法插入！n");return 0;else if (i<0|i>L->size)(printf("参数i不合法！ n");return 0;else(for(j=L->size; j>i; j-)L->Listj=L->Listj-1;L->Li

13、sti=x;L->size+;return 1;int ListDelete(SeqList *L, int i, DataType *x)(int j;if(L->size<=0)(printf("顺序表已空无数据元素可删！n");return 0;else if(i<0|i>L->size-1)(printf("参数i不合法！ n");return 0;else(*x=L->Listi;for(j=i+1; j<L->size-1;j+)L->Listj-1=L->Listj;L-&g

14、t;size-;return 1;int ListGet(SeqList L, int i, DataType *x)if(i<0|i>L.size-1)printf("参数i不合法！ n");return 0;else*x=L.Listi;return 1;/*测试主函数设计如下：*/#include<stdio.h>#define MaxSize 100typedef int DataType;#include "SeqList.h"int SLOrderInsert(SeqList *L,DataType x)int j;i

15、f(L->size>=MaxSize-1 )printf("顺序表已满无法插入!n");return 0;for(j=L->size-1;j>0&& x<L->listj;j-)L->listj+1=L->listj;L->listj+1=x;L->size+;return 1;SeqList MyList;int a=1,2,4,5,6,8,9;/*数组a中的数据元素递增有序*/int i,n=7;int x;ListInitiate(&MyList);for(i=0;i<n+1;i+)ListInitiate(&MyList);SLOrderInsert(&MyList,ai);for(i=0;i<n+1;i+)ListGet(MyList,i,x);printf("%d”,ai);实验结果：(1) 2-21运行结果如下:e F:shiijnTC2TC, ESE回(2) 2-22运行结果如下:R F:shujuTC2TC_EXE 12456