程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 數據結構：線性鏈表的順序存儲結構，數據結構線性

數據結構：線性鏈表的順序存儲結構，數據結構線性

編輯：C++入門知識

數據結構：線性鏈表的順序存儲結構，數據結構線性

首先先了解什麼是線性表的順序儲存結構，線性表的順序存儲結構就是用一段連續的存儲空間單元一次存儲線性表的數據元素。

這裡我們可以用C/C++語言來表示順序存儲結構。

於是我們來定義一個順序存儲的代碼如下：

typedef int ElemType;   /*存儲類型，視情況而定，這裡假設是int*/

const int MAXSIZE = 100;  /*存儲空間初始分配量*/

struct array
{
	ElemType data[MAXSIZE];  /*線性表的數組，最大值為MAXSIZE*/
	int length;  /*線性表的長度*/
};

從這裡我們來講解，順序結構的三個屬性：

好了基礎的說完了，我來貼代碼了。

array.h

#ifndef ARRAY_H_
#define ARRAY_H_

#include <iostream>
using namespace std;

typedef int ElemType;

const int MAXSIZE = 100;

struct array
{
	ElemType data[MAXSIZE];
	int length;
};

class arraylist
{
public:
	arraylist();  /*構造函數，初始化線性表*/
	bool ListEmpty();/*判斷線性表是否為空*/
	bool GetElem(int i, ElemType &e); /*根據i的值來獲取線性表中對應的第i個元素，將元素的值賦給e*/
	int Locate(ElemType& e);/*返回線性表中e出現的首個位置*/
	bool ListInsert(int i,ElemType e); /*將e插入到i元素之前*/
	bool ListDelete(int i,ElemType &e); /*將線性表中的i位置元素刪除，並將刪除的值存放在e中*/
	int ListLength(); /*返回線性表的長度*/
	bool ListTravel(); /*遍歷線性表*/
	void UnionList(array& arr1); /*將arr1中有，線性表中沒有的元素插入到線性表的後面*/
	~arraylist();
private:
	array arr;
};

#endif

array.cpp

#include "array.h"

arraylist::arraylist()
{
	arr.length = 0;
	for(int i = 0; i< MAXSIZE; i++)
	{
		arr.data[i] = 0;
	}
}

bool arraylist::ListEmpty()
{
	if(arr.length == 0)
		return true;
	else
		return false;
}

bool arraylist::GetElem(int pos, ElemType& ptr)
{
	if(arr.data == 0 || pos < 1|| pos>arr.length)
		return false;
	else
		ptr = arr.data[pos - 1];
	return true;
}

int arraylist::Locate(ElemType& Elem)
{
	for(int i = 0; i<arr.length; i++)
	{
		if(Elem == arr.data[i])
			return i+1;
	}
	return 0;
}

bool arraylist::ListInsert(int pos,ElemType Elem)
{
	if(arr.length == MAXSIZE)
	{
		return false;
	}
	if(pos > arr.length + 1 || pos < 1)
	{
		return false;
	}
	if(pos < arr.length + 1)
	{
		for(int i= pos; i <= arr.length; i++)
		{
			arr.data[i+1] = arr.data[i];
		}
	}
	arr.data[pos]=Elem;
	arr.length++;
	return true;
}
bool arraylist::ListDelete(int pos,ElemType &Elem)
{
	if(ListEmpty())
	{
		return false;
	}
	if(pos<1 || pos > arr.length)
	{
		return false;
	}
	Elem = arr.data[pos -1];
	for(int i= pos;i<arr.length;i++)
	{
		arr.data[i -1] = arr.data[i];
	}
	arr.length--;
	return true;
}

int arraylist::ListLength()
{
	return arr.length;
}

void arraylist::UnionList(array &arr2)
{
	int lena = arr.length;
	int lenb = arr2.length;
	int item;
	int flag = 1;

	for(int i = 0;i < lenb; i++)
	{
		if(arr2.length == 0 || i + 1 < 1||i+1 > arr2.length)
			flag = 0;
		item = arr2.data[i];
		if(flag)
		{
			if(Locate(item) == 0)
				ListInsert(++lena,item);
		}
	}
}

bool arraylist::ListTravel()
{
	if(ListEmpty())
	{
		return false;
	}
	for(int i = 0; i<arr.length; i++)
	{
		cout<<arr.data[i]<<" ";
	}
	cout<<endl;
	return true;
}

arraylist::~arraylist()
{
	arr.length = 0;
	for(int i = 0; i< MAXSIZE; i++)
	{
		arr.data[i] = 0;
	}
}

main.cpp

#include "array.h"

int main()
{
    arraylist list;
    for(int i = 0; i<5; i++)
    {
        list.ListInsert(i,i);
    }
    list.ListTravel();
    int var = 2;
    int pos = list.Locate(var);
    if(pos != 0)
    {
        int result;
        list.ListDelete(pos,result);
        cout<<"delete: "<<result<<endl;
    }
    list.ListTravel();

    array arr2 = {0};
    for(int i = 0; i<4; i++)
        arr2.data[i] = 6;
    arr2.length = 4;
    for(int i= 0 ; i<4; i++)
        cout<<arr2.data[i]<<" ";
    cout<<endl;

    list.UnionList(arr2);
    list.ListTravel();

    system("pause");
    return 0;
}

最終運行結果：