看了這個媽媽再也不擔心我的鏈表啦QVQ.....
3.1鏈表的定義
找了一堆感覺都是廢話
3.2動態記憶體分配
malloc:
fp = (資料型別*)malloc(sizeof(資料型別))
free:
free(void *fp)
3.3鏈表的建立
typedef struct list
{
int num;
struct list *next;
}node;
typedef node *link;
?
link creat_list(int n)
{
link head;
link ptr;
int i;
?
head = (link)malloc(sizeof(node));
if(!head)
{
cout << "記憶體分配失敗" << endl;
return 0;
}
head->next = NULL;
ptr = head;
?
cout << "輸入n個資料" << endl;
for(i = 1; i <= n; ++i)
{
scanf("%d", &ptr->num);
ptr->next = (link)malloc(sizeof(node));
if(!ptr->next)
{
cout << "記憶體分配失敗" << endl;
return 0;
}
ptr->next->next = NULL;
ptr = ptr->next;
}
return head;
}
3.4鏈表的遍歷
link find_node(link head, int num)
{
link ptr;
ptr = head;
while (ptr != NULL)
{
if(ptr->num == num)
return ptr;
ptr = ptr->next;
}
cout << "node" << endl;
return ptr;
}
3.5鏈表的連接
link concatenate(link ptr1, link ptr2)
{
link ptr;
ptr = ptr1;
while(ptr->next != NULL) //讓ptr1的尾巴指向ptr2的頭
ptr = ptr->next;
ptr->next = ptr2;
return ptr1;
}
3.6鏈表內節點的洗掉
三種情況:
-
洗掉第一個節點
-
洗掉最后一個節點
-
洗掉中間節點
link delete_node(link head, link ptr)
{
link previous;
if(ptr == head) //刪頭
return head->next;
else
{
previous = head;
while (previous->next != ptr)
{
previous = previous->next;
}
previous->next = ptr->next;
}
free(ptr); //有借有還,再借不難
return head;
}
3.7釋放鏈表的記憶體空間
link destroy_list(link head)
{
link ptr;
while(head != NULL)
{
ptr = head;
head = head->next;
free(ptr);
}
}
3.8鏈表內節點的插入
與洗掉一樣會有三種情況
link insert_node(link head, link ptr, int value) //插入在ptr之后
{
link new_node = (link)malloc(sizeof(node));
if(!new_node)
{
cout << "分配記憶體失敗" << endl;
return NULL;
}
new_node->num = value;
new_node->next = NULL;
if(ptr == NULL) //頭插
{
new_node->next = head;
return new_node;
}
else
{
if(ptr->next == NULL) //尾插
ptr->next = new_node;
else //中間插
{
new_node->next = ptr->next;
ptr->next = new_node;
}
}
return head;
}
3.9鏈表結構的反轉
link invert_list(link head)
{
link mid, last;
mid = NULL;
while(head != NULL)
{
last = mid;
mid = head;
head = head->next;
mid->next = last;
}
return mid;
}
讓我們看看具體是怎么來的:
-
執行while之前 head指向鏈表第一個 mid == NULL, last無值
-
執行一次 head指向鏈表第二個 mid 指向 鏈表第一個 last == NULL
-
再執行一次 head指向鏈表第三個 mid 指向 鏈表第二個 last 指向 鏈表第一個 并且 mid的前驅是last
-
反復直到反轉完成 回傳mid 也就是反轉后的頭節點
3.10回圈鏈表結構
頭尾相連的鏈表
3.10.1首先建立鏈表
typedef struct clist
{
int data;
struct clist *next;
}cnode;
typedef cnode *clink;
?
clink creat_list(int n)
{
clink head;
clink ptr;
int i;
?
head = (clink)malloc(sizeof(cnode));
if(!head)
{
cout << "記憶體分配失敗" << endl;
return 0;
}
head->next = NULL;
ptr = head;
?
cout << "輸入n個資料" << endl;
for(i = 1; i <= n; ++i)
{
scanf("%d", &ptr->data);
ptr->next = (clink)malloc(sizeof(cnode));
if(!ptr->next)
{
cout << "記憶體分配失敗" << endl;
return 0;
}
ptr->next->next = NULL;
ptr = ptr->next;
}
ptr->next = NULL;
return head;
}
3.10.2回圈鏈表內節點的插入
-
情況一 :插在鏈表的頭部成為鏈表的新開始
-
將新節點的指標指向鏈表的第一個節點
-
找到最后一個節點且將其指標指向新節點
-
回傳新節點 為鏈表新頭部
-
-
情況二:除情況一的其他情況,假設插在ptr之后
-
將新節點的指標指向ptr下一節點
-
將ptr的下一節點設為新節點
-
clink insert_node(clink head, clink ptr, int value)
{
clink new_node = (clink)malloc(sizeof(cnode));
clink previous;
if(!new_node)
{
cout << "分配記憶體失敗" << endl;
return NULL;
}
new_node->data = value;
new_node->next = NULL;
if(head == NULL) //原先就是空表
{
new_node->next = new_node;
return new_node;
}
if(ptr == NULL) // 頭插
{
new_node->next = head;
previous = head;
while(previous->next != NULL)
previous = previous->next;
previous->next = new_node;
head = new_node;
}
else
{
new_node->next = ptr->next;
ptr->next = new_node;
}
return head;
}
3.10.3回圈鏈表內節點的洗掉
-
情況一:刪第一個
-
將鏈表的開始移向下一節點
-
將最后一個節點指向第二個節點
-
-
情況二:除情況一的其他情況,洗掉ptr
-
找到ptr的前一個節點
-
將ptr前一個節點的后繼設為ptr的后繼
-
clink delete_node(clink head, clink ptr)
{
clink previous;
if(head == NULL) //空表
return NULL;
previous = head;
if(head != head->next) //不止一個節點
while(previous->next != ptr)
previous = previous->next;
?
if(ptr == head) //頭插
{
head = head->next;
previous->next = ptr->next;
}
else
{
previous->next = ptr->next;
}
free(ptr);
return head;
}
3.11雙向鏈表結構
3.11.1雙向鏈表的建立
倆個指標,一個指向前驅,一個指向后繼
typedef struct dlist
{
int data;
struct dlist *front; //后繼
struct dlist *back; //前驅
}dnode;
typedef dnode *dlink;
?
dlink create_dlist(int *arr, int len)
{
dlink head, before, new_node;
int i;
head = (dlink)malloc(sizeof(dnode));
if(!head)
{
cout << "記憶體分配失敗" << endl;
return NULL;
}
head->data = arr[0];
head->back = NULL;
head->front = NULL;
before = head;
for(i = 1; i < len; ++i)
{
new_node = (dlink)malloc(sizeof(dnode));
new_node->data = arr[i];
new_node->front = NULL;
new_node->back = before;
before = new_node;
}
return head;
}
3.11.2雙向鏈表的插入
-
情況一:頭插
-
將新節點的指標front指向雙向鏈表的開始
-
將表頭的back指向新節點
-
head = new_node
-
-
情況二:尾插
-
將最后一個節點的front指向新節點
-
新節點的back指向尾部
-
-
情況三:中間插,假設在ptr之后
-
新節點的前驅指向ptr
-
新節點的后繼變為ptr的后繼
-
ptr的后繼指向新節點
-
原ptr后繼的前驅指向新節點
-
dlink insert_node(dlink head, dlink ptr, int value)
{
dlink new_node = (dlink)malloc(sizeof(dnode));
if(!new_node)
{
cout << "記憶體分配失敗" << endl;
return NULL;
}
new_node->back = NULL;
new_node->front = NULL;
new_node->data = value;
if(head == NULL) //空表
return new_node;
if(ptr == NULL) //頭插
{
new_node->front = head;
head->back = new_node;
head = new_node;
}
else
{
if(ptr->front == NULL) //尾插
{
ptr->front = new_node;
new_node->back = ptr;
}
else
{
ptr->front->back = new_node;
new_node->front = ptr->front;
new_node->back = ptr;
ptr->front = new_node;
}
}
return head;
}
3.11.3雙向鏈表節點的洗掉
-
情況一:刪頭
-
將指向鏈表開始節點的指標head指向第二個節點
-
將第二個節點的前驅設為NULL
-
-
情況二:刪尾
-
最后一節點的后繼設為NULL
-
-
情況三:刪中間,洗掉ptr
-
ptr前驅的后繼設為ptr后繼的前驅
-
ptr后繼的前驅設為ptr前驅的后繼
-
dlink delete_node(dlink head, dlink ptr)
{
if(ptr->back == NULL) //刪頭
{
head = head->front;
head->back = NULL;
}
else
{
if(ptr->front == NULL) //刪尾
{
ptr->back->front == NULL;
}
else
{
ptr->back->front = ptr->front;
ptr->front->back = ptr->back;
}
}
free(ptr);
return head;
}
3.12回圈雙向鏈表
3.12.1建立
typedef struct dlist
{
int data;
struct dlist *front; //后繼
struct dlist *back; //前驅
}cdnode;
typedef cdnode *cdlink;
?
cdlink create_dlist(int *arr, int len)
{
cdlink head, before, new_node;
int i;
head = (cdlink)malloc(sizeof(cdnode));
if(!head)
{
cout << "記憶體分配失敗" << endl;
return NULL;
}
head->data = arr[0];
head->back = NULL;
head->front = NULL;
before = head;
for(i = 1; i < len; ++i)
{
new_node = (cdlink)malloc(sizeof(cdnode));
new_node->data = arr[i];
new_node->front = NULL;
new_node->back = before;
before = new_node;
}
head->back = new_node;
new_node->front = head;
//head->back = NULL;
//new_node->front = NULL;
return head;
}
-
情況一:洗掉或插入第一個節點
-
情況二:除情況一
3.12.2洗掉
cdlink delete_node(cdlink head, cdlink ptr)
{
if(head == NULL)
return NULL;
if(ptr == head) head = head->front; //頭
ptr->back->front = ptr->front;
ptr->front->back = ptr->back;
free(ptr);
return head;
}
3.12.3插入
cdlink insert_node(cdlink head, cdlink ptr, int value)
{
cdlink new_node = (cdlink)malloc(sizeof(cdnode));
if(!new_node)
{
cout << "記憶體分配失敗" << endl;
return NULL;
}
new_node->data = value;
if(head == NULL) //空表
{
new_node->back = new_node;
new_node->front = new_node;
return new_node;
}
if(ptr == NULL) //頭插
{
head->back->front = new_node;
new_node->front = head;
new_node->back = head->back;
head->back = new_node;
head = new_node;
}
else
{
ptr->front->back = new_node;
new_node->front = ptr->front;
new_node->back = ptr;
ptr->front = new_node;
}
return head;
}
最后代碼大匯總
#include <bits/stdc++.h>
using namespace std;
typedef struct list
{
int num;
struct list *next;
}node;
typedef node *link;
link creat_list(int n)
{
link head;
link ptr;
int i;
head = (link)malloc(sizeof(node));
if(!head)
{
cout << "記憶體分配失敗" << endl;
return 0;
}
head->next = NULL;
ptr = head;
cout << "輸入n個資料" << endl;
for(i = 1; i <= n; ++i)
{
scanf("%d", &ptr->num);
ptr->next = (link)malloc(sizeof(node));
if(!ptr->next)
{
cout << "記憶體分配失敗" << endl;
return 0;
}
ptr->next->next = NULL;
ptr = ptr->next;
}
return head;
}
link find_node(link head, int num)
{
link ptr;
ptr = head;
while (ptr != NULL)
{
if(ptr->num == num)
return ptr;
ptr = ptr->next;
}
cout << "node" << endl;
return ptr;
}
link concatenate(link ptr1, link ptr2)
{
link ptr;
ptr = ptr1;
while(ptr->next != NULL)
ptr = ptr->next;
ptr->next = ptr2;
return ptr1;
}
link delete_node(link head, link ptr)
{
link previous;
if(ptr == head)
return head->next;
else
{
previous = head;
while (previous->next != ptr)
{
previous = previous->next;
}
previous->next = ptr->next;
}
free(ptr);
return head;
}
link destroy_list(link head)
{
link ptr;
while(head != NULL)
{
ptr = head;
head = head->next;
free(ptr);
}
}
link insert_node(link head, link ptr, int value) //插入在ptr之后
{
link new_node = (link)malloc(sizeof(node));
if(!new_node)
{
cout << "分配記憶體失敗" << endl;
return NULL;
}
new_node->num = value;
new_node->next = NULL;
if(ptr == NULL) //頭插
{
new_node->next = head;
return new_node;
}
else
{
if(ptr->next == NULL) //尾插
ptr->next = new_node;
else //中間插
{
new_node->next = ptr->next;
ptr->next = new_node;
}
}
return head;
}
link invert_list(link head)
{
link mid, last;
mid = NULL;
while(head != NULL)
{
last = mid;
mid = head;
head = head->next;
mid->next = last;
}
return mid;
}
int main()
{
return 0;
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef struct clist
{
int data;
struct clist *next;
}cnode;
typedef cnode *clink;
clink creat_list(int n)
{
clink head;
clink ptr;
int i;
head = (clink)malloc(sizeof(cnode));
if(!head)
{
cout << "記憶體分配失敗" << endl;
return 0;
}
head->next = NULL;
ptr = head;
cout << "輸入n個資料" << endl;
for(i = 1; i <= n; ++i)
{
scanf("%d", &ptr->data);
ptr->next = (clink)malloc(sizeof(cnode));
if(!ptr->next)
{
cout << "記憶體分配失敗" << endl;
return 0;
}
ptr->next->next = NULL;
ptr = ptr->next;
}
ptr->next = NULL;
//ptr->next = head;
return head;
}
clink insert_node(clink head, clink ptr, int value)
{
clink new_node = (clink)malloc(sizeof(cnode));
clink previous;
if(!new_node)
{
cout << "分配記憶體失敗" << endl;
return NULL;
}
new_node->data = https://www.cnblogs.com/xiguan/p/value;
new_node->next = NULL;
if(head == NULL) //原先就是空表
{
new_node->next = new_node;
return new_node;
}
if(ptr == NULL) // 頭插
{
new_node->next = head;
previous = head;
while(previous->next != NULL)
previous = previous->next;
previous->next = new_node;
head = new_node;
}
else
{
new_node->next = ptr->next;
ptr->next = new_node;
}
return head;
}
clink delete_node(clink head, clink ptr)
{
clink previous;
if(head == NULL) //空表
return NULL;
previous = head;
if(head != head->next) //不止一個節點
while(previous->next != ptr)
previous = previous->next;
if(ptr == head) //頭插
{
head = head->next;
previous->next = ptr->next;
}
else
{
previous->next = ptr->next;
}
free(ptr);
return head;
}
int main()
{
return 0;
}
#include <bits/stdc++.h>
using namespace std;
typedef struct dlist
{
int data;
struct dlist *front; //后繼
struct dlist *back; //前驅
}dnode;
typedef dnode *dlink;
dlink create_dlist(int *arr, int len)
{
dlink head, before, new_node;
int i;
head = (dlink)malloc(sizeof(dnode));
if(!head)
{
cout << "記憶體分配失敗" << endl;
return NULL;
}
head->data = https://www.cnblogs.com/xiguan/p/arr[0];
head->back = NULL;
head->front = NULL;
before = head;
for(i = 1; i < len; ++i)
{
new_node = (dlink)malloc(sizeof(dnode));
new_node->data = arr[i];
new_node->front = NULL;
new_node->back = before;
before = new_node;
}
return head;
}
dlink insert_node(dlink head, dlink ptr, int value)
{
dlink new_node = (dlink)malloc(sizeof(dnode));
if(!new_node)
{
cout <<"記憶體分配失敗" << endl;
return NULL;
}
new_node->back = NULL;
new_node->front = NULL;
new_node->data = https://www.cnblogs.com/xiguan/p/value;
if(head == NULL) //空表
return new_node;
if(ptr == NULL) //頭插
{
new_node->front = head;
head->back = new_node;
head = new_node;
}
else
{
if(ptr->front == NULL) //尾插
{
ptr->front = new_node;
new_node->back = ptr;
}
else
{
ptr->front->back = new_node;
new_node->front = ptr->front;
new_node->back = ptr;
ptr->front = new_node;
}
}
return head;
}
dlink delete_node(dlink head, dlink ptr)
{
if(ptr->back == NULL) //刪頭
{
head = head->front;
head->back = NULL;
}
else
{
if(ptr->front == NULL) //刪尾
{
ptr->back->front == NULL;
}
else
{
ptr->back->front = ptr->front;
ptr->front->back = ptr->back;
}
}
free(ptr);
return head;
}
int main()
{
return 0;
}
#include <bits/stdc++.h>
using namespace std;
typedef struct dlist
{
int data;
struct dlist *front; //后繼
struct dlist *back; //前驅
}cdnode;
typedef cdnode *cdlink;
cdlink create_dlist(int *arr, int len)
{
cdlink head, before, new_node;
int i;
head = (cdlink)malloc(sizeof(cdnode));
if(!head)
{
cout << "記憶體分配失敗" << endl;
return NULL;
}
head->data = https://www.cnblogs.com/xiguan/p/arr[0];
head->back = NULL;
head->front = NULL;
before = head;
for(i = 1; i < len; ++i)
{
new_node = (cdlink)malloc(sizeof(cdnode));
new_node->data = arr[i];
new_node->front = NULL;
new_node->back = before;
before = new_node;
}
head->back = new_node;
new_node->front = head;
//head->back = NULL;
//new_node->front = NULL;
return head;
}
cdlink delete_node(cdlink head, cdlink ptr)
{
if(head == NULL)
return NULL;
if(ptr == head) head = head->front; //頭
ptr->back->front = ptr->front;
ptr->front->back = ptr->back;
free(ptr);
return head;
}
cdlink insert_node(cdlink head, cdlink ptr, int value)
{
cdlink new_node = (cdlink)malloc(sizeof(cdnode));
if(!new_node)
{
cout <<"記憶體分配失敗" << endl;
return NULL;
}
new_node->data = https://www.cnblogs.com/xiguan/p/value;
if(head == NULL) //空表
{
new_node->back = new_node;
new_node->front = new_node;
return new_node;
}
if(ptr == NULL) //頭插
{
head->back->front = new_node;
new_node->front = head;
new_node->back = head->back;
head->back = new_node;
head = new_node;
}
else
{
ptr->front->back = new_node;
new_node->front = ptr->front;
new_node->back = ptr;
ptr->front = new_node;
}
return head;
}
int main()
{
return 0;
}
轉載請註明出處,本文鏈接:https://www.uj5u.com/houduan/20768.html
標籤:C++
上一篇:如何去掉cxgrid表格中Header,band里面的表格線,那個屬性可以控制?
下一篇:C++ 關鍵字decltype
