数据结构：数据表与链表的基本操作

顺序表，全名顺序存储结构，是线性表的一种。通过《线性表》一节的学习我们知道，线性表用于存储逻辑关系为“一对一”的数据，顺序表自然也不例外。

不仅如此，顺序表对数据的物理存储结构也有要求。顺序表存储数据时，会提前申请一整块足够大小的物理空间，然后将数据依次存储起来，存储时做到数据元素之间不留一丝缝隙。

1.编写程序实现一个顺序表，每个节点有一个整数成员，功能如下：
(1)初始化顺序表
(2)显示整个链表的值。
(3)在尾部添加节点；
(4)在指定位置插入节点；
(5)查找任何一个值，如果存在则返回序号，否则返回-1
(6)返回指定序号节点值。
2.编写程序实现一个线性表采用链式存储，每个节点有一个整数成员，功能如下：
(1)初始化顺序表
(2)显示整个链表的值。
(3)在尾部添加节点；
(4)在指定位置插入节点；
(5)查找任何一个值，如果存在则返回序号，否则返回-1
(6)返回指定序号节点值。

（1）顺序表

#include<iostream>
using namespace std;

#define ListSize 100      //线性表的最大长度
typedef int DataType;

typedef struct
{
    DataType data[ListSize];   //用数组存储线性表中的元素
    DataType length;           //顺序表的长度
}SeqList, * PSeqList;

void InitList(PSeqList L);  //顺序表的初始化操作
int LengthList(PSeqList L); //求顺序表的长度
int GetData(PSeqList L, int i); //返回数据表中第i个元素的值
int InsList(PSeqList L, int i, DataType e);   //在顺序表的第i个位置插入元素
int DelList(PSeqList L, DataType i, DataType* e); //删除顺序表L的第i个数据元素
int Locate(PSeqList L, DataType e); //查找数据元素e在表中的位置
void PushFront(PSeqList L, DataType e); //头插，在表头插入元素e
void PopFront(PSeqList L);    //头删,删除表中的第一个元素
void PushBack(PSeqList L, DataType e);  //尾插，在表尾插入元素e
void PopBack(PSeqList L); //尾删，删除表尾元素
void ClearList(PSeqList L);  //清空顺序表
int EmptyList(PSeqList L);   //判断顺序表是否为空
void PrintList(PSeqList L);  //打印表中元素

int main(void)
{
    //system("chcp 65001");
    SeqList L;
    DataType data;
    //初始化顺序表
    InitList(&L);
    //在表中插入元素
    printf("依次在表中插入元素(1,2,3,4,5)：\n");
    InsList(&L, 1, 1);
    InsList(&L, 2, 2);
    InsList(&L, 3, 3);
    InsList(&L, 4, 4);
    InsList(&L, 5, 5);

    //打印表中元素
    printf("表中元素有：\n");
    PrintList(&L);
    //头插
    printf("在表头依次插入元素，6,7:\n");
    PushFront(&L, 6);
    PushFront(&L, 7);
    //尾插
    printf("在表尾依次插入元素，8,9:\n");
    PushBack(&L, 8);
    PushBack(&L, 9);
    printf("表中元素有：\n");
    PrintList(&L);
    //头删
    printf("头删一个元素:\n");
    PopFront(&L);
    //尾删
    printf("尾删一个元素:\n");
    PopBack(&L);
    //输出表中第4个元素值
    PrintList(&L);
    printf("表中第4个元素值为：\n%d\n", GetData(&L, 4));
    //查找表中第 i个元素的位置
    printf("元素2在表中的位置为：\n");
    printf("%d\n", Locate(&L, 2));
    //删除表中第2个元素对应的值
    printf("删除表中第2个元素：%d\n", DelList(&L, 2, &data));
    printf("顺序表的长度为：%d\n", LengthList(&L));
    printf("表中元素为：\n");
    PrintList(&L);
    //printf("删除的元素值为：%d\n", data);
    //清空顺序表
    ClearList(&L);
    PrintList(&L);
    system("pause");
    return 0;
}

//初始化顺序表
void InitList(PSeqList L)
{
    if (L == NULL)
    {
        return;
    }
    L->length = 0;
}

//求顺序表的长度

int LengthList(PSeqList L)
{
    if (L == NULL)
    {
        return 0;
    }
    return L->length;
}

//返回数据表中第i个元素的值
int GetData(PSeqList L, int i)
{
    if (L->length < 1 || (L->length > LengthList(L)))
    {
        return 0;
    }
    //数据元素的序号从1开始，数组下表从0开始，第i个元素对应的数组下标为i-1;
    return L->data[i - 1];
}

//在L中第i个位置，插入新的数据元素e

