【数据结构】链表定义及其常用的基本操作（C/C++）

84 阅读 0 评论 56 点赞

我是靠谱客的博主健壮画笔，最近开发中收集的这篇文章主要介绍【数据结构】链表定义及其常用的基本操作（C/C++），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

●图示

●链表类型定义

●常用的基本操作（单链表）

●简单案例

●图示

●链表类型定义

1.单链表存储结构的定义

typedef struct lnode{
	elemtype data;
	struct lnode *next;
}lnode,*linklist;

定义链表L：linklist &L；

定义结点指针：lnode *p;

实例如下：

①数据和链表结构的第一种定义方法

typedef struct student{
	char num[8];
	char name[8];
	int score;
	struct student *next;
}lnode,*linklist;

②将数据和链表结构第二种定义方法

typedef struct{
	char num[8];
	char name[8];
	int score;
}elemtype;
typedef struct lnode{
	elemtype date;
	struct lnode *next;
}lnode,*linklist;

2. 带尾指针循环链表的合并（将单链表的头尾用指针进行相连）

linklist connect(linklist ta,linklist tb)
{
    p=ta->next;
	ta->next=tb->next->next;
	delete tb->next;
	tb->next=p;
	return tb;	
}

3.双向链表结构的定义

typedef struct lnode{
    elemtype data;
	struct lnode *prior,*next;	
}lnode,*linklist;

●常用的基本操作（单链表）

1.链表的初始化

void initlist(linklist &L)
{
	L = new lnode;
	L->next = NULL;
}

2. 判断链表是否为空

int listempty(linklist& L)
{
	if (L->next)
		return 0;
	else
		return 1;
}

3. 单链表的销毁

int destorylist(linklist& L)
{
	lnode* p;
	while (L != NULL)
	{
		p = L;
		L = L->next;
		delete p;
	}
	return 1;
}

4. 单链表的清空

int clearlist(linklist& L)
{
	lnode* p;  //结点指针
	lnode* q;
	p = L->next;
	while (p)
	{
		q = p->next;
		delete p;
		p = q;
	}
	L->next = NULL;
	return 1;
}

5. 求链表表长

int listlength(linklist& L)
{
	lnode* p;
	p = L->next;
	int i = 0;
	while (p)
	{
		i++;
		p = p->next;
	}
	return 1;
}

6. 取单链表中第i个元素的内容

int getelem(linklist& L, int i, elemtype e)
{
	lnode* p;
	p = L->next;
	int j = 1;
	while (p && j < i)
	{
		p = p->next;
		j++;
	}
	if (!p || j > i)
	{
		return 0;
	}
	e = p->data;
	return 1;
}

7. 在第i个结点前插入值为e的新结点

int listinsert(linklist& L, int i, elemtype e)
{
	lnode* p;
	p = L;
	int j = 0;
	while (p && j < i - 1)
	{
		p = p->next;
		j++;
	}
	if (!p || j > i - 1)
	{
		return 0;
	}
	linklist s;
	s = new lnode;
	s->data = e;
	s -> next = p -> next;
	p -> next = s;
	return 1;
}

8. 删除第i个结点

int listdelete(linklist& L, int i, elemtype e)
{
	lnode* p;
	lnode* q;
	p = L;
	int j = 0;
	while (p->next&&j<i-1)
	{
		p = p->next;
		j++;
	}
	if (!(p->next) || j > i - 1)
	{
		return 0;
	}
	q = p->next;
	p->next = q->next;
	e = q->data;
	delete q;
	return 1;
}

9. 头插法

void createlist_H(linklist &L,int n)
{
	linklist p;
	for(i=n;i>0;i--)
	{
	p=new lnode;
	cin>>p->date; //输入数据
	p->next=L->next;
	L->next=p;	
	} 
}

10.尾插法

void create_R(linklist &L,int n)
{
	linklist p;
    linklist r;
	r=L;
	while(i=0;i<n;i++)
	{
	p=new lnode;	
	cin>>p->date;  //输入数据
	p->next=NULL; 
	r->next=p;
	r=p;	
	}	
}

●简单案例

（这里只实现用顺序表存储3个学生的学号、姓名、年龄并且将其输出查看。若进行其他操作，对代码进行简单修改即可）

