学步园

今天是通关数据结构这本书进程中的第一天，所以一定要耐着性子做下去。

目的：熟练使用顺序存储和链式存储。最后做出一个顺序存储的简单模板和一个完善的实现链式存储学生信息管理系统。

1.顺序表的存储结构

//-----顺序表的存储结构-----
#define MAXSIZE 100//顺序表可能达到的最大长度。
typedef struct{
	ElemType *elem;//基地址,相当于一个数组的首地址
	int length;//当前长度
}Sqlist;//定义一个Sqlist类型，生成的数据具有Sqlist类型的空间存储区域。

2.顺序表的基本操作（初始化、查找、插入、删除）

//-----顺序表的初始化-----
Status InitList_Sq(SqList &L){//构造一个空顺序表
	L.elem= new ElemType[MAXSIZE];//为顺序表分配大小为MAXSIZE的存储空间
	if(!L.elem) exit(OVERFLOW)//存储分配失败
	L.length=0;//空表长度为0
	return OK;
}

//-----顺序表的查找-----	
Status LocateElem_Sq(SqList L,ElemType e){//查找是否具有e相等元素，并返回其“位序”。
	for(i=0; i<L.length; i++){
		if(L.elem[i]==e) return i+1;
	return 0;
		
}//位序：位置顺序，而非下标。

//-----顺序表的插入-----
Status ListInsert_Sq(SqList &L,int i, ElemType e){//在线性表L的第i个位置前插入元素e
	if(i<1||i>L.length+1||L.length==MAXSIZE) return ERROR;
	e=L.elem[i-1];
	for(j=L.length-1; j>=i-1; j--)
		L.elem[j+1]=L.elem[j];
	L.elem[i-1]=e;
	++L.length;
	return OK;
}

//-----顺序表的删除-----
Status ListDelete_Sq(SqList &L,int i, ElemType &e){//删除线性表L的第i个位置的元素，并赋值给e
	if(i<1||i>L.length) return ERROR;
	e=L.elem[i-1];
	for(j=i; j<=L.length-1; j++)
		L.elem[j-1]=L.elem[j];
	--L.length;
	return OK;
}

总结：顺序表的一系列操作相对而言是比较简单的，需要注意的是位序和数组下标不要搞混了，位序=数组下标+1。

对线性表顺序存储的简单实现：

#include<iostream>
#include<cstdlib>
#define MAXSIZE 100
#define Status int
#define ERROR 0
#define OVERFLOW -1
#define ElemType int
#define OK 1
using namespace std;

//-----顺序表的存储结构-----
typedef struct{
	ElemType *elem;//基地址,相当于一个数组的首地址
	int length;//当前长度
}SqList;

//-----顺序表的初始化-----
Status InitList_Sq(SqList &L){//构造一个空顺序表
	L.elem= new ElemType[MAXSIZE];//为顺序表分配大小为MAXSIZE的存储空间
	if(!L.elem) exit(OVERFLOW);//存储分配失败
	int len,i;
	cout<<"输入线性表长度"<<endl;
	cin>>len;
	for(i=0,L.length=0; i<len; i++){
	   cin>>L.elem[i];
	   ++L.length;//空表长度为0
    }
	return OK;
}

//-----顺序表的查找-----	
Status LocateElem_Sq(SqList L,ElemType e){//查找是否具有e相等元素，并返回其“位序”。
	for(int i=0; i<L.length; i++)
		if(L.elem[i]==e) return i+1;
	return 0;
}

//-----顺序表的插入-----
Status ListInsert_Sq(SqList &L,int i, ElemType e){
    if(i<1||i>L.length+1||L.length==MAXSIZE) return ERROR;
	for(int j=L.length-1; j>=i-1; j--)
		L.elem[j+1]=L.elem[j];
	L.elem[i-1]=e;
	++L.length;
	return OK;
}

//-----顺序表的删除-----
Status ListDelete_Sq(SqList &L,int i, ElemType &e){
	if(i<1||i>L.length) return ERROR;
	e=L.elem[i-1];
	for(int j=i; j<=L.length-1; j++)
		L.elem[j-1]=L.elem[j];
	--L.length;
	return OK;
}

int main(){
    SqList L;
    InitList_Sq(L);
    cout<<"线性表为："<<endl; 
    for(int i=0; i<L.length; i++)
        cout<<L.elem[i]<<" ";
    cout<<endl<<endl<<"在第三个位置插入元素3后，线性表为:"<<endl; 
    ListInsert_Sq(L,3,3);
    for(int i=0; i<L.length; i++)
        cout<<L.elem[i]<<" ";
    int e;
    ListDelete_Sq(L,5,e);
    cout<<endl<<endl<<"第五个位置删除的元素为："<<e;
    cout<<endl<<endl<<"查找等于13的元素位于第"<<LocateElem_Sq(L,13)<<"个位置"<<endl; 
    //while(1);
}

输入测试数据：

————2014.11.4