算法思想----以输入结束标记作为链表创建的结束

1）构造带头结点的空链表
2）读入一个元素的值
3）当读入的元素值不是“输入结束标记”时，循环4）-7），如果是“输入结束标记”时，转步骤8）
4）申请一个新结点
5）将读入的元素值存入新结点的值域
6）将新结点插入在链表中
7）读入下一个元素的值，转步骤3）
8）建立完毕，返回头指针

尾插法建表（向后插入法）：

将新结点插到当前单链表的表尾上。
思路：增加一个尾指针p，使之指向当前单链表的表尾。

头插法建表（向前插入法）：

从一个空表开始，生成新结点，读入数据
将读入数据存放到新结点的数据域中，然后新结点插入到当前链表的头结点之后。

编制C/C++程序，利用链接存储方式实现下列功能：从键盘输入数据建立一个线性表（整数），并输出该线性表，输入输出要有相应的字幕提示

#include <iostream>
using namespace std;
typedef int ElemType;        //数据元素的类型为ElemType，将ElemType定义为int类型
//单链表结点的类型定义
typedef struct node
{
    ElemType data;
    node *next;
};

node* Create1()            //尾插法创建单链表
{
    ElemType x;
    node * h, *s, *p;
    h = new node;
    h->next = NULL;
    p = h;
    cin >> x;
    while (x != -1)
    {
        s = new node;
        s->data = x;
        p->next = s;
        p = s;
        cin >> x;
    }
    p->next = NULL;
    return h;
}

node* Create2()        //头插法创建单链表
{
    ElemType x;
    node *h, *s;
    h = new node;
    h->next = NULL;
    cin >> x;
    while (x != -1)
    {
        s = new node;
        s->data = x;
        s->next = h->next;
        h->next = s;
        cin >> x;
    }
    return h;
}
void Print(node *head)        //顺序输出单链表
{
    node *p;
    p = head->next;
    while (p != NULL)
    {
        cout << p->data << "，";
        p = p->next;
    }
}

int main()
{
    node *head;        //创建头指针
    cout << "请输入链表的数据，以-1作为结束：\n";
    //head = Create1();
    head = Create2();
    //cout << "这个链表数据为（尾插法）：\n";
    cout << "这个链表数据为（头插法）：\n";
    Print(head);
    system("pause");
    return 0;
}

线性表的顺序存储结构定义

是指用一组地址连续的存储单元依次存储线性表中的各个元素，使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中。
i> 采用顺序存储结构的线性表通常称为顺序表。

i> 1、当线性表采用顺序存储结构称为顺序表，是用一段地址连续的存储单元依次存储线性表的数据元素，通常用一维数组来实现。
2、顺序表中数据元素之间的逻辑关系是用存储位置表示的，即逻辑上相邻的数据元素，在存储位置上也是相邻，以此来保证元素之间的逻辑关系。

插入操作

指在表的第i (1≤i≤n+1)个位置，插入一个新元素e，使长度为n的线性表 (a1，…，ai-1，ai，…，an) 变成长度为n+1的线性表（a1，…,ai-1，e，ai，…，an）。

删除操作

指将表的第i(1≤i≤n)个元素删去，使长度为n的线性表 (a1，…,ai-1，ai，ai+1，…，an)，变成长度为n-1的线性表(a1，…,ai-1， ai+1，…，an)。

编制C/C++程序，利用顺序存储方式实现下列功能：从键盘输入数据建立一个线性表（整数），并输出该线性表；然后根据屏幕提示，进行数据的插入或删除等操作，并在插入或删除数据后输出线性表。

#include <iostream>
using namespace std;

#define MAXSIZE 1000        //根据需要设置为线性表可能达到的最大长度
typedef int ElemType;        //数组元素的类型为ElemType，将ElemType定义为int类型

//顺序表的建立：定义了一个名为SqList的结构体
typedef struct
{
    ElemType *data;        //存储空间的基地址
    int length;            //顺序表的当前长度（实际已经存入的元素个数）
}SqList; 

//顺序表的初始化
void InitList(SqList &L) 
{
    L.data = new ElemType[MAXSIZE];        //构造一个新的顺序表L，并为之分配大小为MAXSIZE的空间
    if (L.data == NULL)
    {
        cout << "存储空间分配失败！\n";
        exit(0);        //存储空间分配失败退出
    }
    L.length = 0;
    cout << "顺序表初始化完成！\n";
}

