中北大学 算法与数据结构实验报告

实验类别：算法与数据结构 专

业：信息与计算科学

班 级：13080241 学 号：1308024120 姓 名：杨燕

中北大学理学院

实验一 链表的应用（一）建立线性表

【实验内容】

1、画出详细规范的算法流程图 2、定义链表结点数据类型 3、定义链表数据类型 4、实现单向线性链表的建立 5、实现单向线性链表取元素 6、实现单向线性链表遍历 7、实现单向线性链表插入 8、实现单向线性链表删除 【实验方法与步骤】

1、定义链表结点数据类型

typedef struct LNode { int data; struct LNode *next; }LNode,*LinkList;

其中int data;表示节点是整型数据，若定义浮点型的为：float data;其他类似。

2、定义链表数据类型

typedef char DateType typedef struct LNode { DateType data; struct LNode *next; }LNode,*LinkList;

3、实现单向线性链表的建立 #include

#include #include

typedef struct LNode { int data; struct LNode *next; }LNode,*LinkList;

void CreateList_L(LinkList &L,int n)

{ //逆位序输入n个数据元素的值，建立带头结点的单链表L int i;

1

LNode *p;

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

L->next=NULL;//先建立一个带头结点的空链表

cout<<\请输入创建的单链表中的数据: <如：34,67,3,-9,45,...>\ for(i=n;i>0;--i) { p=(LinkList)malloc(sizeof(LNode));//生成新结点 cin>>p->data; p->next=L->next;//将新结点插入到单链表的头 L->next=p;//修改单链表头结点的指针域 }//for结束

if(n) cout<<\成功创建一个单链表!\ else cout<<\创建了一个空链表!\}

void main() {

LinkList L;

int InitLNodeNum;

cout<<\ cout<>InitLNodeNum;

CreateList_L(L,InitLNodeNum); cout<<\ getch();

}//end of main() function

4、实现单向线性链表取元素

#include #include

2

#include #define ElemType int

#define LIST_MAX_LENGTH 100 //LIST_MAX_LENGTH是单链表L的最大长度 typedef struct LNode { ElemType data; struct LNode *next; }LNode,*LinkList;

void CreateList_L(LinkList &L,int n) { //创建一个带头结点的单链表L int i;

LNode *p;

L=(LinkList)malloc(sizeof(LNode)); L->next=NULL; for(i=n;i>0;--i) { p=(LinkList)malloc(sizeof(LNode)); cin>>p->data; p->next=L->next; L->next=p; } }

int GetElem_L(LinkList L,int i,int &e) //GetElem_L() function

{//L为带头结点的单链表的头指针，当第i个元素存在时，其值赋给e并返回OK， //否则返回Error LNode *p; int j=1;

p=L->next; //初始化，p指向链表第一个结点，j为计数器 while(p&&jnext;++j;} if(!p||j>i)

{ cout<<\这个元素 \不存在!\ getch(); exit(0); }//结束if e=p->data; return (e);

}//结束单链表的取元素

void main() //main() function {

LinkList L;

int e; //e can be Every DataType

3

int i,LListNodeNum; //j is a counter for cycle

cout<<\ cout<<\请输入创建的单链表的大小: \ cin>>LListNodeNum;

cout<<\请输入创建的单链表中的数据: \ CreateList_L(L,LListNodeNum);

cout<>i; //输入要提取的数据

if(i>LListNodeNum) cout<

cout<

5、实现单向线性链表遍历

#include #include #include #include

#define LIST_INIT_LENGTH 10 //LIST_INIT_LENGTH is the Init_Define_Length of LinkList typedef int ElemType; typedef struct LNode { int data; struct LNode *next; }LNode,*LinkList;

void CreateList_L(LinkList &L,int n) //CreatList_L() subfunction { //To Creatre a LinkList L with HeadNode

4