发布时间: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 = {'