day19-线性表（顺序表）（链表I）

一、补充

• 安装软件命令： sudo apt-get install  (软件名)

1. 安装格式化对齐：sudo apt-get install clang-format
2. 内存泄漏检测工具： sudo apt-get install valgrind

        编译后，使用命令         valgrind ./a.out        即可看内存是否泄露

二、 顺序表的基本操作

        表头结构是可选项，但最好在使用中加上；

#ifndef _SEQLIST_H_
#define _SEQLIST_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 ModifySeqList(SeqList *list, char *old, DATATYPE *newdata);
//根据名字，删除指定元素
int DeleteSeqList(SeqList *list, char *name);
//清空表，清空表中已有元素
int ClearSeqList(SeqList *list);
//获得表中有效元素的个数
int GetSizeSeqList(SeqList *list);
//获得指定小标的元素本身
DATATYPE *GetItemSeqList(SeqList *list, int ind);
#endif

2.1 创建顺序表

SeqList *CreateSeqList(int len)
{SeqList *sl = malloc(sizeof(SeqList));if (NULL == sl){fprintf(stderr, "CreateSeqList malloc error\n");return NULL;}sl->head = malloc(sizeof(DATATYPE) * len);if (NULL == sl->head){fprintf(stderr, "CreateSeqList malloc2 error\n");return NULL;}sl->tlen = len;sl->clen = 0;return sl;
}

2.2 判断是否已满

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

2.3  尾插，在顺序表最后插入元素

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

2.4  遍历顺序表

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

2.5 获得表中有效元素的个数

int GetSizeSeqList(SeqList *list) 
{ return list->clen; 
}

2.6 判断表是否为空表

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

2.7 根据名字，查找元素

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

 2.8 获得指定下标的元素本身

DATATYPE *GetItemSeqList(SeqList *list, int ind)
{if (NULL == list){return NULL;}int len = GetSizeSeqList(list);if (ind < 0 || ind >= len){return NULL;}return &list->head[ind];
}

2.9 按指定位置插入元素

int InsertPosSeqList(SeqList *list, DATATYPE *data, int pos)
{if (IsFullSeqList(list)){return 1;}int len = GetSizeSeqList(list);if (pos < 0 || pos > len){return 1;}int i = 0;for (i = list->clen; i > pos; i--){// Head[i] = head[i - 1];memcpy(&list->head[i], &list->head[i - 1], sizeof(DATATYPE));}memcpy(&list->head[pos], data, sizeof(DATATYPE));list->clen++;return 0;
}

2.10  根据名字，删除指定元素

int DeleteSeqList(SeqList *list, char *name)
{if (IsEmptySeqList(list)){return 1;}int ret = FindSeqList(list, name);if (-1 == ret){printf("not find\n");return 1;}else{int len = GetSizeSeqList(list);int i;for (i = ret; i < len - 1; i++){memcpy(&list->head[i], &list->head[i + 1], sizeof(DATATYPE));}list->clen--;}return 0;
}

2.11 根据名字，修改指定元素

int ModifySeqList(SeqList *list, char *old, DATATYPE *newdata)
{if (IsEmptySeqList(list)){return 1;}int ret = FindSeqList(list, old);if (-1 == ret){printf("not find\n");return 1;}memcpy(&list->head[ret], newdata, sizeof(DATATYPE));return 0;
}

 2.12 清空表，清空表中已有元素

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

2.13 销毁顺序表

int DestroySeqList(SeqList *list)
{if (NULL == list){return 1;}free(list->head);free(list);return 0;
}

三、 线性表顺序存储的优点，缺点

3.1 优点

1. 无需为表中的逻辑关系增加额外的存储空间
2. 可以快速随机访问元素O(1)

3.2 缺点

1. 插入，删除元素需要移动元素o(n)
2. 无法动态存储

四、 链表（线性表的链式存储）

        目的：解决顺序存储的缺点，插入和删除，动态存储问题

•  特点：

1. 线性表链式存储结构的特点是一组任意的存储单位存储线性表的数据元素，存储单元可以是连续的，也可以不连续;
2. 可以被存储在任意内存未被占用的位置上,所以前面的顺序表只需要存储数据元素信息就可以了。在链式结构中还需要一个元素存储下一个元素的地址
3. 为了表示每个数据元素，a[i]与其直接后继数据元素a[i+1]之间的逻辑关系，                         对a[i]来说，除了存储其本身的信息外，还需要存一个指示器直接后续的信息。
4. 我们把存储元素信息的域叫数据域，把存储直接后继位置的域叫指针域。这两部分信息组成数据元素ai的存储映像，叫结点(Node);

4.1 单向链表

• next指针指向整个结点开始位置
• 自定义类型不支持嵌套定义，因为不知道分配多大的内存空间；即在typedef srtuct node中，struct node next;不可取                    但*next可取
• 内存中开辟空间，用指针去接表头结构

typedef struct
{char name[10];char sex;int age;int score;
}DATATYPE;typedef struct _node_
{DATATYPE data;struct _node_ *next;
}LinkNode;typedef struct
{LinkNode *head;int clen;
}LinkList;

4.1.1 创建链表

LinkList *CreateLinklist()
{LinkList *ll = malloc(sizeof(LinkList));if(NULL == ll){fprintf(stderr, "CreateLinklist malloc");return NULL;}ll->head = NULL;ll->clen = 0;return ll;
}

4.1.2  判断链表是否为空

int IsEmptyLinkList(LinkList *ll)
{return  0 == ll->clen ;
}

4.1.3 头插法

（1）链表为空(直接将head指向newnode)

（2） 链表非空

int InsertHeadLinkList(LinkList *ll, DATATYPE *data)
{LinkNode *newnode = malloc(sizeof(LinkNode));if(NULL == newnode){fprintf(stderr, "InsertHeadLinkList malloc");return 1;}memcpy(&newnode->data, data, sizeof(DATATYPE));newnode->next = NULL;if(IsEmptyLinkList(ll)){ll->head = newnode;}else{newnode->next = ll->head;ll->head = newnode;}ll->clen++;return 0;
}

 4.1.4 获得表中有效元素的个数

int GetSizeLinkList(LinkList *ll)
{return ll->clen;
}

4.1.5 遍历表中元素

• 使tmp->next来进行遍历，借助循环 

int ShowLinkList(LinkList *ll)
{int len = GetSizeLinkList(ll);LinkNode *tmp = ll->head;int i;for(i = 0; i < len; ++i){printf("%s %c %d %d \n", tmp->data.name, tmp->data.sex,tmp->data.age, tmp->data.score);tmp = tmp->next;}return 0;
}

4.1.6 根据名字，寻找元素

DATATYPE *FindLinkList(LinkList *ll, char *name)
{LinkNode *tmp = ll->head;while (tmp) {if(0 == strcmp(tmp->data.name, name)){return &tmp->data;}tmp = tmp->next;}return NULL;
}

4.1.7 根据名字，删除元素

• 通过比较tmp下一个的内容来控制，使tmp停于待删结点的前一个结点 

int DeleteLinkList(LinkList* ll, char* name)
{LinkNode* tmp = ll->head;if (IsEmptyLinkList(ll)){return 1;}if (0 == strcmp(tmp->data.name, name)){ll->head = ll->head->next;free(tmp);ll->clen--;return 0;}while (tmp->next){if (0 == strcmp(tmp->next->data.name, name)){LinkNode* tmp2 = tmp->next;tmp->next = tmp->next->next;free(tmp2);ll->clen--;return 0;}tmp = tmp->next;}return 1;
}