1 原理
順序表的缺點：
- 插入和刪除移動大量元素
- 數組的大小不好控制
- 占用一大段連續的存儲空間，造成很多碎片
鏈表規避了上述順序表缺點
邏輯上相鄰的兩個元素在物理位置上不相鄰
頭結點
L：頭指針
頭指針：鏈表中第一個結點的存儲位置，用來標識單鏈表。
頭結點：在單鏈表第一個結點之前附加的一個結點，為了操作上的方便。
? ?若鏈表有頭結點，則頭指針永遠指向頭結點，不論鏈表是否為空，頭指針均不為空，頭指針是鏈表的必須元素，他標識一個鏈表。頭結點是為了操作的方便而設立的，其數據域一般為空，或者存放鏈表的長度。有頭結點后，對在第一結點前插入和刪除第一結點的操作就統一了，不需要頻繁 重置頭指針。但頭結點不是必須的。
?優缺點
優點：
- 插入和刪除操作不需要移動元素，只需要修改指針
- 不需要大量的連續存儲空間
缺點：
- 單鏈表附加指針域，也存在浪費存儲空間的缺點
- 查找操作時需要從表頭開始遍歷，依次查找，不能隨機存取
2 表示
2.1 定義
typedef int ElemType ;typedef struct LNode{ //單鏈表結點類型ElemType data; //數據域struct LNode* next;//指針域
}LNode, *LinkList;2.2 新建鏈表
2.2.1 頭插法新建鏈表
void list_head_insert(LinkList &L)
{ElemType x;LNode *s;L= (LinkList)malloc(sizeof(LNode));//申請頭節點空間L->next = NULL;scanf("%d",&x);while(x!=9999){s= (LinkList)malloc(sizeof(LNode));//申請節點空間s->data = x;s->next = L->next;//指向原本第一個節點L->next = s; //頭結點的nextscanf("%d",&x);}
}?2.2.2 尾插法新建鏈表
void list_tail_insert(LinkList &L)
{L= (LinkList)malloc(sizeof(LNode));//申請頭節點空間ElemType x;LNode *s, *r = L;//s是用來指向新節點，r始終指向鏈表尾部L->next = NULL;scanf("%d", &x);while(x!=9999){s = (LinkList) malloc(sizeof(LNode));s->data=x;r->next = s;r=s;scanf("%d", &x);}r->next=NULL;//讓為節點的next=NULL}?2.3 打印鏈表
void print_list(LinkList L)
{L = L->next;while(L != NULL){printf("%3d",L->data);L =L->next;}printf("\n");
}2.4 查找
2.4.1 按位置查找
頭節點代表第0個位置
?
//按位置查找
LinkList GetElem(LinkList L, int SearchPos)
{int i = 0;if(SearchPos < 0){return NULL;}while(L && i < SearchPos){L = L->next;i++;}return L;
}
2.4.2 按值查找
//按值 查找
LinkList LocateElem(LinkList L, ElemType SearchVal)
{while(L){if(L->data ==SearchVal){return L;}else{L =L->next;}}return NULL;}?2.5 插入
插入情況?
?
bool ListFrontInsert(LinkList L, int InsertPose, ElemType InsertValue)
{LinkList p = GetElem(L, InsertPose-1);if(p == NULL){return false;}LinkList q ;q =(LinkList)malloc(sizeof(LNode));q->data = InsertValue;q->next = p->next;p->next = q;return true;}
2.6 刪除
刪除注意的點：
- 需要釋放刪除節點的空間
- 需要判斷刪除的位置是否存在
???????
void dele_elem(ListLink L, int pos) {if (pos <0) {return ;}ListLink r,q; //q用來存儲要刪除的節點r = find_elem(L, pos -1);if (NULL == r) {return;}q=r->next;if (q==NULL){return;}r->next = q->next;//斷鏈free(q);q = NULL;//防止野指針
}引用：要不要對變量進行賦值，如果不用不加引用，若要加引用
)