#include<iostream>
using namespace std;
//数据的准备
typedef struct {
	char key[10];
	char name[20];
	int age;
}elemtype;
typedef struct lnode {
	elemtype data;
	struct lnode* next;
}lnode,*linklist;
//链表的初始化
void initlist(linklist &L)
{
	L = new lnode;
	L->next = NULL;
}
//判断链表是否为空
int listempty(linklist& L)
{
	if (L->next)
		return 0;
	else
		return 1;
}
//单链表的销毁
int destorylist(linklist& L)
{
	lnode* p;
	while (L != NULL)
	{
		p = L;
		L = L->next;
		delete p;
	}
	return 1;
}
//单链表的清空
int clearlist(linklist& L)
{
	lnode* p;  //结点指针
	lnode* q;
	p = L->next;
	while (p)
	{
		q = p->next;
		delete p;
		p = q;
	}
	L->next = NULL;
	return 1;
}
//求链表表长
int listlength(linklist& L)
{
	lnode* p;
	p = L->next;
	int i = 0;
	while (p)
	{
		i++;
		p = p->next;
	}
	return 1;
}
//取单链表中第i个元素的内容 
int getelem(linklist& L, int i, elemtype e)
{
	lnode* p;
	p = L->next;
	int j = 1;
	while (p && j < i)
	{
		p = p->next;
		j++;
	}
	if (!p || j > i)
	{
		return 0;
	}
	e = p->data;
	return 1;
}
//在第i个结点前插入值为e的新结点	
int listinsert_L(linklist& L, int i, elemtype e)
{
	lnode* p;
	p = L;
	int j = 0;
	while (p && j < i - 1)
	{
		p = p->next;
		j++;
	}
	if (!p || j > i - 1)
	{
		return 0;
	}
	linklist s;
	s = new lnode;
	s->data = e;
	s -> next = p -> next;
	p -> next = s;
	return 1;
}
//删除第i个结点
int listdelete(linklist& L, int i, elemtype e)
{
	lnode* p;
	lnode* q;
	p = L;
	int j = 0;
	while (p->next&&j<i-1)
	{
		p = p->next;
		j++;
	}
	if (!(p->next) || j > i - 1)
	{
		return 0;
	}
	q = p->next;
	p->next = q->next;
	e = q->data;
	delete q;
	return 1;
}
//头插法
void createlist_H(linklist& L, int n)
{
	linklist p;
	for (int i = n; i > 0; i--)
	{
		p = new lnode;
		cin >> p->data.key;
		cin >> p->data.name;
		cin >> p->data.age;
		p->next = L->next;
		L->next = p;
	}
}
//尾插法
void create_R(linklist& L, int n)
{
	linklist p;
	linklist r;
	r = L;
	for(int i = 0; i < n; i++)
	{
		p = new lnode;
		cin >> p->data.key;
		cin >> p->data.name;
		cin >> p->data.age;
		p->next = NULL;
		r->next = p;
		r = p;
	}
}
//查询所有结点
void listall(linklist& L,int n)
{
	lnode* p;
	p = L->next;
	for(int i=1;i<=n;i++)
	{ 
		cout << p->data.key << " "<<p->data.name <<" "<< p->data.age << endl;
	    p=p->next;
    }
}
void showfunc()
{
	cout << "1.单链表的初始化" << endl;
	cout << "2.判断单链表是否为空" << endl;
	cout << "3.单链表的销毁" << endl;
	cout << "4.单链表的清空" << endl;
	cout << "5.求单链表表长" << endl;
	cout << "6.取单链表中第i个元素的内容" << endl;
	cout << "7.在第i个结点前插入值为e的新结点" << endl;
	cout << "8.删除第i个结点" << endl;
	cout << "9.头插法" << endl;
	cout << "10.尾插法" << endl;
	cout << "11.查询顺序表所有结点" << endl;
}
void text()
{
	linklist ll;
	while(1)
	{ 
		showfunc();
		cout << "#要执行的操作#" << endl;
		int n;
		cin >> n;
		switch (n)
		{
		int num;
		case 1:
			initlist(ll);
			cout << "初始化成功" << endl;
			break;
		case 10:
			cout << "要输入的学生数：" << endl;
			cin >> num;
			createlist_H(ll, num);
			cout << "输入成功" << endl;
			break;
		case 11:
			listall(ll,num);
			break;
		}
		system("pause");
		system("cls");  //每执行一次操作清一次屏
	}
}
int main()
{
	text();
}