数据结构-表

基于C/C++顺序表和链表的构建与操作。

---

顺序表

---

静态表结构

//静态顺序表结构
typedef struct SeqList_Static{
    ElemType data[MaxSize];
    int length;
}SeqList_Static;

静态表操作

初始化

//顺序表初始化
SeqList_Static *SeqList_Static_Init()
{
    // 一次性开辟存储空间
    SeqList_Static *L = (SeqList_Static *)malloc(sizeof(SeqList_Static));
    L->data[0] = NULL;//初始化为空，长度为0
    L->length = 0;
    //初始化时，顺序插入0-9
    for (int i = 0; i < 10; i++)
    {
        L->data[i] = i;
        L->length++;
    }
    return L;
}

顺序打印

//静态链表的打印
void SeqList_Static_Print(SeqList_Static *L)
{
    for (int i = 0; i < L->length; i++)
    {
        printf("%d ", L->data[i]);
    }
}

元素插入

// 静态链表——插入元素
bool SeqList_Static_Insert(SeqList_Static *L, int i, ElemType x)
{   
    //判断插入位置的合法性
    if (i > L->length or i <= 0)
        return false;
    // 要插入位置的后面结点循环右移一位
    for (int j = L->length; j >= i; j--)
    {
        L->data[j] = L->data[j - 1];
    }
    L->data[i-1] = x;//插入元素
    L->length++;
    printf("\n插入之后的链表为:\n");
    SeqList_Static_Print(L);
    return true;
}

元素删除

// 静态链表——删除元素
bool SeqList_Static_Delete(SeqList_Static *L, int i)
{
    //判断要删除位置的合法性
    if (i > L->length or i <= 0)
        return false;
    // 要删除位置的后面结点循环左移一位
    for (; i < L->length; i++)
    {
        L->data[i-1] = L->data[i];
    }
    L->length--;
    printf("\n删除之后的链表为:\n");
    SeqList_Static_Print(L);
    return true;
}

---

动态表结构

#define MaxSize 100         //静态链表的最大长度
#define InitSize 10         //预定义顺序表初始长度
#define ListIncrement 10    //预定义顺序表扩充增量
typedef int ElemType;       //元素类型

//动态顺序表结构
typedef struct SeqList{
    ElemType *data;
    int length,capacity;//长度，动态的最大容量
} SeqList;

动态表操作

初始化

// 动态表初始化
SeqList *SeqList_Init()
{
    SeqList *L = (SeqList *)malloc(sizeof(SeqList));
    L->data = (ElemType *)malloc(sizeof(ElemType) * InitSize);//不加会出错 不懂为什么
    L->length = 0;
    L->capacity = InitSize; //动态的空间最大量
    L->data[0] = NULL;
    //初始化时，顺序插入0-9
    for (int i = 0; i < 10; i++)
    {
        L->data[i] = i;
        L->length++;
    }
    return L;
}

查找元素

//按值查找
int SeqList_Locate(SeqList L,ElemType e)
{
    for(int i=1;i<=L.length;i++)
        if(L.data[i-1]==e)return i;         //返回第i个元素(下标为i-1值为e)的位号i
    return 0;                               //返回0表明查找失败
}

插入元素

//插入元素
bool ListInsert_Seq(SeqList *L, int i, ElemType e)
{ 
    if (i < 1 || i > L->length + 1)
        return false; //i的位置不合法
    if (L->length >= L->capacity)
    {                                                                                                   //当前长度已达到最大容量，扩充分配存储空间
        ElemType *newbase = (ElemType *)realloc(L->data, sizeof(ElemType) * (InitSize + ListIncrement)); //顺序表扩充
        if (!newbase)
            return false;           //存储分配失败
        L->data = newbase;           //新基址
        L->capacity += ListIncrement; //增加存储容量
    }
    for (int j = L->length; j >= i; j--) //第i个元素以及其后的元素右移1个位置
        L->data[j] = L->data[j - 1];
    L->data[i - 1] = e; //腾出一个空位置插入新元素
    L->length++;        //表当前长度+1
    return true;
}

删除元素

//删除操作
bool ListDelete_Seq(SeqList &L,int i,ElemType& e){//删除第i个位置（1<=i<=L.length）元素
    if(i<1||i>L.length)return false; //i的位置不合法
    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;
}

···

---

### 单链表

---

结点结构

//结点元素
typedef int ElemType;

// 创建单链表结点结构
typedef struct LNode
{
    ElemType data;//数据域
    struct LNode *next;//指针域，用于指向下一个结点
} LNode, *LinkedList;

单链表创建

头插法

以顺序插入0-9为例创建带有头结点的单链表：

