数据结构——02线性表

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档

文章目录


前言

提示:这里可以添加本文要记录的大概内容:
例如:随着人工智能的不断发展,机器学习这门技术也越来越重要,很多人都开启了学习机器学习,本文就介绍了机器学习的基础内容。


提示:以下是本篇文章正文内容,下面案例可供参考

一、线性表是什么?

1.概念

零个或多个数据元素的有限序列。元素之间是有顺序了,如果存在多个元素,第一个元素无前驱,最有一个没有后继,其他的元素只有一个前驱和一个后继。
当线性表元素的个数n(n>=0)定义为线性表的长度,当n=0时,为空表。在非空的表中每个元素都有一个确定的位置,如果a1是第一个元素,那么an就是第n个元素。

2.优缺点

	优点:
	1,无需为表中的逻辑关系增加额外的存储空间
	2,可以快速随机访问元素O(1)
	缺点:
	1,插入,删除元素需要移动元素o(n)
	2,无法动态存储。

二、源码

1.结构

	.
├── all
├── fun.c
├── fun.o
├── head.h
├── main.c
├── main.o
└── Makefile

0 directories, 7 files

2.源文件

代码如下(示例):
fun.c

#include "head.h"
SeqList *CreateSeqList(int len)
{
	SeqList* temp = malloc(sizeof(SeqList));
	if(NULL == temp)
	{
		perror("malloc error");
		exit(1);
	}
	temp->head = malloc(sizeof(DATATYPE)*len);
	if(NULL == temp->head)
	{
		perror("malloc error 2");
		exit(1);
	}
	temp->tlen = len;
	temp->clen = 0;
	return temp;
}
int DestroySeqList(SeqList **list)
{
	if(NULL == *list)
	{
		printf("*list is NULL");
		return -1;
	}
	free((*list)->head);
	free(*list);
	*list = NULL;
	return 0;
}
int ShowSeqList(SeqList *list)
{
	
	if(IsEmptySeqList(list))
	{
		return -1;
	}
	int i = 0;
	for(i=0;i<list->clen;++i)
	{
		printf("name = %s sex = %c age = %d grade = %d\n"
				,list->head[i].name
				,list->head[i].sex
				,list->head[i].age
				,list->head[i].score);
	}
	return 0;
}
int InsertTailSeqList(SeqList *list, DATATYPE *data)
{
	if(IsFullSeqList(list))
	{
		return -1;
	}
	memcpy(&list->head[list->clen],data,sizeof(*data));
	list->clen++;
	return 0;
}
int IsFullSeqList(SeqList *list)
{
	if(list->tlen == list->clen)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

int IsEmptySeqList(SeqList *list)
{
	return 0 == list->clen;
}
int InsertPosSeqList(SeqList *list, DATATYPE *data, int pos)
{
	int i =0;
	if(pos >= 0 && pos <list->clen+1)
	{
		for(i=0;i<list->clen-pos;++i)
		{
			memcpy(&list->head[list->clen-i],&list->head[list->clen-1-i],sizeof(*data));
		}
		memcpy(&list->head[pos],data,sizeof(*data));
		list->clen++;
	}
	else
	{
		printf("pos is error\n");
		return -1;	
	}

	return 0;
}
int FindSeqList(SeqList *list, char *name)
{
	int i =0 ;
	for(i=0;i<list->clen;++i)
	{
		if(0 == strcmp(list->head[i].name,name))

		{
			return i;
		}
	}
	return -1;
}
int ReviseSeqList(SeqList *list, char *old, DATATYPE *new)
{
	int ret = FindSeqList(list,old);
	if(ret>=0)
	{
		memcpy(&list->head[ret],new,sizeof(*new));
	}
	else
	{
		printf("old data not in this list\n");
		return -1;
	}
	return 0;
}
int DeleteSeqList(SeqList *list, char *name)
{
	int i= 0;
	int ret = FindSeqList(list,name);
	memset(&list->head[ret],0,sizeof(DATATYPE));
	if(ret>=0)
	{
		for(i=0;i<list->clen-ret;++i)
		{
			memcpy(&list->head[ret+i],&list->head[ret+1+i],sizeof(DATATYPE));
		}
		list->clen--;
	}
	else
	{
		printf("old data not in this list\n");
		return -1;
	}
	return 0;
}
int ClearSeqList(SeqList *list)
{
	list->clen =0;
	return 0;
}

head.h

#ifndef __HEAD_H__
#define __HEAD_H__

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct person
{
	char name[32];
	char sex;
	int age;
	int score;
}DATATYPE;

typedef struct list
{
	DATATYPE *head;
	int tlen;
	int clen;
}SeqList;
SeqList *CreateSeqList(int len);
int DestroySeqList(SeqList **list);
int ShowSeqList(SeqList *list);
int InsertTailSeqList(SeqList *list, DATATYPE *data);
int IsFullSeqList(SeqList *list);
int IsEmptySeqList(SeqList *list);
int InsertPosSeqList(SeqList *list, DATATYPE *data, int pos);
int FindSeqList(SeqList *list, char *name);
int ReviseSeqList(SeqList *list, char *old, DATATYPE *new);
int DeleteSeqList(SeqList *list, char *name);
int ClearSeqList(SeqList *list);



#endif

main.c

#include "head.h"

int main(int argc, const char *argv[])
{
	DATATYPE data[] = {
		{"zhangsan",'f',18,99},
		{"lisi",'f',18,99},
		{"waner",'f',18,99},	
		{"xiaowang",'f',18,99},
	};
	DATATYPE new = {"niuda",'f',18,99};
	SeqList* list = CreateSeqList(10);
	InsertTailSeqList(list,&data[0]);
	InsertTailSeqList(list,&data[1]);
	InsertTailSeqList(list,&data[2]);
	InsertPosSeqList(list,&data[3],3);
	DeleteSeqList(list,"lisi");
	ShowSeqList(list);
	DestroySeqList(&list);
	return 0;
}

makefile

OBJ=all
SRC=main.o fun.o
CC=gcc
LFLAG=-g -lm
$(OBJ):$(SRC)
	$(CC) $^ -o $@ $(LFLAG) 
%.o:%.c
	$(CC) -c $< -o $@ 

clean:
	rm $(OBJ)
disclean:
	rm $(OBJ) *.o


上一篇:C++ 顺序表实现及分析


下一篇:Git学习指南第11章