数据结构学习笔记第二章线性表

r囧r小猫 2022-05-29 14:16 255阅读 0赞

线性表的逻辑结构

线性表的顺序储存结构

线性表的链式储存结构

顺序表和链表的比较

应用举例

内容：

1.线性表的逻辑结构

A:线性表的定义：

线性表是一种最见到那最常用的数据结构，也是最典型的线性结构/

线性表简称表，是由0个或者多个具有相同类型的数据元素构成的有限序列，元素的个数称为线性表的长度；

长度为0的线程被称为空表，对于一个满足上述性质的集合我们认为它属于线性表结构。

B：线性表的运算

线性表的运算是指对线性表的基本的操作

具体的我们在 链式表的基本组成中学习

2.线性表的顺序储存结构

// ConsoleApplication1.cpp: 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    #include<iostream>
    using namespace std;
    
    const int MAXSIZE =10000;
    template <class T>
    class Seqlist
    {
    public:
    	Seqlist() { length = 0; };
    	Seqlist ( const T a[], int n );
    	void getlength() { retrn length; }
    	void insert(int i, T x);
    	void Printlist();
    	T Delete(int i);
    	T get(int i);
    	int locate(T x);
    private:
    	T data[MAXSIZE];
    	int length;
    };
    
    template <class T>
    Seqlist <T>::Seqlist(const T a[], int n)
    {
    	if (n > MAXSIZE) throw "数组长度超过顺序表的最大值";
    	for (int i = 0; i < n; i++)
    	{
    		data[i] = a[i];
    	}
    	length = n;
    }
    
    template<class T>
    void Seqlist<T>::Printlist()
    {
    	cout << "按序号一次遍历顺序表中的各个数据元素：" << endl;
    	for (int i = 0; i < length; i++)
    		cout << data[i] << "";
    	cout << endl;
    }
    
    template<class T>
    void Seqlist<T>::insert(int i,T x)
    {
    	if (length >= MAXSIZE) throw"上溢异常";
    	if (i<1 || i>length)throw"位置异常";
    	for (int j = length; j >= i; j--)
    		data[j] = data[j-1];
    	data[i - 1] = x;
    	length++;
    
    }
    
    template<class  T >
    T Seqlist<T> ::Delete (int i)
    {
    	if (0 == length)throw "下溢异常";
    	if (i<1 || i>length)throw"位置异常";
    	T x = data[i - 1];
    	for (int j = i; j < length; j++)
    		data[j - 1] = data[j];
    	length--;
    	return x;
    }
    
    template<class T>
    T Seqlist <T>::get(int i)
    {
    	if (i < 1 || i>length)throw"位置异常";
    	return data[i - 1];
    }//"时间的复杂度是 1；
    
    template<class T>
    int Seqlist<T>::locate (const T x)
    {
    	for (int i = 0; i < length;i++)
    		if (x == data[i])return i + 1;
    	return 0;
    }//”时间的复杂度是 n
    
    
    int main()
    {
    	int a[7] = { 1,2,3,4,5,6,7 };
    	Seqlist<int>list(a, 7);
    	list.Printlist();
    	list.insert(1, 0);
    	list.Printlist();
    	int x = list.Delete(8);
    	cout << "删除元素：" << x << endl;
    	list.Printlist();
    	int p = list.locate(4);
    	cout << "元素4的位置；" << p << endl;
        return 0;
    }

3.线性表的链式储存结构

1，顺序结构和链式结构的比较：

顺序表的优点如下：

1，不需要为表示元素之间的逻辑关系而增加额外的存储空间；

2.可以方便的随机访问顺序表中任何·位置的元素；

顺序表的缺点如下：

1.插入和删除操作需要移动大量的元素，效率低下，在等概率的情况下，两种方法都需要移动一半的元素；

2.顺序表难以选择合适的储存容量，顺序表要求占用连续的储存空间，储存分配只能预先进行,依次属于静态的存储方式，如果开始的时候分配的内存过小那么就无法完成任务；

所以根据顺序表的缺点我们制作了链式储存结构：、

单链表：

