数据结构线性表实验报告剖析

实 验 报 告

课程名称： 实验名称： 姓 名： 专 业： 班 级： 学 号：

数据结构

线性表的顺序实现和链式实现

计算机科学与技术

计算机科学与技术学院

实验教学中心

2016 年 11月 29日

哈尔滨理工大学计算机科学与技术学院实验教学中心 实验报告

实验项目名称：线性表的顺序实现和链式实现

一、实验目的

1．理解顺序表的结构特点及有关概念，掌握顺序表建立、插入、删除的基本操作算法。 2．理解单链表的结构特点及有关概念，掌握单链表建立、插入、删除的基本操作算法。

二、实验内容

1.顺序表操作内容

1.1建立n个元素的顺序表，实现顺序表建立的基本操作。 1.2在指定位置插入一个元素，实现顺序表插入的基本操作。

1.3在顺序表中删除指定位置上的元素，实现顺序表的删除的基本操作。

2.链式表操作内容

2.1建立一个包括头结点和3个结点的（4，2，1）的单链表，实现单链表建立的基本操作。 2.2在已建好的单链表中的指定位置（x=2）插入一个结点3，实现单链表插入的基本操作。 2.3在一个包括头结点和4个结点的（4，3，2，1）的单链表的指定位置删除一个结点，实现单链表删除的基本操作。

三、实验用设备仪器及材料

计算机及CodeBlocks编程软件。

四、实验原理

利用C语言实现

五、实验操作步骤

1.顺序表的实现及操作代码 #include #include

#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 #define OK 1 #define ERROR -1 #define OVERFLOW -2 typedef int ElemType; typedef int Status; 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;

L.listsize=LIST_INIT_SIZE; return OK; }

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

if(i<1||i>L.length+1) return ERROR; if(L.length>=L.listsize) {

ElemType

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

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

L.listsize += LISTINCREMENT; }

ElemType *q=&(L.elem[i-1]);

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

++L.length; return OK; }

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

if(i<1||i>L.length+1) return ERROR; ElemType *p=&L.elem[i-1]; e=*p;

ElemType *q=L.elem+L.length-1; for(++p;p<=q;++p) *(p-1)=*p; --L.length; return OK; }

Status LocateElem_Sq(SqList L,ElemType e, Status(*compare)(ElemType,ElemType)) {

int i=1;

哈尔滨理工大学计算机科学与技术学院实验教学中心 实验报告

ElemType *p=L.elem;

while(i<=L.length&&!(*compare)(*p++,e))++i; if(i<=L.length) return i; else return 0; }

Status compare(ElemType a,ElemType b) {

if(a==b) return OK; else return 0; }

void MergeList_Sq(SqList La,SqList Lb,SqList&Lc) {

ElemType *pa=La.elem,*pb=Lb.elem,*pc;

Lc.listsize=Lc.length=La.length+Lb.length;

Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType)); if(!Lc.elem)exit(OVERFLOW);

ElemType *pa_last=La.elem+La.length-1; ElemType *pb_last=Lb.elem+Lb.length-1; while(pa<=pa_last&&pb<=pb_last) {

if(*pa<=*pb)*pc++=*pa++; else *pc++=*pb++; }

while(pa<=pa_last) {

*pc++=*pa++; }

while(pb<=pb_last) {

*pc++=*pb++; } }

void ClearList_Sq(SqList &L) {

if(L.length!=0) L.length=0; }

void DestoryList_Sq(SqList &L) {

if(L.elem!=0) free(L.elem); L.elem=NULL; }

void ListSort_Sq(SqList &L,int Sta,int End) {

哈尔滨理工大学计算机科学与技术学院实验教学中心 实验报告

ElemType tmp;

for(int i=Sta-1;ifor(int j=i+1;jif(L.elem[i]>L.elem[j]) {

tmp=L.elem[i];

L.elem[i]=L.elem[j]; L.elem[j]=tmp; } } } }

