数据结构：（1）线性表

一、基本概念

概念：零个或多个数据元素的有限序列

   元素之间是有顺序了。如果存在多个元素，第一个元素无前驱，最后一个没有后继，其他的元素只有一个前驱和一个后继。

   当线性表元素的个数n（n>=0）定义为线性表的长度，当n=0时，为空表。在非空的表中每个元素都有一个确定的位置，如果a1是第一个元素，那么an就是第n个元素。

线性表的常规操作 ADT
typedef struct person {
   char name[32];
   char sex;
   int age;
   int score;
}DATATYPE;
//typedef int Datatype;

typedef struct list {
   DATATYPE *head;//数组名
   int tlen;//数组有多大
   int clen;//当前存储了几个元素
}SeqList;

例：

1.SeqList *CreateSeqList(int len);
2.int DestroySeqList(SeqList *list);
3.int ShowSeqList(SeqList *list);
4.int InsertTailSeqList(SeqList *list, DATATYPE data);
5.int IsFullSeqList(SeqList *list);
6.int IsEmptySeqList(SeqList *list);
7.int InsertPosSeqList(SeqList *list, DATATYPE data, int pos);
8.int FindSeqList(SeqList *list, char *name);
9.int ModifySeqList(SeqList *list, char *old, DATATYPE new);
10.int DeleteSeqList(SeqList *list, char *name);
11.int ClearSeqList(SeqList *list);

内存泄露检测工具
sudo apt-get install valgrind
valgrind ./all

1. CreateSeqList 创建表

SeqList *CreateSeqList(int size)
{if(size<=0){fprintf(stderr,"size is error,range >1");return NULL;}SeqList* sl = ( SeqList*)malloc(sizeof(SeqList));if(NULL == sl){perror("CreateSeqList malloc");exit(1);}sl->head = (DATATYPE*)malloc(sizeof(DATATYPE)*size);if(NULL == sl->head){perror("CreateSeqList malloc");exit(1);}sl->tlen = size;sl->clen = 0;return sl;
}

2. DestroySeqList 销毁表

int DestroySeqList(SeqList *sl)
{if(NULL == sl){fprintf(stderr,"SeqList point not NULL");return 1;}if(sl->head)free(sl->head);free(sl);return 0;
}

3. ShowSeqList 遍历表，打印内容

int ShowSeqList(SeqList *list)
{if(NULL == list){fprintf(stderr,"list error,list is null\n");return -1;}int i = 0 ;int len = GetSizeSeqList(list);for(i=0;i<len;i++){printf("name:%s sex:%c age:%d score:%d\n",list->head[i].name,list->head[i].sex,list->head[i].age,list->head[i].score);}return 0;
}

4. InsertTailSeqList 尾插

int InsertTailSeqList(SeqList *list, DATATYPE *data)
{if(NULL == list){fprintf(stderr,"InsertTailSeqList error,list is null\n");return -1;}if(IsFullSeqList(list)){fprintf(stderr,"InsertTailSeqList error ,seqlist is full\n");return 1;}memcpy(&list->head[list->clen] , data,sizeof(DATATYPE));list->clen++;return 0;
}

5. IsFullSeqList 表满判断

int IsFullSeqList(SeqList *list)
{if(NULL == list){fprintf(stderr,"IsFullSeqList error,list is null\n");return -1;}return list->clen == list->tlen;
}

6. IsEmptySeqList 表空判断

int IsEmptySeqList(SeqList *list)
{return 0==list->clen;
}

7. InsertPosSeqList 任意位置插入

int InsertPosSeqList(SeqList *list, DATATYPE *data, int pos)
{if(NULL == list){fprintf(stderr,"list is null\n");return 1;}if(IsFullSeqList(list)){fprintf(stderr,"list is full\n");return 1;}if(pos<0 ||pos>GetSizeSeqList(list)){fprintf(stderr,"pos is error\n");return 1;}int i = 0 ;for(i =GetSizeSeqList(list); i>=pos ; i-- ){memcpy(&list->head[i],&list->head[i-1],sizeof(DATATYPE));}memcpy(&list->head[pos],data,sizeof(DATATYPE));list->clen++;return 0;
}

8. FindSeqList 查找表内某个内容，返回其下标

int FindSeqList(SeqList *list, char *name)
{if(NULL == list){fprintf(stderr,"FindSeqList error,list is null\n");return 1;}if(IsEmptySeqList(list)){fprintf(stderr,"FindSeqList error,seqlist is empty\n");return -1;}int len = GetSizeSeqList(list);int i = 0 ;for(i=0;i<len;i++){if(0==strcmp(list->head[i].name,name)){return i;}}return -1;
}

9. ModifySeqList 修改表内某个内容

int ModifySeqList(SeqList *list, char *old, DATATYPE *newdata)
{if(NULL == list){fprintf(stderr,"ModifySeqList error,list is null\n");return 1;}int ret = FindSeqList(list,old);if(-1 == ret){fprintf(stderr,"modify error,can't find\n");return 1;}DATATYPE* tmp = GetSeqListItem(list,ret);memcpy(tmp,newdata,sizeof(DATATYPE));return 0;
}

10. DeleteSeqList 删除表的内容

int DeleteSeqList(SeqList *list, char *name)
{if(NULL == list){fprintf(stderr,"DeleteSeqList error,list is null\n");return 1;}int ret = FindSeqList(list,name);if(-1 == ret){return 1;}else{int i = 0 ;for(i =ret; i <GetSizeSeqList(list)-1 ; i++){memcpy(&list->head[i] ,&list->head[i+1],sizeof(DATATYPE));}}list->clen--;return 0 ;
}

11. ClearSeqList 把表清空

int CleanSeqList(SeqList *list)
{if(NULL == list){fprintf(stderr,"CleanSeqList error,list is null\n");return 1;}list->clen = 0 ;return 0;
}

main.c

#include <stdio.h>
#include "seqlist.h"
int main()
{SeqList* sl = CreateSeqList(10);DATATYPE data[5]={{"zhangsan",'m',20,70},{"lisi",'f',21,60},{"wangmazi",'m',25,80},{"liubei",'f',30,85},{"caocao",'f',40,90},};InsertTailSeqList(sl,&data[0]);InsertTailSeqList(sl,&data[1]);InsertTailSeqList(sl,&data[2]);printf("----------------show------------------\n");ShowSeqList(sl);printf("----------------find------------------\n");char find_name[50]="lisi";int ret = FindSeqList(sl,find_name);if(-1 == ret){printf("can't find person ,%s\n",find_name);}else{DATATYPE* tmp   =  GetSeqListItem(sl,ret) ;printf("name:%s score:%d\n",tmp->name,tmp->score);}printf("----------------pos------------------\n");InsertPosSeqList(sl,&data[3],3);ShowSeqList(sl);printf("----------------modify------------------\n");ModifySeqList(sl,"li1si",&data[4]);ShowSeqList(sl);printf("----------------delete------------------\n");DeleteSeqList(sl,"zhangsan");ShowSeqList(sl);DestroySeqList(sl);printf("Hello World!\n");return 0;
}