实验一：线性表的存储结构定义及基本操作

(一) 基本实验内容(顺序表)：

建立顺序表,完成顺序表的基本操作：初始化、插入、删除、逆转、输出、销毁、置空表、求表长、查找元素、判线性表是否为空、实现顺序表元素的逆转。

插入操作分成两种：根据顺序表结点的位置插入一个新结点(位置插入)，也可以根据给定的值进行插入( 值插入)；

删除操作也分成两种：根据顺序表结点的位置删除一个结点(位置删除)，也可以根据给定的值删除对应的第一个结点，或者删除指定值的所有结点(值删除)。

代码：

 #include<iostream>
 #include<stdlib.h>

 #define LIST_INIT_SIZE 100 //线性表储存空间的初始分配量
 #define LISTINCREMENT 10 //线性表储存空间的分配增量

using namespace std;

typedef struct{
    int *elem;//储存空间基质
    int length;//当前长度
    int listsize;//当前分配的储存容量(以sizeof(int)为单位)
}Sqlist;

//初始化
//1.构造一个空的线性表L
bool InitList(Sqlist &L){
    L.elem = new int[LIST_INIT_SIZE];
    if(! L.elem ) return false;//分配失败
    L.length = 0;//空表长度为0
    L.listsize = LIST_INIT_SIZE;//初始存储容量
    return true;
}
//2.输入具体元素
void CreatList (Sqlist &L, int n){
    cout << "you can input " << n << " elems"<< endl;
    cout <<"input: ";
    for(int i = 0; i < n; i++){
        cin >> L.elem[i];
        L.length++;
    }
}

//插入
//1.在L的第i个位置之前插入新的数据元素e,L的长度加1
bool ListInsert (Sqlist &L, int i, int e){

    //初始判断
    //i的合法值为1<=i<=ListLength(L)+1
    if(i < 1 || i > L.length+1) return false;//i不合法
    if(L.length >= L.listsize){
        //当前储存空间已满，增加分配
        int *newbase;
        newbase = (int *) realloc (L.elem, (L.listsize + LISTINCREMENT) * sizeof(int));
        if(! newbase) return false;//分配失败
        L.elem = newbase;//新的基址
        L.listsize += LISTINCREMENT;
    }

    //移动元素为插入做准备
    int *q; //q用来储存插入位置
    int *p; //p用来移动元素
    q = &(L.elem[i-1]);//q为插入的位置
    for(p = &(L.elem[L.length-1]); p >= q; --p){
        *(p+1) = *p;//插入位置以及之后的元素从最后开始依次右移    
    }

    //插入
    *q = e;//插入e
    ++L.length;//表长增加1；
    return true;
}
//2.在L中数值为n的第一个位置之前插入新的数据元素e，L的长度增加1
int ListSearch (Sqlist &L, int x);
bool ListInsertOnlyElem (Sqlist &L, int n, int e){

    //初始判断
    if(L.length >= L.listsize){
        //当前储存空间已满，增加分配
        int *newbase;
        newbase = (int *) realloc (L.elem, (L.listsize + LISTINCREMENT) * sizeof(int));
        if(! newbase) return false;//分配失败
        L.elem = newbase;//新的基址
        L.listsize += LISTINCREMENT;
    }

    //查找指定数据元素所在位置
    int i = 0;//用于储存查找元素所在位置
    i = ListSearch(L, n);
    //测试：cout << "ListSearch: " << ListSearch(L,n) << endl;
    //测试：cout << "i:" << i << endl;

    //移动元素为插入做准备
    int *q; //q用来储存插入位置
    int *p; //p用来移动元素
    q = &(L.elem[i]);//q为插入的位置
    for(p = &(L.elem[L.length-1]); p >= q; --p){
        *(p+1) = *p;//插入位置以及之后的元素从最后开始依次右移    
    }

    //插入
    *q = e;//插入e
    ++L.length;//表长增加1；
    return true;
}

