数据结构作业——1单向链表的基本操作

数据结构，严蔚敏C语言版。书上的基本实现。

 

1.h：//预定义头文件 和 宏定义（函数结果状态代码）。

 

 

#pragma once
#include<iostream>
#include<malloc.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVER -2
#define n 10
typedef int Santus;

 

 

2.h：定义单向链表的结构体。

采用递归定义，next指向下一个结构体。

#pragma once
typedef int Elemtype;
typedef struct Lnode {
	Elemtype data;
	struct Lnode *next;
}Lnode,*Linklist;

3.h：

#pragma once
#include"1.h"
#include"2.h"
using namespace std;
void show() {
	cout << "1.取出第i个元素" << endl

		<< "2.插入节点" << endl//
		<< "3.删除节点" << endl
		<< "4.清空链表" << endl
		<< "5.读链表" << endl
		<< "6.是否为空" << endl
		<< "7.链表元素个数" << endl
		<< "8.第一个与e满足compare关系" << endl
		<< "9.销毁链表" << endl
		<< "10.返回前驱" << endl
		<< "11.返回后继" << endl;
}
//Santus list_creat2(Linklist &l) {//头插建立链表


//}
Santus list_creat(Linklist & l, Elemtype a[n]) {//尾插建立链表
	l = (Linklist)malloc(sizeof(Lnode));
	if (!l) {
		cout << "建立失败" << endl;
		return ERROR;
	}
	l->next = NULL;
	Linklist l1 = l;
	for (int j = 0; j < n; j++) {
		Linklist p= (Linklist)malloc(sizeof(Lnode));
		if (!p) {
			cout << "建立失败" << endl;
			return ERROR;
		}
		p->data = a[j];
		p->next = nullptr;
		l1->next = p;
		l1 = l1->next;

	}
	return OK;
}
void LinkedListCreateTailL(Linklist& L, Elemtype a[n])

{

	L = (Lnode *)malloc(sizeof(Lnode));

	if (L == NULL)

	{

		printf("申请空间失败！");

		exit(0);

	}

	L->next = NULL;

	Linklist tail = L;         //设置尾指针，方便插入



	for (int j = 0; j<n; j++)

	{

		Linklist p = (Lnode *)malloc(sizeof(Lnode));

		if (p == NULL)

		{

			printf("申请空间失败！");

			exit(0);

		}



		p->data = a[j];

		p->next = NULL;

		tail->next = p;

		tail = p;

	}

}
Santus Getelem(Linklist l, int i, Elemtype&e) {//取出元素
	Linklist p = l->next;
	int j = 1;
	while (p  && j < i) {
		p = p->next;
		++j;

	}
	if (!p||j>i)
		return ERROR;
	e = p->data;
	return OK;
	
}
Santus list_insert(Linklist & l,int i,Elemtype e) {//插入元素
	Linklist p=l ;
	int j = 0;
	while (p&&j < i - 1) {
		p = p->next;
		++j;
	}
	if (!p || j > i - 1)
		return ERROR;
	Linklist q = (Linklist)malloc(sizeof(Lnode));
	if (!q)
		return ERROR;
	q->data = e;
	q->next = p->next;
	p->next = q;
	return OK;

}
void read(Linklist l) {//read list
	if (l->next == NULL)
		cout << "没有数据" << endl;
	else {
		Linklist p = l->next;
		while (p != NULL) {
			cout << p->data << "   ";
			p = p->next;
		}
	}
}
Santus list_delet(Linklist &l, int i, Elemtype &e) {//删除节点
	Linklist p = l;
	int j = 0;
	while (p->next&&j < i - 1) {
		p = p->next;
		++j;
	}
	if (!p->next || j > i - 1)
		return ERROR;
	Linklist q = p->next;
	e = q->data;
	p->next = q->next;
	return OK;
	
}
Santus  clear_list(Linklist&l) {//清空链表
	Linklist p = l->next,q=p;
	while (p) {
		p = p->next;
		free(q);
		q = p;
	}
	free(q);
	l->next = NULL;
	return OK;
}
Santus destory_list(Linklist& l) {//销毁链表，销毁头结点
	Linklist p = l;
	while (p) {
		l = l->next;
		free(p);
		p = l;
		
	}
	return OK;
}
Santus list_empty(Linklist l) {//是否为空链表
	if (l->next == NULL)
		return TRUE;
	else
		return FALSE;
}
int list_length(Linklist l) {//链表元素个数
	Linklist p = l;
	int j = 0;
	while (p->next) {
		p = p->next;
		j++;
	}
	return j;
}
Santus compare(Elemtype e1, Elemtype e2 ) {
	if (e1 == e2)
		return OK;
	else
		return FALSE;

}

