数据结构 day02

3. 线性表

3.1. 顺序表

3.1.3. 顺序表编程实现

操作：增删改查

.h 文件

#ifndef __SEQLIST_H__
#define __SEQLIST_H__
#define N 10
typedef 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,未满返回0
int 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为被查找的数据，返回下标，未找到返回-1
int 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,未满返回0
int 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为被查找的数据，返回下标，未找到返回-1
int 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 = {'\0', &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){printf("空间开辟失败\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){printf("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;
}