day20-线性表（链表II）

一、调试器

1.1 gdb（调试器）

        在程序指定位置停顿

1.1.1 一般调试

        gcc直接编译生成的是发布版（Release）

1. gcc -g        //-g调式版本，（体积大，内部有源码）（DeBug）
   1. gcc -g main.c linklist.c
2. gdb a.out  //a.out指代可执行文件
3. b fun.c: 36 //设置断点，运行到该位置程序自动停
   1. b InsertPosLinklist
   2. b linklist.c:137
4. r           运行
5. n         // 执行下一步              n     s    //步入函数，自定义函数
6. 使用p命令，查看变量或指针等数据
   1. p *data
   2. p len
7. 按q退出
8. 输入list   //查看源码，默认Main.c，一次十行，按回车查看后十行

1.1.2 找段错误

1. gcc -g main.c linklist.c
2. gdb a.out
3. 按r直接运行
4. 重现错误
5. where找出段错误位置

二、链表（续，见day19）

2.1 单链表

2.1.1 尾插

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

2.1.2 指定位置插

（1）在首位插入，头插

（2）在最后插入，尾插

（3）中间插：

int InsertPosLinkList(LinkList *ll, DATATYPE *data, int pos)
{int len = GetSizeLinkList(ll);if(pos < 0 || pos > len){return 1;}if(0 == pos){return InsertHeadLinkList(ll, data);}else if(pos == len){return InsertTailLinkList(ll, data);}else {LinkNode *tmp =ll->head;LinkNode *newnode = malloc(sizeof(LinkNode));if(NULL == newnode){fprintf(stderr, "InsertPosLinkList malloc");return 1;}memcpy(&newnode->data, data, sizeof(DATATYPE));newnode->next = NULL;int i;for(i = 0; i < pos - 1;++i){tmp = tmp->next;}newnode->next = tmp->next;tmp->next = newnode;ll->clen++;}return 0;}

2.1.3 更改结点信息

int ModifyLinkList(LinkList*ll,char*name,DATATYPE*data)
{DATATYPE * tmp = FindLinkList(ll, name);if(NULL == tmp){return 1;}memcpy(tmp,data,sizeof(DATATYPE));return 0;
}

2.1.4 销毁链表

int DestroyLinkList(LinkList*ll)
{while(1){LinkNode *tmp = ll->head;if(tmp == NULL){break;}ll->head = ll->head->next;free(tmp);}free(ll);return 0;
}

2.2 单链表练习

2.2.1 找中间值

2.2.2 找倒数第k个元素

2.2.3 链表的逆序 

 2.2.4 链表的排序（插入排序）

2.2.5 判断是否为环形链表

 三、顺序表和链表对比

3.1存储方式

        顺序表 是一段连续的存储单元
        链表     是逻辑结构连续物理结构（在内存中的表现形式）不连续

3.2 时间性能

        查找 ：          顺序表O(1)         链表  O(n)

        插入和删除：顺序表 O(n)        链表   O(1)

3.3 空间性能

        顺序表 需要预先分配空间，大小固定
        链表， 不需要预先分配，大小可变，动态分配

3.4 循环链表

        简单的来说，就是将原来单链表中最有一个元素的next指针指向第一个元素或头结点，链表就成了一个环，头尾相连，就成了循环链表。circultlar linker list.
        注意非空表，和空表。多数会加入头结点。
        原来结束的条件是 p->next != NULL ------->>>>> p-next != Head