//头插法创建单链表
LinkedList Create_LinkedList_H()
{
    LNode *L;//创建头结点
    L = (LNode*)malloc(sizeof(LNode));//开辟头结点存储空间
    L->next = NULL;//默认将头结点指向空
    LNode *s; //创建辅助结点
    for (int x = 0; x < 10; x++)//0-9循环入队
    {
        s = (LNode *)malloc(sizeof(LNode));//开辟新的结点空间
        s->data = x;		//1.为新的结点赋值
        s->next = L->next;	//2.将新结点的后继指针指向头节点原来的后继，即插入到头结点后面
        L->next = s;	   //3.最后修改头结点的后继指针指向新节点
    }
    return L;//返回生成的链表
}

尾插法

// 尾插法创建单链表
LinkedList Create_LinkedList_R()
{
    LNode *L;//创建头结点
    L = (LNode*)malloc(sizeof(LNode));//开辟结点空间
    LNode *s;     //辅助节点指针
    LNode *r = L; //相当于尾指针，当前初始指向头结点
    for (ElemType x = 0; x < 10; x++)
    {
        s = (LNode *)malloc(sizeof(LNode));//开辟新节点空间
        s->data = x; //将新结点赋值
        r->next = s; //将新结点接到当前尾指针的后端
        r = s;       //将尾指针移到最后的结点
    }
    s->next = NULL;//将最后得结点后继指针指向空
    return L;//返回新的结点
}

单链表操作

遍历打印

// 遍历打印带头结点的单链表
void Print_LinkedList(LNode *L)
{
    LNode *p = L->next;//跳过头结点
    for (; p; p = p->next)//循环遍历链表
    {
        printf("%d ", p->data);
    }
}

查找元素

//按照序号查找元素
LinkedList GetElem_By_Number(LinkedList L, int i)
{
    if (i == 1)	//查找第一个元素，则直接返回头结点的后继结点
        return L->next;
    if (i < = 0)//非法查找
        return NULL;
    int j = 1;
    LNode *p = L->next;//跳过头结点
    while (p && j < i)//当p非空且未到循环次数
    {
        j++;
        p = p->next;//跳到下一个结点
    }
    return p;//返回p的指针位置
}

// 按照值来查找元素
LinkedList GetElem_By_Value(LinkedList L, ElemType x)
{
    if (L == NULL || x == NULL)//其一为空
        return NULL;
    LNode *p = L->next;//跳过头结点
    while (p->data != x)
    {
        p = p->next;
    }
    return p;//返回指针
}

插入结点

// 在第i个结点处插入新结点
LinkedList Insert_LinkedList(LinkedList &L, int i, ElemType x)
{
    LNode *p = GetElem_By_Number(L, i - 1);//得到要插入元素的前一个结点
    LNode *s = (LNode *)malloc(sizeof(LNode));//开辟存储空间
    s->data = x;//赋值
    s->next = p->next;//将新节点的后继指向要插入位置的后一个结点
    p->next = s;//将要插入位置的前一个元素的后继指向新节点
    return L;//返回新链表
}

删除结点

// 删除第i个结点
LinkedList Delete_LinkedList(LinkedList &L, int i)
{
    LNode *p = GetElem_By_Number(L, i - 1);//p指向删除元素的前一个结点
    LNode *q = p->next; //q指向要删除的结点
    p->next = q->next;  //前一个直接跳过要删除元素指向要删除元素的后继
    free(q);            //释放掉q的空间
    return L;
}

···

---

### 双链表

---

结点结构

//定义双链表结点结构
typedef struct DLNode{
    ElemType data;
    struct DLNode *prior, *next;//双指针
}DLNode;

双链表操作

头插法创建单链表

//头插法建立双链表
DLNode *Create_Double_LinkedList_H()
{
    DLNode *L;                            //头结点L
    L = (DLNode *)malloc(sizeof(DLNode)); //为头结点分配内存
    L->next = L;                          //初始化指针
    L->prior = L;
    L->data = NULL;
    DLNode *s; //新结点
    for (int i = 0; i < 10; i++)
    {
        s = (DLNode *)malloc(sizeof(DLNode));
        s->data = i;
        L->next->prior = s;
        s->prior = L;
        s->next = L->next;
        L->next = s;
    }
    return L;
}

尾插法创建双链表

//尾插法建立双链表
DLNode *Create_Double_LinkedList_R()
{
    DLNode *L = (DLNode *)malloc(sizeof(DLNode));
    L->prior = L->next = L;
    DLNode *s;
    for (int i = 0; i < 10; i++)
    {
        DLNode *r = L->prior; //定义为尾指针
        s = (DLNode *)malloc(sizeof(DLNode));
        s->data = i;//赋值
        r->next = s;//原尾指针后继指向新结点
        s->prior = r;//新结点前驱指向原尾结点
        s->next = L;//新结点的后继为头结点
        L->prior = s; //头结点的前驱为新结点
    }
    return L;
}

打印双链表

// 打印双循环链表
void Print_Double_LinkedList(DLNode *L)
{
    DLNode *p = L->next; //p跳过头结点，指向第一个结点
    while (p != L)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

···

---

### 测试源码

---

链表源码，请点击这里获取 顺序表源码，请点击这里获取

---

随时补充

---