实验二 (2)

2014～2015学年 第 一 学期 2012级 通信工程 专业 班级： 学号： 姓名：

实验一 线性表及其应用

一、 实验目的：

1．掌握用 C语言调试程序的基本方法。

2．掌握线性表的基本运算，如插入、删除等。

二、 实验内容：

1． 编写程序，实现顺序表的各种基本运算（假设顺序表的元素类型为char），并在此基础上完成如下功能： （1） 初始化顺序表L； （2） 采用尾插法依次插入元素a、b、c、d、e； （3） 输出顺序表L； （4） 输出顺序表L的长度； （5） 判断顺序表L是否为空； （6） 输出顺序表L中的第3个元素； （7） 输出元素a的位置； （8） 在的4个元素的位置上插入元素f； （9） 输出顺序表L；

（10） 删除L中的第3个元素； （11） 输出顺序表L； （12） 释放顺序表L。

2． 编写程序，实现单链表的各种基本运算（假设顺序表的元素类型为char），并在此基础上完成如下功能：

（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。 三、实验要求：

1． C完成算法设计和程序设计并上机调试通过。 2． 撰写实验报告，提供实验结果和数据。 3． 写出算法设计小结和心得。

第 1 页 共 14 页

三、 程序源代码： 实验一

#include #include #define MaxSize 50 typedef char ElemType;

typedef struct {

ElemType data[MaxSize];

int length;

} SqList;

//初始化

void InitList(SqList *&L) {

L=(SqList *)malloc(sizeof(SqList)); L->length=0;

}

//销毁

void DestroyList(SqList *L) { free(L);

}

//判断是否为空

int ListEmpty(SqList *L) {

return(L->length==0);

第 2 页 共 14 页

}

//判断长度

int ListLength(SqList *L) { }

//显示输出

void DispList(SqList *L)

int GetElem(SqList *L,int i,ElemType &e)

int LocateElem(SqList *L, ElemType e)

