我们建立一个头文件用于建立结构体与函数等。

首先写上预备代码。。。

#include<iostream>
#include<string.h>
using namespace std;

然后建立链表

struct Node  //用结构体建立单链表的节点
{
	char data;
	Node* next;
};

接下来是几个基础操作的函数。

void initList(Node*& l)//初始化一个空表
{
	l = (Node*)malloc(sizeof(Node));
	l->next = NULL;
}

下面的头插法建立的单链表元素顺序是反的，在使用中，数组ass应反向输入即可得到正向结果。

void createListh(Node*& l, char ass[]) //用ass中的数据给单链表赋值,头插法
{
	l = (Node*)malloc(sizeof(Node));
	l->next = NULL;
	int i, n;
	n = strlen(ass) / sizeof(ass[]);
	Node* s;
	for (i = ;i < n;i++)
	{
		s = (Node*)malloc(sizeof(Node));
		s->data = ass[i];
		s->next = l->next;
		l->next = s;
	}
}

void createListt(Node*& l, char ass[]) //用ass中的数据给单链表赋值,尾插法
{
	l = (Node*)malloc(sizeof(Node));
	int i, n;
	n = strlen(ass) / sizeof(ass[]);
	Node* s, * r = l;
	for (i = ;i < n;i++)
	{
		s = (Node*)malloc(sizeof(Node));
		s->data = ass[i];
		r->next = s;
		r = s;
	}
	r->next = NULL;
}

void destroyList(Node*& l) //销毁单链表
{
	Node* pre, * p;
	pre = l;
	p = l->next;
	while (p != NULL)
	{
		free(pre);
		pre = p;
		p = pre->next;
	}
	free(pre);
}

bool emptyList(Node*& l)  //确定单链表是否为空
{
	return (l->next == NULL);
}

int lengthList(Node*& l)  //求单链表的长度
{
	Node* p = l;
	int i = ;
	while (p->next != NULL)
	{
		p = p->next;
		i++;
	}
	return i;
}

void coutList(Node*& l)  //依次输出单链表所有元素
{
	Node* p = l;
	int i = ;
	while (p->next != NULL)
	{
		p = p->next;
		cout << p->data;
	}
}

void getiList(char& e, int i, Node*& l)//获取第i个元素
{
	Node* p = l;
	int j = ;
	while (j < i && p->next != NULL)
	{
		p = p->next;
		j++;
	}
	if (i != j)
		cout << "超出顺序表范围";
	else
		e = p->data;
}

int findeList(char e, Node*& l)//找到第一个元素e所在的位置
{
	int i = 1;
	Node* p = l;
	while (p->next!=NULL&&p->next->data!=e)
	{
		i++;
		p = p->next;
	}
	if (p->next == NULL)
	{
		cout << "未找到元素";
		return ;
	}
	else
		return i;
}

void insertList(char e, int i, Node*& l)  //将e插入第i个位置
{
	Node* p = l, * s;
	s = (Node*)malloc(sizeof(Node));
	int j = 1;
	while (j<i&&p->next!=NULL)
	{
		j++;
		p = p->next;
	}
	if (i == j)
	{
		s->data = e;
		s->next = p->next;
		p->next = s;
	}
	else
		cout << "指定的位置不存在";
}

void deleteList(int i, Node*& l)//删除第i个元素
{
	Node* p = l, * s = l->next;
	int j = 1;
	while (j < i && s != NULL)
	{
		p = s;
		s = s->next;
		j++;
	}
	if (i!=j)
		cout << "超出范围";
	else
	{
		p->next = s->next;
		free(s);
	}
}

下面是测试程序。

#include<iostream>
#include<math.h>
#include<string.h>
#include"danlianbiao.h"
using namespace std;
int main()
{
	char x = '5', a[27] = "abcdefghijklmnopqrstuvwxyz";
	Node* list, * list2;
	initList(list);
	createListt(list, a);
	cout << list->next->data << endl;
	initList(list2);
	createListh(list2, a);
	cout << list2->next->data << endl;
	destroyList(list2);
	cout << emptyList(list) << endl;
	cout << lengthList(list) << endl;
	coutList(list);
	int n = 3;
	getiList(x, n, list);
	cout << endl << x << endl;
	cout << findeList('5', list) << endl;
	insertList('a', 3, list);
	coutList(list);
	deleteList(3, list);
	cout << endl;
	coutList(list);
	destroyList(list);
}

ITPub博客

数据结构与算法实现代码（2）——单链表

最新文章