数据结构2.22

思维导图

顺序表(按位置插入、按位置删除和去重)

//main.c
#include "seq_list.h"
int main()
{
	seq_p L = create_seq_list();
	insert_head(L,23);
	insert_head(L,20);
	insert_head(L,9);
    insert_head(L,20);
	insert_head(L,20);
	insert_head(L,6);
	insert_pos(L,321,2);
	insert_pos(L,123,6);
	out_put(L);
	putchar(10);
	del_pos(L,2);
	out_put(L);
    putchar(10);
    del(L);
    out_put(L);
	return 0;
}

//seq_list.c
#include "seq_list.h"

seq_p create_seq_list()
{
	seq_p L = (seq_p)malloc(sizeof(seq_list));
	if(L==NULL)
	{
		printf("空间申请失败\n");
		return;
	}
	L->len = 0;
	bzero(L,sizeof(L->data));
	return L;
}

int seq_empty(seq_p L)
{
	if(L==NULL)
		return -1;
	return L->len==0?1:0;
}
int seq_full(seq_p L)
{
	if(L==NULL)
		return -1;
	return L->len==MAX?1:0;
}

void out_put(seq_p L)
{
	if(L==NULL)
	{
		return;
	}
	if(seq_empty(L))
	{
		printf("表为空\n");
		return;
	}
	for(int i=0;i<L->len;i++)
	{
		printf("%d\n",L->data[i]);
	}
}

//顺序表头插
void insert_head(seq_p L,datatype data)
{
	if(L==NULL)
	{
		printf("入参为空,请检查\n");
		return;
	}
	if(seq_full(L)==1)
	{
		printf("表已满,不能头插插入\n");
		return;
	}
	for(int i=L->len-1;i>=0;i--)
	{
		L->data[i+1] = L->data[i];
	}
	L->data[0]=data;
	L->len++;
}

//按位置插入
//从第0个位置开始计数
void insert_pos(seq_p L,datatype value,int pos)
{
	if(L==NULL)
	{
		printf("入参为空,请检查\n");
		return;
	}
	if(seq_full(L)==1)
	{
		printf("表已满,不能按位置插入\n");
		return;
	}
	if(pos>L->len||pos<0)
	{	
		printf("位置不合理\n");
		return;
	}
	for(int i=L->len-1;i>=pos;i--)
	{
		L->data[i+1]=L->data[i];
	}
	L->data[pos]=value;
	L->len++;
}

//按位置删除
void del_pos(seq_p L,int pos)
{
	if(L==NULL)
	{
		printf("入参为空,请检查\n");
		return;
	}
	if(seq_empty(L))
	{
		printf("表为空,无需删除\n");
		return;
	}
	if(pos>L->len||pos<0)
	{	
		printf("位置不合理\n");
		return;
	}
	for(int i=pos;i<L->len-1;i++)
	{
		L->data[i]=L->data[i+1];
	}
	L->len--;
}

//顺序表去重
void del(seq_p L)
{
	if(L==NULL){return;}
	if(seq_empty(L)){return;}
	if(L->len==1){printf("只有一个元素\n");return;}
	for(int i=0;i<L->len;i++)
	{
		for(int j=i+1;j<L->len;j++)
		{
			if(L->data[i]==L->data[j])
			{
				del_pos(L,j);
				j--;
			}
		}
	}
}


//seq_list.h
#ifndef __SEQ_LIST_H__
#define __SEQ_LIST_H__
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 7
typedef int datatype;
typedef struct seq_list
{
	datatype data[MAX];
	int len;
}seq_list,*seq_p;
//创建顺序表
seq_p create_seq_list();
//判满
int seq_full(seq_p L);
//判空
int seq_empty(seq_p L);

//打印顺序表
void out_put(seq_p L);

//顺序表头插//顺序表头插
void insert_head(seq_p L,datatype data);

//按位置插入
void insert_pos(seq_p L,datatype value,int pos);

//按位置删除
void del_pos(seq_p L,int pos);

//顺序表去重
void del(seq_p L);




#endif

链表的尾插和输出

//main.c
#include "link_list.h"
int main()
{
    link_p H=NULL;
	H = create_head();
 	insert_head(H,12);
	insert_head(H,6);
	insert_head(H,90);
	pout(H);
	insert_tail(H,8);
	insert_tail(H,7879);
	pout(H);
	return 0;
}

//link_list.c
#include "link_list.h"

//创建单链表,在堆区申请空间
//实际在创建头结点,因为头结点指向整条链表
link_p create_head()
{
	link_p L= (link_p)malloc(sizeof(link_list));
	if(L==NULL)
	{
		printf("空间申请失败\n");
		return NULL;
	}
	L->len=0;  //创建时链表中没有元素,长度为0
	L->next=NULL;  //创建空的单链表,头结点没有指向,置空  
	return L;
}
//创建结点
link_p create_node(datatype data)
{
	link_p new=(link_p)malloc(sizeof(link_list));
	if(new==NULL)
	{
		printf("空间申请失败\n");
		return NULL;
	}
	new->data=data;
	return new;
}
//头插
void insert_head(link_p H,datatype data)
{
	//1\容错判断
	if(H==NULL)
	{
		printf("入参为空,请检查\n");
		return;
	}
	//申请新的结点
	link_p new = create_node(data);
	//新结点指向头结点的下一个结点
	new->next = H->next;
	//头结点指向新的结点
	H->next = new;
	H->len++;
}

//尾插
void insert_tail(link_p H,datatype data)
{
	if(H==NULL)
	{
		printf("入参为空,请检查\n");
		return;
	}
	link_p new = create_node(data);
	while(H->next!=NULL)
	{
		H=H->next;
	}
	H->next=new;
}

//输出
void pout(link_p H)
{
	link_p head=H->next;
	if (head == NULL)
	{
		printf("空link\n");
		return;
	}
	while (head != NULL) {
		printf("%d ", head->data);
		head = head->next;
	}
	putchar(10);
}


//link_list.h
#ifndef __LINK_LIST_H__
#define __LINK_LIST_H__
#include <stdio.h>
#include <stdlib.h>

typedef int datatype;
typedef struct link_list
{
	union
	{
		int len;
		datatype data;
	};
	struct link_list *next;
}link_list,*link_p;

//创建单链表,在堆区申请空间
link_p create_head();
//创建结点
link_p create_node(datatype data);
//头插
void insert_head(link_p H,datatype data);

//尾插
void insert_tail(link_p H,datatype data);
//输出
void pout(link_p H);

#endif