数据结构-day4

  • 开发
  • 41

head.h

#ifndef __HEAD_H__
#define __HEAD_H__
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
enum
{
	FALSE=-1,
	SUCCESS
};
typedef struct Student
{
	char name[20];
	char sex;
	float score;
}Stu;
typedef Stu datatype;
//定义节点结构体
//节点：数据域 指针域
typedef struct Node
{
	//数据域：存储数据元素
	datatype data;
	//指针域：存储下一个节点的地址
	struct Node *next;
}*Linklist;
Linklist insert_head(Linklist head,datatype element);
Linklist create();
void output(Linklist head);
Linklist insert_rear(Linklist head,datatype element);
Linklist delete_head(Linklist head);
Linklist delete_rear(Linklist head);
Linklist insert_pos(Linklist head,int pos,datatype element);
Linklist delete_pos(Linklist head,int pos);
void update_pos(Linklist head,int pos,datatype element);
Linklist rev(Linklist head);
void search_pos(Linklist head ,int pos);
void last_n(Linklist head,int n);
Linklist delete_key(Linklist head,datatype key);
void update_key(Linklist head,datatype key ,datatype element);
int search_key(Linklist head,datatype key);
void simple_sort(Linklist head);
Linklist free_space(Linklist head);
void Bubble(Linklist head);
#endif

main.c


#include "head.h"
int main(int argc, const char *argv[])
{
	Linklist head=NULL; //定义单链表的头指针
	int n;
	datatype element;//插入的值
	printf("please enter n:");
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		printf("please enter %d element:\n",i+1);
		scanf("%s",element.name);
		getchar();
		scanf("%c",&element.sex);
//		getchar();
//		element.sex=getchar();
//		getchar();		
//		gets(element.name);
		scanf("%f",&element.score);
//		printf("%s,%c,%.1f\n",element.name,element.sex,element.score);
	//	head=insert_head(head,element);
		head=insert_rear(head,element);
	}

	//遍历
	output(head);
	//头删
//	head=delete_head(head);
//	head=delete_head(head);
	
	//尾删
//	head=delete_rear(head);
//	output(head);
/*	
	//按任意位置插入
	int pos;
	printf("please enter insert pos:");
	scanf("%d",&pos);
	printf("please enter insert element:");
	scanf("%d",&element);
	head=insert_pos(head,pos,element);
	output(head);
	//按任意位置删除
	printf("please enter delete pos:");
	scanf("%d",&pos);
	head=delete_pos(head,pos);
	output(head);

	//任意位置查找
	printf("please enter search pos:");
	scanf("%d",&pos);
	search_pos(head,pos);
	//任意位置修改
	printf("please enter update pos:");
	scanf("%d",&pos);
	printf("please enter update element:");
	scanf("%d",&element);
	update_pos(head,pos,element);
	output(head);
	*/
//	head=rev(head);
//	output(head);

//	printf("please enter n:");
//	scanf("%d",&n);
//	last_n(head,n);
//	output(head);

//	Bubble(head);
//	output(head);

/*	datatype key;
	printf("please enter search key:");
	scanf("%d",&key);
	int flag=search_key(head,key);
	if(flag==FALSE)
		puts("unexists");
	else
		puts("exists");
	
	//按任意元素修改
	printf("please enter update key:");
	scanf("%d",&key);
	printf("please enter update element:");
	scanf("%d",&element);
	update_key(head,key,element);
	output(head);
	//任意元素删除
	printf("please enter delete key:");
	scanf("%d",&key);
	head=delete_key(head,key);
	output(head);*/

	//简单选择排序
//	simple_sort(head);
//	output(head);
	//释放内存
//	head=free_space(head);
//	output(head);
	return 0;
}

test.c

#include "head.h"
Linklist create(){
	Linklist p=(Linklist)malloc(sizeof(struct Node));
	if(!p)
		return NULL;
	strcpy(p->data.name,"No");
	p->data.sex='N';
	p->data.score=-1;
	p->next=NULL;
	return p;
}
Linklist input(Linklist q,datatype element){
        strcpy(q->data.name,element.name);
        q->data.sex=element.sex;
        q->data.score=element.score;
	return q;
}
Linklist insert_head(Linklist head,datatype element){
	Linklist q=create();
	strcpy(q->data.name,element.name);
        q->data.sex=element.sex;
        q->data.score=element.score;
	if(!head)
		head=q;
	else{
		q->next=head;
		head=q;
	};
}
void output(Linklist head){
	if(!head){
		puts("empty");
		return;
	}
	Linklist p=head;
	while(p){
		printf("%s,%c,%.1f\n",p->data.name,p->data.sex,p->data.score);
		p=p->next;
	}
	
}
Linklist insert_rear(Linklist head,datatype element){
	Linklist q=create();
//	strcpy(q->data.name,element.name);
//	q->data.sex=element.sex;
//	q->data.score=element.score;
        q=input(q,element);
	if(!head)
		head=q;
	else{
		Linklist p=head;
		while(p->next)
			p=p->next;
		p->next=q;
	}
	return head;
}
Linklist delete_head(Linklist head){
	if(!head){
		puts("empty");
		return head;
	}
	Linklist p=head;
	head=head->next;
	free(p);
	p=NULL;
	return head;	
}
Linklist delete_rear(Linklist head){
	if(!head)//当链表为空
		return head;
	if(!head->next)//只有一个节点
	{
		free(head);
		head=NULL;
		return head;
	}
	//多个节点
	Linklist p=head;
	while(p->next->next){
		p=p->next;
	}
	free(p);
	p=NULL;
	return head;
}
int length(Linklist head){
	int len=0;
	Linklist p=head;
	while(p){
		p=p->next;
		len++;
	}
	return len;
}
Linklist insert_pos(Linklist head,int pos,datatype element){
	//判断位置是否合法
	if(pos<1||pos>length(head)+1){
		puts("error");
		return head;
	}
	//插入位置为1
	if(pos==1){
		head=insert_head(head,element);
		return head;
	}
        //插入位置不为1
        //找到pos-1的位置，插入pos-1的后面
	Linklist p=head;
	for(int i=0;i<pos-1;i++){
		p=p->next;
	}
	Linklist q=create();
	q=input(q,element);
	q->next=p->next;
	p->next=q;
	return head;
}
Linklist delete_pos(Linklist head,int pos){
	if(pos<1||pos>length(head)+1)
		return head;
	if(!head)
		return head;
	if(pos==1){
		delete_head(head);
		return head;
	}
	Linklist p=head;
	for(int i=0;i<pos-1;i++){
		p=p->next;
	}
	Linklist q=p->next;
	p->next=q->next;
	free(q);
	q=NULL;
	return head;	
}

