順序表和鏈表?優缺點
存儲方式：
順序表是一段連續的存儲單元
鏈表是邏輯結構連續物理結構（在內存中的表現形式）不連續
時間性能，
查找順序表O(1)：下標直接查找
鏈表??O(n)：從頭指針往后遍歷才能找到
插入和刪除：
順序表?O(n)：需要整體元素移動后插入
鏈表???O(1)：只需改指定位置指針指向即可。

空間性能
順序表?需要預先分配空間，大小固定
鏈表，?不需要預先分配，大小可變，動態分配


循環鏈表
簡單的來說，就是將原來單鏈表中最有一個元素的next指針指向第一個元素或頭結點，鏈表就成了一個環，頭尾相連，就成了循環鏈表。circultlar?linker?list。

雙向鏈表：

如圖：每個節點都包含三部分，數據，指向下個節點的指針，指向上個節點的指針。

Makefile：工程管理工具。

預處理、編譯、匯編生產obj、鏈接

a.out：main.c ./doubleLinklist.c

????????gcc main.c doubleLinklist.c

Clean:

????????rm a.out.

保存后按make命令默認走第一條規則生成a.out

按make clean清除a.out

#代表源文件

SRC += main.c

SRC +=doulink.c

DST = app

CC = gcc

FLAG = -g

LIB=-lm

$(DST):$(SRC)

????????$(CC) ?$(SRC) $(FLAG) $(LIB) -o $(DST)

clean

????????rm $(DST)

指定文件：make -f makefile2

今天寫了雙向鏈表相關操作的函數：

#include "doulink.h"

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

struct DouLinkList* CreateDouLinkList()//創建雙向鏈表

{

????struct DouLinkList* dl = (struct DouLinkList*) malloc(sizeof(struct DouLinkList));

????if(NULL == dl)

????{

????????fprintf(stderr,"CreateDouLinkList malloc\n");

????????return NULL;

????}

????dl->head = NULL;

????dl->clen = 0;

????return dl;

}

int InsertHeadDouLinkList(struct DouLinkList* dl, struct DATATYPE* data)//雙向鏈表頭查

{

????struct DouNode * newnode = ??(struct DouNode*)malloc(sizeof(struct DouNode));

????if(NULL == newnode)

????{

????????fprintf(stderr,"inserthead malloc\n");

????????return 1;

????}

????memcpy(&newnode->data,data,sizeof(struct DATATYPE));

????newnode->next = NULL;

????newnode->prev = NULL;

????newnode->next = dl->head;

????if(dl->head)

????{

????????dl->head->prev = newnode;

????}

????dl->head ?= newnode;

????dl->clen++;

????return 0;

}

int ShowDouLinkList(struct DouLinkList* dl,DIR dir)//雙向鏈表遍歷

{

????struct DouNode* tmp = dl->head;

????if( FORWADR==dir)

????{

????????while(tmp)

????????{

????????????printf("%s %c %d %d\n",tmp->data.name,tmp->data.sex,tmp->data.age,tmp->data.score);

????????????tmp=tmp->next;

????????}

????}

????else if(BACKWADR == dir)

????{

????????while(tmp->next)

????????{

????????????tmp=tmp->next;

????????} // end node

????????while(tmp)

????????{

????????????printf("%s %c %d %d\n",tmp->data.name,tmp->data.sex,tmp->data.age,tmp->data.score);

????????????tmp=tmp->prev;

????????}

????}

????return 0;

}

int InsertTailDouLinkList(struct DouLinkList*dl,struct DATATYPE*data)//雙向鏈表尾插

{

????if(IsEmptyDouLinkList(dl))

????{

????????return InsertHeadDouLinkList(dl,data);

????}

????else ?

????{

????????struct DouNode* tmp = dl->head ;

????????while(tmp->next)

????????{

????????????tmp= tmp->next;

????????}

????????struct DouNode* newnode = (struct DouNode*)malloc(sizeof(struct DouNode));

????????if(NULL == newnode)

????????{

????????????fprintf(stderr,"InsertTailDouLinkList malloc\n");

????????????return 1;

????????}

????????//初始化節點

????????memcpy(&newnode->data,data,sizeof(struct DATATYPE));

????????newnode->next ?= NULL;

????????newnode->prev = NULL;

???????// 連接鏈表

????????newnode->prev ?= tmp;

????????tmp->next ?= newnode;

????????dl->clen++;

????}

????return 0;

}

int InsertPosDouLinkList(struct DouLinkList*dl,struct DATATYPE*data,int pos)//雙向鏈表指定位置插入元素

{

????int len = GetSizeDouLinkList(dl);

????

????if(pos<0 || pos>len)

????{

????????return 1;

????}

????if(0 == pos)

????{

????????return InsertHeadDouLinkList(dl,data);

????}

????else if(pos == len)

????{

????????return InsertTailDouLinkList(dl,data);

????}

????else

????{

????????struct DouNode* tmp = dl->head;

????????int i = 0 ;

????????for(i = 0 ;i<pos;++i)

????????{

????????????tmp=tmp->next;

????????}

????????struct DouNode* newnode = (struct DouNode*)malloc(sizeof(struct DouNode));

????????if(NULL == newnode)

????????{

????????????fprintf(stderr,"InsertposDouLinkList malloc\n");

????????????return 1;

????????}

????????memcpy(&newnode->data , data,sizeof(struct DATATYPE));

????????newnode->next ?= NULL;

????????newnode->prev ?= NULL;

????????newnode->next ?= tmp;

????????newnode->prev ?= tmp->prev;

????????tmp->prev = newnode;

????????newnode->prev->next ?= newnode;

????????dl->clen++;

????}

????return 0;

}

int IsEmptyDouLinkList(struct DouLinkList*dl)//雙向鏈表是否為空

{

????return 0 == dl->clen;

}

int GetSizeDouLinkList(struct DouLinkList*dl)//雙向鏈表長度獲取

{

????return dl->clen;

}

struct DouNode* FindDouLinkList(struct DouLinkList* dl,char *name)//查找元素

{

????if(IsEmptyDouLinkList(dl))

????{

????????return NULL;

????}

????struct DouNode* tmp = dl->head;

????int len = GetSizeDouLinkList(dl);

????int i = 0 ;

????for(i = 0 ;i< len; ++i)

????{

????????if(0 == strcmp(tmp->data.name,name))

????????{

????????????return tmp;

????????}

????????tmp= tmp->next;

????}

????return NULL;

}

int ModifyDouLinkList(struct DouLinkList* dl,char *name,struct DATATYPE* data)//修改元素

{

????struct DouNode* ret = FindDouLinkList(dl,name);

????if(NULL == ret)

????{

????????return 1;

????}

????memcpy(&ret->data,data,sizeof(struct DATATYPE));

????return 0;

}