数据结构上机实验（编程）（单链表的基本操作）

Question

实验目的及要求
1.熟悉线性表的基本运算在顺序存储结构上的实现；
2.以线性表的基本操作（建表、插入、删除等）的实现为重点；
3.通过本次实验帮助学生加深对C/c++ 语言的使用（特别是函数参数、数据类型的定义和数组的使用）。

不需要太难的结构，最好带上解释..需要调用函数的那种...谢谢啦

Answer 1

我们正在学数据结构，两星期前写好了线性表的所有基本操作，运行全部正确。包括InitList、DestoryList、ClearList、ListEmpty、ListLength、GetElem、LocateElem、PriorElem、NextElem、ListInsert、ListDelete、ListTraverse

我所编译的环境是VC++ 6.0，有三个文件linklist.h linklist.cpp main.cpp 至于怎样用你应该知道的，我就不多说了。

========================linklist.h============================
#include <iostream>
using namespace std;

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

typedef int Status;
typedef int ElemType;

//线性表的单链表存储结构
typedef struct LNode
{
ElemType data;
int len;
struct LNode * next;
}LNode,*LinkList;

void CreateList_L(LinkList &L,int n);

int ListLength(LinkList L);

Status ListInsert(LinkList & L,int i,ElemType e);

Status ListDelete(LinkList & L,int i,ElemType & e);

ElemType GetElem(LinkList L,int i);

Status EmptyList_L(LinkList L);

int LocateElem(LinkList L,ElemType e);

Status PriorElem(LinkList L,ElemType curr_e,ElemType & e);

Status NextElem(LinkList L,ElemType curr_e,ElemType & e);

Status ListTraverse(LinkList L);

Status ClearList_L(LinkList & L);

void DestoryList_L(LinkList & L);

==========================linklist.cpp=======================
#include "linklist.h"

int LISTLEN = 0;

//逆序输入n个元素的值
//创建带有头结点的线性单链表
void CreateList_L(LinkList &L,int n)
{

L = (LinkList)malloc(sizeof(LNode));
L->len = 0;
L->next = NULL;

for(int i = n;i>0;--i)
{
LinkList p = (LinkList)malloc(sizeof(LNode));
cout<<"请输入元素的值(前插):";
cin>>p->data;
p->next = L->next; //插入到表头
L->next = p;
L->len++;
LISTLEN++;
}
}

//求表长
int ListLength(LinkList L)
{
int len1=0;
LinkList p = L->next;
while(p)
{
p = p->next;
len1++;
}
return len1;
//return L->len;

}

//在链表的第i位之前插入元素e
// i 的合法位置是：1 <= i <= ListLength(L)+1
Status ListInsert(LinkList & L,int i,ElemType e)
{
if(i<1 || i>ListLength(L)+1)
{
cout<<"插入失败! 访问越界..."<<endl;
return ERROR;
}
else
{
int j;
LinkList p = L;
for(j = 0;j<i-1;j++) //for循环结束后p将指向第i-1个元素，即应该在p后插入元素e
p = p->next;
LinkList s = (LinkList)malloc(sizeof(LNode));
s->data = e;
s->next = p->next;
p->next = s;

L->len++;
return TRUE;
}
}

//删除链表的第i个元素，并用e返回值
//i的合法范围是：0<i<ListLength(L)+1
Status ListDelete(LinkList & L,int i,ElemType & e)
{
if(i<1 || i>ListLength(L))
{
cout<<"访问越界..."<<endl;
return ERROR;
}
else
{
LinkList p = L;
int j;
for(j = 0;j < i-1;j++) //for循环后指针p将指向要删除的元素的前驱结点
p = p->next;
e = p->next->data;
LinkList q = p->next;
p->next = q ->next;
L->len--;
free(q);

return TRUE;
}
}

//获取表中第i个元素
//i的合法取值范围是：0 < i < ListLength(L)+1
ElemType GetElem(LinkList L,int i)
{
if(i<1 || i>ListLength(L))
{
cout<<"取值非法! 链表中无此位序元素"<<endl;
return ERROR;
}
else
{
LinkList p = L;
int j;
for(j = 0;j<i;j++)
p = p->next;
return p->data;
}

}

//判断链表是否为空
Status EmptyList_L(LinkList L)
{
if(L->next == NULL)
return TRUE;
return ERROR;
}

//在链表中查找定位元素e的位序，并通过函数返回
int LocateElem(LinkList L,ElemType e)
{
int i = 0;
LinkList p = L;
while(p->next && p->next->data != e)
{
p = p->next;
i++;
}
if(p->next == NULL)
{
cout<<"在链表中找不到元素 "<<e<<endl;
return ERROR;
}

return (i+1);
}

//求当前元素curr_e的直接前驱元素，用e返回其值
Status PriorElem(LinkList L,ElemType curr_e,ElemType & e)
{
LinkList p = L;
while(p->next && curr_e != p->next->data)
p = p->next;
if(p->next == NULL)
{
cout<<"在链表中找不到元素 "<<curr_e<<" ，无法求其前驱元素!"<<endl;
return ERROR;
}
if(p == L)
{
cout<<"元素 "<<curr_e<<" 是链表中的首元元素，无前驱..."<<endl;
return ERROR;
}
e = p->data;
return OK;
}

