Статический связанный список — использование последовательного хранения для достижения функции связанного хранения

глубокое обучение

Статический связанный список

\

структура

struct node{
		T data;
		int link;
	};


Один элемент содержит данные, а другой элемент (ссылка) содержит расположение следующих данных.

Хранится в массиве для формирования статического связанного списка: node SL[MAXSIZE]

\

Контекст данных определяется не порядком массива, а ссылкой. Или:

Вывод связанного списка выводится не в порядке массива, а с указанной позиции (ссылки).

\

Стоит отметить, что существует два связанных списка:

Список данных: в этом списке хранятся полезные данные, головной узел SL [0];

Резервный связанный список: при вставке новых данных выделяется пространство этого связанного списка, и выделенное пространство преобразуется в часть связанного списка данных; головной узел находится в SL [MAXSIZE-1].

\

Как показано ниже:

\

\

\

\

\

\

\

\

\

\

\

\

\

\

Две программные реализации:

\

1 Создайте файл SList.h:

\

#ifndef SLIST_H
#define SLIST_H
const int MAXSIZE=10;
template <typename T>
class SList{
	struct node{
		T data;
		int link;
	};
private:
	node SL[MAXSIZE];
	int New(){
		int i=SL[MAXSIZE-1].link;
		if(i)
			SL[MAXSIZE-1].link=SL[i].link;
		return i;
	}
	void Delete(int k){
		SL[k].link=SL[MAXSIZE-1].link;
		SL[MAXSIZE-1].link=k;
	}
public:
	SList(){
		int i;
		SL[0].link=0;
		SL[MAXSIZE-1].link=1;
		for(i=1;i<MAXSIZE-2;i++)
			SL[i].link=i+1;
		SL[MAXSIZE-2].link=0;
		
	}
	void ClearList(){
		int j,i=SL[MAXSIZE-1].link;
		while(i){
			j=i;
			i=SL[i].link;
		}
		SL[j].link=SL[0].link;
		SL[0].link=0;
	}
	bool ListEmpty(){
		return SL[0].link==0;
	}
	int ListLen()const{
		int count=0,i=SL[0].link;
		while(i){
			i=SL[i].link;
			count++;
		}
		return count;
	}
	
	
	bool PriorElem(T e, bool(*eq)(T, T), T &pre_e)const
	{

		int j, i=SL[0].link;
		do
		{
			j=i;
			i=SL[i].link;
		}while(i && !eq(SL[i].data, e));
		if(i)
		{
			pre_e=SL[j].data;
			return true;
		}
		return false;
	}
	bool NextElem(T e, bool(*eq)(T, T), T &next_e)const
	{

		int i=SL[0].link;
		while(i)
		{
			if(eq(SL[i].data, e) && SL[i].link)
			{
				next_e=SL[SL[i].link].data;
				return true;
			}
			i=SL[i].link;
		}
		return false;
	}

	bool InsertElem(int i,T e){
		int m,k=0;
		for(m=1;m<i;m++){
			k=SL[k].link;
			if(k==0)
				break;

		}
		if(m<i) return false;
		else{
			m=New();
			if(m){
				SL[m].data=e;
				SL[m].link=SL[k].link;
				SL[k].link=m;
				return true;
			}
			return false;
		}
	}
	bool DeleteElem(int i,T &e){
		int m,k=0;
		for(m=1;m<i;m++){
			k=SL[k].link;
			if(k==0) break;
		}
		if(m<i||SL[k].link==0) return false;
		else{
			m=SL[k].link;
			SL[k].link=SL[m].link;
			e=SL[m].data;
			Delete(m);
			return true;
		}
	}
	void ListPrint(void(*visit)(T*)){
		int i=SL[0].link;
		while(i){
			visit(&SL[i].data);
			i=SL[i].link;
		}
		cout<<endl;
	}
};
#endif


\

2 Протестируйте класс SList:

\

#include <iostream>
#include<string>
using namespace std;
typedef string T;
bool equal(string c1, string c2)
{
	return c1==c2;
}
void print(T* c)
{
	cout<<*c<<" ";
}
#include "SList.h"
int main()
{
	SList<T> L;
	T e, e0="kobe";
	bool i;
	int j, k;
	T s;
	cout<<"请输入你心中最好的6名球星："<<endl;
	for(j=1; j<=6; j++){
		cin>>s;
		i=L.InsertElem(j, s);
	}
	cout<<endl;
	cout<<"你的榜单L=";
	L.ListPrint(print);
	cout<<"L是否空？"<<boolalpha<<L.ListEmpty()<<"，L长=";
	cout<<L.ListLen()<<endl;
	
	i=L.PriorElem(e0, equal, e);
	if(i)
		cout<<"球星"<<e0<<"的前一名为"<<e<<endl;
	
	i=L.NextElem(e0, equal, e);
	if(i)
		cout<<"球星"<<e0<<"的后一名为"<<e<<endl;
	
	k=L.ListLen();
	for(j=k+1; j>=k; j--)
	{
		i=L.DeleteElem(j, e);
		if(i)
			cout<<"删除第"<<j<<"个球星成功，他是"<<e<<endl;
		else
			cout<<"删除第"<<j<<"个球星失败（榜单不存在此球星），";
	}
	cout<<"依次输出L的球星：";
	L.ListPrint(print);
	L.ClearList();
	cout<<"清空L后，L=";
	L.ListPrint(print);
	cout<<"L是否空？"<<boolalpha<<L.ListEmpty()<<"，L长=";
	cout<<L.ListLen()<<endl;

	return 0;
}


\

\

\

Три бегущих результата:

\

\

Категории