//删除
//1.删除L的第i个数据元素，并用e返回其值，L的长度减1
bool ListDelete (Sqlist &L, int i, int &e){

    //初始判断
    //i的合法值为1<=i<=ListLength(L)
    if(i < 1 || i > L.length) return false;//i不合法

    //删除元素
    int *p;//用于要被删除元素的位置
    p = &(L.elem[i-1]);//被删除元素的位置
    e = *p;//储存被删除元素的位置

    //移动元素填补删除的位置
    int *q;//用于储存表尾元素位置
    q = L.elem + L.length - 1;//表尾元素的位置
    for(++p; p <= q; ++p){
        //此时p闲置了，用来移动元素
        *(p-1) = *p;//被删除的元素依次左移
    }

    --L.length;//表长减1
    return true;
}
//2.删除L中值为n的第一个位置的元素,并用e返回其位置，L的长度减1
bool ListDeleteOnlyElem (Sqlist &L, int n, int &e){

    //查找指定数据元素所在位置
    int i = 0;//用于储存查找元素所在位置
    i = ListSearch(L, n);

    //删除元素
    int *p;//用于要被删除元素的位置
    p = &(L.elem[i]);//被删除元素的位置
    e = i+1;//储存被删除元素的位置

    //移动元素填补删除的位置
    int *q;//用于储存表尾元素位置
    q = L.elem + L.length - 1;//表尾元素的位置
    for(++p; p <= q; ++p){
        //此时p闲置了，用来移动元素
        *(p-1) = *p;//被删除的元素依次左移
    }

    --L.length;//表长减1
    return true;    
}


//逆转
//1.顺序表逆转
bool ListReverse (Sqlist &L){
    //初始判断
    if(L.length == 0) return false;
    //逆转
    int i = 0, j = L.length-1;//找到顺序表的首尾
    for(i, j ; i < L.length/2 ; i++,j--){//从中间对两边进行交换
        swap(L.elem[i], L.elem[j]);
    }
    return true;
}
//2.元素逆转
bool ListReverseElem (Sqlist &L, int i, int j){
    //初始判断
    if(L.length == 0) return false;
    //元素逆转
    swap(L.elem[i], L.elem[j]);
    return true;
}

//输出
bool ListOutput (Sqlist &L){
    //初始判断
    if(L.length == 0){
        cout << "list is empty" << endl;
        return false;
    }
    //输出
    cout << "list: ";
    for( int i = 0; i < L.length; i++){
        cout << L.elem[i] << " ";
    }
    cout << endl;
    return true;
}

//销毁
bool DestroyList (Sqlist &L){
    if(L.elem){
        delete L.elem;
    }
    L.length = 0;
    L.listsize = 0;
    cout << "list has already destroied." << endl;
}

//置空表
bool ClearList(Sqlist &L){
    if(L.length == 0){
        cout << "list is empty" << endl;
        return false;
    }
    for( int i = 0; i < L.listsize; i++){
        L.elem[i] = 0;
    }
    L.length = 0;
    return true;
}

//求表长
int ListLength(Sqlist &L){
    cout << "listlength: " << L.length << endl;
    return L.length;
}

//查找元素
int ListSearch (Sqlist &L, int x){
    int flag = 0;//创建一个标记
    int i = 0;//用于返回所查找元素的位置
    if(L.length == 0) return NULL;//表内无元素

    for( i = 0; i < L.length; i++){
        //测试：cout << "xunhuang i:" << i << endl;
        if(L.elem[i] == x){
            cout << "elem's location is: " << i+1 << endl;
            flag = 1;
            break;
        }
    }
    if(flag == 0){
        cout << "can't find the elem." << endl;
    }
    return i;
}
//判断线性表是否为空
bool ListEmpty (Sqlist &L){
    if(L.length ==  0){
        cout << "list is empty." << endl;
        return false;
    }
    else{
        cout << "list is not empty." << endl;
        return true;
    }
}