int locate_elem(Linklist l, Elemtype e) {//返回第一个与e满足compare的元素位序
	Linklist p = l->next;
	int j = 1;
	while (p && !((*compare)(p->data, e))) {
		p = p->next;

			j++;
	}
	if (!p)
		return 0;
	return j;

}
Santus prior_elem(Linklist l, Elemtype cur_e, Elemtype &pre_e) {//返回前驱节点
	Linklist p = l->next;
	int j = 1;
	while (p&&j < locate_elem(l, cur_e) - 1) {
		p = p->next;
		j++;
	}
	if (!p||j>locate_elem(l, cur_e) - 1)
		return ERROR;
	pre_e = p->data;
	return OK;
}
Santus next_elem(Linklist l, Elemtype cur_e, Elemtype &next_e) {//返回节点后继
	Linklist p = l->next;
	int j =1;
	while (p->next&&j < locate_elem(l, cur_e)) {
		p = p->next;
		j++;
	}
	if (!p->next || j > locate_elem(l, cur_e))
		return ERROR;
	next_e = p->next->data;
	return OK;
}

text.cpp:

#include"1.h"
#include"2.h"
#include"3.h"
using namespace std;



int main() {
	Linklist l;
	Elemtype a[n] = { 1,2,3,4,5,6,7,8,9,10 },e,e2;
	list_creat(l, a);
	//LinkedListCreateTailL(l, a);
	int i;
	
	 show();
	do {
		

		int select;
		cout << "input caozuo" << endl;
		cin >> select;
		switch (select)
		{
		case 1:
			cout << "取出第几个" << endl;
			cin >> i;
			Getelem(l, i, e);
			if (Getelem(l, i, e) == ERROR)
				cout << "读取失败" << endl;
			else {
				cout << e << endl;
				read(l);
				cout << endl;
			}
			
			break;
		case 2:
			cout<<"input set" << endl;
			cin >> i;
			cout << "input num" << endl;
			cin >> e;
			
			if (list_insert(l, i, e) == ERROR)
				cout << "插入失败" << endl;
			else {
				read(l);
				cout << endl;
			}
			break;
		case 3:
			cout << "input set" << endl;
			cin >> i;
			if (list_delet(l, i, e) == ERROR) {
				cout << "失败" << endl;
				
			}
			else {
				read(l);//读链表
				cout << endl;
				cout << e << endl;
			}
			break;
		case 4://清空链表
			if (clear_list(l))
				cout<<"清空成功"<<endl;

				
			break;
		case 5:
			read(l);
			cout << endl;
			break;
		case 6:
			if (list_empty(l))
				cout << "空链表" << endl;
			else
				cout << "非空链表" << endl;
			
			break;
		case 7:
			cout << "元素个数为：" << list_length(l) << endl;
			break;
		case 8:
			cout << "input e:";
			cin >> e;
			if (locate_elem(l, e) != 0)
				cout << "存在于" << locate_elem(l, e) <<"位置"<< endl;
			else
				cout << "不存在" << endl;
			break;
		case 9:
			if (destory_list(l))
				cout << "销毁成功" << endl;
			break;
		case 10:
			cout << "input number" << endl;
			cin >> e;
			if (prior_elem(l, e, e2) != ERROR)
				cout << e2 << endl;
			else
				cout << "错误" << endl;
			break;
		case 11:
			cout << "input number" << endl;
			cin >> e;
			if (next_elem(l, e, e2) != ERROR)
				cout << e2 << endl;
			else
				cout << "错误" << endl;
			break;
		default:
			cout << "input right select" << endl;
			break;
		}


	} while (1);



	
	

	system("pause");
	return 0;
}