数据结构学习——2
一、顺序表（2）
创建一个学生结构体的顺序表(练习)
sqlist.h
/*===============================================
* 文件名称：sqlist.h
* 创 建 者：
* 创建日期：2025年07月28日
* 描 述：
================================================*/
#ifndef __SQLIST_H__
#define __SQLIST_H__
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXLEN 5
typedef struct
{
char name[10];
char school[20];
}student;
typedef student data_t;
typedef struct
{
data_t *data[MAXLEN];
int last;
}seqlist_t;
//初始化创建
seqlist_t *seqlist_init();
//销毁
void seqlist_distroy(seqlist_t **sq);
//判空
int seqlist_empty(seqlist_t *sq);
//判满
int seqlist_full(seqlist_t *sq);
//清空
void seqlist_clear(seqlist_t *sq);
//插入到指定位置
int seqlist_insert(seqlist_t *sq,data_t *data,int index);
//直接插入到末尾
int seqlist_insertAtLast(seqlist_t *sq,data_t data);
//删除
int seqlist_delete(seqlist_t *sq,int index);
//遍历
int seqlist_print(seqlist_t *sq);
#endif
sqlist.c
/*===============================================
* 文件名称：sqlist.c
* 创 建 者：
* 创建日期：2025年07月28日
* 描 述：
================================================*/
#include <stdio.h>
#include "sqlist.h"
//初始化创建
seqlist_t *seqlist_init()
{
seqlist_t *sq = malloc(sizeof(seqlist_t));
if(sq ==NULL)
return NULL;
sq->last = -1;
return sq;
}
//销毁
void seqlist_distroy(seqlist_t **sq)
{
if(*sq == NULL)
return;
free(*sq);
}
//判空
int seqlist_empty(seqlist_t *sq)
{
if(sq->last == -1)
return 1;
return 0;
}
//判满
int seqlist_full(seqlist_t *sq)
{
if(sq->last == MAXLEN - 1)
return 1;
return 0;
}
//清空
void seqlist_clear(seqlist_t *sq)
{
sq->last = -1;
}
//插入到指定位置
int seqlist_insert(seqlist_t *sq,data_t *data,int index)
{
//先判断表满
if(seqlist_full(sq))
return 0;
//判断插入位置是否合法
if(index < 0 || index > sq->last + 1)
return 0;
//表为空且插入位置为0
if(seqlist_empty(sq) && index == 0)
{
sq->data[index] = data;
sq->last += 1;
return 1;
}
for(int i = sq->last + 1 ; i > index ; i--)
sq->data[i] = sq->data[i-1];
sq->data[index] = data;
sq->last += 1;
return 1;
}
//直接插入到末尾
int seqlist_insertAtLast(seqlist_t *sq,data_t data);
//删除
int seqlist_delete(seqlist_t *sq,int index)
{
//判断空
if(seqlist_empty(sq))
return 0;
//判断位置合法
if(index < 0 || index > sq->last)
return 0;
for(int i = index ; i < sq->last ; i++)
sq->data[i] = sq->data[i + 1];
sq->last -= 1;
return 1;
}
//遍历
int seqlist_print(seqlist_t *sq)
{
//判空
if(seqlist_empty(sq))
return 0;
int count = 0;
while(count <= sq->last)
{
printf("姓名: %s 学校: %s\n",
sq->data[count]->name,sq->data[count]->school);
count++;
}
return 1;
}
main.c
/*===============================================
* 文件名称：main.c
* 创 建 者：
* 创建日期：2025年07月28日
* 描 述：
================================================*/
#include <stdio.h>
#include "sqlist.h"
int main(int argc, char *argv[])
{
seqlist_t *list = seqlist_init();
student stu1 = {"zhangsan","school1"};
student stu2 = {"lisi","school2"};
student stu3 = {"wangwu","school3"};
student stu4 = {"zhaoliu","school4"};
student *p1 = &stu1;
student *p2 = &stu2;
student *p3 = &stu3;
student *p4 = &stu4;
seqlist_insert(list,p1,0);
seqlist_insert(list,p2,0);
seqlist_insert(list,p3,0);
seqlist_insert(list,p4,0);
seqlist_print(list);
printf("-------------------\n");
seqlist_delete(list,2);
seqlist_print(list);
return 0;
}
顺序表优缺点
优点：顺序表直观简洁，优点:引更改很方便。
缺点：空间固定，插入、删除的时间复杂度高，麻烦
二、链表
1.链表结构
以节点作为数据的载体，节点包含存储的信息，以及下一个节点的地址；
struct node{
char name[20];
struct node *next;
};
link.h
/*===============================================
* 文件名称：link.h
* 创 建 者：
* 创建日期：2025年07月28日
* 描 述：
================================================*/
#ifndef __LINK_H__
#define __LINK_H__
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef int data_t;
typedef struct Node{
data_t data;
struct Node *next;
}link_t;
//create
link_t *link_create();
//empty
int is_empty(link_t *head);
//clear
void link_clear(link_t *head);
//length
int link_length(link_t *head);
//insert
int link_insert(link_t *head,data_t data,int pos);
//remove
int link_remove(link_t *head,int pos);
//alter
int link_alter(link_t *head,data_t old_val,data_t new_val);
//search
link_t *link_search(link_t *head,data_t val);
//show
void link_show(link_t *head);
#endif
link.c
/*===============================================
* 文件名称：link.c
* 创 建 者：
* 创建日期：2025年07月28日
* 描 述：
================================================*/
#include "link.h"
//create
link_t *link_create()
{
link_t *head = (link_t *)malloc(sizeof(link_t));
if(head == NULL)
return NULL;
head->next = NULL;
return head;
}
//empty
int is_empty(link_t *head)
{
return head->next == NULL ? 1 : 0;
//return head->next == NULL;
}
//clear
void link_clear(link_t *head)
{
link_t *p = head->next;
while(p != NULL)
{
link_t *q = p;
p = p->next;
free(q);
}
head->next = NULL;
}
//length
int link_length(link_t *head)
{
int count = 0;
link_t *p = head->next;
while(p != NULL)
{
p = p->next;
count++;
}
return count;
}
//insert
int link_insert(link_t *head,data_t data,int pos)
{
if(pos < 0 || pos > link_length(head))
return 0;
link_t *p = head;
while(pos--)
p = p->next;
link_t *new = (link_t *)malloc(sizeof(link_t));
new->data = data;
new->next = p->next;
p->next = new;
return 1;
}
//remove
int link_remove(link_t *head,int pos)
{
if(pos < 0 || pos > link_length(head))
return 0;
link_t *p = head;
while(pos--)
p = p->next;
link_t *temp = p->next;
p->next = temp->next;
free(temp);
return 1;
}
//alter
int link_alter(link_t *head,data_t old_val,data_t new_val)
{
link_t *p = link_search(head,old_val);
if(p == NULL)
return 0;
p->data = new_val;
return 1;
}
//search
link_t *link_search(link_t *head,data_t val)
{
link_t *p = head->next;
while(p != NULL)
{
if(p->data == val)
break;
p = p->next;
}
return p;
}
//show
void link_show(link_t *head)
{
link_t *p = head->next;
while(p != NULL)
{
printf("%4d",p->data);
p = p->next;
}
printf("\n");
}
main.c
/*===============================================
* 文件名称：main.c
* 创 建 者：
* 创建日期：2025年07月28日
* 描 述：
================================================*/
#include "link.h"
int main(int argc, char *argv[])
{
link_t *head = link_create();
if(head == NULL)
printf("create failed\n");
int num = 0;
while(num < 20)
{
link_insert(head,num,num);
num++;
}
link_show(head);
link_insert(head,200,10);
link_show(head);
link_remove(head,10);
link_show(head);
link_alter(head,15,200);
link_show(head);
return 0;
}
运行截图
2.单链表的优缺点
优点：插入、删除很方便，空间不固定可以随时改变表的大小
缺点：不能从后继找到前驱
三、作业
将链表翻转输出
反转函数(link.c)
//reverse
void link_reverse(link_t *head)
{
if(is_empty(head))
return;
printf("链表反转\n");
//双指针
link_t *p = head->next;
link_t *q = p->next;
//定义交换次数
int count = link_length(head) - 1;
while(count--)
{
//p永远指向原链表的第一个元素
//改变p的next(保证后续不断开)
p->next = q->next;
//将分离出来的p的next保留head的next
q->next = head->next;
//将分离出来的q插入到head后面
head->next = q;
//改变q的位置开始新的一轮换位
q = p->next;
}
}
main.c
/*===============================================
* 文件名称：main.c
* 创 建 者：甘子煜(青木莲华)
* 创建日期：2025年07月28日
* 描 述：链表实现+反转函数
================================================*/
#include "link.h"
int main(int argc, char *argv[])
{
link_t *head = link_create();
if(head == NULL)
printf("create failed\n");
int num = 0;
while(num < 20)
{
link_insert(head,num,num);
num++;
}
link_show(head);
link_insert(head,200,10);
link_show(head);
link_remove(head,10);
link_show(head);
link_alter(head,15,200);
link_show(head);
link_reverse(head);
link_show(head);
link_clear(head);
printf("已清空\n");
link_show(head);
return 0;
}
运行截图
京公网安备 11010502036488号