线性表的基本操作实现及其应用.doc

_线性表的基本操作实现及其应用三、实验步骤
㈠、数据结构与核心算法的设计描述
1、单链表的结点类型定义
/* 定义DataType为int类型*/
typedef int DataType;
/* 单链表的结点类型*/
typedef struct Lnode
{ int data;
struct LNode *next;
} LNode,*LinkList;
2、初始化单链表
LinkList LinkList_L(LinkList &L)
{ L 为带头结点的单链表的头指针
L=(LinkList)malloc(sizeof(LNode)); // 分配存储空间
L->next=NULL; //将链表置空
return L;
}
3、用尾插法创建单链表
void CreateList_L(LinkList &L,int n)
{ L 为带头结点的单链表的头指针,n为创建的链的结点个数
int i;
LNode *p;//定义结点指针
L=(LinkList)malloc(sizeof(LNode));//为链表分配空间
L->next=NULL;
cout<<"为链表创建元素,请输入元素:"<<endl;
for(i=n;i>0;--i)
{ p=(LinkList)malloc(sizeof(LNode));//令P指向头结点
cin>>p->data; // 输入第一个元素
p->next=L->next; //指向下一个地址
L->next=p;
}
if(n) cout<<"链表已成功创建!"<<endl;
else cout<<"创建一个空链表成功!"<<endl;
}4、求单链表的长度
int ListLength_L( LinkList &L )
{ L 为带头结点的单链表的头指针
LNode *p; int NodeNum;
NodeNum = 0;
p = L->next; // 不带头结点的统计p = L;
while( p ) // 查找X p&&p->data!=x { NodeNum++; //k++
p = p->next;
}return NodeNum; //输出累加后的值就是个数
}
5、遍历单链表
void Bianli_L(LinkList &L,int NodeNum)
{ L 为带头结点的单链表的头指针,NodeNum为元素个数
LNode *p=L;int i; //定义结点P并指向头结点
cout<<"链表如下:";
for(i=0;i<NodeNum;i++)
{ p=p->next; //令P指向下个结点
cout<<p->data<<" ";//从第一个结点输出元素
}
cout<<endl;
}
6、向单链表中插入元素
int ListInsert_L(LinkList &L,int i,int e)
{ // L 为带头结点的单链表的头指针,本算法
// 在链表中第i 个结点之前插入新的元素 e
LNode *p=L; //定义结点P并指向头结点
int j=0;
while(p&&j<i-1) //从第一个元素开始查找直到最后一个
{ p=p->next; //查找第i位置并赋给P
++j;
}
if(!p||j>i-1) //如果查到最后仍不存在或结点i输入错误
{ cout<<"Errer! The location is illegal!"<<endl;//提示错误
return (ERROR);
} LNode *s; //定义结点S
s=(LinkList)malloc(sizeof(LNode)); //为S分配地址
s->data=e;//将e的值赋给S
s->next=p->next;//s插入P前
p->next=s;
return (OK);
}
7、从单链表表中查找与给定元素值相同的元素在链表中的位置
int SearchE_L(LinkList &L ,int e)
{ // L 为带头结点的单链表的头指针,e为要查找的元素的值
LNode *p;int a=1; //定义结点p
p=L->next; //p指向链表第一个元素
while(p&&p->data!=e){p=p->next;a++;}//从链表中的第一个元素往后查找指定元素
if(p) return a; //如果找到返回其值
else
cout<<"要查找的元素不存在!"<<endl;//否则此元素不存在
} 8、从单链表表中查找