数据结构与算法——线性表—顺序表（顺序线性表）

喜欢ヅ旅行 2022-03-16 12:54 466阅读 0赞

线性表（linear list）是最简单，也是最基本的一种线性数据结构，它有两种存储表示方法：**顺序表和链表**。它的主要基本操作是插入，删除和查找。  
**3.1 顺序表（顺序线性表）**  
顺序表是用一组地址连续的顺序存储单元依次存储数据元素的线性结构。换句话说，**将线性表中的数据元素一个挨一个得存放在某个存储区域中**。顺序表又称顺序线性表（顺序存储的线性表）  
特点：具有随机存取的特点，即**快速查找**。但是做**插入和删除**动作时，需要移动大量的元素，效率较低。  
顺序表在计算机中是以**数组的形式**保存的线性表。

顺序表相关操作：直接调用函数即可，封装好的接口  
SqList.h:  
/\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*  
\[顺序表操作\]  
\[1\] initList, 初始化一个空的顺序表  
\[2\] createList, 根据数组 elems 构建一个顺序表  
\[3\] insertElem, 在顺序表中第 pos 个位置插入元素 elem  
\[4\] removeElem, 在顺序表中移除第 pos 个元素，并由 pElem 返回其值  
\[5\] getElem, 获取顺序表上位置为 pos 的元素，并由 pElem 返回其值  
\[6\] locateElem, 获取元素 elem 在顺序表上第一次出现的位置，如果不存在返回 -1  
\[7\] printList, 打印整个顺序表  
\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/

#pragma once
    
    #include <iostream>
    using namespace std;
    /*****************************************
    第一部分，数据结构、宏定义
    ***************************************/
    
    #define MAXSIZE 10 //无 ；
    
    typedef int ElemType;//有 ；元素类型
    
    typedef struct   //顺序表结构类型
    {
    	ElemType data[MAXSIZE];
    	int length;
    
    }SqList;//sequence顺序
    
    typedef enum
    {
    	OK = 0, //,
    	ERROR = 1 //null
    
    }STATU;
    
    /*****************************************
    第二部分，函数实现
    ****************************************/
    void initList(SqList *pList) {
    
    	pList->length = 0;
    
    }
    STATU createList(SqList *pList, ElemType elems[], int lenght)
    {
    	if (lenght > MAXSIZE)
    		return ERROR;
    
    	for (int i = 0; i < lenght; i++)
    	{
    		pList->data[i] = elems[i];
    	}
    
    	pList->length = lenght;
    
    	return OK;
    }
    
    STATU insertElem(SqList *pList, int pos, ElemType elem)
    {
    	if (pos < 0 || pos > pList->length)
    	{
    		return ERROR;
    	}
    
    	for (int i = pList->length; i > pos; i--)
    	{
    		pList->data[i] = pList->data[i-1];//将data[pos]及后面的元素都向后移动一个位置
    	}
    
    	pList->data[pos] = elem;
    	pList->length ++;
    
    	return OK;
    }
    
    
    STATU removeElem(SqList *pList, int pos, ElemType *elem)
    {
    	if (pos < 0 || pos > pList->length)
    	{
    		return ERROR;
    	}
    
    	*elem = pList->data[pos];//先将pos位置的元素提取出来，不然就会被后面的一位覆盖掉
    
    	for (int i = pos; i < pList->length-1; i++)//待测试 要加-1
    	{
    		pList->data[i] = pList->data[i+1];
    	}
    
    	pList->length --;
    
    	return OK;
    }
    
    STATU getElem(SqList list, int pos, ElemType *pElem) {
    
    	// 判断位置是否合理
    
    	if (pos < 0 || pos > list.length - 1)
    
    		return ERROR;
    
    
    
    	*pElem = list.data[pos];
    
    	return OK;
    
    }
    
    int locateElem(SqList list, ElemType elem) {
    
    	int pos = 0;
    
    	for (pos = 0; pos < list.length; pos++) {
    
    		if (elem == list.data[pos])
    
    			return pos;
    
    	}
    
    	return -1;
    
    }
    
    void myPrint(SqList list)
    {
    	if (0 == list.length)
    	{
    		cout << "list is empty" << endl;
    	}
    
    	for (int i = 0; i>list.length; ++i)
    	{
    		cout << list.data[i] << " ";
    	}
    	cout << endl;
    }