// 链式储存结构.cpp: 定义控制台应用程序的入口点。
    //单链表
    
    #include "stdafx.h"
    #include<iostream>
    using namespace std;
    
    template<class T>
    struct Node
    {
    	T data;
    	struct Node<T> *next;
    };
    
    template <class T>
    class linklist
    {
    public:
    	linklist() { front = new node <T>; front->next = NULL; }
    	linklist(T a[], int n);
    	~linklist();
    	void printlist();
    	int getlength();
    	Node<T> *get(int i);
    	int locate(T x);
    	void insert(int i,T x);
    	void insert(int n;)
    	T Delete(int i);
    private :
    	Node<T>*front;
    };
    
    template <class T>//利用头插法建立链表
    linklist<T>::linklist(T a[],int n)
    {
    	front = new Node<T>;
    	front->next = NULL;
    	for (int i=n-1;i>=0;i--)
    	{
    		Node<T>*s = new Node <T>;
    		s->data = a[i];
    		s->next = front->next;
    		front->next = s;
    	}
    }
    //头插法
    //template <class T >
    //linklist <T>::linklist(T a[].int n)
    //{
    //	front = new Node <T>;
    //	new Node<T> *r =front;
    //	for (i = 0; i < n; i++)
    //	{
    //		Node <T> * p = new Node <T >;
    //		p->data = a[i];
    //		r->next = p;
    //		r = p;
    //	}
    //		r->next =NULL;
    //}//尾插法
    //linklist<T>::linklist(T a[],int n)
    //{
    //	front = new node <T>;
    //	for (i = 0; i < n; i++)
    //	{
    //		front->next = new node<T>;
    //		front->next->data = a[i];
    //		front = front->next;
    //	}
    //	front->next = NULL;
    //}
    //尾插法 的改良版 改变了front
    //template <class T>
    //linklist<T>::linklist(T a[],int n)
    //{
    //	front = new Node <T>;
    //	Node <T> *r = front;
    //	for (int i = 0; i < n; i++)
    //	{
    //		Node <T> *p=front->next;
    //		p->data =front ->next->data ;
    //		front->next = p;
    //	}
    //};//头插法的改良版
    template<class T>
    linklist<T>::~linklist()
    {
    	node<T>*p = front;
    	while (p)
    	{
    		front = p;
    		p = p->next;
    		delete front;
    	}
    }
    template <class T>
    void linklist<T>::printlist()
    {
    	new Node <T>*p=front;
    	for (;;)
    	{
    		if (front->next != 0)
    		{
    			p = front->next;
    			cout << p->data << " ";
    		}
    		else
    			break;
    	}
    }
    template<class T>
    int linklist<T>::getlength()
    {
    	int i=0;
    	new Node <T>*p=front;
    	for (;;)
    	{
    		if (front->next != 0)
    		{
    			p = p->next;
    			i++;
    		}
    		else
    			break;
    	}
    	return i;
    }
    template<class T>
    Node<T>* linklist<T>::get(int i)
    {
    	int i_n = 1;
    	new Node <T>*p=front->next;
    	while (!p&&i != j)
    	{
    		p = p->next;
    		j++;
    	}
    	return  p;
    }
    template<class T>
    int linklist<T>::locate(T x)
    {
    	int i_n = 1;
    	new Node <T>*p = front->next;
    	while (p)
    	{
    		if (p->value == x) return i_n;
    		i_n++:
    		p = p->next;
    	}
    	return -1;
    }
    template<class T>
    void linklist<T>::insert(int i, T x)//插入有前插和后插两种插法，而前后插又可以相互转换，并且也可以改进；
    {
    	new Node <T> *p=front;
    	if(i != 1)p = get(i - 1);
    	if (p)
    	{
    		Node<T>*s = new Node <T>;
    		s->data=x;
    		s->next = p->next;
    		p->next = s;
    		//一些奇妙的变式
    		//上图为后插：但是我们也可进行前插；
    		//	比如：get(i - 2)->next = s; s->next = p->next;
    	}
    	else
    		throw "插入的位置错误";
    }
    template<class T>
    T linklist<T>::Delete(int i)
    {
    	Node <T>*p = front;
    	if (i != 1)
    		p = get(i - 1);
    	if (!p && !p->next)throw"位置错误"
    	Node<T>*q = p->next;
    	p->next = q->next;
    	T x = q - > data;
    	delete q;
    	rerurn x;
    }
    int main()
    {
    	return 0;
    }

循环链表：

双向链表：

静态链表：

4.顺序表和链表的比较

4.1时间性能：如果采用的是查找而很少采用插入和删除操作，那么应该采用顺序表；

如果进行的是插入和删除操作只需要修改指针，那么用链表就更合适；

如果进行的删除和插入操作是发生在表头和表尾之间，那么用循环链表更加合适；

4.2 空间性能的比较：

顺序表的储存空间是静态分布的。因此必须提前确定其储存大小，如线性表的长度变化较大，则储存规模眼最大的长度来确定否则会出现溢出，但是如果大空间只是偶尔会用到，那么势必会造成空间的浪费；

而对于静态链表，其储存空间也是静态分配的，因此会具有同样的问题。

动态链表的存储空间是动态丰沛的，因此只要内存空间还有空闲就不会溢出；因此，对于空间变化较大或者长度难以估计的线性表，应该采用动态链表作为储存结构；

但是动态链表的储存密度比较小，储存空间的利用率比较低；