数据结构-线性表

原创
2017/07/28 15:52
阅读数 42

 

注:1.单链表头结点没有数据data,且逻辑序号为i = 0,p = L;

       2.限制条件,判断某元素是否在单链表中,类似顺序表中i < n,单链表p!=NULL

       3.插入数据元素时,j必须从0开始。

       

#include<iostream>
#include<stdlib.h>
using namespace std;
typedef struct LNode
{
	char data;
	struct LNode * next;
}LinkList;
//尾插法建单链表
void CreateList(LinkList *&L,char a[],int n)
{
	int i;
	LinkList * r,*s;
	//头结点为空
	L = (LinkList *)malloc(sizeof(LinkList));
	r = L;
	for(i = 0;i < n;i++)
	{
		s = (LinkList *)malloc(sizeof(LinkList));
		s->data = a[i];
		r->next = s;
		r = s;
	}
	r->next = NULL;
}
//判断单链表是否为空
bool ListEmpty(LinkList *&L)
{
	return (L->next == NULL);
}
//单链表的节点个数
int ListLength(LinkList *&L)
{
	int n = 0;
	LinkList * p = L;
	while(p->next != NULL)
	{
		n++;
		p = p->next;
	}
	return n;
}
//输出单链表的各节点的值
void DispList(LinkList *&L)
{
	LinkList * p = L->next;
	while(p != NULL)
	{
		cout<<p->data<<" ";
		p = p->next;
	}
    cout<<endl;
}
//查找第3个节点,并将其输出出来
void GetElem(LinkList *&L,int i)
{
	int j = 0;
	LinkList * p = L;
	if(i <= 0)
		cout<<"i值不正确";
	else
	{
		while(j < i && p != NULL)
		{
			j++;
			p = p->next;
		}
		if(p == NULL)
		   cout<<"p为空";
		else
		    cout<<"第i个节点值为"<<p->data<<endl;
	}
}
//查找与e相等的第一个节点,若存在,返回逻辑序号,否则返回0
void LocateElem(LinkList *&L, int e)
{
	int i = 1;
	LinkList * p = L->next;
	while(p != NULL && p->data != e)
	{
		p = p->next;
		i++;
	}
	if(p != NULL)
		cout<<"与e相等的节点的逻辑序号为"<<i<<endl;
	else
		cout<<"查找错误"<<endl;

}
//插入数据元素
void InsertList(LinkList *&L,int i,char e)
{
	int j = 0;
	LinkList * p = L,*s;
	while(j < i - 1 && p != NULL)
	{
		j++;
		p = p->next;
	}
	if(p != NULL)
	{
		s = (LinkList *)malloc(sizeof(LinkList));
		s->data = e;
		s->next = p->next;
		p->next = s;
	}
}
//删除数据元素,删除第i个元素
void ListDelete(LinkList *&L,int i)
{
	int j = 0;
	LinkList * p = L;
	while(j < i - 1 && p != NULL)
	{
		j++;
		p = p->next;
	}
	if(p != NULL)
	{
		p->next = p->next->next;
	}
}
int main()
{
	LinkList * L;
	char a[101];
	int n,i;
	cin>>n;
	for(i = 0;i < n;i++)
		cin>>a[i];
	CreateList(L,a,n);
	//判断单链表是否为空
    cout<<"是否为空:"<<ListEmpty(L)<<endl;
	//返回单链表的节点个数-长度
    int length = ListLength(L);
	cout<<"节点个数:"<<length<<endl;
	//输出单链表的各节点的值
	cout<<"单链表各节点的值:";
	DispList(L);
    //查找第3个节点,并将其输出出来
	int g;
	cout<<"输入第几个节点i:";
	cin>>g;
    GetElem(L,g);
	//查找与e相等的第一个节点,若存在,返回逻辑序号,否则返回0
	char e;
	cout<<"输入e的值:";
	cin>>e;
    LocateElem(L,e);
	//插入数据元素
    int k;char ke;
	cout<<"输入插入位置i的值及插入数据e的值:";
	cin>>k>>ke;
    InsertList(L,k,ke);
    DispList(L);
	//删除数据元素,删除第i个元素
	int di;
	cout<<"输入删除的第i个元素的i:";
	cin>>di;
	ListDelete(L,di);
    DispList(L);
	return 0;
}

 

展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部