数据结构 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; }
4. 遍历链表
void showLinkList(link_node_t *p) { while (p->next != NULL) { p = p->next; printf("%-4d", p->data); } }