c/c++单链表的创建及操作
程序员文章站
2022-06-06 13:46:18
...
大一下期第二次数据结构单链表实验代码
case 2及case 5处仍存在问题待解决
/*1、创建一个带头结点的单链表(头指针为head),且遍历此链表(输出链表中各结点的值);
2、查找单链表中的第i个结点,并输出结点元素的值;
3、在单链表中的第i个结点前插入一个结点值为e的正整数(从外部输入);
4、删除单链表中的第j个结点;
*5、将单链表中的各结点就地逆序(不允许另建一个链表);
*/
#define OK 1
#define ERROR -1
#include<stdio.h>
#include<stdlib.h>
#include <iostream>
using namespace std;
typedef struct LNode //单链表存储结构
{
int data; //结点数据域
struct LNode *next;//结点的指针域
}LNode,*LinkList;
LNode head;
int ListInit(LinkList &head)//构造一个空的单链表L
{
head=new LNode;//生成新结点作为头结点,头指针head指向头结点
head->next=NULL;//头结点指针域置空
return OK;
}
int ListCreat_R(LinkList &head,int n)//后插法创建单链表
{
LinkList r,p;
r=head;
cout<<"请输入链表的元素:"<<endl;
for(int i=0;i<n;i++)
{
p=new LNode;//生成新结点
cin>>p->data;//输入元素赋值给新结点*p的数据域
p->next=NULL;
r->next=p;//将新结点插入尾结点*r
r=p;//r指向新的尾结点*p
}
return OK;
}
int ListTraverse(LinkList &head)//遍历链表
{
LinkList p=head->next;//初始化,p指向首元结点
int i=0;//计数器赋值为0
while(p)
{
cout<<p->data<<" ";
p=p->next;
i++;
}
if(i==0)
{
cout<<"链表为空!"<<endl;
return ERROR;
}
return OK;
}
int GetElem(LinkList &head,int i,int &e)//按位置查找链表元素的值
{
LinkList p=head->next;//初始化,p指向首元结点
int j=1;//计数器j赋初值为1
while(p&&j<1)//顺链域向后扫描直到p为空或p指向第i个元素
{
p=p->next;//p指向下一个结点
++j;//计数器加一
}
if(!p||j>i)//i值不合法
return ERROR;
e=p->data;//取第i个结点的数据域
return OK;
}
int ListInsert(LinkList &head,int i,int e)//在链表第i个位置插入值为e的新结点
{
LinkList p=head,s;
int j=0;
while(p&&(j<i-1))//查找第i-1个结点,令p指向该结点
{
p=p->next;
++j;
}
if(!p||j>i-1)//i值不合法返回ERROR
return ERROR;
s=new LNode;//生成新结点*s
s->data=e;//*s的数据域为e
s->next=p->next;//*s指针域指向结点a
p->next=s;//*p指针域指向*s
return OK;
}
int ListDelete(LinkList &head,int i)//在链表中删除第i个元素
{
LinkList p=head,q;
int j=0;
while((p->next)&&(j<i-1))//查找第i-1个结点,并令p指向该结点
{
p=p->next;
++j;
}
if(!(p->next)||(j>i-1))//i值不合法
return ERROR;
q=p->next;//临时保存被删结点的地址以备释放
p->next=q->next;//改变删除结点前驱结点的指针域
free(q);//释放删除结点的空间
return OK;
}
int ListReverse(LinkList &head)//将链表原地逆序
{
if(head==NULL||head->next==NULL)
return ERROR;
else
{
LinkList p=head->next,q;
head->next=NULL;
while(p)
{
q=p->next;
p->next=head;
head=p;
p=q;
}
}
return OK;
}
int main()
{
int c,i,e,n;
LinkList L;
ListInit(L);
cout<<"请输入链表元素的个数:"<<endl;
cin>>n;
ListCreat_R(L,n);
cout<<"创建链表成功!"<<endl;
cout<<"1.遍历单链表"<<endl;
cout<<"2.按位置查找链表中的一个元素"<<endl;
cout<<"3.在链表中插入一个元素"<<endl;
cout<<"4.在链表中删除一个元素"<<endl;
cout<<"5.就地逆序链表"<<endl;
cout<<"请选择要完成的操作并输入对应序号:"<<endl;
cin>>c;
switch(c)
{
case 1:
ListTraverse(L);
break;
case 2:
cout<<"请输入要查找的元素位置:"<<endl;
cin>>i;
GetElem(L,i,e);
cout<<e<<endl;
break;
case 3:
cout<<"请输入要插入数值的位置:"<<endl;
cin>>i;
cout<<"请输入要插入的数值:"<<endl;
cin>>e;
ListInsert(L,i,e);
cout<<"新链表为:"<<endl;
ListTraverse(L);
break;
case 4:
cout<<"请输入要删除元素的位置:"<<endl;
cin>>i;
ListDelete(L,i);
cout<<"新链表为:"<<endl;
ListTraverse(L);
break;
case 5:
ListReverse(L);
cout<<"新链表为:"<<endl;
ListTraverse(L);
break;
default: break;
}
return 0;
}