一、調試器
1.1 gdb(調試器)
? ? ? ? 在程序指定位置停頓
1.1.1 一般調試
? ? ? ? gcc直接編譯生成的是發布版(Release)
- gcc -g? ? ? ? //-g調式版本,(體積大,內部有源碼)(DeBug)
- gcc -g main.c linklist.c
- gdb a.out? //a.out指代可執行文件
- b fun.c: 36 //設置斷點,運行到該位置程序自動停
- b InsertPosLinklist
- b linklist.c:137
- r? ? ? ? ? ?運行
- n? ? ? ? ?// 執行下一步? ? ? ? ? ? ? n? ? ?s? ? //步入函數,自定義函數
- 使用p命令,查看變量或指針等數據
- p *data
- p len
- 按q退出
- 輸入list? ?//查看源碼,默認Main.c,一次十行,按回車查看后十行
1.1.2 找段錯誤
- gcc -g main.c linklist.c
- gdb a.out
- 按r直接運行
- 重現錯誤
- 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?
?? ??? ??? ?
?? ??? ??? ?
?? ??? ??? ?
?? ??? ?
?