发布时间:2025-06-24 20:02:52  作者:北方职教升学中心  阅读量:340


3. 线性表

3.1. 顺序表

3.1.3. 顺序表编程实现

 操作:增删改查

.h 文件 

#ifndef __SEQLIST_H__#define __SEQLIST_H__#define N 10typedef struct seqlist{    int data[N];    int last; //代表数组中最后一个有效元素的下标} seqlist_t;//1.创建一个空的顺序表seqlist_t *CreateEpSeqlist();//2.向顺序表的指定位置插入数据int InsertIntoSeqlist(seqlist_t *p, int post, int data);//3.遍历顺序表void ShowSeqlist(seqlist_t *p);//4.判断顺序表是否为满,满返回1,未满返回0int IsFullSeqlist(seqlist_t *p);//5.判断顺序表是否为空int IsEpSeqlist(seqlist_t *p);//6.删除顺序表中指定位置的数据int DeleteIntoSeqlist(seqlist_t *p, int post);//7.清空顺序表 (清空:访问不到,但是内存中还有;销毁:内存清空)void ClearSeqList(seqlist_t *p);//8.修改指定位置的数据,post为被修改数据位置,data为修改成的数据int ChangePostSeqList(seqlist_t *p,int post,int data);//9.查找指定数据出现位置,data为被查找的数据,返回下标,未找到返回-1int SearchDataSeqList(seqlist_t *p,int data);#endif

 1.创建一个空的顺序表

#include <stdio.h>#include "seqlist.h"#include <stdlib.h>// 1.创建一个空的顺序表seqlist_t *CreateEpSeqlist(){    // 1. 动态申请一块空间存放顺序表    seqlist_t *p = NULL;    p = (seqlist_t *)malloc(sizeof(seqlist_t));    // 2. 检测空间是否开辟成功    if (NULL == p)    {        perror("malloc last!");        return NULL;    }    else    {        // 空间开辟成功,对last初始化        printf("malloc success!\n");        p->last = -1;        return p;    }}

2.向顺序表的指定位置插入数据

#include <stdio.h>#include "seqlist.h"// 2.向顺序表的指定位置插入数据int InsertIntoSeqlist(seqlist_t *p, int post, int data){    // post容错,post范围,顺序表满了    if (post > p->last + 1 || post < 0 || IsFullSeqlist(p))    {        perror("Insert Failed");        return -1;    }    // 从post开始,到last,中间的元素向后移动一位    for (int i = p->last; i >=post; i--)    {        p->data[i+1] = p->data[i];    }    p->data[post] = data;    p->last++;    return 0;}

3.遍历顺序表

#include <stdio.h>#include "seqlist.h"//3.遍历顺序表void ShowSeqlist(seqlist_t *p){     for (int i = 0; i <= p->last; i++)        printf("%-4d", p->data[i]);    printf("\n");}

4. 判断顺序表是否为满

#include <stdio.h>#include "seqlist.h"// 4.判断顺序表是否为满,满返回1,未满返回0int IsFullSeqlist(seqlist_t *p){    // if (p->last + 1 == N)    //     return 1;    // else    //     return 0;    return p->last +1 == N;}

5. 判断顺序表是否为空

#include <stdio.h>#include "seqlist.h"// 5.判断顺序表是否为空int IsEpSeqlist(seqlist_t *p){    return p->last == -1;}

 6. 删除顺序表中指定位置的数据

#include <stdio.h>#include "seqlist.h"// 6.删除顺序表中制定位置的数据int DeleteIntoSeqlist(seqlist_t *p, int post){    // 容错判断    if (IsEpSeqlist(p) || post < 0 || post > p->last)    {        perror("Delete Failed!");        return -1;    }    // 从下标为post+1 到last的元素向前移动一个单位    for (int i = post + 1; i <= p->last; i++)        p->data[i - 1] = p->data[i];    p->last--;    return 0;}

7. 清空顺序表

#include <stdio.h>#include "seqlist.h"// 7.清空顺序表 (清空:访问不到,但是内存中还有;销毁:内存清空)void ClearSeqList(seqlist_t *p){    p->last = -1;}

8. 修改指定位置的数据

#include <stdio.h>#include "seqlist.h"// 8.修改指定位置的数据,post为被修改数据位置,data为修改成的数据int ChangePostSeqList(seqlist_t *p, int post, int data){    // 容错判断    if (post < 0 || post > p->last || IsEpSeqlist(p))    {        perror("Change Failed!");        return -1;    }    // 修改指定位置的数据    p->data[post] = data;    return 0;}

9. 查找指定数据出现位置

#include <stdio.h>#include "seqlist.h"// 9.查找制定数据出现位置,data为被查找的数据,返回下标,未找到返回-1int SearchDataSeqList(seqlist_t *p, int data){    for (int i = 0; i <= p->last; i++)        if (p->data[i] == data)            return i;    return -1;}

 main.c