int InsList(PSeqList L, int i, DataType e)
{

    //判断插入位置是否合法
    if (i < 1 || L->length >(LengthList(L) + 1))
    {
        printf("插入位置不合法!\n");
        return 0;
    }
    //判断顺序表是否已满
    else if (L->length >= ListSize)
    {
        printf("顺序表已满，不能插入！\n");
        return 0;
    }
    else
    {
        for (int k = i; k <= L->length; k--)
        {
            L->data[k + 1] = L->data[k];
        }
        L->data[i - 1] = e;
        L->length++;   //数据表的长度加1
        return 1;
    }
    return 0;
}

//删除L的第i个数据元素

int DelList(PSeqList L, DataType i, DataType* e)
{
    if (L->length < 1)
    {
        printf("表为空！\n");
        return  0;
    }
    *e = L->data[i - 1];
    for (int k = i; k < L->length; k++)
    {
        L->data[k - 1] = L->data[k];
    }
    L->length--;
    return *e;
}

//查找e在表中的位置

int Locate(PSeqList L, DataType e)
{
    for (int k = 0; k < L->length; k++)
    {
        if (L->data[k] == e)
        {
            //k为e对应的数组下标，在表中对应序号应为k+1
            return k + 1;
        }
    }
    return 0;
}

//头插，在表头插入元素e

void PushFront(PSeqList L, DataType e)
{
    if (L->length == ListSize)
    {
        printf("顺序表已满，不能插入！\n");
    }
    //将表中元素依次后移一位
    for (int k = L->length; k > 0; k--)
    {
        L->data[k] = L->data[k - 1];
    }
    //插入元素
    L->data[0] = e;
    L->length++;
}

//头删,删除顺序表中的第一个元素，把顺序表中的元素依次往前移动一位

void PopFront(PSeqList L)
{
    if (EmptyList(L))
    {
        printf("顺序表为空，不能插入！\n");
    }
    for (int k = 1; k <= L->length - 1; k++)
    {
        L->data[k - 1] = L->data[k];
    }
    L->length--;
}

//尾插
void PushBack(PSeqList L, DataType e)
{
    if (L->length == ListSize)
    {
        printf("顺序表已满，不能插入!\n");
    }
    L->data[L->length] = e;
    L->length++;
}


//尾删
void PopBack(PSeqList L)
{
    if (EmptyList(L))
    {
        printf("表为空！\n");
    }
    L->length--;

}

//清空顺序表
void ClearList(PSeqList L)
{
    L->length = 0;
}

//判断表是否为空

int EmptyList(PSeqList L)
{
    if (L->length == 0)
    {
        return 1;
    }
    return 0;
}

//打印表中元素

void PrintList(PSeqList L)
{
    if (EmptyList(L))
    {
        printf("表为空！\n");
        return;
    }
    for (int k = 0; k < L->length; k++)
    {
        printf("%-3d", L->data[k]);
    }
    printf("\n");
}

（2）链表

#include <stdio.h>
#include <stdlib.h>
using namespace std;

typedef int DataType;

typedef struct Node
{
    DataType Data;
    struct Node* Next;
}Node, * LinkList;

void InitList(LinkList* PHead);//单链表的初始化
int ListEmpty(LinkList PHead);//判断单链表是否为空
void CreatFormHead(LinkList PHead); //头插法建表
void CreatFormTail(LinkList PHead); //尾插法建表
Node* Get(LinkList PHead, int i);//按序号查找
int Locate(LinkList PHead, DataType data); //按值查找
int length(LinkList PHead); //求表长操作
void InsList(LinkList PHead, int i, DataType data); //插入操作
int DelList(LinkList PHead, int i, DataType* data); //删除操作
void DestoryList(LinkList PHead);//销毁顺序表
void PrintList(LinkList PHead);//打印表中元素

int main(void)
{
    //system("chcp 65001");
    LinkList L;
    LinkList L1;
    DataType data;
    int num;//需要操作的元素序号
    int val;//插入元素值
    InitList(&L);
    InitList(&L1);
    printf("头插法建表(L1):");
    CreatFormHead(L1);
    printf("链表中的元素有:\n");
    PrintList(L1);
    printf("\n");
    printf("尾插法建表(L):");
    CreatFormTail(L);
    //后面为对尾插法所建表的操作
    printf("链表中的元素有:\n");
    PrintList(L);
    printf("\n");
    printf("在链表中插入一个元素:\n");
    printf("请输入插入位置:");
    scanf("%d", &num);
    printf("请输入插入元素值:");
    scanf("%d", &val);
    InsList(L, num, val);
    printf("链表中的元素有:\n");
    PrintList(L);
    printf("\n");
    printf("删除链表中的元素:\n");
    printf("请输入删除位置:");
    scanf("%d", &num);
    DelList(L, num, &data);
    printf("删除元素的值为%d\n", data);
    printf("\n");
    printf("链表中的元素有:\n");
    PrintList(L);
    printf("\n");
    printf("链表的长度为:%d\n", length(L));
    printf("\n");
    printf("请输入要查找的元素序号:\n");
    scanf("%d", &num);
    Node* p = Get(L, num);
    printf("第%d个元素值为:%d\n", num, p->Data);
    printf("请输入要查找的元素值:\n");
    scanf("%d", &val);
    printf("%d在表中的位置序号为:%d\n", val, Locate(L, val));
    printf("\n");
    //system("pause");

    return 0;
}