{ int i=0;

while (ilength && L->data[i]!=e) i++;

第 3 页 共 14 页

return(L->length);

{ int i;

if (ListEmpty(L)) return; for (i=0;ilength;i++) printf(\"%c\printf(\"\\n\"); }

{

if (i<1 || i>L->length) return 0; e=L->data[i-1]; return 1; }

if (i>=L->length) return 0; else

return i+1; }

//尾插法

int ListInsert(SqList *&L,int i,ElemType e)

int ListDelete(SqList *&L,int i,ElemType &e)

{ int j;

if (i<1 || i>L->length) return 0; i--;

//将顺序表位序转化为elem下标*/

{ int j;

if (i<1 || i>L->length+1) return 0; i--;

//将顺序表位序转化为elem下标*/

//将data[i]及后面元素后移一个位置*/

for (j=L->length;j>i;j--) L->data[j]=L->data[j-1]; L->data[i]=e; L->length++; return 1; }

//顺序表长度增1*/

e=L->data[i];

for (j=i;jlength-1;j++) L->data[j]=L->data[j+1]; L->length--; return 1;

第 4 页 共 14 页

}

void main() {

printf(\"输出L\\n\"); SqList *L; ElemType e; InitList(L); ListInsert(L,1,'a'); ListInsert(L,2,'b'); ListInsert(L,3,'c'); ListInsert(L,4,'d'); ListInsert(L,5,'e');

//输出L

DispList(L);

//判断长度

printf(\"判断长度\\n\");

printf(\"ListLength(L)=%d\\n\

//判断为空

printf(\"判断是否为空\\n\");

printf(\"ListEmpty(L)=%d\if (ListEmpty(L))

printf(\" 当前为空\\n\");

else

printf(\" 当前不为空\\n\");

printf(\"ListEmpty(L)=%d\\n\

//定位第三个

printf(\"定位第三个\\n\"); GetElem(L,3,e);

第 5 页 共 14 页

printf(\"e=%c\\n\

//查找A的位置

printf(\"查找A的位置\\n\");

printf(\"LocateElem(L,'a')=%d\\n\

//第四个位置插入f printf(\"第四个位置插入f\\n\");

ListInsert(L,4,'f');

//输出L printf(\"输出L\");

DispList(L);

//删除第三个元素 printf(\"删除第三个元素\\n\");

ListDelete(L,3,e);

//输出L printf(\"输出L\");

DispList(L);

//释放空间 printf(\"当前已经释放空间\\n\"); DestroyList(L);

} 实验二

#include #include typedef char ElemType; typedef struct LNode //定义单链表结点类型 {

ElemType data;

struct LNode *next; } LinkList;

第 6 页共 14 页

void InitList(LinkList *&L) {

L=(LinkList *)malloc(sizeof(LinkList));

//创建头结点 L->next=NULL;

}

void DestroyList(LinkList *&L) { LinkList *p=L,*q=p->next; while (q!=NULL) {

free(p); p=q; q=p->next; } free(p);

}

int ListEmpty(LinkList *L) { return(L->next==NULL);

}

int ListLength(LinkList *L) { LinkList *p=L;int i=0; while (p->next!=NULL)

{

第 7 页 共 14 页

}

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

return(i);

void DispList(LinkList *L) { }

int GetElem(LinkList *L,int i,ElemType &e) {

int j=0; LinkList *p=L; while (jnext; }

if (p==NULL) return 0; else {

第 8 页 共 14 页

LinkList *p=L->next; while (p!=NULL) {

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

printf(\"\\n\");

}

e=p->data; return 1; }

int LocateElem(LinkList *L,ElemType e) { }

int ListInsert(LinkList *&L,int i,ElemType e) {

int j=0;

LinkList *p=L,*s; while (jnext; }

if (p==NULL) //未找到第i-1个结点

第 9 页 共 14 页

LinkList *p=L->next; int n=1;

while (p!=NULL && p->data!=e) {

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

if (p==NULL) return(0); else

return(n);

}

return 0; else {

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

//将*s插入到*p之后

//创建新结点*s

//找到第i-1个结点*p

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

int ListDelete(LinkList *&L,int i,ElemType &e) {

int j=0;

LinkList *p=L,*q; while (jnext; }

if (p==NULL) return 0; else {

q=p->next;

//q指向要删除的结点

//找到第i-1个结点*p

//未找到第i-1个结点

if (q==NULL) return 0; e=q->data; p->next=q->next; free(q); return 1; }

第 10 页 共 14 页

//从单链表中删除*q结点 //释放*q结点

}

void main() { LinkList *H; char D; InitList(H); ListInsert(H,1,'a'); ListInsert(H,2,'b'); ListInsert(H,3,'c'); ListInsert(H,4,'d'); ListInsert(H,5,'e'); //输出H

printf(\"输出H:\");DispList(H);

printf(\"判断是否为空:\"); if(ListEmpty(H))

printf(\"当前为空\\n\"); else

printf(\"当前不为空\\n\");

//判断A的位置

printf(\"判断A的位置:\"); int b=LocateElem(H,'a'); printf(\"%d\

//寻找地三个元素 // GetElem(H,3,D);

// printf(\"第三个元素为%s\

//第四位置插入f

第 11 页共 14 页

printf(\"\\n第四位置插入f\"); ListInsert(H,4,'f');

//输出H

printf(\"\\n输出H:\");DispList(H);

//删除第三个

printf(\"已经删除第三个\"); }

四、 测试结果（程序运行结果采用截图的方式打印）：

实验一结果 //销毁链表

printf(\"已经销毁脸链表H\\n\"); DestroyList(H); //输出H

printf(\"当前链表输出H:\");DispList(H); ListDelete(H,3,D);

第 12 页 共 14 页

实验二结果

五、 小结（包括收获、心得体会、存在的问题及解决问题的方法、建议等）

注：内容一律使用宋体五号字，单倍行间距

通过这次实验我掌握了用C浯言对数据结构的一些问题程序的初步编程，更加牢固掌握了数据结构的部分知识，但发现了许多问题与不足。C语言的部分知识基本快忘完了，一些基本操作也忘了一部分，造成实验的难以继续。其次数据结构掌握的不牢不全面，我应该在今后的日子多温习温习C语言，多看看数据结构课本，多做实验，更加好的学习数据结构。

第 13 页 共 14 页

第 14 页共 14 页