王道数据结构线性表基本操作实现

冷不防 2022-01-13 13:23 277阅读 0赞

#include<iostream>
    using namespace std;
    
    //#define MaxSize 50 //线性表最大长度
    #define InitSize 100 //表长度初始定义
    
    typedef int ElemType;
    
    //typedef struct { 
    // ElemType data[MaxSize]; //线性表元素
    // int length; //线性表当前长度
    //}SqList; //顺序表类型定义
    
    
    //线性表中的元素位序从1开始，而数组中元素的下标从0开始
    typedef struct { 
    	ElemType* data;            //指示动态分配数组的指针
    	int length;                //顺序表当前长度
    	int MaxSize;               //数组的最大容量
    }SqList;                       //动态分配数组顺序表的类型定义
    
    /*初始化表*/
    void InitList(SqList& L) { 
    	L.data = (ElemType*)malloc(sizeof(ElemType) * InitSize);  //C风格
    	//L.data = new ElemType[InitSize]; //C++风格
    	if (!L.data) exit(0);
    	L.length = 0;           //空表的长度为0
    	L.MaxSize = InitSize;   //初始数据元素存储容量
    }
    
    /*求表长*/
    int Length(SqList& L) { 
    	return L.length;
    }
    
    /* 按位查找操作： 查找第i个位置上的元素 */
    int GetElem(SqList& L, int i) { 
    	if (i<1 || i>L.length) { 
    		return -1;
    	}
    	return L.data[i - 1];
    }
    
    /*判空操作*/
    bool empty(SqList L) { 
    	return L.length == 0;
    }
    
    /*输出操作:*/
    void PrintList(SqList L) { 
    	if (empty(L)) cout << "SqList is Empty!" << endl;
    	else { 
    		for (int i = 0; i < L.length; i++) { 
    			cout << L.data[i] << " ";
    		}
    		cout << endl;
    	}
    }
    
    /*清空线性表*/
    bool ClearList(SqList& L) { 
    	L.length = 0;
    	return true;
    }
    
    
    /*销毁操作*/
    void DestoryList(SqList& L) { 
    	delete[] L.data;
    	L.data = NULL;
    	L.length = 0;
    	L.MaxSize = 0;
    }
    
    
    /* 顺序表插入操作: 顺序表的第i(1~L.length)个位置插入新元素e 若i的位置不合法，返回false，否则，将顺序表的第i个元素及之后所有元素后移一位 空出第i个位置，将新元素e插入,顺序表长度加1. */
    bool ListInsert(SqList& L, int i, ElemType e) { 
    	if (i<1 || i>L.length+1) {  //判断插入的位置是否合法
    		return false;
    	}
    	if (L.length >= L.MaxSize) {   //当前存储空间满，无法插入
    		return false;
    	}
    	for (int j = L.length; j >= i; j--) {   //将第i个元素及之后的元素后移一位
    		L.data[j] = L.data[j - 1];
    	}
    	L.data[i - 1] = e;              //在位置i处放入e
    	L.length++;
    	//cout << L.length << " zhi:" << L.data[i - 1] << endl;
    	return true;
    }
    
    /* 删除操作: 删除顺序表中第i个位置的元素，若成功返回true，并将被删除元素用引用 变量e返回，否则返回false */
    bool ListDetele(SqList& L, int i, ElemType& e) { 
    	if (i<1 || i>L.length) {  //判断删除的位置是否合法
    		return false;
    	}
    	e = L.data[i - 1];        //将被删除的元素赋值给e
    	for (int j = i; j < L.length;j++) {   //第i个位置后的元素前移一位
    		L.data[j - 1] = L.data[j];
    	}
    	L.length--;               //线性表长度减1
    	return true;
    }
    
    /* 按值查找： 查找第一个元素值等于e的元素，并返回其位序 */
    int LocateElem(SqList L, ElemType e) { 
    	for (int i = 0; i < L.length;i++) { 
    		if (L.data[i] == e) {     //找到e，返回位序i+1
    			return i + 1;
    		}
    	}
    	return 0;            //查找失败。
    }
    
    int main() { 
    	SqList list;
    	ElemType t;
    	InitList(list);          //初始化
    	for (int i = 1; i <= 10; i++) {  //插入数据
    		ListInsert(list, i, i+10);
    	}
    
    	PrintList(list);  //遍历线性表
    	cout << "Length: " << Length(list) << endl;
    	cout << "按值查找: " << LocateElem(list,15) << endl;
    	cout << "按位查找: " << GetElem(list, 5) << endl;
    	cout << "Delete Elem: "; 
    	ListDetele(list, 2, t);
    	cout << t << endl;
    	PrintList(list);
    	
    	cout << "Clear List: ";
    	ClearList(list);
    	PrintList(list);
    
    	return 0;
    }