//单链表的初始化
void InitList(LinkList* PHead)
{
    if ((*PHead = (LinkList)malloc(sizeof(Node))) == NULL)
    {
        printf("内存申请失败!\n");
        return;
    }
    (*PHead)->Next = NULL;
}

//判断单链表是否为空
int ListEmpty(LinkList PHead)
{
    return PHead->Next == NULL;
}

//头插法建表
void CreatFormHead(LinkList PHead)
{
    DataType data;
    Node* s; //要插入的结点指针
    scanf("%d", &data);
    while (data != -1)//输入要插入的值以-1作为结束标志
    {
        s = (Node*)malloc(sizeof(Node));
        s->Data = data;
        s->Next = PHead->Next;
        PHead->Next = s;
        scanf("%d", &data);
    }
}

//尾插法建表
void CreatFormTail(LinkList PHead)
{
    Node* s;
    Node* tail;
    DataType data;
    tail = PHead;
    scanf("%d", &data);
    while (data != -1)
    {
        s = (Node*)malloc(sizeof(Node));
        s->Data = data;
        s->Next = tail->Next;
        tail->Next = s;
        tail = s;//tail始终指向表尾
        scanf("%d", &data);
    }
}

//按序号查找
Node* Get(LinkList PHead, int i)
{
    Node* p;//结点指针
    int j = 0;
    p = PHead;
    if (ListEmpty(PHead))//空表
    {
        printf("表为空！\n");
        return 0;
    }
    while (!ListEmpty(PHead) && j < i)
    {
        p = p->Next;
        j++;
    }
    if (j == i)
    {
        return p;/*返回指向第i个结点的指针p*/
    }
    return NULL;
}


//按值查找
int Locate(LinkList PHead, DataType data)
{
    Node* p = PHead->Next;
    int i = 1;
    while (p)
    {
        while (p->Data != data)
        {
            p = p->Next;
            i++;
        }
        break;//找到节点时退出循环
    }
    return i;
}

//求单链表的长度
int length(LinkList PHead)
{
    Node* p;
    p = PHead;
    int len = 0;
    while (p->Next != NULL)
    {
        len++;
        p = p->Next;
    }
    return len;
}

//任意位置插入
void InsList(LinkList PHead, int i, DataType data)
{
    Node* p;
    Node* s;
    p = PHead;
    int j = 0;
    while (p->Next != NULL && j < i - 1)
    {
        p = p->Next;
        j++;
    }
    if (p == NULL)
    {
        return; //插入位置不合法
    }
    s = (Node*)malloc(sizeof(Node));//新建一个结点
    s->Data = data;
    s->Next = p->Next;
    p->Next = s;
}

//任意位置删除
int DelList(LinkList PHead, int i, DataType* data)
{
    Node* p;
    Node* s;
    p = PHead;
    int k = 0;
    /* 删除位置i小于0，或者删除位置大于元素个数，
    比如链表中只有一个元素，i=2时 */
    if (i < 0 || i>length(PHead))
    {
        printf("删除位置不合法！\n");
        return 0;//删除位置不合法
    }
    while (p->Next != NULL && k < i - 1)
    {
        p = p->Next;
        k++;
    }
    s = p->Next;
    *data = s->Data;
    p->Next = s->Next;
    free(s);
    return *data;
}

//销毁链表
void DestoryList(LinkList PHead)
{
    Node* p;
    Node* q;
    p = PHead;
    while (p->Next != NULL)
    {
        q = p;
        p = p->Next;
        free(q);
    }
}


//打印表中元素
void PrintList(LinkList PHead)
{
    Node* p;
    p = PHead->Next;
    while (p)
    {
        printf("%d ", p->Data);
        p = p->Next;
    }
    printf("\n");
}

代码出自：
https://blog.csdn.net/liubo_01/article/details/80186552/
https://ask.csdn.net/questions/7678785?spm=1005.2026.3001.5839&username=wzxqq0823

其实就是数据结构的上机实验，第一个用数组实现，第二个用链表实现，百度搜索下。