数据结构编程实验----链表的基本操作实现

链表的基本操作的实现，个人感觉链表的实现比顺序表的实现复杂了一点，特别是在操作的实现的过程中对边界的判断有点困难，画图吧，画图就可以很清楚地看出各个节点之间的关系和边界了。
1.链表的定义

#include <iostream>
#include<string>
#include<math.h>
using namespace std;
typedef int elemtype;
struct node {
	elemtype elem;
	node * next;
};
typedef node* linklist;

2.初始化链表

void initlinklist(linklist &l)
{
	l = new node;//建立头节点
	l->next = NULL;
}

3.创建链表，使链表含有元素

void createlink(linklist &l)//尾插法建表
{
	node *r, *s;
	int flag = 1,date = 0;
	r = l;//让r去指向l
	while (cin>>date&&date!='$')
	{
		s = new node;
		s->elem = date;
		s->next = r->next;//让r的next指向s的next，r的next为null,这样创建结束以后尾指针指向null，表示末尾
		r->next = s;
		r = s;
	}
	cout << "创建结束！！！" << endl;
}

4.打印输出链表内部的元素

void print(linklist l)
{
	node *s;
	s = l->next;
	while (s != NULL)
	{
		cout << s->elem << " ";
		s = s->next;
	}
	cout << endl;
}

5.求链表的长度

void linklength(linklist l)
{
	node *s;
	int len = 0;
	s = l->next;
	while (s != NULL)
	{
		len++;
		s = s->next;
	}
	cout<<"链表的长度为："<<len << endl;
}

6.查找第i个位置，并返回该位置的值

bool located1(linklist l, int i)//查找第i个位置，并返回该位置的值
{
	int j = 0;
	node *p = l;
	if (i < 0)
	{
		cout << "查找位置有问题！！！" << endl;
		return false;
	}
	while (p->next&&j < i)
	{
		j++;
		p = p->next;
	}
	if (i == j)
	{
		cout << "已找到该节点！! ！值为：" << p->elem << endl;
		return 1;
	}
	else 
		return false;//当i大于表长时
}

7.查找链表中值为key的节点，并返回位置

bool located2(linklist l, elemtype key)//查找链表中值为key的节点，并返回位置
{
	node *s = l->next;
	int j = 0,flag=0;
	while (s)
	{
		j++;
		if (s->elem == key)
		{
			cout << "已经找到值为" << key << "的节点，在第" << j << "个位置！！！" << endl;
			//break;   加入break语句的情况下找到就退出，不加入可以全部查找，根据需求选择加不加break；
			flag = 1;
		}
		s=s->next;
	}
	if (flag)
		return true;
	else
	{
		cout << "未在链表中找到值为" << key << "的节点！！！" << endl;
		return false;
	}
	
}

8.插入操作

bool insertlink(linklist &l, int i, elemtype e)
{
	node *s, *r;
	int j = 0;
	r = l;
	if(i<0)
	{
		cout << "插入位置有错误！！！" << endl;
		return false;
	}
	while (r&&j < i-1)
	{
		r = r->next;
		j++;
	}
	if (!r)
	{
		cout << "插入位置有错误！！！" << endl;
		return false;
	}
	s = new node;
	s->elem = e;
	s->next = r->next;
	r->next = s;
	return true;
}

9.删除操作

bool deletelink(linklist &l, int i, elemtype *e)//删除第i个节点的值，并将值用e带会
{
	node *q,*r; int j = 0;
	q = l;
	if (i < 0)
	{
		cout << "删除的位置有误！！！" << endl;
		return false;
	}
	while (q->next&&j < i - 1)
	{
		q = q->next;
		j++;
	}
	if (!(q->next))
	{
		cout << "删除的位置有误！！！" << endl;
		return false;
	}
	r = q->next;
	 q->next=r->next;
	 *e = r->elem;
	delete r;
	return true;
}

10.主函数

int main()
{
    std::cout << "Hello World!\n"; 
	linklist l;
	initlinklist(l);
	createlink(l);
	print(l);
	linklength(l);
	located1(l, 3);//查找链表中第三个位置的元素
	located2(l, 3);//查找链表中值为3的元素
	insertlink(l, 5, 100);//在第五个位置插入值为100的元素
	print(l);
	elemtype *a;
	a = new int;
	if(deletelink(l, 5, a))
	{ 
		cout << "成功删除节点！！！" << endl;
	}
	print(l);
	return 0;
}

运行结果
数据结构编程实验----链表的基本操作实现
在创建链表的过程中，输入的元素个数不固定，当输入结束的时候可以输入‘￥’，或者可以使用回车+Ctrl+z+回车的方式去停止输入。

数据结构编程实验----链表的基本操作实现

相关推荐