void update_pos(Linklist head,int pos,datatype element){
	if(pos<1||pos>length(head)+1)
		return head;
	if(pos==1){
		head=input(head,element);
		return head;
	}
	Linklist p=head;
	for(int i=0;i<pos;i++){
		p=p->next;
	}
	p=input(p,element);
	return head;
}
Linklist rev(Linklist head){
	if(!head)
		return head;
	Linklist p=head->next;
	head->next=NULL;
	while(p)//p作为链表的新头
	{
		Linklist t=p;//t作为新链表的头
		p=p->next;
		t->next=head;
		head=t;
	}
	return head;
void search_pos(Linklist head ,int pos){
	if(NULL==head || pos<1 || pos>length(head))
		return;
	Linklist p=head;
	for(int i=1;i<pos;i++)
	{
		p=p->next;
	}
	printf("search by pos is %s,%c,%.1f\n",p->data.name,p->data.sex,p->data.score);
}
//倒数第n：正数第len-n+1   len --> n+while(p)-1
void last_n(Linklist head,int n){
	if(NULL==head || n<1 || n>length(head))
		return ;
	Linklist p,q;
	p=q=head;
	//p走n步
	for(int i=0;i<n;i++)
	{
		p=p->next;
	}
	//p和q走
	while(p)
	{
		p=p->next;
		q=q->next;
	}
	printf("last n is %s,%c,%.1f\n",p->data.name,p->data.sex,p->data.score);
}
Linklist delete_key(Linklist head,datatype key);
void update_key(Linklist head,datatype key ,datatype element);
int search_key(Linklist head,datatype key);
void simple_sort(Linklist head);//简单选择排序
Linklist free_space(Linklist head){//head=free_space(head);
	if(!head)
		return NULL;
	while(head)
	{
		head=delete_head(head);
	}
	return head;
void Bubble(Linklist head)
{
	if(NULL==head)
		return;

	int len=length(head);
	printf("%d  \n",len);
	for(int i=1;i<len;i++)
	{
		Linklist p=head;
		for(int j=0;j<len-i;j++)
		{
			if(p->data.score > p->next->data.score)
			{
				datatype t;
				strcpy(t.name,p->data.name);
				t.sex=p->data.sex;
				t.score=p->data.score;
				p=input(p,p->next);
				strcpy(p->next->data.name,t.name);
				p->next->data.sex=t.sex;
				p->next->data.score=t.score;
			}
				p=p->next;
		}
	}
}

结果展示：

阅读全部

相关推荐

最近更新

  3. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-02-03 09:00:02       94 阅读

  4. Could not load dynamic library ‘cudart64_100.dll‘

    2024-02-03 09:00:02       100 阅读

  9. 在Django里面运行非项目文件

    2024-02-03 09:00:02       82 阅读

  19. Python语言-面向对象

    2024-02-03 09:00:02       91 阅读

  20. 如何分清楚常见的 Git 分支管理策略Git Flow、GitHub Flow 和 GitLab Flow

    2024-02-03 09:00:02       85 阅读

热门阅读

  8. 算法篇：递归、搜索与回溯算法

    2024-02-03 09:00:02       42 阅读

  10. 华为OD机试真题-会议室占用时间-2023年OD统一考试（C卷）

    2024-02-03 09:00:02       56 阅读

  11. Android CameraManager 使用

    2024-02-03 09:00:02       51 阅读

  16. 【Go语言成长之路】Hello Go

    2024-02-03 09:00:02       57 阅读

  18. golang网络编程day6（结）

    2024-02-03 09:00:02       39 阅读

  21. PTA-C语言题库-选择排序（选择排序、冒泡排序+解法+解析）

    2024-02-03 09:00:02       47 阅读

  25. 机器翻译在各领域的应用

    2024-02-03 09:00:02       62 阅读

  26. 【Eclipse插件开发】2运行时环境Runtime总览-【下篇】

    2024-02-03 09:00:02       53 阅读

  30. 体悟PyTorch的优雅

    2024-02-03 09:00:02       55 阅读