//通过顺序表读入值的方式，创建顺序表
void Create(SqList &L, int n) 
{
    ElemType e;
    for (int i = 0; i < n; i++) 
    {
        cin >> e;
        L.data[i] = e;
        L.length++;
    }
}

//顺序表插入值
/*在指定位置插入InsList(&L,i,e);                                *
 *要求在表的第i个位置，插入一个值为e的新元素。*/
void Insert(SqList &L, int i, ElemType e)
{
    if ((i < 1) || (i > L.length + 1))
    {
        cout << "插入地址不合法！\n";
        exit(0);
    }
    if (L.length == MAXSIZE)
    {
        cout << "存储空间已满！\n";
        exit(0);
    }
    for (int j = L.length - 1; j >= i - 1; j--)
    {
        L.data[j + 1] = L.data[j];
    }        //以上是从后比较的方法，可以边比较边移动
    L.data[i - 1] = e;
    ++L.length;
}
/*删除数据元素Delete(&L,i)
将顺序表的第i个元素删去*/
void Delete(SqList &L, int i)
{
    if ((i < 1) || (i > L.length))
    {
        cout << "删除地址不合法！\n";
        exit(0);
    }
    for (int j = i; j <= L.length - 1; j++)
    {
        L.data[j - 1] = L.data[j];
    }
    L.length--;
}
/*遍历并输出顺序表Print(L);
按照顺序表中元素的顺序依次输出每个元素的值*/
void Print(SqList L)
{
    if (L.length == 0)
    {
        cout << "线性表长度为0\n";
        exit(0);
    }
    for (int k = 0; k < L.length; k++)
    {
        if (k == L.length - 1)
        {
            cout << L.data[k];
        }
        else
        {
            cout << L.data[k] << ' ';
        }
    }
 }
/*清空顺序表ClearList(L);
清空顺序表：即表示将顺序表设置为长度为0的空表*/
void ClearList(SqList &L)
{
    L.length = 0;
}
/*判断顺序表是否存满IsListEmpty(L)
判断顺序表是都为空：如果空返回1，否则返回0*/
int IsListEmpty(SqList L)
{
    if (L.length == 0)
        return 1;
    else
        return 0;
}
/*求顺序表的长度ListLength(L)
要求返回线性表L的长度*/
int ListLength(SqList L)
{
    return L.length;
}
/*按序号查找GetData(L,I,e)
要求查找线性表L中第i个数据元素*/
void GetData(SqList L, int i, ElemType &e)
{
    if ((i < 1) || (i > L.length))
    {
        cout << "删除地址不合法！\n";
        exit(0);
    }
    e = L.data[i - 1];
}
/*按值查找Locate(L,e)
要求查找线性表中与给定值e相等的数据元素，
若在表L中找到与e相等的元素，则返回该元素在顺序表中的序号；
若找不到，则返回一个“空序号“，如'0'                                        */
int Locate(SqList L, ElemType e)
{
    int i = 1;
    while ((i <= L.length) && (L.data[i - 1] != e))
        i++;
    if (i <= L.length)        //找到，返回位序i+1
        return i;
    else
        return 0;        //未找到，返回位序0
}
int main()
{
    int n, i;
    ElemType e;
    cout << "请输入线性表的整数个数n：";
    cin >> n;
    SqList L;        //给线性表分配内存空间
    InitList(L);        //顺序表的初始化
    cout << "请输入线性表的各个元素：";
    Create(L, n);        //通过顺序表读入值的方式，创建顺序表
    cout << "原线性表如下：\n";
    Print(L);        //输出顺序表
    cout << "\n请输入要插入的元素及其所要插入的位置：";
    cin >> e >> i;
    Insert(L, i, e);
    cout << "插入之后的数组：\n";
    Print(L);
    cout << "\n请输入要删除的元素的位置：";
    cin >> i;
    Delete(L, i);
    cout << "删除之后的数组：\n";
    Print(L);
    cout << "\n请输入要查找的位置：";
    cin >> i;
    GetData(L, i, e);
    cout << "该值是：" << e;
    cout << "\n请输入要查找的值：";
    cin >> e;
    i = Locate(L, e);
    cout << "该值所在的位置是：" << i;
    system("pause");
    return 0;
}