void prin(SqList &L) {

printf(\"当前线性表元素依次是:\\n\"); for(int i=0;iprintf(\"%d \ }

printf(\"\\n\\n\"); }

int main() {

int n,m,t; SqList L;

InitList_Sq(L);

printf(\"请输入要建立线性表的大小n:\\n\"); scanf(\"%d\

printf(\"请依次输入线性表元素:\\n\"); for(int i=1;i<=n;i++) {

scanf(\"%d\

ListInsert_Sq(L,i,m); }

while(true) {

printf(\"请选择操作（输入0退出操作）:\\n1、排序元素; 2插入元素;\\n\");

scanf(\"%d\ if(t==0)break; else if(t==1) {

int Sta,End;

、删除元素; 3、

哈尔滨理工大学计算机科学与技术学院实验教学中心 实验报告

printf(\"请输入要排序元素的起始终止位置：\\n\"); scanf(\"%d%d\ ListSort_Sq(L,Sta,End); prin(L); }

else if(t==2) {

int loc,val;

printf(\"请输入要删除元素的位置：\\n\"); scanf(\"%d\

ListDelete_Sq(L,loc,val);

printf(\"删除元素的值：%d\\n\ prin(L); }

else if(t==3) {

int loc,val;

printf(\"请输入要插入元素的位置及元素值:\\n\"); scanf(\"%d%d\ ListInsert_Sq(L,loc,val); prin(L); } }

return 0; }

2.链式表的实现及操作 #include #include

#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 #define OK 1 #define ERROR -1 #define OVERFLOW -2 typedef int ElemType; typedef int Status; typedef struct LNode{ ElemType data;

struct LNode *next; }LNode,*LinkList;

Status GetElem_L(LinkList L,int i,ElemType &e) {

LNode *p=L->next; int j=1;

while(p&&j哈尔滨理工大学计算机科学与技术学院实验教学中心 实验报告

p=p->next;j++; }

if(!p||j>i) return ERROR; e=p->data; return OK; }

Status ListInsert_L(LinkList &L,int i,ElemType e) {

LNode *p=L; int j=0;

while(p&&jp=p->next;++j; }

if(!p||j>i-1) {

return ERROR; }

LNode *s=(LinkList)malloc(sizeof(LNode)); s->data=e;

s->next=p->next; p->next=s; return OK; }

Status ListDelete_L(LinkList &L,int i,ElemType &e) {

LNode *p=L; int j=0;

while(p->next&&jp=p->next; ++j; }

if(!p->next||j>i-1) return ERROR; LNode *q=p->next; p->next=q->next; e=q->data; free(q); return OK; }

void CreateList_L(LinkList &L,int n) {

L=(LinkList)malloc(sizeof(LNode)); L->next=NULL; LNode *q;

哈尔滨理工大学计算机科学与技术学院实验教学中心 实验报告

q=L;

for(int i=n;i>0;i--) {

LNode *p=(LinkList)malloc(sizeof(LNode)); scanf(\"%d\ q->next=p; p->next=NULL; q=p; } }

void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc) {

LNode *pc,*pa=La->next,*pb=Lb->next; Lc=pc=La; while(pa&&pb) {

if(pa->data<=pb->data) {

pc->next=pa;pc=pa;pa=pa->next; } else {

pc->next=pb;pc=pb;pb=pb->next; }

pc->next=pa?pa:pb; free(pb); } }

void prin(LinkList &L) {

LNode *p=L->next;

printf(\"当前线性表的元素依次是：\\n\"); while(p) {

printf(\"%d \ p=p->next; }

printf(\"\\n\\n\"); }

int main() {

int n,t; LinkList L;

printf(\"请输入要建立线性表的大小n:\\n\"); scanf(\"%d\

哈尔滨理工大学计算机科学与技术学院实验教学中心 实验报告

printf(\"请依次输入每个元素的值:\\n\"); CreateList_L(L,n); while(true) {

printf(\"请选择操作（输入0退出操作）:\\n1、删除元素; 2、插入元素;\\n\"); scanf(\"%d\ if(t==0)break; else if(t==1) {

int loc,val;

printf(\"请输入要删除元素的位置：\\n\"); scanf(\"%d\

ListDelete_L(L,loc,val);

printf(\"删除元素的值：%d\\n\ prin(L); }

else if(t==2) {

int loc,val;

printf(\"请输入要插入元素的位置及元素值:\\n\"); scanf(\"%d%d\ ListInsert_L(L,loc,val); prin(L); } }

return 0; }

哈尔滨理工大学计算机科学与技术学院实验教学中心 实验报告

六、实验结果分析

1.顺序表代码运行截图

2.链式表代码运行截图