int main(){
    Sqlist L;
    cout << "1. InitList" << endl;
    cout << "2. CreatList" << endl;
    cout << "3. ListInsert" << endl;
    cout << "4. ListInsertOnlyElem" << endl;
    cout << "5. ListDelete" << endl;
    cout << "6. ListDeleteOnlyElem" << endl;
    cout << "7. ListReverse" << endl;
    cout << "8. ListReverseElem" << endl;
    cout << "9. ListOutput" << endl;
    cout << "10.DestroyList" << endl;
    cout << "11.ClearList" << endl;
    cout << "12.ListLength" << endl;
    cout << "13.ListSearch" << endl;

    
    cout << endl;
    cout << "14.qute"<< endl;
    cout << endl;
    cout << "number: ";

    int number;
    cin >> number;
    while(number != 14){
        switch (number)
        {
        case 1:
            InitList(L);
            ListOutput(L);
            break;
        case 2:
            int n;
            cout << "what is the total number of input elems?" << endl;
            cout << "total number: ";
            cin >> n;
            CreatList(L, n);
            ListOutput(L);
            break;
        case 3:
            int i ;//插入位置
            int e ;//插入数据
            cout << "input the location you want to insert: ";
            cin >> i;
            cout <<  endl <<"input elem: " ;
            cin >> e;
            ListInsert(L,i,e);
            ListOutput(L);
            break; 
        case 4:
            cout << "input what elem you want to find for insert: ";
            cin >> n;
            cout << endl << "input elem: ";
            cin >> e;
            ListInsertOnlyElem(L,n,e);
            ListOutput(L);
            break;  
        case 5:
            cout << "input the location you want to delete: ";
            cin >> i;
            ListDelete(L,i,e);
            cout << endl << "delete elem is: " << e << endl;
            ListOutput(L);
            break;
        case 6:
            cout << "input what elem you want to find for delete: ";
            cin >> n;
            ListDeleteOnlyElem(L,n,e);
            cout << endl << "delete location is: " << e << endl;
            ListOutput(L);
            break;
        case 7:
            ListReverse(L);
            ListOutput(L);
            break;
        case 8:
            int j;
            cout << "input which two location of elem you want to swap: \n";
            cout << "first location: ";
            cin >> i;
            cout << endl << "second location: ";
            cin >> j;
            ListReverseElem(L,i-1,j-1);
            ListOutput(L);
            break;
        case 9:
            ListOutput(L);
            break;
        case 10:
            DestroyList(L);
            ListOutput(L);
            break;
        case 11:
            ClearList(L);
            ListOutput(L);
            break;
        case 12:
            ListLength(L);
            break;
        case 13:
            int x;
            cout << "input which elem you want to find: ";
            cin >> x;
            cout << endl;
            ListSearch(L, x);
            break;

        default:
            cout << "error number" << endl;
            break;
        }
        cout << "number: ";
        cin >> number;
    }
}

测试：
功能1：初始化
number 1；number 2；

功能2：插入
number 3；位置插入
number 4；值插入

功能3：删除
number 5；位置删除
number 6；值删除

功能4：逆转
number 7；逆转
number 8；元素逆转

功能5：输出
number 9；

功能6：销毁
number 10；

功能7：置空表
number 11；

功能8：求表长
number 12；

功能9：查找元素
number 13；

(二) 基本实验内容(单链表)：

建立单链表,完成链表(带表头结点) 的基本操作：建立链表（一个一个地输入各结点数据，并建立起前后相互链接的关系）、插入、删除、查找、输出、求前驱、求后继、两个有序链表的合并操作。

其他基本操作还有销毁链表、将链表置为空表、求链表的长度、获取某位置结点的内容、搜索结点。

插入操作分成两种：根据顺序表结点的位置插入一个新结点(位置插入)，也可以根据给定的值进行插入( 值插入)；

删除操作也分成两种：根据顺序表结点的位置删除一个结点(位置删除)，也可以根据给定的值删除对应的第一个结点，或者删除指定值的所有结点(值删除)。

 (三) 扩展实验内容(顺序表)

根据给定元素的值查前驱元素、查后继元素；顺序表合并等。

关于合并操作：对已建好的两个顺序表进行合并操作,若原线性表中元素非递减有序排列,要求合并后的结果还是有序(有序合并); 对于原顺序表中元素无序排列的合并只是完成 A=A ∪B ( 无序合并), 要求同样的数据元素只出现一次。

(四) 扩展实验内容(单链表)

根据给定结点的值查前驱元素、查后继元素；两个有序链表的合并（分别将两个单链表的结点依次插入到第 3 个单链表中,继续保持结点有序）。