#include <stdio.h>#include "seqlist.h"#include <stdlib.h>int main(int argc, char const *argv[]){    // 创建空顺序表    seqlist_t *p = NULL;    p = CreateEpSeqlist();    // 插入数据    InsertIntoSeqlist(p, 0, 1);    InsertIntoSeqlist(p, 1, 2);    InsertIntoSeqlist(p, 2, 3);    InsertIntoSeqlist(p, 3, 4);    InsertIntoSeqlist(p, 4, 5);    // 遍历顺序表    ShowSeqlist(p);    // 删除指定位置的数据    DeleteIntoSeqlist(p, 2);    ShowSeqlist(p);    // 修改指定位置的数据    ChangePostSeqList(p, 1, 999);    ShowSeqlist(p);    // 查找指定数据的位置    printf("post = %d\n", SearchDataSeqList(p, 4));    // 清空顺序表    ClearSeqList(p);    printf("%d\n",IsEpSeqlist(p));    // 释放空间    free(p);    return 0;}

3.2. 链表 Link

        链表又叫单链表,链式存储结构,用于存储逻辑关系为 “ 一对一 ” 的数据。每个元素配有指针域,存储和访问时通过指针域指向下一个节点的地址。

3.2.1. 链表的特性

逻辑结构:线性结构

存储结构:链式存储

特点:内存可以不连续

解决问题:长度固定,插入和删除操作繁琐

操作:增删改查

struct node_t{    int data;    // 数据域    struct node_t next;    // 指针域,存放下一个节点的地址};

3.2.2. 单向链表

1)有头单向链表

        第一位数据域无效,无法存储数据

2)无头单向链表

        第一位数据域有效

 单向链表的基本操作

 1. 定义结构体数组,作为链表的一个节点

typedef struct Link_list{    int data;    struct Link_list *next;}link_node_t, *link_list_t;

2. 定义链表节点

link_node_t A = {'a', NULL};    link_node_t B = {'b', NULL};    link_node_t C = {'c', NULL};    link_node_t D = {'d', NULL};

3. 定义头指针

        无头

link_list_t h = &A;

        有头            定义头节点,让头指针指向头节点

link_node_t S = {'', &A};link_list_t h = &S;

4. 遍历链表

        无头

while (h != NULL)    {        printf("%-4c", h->data);        h = h->next;    }    printf("\n");

        有头

按照有头节点方式遍历

while (h->next != NULL){    h = h->next;    printf("%-4c", h->data);}

按照无头节点方式遍历

h = h->next;while(h != NULL){    printf("%-4c", h->data);    h = h->next;}
 有头单向链表的函数操作

头文件 .h 

#ifndef __LINKLIST_H__#define __LINKLIST_H__typedef int datatype;typedef struct node_t{    datatype data;       // 数据域    struct node_t *next; // 指针域,指向自身结构体的指针} link_node_t, *link_list_t;// 1.创建一个空的有头单向链表link_list_t createEmptyLinkList();// 2.链表指定位置插入数据int insertIntoPostLinkList(link_node_t *p, int post, datatype data);// 3.计算链表的长度。int lengthLinkList(link_node_t *p);// 4.遍历链表void showLinkList(link_node_t *p);// 5.链表指定位置删除数据int deletePostLinkList(link_node_t *p, int post);// 6.判断链表是否为空int isEmptyLinkList(link_node_t *p);// 7.清空单向链表void clearLinkList(link_node_t *p);// 8.修改指定位置的数据 post 被修改的位置 data修改成的数据int changePostLinkList(link_node_t *p, int post, datatype data);// 9.查找指定数据出现的位置 data被查找的数据 //search 查找int searchDataLinkList(link_node_t *p, datatype data);// 10.删除单向链表中出现的指定数据,data代表将单向链表中出现的所有data数据删除int deleteDataLinkList(link_node_t *p, datatype data);// 11.转置链表// 解题思想://(1) 将头节点与当前链表断开,断开前保存下头节点的下一个节点,//    保证后面链表能找得到,定义一个q保存头节点的下一个节点,//    断开后前面相当于一个空的链表,后面是一个无头的单向链表//(2) 遍历无头链表的所有节点,//    将每一个节点当做新节点插入空链表头节点的下一个节点//    (每次插入的头节点的下一个节点位置)void reverseLinkList(link_node_t *p);#endif

1. 创建一个空的有头单项链表

link_node_t *createEmptyLinkList(){    link_list_t h = (link_list_t)malloc(sizeof(link_node_t));        // 容错判断    if (h == NULL)    {        perror("空间开辟失败\n");        return NULL;    }    // 头节点初始化    h->next=NULL;        return h;}

2. 链表指定位置插入节点

int insertIntoPostLinkList(link_node_t *p, int post, datatype data){    link_list_t pnew = NULL; // 指向新节点    // 容错判断    if(post > lengthLinkList(p) || post < 0)    {        perror("post 范围错误");        return -1;    }    // 创建新节点并初始化    pnew = (link_list_t)malloc(sizeof(link_node_t));    pnew->data = data;    pnew ->next = NULL;    // 移动头指针,指向插入位置的前一个节点    for(int i = 0; i < post; i++)    {        p = p->next;    }    // 链接插入节点    pnew->next = p->next;    p ->next = pnew;    return 0;}

3. 计算链表长度

int lengthLinkList(link_node_t *p){    int len = 0;    while (p->next != NULL)    {        p = p->next;        len++;    }    return len;}

4. 遍历链表

void showLinkList(link_node_t *p){    while (p->next != NULL)    {        p = p->next;        printf("%-4d", p->data);    }}