/*
//求当前元素curr_e的直接后继元素，用e返回其值
Status NextElem(LinkList L,ElemType curr_e,ElemType & e)
{
LinkList p = L->next;
//cout<<curr_e<<endl;

//cout<<p->next->data<<endl;

if(p == NULL)
{
cout<<"链表是个空表!"<<endl;
return ERROR;
}

if(p->next == NULL)
{
cout<<"链表中只有一个元素，无后继..."<<endl;
return ERROR;
}

while(p->next && curr_e != p->data)
{
//cout<<"while"<<endl;
p = p->next;
}
cout<<"p->data = "<<p->data<<endl;

if(p->data != curr_e)
{
cout<<"111"<<endl;
cout<<"在链表中找不到元素 "<<curr_e<<" ，无法求其后继元素!"<<endl;
return ERROR;
}

if(p->next == NULL && curr_e == p->data)
{
cout<<"222"<<endl;
cout<<"元素 "<<curr_e<<" 是链表中的尾元元素，无后继..."<<endl;
return ERROR;
}
cout<<"333"<<endl;
e = p->data;
return OK;
}
*/

//求当前元素curr_e的直接后继元素，用e返回其值
Status NextElem(LinkList L,ElemType curr_e,ElemType & e)
{
LinkList p = L->next;
while(p && p->data != curr_e)
p = p->next;
if(p == L->next)
{
if(p == NULL)
{
cout<<"\n链表是一个空表，无法做取后继操作!"<<endl;
return ERROR;
}
else
{
cout<<"\n链表中只有一个元素，无法求其后继..."<<endl;
return ERROR;

}
}
if(p == NULL)
{
cout<<"\n在链表中未能找到元素: "<<curr_e<<endl;
return ERROR;
}
if(p->next == NULL)
{
cout<<"\n元素 "<<curr_e<<" 是链表的尾元元素，无法求其后继..."<<endl;
return ERROR;
}
e = p->next->data;
return OK;

}

//对链表进行遍历操作
Status ListTraverse(LinkList L)
{
LinkList p = L->next;

if(LISTLEN == 0)
{
cout<<"\n链表中除头结点以外的所有内容已被释放，是一个空表!"<<endl;
cout<<"\n遍历失败..."<<endl;
return ERROR;
}
if(LISTLEN == -1)
{
cout<<"\n所有内容已被释放，链表已被销毁!"<<endl;
cout<<"\n遍历失败..."<<endl;
return ERROR;
}
while(p != NULL)
{
cout<<p->data<<" ";
p = p->next;
}
cout<<"\n遍历成功!"<<endl;
return OK;
}

//清空链表的内容
//单链表的清空是指释放除头结点以外的内存空间
Status ClearList_L(LinkList & L)
{
LinkList p = L;
while(p->next)
{
LinkList m = p->next;
free(p);
p = m;
}
L->next = NULL;
LISTLEN = 0;
return OK;
}

//销毁链表
//单链表的释放是指释放链表的所有结点内存空间
void DestoryList_L(LinkList & L)
{
LinkList p = L;
while(p->next)
{
LinkList m = p->next;
free(p);
p = m;
}

//free (p);
//free (L);
LISTLEN = -1;
}

=========================main.cpp=======================
#include "linklist.h"

int main()
{
LinkList L;
ElemType e;
ElemType curr_e;
int n;
int status; //返回函数执行状态

cout<<"请输入所需创建的元素个数:";
cin>>n;
cout<<endl;

//创建单链表
CreateList_L(L,n);
cout<<endl;

//遍历
status = ListTraverse(L);

//返回链表表长
cout<<"\n单链表的长度是: "<<ListLength(L)<<endl;

//链表的插入操作
cout<<"\n请输入需要插入元素的位置: ";
cin>>n;
cout<<"\n请输入插入的元素值: ";
cin>>e;
status = ListInsert(L,n,e);
if(status)
cout<<"\n链表元素插入成功!"<<endl;
else
cout<<"\n链表元素插入失败!"<<endl;

status = ListTraverse(L);
cout<<endl;

//单链表的删除操作
cout<<"请输入需要删除的元素的位置: ";
cin>>n;
status = ListDelete(L,n,e);
if(status)
{
cout<<"\n删除成功!";
cout<<" 删除的元素是: "<<e<<endl;
}
else
cout<<"\n删除失败..."<<endl;

status = ListTraverse(L);
cout<<endl;

//获取单链表的元素
cout<<"请输入你想获取的元素在链表中的位置: ";
cin>>n;
e = GetElem(L,n);
if(n > 0 && n <= L->len)
cout<<"\n单链表第"<< n <<"个元素值是: "<<e<<endl;

//单链表判空操作
status = EmptyList_L(L);
if(status)
cout<<"\n单链表为空表!"<<endl;
else
cout<<"\n单链表非空，其中含有元素."<<endl;

//查找定位元素
cout<<"\n请输入所需查找的元素: ";
cin>>e;
n = LocateElem(L,e);
if(n)
cout<<"\n元素 "<<e<<" 在链表中的位置是: "<<n<<endl;

//前驱操作
cout<<"\n需要求其前驱的元素值: ";
cin>>curr_e;
status = PriorElem(L,curr_e,e);
if(status)
cout<<"\n元素 "<<curr_e<<" 的前驱是: "<<e<<endl;

//后继操作
cout<<"\n需要求其后继的元素值: ";
cin>>curr_e;
status = NextElem(L,curr_e,e);
if(status)
cout<<"\n元素 "<<curr_e<<" 的后继是: "<<e<<endl;

//单链表的清空操作
cout<<"\n调用清空链表函数";
status = ClearList_L(L);

cout<<endl;

status = ListTraverse(L);

//单链表的销毁操作
cout<<"\n调用链表销毁函数";
DestoryList_L(L);

cout<<endl;

status = ListTraverse(L);

cout<<endl;

return 0;
}

Answer 2

我空间里有一些，你说的好像都有